Chaffing and Winnowing: Confidentiality without Encryption (1998)

http://people.csail.mit.edu/rivest/Chaffing.txt

by ronancremin • 13 years ago

69 47 13 years ago

people.csail.mit.edu

zepolud7• 13 years ago

It's cool but basically solves a problem that no longer exists. Once you've caused enough suspicion, they can simply dig up the records of all the data you've sent, both chaff and wheat, and serve you with an order to disclose your authentication key/lawfully hack you computer and obtain it without asking/apply some lead pipe cryptanalysis and get it anyway. In the end, it's no better than regular encryption, at the cost of being at least twice more inefficient.

Still, for all the crypto export nonsense, 1998 appears to have been a more innocent time:

"But access to authentication keys is one thing that government has long agreed that they don't want to have."

Lexarius2• 13 years ago

Near the bottom they mention using more than one wheat stream to achieve something like deniable encryption. If they ask you for the key, give them the one that produces innocent-looking messages.

ionforce• 13 years ago

I'm sure if law enforcement doesn't like your innocent looking messages they can just keep demanding that you give them the real key.

How easy is it to produce a stream of messages that is fake but looks real?

AnthonyMouse• 13 years ago

In the end, it's no better than regular encryption, at the cost of being at least twice more inefficient.

He goes on to explain how to make it more efficient: If you need every "wheat" packet to reconstruct any part of the message, you can send a finite number of chaff packets (e.g. 1000) in random locations, which would make reconstructing a message of arbitrary length infeasible for an adversary that can't separate the wheat from the chaff other than by exhaustive search.

knowaveragejoe2• 13 years ago

Isn't this still, in essence at least, Steganography?

zepolud7• 13 years ago

Nope. You would be painting a huge red target on yourself if you tried something like this.

The purpose of steganography is not to get noticed in the first place. It's orthogonal to regular cryptography.

ozi• 13 years ago

Unfortunately, common steganography algos used on images are easy to detect with statistical analysis.

betterunix3• 13 years ago

Steganography suffers from the warden problem: being in possession of steganography software is suspicious regardless of whether or not you use it.

DanBC2• 13 years ago

See also "Chaffinch: Confidentiality in the Face of Legal Threats" by Richard Clayton and George Danezis from University of Cambridge, which has some more plausible deniability.

(http://www.cl.cam.ac.uk/~rnc1/Chaffinch.html)

crb002• 13 years ago

I've thought about writing a Chrome plugin to do something similar. While on it would randomly chaff the low order bits of any image you upload, and would automatically add a chaff postscript to every Gmail. An adversary would have no clue which images/messages contain ciphertext, and which contain nothing but random chaff.

Cyranix2• 13 years ago

Was unreachable for me, here's the cached version: http://webcache.googleusercontent.com/search?q=cache:zgl1Lf2...

theboss2• 13 years ago

Kind of interesting scheme that doesn't really work in 2013.

Wouldn't this be vulnerable to replay attacks, or am I missing something?

hellcow• 13 years ago

If Alice's messages could all be intercepted and manipulated prior to Bob's receiving them, then yes, they could be changed without either party knowing.

Combined with asymmetric encryption of the messages, you should be able to prevent that from happening.

theboss2• 13 years ago

Without any manipulation why wouldn't this be vulnerable to a replay attack?

jamesrom• 13 years ago

No. This is just a method of "securing" messages without encryption. It still requires a shared key. Replaying messages sent this way would be no different to replaying an encrypted message.

This is not an authentication scheme.

sirmarksalot2• 13 years ago

I'm probably misunderstanding this. The way I'm envisioning this is basically a half-dozen parallel conversations, with only one of them being the actual conversation.

Couldn't it be easily defeated with contextual analysis? I mean, if it were English sentences, the attacker could just choose a set of packets that make grammatical sense. Or in more real-world examples, you'd just choose the packets that form a valid HTTP session.

To work around this, you'd have to choose your chaff packets to flow seamlessly from one to the other, which would make chaffing a really hard problem.

ronaldx• 13 years ago

Keep reading: the first example is a bit misleading (for the reason you state) and the article gets more interesting.

They deal with this problem by coding the message with single-bit packets, always contrasting 0s with 1s.

sirmarksalot2• 13 years ago

Yup, that was the critical piece I was missing. Thanks!

kyboren• 13 years ago

In that document, he proposed two different systems.

The first transmits two tuples for every bit of the message. In pseudo-ish code:

    for(i = 0; i < message_bits.length; ++i){
        send( (sequence_number, 0, (message_bits[i] == 0? HMAC(shared_key, sequence_number . '0') : rand())) );
        send( (sequence_number, 1, (message_bits[i] == 1? HMAC(shared_key, sequence_number . '1') : rand())) );
    }

Without knowing the HMAC key, the only information exposed is the length of the message. Without the HMAC key, you can't tell whether '0' or '1' (both of which are sent, for every bit in the message) is the correct bit.

The second works in a slightly different way. You take a message, and transform it into a package in such a way that one must determine the entire package contents before being able to decode any part of the package. (Rivest's proposal for such an 'All-or-Nothing Transform' can be found in [1]).

Next, you packetize that transformed package. Rivest proposes blocks of 1024 bits, but it could be anything. The point is you can't send (2^1024 - 1) 'chaff' blocks, which would be required to not leak any information about a 1024-bit message block.

But, crucially, you must determine which is the correct block for every sequence number sent. So, if one includes just one 'chaff' block for each 'wheat' block (so there is one wheat and one chaff block for each sequence number), and sends n blocks, then an attacker who doesn't know the HMAC key would need to choose the right combination of blocks of all sequence numbers--a 1 in 2^n chance--before being able to decode your message.

If one splits an all-or-nothing transformed message into at least 256 blocks and sends one 'chaff' block with each 'wheat' block, you could be pretty sure the message remains confidential. Of course, this assumes all those pesky security assumptions about the random number generator, transform, and HMAC function hold up.

[1] http://theory.lcs.mit.edu/~cis/pubs/rivest/fusion.ps

lucb1e• 13 years ago

Might be just me, but I'm thinking encryption is way easier than this.

Cyranix2• 13 years ago

But that's rather missing the point, isn't it? The premise is "Under circumstances where encryption is not a viable option, what secure communication methods might be possible?" so responses that ignore the premise, like "just use encryption" or "just don't get into such circumstances", aren't the most salient critiques.

bigiain• 13 years ago

Two points: First, this was from 1998 - back when "exporting encryption" from the US was punishable as exporting weapons. Secondly, this is proposing a communication scheme where there is no "encryption/decryption key" for the NSA to coerce people into handing over.

Chaffing and Winnowing: Confidentiality without Encryption (1998)

Related Stories