Re: Chaffing & winnowing without overhead

[Ryan Anderson <ryan@michonline.com>]

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