The chaffing society

-- By SamuelRoth - 04 Dec 2014

Rivest's other algorithm

In his 1998 paper Chaffing and Winnowing: Confidentiality without Encryption, Ronald Rivest proposes a new technical method that, in theory, achieves strong information confidentiality without traditional encryption. His proposal, which he calls "Chaffing and Winnowing," involves splitting up the plaintext into many small packets—Rivest suggests as small as a single bit—and computing a "message authentication code" (MAC) for each one by using a cryptographic function to combine the data in the packet with a secret key. The sender then adulterates the plaintext packets with a similar number of false packets, each with its own fabricated MAC, so that an eavesdropper cannot tell the "wheat" from the "chaff." Only the recipient, possessed of the secret key, can determine which MACs are valid, and thereby distinguish the true plaintext from false.

But Rivest's endorsement and operationalization of the concept have failed to promote its use in contemporary cryptography: A Google search for "Rivest chaffing" yields only various exegeses of the basic idea, and a 2006 technical analysis conducted by a student at the University of Bath still struggles with the question of whether it could be "a real alternative to using traditional encryption techniques."

When you're a famous cryptographer like Rivest, every idea must look like an algorithm. But I propose that chaffing's primary potential is not as a cryptographic technique per se, but as a strategy of resistance to corporate surveillance.

Way too big data

As we have discussed in class, databases threaten privacy most effectively when used to make correlations and connections between previously discrete pieces of information. Prof. Moglen recounted the anecdote of the last missing social security number from Baltimore; for another example, consider the security researcher who combined voting records and supposedly "anonymized" medical data to uncover the health records of the governor of Massachusetts.

But what if all those tables were intentionally bogged down with bad rows? Government electronic surveillance is concerned with finding any basis, significant or insubstantial, on which to justify real-world action, but business intelligence depends on the watcher's ability to effectively narrow the field of data down to the specific pieces of information she needs: The Massachusetts researcher, for instance, succeeded in part because only six people in the city of Cambridge shared the governor's birthdate. What if "big data" became "way too big data," most of it false?

Wheat into chaff

Some applications are obvious. If Facebook cares which recipes its users are saving on Epicurious—cares so much, in fact, that it will surveil its users even after they log out—then write a program that saves recipes on Epicurious in the background twenty-four hours a day. If one's phone provider tracks who is calling whom, write an app that, in the background, ceaselessly places calls to other phones with the same app, and does so in a way that hard for a computer to distinguish meaningful phone conversation.

A similar program for one's web browser could defend unencrypted web browsing against invasion of privacy by hiding bona fide user requests in a field of chaff. At some point, even Google or Apple has got to run out of hard drive. Or, in the case of more opportunistic corporate surveillance schemes such as Phorm, perhaps it would be more effective to amass each user's cookies on a central server and then install the whole archive in every user's cache.

Wheat into chaff into wheat

But all of the above applications assume that the person who creates the chaff in the database does not need to be able to separate out the wheat again. What if that's an important part of the system, because the database in question is of emails or tweets or Facebook friends? (Supposing, arguendo, that tweets or Facebook friends are things which one should accumulate in a database at all.)

The solution here is not much more complex: Users could chaff the database in a reversible way by use of a program that would interface between the user and the database, along the lines of the Lucent Personalized Web Assistant of the late 1990s. Whenever two users of the chaffing program first communicate with each-other, their instances of the program would agree on a private key by means of a secure handshake; this key would then be used to generate valid MACs for genuine emails between those two individuals. Meanwhile, those users' chaffing programs would start up a non-stop exchange of fake communications, so that future valid communications would be indistinguishable from so much noise.

These chaffed communications could, of course, also be encrypted. But when an email exchange is merely encrypted, the operators of the sender's and recipient's respective email services can still track when and how often the individuals communicate. Adding in chaffing prevents even that minimal kind of surveillance.

Furthermore, the users of the email chaffing program could consent to have fake emails sent to their address from all the users of the chaffing program with whom they have not yet executed a secure handshake—i.e., from strangers. Thus, from the perspective of the email provider, the network of people in communication with one-another and the network of people using the chaffing program are identical. If the value of the vast troves of data currently being assembled by major online service providers comes from making correlations that simulate real-world activities and social relationships, chaffing will complicate and limit their ability to do so.

Technology, politics, law, and culture

In short, the chaffing society seems technologically achievable. The chaffing approach will also certainly require political components, so that the flood of bad data is understood as something other than hacking or an attempt at distributed denial of service. There may even be legal implications, although it is difficult to anticipate what legal challenges will be raised against a strategy that involves, in principle, nothing more than an exponential numerical increase in otherwise legal activities. But the primary challenge will likely be cultural: convincing the movements against surveillance that privacy can be built upon a new vision of radical oversharing.

---

You are entitled to restrict access to your paper if you want to. But we all derive immense benefit from reading one another's work, and I hope you won't feel the need unless the subject matter is personal and its disclosure would be harmful or undesirable. To restrict access to your paper simply delete the "#" character on the next two lines:

• #Set ALLOWTOPICVIEW = TWikiAdminGroup, SamuelRoth
• #Set DENYTOPICVIEW = TWikiGuest

Note: TWiki has strict formatting rules for preference declarations. Make sure you preserve the three spaces, asterisk, and extra space at the beginning of these lines. If you wish to give access to any other users simply add them to the comma separated ALLOWTOPICVIEW list.