[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
es:
>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.
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
packet.
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