Chaffing and winnowing

Chaffing and winnowing is a cryptographic technique to achieve confidentiality without using encryption when sending data over an insecure channel. The name is derived from agriculture: after grain has been harvested and threshed, it remains mixed together with inedible fibrous chaff. The chaff and grain are then separated by winnowing, and the chaff is discarded. The technique was conceived by Ron Rivest. Although it bears similarities to both traditional encryption and steganography, it cannot be classified under either category.

This technique is remarkable compared to ordinary encryption methods because it allows the sender to deny responsibility for encrypting their message. When using chaffing and winnowing, the sender transmits the message unencrypted, in clear text. Although the sender and the receiver share a secret key, they use it only for authentication. However, a third party can make their communication confidential by simultaneously sending specially crafted messages through the same channel.

How it works

	secure channel		insecure channel
Alice	→	Charles	→	Bob
constructs 4 packets, each containing one bit of her message and a valid MAC	Serial Bit MAC 1 1 234 2 0 890 3 0 456 4 1 678	adds 4 chaff packets with inverted bits and invalid MAC, shown in italics (chaffing)	Serial Bit MAC 1 0 321 1 1 234 2 0 890 2 1 987 3 0 456 3 1 543 4 0 765 4 1 678	discards packets with invalid MAC to recover the message (winnowing)
In this example, Alice wishes to send the message "1001" to Bob. For simplicity, assume that all even MAC are valid and odd ones are invalid.

The sender (Alice) wants to send a message to the receiver (Bob). In the simplest setup, Alice enumerates the bits in her message and sends out each bit in a separate packet. Each packet contains the bit's serial number in the message, the bit itself (both unencrypted), and a message authentication code (MAC) whose secret key Alice shares with Bob. Charles, who transmits Alice's packets to Bob, interleaves in a random order the packets with corresponding bogus packets (called "chaff") with corresponding serial numbers, the bits inverted, and a random number in place of the MAC. Charles does not need to know the key to do that (real MAC are large enough that it is extremely unlikely to generate a valid one by chance, unlike in the example). Bob uses the MAC to find the authentic messages and drops the "chaff" messages. This process is called "winnowing".

An eavesdropper located between Alice and Charles, can easily read Alice's message. But an eavesdropper between Charles and Bob would have to tell which packets are bogus and which are real (i.e. to winnow, or "separate the wheat from the chaff"). That is infeasible if the MAC used is secure and Charles does not leak any information on packet authenticity (e.g. via timing).

When an adversary requires Alice to disclose her secret key, she can defend with the argument that she used the key merely for authentication and did not intend to make the message confidential. If the adversary cannot force Alice to disclose an authentication key (which knowledge would enable the adversary to forge messages from Alice), then her messages will remain confidential. On the other hand, Charles does not even possess any secret keys that he could be ordered to disclose.

Variations

The simple variant of the chaffing and winnowing technique described above adds many bits of overhead per bit of original message. To make the transmission more efficient, Alice can process her message with an all-or-nothing transform and then send it out in much larger chunks. The chaff packets will have to be modified accordingly. Because the original message can be reconstructed only by knowing all of its chunks, Charles needs to send only enough chaff packets to make finding the correct combination of packets computationally infeasible.

Chaffing and winnowing lends itself especially well to use in packet-switched network environments such as the Internet, where each message (whose payload is typically small) is sent in a separate network packet. In another variant of the technique, Charles carefully interleaves packets coming from multiple senders. That eliminates the need for Charles to generate and inject bogus packets in the communication. However, the text of Alice's message cannot be well protected from other parties who are communicating via Charles at the same time. This variant also helps protect against information leakage and traffic analysis.^{[citation needed]}

See also

• Null cipher
• Spam email

External links

• Rivest's article on chaffing and winnowing