“ There are 2 pairs (X, X ) such that ∆X = 10000001 and ∆Y = 11111101.

“ There are 4 pairs (X, X ) such that ∆X = 10000001 and ∆Y = 11111110.

“ There are 2 pairs (X, X ) such that ∆X = 10000001 and ∆Y = 11111111.

(6) “ There are 16 pairs (X, X ) such that ∆X = 00001110 and ∆Y = 00001000.

“ There are 8 pairs (X, X ) such that ∆X = 00001110 and ∆Y = 01001000.

“ There are 16 pairs (X, X ) such that ∆X = 00001110 and ∆Y = 01101000.

“ There are 32 pairs (X, X ) such that ∆X = 00001110 and ∆Y = 01111000.

“ There are 4 pairs (X, X ) such that ∆X = 00001110 and ∆Y = 11001000.

“ There are 2 pairs (X, X ) such that ∆X = 00001110 and ∆Y = 11001001.

“ There are 2 pairs (X, X ) such that ∆X = 00001110 and ∆Y = 11001011.

“ There are 8 pairs (X, X ) such that ∆X = 00001110 and ∆Y = 11101000.

“ There are 4 pairs (X, X ) such that ∆X = 00001110 and ∆Y = 11101001.

“ There are 4 pairs (X, X ) such that ∆X = 00001110 and ∆Y = 11101011.

“ There are 16 pairs (X, X ) such that ∆X = 00001110 and ∆Y = 11111000.

“ There are 8 pairs (X, X ) such that ∆X = 00001110 and ∆Y = 11111001.

“ There are 8 pairs (X, X ) such that ∆X = 00001110 and ∆Y = 11111011.

Thus our 6-round characteristic is

(80H , 02H , 08H , 60H , 81H , 0EH , 78H ),

holding with probability

128 64 56 92 64 32 1

— — — — — ≈ .

128 128 128 128 128 128 51

This would imply that for every 51 random and uniformly distributed pairs of chosen plaintexts with

difference ∆P = 80H we expect about 1 pair of corresponding ciphertexts to have a difference of 78H .

However, it is not quite as simple as this, since the subkeys are ¬xed (not random) and may cause

some difference paths found by the above method to be impossible to follow in practice no matter

how many chosen plaintexts we have.

Also, there may be more than one n-round characteristic with the same plaintext difference and

ciphertext difference. For example, another 6-round characteristic of the above cipher is

(80H , 02H , 18H , A3H , 86H , 0AH , 78H ),

24

which holds with probability ≈ 1561 . There is no way to tell which of these two 6-round characteristics

1

was used to arrive at a ciphertext difference of 78H from a plaintext difference of 80H . As there may be

many ways of arriving at a particular output difference, the probability of obtaining a pair of plain-

texts that cause the output difference of a characteristic may be higher than the probability of the

characteristic. The attacker is not usually concerned with the message differences after each round,

only in the last difference of a characteristic. An i-round differential is a pair (∆X, ∆Y ) specifying the

input difference and output difference after i rounds [8, 9]. The probability of a speci¬c differential is

the sum of probabilities of all characteristics that have the same input and ¬nal output difference as

the differential.

A right pair, with respect to an i-round differential (∆X, ∆Y ), is a pair of plaintexts such that their

difference is equal to ∆X and their difference after i rounds of encryption is equal to ∆Y . A wrong

pair is a pair of plaintexts that is not a right pair.

To execute the differential cryptanalysis chosen-plaintext attack on an n-round block cipher:

1. Find an (n’1)-round differential (∆X, ∆Y ) that holds with high probability (preferably the best

(n ’ 1)-round differential).

2. Choose a random plaintext P and compute P = P • ∆X. Encrypt both plaintexts so that

C = E(P, K) and C = E(P , K), where K is the unknown key.

3. Recover all possible values of the subkey Kn that may cause the one-round outputs of C and C

from inputs with difference ∆Y . A basic method of identifying possible subkeys is to deduce the

subkeys K that can tranform round input Y into output C, for every possible input Y , and then

compare the one-round encryption of (Y • ∆Y ) with each deduced subkey against ciphertext

C . Any subkey K which passes this test is a possible candidate for the actual last subkey, and

we increment a counter corresponding to K by 1.

4. Repeat the test on another chosen plaintext, until one value of the subkey has been counted

signi¬cantly more than the others. This subkey (or small set of subkeys) is assumed to be the

actual subkey used in the n-th round.

If we know some n-round differential that includes the (n’1)-round differential, then we may be able

to discard some pairs of plaintexts on the basis that their ciphertext differences would not follow from

the (n ’ 1)-round difference.

We can apply differential cryptanalysis to an 8-round variant of STEA. The variant applies a bitwise

left rotation to the message block after the addition in the round function. The message block is

rotated by 1 bit on odd rounds, and 9 bits on even rounds, so that the round function is described by

Li = Ri’1 ,

(Ri’1 • Ki )) < Si ,

