<<

. 2
( 6 .)



>>

2
σ, 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

<<

. 2
( 6 .)



>>