Chaffing and winnowing
From Wikipedia, the free encyclopedia
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 a cereal crop is harvested it remains mixed together with fibrous chaff, and must be separated out by a step of winnowing. It was conceived by Ron Rivest. Although the technique 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.
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 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. Bob uses the MAC to find the authentic messages and drops the "chaff" messages. This process is called "winnowing".
Eve, 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 "separate the wheat from the chaff"). That is infeasible, given that the MAC used is secure and that Charles does not leak any information on packet authenticity (via timing, for example).
When an authority 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 authority cannot order Alice to disclose an authentication key (which knowledge would enable the authority 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.
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]
