From msuinfo!uwm.edu!vixen.cso.uiuc.edu!howland.reston.ans.net!usenet.ins.cwru.edu!eff!news.kei.com!ddsw1!chinet!schneier Thu Jan 20 23:12:54 1994 Newsgroups: sci.crypt Path: msuinfo!uwm.edu!vixen.cso.uiuc.edu!howland.reston.ans.net!usenet.ins.cwru.edu!eff!news.kei.com!ddsw1!chinet!schneier From: schneier@chinet.chinet.com (Bruce Schneier) Subject: New Attack on 8-round DES Message-ID: Organization: Chinet - Public Access UNIX Date: Wed, 19 Jan 1994 15:55:47 GMT Lines: 184 At the RSA Conference last week, Martin Hellman presented a new cryptanalytic result with his doctoral student, Susan Langford. The attack combines aspects of linear and differential cryptanalysis to break 8-round DES faster than was previously possible. At this time the attack does not extend to 16-round DES, but I am hopeful. Following is Hellman's announcement: MAIN RESULT: a chosen text attack on 8- round DES that recovers 10 bits of key, takes less than than 10 seconds on a SUN-4 workstation, has 80% probability of success with only 512 chosen plaintexts and 95% probability of success with 768 chosen plaintexts. While the time is comparable to pre-existing attacks, the amount of required text is significantly reduced. The best current Biham- Shamir 8-round attack requires over 5,000 chosen plaintexts, and Matsui's attack, presented at Eurocrypt '93, requires approximately 500,000 known plaintexts. [Since Matsui uses a much more desirable known plaintext attack, direct comparison is not possible with his results and his much larger number of required plaintexts noted above should not be taken as making his attack of less interest than either Biham-Shamir or ours. On the contrary, his paper is an impressive and important advance.] Both Biham-Shamir and Matsui recover more bits of key than we do, reducing the cost of the semi-exhaustive search that follows the analysis phase. (We hope to get more key with further study. See the last paragraph below for a start.) NOTE: In what follows, we use FIPSPUB-46's DES numbering so that plaintext, ciphertext and intermediate result bits are numbered from 1 to 64 reading from right to left. This differs from Matsui's numbering which numbers bits from 0 to 63, reading from right to left. BASIC APPROACH: Toggling bits 2 and/or 3 in round n [that is, bits 2 and/or 3 of (L_n,R_n)] and keeping all remaining 62 bits unchanged, causes bits 3, 8, 14, 25, and 49 in round n+3 to be unchanged. (The same applies to toggling bits 10 and/or 11, but for simplicity we will not deal with that here.) The parity (mod-2 sum) of bits 3, 8, 14, 25, and 49 in round n+3 is therefore also invariant under this transformation in round n. These five bits correspond to the input bits of Matsui's best three round probabilistic parity relation, which holds with probability p = 0.695. Hence, the parity of Matsui's output bits (bits 3, 8, 14, 25, and 49 in round n+6) is unchanged with probability p^2 + q^2 = 0.576 where q = 1- p. (The probability is p^2 + q^2 because Matsui's parity relation must hold, or fail, twice -- once for the reference plaintext and once for the plaintext which toggles only bits 2 and/or 3 in round n.) By a technique to be described below, we choose n=1 as the round in which the toggling of bits 2 and/or 3 occurs, so that the parity invariance to be observed occurs in round n+6 = 7 with probabiltiy 0.576. Following Matsui, we decipher the corresponding two ciphertexts backward through one round to get the output bits of the parity relation: bits 3, 8, 14, 25, and 49 in round 7, before the swap of L and R. Bits 3, 8, 14, and 25 are known because they are part of the ciphertext, and only bit 49 must be deciphered. Deciphering bit 49 involves only S1 in round 8, so we can test the 6-bit subkey K_{8,1} used by S1 in round 8. When the correct value is used, we should observe parity invariance 57.6% of the time, and when an incorrect value is used, we should observe parity invariance approximately 50% of the time. Based on Matsui's rule of thumb that approximately 8/(|p-0.5|^2) observations are needed when p is the probability of observing a parity relation, this would predict that about 1,400 plaintext pairs, or 2,800 chosen plaintexts, would be required. This number must be increased to account for the method of obtaining the desired toggling in round 1 as opposed to round 0 (the plaintext), but is decreased by another technique, soon to be described. Toggling bits 2 and/or 3 in round 1 is obtained using structures related to Biham and Shamir's 16-round attack on DES. Choose any reference plaintext and let P(0) through P(64) be the 64 plaintexts obtained by adding (XOR'ing) all possible 6-bit patterns to the reference plaintext, where the six bits involved are bits 9, 17, 23, and 31 of L0 and bits 2 and 3 of R0. The bits of L0 correspond to the four outputs of S1, and bits 2 and 3 of R0 become bits 2 and 3 of L1, the bits we want toggled. Since the only bit(s) changed in R0 are input(s) to S1, only the outputs of S1 can change in round 1. Because we included all 16 possibilities in the structure, if we knew the 6- bit subkey K_{1,1}, for each of the 64 P(i)'s we could choose three other P(j)'s which had the desired toggling in round 1. One P(j) would toggle bit 2, one would toggle bit 3, and one would toggle bits 2 and 3. All three pairs could be used to help determine K_{8,1}. Since we do not know K_{1,1), we could test all 64^2 = 4096 values of (K_{1,1},K_{8,1}), but two of the bits of K_{1,1) are equal to two of the bits of K_{8,1}, so that there are only 1024 possible subkey pairs to search over. The need to search over 1024 instead of 64 values increases the required number of observations above Matsui's 8/(|p-0.5|^2) rule of thumb, as noted above. However, each structure of 64 plaintexts produces 64*3 observations, of which half or 96, are independent (i,j and j,i were both counted in the 64*3), decreasing the required number of plaintexts from the simple approach that requires two chosen plaintexts (one pair) per observation. The net effect, determined experimentally, is that 512 chosen plaintexts allow an 80% success rate and 768 chosen plaintexts allow a 95% success rate in determining the 10 bits of key in (K_{1,1},K_{8,1}). An even higher success rate can be had, with no increase in the number of required plaintexts, if we are willing to use ideas related to "list decoding" of error correcting codes. The most likely (K_{1,1},K_{8,1}) would be tried first in the semi-exhaustive search and, if it did not work (which would happen one time in fifty), the next most likely value could be tried, etc. With a list of two, this would increase the average computation by only 2%,while significantly decreasing the probability of failure. Additional bits of key can be recovered by using other, lower probability 3-round parity relations in rounds 5 to 7, in place of Matsui's optimal 3- round parity relation. For example, bits 5, 13, 21, 27, and 63 of round 4 also remain unchanged when bits 2 and/or 3 of round 1 are toggled. Therefore, we can use a 3-round parity invariance involving these bits and bits 5, 13, 21, 27, and 61 of round 7 which holds with probability 0.527, instead of Matsui's optimal 0.576. Deciphering S6 through round 8 as described above allows us to recover the six additional bits of key K_{8,6}. Although the probability distribution of this second parity relation is significantly worse than the optimal relation, the probability of error is not much higher because of the smaller number of key bits being found. For example, the 768 chosen plaintexts which had a 95% success rate on the first ten bits of key, have an 85% success rate for all sixteen bits of key. However, the idea of list decoding, mentioned above, can be applied here with even greater success.