Chaffing and winnowing

related topics
{system, computer, user}
{law, state, case}
{food, make, wine}
{math, number, function}

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

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 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.


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.

Full article ▸

related documents
Real-time operating system
Apple IIe Card
Very-large-scale integration
Motorola 68020
Composite video
Capacitive coupling
Break key
Digital image processing
Picture archiving and communication system
S-100 bus
Audio signal processing
RAM disk
Frequency-shift keying
Open Systems Interconnection
Cambridge Z88
Intel 80286
Telephony Application Programming Interface
Channel access method
Direct-sequence spread spectrum
Motorola 6809
Asynchronous communication