σ, is de¬ned by

σi (L, R) = (L • F (R, Ki ), R),

where F is the cipher function and Ki is a subkey. We can show that σ is an involution by showing that

σ2 (L, R) = (L, R), as follows:

σi (L, R) = σi (L • F (R, Ki ), R)

2

= (L • F (R, Ki ) • F (R, Ki ), R)

= (L, R).

This also shows that the cipher function does not need to be invertible. The permutation part of the

round function, which we denote by π, is de¬ned by

π(L, R) = (R, L),

which is a simple “swapping” of halves. This is obviously an involution. Our goal is to make an E/D

similar cipher by alternately applying the substitution σ and permutation π. As both σ and π are

5

involutions, this is easily acheived by ensuring that the cipher ends with the same function that is ap-

plied ¬rst (hence making the cipher appear “symmetrical”). The round function of a Feistel cipher is

ρ(L, R) = π(σ(L, R)). This is not an involution, but the cipher is E/D similar if the round substitution

σ is the ¬rst and last stage of the cipher:

= σn (ρn’1 (· · · (ρ1 (P )) · · ·)),

C = E(P, K)

= σ1 (ρ2 (· · · (ρn (C)) · · ·)).

P = D(C, K)

In practice, the round function ρ is applied n times and then the output transformation π is applied to

undo the π permutation in the n-th round (so the last effective operation on the message block would

be the substitution part σn , as required).

Another point that we have to address is how the decryption subkeys are derived from the encryp-

tion subkeys. It was mentioned that the decryption subkeys would be the inverse of the operation

which is used to combine them with the data. In the function σ, the key-dependent output of the

cipher function is combined with the message block using the exclusive-or operation. Hence the

decryption subkeys are the same as the encryption subkeys, since the inverse of any element, with

respect to •, is itself.

The only difference between encryption and decryption is the order in which the subkeys are ap-

plied, hence this construction is E/D similar.

More speci¬cally, the plaintext is divided into two blocks, P = (L0 , R0 ). Then, for an n-round

cipher, the following round function is iterated (for 1 ¤ i ¤ n):

Li = Ri’1 ,

(6)

= Li’1 • F (Ri’1 , Ki ),

Ri

where F is the cipher function and the Ki are subkeys. The ciphertext is C = (Rn , Ln ). Note that the

order of the message halves is reversed in the output; this is due to the output transformation (which

undoes the swap of the n-th round).

In general we can use any group operation — in place of • in equation 6 so that the round function

could be

Li = Ri’1 ,

= Li’1 — F (Ri’1 , Ki ).

Ri

The round function required for decryption would be

Li = Ri’1 ,

= Li’1 — (F (Ri’1 , Ki ))’1 ,

Ri

where it would be necessary to compute the inverse (with respect to the operation —) of the cipher

function output. Consequently, the decryption round may not be the same as the encryption round,

in which case the cipher will no longer be E/D similar. Examples of ciphers which use this modi¬ed

Feistel structure are the TEA and STEA block ciphers, which use integer addition modulo 232 (the op-

eration ) instead of exclusive-or, and consequently both TEA and STEA require separate decryption

functions.

The only parts of the block cipher which are not speci¬ed by the Feistel structure are the design of

the cipher function and the key schedule algorithm which determines how the subkeys (K1 , . . . , Kn )

are derived from the key K.

6

3 The TEA Block Cipher

The TEA (Tiny Encryption Algorithm) block cipher was presented at the Fast Software Encryption

workshop in 1994 [15]. It is a 64-round Feistel cipher operating on 64-bit message blocks with a 128-

bit key. It was designed for software implementation and all its operations are on 32-bit words and use

arithmetic and logic operations rather than using (traditional) substitution and permutation tables in

the cipher function.

As mentioned previously, the round function differs slightly from the usual speci¬cation in that

integer addition modulo 232 is used instead of exclusive-or as the combining operator:

Li = Ri’1 ,

(7)

Ri = Li’1 F (Ri’1 , Ki ),

