<<

. 6
( 11 .)



>>



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

<<

. 6
( 11 .)



>>