theory.lcs.mit.edu/~rivest/chaffing.txt
Chaffing and Winnowing: Confidentiality without Encryption Ronald L. Rivest MIT Lab for Computer Science March 18, 1998 (rev. There are two major techniques for achieving confidentiality: -- Steganography: the art of hiding a secret message within a larger one in such a way that the adversary can not discern the presence or contents of the hidden message. For example, a message might be hidden within a picture by changing the low-order pixel bits to be the message bits. The legitimate receiver possesses a secret decryption key that allows him to reverse the encryption transformation and retrieve the message. The sender may have used the same key to encrypt the message (with symmetric encryption schemes) or used a different, but related key (with public-key schemes). DES and RSA are familiar examples of encryption schemes. This paper introduces a new technique, which we call chaffing and winnowing''---to winnow is to separate out or eliminate (the poor or useless parts),'' (Webster's Dictionary), and is often used when referring to the process of separating grain from chaff. Novel techniques for confidentiality are interesting in part because of the current debate about cryptographic policy as to whether law enforcement should be given when authorized surreptitious access to the plaintext of encrypted messages. The usual technique proposed for such access is key recovery,'' where law enforcement has a back door'' that enables them to recover the decryption key. As usual, the policy debate about regulating technology ends up being obsoleted by technological innovations. Trying to regulate confidentiality by regulating encryption closes one door and leaves two open (steganography and winnowing). We now explain how a confidentiality system based on winnowing works. There are two parts to sending a message: authenticating (adding MACs), and adding chaff. The recipient removes the chaff to obtain the original message. The sender breaks the message into packets, and authenticates each packet using a secret authentication key. That is, the sender appends to each packet a message authentication code'' or MAC'' computed as a function of the packet contents and the secret authentication key, using some standard MAC algorithm, such as HMAC-SHA1 (see Krawczyk et al. We have the transformation of appending a MAC thus: packet --> packet, MAC The packet is still in the clear''; We note that software that merely authenticates messages by adding MACs is automatically approved for export, as it is deemed not to encrypt. There is a secret key shared by the sender and the receiver to authenticate the origin and contents of each packet---the legitimate receiver, knowing the secret authentication key, can determine that a packet is authentic by recomputing the MAC and comparing it to the received MAC. If the comparison fails, the packet and its MAC are automatically discarded. The sender and the receiver can initially create and agree upon the secret authentication key with any standard technique, such as authenticated Diffie-Hellman. We note that it is typical for each packet to contain a serial number as well. For example, when a long file is transmitted it is broken up into smaller packets, and each packet carries a unique serial number. The serial numbers help the receiver to remove duplicate packets, identify missing packets, and to correctly order the received packets when reassembling the file. The MAC for a packet is computed as a function of the serial number of the packet as well as of the packet contents and the secret authentication key. As an example, we might have a sequence of the form: (1,Hi Bob,465231) (2,Meet me at,782290) (3,7PM,344287) (4,Love-Alice,312265) of triples of sequence number, message, and MAC. The second process involved in sending a message is adding chaff'': adding fake packets with bogus MACs. The chaff packets have the correct overall format, have reasonable serial numbers and reasonable message contents, but have MACs that are not valid. The chaff packets may be randomly intermingled with the good (wheat) packets to form the transmitted packet sequence. Extending the preceding example, chaff packets might make the received sequence look like: (1,Hi Larry,532105) (1,Hi Bob,465231) (2,Meet me at,782290) (2,I'll call you at,793122) (3,6PM,891231) (3,7PM,344287) (4,Yours-Susan,553419) (4,Love-Alice,312265) In this case, for each serial number, one packet is good (wheat) and one is bad (chaff). Instead of randomly intermingling the chaff with the wheat, the packets can also be output in sorted order, sorting first by serial number, and then by message contents. To obtain the correct message, the receiver merely discards all of the chaff packets, and retains the wheat packets. In a a typical packet-based communication system the receiver will automatically discard all packets with bad MACs. So the winnowing'' process is a normal part of such a system. As above, winnowing'' is the (usual) process of discarding all packets with bad MACs. We call the good packets wheat'' for consistency of metaphor. This depends on the MAC algorithm, on how the original message is broken into packets, and on how the chaffing is done. A typical MAC algorithm (such as HMAC-SHA1) will appear to act like a random function'' to the adversary, and in such a case the adversary will not be able to distinguish wheat from chaff. It is possible in principle, however, to have an unfortunate MAC algorithm that leaks'' information about the message being MAC'ed, allowing the adversary to gain an advantage in distinguishing wheat from chaff. For example, one could define a LEAKY-HMAC-SHA1 MAC algorithm to have an output that is the concatenation of the output of the HMAC-SHA1 algorithm together with the low-order bit of the message being MAC'ed. However, in practice (and in theory) one looks for MAC algorithms that are indistinguishable from random functions, and such algorithms also work fine in a chaffing and winnowing application. Note that the problem of providing confidentiality by chaffing and winnowing is based on the difficulty (for the adversary) of distinguishing the chaff from the wheat. It is *not* based on the difficulty of breaking an encryption scheme, since there is no encryption being performed (although confidentiality may be obtained nonetheless, just as for steganography). If the adversary sees only one packet with a given serial number, then that packet is probably wheat, and not chaff. So a good chaffing process will add at least one chaff packet for each packet serial number used by the message. The adversary may also distinguish wheat from chaff by the contents of each packet. If the wheat packets each contains an English sentence, while the chaff packets contain random bits, then the adversary will have no difficulty in winnowing the wheat from the chaff himself. On the other hand, if each wheat packet contains a single bit, and there is a chaff packet with the same serial number containing the complementary bit, then the adversary will have a very difficult (essentially impossible) task. Being able to distinguish wheat from chaff would require him to break the MAC algorithm and/or know the secret authentication key used to compute the MACs. With a good MAC algorithm, the adversary's ability to winnow is nonexistant, and the chaffing process provides perfect confidentiality of the message contents. I stress that the sending process for chaffing and winnowing is not encryption; Let us assume that the original message is broken into very short (one-bit) packets, and that MACs have been added to each such packet to create the wheat packets. Here each MAC might be 64 bits in length, and each serial number 32 bits long. The process of creating chaff is also easy: just create a chaff packet with whatever serial number and packet contents you may like, and include a random 64-bit MAC value. This MAC value is overwhelmingly likely to be bad, and thus the packet created is overwhelmingly likely to be chaff. Again, it is assumed here that an adversary, not knowing the secret authentication key, can not distinguish a good (wheat) packet from a ba...
|
http://csua.com/feed/