Ri = (Li’1 <<

where Ki = K1 and Si = 1 for i odd, and Ki = K2 and Si = 9 for i even. The 64-bit plaintext is

(L0 , R0 ) and the 64-bit ciphertext is (L8 , R8 ). The bitwise rotation provides better diffusion in this

STEA variant and would defeat the divide-and-conquer attack (but not linear cryptanalysis). This

STEA has a 6-round characteristic described by

E0000000 C0000000H ,

Prob=0.250 : C0000000 40000000H ,

Prob=0.500 : 40000000 00000000H ,

Prob=0.500 : 00000000 80000000H ,

25

Prob=1.000 : 80000000 00000100H ,

Prob=0.500 : 00000100 00000201H ,

Prob=0.125 : 00000201 00060200H ,

which holds with probability 1/256. We expect about one plaintext pair of 256 pairs to have difference

00000201 00060200H after 6 rounds of encryption. As we are dealing with an 8-round cipher, we can-

not identify right pairs with this characteristic. We could attempt the chosen-plaintext attack if we

knew the ciphertexts after 7 rounds of encryption, and we can recover these by decrypting the cipher-

text by only one round with every possible subkey K8 . Thus, for each ciphertext pair C = (L8 , R8 ) and

C = (L8 , R8 ), we have 232 possible values of (L7 , R7 ) and (L7 , R7 ). We can test whether this is likely

to be a right pair by taking the difference of the left halves of these ciphertexts and comparing against

the expected difference:

L7 • L7 = 00060200H .

If this condition is not satis¬ed, then we discard this pair and try again on another pair of random

chosen plaintexts. Otherwise, we increment a counter for K8 and proceed with the attack assuming

that the pair is a right pair and deducing possible values of K7 (if any) for which

L6 • L6 = 00000201H .

This would require an additional 232 trial decryptions for every pair of ciphertexts that passed the test

from round 7. Thus, the complexity of testing one pair of chosen plaintexts is about 233 and we would

expect to recover the values of the last two round subkeys (and hence the key).

The differential cryptanalysis method was discovered before linear cryptanalysis, so there has

been considerable more research on the security of block ciphers with respect to differential crypt-

analysis. There are a number of improvements and evolutions of the basic idea, such as the concepts

of truncated and higher-order differentials (which have been used to attack the SAFER and reduced-

round IDEA block ciphers) [7].

11 Acknowledgements

Thanks to Sean Murphy, Fred Piper, Peter Wild and Chris Mitchell for their advice and for providing

me with some of the literature references. Thanks also to David Wagner for some interesting discus-

sions.

References

[1] Henry Beker and Fred Piper, Cipher Systems: The Protection of Communications, Northwood

Books, 1982.

[2] Eli Biham and Adi Shamir, Differential Cryptanalysis of the Data Encryption Standard, Springer-

Verlag, 1992.

[3] Roger Fleming, “An attack on a weakened version of TEA”. Posted on sci.crypt, 22 Oct 1996.

[4] Edna K. Grossman and Bryant Tuckerman, “Analysis of a Feistel-like cipher weakened by having

no rotating key”. IBM Research Report RC6375, Yorktown Heights, NY, 1977.

26

[5] M. Hellman, R. Merkle, R. Schroeppel, L. Washington, W. Dif¬e, S. Pohlig, and P Schweitzer, “Re-

.

sults of an initial attempt to cryptanalyze the NBS Data Encryption Standard”. Technical Report

SEL 76-042, Department of Electrical Engineering, Stanford University, 1976.

[6] John Kelsey, Bruce Schneier, and David Wagner, “Related-Key Cryptanalysis of 3-WAY, Biham-

DES, CAST, DES-X, NewDES, RC2, and TEA”. In Information and Communications Security”

Proceedings of ICICS 1997, Lecture Notes in Computer Science 1334, Springer-Verlag, 1997.

[7] Lars R. Knudsen, “Truncated and Higher Order Differentials”. In Fast Software Encryption”

Proceedings of the Second International Workshop, Lecture Notes in Computer Science 1008,

Springer-Verlag, 1994.

[8] Xuejia Lai, On the Design and Security of Block Ciphers, ETH Series in Information Processing 1,

Hartung-Gorre Verlag, 1992.

[9] Xuejia Lai, James L. Massey, and Sean Murphy, “Markov Ciphers and Differential Cryptanalysis”.

In Advances in Cryptology”Proceedings of EUROCRYPT ™92, Lecture Notes in Computer Science

547, Springer-Verlag, 1992.

[10] Mitsuru Matsui, “Linear Cryptanalysis Method for DES Cipher”. In Advances in Cryptology”

Proceedings of EUROCRYPT ™93, Lecture Notes in Computer Science 765, Springer-Verlag, 1993.

[11] Mitsuru Matsui, “The First Experimental Cryptanalysis of the Data Encryption Standard”. In

Advances in Cryptology”Proceedings of CRYPTO ™94, Lecture Notes in Computer Science 839,

Springer-Verlag, 1994.

[12] Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone, Handbook of Applied Cryptogra-

phy, CRC Press, 1997.

[13] Roger M. Needham and David J. Wheeler, “Tea extensions”. October 1997.

[14] Rainer A. Rueppel, Analysis and Design of Stream Ciphers, Springer-Verlag, 1986.

[15] David J. Wheeler and Roger M. Needham, “TEA, a Tiny Encryption Algorithm”. In Fast Software

Encryption”Proceedings of the Second International Workshop, Lecture Notes in Computer Sci-

ence 1008, Springer-Verlag, 1994.

27