Compression side channel

[Ben Laurie]

Sandy Harris wrote:
> 
> John Kelsey wrote:
> 
> > The basic result: Lossless compression algorithms leak data about their
> > input in the size of their output.  ... However, compressors like Zip
> > deflate and Unix compress maintain state, which is changed as new bytes
> > of text are processed.  This state basically is used to make future
> > texts compress better if they're more like recent texts.
> >
> > This leads to some really powerful attacks, at least in the
> > chosen-plaintext model.  We have something like
> >
> >         E(X) = encrypt(compress(X))
> >
> > where the encryption preserves length (e.g., RC4 encryption).  Suppose
> > someone is sending a secret S in these messages, and the attacker gets
> > to choose some prefix or suffix to send, e.g.
> >
> > X[0] = S+suffix[0]
> > X[1] = S+suffix[1]
> > ...
> >
> > Well, if the attacker can watch how these compress, he can learn a *lot*
> > about these secret strings.
> 
> Once you've pointed it out, it seems obvious, but at least to me it wasn't
> until you did. Methinks that indicates a good piece of work on your part.
> 
> Does using non-adaptive compression save the day?

If you know the length of the plaintext and the encoding, no (because
the length reduction gives hints about the plaintext again - in the
worst case, it could give it away completely, so it could actually be
worse than adaptive compression).

If you have no idea of the length, then my guess is that it does help.

Cheers,

Ben.

--
http://www.apache-ssl.org/ben.html

"There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit." - Robert Woodruff



---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com