The most well-known symmetric encryption algorithm is the Data Encryption Standard (DES). It denes a block cipher with 64-bit blocks and 56-bit keys. Due to questions raised regarding the small key size, several varieties of multiple encryption have been considered for the DES, including double and triple DES. Fig.1. Double encryption (top) and triple encryption (bottom) LM P E1 E2 PIC E1 LM E2 N E3 ABC In this paper, we consider arbitrary single encryption functions Ef0,1gk f0,1gs −! f0,1gs with k-bit keys and a block size of s bits, and in particular point out the consequences of our ndings for triple DES. Since multiple encryption is mainly of relevance to strengthen block ciphers with a small key space, we concentrate on k s. With two k-bit keys L and M and two encryption functions E1 and E2, double encryption is dened by C = E2 M(E1 L(P)). Here, C denotes the ciphertext and P the plaintext. Similarly, triple encryption is dened by C = E3 N(E2 M(E1 L(P))). Figure 1 describes double and triple encryption. If L =N, this denes the special case of two-key triple encryption. In this paper, we concentrate on the case of general (three-key) triple encryption. Double DES is double encryption with E1 = E2 = E. Triple DES is usually dened by E1 = E3 = E,E2 =D,whereE denotes the (single) DES encryption function and D its decryption counterpart. In general, we assume the functions Ei and Di to behave like a set of 2k random permutations Ei K with K 2f0,1gk, chosen according to the uniform probability distribution. Usually, nonrandom statistical properties are considered to be weaknesses of block ciphers. In the special case of the DES, two important statistical weaknesses are known, the complementation property, which is exploited in Section 6 of this paper, and a small number of weak keys. All attacks considered in this paper are key-search attacks and exploit known (or chosen) pairs of plaintext and ciphertext. To measure the complexity of an attack, we consider four values: 1. The number of known plaintext-ciphertext pairs. 2. The storage space required for the attack. 3. The number of single encryptions y := Ei K(x)orx := Di K(y) to mount the attack. 4. The overall number of operations (\steps") to mount the attack. The third value demands some explanation: Clearly, given a key K and a plaintext x (or a ciphertext y) the attacker can compute the corresponding ciphertext y := Ei K(x) (or the corresponding plaintext). A good block cipher behaves like a random permutation, hence given some triples (plaintext,ciphertext,key) one can't nd other triples more eciently than by encrypting/decrypting again. Attacking multiple encryption without breaking the underlying encryption function can be described as attacking multiple encryption in the presence of encryption/decryption oracles. Figure 2 visualizes such an oracle. The underlying cipher is treated as a black box. We simply write \single encryption" for accessing the encryption/decryption oracle. Much work has been done with respect to this model. This view also motivates to specically count the single encryptions, in addition to counting all steps. Note that such a single encryption counts as one step, but in practice is an exceptionally complex step by itself, compared to common operations like comparisons and table look-ups. One may as well concentrate on the number of single encryptions and disregard the number of steps and the amount of space required. This is an approved method for estimating the minimum strength of a composed cipher, in order to demonstrate the soundness of the composition technique. In this context, one neglects possible weaknesses of the underlying encryption functions. Idealizations of the underlying encryption functions are accessible to the attacker by querying encryption/decryption oracles, but the attacker has no knowledge about the oracles' internals. In the sequel, we refer to this point of view as the \black-box-only" model. The rest of this paper is organized as follows. Section 2 describes previously known attacks, concentrating on the meet-in-the-middle attack. In Section 3, we introduce the notion of \t-collisions" and use it for a technique to reduce the number of steps. In Sections 4 and 5 we consider that single encryptions are much slower than each of the other steps, and we design attacks optimized to save single encryptions (but not the total number of steps). In Section 6 we exploit the complementation property of DES and triple DES to further improve our attacks. Finally, in Section 7 we concentrate on the consequences of our ndings for the security of triple DES. 2 Previous Work Double encryption can be broken with meet-in-the-middle (MITM). This attack requires d2k/se known plaintext/ciphertext pairs on the average, about 2k units of storage, about 2k single encryptions, and about as much steps. For a plaintext p and a corresponding ciphertext c, compute all values IL = E1 L(p) and store all pairs (IL,L) in a table, indexed by IL. Since there are 2k keys L, this requires 2k units of storage, 2k steps and 2k single encryptions. Now, all values I0 M = D2 M(c) are computed. For the correct key pair (L,M) the equation IL = I0 M must hold. Thus the attacker needs to look up I0 M in the previously computed table of pairs (IL,L). Two-key triple encryption can be broken by a chosen plaintext attack using about 2k units of everything: 2k plaintext/ciphertext pairs, 2k units of storage, 2k single encryptions, and 2k steps, see [5]. The best known way to attack general triple encryption is also by MITM [4, Section 7.2.3]. Let a plaintext/ciphertext pair (p,c) be given. Proceed as follows: 1. Compute all values bN = D3 N(c), N 2f0,1gk, and store the pairs (bN,N)in a table, indexed by bN. 2. Compute all values bL,M = E2 M(E1 L(p)) with L,M 2f0,1gk, and look for (bL,M,N) in the previously computed table of pairs (bN,N).1 3. Test all key triples (L,M,N) with bL,M = bN until only one such triple remains. The rst stage requires about 2k steps and single encryptions and as much units of storage. The second requires about 22k steps and single encryptions. The third stage is cheap. Note that we need at least l d3k/se pairs of plaintext and ciphertext for the attack. In the case of triple DES, we need l 3=d356/64e such pairs, about 256 units of storage, about 2112 single encryptions and the same number of steps (mainly table look-ups). (The expected number of steps and single encryptions needed for the MITM attack is 2111. This is the number we use when comparing the MITM attack with our probabilistic attacks.) Advanced MITM techniques for attacking two-key triple encryption have been studied by van Oorschot and Wiener [6]. The same authors also proposed advanced MITM techniques for attacking double encryption [7]. Kelsey, Schneier, and Wagner [2] demonstrated how to attack three-key triple DES using related-key techniques. Let a plaintext p and a corresponding ciphertext c be known to the attacker. Assume the attacker to be able to change the rst subkey from L to L + ∆ (both L and L +∆ unknown to the her, but ∆ known). If the attacker receives the decryption of c under the modied key, then she can nd the subkey L using only 2k steps (and the same number of single encryptions). The second and third subkeys M and N can be found as in the case of double encryption. If the same plaintext is encrypted 228 times using triple DES under 228 dierent keys, an attacker can recover one of the 228 keys using 284 steps (and the same number of single encryptions). This result is due to Biham [1]. DESXis a variant of DES, where encrypting and decrypting requires to compute one single encryption and two XORs of s-bit blocks. Kilian and Rogaway [3] describe the security of DESX in the black-box-only model, concentrating on nding a lower bound for the number of single encryptions every black box attack needs. 3 Howto Save Steps In this section, we describe an \operation optimized" attack to save some steps of computation, compared to MITM. Consider a function f : f0,1g−! f0,1gs.Acollision is a pair x,y of inputs with x= y and f(x)=f(y). The value v 2f0,1gs is associated with a t-collision, if there exists a set S with jSjt inputs and f(x)=v for all 1 When computing the complexity of this stage, the operation of computing a value bL,M = E2 M(E1 L(p)) and looking up the pair (bL,M,N) in a table and the operations to maintain the loop together count as one step. x 2 S. Assuming the function f : f0,1g−! f0,1gs to behave like a random function, and that 1 w 2t inputs are randomly chosen, the expected number of values v 2f0,1gs associated with a t-collision2 is about wt 2−s(t−1). Given plaintext/ciphertext pairs (pi,ci), our attack depends on nding t-collisions for the functions fpi : f0,1gk −! f0,1gs, fpi (L)=E1 L(pi). We consider all keys L 2f0,1gk, hence the number of inputs for the function fpi is w =2k. We write K1(a,i) for the set of all keys which encrypt the plaintext pi to the ciphertext a using E1. Similarly, we write K3(b,i) for all keys which decrypt the ciphertext ci to b, using E3. I.e., K1(a,i)=L2f0,1gk j E1 L(pi)=a K3(b,i)=N 2f0,1gk j E3 L(b)=ci . and If jK1(a,i)jt, the value a is associated with a t-collision. Given a pair (pi,ci), we choose set SA(i) f0,1gs of values associated with t-collisions: SA(i)=a2f0,1gs j there exists a t-collision K1(a,i). . Our attack works like this: i := 1; Repeat: let (pi,ci) 2 (f0,1gs)2 be a known pair of plaintext and ciphertext; initialize the sets K1(,i), K3(,i), and SA(i) to be empty; A. for L 2f0,1gk: a := E1 L(pi); K1(a,i):=K1(a,i)+fLg; if jK1(a,i)jt then SA(i):=SA(i)+fag; (Now SA(i) is the set of all values a associated with a t-collision. ) for N 2f0,1gk: b := D3 N(ci); K3(b,i):=K3(b,i)+fNg; B. for a 2 SA(i): for M 2f0,1gk: b := E2 M(a); for N 2 K3(b,i): for L 2 K1(a,i): tripletest(i,L,M,N); i := i+1; until tripletest accepts. The procedure \tripletest" can be realized like this: tripletest(i,L,M,N)is SI := f1,...,lg−fig; d := 3k −s+δ; repeat: choose j 2 SI at random; 2 Cf. Rivest and Shamir [8], who exploit this for one of their micropayment schemes. To verify this estimation, one can use a well known special case, the \birthday paradox": The expected number of inputs for f until the rst 2-collision occurs is c ∗ 2s/2 with a small constant c. (Actually, c = p π/2 ≈ 1.25, cf. [4, Section 2.1.5]). SI := SI −fjg; c := E3 N(E2 M(E1 L(pj))); d := d−s; until (d 0) or (cj= c); if (cj = c) then accept (L,M,N) as the correct key-triple and stop else reject (L,M,N) and continue. When \tripletest" is called, the equation E3 N(E2 M(E1 L(pi))) = ci holds. In the procedure, we are looking for j= i such that E3 N(E2 M(E1 L(pj)))= cj. If we fail often enough, i.e., 3k−s+δ s times, we accept the key-triple (L,M,N) as correct. The value δ serves as a security parameter, the risk to accept an incorrect key-triple is no more that 2−δ. On the average, a wrong key-triple requires insignicantly more than three single encryptions, i.e., one computation of c := ..., since for j 2f1,...,lg−fig, the equation E3 N(E2 M(E1 L(pj))) = cj holds one out of 2s times. The correct triple is always accepted after 3k−s+δ s rounds. E.g., two rounds are sucient for triple DES (k = 56 and s = 64) if δ = 20. In the sequel, we assume δ to be \large enough" and ignore the risk of accepting an incorrect key-triple. Let t be chosen such that wt 2−s(t−1) 2k. Theorem 1. The expected number of pairs (pi,ci) for the operation optimized attack to succeed is 2k/(wt 2−s(t−1)t) (except for a small factor). Sketch of proof. Every t-collision K1(a,i) 2 SA(i) consists of at least t keys and hence has at least a t2−k chance to contain the correct rst key L. Every index i corresponds to a pair (pi,ci) of plaintext and ciphertext. For every i, we expect to nd about wt 2−s(t−1) values a to be associated with a t-collision K1(a,i). Thus the expected number of (plaintext,ciphertext)-pairs we need to consider in order to nd the correct rst key L is 2k/(wt 2−s(t−1)t). It is easy to verify the following: If (L,M,N) is the correct key triple, K1(a,i) 2 SA(i) and L 2 K1(a,i), then the procedure tripletest(i,L,M,N)is executed in stage B with the index i and the keys (L,M,N) as parameters. ut Theorem 2. With l pairs (pi,ci), the operation optimized attack requires the following resources: { Θ(2k) units of storage space, and { Θ(wt2−s(t−1)2kl+wt2−s(t−1)lt22k−s) steps (and as much single encryptions). Proof. Both stages are to be executed l times. During every iteration of the \Repeat" loop, no results of previous iterations are needed. Hence, the amount of storage for the attack can be estimated by the storage space during one iteration, and the required number of steps is l times the average number of steps during one iteration. Below, we estimate the storage space and the number of steps for one such iteration. Both loops of stage A are iterated 2k times, hence the number of steps is about 22k. When the rst loop is nished, the storage space for the sets K1(a,i) (i.e., 2k units) is no longer needed, and can be reused, with the exception of the sets K1(a,i) 2 SA(i). For the second loop, 2k units of storages space are needed for the sets K3(,i). Since wt 2−s(t−1) 2k, we expect the probability for jSA(i)j > 2k to be negligible, and we approximate the storage space for stage A by 2k. Now, we consider stage B. For every pair (pi,ci) we expect the existence of wt 2−s(t−1) t-collisions; thus the loop \for a 2 SA(i)" is iterated wt 2−s(t−1) times on the average. The loop \for M ..." is iterated 2k times, hence, wt 2−s(t−1) 2k single encryptions b := E2 M(a) are done. So far, we need wt 2−s(t−1) 2k steps. The expected size of a set K3(b,i)is2k−s 1. K1(a,i)isa t-collision, thus it contains about t keys L, and the procedure tripletest is to be called wt 2−s(t−1) 2k 2k−s t times. During each of the iterations of stage A and B and hence during the complete algorithm Θ(2k) units of storage space are needed, and the number of steps is lΘ(2k +wt2−s(t−1) 2k +wt2−s(t−1)2k 2k−st)=Θ(wt2−s(t−1)2k+ wt 2−s(t−1) 2k 2k−s t), similarly to the number of single encryptions. ut The constants hidden by the asymptotics are small. Given l pairs of plaintext and ciphertext, we need about 2k units of storage space|as is the case for the MITMattack. Thenumberofsteps is stepsA+stepso B+stepsi B. Here stepsA 2l2k is the number of steps steps for stage A, stepso B lwt2−s(t−1)2k is the number of steps for the outer loops of stage B (i.e., the number of times the operation b := E2 M(a) is executed), and stepsi B 3lwt2−s(t−1)22k−s is the number of steps for all loops of stage B and for tripletest. For triple DES (k = 56 and s = 64) expected number of t-collisions is about 2kt2−s(t−1).Ift = 8, then 2kt2−s(t−1) =20 = 1, we expect one 8-collision, the attack requires about 256 units of storage space, and for l =2k/(wt2−s(t−1)t)= 253 we need about stepsA 2110 steps (mainly table look-ups and single encryptions) for the attack|instead of 2111 similar steps for MITM. We can improve this by choosing t = 7: The expected number of 7-collisions is 2kt2−s(t−1) =28 = 256. Again, the attack requires about 256 units of storage space. For l =2k/(wt 2−s(t−1)t)=256/(256 8)=245,wegetstepsA 2102, stepsi B 3 2104, and stepso B l wt 2−s(t−1) 2k =(2k/(wt 2−s(t−1)t)) wt 2−s(t−1) 2k =22k/7=2112/7 2109.2, thus we only need slightly more than 2109 steps (and as much single encryptions). From a practical point of view, the operation optimized attack is not very useful for breaking triple DES. It is faster than MITM, but requires much more pairs of known plaintexts/ciphertext (e.g., about 245 if t = 7, compared to 3 for MITM). But from a theoretical point of view, the attack's performance clearly indicates triple DES to be weaker than widely believed.
4. How to Save Single Encryptions
The previous section's technique to reduce the number of steps seems to be at a dead end. So in the next two sections, we concentrate on reducing the number of single encryptions instead the number of steps. This section deals with an \encryption optimized" attack. Instead of l sets SA(i) depending on pi, we choose one xed set SA and no longer exploit the occurances of t-collisions. Let there be l plaintext/ciphertext pairs (p1,c1), ..., (pl,cl) known to the attacker. In the previous section, we computed a set SA(i) f0,1gs for every index i 2f1,...,lg. Now instead, we choose one set SA = SA(1) = =SA(l). The size jSAj of SA is xed and jSAj2s. We assume the a 2 SA to be chosen randomly. (We use the independence of the sets SA and fa 2f0,1gsja = E1 L(pi)g, where L denotes the correct rst key.) Our attack consists of three stages: 1. For a 2 SA: compute the sets S1(a)=(i,L) 2f1,...,lgf0,1gk j E1 L(pi)=a . 2. For b 2f0,1gs and i 2f1,...,lg: compute the sets K3(b,i)=N 2f0,1gk j E3 N(b)=ci . 3. For M 2f0,1gk and a 2 SA: b := E2 M(a); for (i,L) 2 S1(a): for N 2 K3(b,i): tripletest(i,L,M,N). What is the chance to nd the correct key by using the algorithm? Theorem 3. If jSAj2s/l, the encryption optimized attack's probability to nd the correct key-triple is close to 1/2. Sketch of proof. The attack succeeds in nding the correct key triple (L,M,N), if for any i 2f1,...,lg the operation \tripletest(i,L,M,N)" is executed, i.e., if a pair (i,a) exists in f1,...,lgSA with E1 L(pi)=a. The existence of such a pair can be expected if l jSAj2s (due to the birthday paradox). ut One of the resources required to mount the attack is the number l of known plaintext/ciphertext pairs. What about the other resources? Theorem 4. If jSAj2s/l, s k and 22k−s l 22s−2k, the encryption optimized attack requires the following resources: { Exactly l known plaintext/ciphertext pairs, {Θ(l2k)unitsofstoragespace, {Θ(22k)steps, {andΘ(23k−s)singleencryptions. Proof.LetthesetsS1()andK3(,)beinitializedtobeempty.Thersttwo stagescanberealizedlikethis: 1.Fori2f1,...,lgandL2f0,1gk:a:=E1 L(pi); S1(a):=S1(a)+f(i,L)g. (Or:Ifa2SA,thenS1(a):=...) 2.Fori2f1,...,lgandN2f0,1gk:b:=D3 N(ci); K3(b,i):=K3(b,i)+fNg. Eachloopisiteratedl2ktimes,hencetheoverallnumberofelementsinthe setsK3(,)arel2k,theoverallnumberofelementsinthesetsS1()isthe same(butweonlyneedthesetsS1(a)fora2SA),andthenumberofstepsand singleencryptionsforthersttwostagesisΘ(l2k). Stage3requiresmuchlessstoragethanthersttwostages.Itsouterloop \ForM2f0,1gkanda2SA"isiterated2kjSAj2k+s/ltimes.Onthe average,themiddleloop\for(i,L)2S1(a)"isiteratedl2k/2stimes,and theinnerloop\forN2K3(b,i)"isiterated2k−stimes.Since2k−s<1,the outerandthemiddleloopdeterminethenumber(2kjSAj)(l2k/2s)22k ofstepsforstage3.Butforthesingleencryptions,wecounthowoftenthe operation\b:=E2 M(a)"isexecutedintheouterloop(i.e.,2kjSAj2k+s/l)and addthreetimesthenumbertheoperation\c:=E3 N(E2 M(E1 L(pj)))"isexecuted withintheproceduretripletest(i.e.,3(2kjSAj)(l2k/2s)(2k−s)323k−s). Ifl22s−2k,asrequired,thetripletestpartdominatesthesum,i.e.,the numberofsingleencryptionsinstage3isabout323k−s=Θ(23k−s). Thusthestoragerequirementfortheattackisdominatedbystage2,the numberofstepsandthenumberofsingleencryptionsaredominatedbystage 3.HenceweneedΘ(l2k)unitsofstoragespace,Θ(22k)stepsandespecially Θ(23k−s)singleencryptions.ut Asonecaneasilydeducefromtheproof,theconstantshiddenbytheasymptoticsaresmall.Weneedaboutl2kunitsofstorage,about22ksteps,andabout 323k−s+2k+s/lsingleencryptions.FortripleDES,wemaychooselwithinthe range216l248.Given,say,l=216knownpairsofplaintextandciphertext, weneedroughly272unitsofstorage(mainlyfortheelementsofthesetsK3(,)), cyclethroughaloopforabout2112times,andhavetoencrypt/decryptabout 323k−s+2k+s/l+l2k+1 32104+2104+273 2106 times. Unliketheoperationoptimizedattack,inwhichwedecreasedthenumberof steps,thissection'sencryptionoptimizedattackreducesthenumberofsingle encryptionsbutnotthenumberofsteps.Thisoptimizationreducesthetimeof theattackassingleencryptionsareconsiderablyslowerthanotheroperations.
5. How to Save more Single Encryptions
The encryption optimized attack's eciency is limited, since tripletest is executed 23k−s times, which induces 3 23k−s single encryptions. As we argued in the sketch of proof of theorem 3, the correct key triple (L,M,N) is found \if a pair (i,a) exists in f1,...,lgSA with E1 L(pi)=a." In this section, we modify the attack; we only execute tripletest if there exist two pairs (i, a), (j, a0) 2f1,...,lgSA with E1 L(pi)=a and E1 L(pj)=a0. This idea leads to the \advanced attack". (More generally, we execute tripletest if r pairs (i1,a1),...,(ir,ar) with E1 L(pj)=aj exist in f1,...,lgSA. In this paper, we concentrate on r 2f1,2g.) On one hand, this forces us to increase the number of known plaintext/ciphertext pairs (p,c) in order to succeed. On the other hand, we need to execute the tripletest much less frequently. The rst two stages are the same as before, for stage 3 we do the following: 3. For M 2f0,1gk: S := fg; for a 2 SA: b := E2 M(a); for (i,L) 2 S1(a): for N 2 K3(b,i): if (L,N) 2 S then tripletest(i,L,M,N) else S := S +f(L,N)g. Theorem 5. If jSAj2 2s/l, the advanced attack's probability to nd the correct key-triple is close to 1/2. Sketch of proof. Let (L,M,N) denote the correct key triple. We consider the iteration of the loop \For M 2f0,1gk:" with M = M, all other iterations cannot succeed anyway. If jSAj2 2s/l, the expected number r of pairs (i1,a1),...,(ir,ar) 2f1,...,lgSA with E1 L(pj)=aj is r = 2. If there actually exist two such pairs (i1,a1) and (i2,a2)inf1,...,lgSA, then the following inclusions hold (i1,L) 2 S1(a1),N 2 K3(E2 M(a1),i1), (i2,L) 2 S1(a2), and N 2 K3(E2 M(a1),i2). In this case, the key pair (L,N) is found twice within the execution of the algorithm. At rst \(L,N) 2 S" is wrong and (L,N) is inserted into the set S. The second time \(L,N) 2 S" is true, tripletest(i,L,M,N) is executed (with i 2fi1,i2g) and accepts because (L,M,N)=(L,M,N) is the correct key triple. ut Theorem 6. If jSAj2s+1/l, the advanced attack requires the following resources: { Exactly l known plaintext/ciphertext pairs, { Θ(l2k) units of storage space, { Θ(22k) steps, { and Θ(l2k +2k+s/l) single encryptions. Proof. The resource requirements for the rst two stages of the advanced attack are the same as for the encryption optimized attack. In the third stage, and for xed M and a, the loop \for (i,L) 2 S1(a)" is iterated about l 2k−s times, the inner loop \for (L,N) 2 S" is iterated about 2k−s times. Hence the size of the set S is roughly jSjl 22k−2s l. The sets K3(,) require l 2k = Θ(l 2k) units of storage and thus dominate the advanced attack's storage requirements. Similarly to the proof of theorem 4, the number of steps is (2k jSAj)(l 2k/2s) 22k+1 = Θ(22k). The rst two stages together require l2k+1 single encryptions. The operation c := E3 N(...) in the procedure tripletest is to be executed about 23k−2s+1 times, inducing 3 23k−2s+1 single encryptions. The operation b := E2 M(a)is to be executed 2k jSAj2k+s+1/l times. Since l 2k+1 number of single encryptions is about l 2k+1 +323k−2s+1 +2k+s+1/l l 3 23k−2s+1, the 2k+1 +2k+s+1/l, i.e., Θ(l 2k +2k+s/l). ut In practice, we need about l 2k units of storage, about 22k+1 steps, and about 2k+s+1/l + l 2k+1 encryptions/decryptions. If we x l =2s/2, we need about 2k+(s/2)+2 single encryptions. (1) For attacking triple DES, given l =232 known pairs of plaintext and ciphertext, we need 288 units of storage space and 2113 steps, but only 290 single encryptions. In comparison to the operation optimized attack, the advanced attack allows us to drastically reduce the amount of single encryptions at the cost of doubling the number of steps. So what is our gain? As we mentioned in the introduction, a single encryption is a very complex operation, compared to, say, table look-ups. If we assume one implementation of DES to require 8 table look-ups per round, i.e., 8 16=27 table look-ups per encryption, our speed-up can be estimated like this: { The expected number of 2111 steps and as much single encryptions of the MITM attack actually correspond to about 1.3 2109 triple encryptions. { The operation optimized attack of section 3 needed 2109 steps and single encryptions. These correspond to about 1.3 2107 triple encryptions. { The encryption optimized attack's 2112 steps (mostly table look-ups) and 2106 single encryptions. This is equivalent to about 2105 triple encryptions. { This section's attack requires 2113 steps (mostly table look-ups) and 290 single encryptions. This corresponds to about 1.3 2104 triple encryptions. Our result 1 for triple encryption (i.e. 290 single encryptions to break triple DES) is very close to Kilian's and Rogaway's lower bound [3] for the number of single encryptions required to break DESX.
6. A Special Variant for Triple DES
So far, we pretended the underlying single block cipher to be ideal, i.e., to behave like a random permutation. But DES is not an ideal block cipher. Most important in this context is the complementation property: If x denotes the complement of the bit-string x, then for every plaintext p 2f0,1gs and every key K 2f0,1gk: DESK(p)= DES K ( p). How does the complementation property aect the eciency of our attacks? First, we note there is not much harm for the attacker. The encryption optimized attack succeeds, if the sets fp1,...,plg and SA are chosen such that there exists a (i,a) 2f1,...,lgSA with E1 L(pi)=a, L the correct rst subkey, cf. proof of theorem 3. This probability is not at all aected by the complementation property E1 L ( pi)= a. We may argue similarly for the advanced attack. The success rate of the operation optimized attack depends on the probability that for a plaintext pi the correct rst subkey L participates in a t-collision K(a,i)=fL,L2,...,Ltg, i.e., E1 L(pi)=E1 L2 (pi)=... = E1 Lt (pi)=a. Again, this probability is not aected by the complementation property E1 L ( pi)= a. Second, there are many ways for the attacker to exploit the complementation property for a small improvement of an attack. For the sake of shortness, we concentrate on one example. Recall the attack in section 3. Let SA be chosen such that for all a 2f0,1gs the equivalence a 2 SA () a 2 SA holds. The attack is unchanged, except for stage B: B. for a 2 SA(i): for M 2f0gf0,1gk−1: b := E2 M(a); for N 2 K3(b,i): for L 2 K1(a,i): tripletest(i,L,M,N); (Next, we exploit b =E2 for N 2 K3( b, i): for L 2 K1( M ( a). ) a, i): tripletest(i,L, M,N); The analysis in section 3 is not much aected. Neither the expected number of pairs of plaintext and ciphertext changes, nor the complexity stepsA of stage A, nor the attack's storage requirements. With respect to stage B, the loop \for a 2 SA(i)" is iterated wt 2−s(t−1) times on the average. The loop \for M ..."isonly iterated 2k−1 times, hence, wt 2−s(t−1) 2k−1 single encryptions b := E2 M(a) are done. So far, we need stepso B = wt 2−s(t−1)2k−1 steps for stage B. Together, the two loops \for N 2..." need as much time as before: stepsi B = wt 2−s(t−1) 2k 2k−s t. If we choose the parameters were t =7,u 2.2, and l =245, the operation optimized attack's complexity is the sum of three numbers stepsA 2102, stepsi B 3 2104, and stepso B 2109.2.
This section's variant does not aect stepsA and stepsi B, hence stepso B 2108.2 approximates the overall number of steps and single encryptions. 7 Comparison and Conclusion Based on today's technology, neither MITM nor any of our attacks constitutes a practical way to break triple DES. If in the future an attack like MITM will be considered practical for doing this, certainly some of the required resources will be more valuable than others. This paper provides a variety of options how to possibly save such a bottleneck resource.
No comments:
Post a Comment