|
|
|
|
Chaffing and Winnowing: Confidentiality without Encryption Ronald L. Rivest MIT Lab for Computer Science March 18, 1998 (rev. April 24, 1998) http://theory.lcs.mit.edu/~rivest/chaffing.txt A major goal of security techniques is ``confidentiality''---ensuring that adversaries gain no intelligence from a transmitted message. 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. (See Wayner (1996) for more information on steganography.) \-- Encryption: transforming the message to a ciphertext such that an adversary who overhears the ciphertext can not determine the message sent. 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. Winnowing does not employ encryption, and so does not have a ``decryption key.'' Thus, the usual arguments in favor of ``key recovery'' don't apply very well for winnowing. 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. (1997)). We have the transformation of appending a MAC thus: packet --> packet, MAC The packet is still ``in the clear''; no encryption has been performed. 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 packe
|