There is no ¬nal unswap, but this is not a problem since the decryption function is separate and deals

with this. The plaintext is P = (L0 , R0 ) and the ciphertext is C = (L64 , R64 ). Each subkey Ki is an

ordered 3-tuple of elements in Z232 , of the form (T, U, V ) where (T, U ) are 64 bits of the secret key and

V is a known 32-bit constant. The cipher function F is de¬ned by

def

T ) • ((M > 5) U ) • (M (8)

F (M, (T, U, V )) = ((M < 4)

< > V ).

To generate the subkeys, ¬rst the 128-bit key K is split into four 32-bit blocks K = (W, X, Y, Z) then

the subkeys Ki are determined by

i+1

δi =δ ,

2

if i is odd

W, X, δi

(for 1 ¤ i ¤ 64).

Ki =

if i is even

Y, Z, δi

For any key K the subkeys Ki are all distinct due to alternate subkeys having different multiples of δ

by the key schedule. The key schedule constant δ = 9E3779B9H is derived from the golden number

but its precise value has no cryptographic signi¬cance; its main purpose is to ensure that the subkeys

are distinct [15].

The round function of TEA is considerably more complicated than the simple block ciphers in the

previous sections of this report, which might raise the following questions:

1. Why are as many as 64 rounds used?

2. Why is the key schedule constant δ required?

3. Why is the message block shifted in the cipher function?

4. Are there any weaknesses in this system?

The last question can be answered immediately, but the answers to the ¬rst three questions should

become apparent in the later sections when we analyse the STEA cipher.

3.1 Equivalent Keys

For any cipher system, a key K is equivalent to key K if and only if

(9)

EK (P ) = EK (P ).

As this is an equivalence relation, we can de¬ne equivalence classes in K and say that a pair of keys K

and K belong to the same equivalence class if equation 9 holds. For a well-designed cipher we would

7

not want equivalent keys to exist (each key K ∈ K should specify a distinct mapping of plaintext to

ciphertext) and so we would expect 2k equivalence classes by equation 9.

Thus, for the TEA cipher we would expect 2128 equivalence classes. In actual fact, however, TEA has

2126 equivalence classes (there are 2126 distinct mappings of plaintext to ciphertext). This weakness

manifests itself in the cipher function (generally the most sensitive part of a Feistel cipher). Note that

for all values of X, Y ∈ Z232 ,

231 231 = 0,

= X • 80000000H .

231

X

Hence,

≡ (X • 80000000H ) (Y • 80000000H ).

X Y

The cipher function (equation 8) can be be manipulated in a similar fashion to prove that

F (M, (T, U, V )) ≡ F (M, (T • 80000000H , U • 80000000H , V )).

This means that every 128-bit key K = (W, X, Y, Z) has three equivalent keys of the form:

(W • 80000000H , X • 80000000H , Y, Z),

(W, X, Y • 80000000H , Z • 80000000H ),

(W • 80000000H , X • 80000000H , Y • 80000000H , Z • 80000000H ).

For example, encrypting plaintext P = (00000000 00000000H ) with any of the following keys produces

the ciphertext C = (9327C497 31B08BBEH ):

00000000 80000000 00000000 00000000H ,

80000000 00000000 00000000 00000000H ,

80000000 00000000 80000000 80000000H ,

00000000 80000000 80000000 80000000H .

This weakness means that although TEA uses a 128-bit key, it provides at best the same security as

a 126-bit key. In an exhaustive key-search, an attacker would only have to test a quarter of the total

number of possible keys (because there is no need to try keys that are equivalent to those that have

already been tested).

In spite of the equivalent keys, the reduction in the complexity of exhaustive key-search does not

pose a threat to the security of TEA (although it does highlight a design ¬‚aw), since it is still compu-

tationally secure. However, the existence of equivalent keys means that TEA is unsuitable for use in a

hash function that is based on block ciphers, such as those suggested in [8].

To eliminate the equivalent keys it would be necessary to redesign the TEA key schedule, which is

precisely what the designers of TEA did [13]. Their improvements also defeat a “related-key” attack

on TEA that requires 223 chosen plaintexts encrypted under two related keys (the value of the second

key depends on the value of the ¬rst key) [6].

4 The STEA Block Cipher

The STEA block cipher is a 64-round Feistel cipher operating on 64-bit message blocks with a 64-bit

key. It was designed purely as a test block cipher for learning about modern cryptanalytic techniques

and a number of variations exist for the same purpose (but designed to illustrate different attacks).

8

The STEA block cipher uses the round function as in equation 7 and the cipher function de¬ned

by

F (M, Ki ) = M • Ki , (10)

where Ki is a 32-bit subkey. Considering the 64-bit key as two 32-bit blocks so that K = (K1 , K2 ), the

subkeys are simply Ki = K1 for i odd and Ki = K2 for i even (where 1 ¤ i ¤ 64). Thus the halves of

the key are applied in alternate rounds.

To encrypt, the plaintext P = (L0 , R0 ) is input to the encryption function, which iterates the round

function

Li = Ri’1 ,

(11)

Ri = Li’1 (Ri’1 • Ki ),

for 1 ¤ i ¤ 64. The output is the ciphertext C = (L64 , R64 ). To decrypt, the ciphertext C = (L0 , R0 ) is

input to the decryption function, which iterates

Ri = Li’1 ,

(Li’1 • Ki ),

Li = Ri’1

for 1 ¤ i ¤ 64. The plaintext is then P = (L64 , R64 ). The subkeys would have to be applied in the

reverse order, as usual, and so Ki = K2 for i odd and Ki = K1 for i even (where 1 ¤ i ¤ 64).

To show the effectiveness of STEA, the following table lists some plaintexts (chosen to have low

Hamming weights and distances from each other) and corresponding ciphertexts:

Key Plaintext Ciphertext

(00000000 00000000H ) (00000000 00000000H ) (00000000 00000000H )

(00000000 00000000H ) (00000000 00000001H ) (61CA20BB 297A859DH )

(00000000 00000000H ) (00000001 00000001H ) (297A859D 8B44A658H )

(00000000 00000000H ) (00000001 00000000H ) (C7B064E2 61CA20BBH )

(00000001 00000003H ) (00000000 00000000H ) (57112EA4 255E6231H )

(00000001 00000003H ) (00000000 00000001H ) (F12AEA7D ED0EC712H )

(00000001 00000003H ) (00000001 00000001H ) (C7B064E3 61CA20BBH )

(00000001 00000003H ) (00000001 00000000H ) (C7B064E2 61CA20BAH )

(55555555 55555555H ) (22222222 22222222H ) (0F3102B4 83B32497H )

The two ciphertext blocks marked by are remarkably similar, differing exactly in the places where

their corresponding plaintexts differ. This indicates a serious problem caused by a lack of diffusion.

There are other noticable patterns in the above table, but from the point of a ciphertext-only attack,

there does not seem to be any resemblence between plaintexts and their corresponding ciphertexts

(except for the case where the plaintext and key are both zero; the reason for this will be explained

later).

STEA does not inherit the equivalent keys problem that TEA suffered from. However, it has a

number of shortcomings of its own due its overly simplistic cipher function and key schedule.

5 Algebraic Solution

As explained in section 2, the round function need not be secure against algebraic solution for the

cipher to be secure, provided that a suf¬cient number of rounds are used.

In 2-round STEA, the plaintext P = (L0 , R0 ) and the ciphertext C = (L2 , R2 ) are related by

(R0 • K1 ),

L2 = L0

(L2 • K2 ).

R2 = R0

9

In each equation there is exactly one unknown term. Thus STEA needs a minimum of three rounds,

otherwise we can recover the 64-bit key with only one known plaintext by

L0 ) • R0 ,

K1 = (L2

R0 ) • L0 .

K2 = (R2

Actually, any Feistel cipher would require a minimum of three rounds, since part of this problem is