Rivest's Chaffing and Winnowing

The New York Times, March 22, 1998, p. 31.

   New Method To Veil Data Could Upstage Export Policy 

      Cryptologists find a way to foil eavesdroppers without
      secret codes.

   By John Markoff

   San Francisco, March 21 -- One of the nation's leading
   computer scientists has proposed a novel technique for
   scrambling data that could circumvent Government export
   policies aimed at limiting the foreign sale of encryption
   technology.

   The technique, which was described this week in an Internet
   discussion among computer researchers, was introduced by
   Ronald L. Rivest, a computer scientist at the Massachusetts
   Institute of Technology and one of the inventors of the
   most widely used commercial encryption scheme, RSA.

   The new approach, which is described in a short technical
   paper that has been posted to Mr. Rivest's M.I.T. Web site
   (http://theory.lcs.mit.edu/~rivest/chaffing.txt), is
   described as "chaffing and winnowing" digital information
   instead of encrypting it.

   According to Mr. Rivest's paper, it is possible to hide a
   message by breaking it into packets that are then secretly
   identified as good information, or "wheat," and gibberish,
   or "chaff," in such a way that an eavesdropper cannot
   distinguish the two.

   Because the individual packets would not be encrypted, Mr.
   Rivest said, such a system would circumvent current export
   restrictions.

   The two principal ways of communicating in secret are
   encryption and steganography. Steganography uses computer
   techniques to embed a secret message in a document like a
   digital image. In encryption, secret information is encoded
   using functions that require difficult mathematical tasks
   to decode, and it has become the standard way of
   transmitting secret information electronically.

   There are no restrictions on the domestic use of this
   technology, but the Government has been trying to force the
   industry to adopt standards that would permit
   law-enforcement officials to have mathematical keys
   allowing them to decode messages without the knowledge of
   the sender or receiver. The Clinton Administration says the
   standards are needed to fight crime and terrorism.
   Opponents argue that the Government decoding keys, to be
   stored in computers, could easily be stolen, compromising
   privacy and the security of credit card numbers and other
   personal information.

   In terms of exports, with few exceptions the Government
   limits the software to codes that can be easily broken.

   "Winnowing does not employ encryption, and so does not have
   a 'decryption key,' " Mr. Rivest wrote in his paper. "As
   usual, the policy debate about regulating technology ends
   up being obsoleted by technological innovations."

   Peter Neumann, an SRI International computer scientist who
   has read Mr. Rivest's paper, said that although "there is
   still no certainty that this is a practical idea," if it
   works, "it throws another clinker at the Justice
   Department."

   Other cryptography experts said they were uncertain whether
   it would be possible to skirt Government export
   restrictions in this way, but that the idea was an
   impressive new approach that might have valuable commercial
   applications.

   "He's a very clever guy," said George Spix, a Microsoft
   researcher who specializes in cryptography policy issues.
   " It goes to show that for all the technological wizardry
   in the world, there's nothing like an intellect."

   One of the potential limitations of the new method is that
   the total information transmitted might need to be hundreds
   of times larger than the actual message.

   Mr. Rivest said, however, that he had discussed the idea
   with Adi Shamir, an Israeli cryptographer, and that Mr.
   Shamir had proposed compression methods that would reduce
   the total transmission to only about twice the actual
   message size.

   The strength of the idea for chaffing and winnowing is that

   it is possible to prove mathematically that a message
   cannot be decoded, Mr. Rivest said.

   He said he had come up with the idea recently while
   teaching an undergraduate computer course.

   In addition to his role as associate director of the
   Laboratory of Computer Science at M.I.T., Mr. Rivest is a
   consultant and shareholder in RSA Data Security Inc., a
   company that develops encryption software.

   "I put the winnowing and chaffing idea out there to
   stimulate debate,"' Mr. Rivest said. "I hope it will help
   clear up some of the issues that have been raised in the
   policy discussion.
             
   [End]

-----BEGIN PGP SIGNED MESSAGE-----

On Sun, 22 Mar 1998, John Young wrote:

>    The New York Times, March 22, 1998, p. 31.
>
>    New Method To Veil Data Could Upstage Export Policy
>
>       Cryptologists find a way to foil eavesdroppers without
>       secret codes.

As if steganography was new.

>    The new approach, which is described in a short technical
>    paper that has been posted to Mr. Rivest's M.I.T. Web site
>    (http://theory.lcs.mit.edu/~rivest/chaffing.txt), is
>    described as "chaffing and winnowing" digital information
>    instead of encrypting it.

Using steganoraphic techniques on low-level elements of
network communication (packets) was considered many years ago
in this very forum.  A particular suggestion seemed much more
effective than Rivest's proposal.  It aim was to hide
information among seemingly innocuous communication.  Whereas,
it is obvious to any observer of a "chaffing" exchange that
an abnormal exchange was taking place.

Of course, if all communication was "chaffed" then that same
exchange would seem perfectly ordinary.  However, the chaffing
technique (creating "bogus" packets, transmitting them along
with the real information, and seperating the two) creates
a lot of overhead... which may not use much bandwidth if
used occasionally, but would create a serious problem if
everyone did it all the time.

>    According to Mr. Rivest's paper, it is possible to hide a
>    message by breaking it into packets that are then secretly
>    identified as good information, or "wheat," and gibberish,
>    or "chaff," in such a way that an eavesdropper cannot
>    distinguish the two.

The earlier suggestion was to hide information in unused, least
significant, portions of the packet _header_, leaving the data
portion intact.  Thus, the overhead of creating "bogus" packets
is eliminated, the bandwidth used in sending them is conserved,
and the processing power used in seperating the "wheat" from the
"chaff" is freed.

Further, by all accounts, the data transmitted would seem
perfectly ordinary to an eavesdropper.  It could be a poem or
a picture.  However, it would be completely irrelevant, as
the real message is hidden in the header.

Finally, there are the more traditional steganographic techniques
such as using the least significant bits of gifs, jpegs, and wavs.
And, most intriguing of all, mimic functions.


 ............................................................................
 . Sergey Goldgaber <sergey@el.net>                 Senior System Engineer  .
 ............................................................................
 .   To him who does not know the world is on fire, I have nothing to say   .
 .                                                      - Bertholt Brecht   .
 ............................................................................

-----BEGIN PGP SIGNATURE-----
Version: 2.6.2

iQCVAwUBNRVG+Mgbnd/MibbZAQEaRwP9Fy825U05t9xyHa0vN5wFFCNBR0NHrik0
cFBG357a1+MRA90uxvUztB736uf71a39HP0172sjyAg3TXVG9MEpCxFDDa6OZAWQ
9Xgq9TSaUTJUXJVsockFTHF6F9zDLIAvw2s365J4dr3++Uj/JreaaX7pcLVmCujO
DkuInR89aG8=
=B9nV
-----END PGP SIGNATURE-----