can be recovered from the input and output of the cipher function (as in STEA) then the key can be

recovered with only one known plaintext3 .

6 A Meet-In-The-Middle Attack

If we have a look at 3-round STEA with independent subkeys, i.e., no key schedule (so that the key

length effectively becomes k = 3 — 32 = 96), we ¬nd that the plaintext P = (L0 , R0 ) and ciphertext

C = (L3 , R3 ) are related by

((L0 (R0 • K1 )) • K2 ),

L3 = R0

(12)

(R0 • K1 ) (L3 • K3 ).

R3 = L0

In a known-plaintext attack, equation 12 shares four known terms (each half of the plaintext and ci-

phertext) and three unknown constants (the three subkeys). There is no way to recover any of the sub-

keys simply by manipulating these equations. An exhaustive key-search on this STEA variant would

require at most 296 encryptions and one known plaintext.

A meet-in-the-middle attack ¬nds a useful tradeoff between memory and computation, for an

ef¬cient key-search. Equation 12 can be rearranged to

= (L3 R0 ) • (L0 (R0 • K1 )),

K2

(13)

= L3 • (R3 L0 (R0 • K1 )).

K3

In a known-plaintext attack, equation 13 has subkeys K2 and K3 expressed in terms of four known

terms and one unknown 32-bit constant (the subkey K1 ). With one known plaintext and by trying

all values of K1 ∈ F32 , we can ¬nd corresponding values of K2 and K3 . In effect, we would have

2

32

2 possible values for the 96-bit key. Another known plaintext block is then encrypted with each of

these 232 possible keys; if the output of a trial encryption matches the actual ciphertext then with high

probability we have recovered the key4 . Thus, to recover the 3-round STEA 96-bit key in a meet-in-

the-middle attack requires at most 233 encryptions and two known plaintexts. A meet-in-the-middle

attack on 4-round STEA with independent subkeys (k = 128) requires at most 265 encryptions and

two known plaintexts. With the STEA key schedule (k = 64) the attack on four rounds is less ef¬cient

than exhaustive key-search.

A meet-in-the-middle attack could also be applied to the block cipher of equation 3. Note that

(P • K0 ).

K1 =C

Now we can recover the key using two known plaintexts in the following way. For each known plain-

text pair, try every possible value of K0 ∈ F64 and obtain two possible values of K1 . If the two possible

2

3 The ¬rst published attack on reduced-round DES was an attack on two rounds, based on this method of attacking 2-round

Feistel ciphers [5].

4 The probability that a key might be found which satis¬es equation 13 for the two known plaintexts but is not the correct

key is 2’64 . The correct key can be uniquely identi¬ed by testing against a third known plaintext.

10

values of K1 match then we have found the correct key. This means we have to try at most 265 encryp-

tions to recover the key, compared with 2128 that would be required for an exhaustive key-search.

There are many variations in the implementation of a meet-in-the-middle attack. A naive attempt

to double the effective key-length of a block cipher might be to encrypt the plaintext with key K1 then

decrypt the result with a different key K2 , so that

C = D(E(P, K1 ), K2 ).

An exhaustive key-search would require up to 22k trials for the key (K1 , K2 ) and one known plaintext.

However, a meet-in-the-middle attack on this construction can recover the key much faster. For k ¤

m, the attack can be attempted as follows. Let (P, C) and (P , C ) be two known plaintexts. We use a

lookup-table T and denote the i-th entry in T by T (i). Complete the lookup-table by T (E(P, K1 )) =

K1 , for every key K1 ∈ Fk . Now, for every key K2 , let K1 = T (E(C, K2 )) and compute a trial encryption

2

of P ; if C = D(E(P , K1 ), K2 ) then we have found the correct 2k-bit key (K1 , K2 ). This meet-in-

the-middle attack recovers the key with up to 2k+1 trials, memory for 2k messages, and two known

plaintexts. If k > m then the lookup-table structure needs to be slightly different since each T (i) may

have more than one value.

The meet-in-the-middle attacks are useful only when we can decompose the encryption process

into more than one equation to solve, each equation has different unknown terms, and the total

length of the unknown terms in each equation is less than the key length k.

If more than three rounds are used in a Feistel cipher then the meet-in-the-middle attack becomes

