. 3
( 6 .)


caused by the fact that each round of a Feistel cipher only encrypts half a message block. If the subkey
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
(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 )),
= L3 • (R3 L0 (R0 • K1 )).

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 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
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.

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
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

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],
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
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,
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.

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:

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

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

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
holds with probability less than 1 .
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

(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,

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
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 ,
= Li’1 • Ri’1 Yi • Ri’1 Yi Zi • Zi ,
for 1 ¤ r ¤ 4. The plaintext P = (L0 , R0 ) and ciphertext C = (R4 , L4 ). This can be attacked by a


. 3
( 6 .)