Last active
April 13, 2020 20:47
-
-
Save s0l0ist/59309573844e734398b4e9180935e555 to your computer and use it in GitHub Desktop.
Geo-hashing with time
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
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' | |
) |
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]
.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
A few comments:
Math.random
is not cryptographically secure. Is it random enough for our purposes?binary
(akalatin1
)? This doesn't match the original python code, but if I change it toutf8
it breaks (sometimes one or both of the safe locations have the same hash as the infected location).self.salt = str(random.randint(0, 2 ** 100)).encode("utf-8")