impractical, since the complexity of the attack increases exponentially with the length of each subkey

for each additional round.

7 A Divide-And-Conquer Attack

There is a very effective known-plaintext attack on STEA that can recover the entire 64-bit key with

only 32 encryptions. This attack is based on the divide-and-conquer principle whereby the cipher

structure is divided into parts and the smaller parts are attacked separately. So far we have reviewed

STEA only from a general algebraic point. We will now take a closer look at the confusion and diffusion

process and reveal a major weakness in STEA.

We denote the i-th bit of A by A[i], where the least-signi¬cant bit (LSB) of A is A[0]. The algorithm

for computing S = A B involves the equations

C[0] = 0,

S[i] = A[i] • B[i] • C[i], (14)

C[i + 1] = A[i]B[i] • A[i]C[i] • B[i]C[i].

where S represents the sum and C is the carry. First note that S[0] = A[0] • B[0]; the LSB is linear over

F2 . Secondly, the only nonlinearity from addition is due to the carry, which only propagates upwards

(diffusion in only one direction).

The STEA round function for the least-signi¬cant bit of the message block is linear:

Li [0] = Ri’1 [0]

Ri [0] = Li’1 [0] • Ri’1 [0] • Ki [0],

Thus we can recover two key bits (the least-signi¬cant bits of K1 and K2 ) using known plaintext by

¬nding the linear expressions relating the LSBs of the plaintext, ciphertext and key. Denoting the

11

plaintext P = (L0 , R0 ) and ciphertext C = (L64 , R64 ), we get the following equations after 64 rounds:

K1 [0] = L64 [0] • R64 [0] • L0 [0],

(15)

K2 [0] = L0 [0] • R0 [0] • R64 [0].

The terms on the right-hand side are known, and hence we recover the values of K1 [0] and K2 [0].

Since each message bit is independent of all other message bits, except for the interference of the

nonlinear carry, we can express any key bit in terms of known message bits by

K1 [i] = L64 [i] • R64 [i] • L0 [i] • C1 [i],

K2 [i] = L0 [i] • R0 [i] • R64 [i] • C2 [i],

where i is the bit position, and C1 and C2 are nonlinear functions of the message and key bits, due to

carry.

Now consider the next bit, bit 1, which is affected by the carry from bit 0. If we eliminate the carry

from bit 1 then we are left with the linear part corresponding to equation 15, which can be solved to

recover two more key bits. We continue in this manner until the entire key is recovered. The easiest

way to eliminate the carry is to calculate its value for the appropriate bit and then to exclusive-or it

with the ciphertext bit. To calculate the carry for the i-th bit, encrypt the (i ’ 1) least-signi¬cant bits

of the plaintext, using the known (i ’ 1) key bits. The value of the bit in the i-th position is the carry

(which we exclusive-or against the actual ciphertext bit).

Thus, we can rapidly recover the 64-bit key using only one known plaintext and 32 encryptions. In

general, for message block length m, this attack will recover the m-bit key with only m encryptions,

2

independent of the number of rounds.

This attack cannot be applied to TEA because the shifts in the cipher function provide much better

diffusion. As each round passes, each bit of the message block becomes more dependent on other

message and key bits. Each ciphertext bit of TEA is a complex nonlinear function of a number of

plaintext and key bits; there is no simple way to solve the equations. The lack of diffusion in STEA

meant that a linear relation could be found between message and key bits in the same position; and

this, of course, was its Archilles heel.

8 Linear Cryptanalysis

The linear cryptanalysis method is one of the most recent techniques of analysing block ciphers. It

is a known-plaintext (statistical) attack, developed by Mitsuru Matsui, used to break the DES cipher

using 50 workstations and 243 known plaintexts [10, 11].

Linear cryptanalysis approximates the nonlinear part of a cipher to a linear equation (so that the

linear cipher will give the same results as the nonlinear cipher most of the time, but will also give

some incorrect results). Since the linear approximation only holds probabilistically, we need a lot

of known plaintexts to be able to make use of the approximation, particularly if the probability of

the approximation is extremely close to half (in this case the approximation provides only a slight

advantage over randomly guessing the value of a key bit).

