34:["$","title",null,{"children":"Hacking hashes: an exploration of the NYC Taxi Data issue | Tom MacWright | Observable"}] 3c:T415,html`

Testing licenses ${rainbowBatch[0][0]} to ${rainbowBatch[rainbowBatch.length - 1][0]}

Here are the de-anonymized values, as they come in. The discussion below is about how this works.

${Array.from(licenseNumberMap.entries()).map(([hash, number]) => ``).join('\n') }

MD5 value	Cracked value
`${hash}`	`${number \|\| '🤔'}`

A glance at the flow of thousands of hashes, styled like the Matrix for authenticity:

${rainbowBatch.slice(0, 20).map(r => html`${r[0]} → ${r[1]}`)}

`3d:[] 38:{"id":"688d96b0e295764e","slug":"hacking-hashes-an-exploration-of-the-nyc-taxi-data-issue","title":"Hacking hashes: an exploration of the NYC Taxi Data issue","thumbnail":"6e5b04d78fc92dad7963cc549243be9750d650c4ca172d6cdb27e75e1f8aaa7f","access_level":"public","create_time":"$D2018-04-05T16:59:26.736Z","update_time":"$D2018-04-05T18:50:40.009Z","view_time":null,"first_public_time":"$D2018-04-05T18:24:42.975Z","has_unpublished_edits":null,"fork":false,"stars":4,"starred":false,"owner":{"type":"team","id":"b47c3705cfcd7c1b","login":"tmcw","name":"Tom MacWright","avatar_url":"https://avatars-next.observableusercontent.com/669bdd774da8a1b9c1b7706ecbc1ea5136b9932c3d5e86b753aa5a098005f674","tier":"starter_2024","bio":"hi!","followed_by_you":false,"follows_you":false},"version":347,"publish_version":347,"role":null,"authored":false,"authors":[{"type":"individual","id":"0bf14b8d9c6eb88a","login":"tmcw","name":"Tom MacWright","avatar_url":"https://avatars-next.observableusercontent.com/669bdd774da8a1b9c1b7706ecbc1ea5136b9932c3d5e86b753aa5a098005f674","tier":null,"bio":"hi!","followed_by_you":false,"follows_you":false}],"members":[{"type":"individual","id":"0bf14b8d9c6eb88a","login":"tmcw","name":"Tom MacWright","avatar_url":"https://avatars-next.observableusercontent.com/669bdd774da8a1b9c1b7706ecbc1ea5136b9932c3d5e86b753aa5a098005f674","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":2,"collection":null,"type":"notebook","body":{"titling":"auto","title":"Hacking hashes: an exploration of the NYC Taxi Data issue","cells":[{"id":0,"value":"md`# Hacking hashes: an exploration of the NYC Taxi Data issue\n\n

\n\nYou may have read about the [NYC Taxi data deanonymization](https://research.neustar.biz/2014/09/15/riding-with-the-stars-passenger-privacy-in-the-nyc-taxicab-dataset/) story. New York released taxi trip data via an information request, and they simply ‘hashed’ certain identifiable details: medallion numbers and another kind of license number called a [‘hack’ license](https://nycitycab.com/HackLicense.aspx). Here’s a quick demonstration of how the de-anonymization works, a sort of simplified and interactive version of [this excellent blog post explanation](https://tech.vijayp.ca/of-taxis-and-rainbows-f6bc289679a1). Okay, so let's come up with some input data: just license numbers, which are six-digits.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":17,"value":"licenseNumbers = {\n trigger;\n let licenseNumbers = [];\n for (let i = 0; i < 10; i++) {\n // Generate a zero-padded six digit number.\n licenseNumbers.push(Math.floor(Math.random() * 1e6).toString().padStart(6, '0'));\n }\n return licenseNumbers;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":26,"value":"md`\n### License numbers\n\nOur fake license numbers: ${licenseNumbers.join(', ')}\n\nThe information request ran this identifiable information through the [MD5 hash algorithm](https://en.wikipedia.org/wiki/MD5). It’s sort of a defamed algorithm - there are better alternatives, and using it to confirm that certain data is what you think it is, is a really bad idea. Essentially, it’s way too easy to come up with inputs that are different but have the same MD5 hash.\n\nThat’s irrelevant to this problem, though - they could have used SHA256 and the same attack would be possible, just slightly less convenient.\n\nAnyway, let’s hash those numbers.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":33,"value":"hashedNumbers = licenseNumbers.map(number => md5.hash(number))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":37,"value":"md`\n### Hashed numbers\n\n${hashedNumbers.map(l => `* \\`${l}\\``).join('\\n')}\n\nThat looks pretty anonymous, right? Lots of characters, hard to guess.\n\nMD5 is a 32-character hexadecimal string, so napkin math says that there are:\n\n- 32 characters, each character with 16 possible values (0-9, a-f)\n- Each 2 hex characters store 2⁸ = ${Math.pow(2, 8)} possibilities (1 byte)\n- 32/2 = ${32 / 2} bytes = 16 * 8 = ${16 * 8} bits\n- 2¹²⁸ = ${Math.pow(2, 128)} potential hashes\n\nUnfortunately, that doesn’t really matter. We don’t have lots of potential license numbers mapping to these many many potential hash values: we know that licenses are 6 digits. So there are 999,999 potential solutions. That's not that many.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":241,"value":"md`# Hacking time!\n\nClick _Start_ to (re)start hacking. You know you want to.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":244,"value":"viewof trigger = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":305,"value":"\nhtml`

👾 👾 HACKING IN PROGRESS ⚡️⌨️ HACKING IN PROGRESS 😈

\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":123,"value":"$3c","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":94,"value":"md`---\n\n## The not-so-gritty details\n\nSo, we're using [spark-md5](https://github.com/satazor/js-spark-md5), which is a bit faster than [JavaScript-MD5](https://github.com/blueimp/JavaScript-MD5), so that helps with the speed. Both are libraries that implement that MD5 hashing algorithm: they take strings as input, return string hashes as output.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":76,"value":"md5 = require('spark-md5')","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":264,"value":"md`The other trick that I’ll use is batches, so that we don’t lose a lot of time in Observable’s lovely built-in [microtasks](https://jakearchibald.com/2015/tasks-microtasks-queues-and-schedules/) that chop up generators. Instead of yielding one hash at a time, we do 1,000 hashes in a simple, tight, fast loop and then yield that. Just cuts down on indirection, bookkeeping, other things that make things slow.\n\nSo rainbowBatch is an ever-changing value of the license numbers from 000000 → 001000, and then 001000 → 002000, and so on. We can tweak the batch size: bigger batches mean it runs faster, but this page is less responsive.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":63,"value":"rainbowBatch = {\n licenseNumbers;\n for (let i = 0; i < 999999; i += 1000) {\n let batch = [];\n for (let j = i; j < i + 1000; j++) {\n const n = j.toString().padStart(6, '0');\n batch.push([n, md5.hash(n)]);\n }\n yield batch;\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":110,"value":"md`---\n\nThen we store a fast mapping of hashes to their re-identified values. I use a JavaScript Map because it’s a [better dictionary datastructure for JavaScript](https://macwright.org/2017/03/13/maps-not-strictly-better.html).`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":116,"value":"mutable licenseNumberMap = new Map(hashedNumbers.map(n => [n, undefined]))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":182,"value":"md`---\n\nThen this cell combines\n\n- _rainbowBatch_, the stream of hash → number solutions\n- _licenseNumberMap_, the mapping of solved hashes\n\nAnd updates licenseNumberMap when we see relevant solutions.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":100,"value":"{\n for (let [number, hash] of rainbowBatch) {\n if (licenseNumberMap.has(hash)) {\n mutable licenseNumberMap = licenseNumberMap.set(hash, number);\n }\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":280,"value":"md`# What have we learned?\n\n- Anonymization is difficult and easy to get wrong.\n- If you have predictable input, hashing it doesn’t do much good, because people can generate all possible inputs, hash all of them, and match.\n- Hacking is fun.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W3d","stdlib":"1"}} 33:null