compression & nulls in cryptosystems

[John Kelsey]

At 06:30 AM 5/31/01 -0400, John Denker wrote:
...
>  3) I can imagine how an attacker could feed chosen plaintext through my 
>moat.  For instance she could email me a chosen message and expect me to 
>download it via the moat.  But getting back to the topic of compression and 
>nulls:  It would seem that they would serve to convert the chosen text into 
>a partially-chosen but partially-unknown (!) text.

Actually, using CBC more-or-less ruins chosen plaintext attacks.  Each long
message gives you, at most, one block whose value going into the block
cipher you can control (assuming you know the IV ahead of time).  After
that, the blocks going in are XORed with the previous ciphertext, and you
presumably don't know what that will be until you've gotten back that first
ciphertext.  

...
>  *) If the point is that compression and nulls have infinite cost or zero 
>value, then I find this highly implausible.
>  -- ISTM nulls would materially hinder differential cryptanalysis.
>  -- ISTM nulls would materially hinder linear cryptanalysis.
>  -- ISTM compression+nulls would materially hinder a key-search
>     along the lines of the EFF DES cracker.
>  -- Can somebody give examples of attacks that would not be hindered?

I gave an example in a note I sent a few minutes ago, where keysearch
machines would have little trouble with your scheme: wait for a packet of
some really short length, and build the keysearch machine to decrypt the
whole short packet and run your decompression scheme on it.  These will
trivially distinguish the known packet value from incorrect values.  

For differential cryptanalysis, you more-or-less need chosen plaintexts, so
anything that prevents you getting chosen plaintexts is a problem.  For
linear cryptanalysis, you more-or-less need known plaintexts, so anything
that prevents you getting them is a problem.  But if I know whole packets,
and the compression+nulls scheme is public, then I have known plaintext.
So I don't think your scheme helps much against linear cryptanalysis.  DC
is impeded both by your scheme, and by using CBC mode encryption.  

>  *) If the point is that there is something else we should be doing with 
>our bandwidth and computational resources, it would help to have a more 
>explicit statement of what the alternatives are, and their relative costs 
>and effectiveness.

Switching from single-DES to triple-DES, or even to DESX (DES with a fixed
64-bit key XORed in before and after encryption), demonstrably increases
security against keysearch attack.  Switching over to DESX costs almost
nothing, and yet has a much bigger impact than compressing your input does,
at least for those short packets.  

...
>I always scratch my head when somebody says that XX attack on YY algorithm 
>requires a huge carefully-chosen plaintext, and ends the discussion there, 
>when by adding nulls you can guarantee that no chosen plaintext ever gets 
>processed as such.

But CBC-mode does the same thing much more cheaply.  

--John



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