[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: IV sizes for AES candidates

No, the low Hamming distance attack would not work here.
The attack goes as follows:
Denote a XOR operation by '+'
Assume you have 2 messages that differ only on one bit - M and M+1.
If you choose their two respective IV's as X and X+1 (that is X and X+1
differ only on the same bit as M and M+1), the two cleartexts will encrypt
to the same cipher text.
C1 = AES(M+X)
C2 = AES(M+1+X+1) = AES(M+X) = C1

In counter mode, if you have two counters with a low Hamming distance you'll
get:
C1 = AES(X) + M
C2 = AES(X+1) + M + 1
Since chances are that E(X) and E(X+1) have a high Hamming distance this
attack does not work in counter mode.


----- Original Message -----
From: Theodore Y. Ts'o <tytso@mit.edu>
To: Steven M. Bellovin <smb@research.att.com>
Cc: Walker, Jesse <jesse.walker@intel.com>; <ipsec@lists.tislabs.com>
Sent: Friday, August 11, 2000 6:41 AM
Subject: Re: IV sizes for AES candidates


>    From: "Steven M. Bellovin" <smb@research.att.com>
>    Date: Thu, 10 Aug 2000 14:29:13 -0400
>
>    In message
<392A357CE6FFD111AC3E00A0C99848B002FE990F@hdsmsx31.hd.intel.com>, "W
>    alker, Jesse" writes:
>    >I share Helger's desire to at least consider counter mode for AES.
Counter
>    >mode is an opportunity to gain better data privacy than CBC mode
offers and
>    >perhaps better performance as well. The WG can fall back to CBC mode
if
>    >scrutiny reveals counter mode is somehow inapplicable within ESP.
>
>    Counter mode appears to be one instance of a "seekable stream cipher",
>    per draft-mcgrew-ipsec-scesp-00.txt.  As was discussed in Pittsburgh,
>    there are a number of limitations, including the very strong
>    requirement for authentication and the need for a flat-out ban on using
>    it with manual keying -- if you don't use IKE, there's just too much
>    risk of seeing two streams encrypted with the same key and counter.
>
> When we talked how IV's for CBC mode, we were told that using a counter
> for the IV was a bad idea, because if the first eight bytes were known
> and fixed (as they commonly were), you could end up with known
> plaintext/ciphertext pairs that were a low hamming distance apart, and
> this could be used as a wedge to attack a cipher.
>
> If you use counter mode, doesn't this guarantee that in the face of
> known plaintext, you'll have a *lot* of known plaintext/cipgertext that
> have a low haming distance, and so would be subject to the same attacks
> as mentioned in the previous paragraph, right?
>
> So wouldn't the argument that says that we shouldn't use a counter to
> generate IV's also mean that using counter mode would also be a bad
> idea?  (This is in addition to all of the issues of an absolute
> requirement for using a MAC if you care about message integrity at
> all, and the dangers of resusing a keystream if you're not careful.)
>
> - Ted
>
>
References: