hypothesis, which is often used, says that when ences of the nonlinear components is nonuniform.

the attacker guesses a wrong value of the key, the A difference between two bit strings, x and x

resulting values are random and uniformly dis- of equal length, is de¬ned in general terms as

x = x — (x )’1 , where — is a group operation on

tributed. If an attacker succeeds in determining

bit strings and where the superscript ’1 denotes

the value of the last-round key, he can peel off one

round of the cipher and do a similar attack on a the inverse element. Consider an iterated cipher,

cf. (1). The pair ( z0 , zs ) is called an s-round

cipher one round shorter to ¬nd the second-last

round key, etc. In some attacks it is advantageous differential [27]. The probability of the differen-

to consider the ¬rst-round key instead of the last- tial is the conditional probability that given an

round key or both at the same time, depending on input difference z0 in the plaintexts, the differ-

the structure of the cipher, the number of key bits ence in the ciphertexts after s rounds is zs . Ex-

involved in each round, etc. periments have shown that the number of chosen

The two most general attacks on iterated ci- plaintexts needed by the differential attack in gen-

phers are linear cryptanalysis and differential eral is approximately 1/ p, where p is the probabil-

cryptanalysis. ity of the differential being used. For iterated ci-

phers, one often speci¬es the expected differences

Linear Cryptanalysis after each round of encryption. Such a structure

over s rounds, i.e., ( z0 , z1 , . . . , zs’1 , zs ), is

called an s-round characteristic. The differential

Linear cryptanalysis [30, 34] is a known plaintext

attack is explained in more details in differential

attack. Consider an iterated cipher, cf. (1). Then a

cryptanalysis.

linear approximation over s rounds (or an s-round

linear hull) is

Extensions, Generalization, and Variations

(zi · ±) • (zi+s · β) = 0, (2)

which holds with a certain probability p, where The differential and linear attacks have spawned

zi , zi+s , ±, β are n-bit strings and where ˜·™ denotes a lot of research in block cipher cryptanalysis and

the dot (or inner) product modulo 2. The strings several extensions, generalizations, and variants

±, β are also called masks. The quantity | p ’ 1/2| of the differential and linear attacks have been

is called the bias of the approximation. The ex- developed. In [15] it was shown how to combine

pression with a ˜1™ on the right side of (2) will have the techniques of differential and linear attacks.

a probability of 1 ’ p, but the biases of the two ex- In particular, an attack on the DES reduced to

pressions are the same. The linear round approx- eight rounds was devised, which on input only 512

imations are usually found by combining several chosen plaintexts ¬nds the secret key. In [47] a

one-round approximations under the assumption generalization of both the differential and linear

that the individual rounds are mutually indepen- attacks, known as statistical cryptanalysis, was in-

dent (for most ciphers this can be achieved by troduced. It was demonstrated that this statisti-

assuming that the round keys are independent). cal attack on the DES includes the linear attack

The complexity of a linear attack is approximately by Matsui but without any signi¬cant improve-

| p ’ 1/2|’2 . It was con¬rmed by computer exper- ment. In [18] an improved linear attack using mul-

iments that the wrong key randomization hy- tiple linear approximations was given. In [24] a

pothesis holds for the linear attack on the DES linear attack is shown using nonlinear approxi-

(see Data Encryption Standard). The attack on mations in the outer rounds of an iterated cipher.

the DES was implemented in 1994, required a In [12, 13] two generalizations of the linear attack

total of 243 known plaintexts [31] and in 2002 were given.

was the fastest, known key-recovery attack on the A dth order differential [26] is the difference be-

tween two (d ’ 1)th order differentials and is a

DES. Linear cryptanalysis for block ciphers gives

collection of 2d texts, where a ¬rst-order differen-

further details of the attack.

tial is what is called a differential above. The main

Differential Cryptanalysis idea in the higher order differential attack is the

fact that a dth order differential of a function of

Differential cryptanalysis [3] is a chosen plaintext maximum algebraic degree d is a constant. Conse-

quently, a (d + 1)th order differential of the func-

attack and was the ¬rst published attack which

could (theoretically) recover DES keys in time less tion is zero. In [16, 22] these attacks were applied

than that of an exhaustive search for the key. In to various ciphers.

a differential attack one exploits that for certain The boomerang attack [50] is a clever applica-

input differences the distribution of output differ- tion of a second-order differential. Boomerangs are

Block ciphers 45

particularly effective when one can ¬nd a good attacks. There are several variants of this attack

differential covering the ¬rst half of the encryp- depending on how powerful the attacker A is as-

tion operation and a good differential covering the sumed to be. One distinguishes between whether

¬rst half of the decryption operation. More details Agets encryptions under one or under several keys

of the attack can be found in boomerang attack. and whether there is a known or chosen relation

Let {±0 , ±1 , . . . , ±s } be an s-round characteristic. between the keys (see related key attack).

Then {±0 , ±1 , . . . , ±s } is called a truncated charac- The slide attack [4] applies to iterated ciphers

teristic, if ±i is a subsequence of ±i . Truncated where the list of round keys has a repeated pat-

characteristics were used to some extent in [3]. tern, e.g., if all round functions are identical, there

Note that a truncated characteristic is a collec- are very ef¬cient attacks.

tion of characteristics and therefore reminiscent

BOUNDS ATTACKS: A motivation for the

of a differential. A truncated characteristic con- OF

tains all characteristics {±0 , ±1 , . . . , ±s } for which Feistel cipher design is the results by Luby and

trunc(±i ) = ±i , where trunc(x) is a truncated value Rackoff (see Luby-Rackoff cipher or [28]). They

of x not further speci¬ed here. The notion of trun- showed how to build a 2n-bit pseudorandom per-

cated characteristics extends in a natural way to mutation from a pseudorandom n-bit function

truncated differentials introduced in [22]. using the Feistel construction. For a three-round

construction they showed that under a chosen

Other Attacks plaintext attack, an attacker needs at least 2n/2

chosen texts to distinguish the Feistel construc-

Integral cryptanalysis [5, 25] can be seen as a tion from a random 2n-bit function. Under a

dual to differential cryptanalysis and it is the best combined chosen plaintext and chosen ciphertext

known attack on the advanced encryption stan- attack, this construction is however easily distin-

dard. The attack is explained in more details in guished from random. For a four-round construc-

multiset attacks. In the interpolation attack [16] tion it was shown that even under this strong at-

tack, an attacker needs at least 2n/2 chosen texts to

one expresses the ciphertext as a polynomial of the

plaintext. If this polynomial has a suf¬ciently low distinguish the construction from a random 2n-bit

degree, an attacker can reconstruct it from known function.

(or chosen) plaintexts and the corresponding ci- In the decorrelation theory [48] one attempts to

phertexts. In this way, he can encrypt any plain- distinguish a given n-bit block cipher from a ran-

text of his choice without knowing the (explicit) domly chosen n-bit permutations. Using particu-

value of the secret key, see interpolation attack for lar well-de¬ned metrics, this approach is used to

more details. There has been a range of other cor- measure the distance between a block cipher and

relation attacks most of which are relative to the randomly chosen permutations. One speaks about

attacked cipher, but which all exploit the nonuni- decorrelation of certain orders depending on the

formity of certain bits of plain- and ciphertexts type of attack one is considering. In [49] it was

[2, 8, 11, 19, 23, 47]. shown how this technique can be used to prove

resistance against elementary versions of differ-

Key Schedule Attacks ential and linear cryptanalysis.

Resistance Against Differential

One talks about weak keys for a block cipher, if

and Linear Attacks

there is a subspace of keys relative to which a cer-

tain attack can be mounted successfully, such that

for all other keys the attack has little or zero prob- First it is noted that one can unify the com-

ability of success. If there are only a small number plexity measures in differential and linear crypt-

of weak keys, they pose no problem for applications analysis. Let pL be the probability of a linear

of encryption if the encryption keys are chosen uni- approximation for an iterated block cipher, then

de¬ne q = (2 pL ’ 1)2 [32]. Let q denote the high-

formly at random. However, when block ciphers

are used in other modes, e.g., for hashing, these est such quantity for a one-round linear approxi-

attacks play an important role as demonstrated mation. Denote by p the highest probability of a

in [6, 42]. one-round differential achievable by the cryptan-

One talks about related keys for a block cipher, alyst. It is possible to lower bound the probabili-

if for two (or more) keys k and k — of a certain ties of all differentials and all hulls in an r -round

relation, there are certain (other) relations be- iterated cipher expressed in terms of p and q

tween the two (or more) encryption functions ek (·) [21, 32, 40, 41]. The probabilities are taken as an

and ek— (·), which can be exploited in cryptanalytic average over all possible keys. It has further been

46 Block ciphers

shown that the round functions in iterated ciphers It was shown [20] that for attacks not exploit-

can be chosen in such a way that the probabili- ing the internal structure, the effective key size is

κ + n ’ log2 m bits, where m is the maximum num-

ties of the differentials and of the linear hulls are

small [39,40]. In this way it is possible to construct ber of plaintext/ciphertext pairs the attacker can

iterated ciphers with a proof of security (as an obtain. (This method applied to the DES is named

average over all possible keys) against differen- DES-X and attributed to Ron Rivest.)

tial and linear cryptanalysis. This approach was

Lars R. Knudsen

used in the design of the block ciphers Misty1 [33]

and Kasumi (see Kasumi/Misty1 or [1]).

References

ENHANCING EXISTING CONSTRUCTIONS [1] (1999). V3.1.1 3GPP TS 35.202. Kasumi. Available

at http://www.3gpp.org

Multiple Encryption [2] Biham, E. and A. Biryukov (1995). “An improve-

ment of Davies™ attack on DES.” Advances in

Cryptology”EUROCRYPT™94, Lecture Notes in

In a double encryption with two keys k1 and k2 ,

the ciphertext corresponding to x is y = ek2 (ek1 (x)). Computer Science, vol. 950, ed. A. De Santis.

Springer-Verlag, Berlin, 461“467.

However, regardless of how k1 , k2 are generated,

[3] Biham, E. and A. Shamir (1993). Differential

there is a meet-in-the-middle attack that breaks

Cryptanalysis of the Data Encryption Standard.

this system with a few known plaintexts using

Springer-Verlag, Berlin.

about 2κ+1 encryptions and 2κ blocks of mem- [4] Biryukov, A. and D. Wagner (1999). “Slide at-

ory, that is, roughly the same time complexity as tacks.” Fast Software Encryption, Sixth Interna-

key search in the original system. Assume some tional Workshop, Rome, Italy, March 1999, Lec-

plaintext x and its corresponding ciphertext y en- ture Notes in Computer Science, vol. 1636, ed. L.R.

crypted as above are given. Compute ek1(x) for all Knudsen. Springer-Verlag, Berlin, 245“259.

choices of the key k1 = i and store the results ti in [5] Daemen, J., L. Knudsen, and V. Rijmen (1997).

“The block cipher square.” Fast Software Encryp-

a table. Next compute dk2(y) for all values of the

key k2 = j and check whether the results s j match tion, Fourth International Workshop, Haifa, Israel,

January 1997, Lecture Notes in Computer Science,

a value in the table, that is, whether for some (i, j),

vol. 1267, ed. E. Biham. Springer-Verlag, Berlin,

ti = s j. Each such match gives a candidate k1 = i

149“165.

and k2 = j for the secret key. The attack is re-

˚

[6] Damgard, I.B. and L.R. Knudsen (1993). “The

peated on additional pairs of plaintext“ciphertext breaking of the AR hash function.” Advances

until only one pair of values for the secret key in Cryptology”EUROCRYPT™93, Lecture Notes

remains suggested. The number of known plain- in Computer Science, vol. 773, ed. T. Helleseth.

texts needed is roughly 2κ ’ n. There are vari- Springer-Verlag, Berlin, 286“292.

ants of this attack with trade-offs between run- ˚

[7] Damgard, I.B. and L.R. Knudsen (1998). “Two-key

ning time and the amount of storage needed [46]. triple encryption.” The Journal of Cryptology, 11

(3), 209“218.

In a triple encryption with three independent keys

k1 , k2 , and k3 , the ciphertext corresponding to x [8] Davies, D. and S. Murphy (1995). “Pairs and triples

of DES S-boxes.” The Journal of Cryptology, 8 (1),

is y = ek3 (ek2 (ek1 (x))). One variant of this idea is

20“27.

well known as two-key triple encryption, proposed

[9] Davies, D.W. and W.L. Price (1989). Security for

in [45], where the ciphertext corresponding to x is

Computer Networks. John Wiley & Sons, New York.

ek1 (dk2 (ek1 (x))). Compatibility with a single encryp- [10] Feistel, H., W.A. Notz, and J.L. Smith (1975). “Some

tion can be obtained by setting k1 = k2 . However, cryptographic techniques for machine-to-machine

whereas triple encryption is provably as secure as data communications.” Proceedings of IEEE, 63

a single encryption, a similar result is not known (11), 1545“1554.

for two-key triple encryption. A two-key triple en- [11] Gilbert, H., H. Handschuh, A. Joux, and

cryption scheme with a proof of security appeared S. Vaudenay (2001). “A statistical attack on

RC6.” Fast Software Encryption, 7th International

in [7].

Workshop, FSE 2000, New York, USA, April 2000,

Lecture Notes in Computer Science, vol. 1978, ed.

Key-Whitening B. Schneier. Springer-Verlag, Berlin, 64“74.

[12] Harpes, C., G.G. Kramer, and J.L. Massey (1995).

Another method of increasing the key size is by “A generalization of linear cryptanalysis and the

key-whitening. One approach is the following: y = applicability of Matsui™s piling-up lemma.” Ad-

ek (x • k1 ) • k2 , where k is a κ-bit key, and k1 and k2 vances in Cryptology”EUROCRYPT™95, Lecture

are n-bit keys. Alternatively, k1 = k2 may be used. Notes in Computer Science, vol. 921, eds. L. Guillou

Block ciphers 47

[26] Lai., X. (1994). “Higher order derivatives and

and J.-J. Quisquater. Springer-Verlag, Berline, 24“

differential cryptanalysis.” Communication and

38.

Cryptography, Two Sides of One Tapestry, ed. R.

[13] Harpes, C. and J.L. Massey (1997). “Partitioning

Blahut. Kluwer Academic Publishers, Dordrecht.

cryptanalysis.” Fast Software Encryption, Fourth

ISBN 0-7923-9469-0.

International Workshop, Haifa, Israel, January

[27] Lai, X., J.L. Massey, and S. Murphy (1992).

1997, Lecture Notes in Computer Science, vol.

“Markov ciphers and differential cryptanalysis.”

1267, ed. E. Biham. Springer-Verlag, Berlin, 13“27.

Advances in Cryptology”EUROCRYPT™91, Lec-

[14] Hellman, M. (1980). “A cryptanalytic time-memory

ture Notes in Computer Science, vol. 547, ed. D.W.

trade-off.” IEEE Trans. on Information Theory, IT-

Davies. Springer-Verlag, Berlin, 17“38.

26 (4), 401“406.

[28] Luby, M. and C. Rackoff (1988). “How to construct

[15] Hellman, M.E. and S.K. Langford (1994).

pseudorandom permutations from pseudorandom

“Differential“linear cryptanalysis.” Advances

functions.” SIAM Journal of Computing, 17 (2),

in Cryptology”CRYPTO™94, Lecture Notes in

373“386.

Computer Science, vol. 839, ed. Y. Desmedt.

[29] Massey, J.L. (1993). “Cryptography: Fundamentals

Springer-Verlag, Berlin, 26“39.

and applications.” Copies of Transparencies, Ad-

[16] Jakobsen, T. and L. Knudsen (1997). “The inter-

vanced Technology Seminars.

polation attack on block ciphers.” Fast Software

[30] Matsui, M. (1993). “Linear cryptanalysis method

Encryption, Fourth International Workshop, Haifa,

for DES cipher.” Advances in Cryptology”

Israel, January 1997, Lecture Notes in Computer

EUROCRYPT™93, Lecture Notes in Computer

Science, vol. 1267, ed. E. Biham. Springer-Verlag,

Science, vol. 765, ed. T. Helleseth. Springer-Verlag,

Berlin, 28“40.

Berlin, 386“397.

[17] Kahn, D. (1967). The Codebreakers. MacMillan,

[31] Matsui, M. (1994). “The ¬rst experimental crypt-

London.

analysis of the Data Encryption Standard.” Ad-

[18] Kaliski, B.S. and M.J.B. Robshaw (1994). “Linear

vances in Cryptology”CRYPTO™94, Lecture Notes

cryptanalysis using multiple approximations.” Ad-

in Computer Science, vol. 839, ed. Y.G. Desmedt.

vances in Cryptology”CRYPTO™94, Lecture Notes

Springer-Verlag, Berlin, 1“11.

in Computer Science, vol. 839, ed. Y. Desmedt.

[32] Matsui, M. (1996). “New structure of block ci-

Springer-Verlag, Berlin, 26“39.

phers with provable security against differential