There are two stages to applying linear cryptanalysis to a block cipher: (1) ¬nding suitable linear

approximations of the cipher, and (2) applying the known-plaintext attack algorithm.

An overview of how suitable linear approximations for a Feistel cipher may be found is as follows:

Step 1 Find linear equations which are good approximations to the nonlinear part of the cipher func-

tion. Take note of the probability with which the linear approximation holds.

12

Step 2 Extend the linear approximations to the round function, and thus formulate a linear equation

for each approximation.

Step 3 Construct a linear approximation of the block cipher by compounding linear equations for the

round function, making sure all intermediate unknown message terms are cancelled out. The

probability of this cipher linear approximation can be calculated from the probabilities of the

round approximations.

Step 4 Calculate the number of known plaintexts required for the known plaintext attack. This de-

pends on the probability of the cipher approximation as well as the required degree of success.

To illustrate what is meant by a linear approximation, we will examine the properties of the three-

input nonlinear boolean function F , de¬ned by

= ABC • BC • B • C. (16)

F (A, B, C)

The following table shows the output of F for all possible inputs:

A B C F

0 0 0 0

0 0 1 1

0 1 0 1

0 1 1 1

1 0 0 0

1 0 1 1

1 1 0 1

1 1 1 0

Note that this nonlinear function is biased: the output has more ones than zeros. It is unwise to use

biased functions as the nonlinear component of a block cipher (or indeed any cipher system). The

bias would de¬nitely leak some information about the plaintext and key in the ciphertext; and this

may lead to a chosen- or known-plaintext attack [1].

The Walsh transform is used to measure the linearity of a boolean function. Speci¬cally, for a

nonlinear function F : Fn ’ F2 , calculate

2

(’1)x·± F (x), (17)

SF (±) =

x∈Fn

2

where x · ± denotes the inner-product of vectors x and ±. The vector ± is the n-tuple of input bits

which are being tested for a correlation to the output bit. The result of equation 17 is an integer in the

range ’2n’1 to 2n’1 , and will be even only if the nonlinear function is 0-1 balanced (the output has

the same number of ones and zeros). In particular, the result is less than zero if the correlation holds

with probability greater than 1 , zero if there is no correlation, and greater than zero if the correlation

2

holds with probability less than 1 .

2

When analysing the DES S-boxes, Matsui generalised the Walsh transform to a function NF : Fn ’ 2

F2 , which measures linearity between subsets of the inputs and the outputs of the nonlinear function

m

(the Walsh transform is the case when the nonlinear function has a one-bit output) [10].

If the Walsh transform is computed on equation 16 over all possible values of ±, it shows that there

are seven distinct linear approximations (linear equations whose output correlates to the output of

the nonlinear function), as follows:

Prob=5/8 : C,

13

Prob=5/8 : B,

B • C,

Prob=7/8 :

A • 1,

Prob=5/8 :

A • C,

Prob=5/8 :

A • B,

Prob=5/8 :

A • B • C • 1.

Prob=5/8 :

These can be veri¬ed by comparing their output against the output of the nonlinear equation:

B•C A•1 A•C A•B A•B•C •1

A B C F

0 0 0 0 0 1 0 0 1

0 0 1 1 1 1 1 0 0

0 1 0 1 1 1 0 1 0

0 1 1 1 0 1 1 1 1

1 0 0 0 0 0 1 1 0

1 0 1 1 1 0 0 1 1

1 1 0 1 1 0 1 0 1

1 1 1 0 0 0 0 0 0

3 5 5 8 7 5 5 5 5

Clearly the best approximation to the nonlinear expression ABC •BC •B •C is the linear expression

B • C, which gives matching output for 7 of the 8 possible inputs.

We will now demonstrate linear cryptanalysis of a simple 4-round Feistel cipher according to the

overview given earlier. Let the cipher function be de¬ned by

F (M, (Y, Z)) = M Y • M Y Z • Z,

where Y and Z are halves of the round subkey. Thus the encryption process is

Li = Ri’1 ,

(18)

= Li’1 • Ri’1 Yi • Ri’1 Yi Zi • Zi ,

Ri

for 1 ¤ r ¤ 4. The plaintext P = (L0 , R0 ) and ciphertext C = (R4 , L4 ). This can be attacked by a