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

Re: IV sizes for AES candidates

In message <009c01c003c2$465b9640$4f81003e@checkpoint.com>, "Tamir Zegman" writ
>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
>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.

That's not the threat model we're concerned about.  In fact, all your 
threat shows is that C1=C2 if the plaintexts are close, and that isn't 
that important.

Let + = addition, ^ = XOR, and assume that there are two plaintext 
messages from the same stream M1 and M2.  Assume further that M1 is k 
cipherblocks long, and that k is small.  (That is reasonable, since 
40-50% of packets are ~40 bytes.)

I showed in a 1997 paper that (a) if you add a small number to a 
counter, the old value and the new still agree in most bit positions, 
and (b) corresponding blocks of adjacent packets from the same stream 
are likely to be very similar, i.e., have a low Hamming distance 
between them.

Consider the first block of ciphertext from M1 and M2 (I'll forgo 
writing M1[1] and C1[1]):

	C1 = AES(X) ^ M1
	C2 = AES(X+k) ^ M2

Per my 1997 analysis, M1^M2 != 0, but M1^M2 ~= 0.  But

	C1 ^ C2 = AES(X) ^ M1 ^ AES(X+k) ^ M2
		= (AES(X) ^ AES(X+k)) ^ (M1 ^ M2)
		~= AES(X) ^ AES(X+k)

Also note that the attacker will know X and k -- X, because it's sent 
in the clear as an "IV", and k from the length of C1.  What is then 
known is X^(X+k) and (approximately) AES(X)^AES(X+k).  The first 
pair has a low Hamming distance, so we have an approximatation to the 
input pairs and output pairs used for differential cryptanalysis and its 
relatives.  Furthermore, we can do this for each plaintext block in a 
packet known to be similar to the corresponding block in an adjacent 

Is this a threat?  I think that that question is really the same as "do 
we know that AES is immune to all current and future variants of 
differential cryptanalysis?"

		--Steve Bellovin