Jesús Cea Avión wrote:

You can have chaffing & winnowing without bandwidth overhead, but the resulting scheme hasn't the original "elegance" anymore. In particular, you don't send the plaintext on the clear.

The new schema is useful to cypher a document using any standard signature library, exportable by definition. Very nice :), since you can use, at last, strong crypto :).

a) When the connection starts, negociate an initial sequence number. The sequence number mustn't be reused. We assume a ordered delivery, like TCP.

b) Calculate the signature for:

[sequence]0 -> MAC0

and

[sequence]1 -> MAC1

c) Compare both MACs and locate the first "different" bit, from high to low bit or viceversa.

d) Send that bit from MAC0 if you want to send a "0" or from MAC1 if you want to send a "1".

On the contrary, it has an elegance all it's own :-). Since this idea has gone through several iterations, starting from Ron's original paper, I wanted to summarize in one place Jesus Cea Avion's idea. All credit for the following technique goes to him. Alice does this: Mreal = MAC(serial number, message bit, key) Mfake = MAC(serial number, complement of message bit, key) In english: She MACs both the bit she means, and then MACs the bit she does NOT mean. She then compares the two MACs to find the first different bit. Then she sends to Bob the bit from Mreal in the position of difference. When Bob gets the bit, he does this: Ma = MAC(serial number, 0, key) Mb = MAC(serial number, 1, key) He then compares Ma to Mb and finds the first difference. The bit in the position of difference is the one that was sent to him by Alice. He then knows whether Ma or Mb is correct. If Ma is the correct one then the plaintext bit is 0, if Mb is the correct one then the plaintext bit is 1. Remember that there is no need to send the serial number, but you MUST use it in the MAC. If you are using a reliable protocol like TCP, or storing it in a file, the serial number is implied by the order it was received/stored. However clever this technique is (and it *is* clever), it defeats the original purpose of Ron's idea. The original reason Ron created chaffing and winnowing was to show that encryption laws are useless. He demonstrated that you can use authentication technologies to create privacy. Even more, even if the government demands that the plaintext be in the open, his original paper was set up to pass even that egregious requirement. Think of what the govenrnment would see with this latest chaffing and winnowing. Two people are send a bitstream that is unreadable without a secret key. No plaintext is visible. In fact, it bears very little resemblance to the name "chaffing and winnowing." It would not matter to them wether you were using DES, IDEA, or C&W. If it looks like a duck, walks like a duck, and quacks like a duck... Another point of Ron's paper was that any technique the government tried to impose on C&W would create unacceptable problems. I dont think these problems would exist in this version of C&W. Anyone know better? -- o Mordy Ovits o Programmer / Cryptographer o SynData Technologies Inc. o Download A Free Copy Of Our Software At: o http://www.syncrypt.com

Jesús Cea Avión wrote:

...

You can have chaffing & winnowing without bandwidth overhead, but the resulting scheme hasn't the original "elegance" anymore. In particular, you don't send the plaintext on the clear. ... b) Calculate the signature for: [sequence]0 -> MAC0 [sequence]1 -> MAC1 c) Compare both MACs and locate the first "different" bit, from high to low bit or viceversa. d) Send that bit from MAC0 if you want to send a "0" or from MAC1 if you want to send a "1".

So why not _send_ the plaintext in the clear? Send the 0 bit, and the bit from the MAC0, and the 1 and the MAC1 bit 0 0, 1 1, 0 1, 1 0, Yes, it's expanding the data 4:1, but that's much better than before. At 12:04 PM 5/11/98 -0400, Mordechai Ovits wrote:

On the contrary, it has an elegance all it's own :-).

I strongly agree. I had proposed using a short checksum, e.g. 8 bits of the MAC, which does leave collisions every ~256 sets, but this is almost as short a checksum as you can get, and eliminates the collision except every ~2**64 pairs.

However clever this technique is (and it *is* clever), it defeats the original purpose of Ron's idea.

If you do include the data bits, you maintain (very marginally) the letter of the requirement here. What you do lose with this method is the ability to mix traffic from different people; 1 bit of MAC just isn't enough to pick out your own bits. Any short MAC limits the amount of mixing you can do; an 8-bit MAC lets you mix a bit without too many collisions, and a 64-bit MAC should be enough for any mixture you'd ever bother with (probably 16 or 32 would as well, though especially for 16 you'd still need a longitudinal checksum or some method of handling rare collisions.) Is it close enough for government work? Probably. Thanks! Bill Bill Stewart, bill.stewart@pobox.com PGP Fingerprint D454 E202 CBC8 40BF 3C85 B884 0ABE 4639

On Mon, 11 May 1998, Mordechai Ovits wrote:

...

In the Rivest's paper you transmit, indeed, all the 2^n plaintexts for a n bit length };-).

Not so. In his paper (before the package tranform stuff), he had the following expansion.

Note that any of the 2^n plaintexts cna be reconstructed from the following sequence of triples. (Assuming no knowledge of the MAC. The attacker has no idea which of each pair of triples related to each sequence is correct, so he must search every possibility, which turns out to be each of the 2^n plaintexts.)

Assuming a 32 bit serial number and a 160 bit MAC, n bits would expand to 388n. This is because Ron is sending it out like this: quote from http://theory.lcs.mit.edu/~rivest/chaffing.txt

...

To make this clearer with an example, note that the adversary will see triples of the form: (1,0,351216) (1,1,895634) (2,0,452412) (2,1,534981) (3,0,639723) (3,1,905344) (4,0,321329) (4,1,978823)

Ryan Anderson PGP fp: 7E 8E C6 54 96 AC D9 57 E4 F8 AE 9C 10 7E 78 C9

By the way, instead of transmitting the first bit for which MAC(sequence,0) differs from MAC(sequence,1), as Jesús suggests, you can get the same effect by transmitting a 0 or 1 depending on MAC(sequence,0) < MAC(sequence,1) (This assumes a big-endian system and unsigned comparisons; little-endians will have to calculate it the hard way.) If you're willing to be wrong 1 time out of 2**33, you can just use the top 32 bits. Earlier in this discussion:

...

In the Rivest's paper you transmit, indeed, all the 2^n plaintexts for a n bit length };-). Not so. In his paper (before the package tranform stuff), he had the following expansion. Assuming a 32 bit serial number and a 160 bit MAC, n bits would expand to 388n. To make this clearer with an example, note that the adversary will see triples of the form: (1,0,351216) (1,1,895634) (2,0,452412) (2,1,534981)

But that _does send the 2^n plaintexts, which are 0 and 1, and n=1. Thanks! Bill Bill Stewart, bill.stewart@pobox.com PGP Fingerprint D454 E202 CBC8 40BF 3C85 B884 0ABE 4639