Chaffing and Winnowing: Confidentiality without Encryption (Ron Rivest) | Hacker News Reader

Chaffing and Winnowing: Confidentiality without Encryption (Ron Rivest)

people.csail.mit.edu

34 pointsmightybyte10 comments

Rivest stresses multiple times that the process he describes is "not encryption" because the cryptographic primitive being used is an authentication one. Therefore, he says, his process can be implemented using software that's approved for US export -- this was back when that was a problem, of course.

Well, yes, kinda. But:

1. The whole process most certainly is encryption by any reasonable definition, especially if (as he suggests) you do it by authenticating two versions of every bit, only one of which checks out. It's basically an obfuscated version of the following scheme: you take your message, you exclusive-or it with a stream of random-enough bits (the bitstream, or enough information to generate it, is your shared secret key), and then you replace 0 with 01 and 1 with 10. So, as with Rivest's scheme, the ciphertext -- oh, excuse me, the plaintext with added chaff -- is basically an interleaving of the plaintext and its bitwise complement, and you need some secret knowledge to know which bit to use from each pair.

2. Sure, you can implement Rivest's scheme using a cryptographic building block that does something other than encryption. But if you build software that does this then that (see 1 above) is surely encryption software, so (back when Rivest's article was written) you run into the same problems with US export as you were trying to avoid.

The Alice/Bob/Charles scenario is bloody clever, though. (And the ability to do this sort of thing, rather than the claim that the process "isn't encryption", is the real point. What Rivest has done is to find a way of decomposing an encryption+decryption process into a small number of parts each of which can somewhat plausibly be claimed not to be for encryption.)

Yes, but you can build one program (or hardware box) that does packet authentication, and another that does the chaffing. Each of those could be exported separately, then the two subsystems combined elsewhere.

Technically excellent - it would work great.

But he suffers from assuming that law works on absolutes. It doesn't. It works on "most likely". So if law saw this, Alice could _say_ it's not me, it's charles. But the law would not believe her.

Does someone who's in the field know if this sounds reasonable?

It depends on what you mean by "reasonable." Yes, it works. As the paper suggests, it is a variation on steganography that hides a small stream of information in a large body of noise and uses a shared-secret (the MAC key in this case) to filter the information out of the noise. OTOH, it is really more of a mental exercise to show how US crypto-export rules were easy to get around if you were clever: according to the rules at the time you could "export" a cryptosystem that just performed authentication as long as it did not encrypt data. This particular bit of subterfuge is no longer necessary so no one is going to bother with it now and there are much better ways to do stego if you need to hide a message; you can also take the probabalistic encryption route if you need deniability...

This technique is entirely reasonable, although not incredibly efficient. There are several ways of converting between symmetric encryption and authentication; the only reason we talk about using, e.g., AES and SHA256 is that AES is much faster than any block cipher you can build out of SHA256, while SHA256 is much faster than any hash you can build out of AES.

If you use a packaging transform, then this becomes efficient in the use of bandwidth.

Yes, but it's still very inefficient in terms of computation.

I'm not qualified to comment on how reasonable this is, but it's author has a good bit of credibility -- he's the "R" in the RSA algorithm for public-key cryptography). Note also that this piece is over 10 years old.

this guy is pretty darn smart in my booke

Reply on news.ycombinator.com