Chaffing and winnowing
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 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.
The sender (Alice
) wants to send a message to the receiver (Bob
). In the simplest setup, Alice enumerates the bit
s 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.
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
.
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
technique to achieve confidentiality
Confidentiality
Confidentiality is an ethical principle associated with several professions . In ethics, and in law and alternative forms of legal resolution such as mediation, some types of communication between a person and one of these professionals are "privileged" and may not be discussed or divulged to...
without using encryption
Encryption
In cryptography, encryption is the process of transforming information using an algorithm to make it unreadable to anyone except those possessing special knowledge, usually referred to as a key. The result of the process is encrypted information...
when sending data over an insecure channel. The name is derived from agriculture: after grain has been harvested and threshed
Threshing
Threshing is the process of loosening the edible part of cereal grain from the scaly, inedible chaff that surrounds it. It is the step in grain preparation after harvesting and before winnowing, which separates the loosened chaff from the grain...
, it remains mixed together with inedible fibrous chaff
Chaff
Chaff is the dry, scaly protective casings of the seeds of cereal grain, or similar fine, dry, scaly plant material such as scaly parts of flowers, or finely chopped straw...
. The chaff and grain are then separated by winnowing, and the chaff is discarded. The technique was conceived by Ron Rivest
Ron Rivest
Ronald Linn Rivest is a cryptographer. He is the Andrew and Erna Viterbi Professor of Computer Science at MIT's Department of Electrical Engineering and Computer Science and a member of MIT's Computer Science and Artificial Intelligence Laboratory...
. Although it bears similarities to both traditional encryption and steganography
Steganography
Steganography is the art and science of writing hidden messages in such a way that no one, apart from the sender and intended recipient, suspects the existence of the message, a form of security through obscurity...
, 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
Authentication
Authentication is the act of confirming the truth of an attribute of a datum or entity...
. 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 |
|
adds 4 chaff packets with inverted bits and invalid MAC, shown in italics (chaffing) |
|
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
Alice and Bob
The names Alice and Bob are commonly used placeholder names for archetypal characters in fields such as cryptography and physics. The names are used for convenience; for example, "Alice sends a message to Bob encrypted with his public key" is easier to follow than "Party A sends a message to Party...
) wants to send a message to the receiver (Bob
Alice and Bob
The names Alice and Bob are commonly used placeholder names for archetypal characters in fields such as cryptography and physics. The names are used for convenience; for example, "Alice sends a message to Bob encrypted with his public key" is easier to follow than "Party A sends a message to Party...
). In the simplest setup, Alice enumerates the bit
Bit
A bit is the basic unit of information in computing and telecommunications; it is the amount of information stored by a digital device or other physical system that exists in one of two possible distinct states...
s 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
Message authentication code
In cryptography, a message authentication code is a short piece of information used to authenticate a message.A MAC algorithm, sometimes called a keyed hash function, accepts as input a secret key and an arbitrary-length message to be authenticated, and outputs a MAC...
(MAC) whose secret key Alice shares with Bob. Charles
Alice and Bob
The names Alice and Bob are commonly used placeholder names for archetypal characters in fields such as cryptography and physics. The names are used for convenience; for example, "Alice sends a message to Bob encrypted with his public key" is easier to follow than "Party A sends a message to Party...
, 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 transformAll-or-nothing transform
In cryptography, an all-or-nothing transform , also known as an all-or-nothing protocol, is an encryption mode which allows the data to be understood only if all of it is known. AONTs are not encryption, but frequently make use of symmetric ciphers and may be applied before encryption...
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
Internet
The Internet is a global system of interconnected computer networks that use the standard Internet protocol suite to serve billions of users worldwide...
, 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
Information leakage
Information leakage happens whenever a system that is designed to be closed to an eavesdropper reveals some information to unauthorized parties nonetheless. For example, when designing an encrypted instant messaging network, a network engineer without the capacity to crack your encryption codes...
and traffic analysis
Traffic analysis
Traffic analysis is the process of intercepting and examining messages in order to deduce information from patterns in communication. It can be performed even when the messages are encrypted and cannot be decrypted. In general, the greater the number of messages observed, or even intercepted and...
.