[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: replay field size
Linear cryptanalysis of DES:
> Date: Thu, 13 Feb 1997 11:37:39 -0500
> From: Steven Bellovin <smb@research.att.com>
> To: Ran Atkinson <rja@inet.org>
> Cc: Robert Glenn <glenn@snad.ncsl.nist.gov>, Stephen Kent <kent@bbn.com>,
> ipsec@tis.com
> 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. +32 16 32 11 48
Dept. Electrical Engineering-ESAT / COSIC fax. +32 16 32 19 86
K. Mercierlaan 94, B-3001 Heverlee, BELGIUM bart.preneel@esat.kuleuven.ac.be
-------------------------------------------------------------------------------
References: