Geo-hashing with time

intersection.js

/*
 Example of an encrypted system in operation.  This works with a few
 assumptions that can be adjusted:
    * Getting within approximately 70' is close enough to note
    * "Infection" sticks around for 2 hours

 Questions can be directed to TripleBlind, Inc.  This code and algorithm
 is donated to the Private Kit project.

 Translated to JS from:
 https://github.com/tripleblindmarket/covid-safe-paths/blob/develop/app/encryption/intersection.py
 */

// npm -i node-forge buffer
const forge = require('node-forge')
const { Buffer } = require('buffer')

/*
 Intersection module constructor
 */
const IntersectionConstructor = () => {
  /**
   * Generates a random integer in the specified range, inclusive.
   * @param low
   * @param high
   * @returns {number}
   */
  const randomIntInc = (low, high) => {
    return Math.floor(Math.random() * (high - low + 1) + low)
  }

  /**
   * Generate a hash
   *
   * @param data
   * @param salt
   * @returns {string}
   */
  const pbkdf2_hmac = (data, salt) => {
    const hashComplexity = 100000
    const rawData = Buffer.from(data)
    const md = forge.md.sha256.create()
    const dk = forge.pkcs5.pbkdf2(rawData.toString('binary'), salt, hashComplexity, md.digestLength, md)
    const buff = Buffer.from(dk, 'binary')
    return buff.toString('hex')
  }

  /*
   * Infected User constructor
   */
  const infectedUser = () => {
    const salt = forge.random.getBytesSync(32)

    const infectedHelperGeneration = (location, thresholds) => {
      const distanceThreshold = thresholds[0]
      const timeThreshold = Math.floor(thresholds[1] / 2)
      const lat = Math.floor(location[0] * 10 ** 6)
      const long = Math.floor(location[1] * 10 ** 6)
      const time = Math.floor(location[2] + timeThreshold / 2)
      const template = [lat, long, time]
      const randomX = randomIntInc(
        Math.floor((-90 * 10 ** 6) / (2 * distanceThreshold)),
        Math.floor((90 * 10 ** 6) / (2 * distanceThreshold))
      )
      const randomY = randomIntInc(
        Math.floor((-180 * 10 ** 6) / (2 * distanceThreshold)),
        Math.floor((180 * 10 ** 6) / (2 * distanceThreshold))
      )
      const randomTime = randomIntInc(0, 2 ** 50)
      const latticePointX = randomX * 2 * distanceThreshold
      const latticePointY = randomY * 2 * distanceThreshold
      const latticePointZ = randomTime * 2 * timeThreshold
      const latticePoint = [latticePointX, latticePointY, latticePointZ]

      const translationVector = latticePoint.map((x, i) => x - template[i])

      const hash = pbkdf2_hmac(latticePoint, salt)
      return [translationVector, hash]
    }

    return {
      salt,
      infectedHelperGeneration
    }
  }

  /*
   * User Hash Generator
   */
  const userHashGeneration = (query, translationVector, salt, thresholds) => {
    const lat = Math.floor(query[0] * 10 ** 6)
    const long = Math.floor(query[1] * 10 ** 6)
    const time = Math.floor(query[2])
    const distanceThreshold = thresholds[0]
    const timeThreshold = Math.floor(thresholds[1] / 2)
    const newQuery = [lat, long, time]

    const translatedQuery = newQuery.map((x, i) => x + translationVector[i])

    const quantizedQuery = []
    quantizedQuery[0] =
      2 * distanceThreshold * Math.ceil((translatedQuery[0] - distanceThreshold) / (2 * distanceThreshold))
    quantizedQuery[1] =
      2 * distanceThreshold * Math.ceil((translatedQuery[1] - distanceThreshold) / (2 * distanceThreshold))
    const quantizedTime = 2 * timeThreshold * Math.ceil((translatedQuery[2] - timeThreshold) / (2 * timeThreshold))
    const quantizedOut = [...quantizedQuery, quantizedTime]

    return pbkdf2_hmac(quantizedOut, salt)
  }

  return {
    infectedUser,
    userHashGeneration
  }
}

const Intersection = IntersectionConstructor()

const userLocations = [
  [41.40338, 39.289342, 32],
  [2.192491, 145.293971, 55]
] // [lat, long, time]
const infUser = Intersection.infectedUser()
//TODO: More accurate threshold
// .000300 is approximately 70 feet
// 2 hours threshold
const thresholds = [300, 2]

const userHelperData = userLocations.map((location) => infUser.infectedHelperGeneration(location, thresholds))

console.log(userHelperData[0][1], 'infected point hash')

const translationVector = userHelperData[0][0]
const salt = infUser.salt
const currentLocation1 = [41.40338, 39.289342, 32] // exact match
const currentLocation2 = [41.40328, 39.289142, 33] // within threshold
const currentLocation3 = [41.40328, 39.289142, 31] // before the infection
const currentLocation4 = [41.40138, 39.289342, 31] // safe area

console.log(
  Intersection.userHashGeneration(currentLocation1, translationVector, salt, thresholds),
  'This point is close to an infected point within 2 hours'
)
console.log(
  Intersection.userHashGeneration(currentLocation2, translationVector, salt, thresholds),
  'This point is close to an infected point within 2 hours'
)
console.log(
  Intersection.userHashGeneration(currentLocation3, translationVector, salt, thresholds),
  'This point is safe'
)
console.log(
  Intersection.userHashGeneration(currentLocation4, translationVector, salt, thresholds),
  'This point is safe'
)

A few comments:

• Math.random is not cryptographically secure. Is it random enough for our purposes?
• Why is the encoding binary (aka latin1)? This doesn't match the original python code, but if I change it to utf8 it breaks (sometimes one or both of the safe locations have the same hash as the infected location).
• What's the advantage of using these libraries over node built-ins? Are we thinking ahead to the environments this will be running in? I'm a bit confused about why forge seems to interpret binary data like salts and keys as UTF-8 strings.
• Any idea why the original uses this to generate a salt instead of your method which seems more standard/secure? self.salt = str(random.randint(0, 2 ** 100)).encode("utf-8")
• Any idea why the original is encoding coordinate numbers as UTF-8? https://github.com/tripleblindmarket/covid-safe-paths/blob/develop/app/encryption/intersection.py#L78

Great points:

• Yes! We can move to a better cryptographically secure RNG. This was just my quick attempt to get it working.
• The encoding is binary because node-forge expects this format. Not really sure why node-forge chose this route. You're probably seeing something like this happen: nodejs/node#12908
• This was an attempt to not be bound to NodeJS. Perhaps it could be used in the browser or React-Native.
• No clue, but I saw this was not a good approach so I used a better way.
• I have no idea, which is why I stuck with binary. It appears as if this is maybe a bug on their side.

Side note: randomTime will fail to generate a good value if the calculation exceeds 2^53

Just noticed the final test location doesn't really match the comment (safe area). This makes more sense: [41.40138, 39.289142, 32].