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

*To*: "Tamir Zegman" <zegman@checkpoint.com>*Subject*: Re: IV sizes for AES candidates*From*: "Steven M. Bellovin" <smb@research.att.com>*Date*: Fri, 11 Aug 2000 15:10:32 -0400*Cc*: "Theodore Y. Ts'o" <tytso@mit.edu>, "Walker, Jesse" <jesse.walker@intel.com>, ipsec@lists.tislabs.com*Sender*: owner-ipsec@lists.tislabs.com

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

- Prev by Date:
**Re: IV sizes for AES candidates** - Next by Date:
**Re: IV sizes for AES candidates** - Prev by thread:
**Re: IV sizes for AES candidates** - Next by thread:
**RE: IV sizes for AES candidates** - Index(es):