Compression side channel

[Peter Wayner]

>
>
>b.  I'm hoping to find out if anyone else has seen similar work
>anywhere.  I've not been able to find any references to this kind of
>attack, though once you've had the idea to try it, it's really pretty
>straightforward.  (And I know there are a couple of occasional posters
>on this list who know a heck of a lot more about compression algorithms
>than I do.  Peter, are you listening?)

These are all good ideas, but I don't know how often you'll get to 
try them, much less use them enough to extract enough information.

I wrote a paper a long time ago that tweaked compression algorithms. 
It wasn't meant to be secure, only ensure that the compression 
algorithms constantly changed the set of bits assigned to each 
character. This meant that a Huffman algorithm encoding 'e' as '0010' 
at one point would use '1011' later. It was a simple remapping of the 
compression tree so it wouldn't cost much.

But I don't think it had any security on its own.

-Peter



>
>The basic result: Lossless compression algorithms leak data about their
>input in the size of their output.  This is really obvious; if some
>inputs didn't compress better than others, we'd either have no
>compression, or lossy compression.  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.  Using a slightly more complicated model for
>building the X[i], I've experimentally extracted 16- and 32-digit PINs
>from messages, using only a few thousand chosen texts and a pretty small
>amount of processing power.  (The code to run the attack is written in
>Python, so it really doesn't have a lot of speed.)  The gist of the
>attack is that I request a bunch of possible 4-digit subsequences in my
>messages, and use how well subsequence+S compresses as a way to place
>those subsequences in order of likelihood that they appear in S.  I then
>try to piece together high-probability candidate sequences for S, based
>on making the subsequences fit together.  I end up with an ordered list
>of likely S guesses, and can get the right answer in my top 20
>candidates about 60-70% of the time with random PINs for S.
>
>There are a bunch of other attacks along these lines.  For example, I
>believe a variant of this attack is possible using known plaintexts
>only.  And with a much weaker kind of chosen plaintext access, we can do
>"string testing," e.g., if we think we know a long subsequence in S, we
>can request E(S+guess), and see what the compression ratio looks like.
>And we can watch a compressed and encrypted stream, and use the
>bandwidth to determine how much redundancy is in the plaintext.  (At
>least, we can determine how much redundancy of a kind the compression
>algorithm is designed to detect and use is present in the plaintext.)
>
>Comments?
>
>- --John Kelsey, kelsey.j at ix.netcom.com / jkelsey at certicom.com
>
>
>-----BEGIN PGP SIGNATURE-----
>Version: PGP 6.5.1 Int.
>
>iQCVAwUBO5rWQyZv+/Ry/LrBAQHowAP/UllCbIhqITK6dYyTgvmsLTlLQUIPGgqf
>poVHkwEgKO+SiEF6BC8j+WG32gLKZ5pcbLyXusyOipR5PegrknxRD/yKvw+yuGFo
>nWumXyuZ/W4W4mQnISoDgtqi/2Zh+7/3Nph8rllZIWO8z8ooqDgUbPAEMnTxmPAj
>/gKeoQzNoto=
>=4rOb
>-----END PGP SIGNATURE-----
>
>
>
>
>---------------------------------------------------------------------
>The Cryptography Mailing List
>Unsubscribe by sending "unsubscribe cryptography" to 
>majordomo at wasabisystems.com




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