The problem and the outcome in brief
Drawing on another app I develop at my own company, I want to describe the privacy design behind a mechanism that tallies anonymous posts. The app has a feature that publishes a piece of text assembled from anonymous posts, and it had to keep the people who posted from being tracked while also preventing one device from inflating the numbers by posting over and over.
In this article I first explain how the app generates a pseudonym for each device with two layers of hashing. Next I explain the threshold that decides whether the assembled text may be published. Right after this threshold went in, it was not doing its job: it counted the number of posts while meaning to count the number of devices. Last, I describe how the design document writes out what this design cannot protect. The material is about three weeks of records of design, implementation, and fixes, along with a design document that kept being updated afterward.
Two requirements pulling in opposite directions, and the final shape
The app has a feature that assembles the anonymous posts collected about a given subject into a single piece of text and publishes it. Two requirements pull on this feature at once, in opposite directions. The people who posted must not be traceable. At the same time, the design must keep one device from posting over and over to fake the support of several devices. Not being able to identify the device is safer for preventing tracking, and being able to identify it is surer for preventing inflated numbers, so the two requirements collide head on.
Let me show the final shape first. The design settled into a form that keeps no more power to tell devices apart than detecting abuse requires. The app generates a pseudonym for each device with two layers of hashing and uses that pseudonym only to count how many distinct devices there are. The number of distinct devices supporting the text and the threshold test alone decide whether the app publishes it. The app uses the pseudonym for nothing but tallying, and what a reader sees is only the number of devices.
The two layers of hashing that generate the pseudonym
On first launch, the device generates exactly one random identifier. That identifier is a UUID v4, in which 122 of the 128 bits are random. The definition of UUID v4 is in RFC 9562. The device keeps the identifier only in its secure storage area, ties it to no account information, and never sends it to the server.
When the device sends a post, it concatenates this identifier with the ID of the subject, hashes them one way with SHA-256, and hands only the hash value to the server. The raw identifier stays inside the device alone and never leaves it. The server applies HMAC-SHA256, a keyed hash, to the value it received, using a key held only in a secret store, and saves the output as the pseudonym for tallying. The definition of HMAC is in RFC 2104. Written as formulas, the flow looks like this.
Device: p = hash(device ID + ":" + subject ID) SHA-256 here
Server: pseudonym = keyed_hash(secret key, p) HMAC-SHA256 here
The hash on the device hides the raw identifier, and the keyed hash on the server prevents pseudonyms from being forged. Anyone who does not know the key cannot compute the output of HMAC, so an attacker who wants to produce pseudonyms has to obtain the key itself. The key sits neither in the database nor on the device.
This division of labor borrows the salt-and-pepper pattern, a standard practice in password storage. A salt is a random value that differs for each value it is added to, and a pepper is a secret shared across the whole system and kept outside the database. OWASP's Password Storage Cheat Sheet sets out this distinction. In this design, the subject ID mixed in on the device plays the role of the salt, and the key on the server plays the role of the pepper. If the device and the server compute the derivation differently, matching the same device breaks. That is why the derivation on the server lives in a single shared module.
The design that closes the range of matching to a single subject
The key point of this design is that the device mixes in the subject ID. Even for posts that came from the same device, the pseudonym is a different value when the subject differs. So neither the server nor anyone reading the database can match a post about subject A with a post about subject B to tell whether they came from the same device. The range in which posts can be tied to the same device stays deliberately closed inside a single subject.
I did not take the option of one stable device hash shared across all subjects. With that, anyone could match the same device across subjects and assemble a history of each device's behavior out of posts that are supposed to be anonymous. On the other hand, the input to this pseudonym does not mix in a server-distributed salt that might be rotated. If the value is not stable for a given subject, counting falls apart. The implementation notes state plainly that concealment is the pepper's job.
The threshold that decides publication
The assembled text keeps a record of which devices' posts went into its material. I count those devices as the devices supporting the text. There are two conditions for publication: support from 5 or more distinct devices, and a share below 0.8 for the single device that contributes the most support. If either one is missing, the app does not publish the text. The default value of the database column is unpublished as well.
During trial operation I lower the threshold from 5 to 2. I do not lower it to 1, though. With support from a single device the share is always 1.0, so publication is structurally impossible, and it would also break the promise to publish only text gathered from several devices. I do not loosen the ceiling of 0.8 on the share even during trial operation. Beyond that, at most 3 posts per pseudonym go into the material, so that repeated posting cannot take over the content. Posts whose pseudonym the code could not compute do not count toward the number of devices, and if the pseudonym is unknown for every post, the code returns 0 devices and a share of 1.0, which always means no publication. I carved this decision out as a pure function of its inputs and outputs alone, and unit tests pin down both the default values and the trial-operation values.
The bug that counted posts while meaning to count devices
Right after it went in, this threshold was at one point effectively not doing its job. What it counted was the number of posts, not the number of distinct devices. The cause was a mix-up. The device was also sending another hash, meant for a different purpose, whose value changes with every post, and the server was using that one as the material for the pseudonym. Since the same device produced a different pseudonym every time it posted about the same subject, a single device could fake the support of several devices just by posting over and over. The fix consolidated everything into one form, in which the server applies HMAC to the stable value the device generates. I made this fix while the app was still in trial operation, before it opened to the public.
There was a reason the other hash got mixed up with this one. The same app has another hash. It mixes a server-distributed salt, a per-row random value, and the date into the device identifier, and deliberately scatters the value for every single post. It is a tool that makes any tally which groups posts by user impossible, down to the structure of the database itself. The hash that scatters its value and the pseudonym for tallying that keeps its value stable look like the same hash, yet they require exactly opposite properties. The moment one goes where the other belongs, the counting mechanism misbehaves without raising a single error.
The limits the design document spells out
This design document writes out the range it cannot protect at the same granularity as the range it can. The table below organizes this by the situation in which data leaks.
| Leak situation | What the attacker gets | What they cannot do, and why |
|---|---|---|
| The database alone leaks | The pseudonyms output by HMAC | Without the secret key, they cannot recompute them, match them, or forge them |
| Both the database and the secret key leak | The pseudonyms and the key | The original input requires a 122-bit random identifier, so brute force does not work |
| The server runtime is compromised | Values already hashed on the device | The raw identifier does not exist outside the device, so they cannot recover it |
| The device itself is compromised | The data inside the device | They can read the data straight off the device, so attacking through the server is pointless |
The design document is candid about why the pepper is there, too. Because the input is 122 bits of randomness, the classic motivation for a pepper, protecting a low-entropy secret, does not apply directly. It is there anyway as a defense-in-depth call: it costs only one HMAC, it gains resistance to a leak of the database alone, it keeps the secret separate, and it acts as insurance if the assumption about randomness ever falls apart.
The document names three things the design cannot protect. First, N distinct devices do not mean there are N distinct people. Second, an attack that mass-produces many devices or emulators to fake identities remains. This is the type known as a Sybil attack, in which one actor claims many identities. Weighting a new device's support low at first, together with rate limits, can raise the cost of the attack, but it cannot bring the faking itself to zero. Third, if separate real people agree among themselves and post the same falsehood, a mechanism that tallies while keeping everyone anonymous has no principle by which to tell it apart. The document accepts that the terms of service, reports from users, and human review cover this part.
The document also settles how I rotate the secret key. Rotating the key severs matching against past pseudonyms and cuts off the material for tracking. In exchange, once the key has changed, I can no longer match the same device to its past pseudonyms, so I can no longer recount the device counts for the past correctly. That is why I keep support counts already published as settled records and never withdraw them by recomputation.
The way the limits are written sits at the center of the design
What works in this design is less the choice of each hash than the way the limits are written. This design document does not declare that tracking is impossible. It splits the situations apart, asking what happens if the database alone leaks and what happens if the key leaks too, and writes out both the range it can protect and the range it cannot. That is the center of the design. Even the two lines on the side it cannot protect are in the document: the design accepts faking that uses many devices and raises its cost, and it sends coordinated falsehood to human review.
In any design, some judgment remains at the end that cannot be fully entrusted to a machine and goes back to human review. In this design it was telling coordinated falsehood apart. What I have wanted to do all along is the other thing: to teach the machine the shapes of these judgments that remain at the end, and to whittle away the role of the human reviewer itself. In time I want to leave only the data, to have even that data produced by AI, and in the end to build an AI that mirrors me. The judgment I just called one that only a person can make is no different. If I can hand over its shape one piece at a time, the line that sends it back to a person should be one I can erase someday. That is what I am working toward.
Originally published at The Future of Humans, AI, and the Web, a site where my research and development is recorded and analyzed by a human and an AI.
Top comments (0)