---------- Forwarded message ---------- Date: Fri, 10 Aug 2001 01:35:39 -0300 From: "Paulo S. L. M. Barreto" <paulo.barreto@terra.com.br> To: coderpunks@toad.com Subject: NSA withdraws proposed mode of operation Many coderpunks probably already know the details; anyway, here's the story. Phillip Rogaway's description of the weaknesses found in NSA's Dual Counter Mode are at the bottom. Enjoy, Paulo. ---------- Forwarded message ---------- Date: Thu, 09 Aug 2001 07:25:34 -0400 From: Robert Shea <rshea@radium.ncsc.mil> Subject: Dual Counter Mode (DCM) On behalf of Brian Snow, Technical Director, Information Assurance, NSA, the following message is forwarded to the AES Team at NIST: NSA believes that a license-free high-speed integrity-preserving mode of operation is needed for the Advanced Encryption Standard, and was pleased to submit the "Dual Counter Mode" (DCM) as a participant in the series of AES Modes Workshops sponsored by NIST. Recently Virgil Gligor and Pompiliu Donescu of the University of Maryland, Phillip Rogaway of the UC Davis and Chiang Mai University, David Wagner of Berkeley, and possibly others, have produced results concerning the secrecy and integrity claims made for DCM. We commend them for their work We withdraw the Dual Counter Mode for consideration as a mode of operation for AES at this time, while we consider the observations and their ramifications. We believe a license-free high-speed integrity-preserving mode of operation is still needed for AES, and will continue to work on this problem as well as encourage others to do so. Brian D. Snow Technical Director Information Assurance Directorate National Security Agency ---------------------------------------------------------------------- Topic: Comments on "Dual Counter Mode" (manuscript date: 4 July 2001) (a modes-of-operation proposal by Mike Boyle and Chris Salter) From: Phillip Rogaway UC Davis and Chiang Mai University Date: Aug 4, 2001 ---------------------------------------------------------------------- 1. DEFINITION OF DCM The definition of DCM isn't real clear, but this is what I understand. Let P = P_1 P_2 ... P_j be the plaintext to encrypt, where one assumes each |P_i|=n and j>0. Let Key = (K, x_0) be the DCM key, where K keys an n-bit block cipher E (I refuse to use "W" for the block length!) and x_0 is a n-bit string. For concreteness, say n = 128. Let N be an n-bit nonce. (The authors specify N = SEQ | SPI | padding, but I shall ignore this, it being, to me, an inappropriate mixing of an application of a mode and the definition of that mode.) The authors map (N, x_0) into a sequence of offsets (they call them "fills") y_0 y_1 y_2 ... y_j y_{j+1} by y_0 = x_0 + N // addition mod 2^n, for example and, for i>0, y_i = multx(y_{i-1}), where, say, / (a << 1) if msb(a)=0 multx(a) = | \ (a << 1) xor 0^{120}10000111 if msb(a)=1 That is, y_i = (x_0 + N) * x^i, where the multiplication is in GF(2^n). Now define DCM_Key (N, P) as C = C_1 C_2 ... C_j C_{j+1} where C_i = E_K( P_i xor y_i) xor y_i for i in [1..j] checksum = P_1 xor ... xor P_j xor N C_{j+1} = E_K(checksum xor y_{j+1}) xor y_0 2. COMPARISON WITH IAPM DCM is identical to IAPM except (a) IAPM omits the nonce N from the checksum (why these authors include the nonce I do not know); and (b) IAPM suggested different (and smarter) ways to make the offsets. 3. THE CHANGES DON'T WORK The changes to IAPM break it; one can see rather easily that DCM does not achieve the usual definitions for privacy or authenticity. 3.1 NO SEMANTIC SECURITY (the customary privacy definition) For simplicity, assume lsb(x_0)=0. (This happens half the time so there is no problem making this assumption.) First observe that nonces with related values map to offsets with related values. In particular, nonces N and (N xor 1) (in a context like this "1" means 0^{n-1}1) map to offsets the first few of which are: N |--> y_0, y_1, y_2 N xor 1 |--> y_0 xor 1, y_1 xor 2, y_2 xor 4 Let the adversary ask a query DCM_Key(0, 0), obtaining a ciphertext that starts with first block C_1; now note that first block of DCM_Key(1, 2) will be C_1 xor 2. This violates privacy. (For example, you can easily tell apart the sequence of messages 0, 0 and 0, 2 when they are DCM-encrypted using nonces 0 and then 1.) [Reminder: my notation is ciphertext = DCM_Key(nonce, plaintext)] 3.2. NO AUTHENTICITY OF CIPHERTEXTS (the customary authenticity definition) For convenience of description, assume that the first two bits and the last two bits of x_0 are 00 (which happens 1/16 of the time, anyway). Let the adversary ask queries: DCM_Key(0, 0) --> getting C_1 C_2. DCM_Key(1, 0 2) --> getting C_1' C_2' C_3' Note: C_2 = E_K(x_0 << 2) xor x_0 and C_2' = E_K((x_0 + 1 << 2) xor 2) xor (x_0 + 1) << 2 = E_K(x_0 << 2) xor (x_0 << 2) xor 2 So C_2 xor x_0 = C_2' xor (x_0<<2) xor 2 and thus x_0 xor (x_0 <<2) = C_2 xor C_2' xor 2 Solve for x_0 (easy by our assumption that x_0 ends in 00). With x_0 now known, one can compute the y_0, y_1, y_2 values associated to any nonce. Forging a ciphertext becomes easy. 4. AND WHAT IF THE NONCE HAD BEEN SEQ | SPI | padding? I think it wouldn't have mattered. With a choice of N = N' | comp(N'), say, where N' is a 64-bit nonce, N' and (N' xor 1) would still map to y_1 and y_1 xor 2, respectively, so you could play the same sorts of games. 5. WHAT'S THE STORY HERE? The entire discussion of out-of-order-packets in the DCM note makes no real sense, as best as I can tell. The authors "solution" amounts to throwing in a nonce -- which is of course present in all of the authenticated-encryption proposals already. The introductory statements about the overhead of IAPM (and other proposals) seems to reflect a non-understanding of that mode. And then the mode itself, which was so easily attacked. All rather odd.