Re: replay field size

[Bart Preneel <[e-mail]>]

Linear cryptanalysis of DES:

> Date: Thu, 13 Feb 1997 11:37:39 -0500
> From: Steven Bellovin <[e-mail]>
> To: Ran Atkinson <[e-mail]>
> Cc: Robert Glenn <[e-mail]>, Stephen Kent <[e-mail]>,
>     [e-mail]
> Subject: Re: replay field size 
>
> [...]
> 
> But it's worse than that.  At 250 bytes/packet, there are about 2^5 DES
> blocks/packet, which means there are 2^37 blocks per ``full'' 32-bit
> security association.  That's getting unpleasantly close to the point
> where linear cryptanalysis is feasible.  (Matsui's CRYPTO '94 paper
> says that with 2^38 known plaintexts, the success rate is 10% with
> complexity 2^50.  The new ``Handbook of Applied Cryptography'' notes
> that ``linear cryptanalysis is possible in a ciphertext-only
> environment if some underlying plaintext redundancy is known (e.g.,
> parity bits or high-order 0-bits in ASCII characters.))  I submit that
> we really don't want to encrypt that much plaintext with any single key
> -- ever.  And of course, we don't know that linear cryptanalysis is the
> ultimate attack.

As far as I know, the extension of Matsui's attack to ciphertext only
(given ASCII plaintext) requires at least 2^{10} times more ciphertext
(see Matsui's Eurocrypt'93 paper). So 2^{38} known plaintexts will become 
something like 2^{48} ciphertext only.  This can probably be still 
improved, but it is not very serious as threat. 

Given the complexity of 2^{50}, it is probably much easier to build 
the DES key search machine -- success probability of 1.6%), which needs 
only 1 plaintext/ciphertext pair, rather than to collect all the data 
on 2^{48} ciphertexts. A complexity of 2^{40} seems more realistic to me, 
which implies that about 10 times more ciphertexts are required.

I would be much more concerned about the `matching ciphertext' problem of 
the CBC-mode: information on the plaintext starts to leak after 2^{33}
blocks (for 2^{38} there will be already 2000 matches). 
A very good reason to never encrypt more than 2^{33} plaintexts with a single key.


Bart Preneel
-------------------------------------------------------------------------------
Katholieke Universiteit Leuven                 tel. [phone]
Dept. Electrical Engineering-ESAT / COSIC      fax. [phone]
K. Mercierlaan 94, B-3001 Heverlee, BELGIUM    [e-mail]
-------------------------------------------------------------------------------