Fauzan Mirza

fauzan@dcs.rhbnc.ac.uk

Department of Mathematics

Royal Holloway University of London

Abstract

This report gives a basic introduction to block cipher design and analysis. The concepts and

design principles of block ciphers are explained, particularly the class of block ciphers known as

Feistel ciphers. Some modern block cipher cryptanalysis methods are demonstrated by applying

them to variants of a weak Feistel cipher called Simpli¬ed TEA (STEA), which is based on the Tiny

Encryption Algorithm (TEA).

1 Introduction

This report gives a basic introduction to block cipher design and analysis (intended to be understand-

able by anyone with some knowledge of discrete mathematics). We will examine the concept of block

ciphers, how they obtain their security, and the principles involved in their design. A popular class

of block ciphers, known as Feistel ciphers, will be described in detail. This report also describes and

demonstrates some modern block cipher cryptanalysis methods by showing how they may be ap-

plied to variants of a specially-designed weak block cipher, which is loosely modelled on the Tiny

Encryption Algorithm (TEA). The weaker variants of TEA are called Simpli¬ed TEA (STEA).

Section 2 is a basic introduction to block cipher design, summarising the types of attacks that a

strong cipher should be able to resist, describing the concepts of confusion and diffusion, and ex-

plaining the principle of Feistel ciphers. In section 3, the TEA block cipher is described and its only

known weakness is explained. In section 4, the STEA block cipher is introduced. Various methods

of attacking STEA, including a very ef¬cient known-plaintext attack and some general block cipher

cryptanalysis methods are described in sections 5“10. Finally, acknowledgements are in section 11.

Preliminaries

This report assumes the following notation for some binary operations.

Exclusive-OR The operation of addition of n-tuples over the ¬eld F2 (also known as exclusive-or) is

denoted by x • y.

y (where x, y ∈ Z2n ).

Integer Addition The operation of integer addition modulo 2n is denoted by x

The value of n should be clear from the context.

Integer Subtraction The operation of integer subtraction modulo 2n is denoted by x y (where x, y ∈

Z2n ). The value of n should be clear from the context. Also, note that x y ≡ x ’y.

Bitwise Shifts The logical left shift of x by y bits is denoted by x < y. The logical right shift of x by y

<

bits is denoted by x > y.

>

1

Bitwise Rotations A left rotation of x by y bits is denoted by x < y. A right rotation of x by y bits is

<<

denoted by x > y.

>>

Hexadecimal numbers will be subscripted with ˜H™, e.g., 20H = 32. The set of plaintext blocks is

denoted by P, the set of ciphertext blocks by C and the set of keys by K. The message block length is

m, where |P| = |C| = 2m , and the key length is k, where |K| = 2k .

2 Block Cipher Design

A symmetric-key block cipher E is a function

E : P — K ’ C. (1)

Moreover, for every key K ∈ K, we have functions

EK : P ’ C,

DK : C ’ P,

and D = E ’1 . In other words, the key determines the bijective mapping of plaintext to ciphertext; it

also determines the inverse mapping of ciphertext to plaintext. If the key is ¬xed, and hence deter-

mines a speci¬c mapping, the block cipher can be considered simply as a large lookup-table (substi-

tution cipher). In particular, identical plaintext blocks encrypt to identical ciphertext blocks.

Substitution ciphers in which m is small (e.g., m = 8, implying 256 distinct message blocks) are

insecure since if the attacker has knowledge of the statistical patterns in the plaintext, then they can

attempt to recover the plaintext from the ciphertext by frequency analysis. Another problem is that

if an attacker correctly guesses the plaintext that corresponds to some ciphertext then they can build

a lookup-table of plaintext-ciphertext pairs corresponding to a particular key, known as a codebook.

Codebooks can be used to decrypt ciphertext blocks without knowledge of the key.

Both problems are solved by increasing the block length, and thus increasing the number of pos-

sible messages. An attacker cannot exploit knowledge of plaintext patterns which are shorter than

the block length. It also becomes impractical for an attacker to build plaintext-ciphertext codebooks.

Typically the message block length m would be at least 64 bits.

We also require it to be infeasible for an attacker, with a known plaintext (P, C), to recover the

key by exhaustive key-search (brute-force). That is, we do not want anyone to be able to determine

the key by trying values of K ∈ K until they ¬nd the key K such that C = E(P, K). By making the

key length suf¬ciently large we can make brute-force attacks computationally infeasible (the cipher

would then be computationally secure). The key length k should be at least 64 bits1

Having decided on the message block length and key length parameters, the designer must then

develop the block cipher in such a way that it should be able to defeat or resist the following types of

attacks, where an attacker would like to recover the key:

Ciphertext-only The attacker has knowledge of some ciphertext but not the plaintext nor the key. In

this case, recovering the plaintext (without the key) may be a successful attack.

Known-plaintext The attacker has knowledge of some ciphertext and corresponding plaintext, en-

crypted under the unknown key

Chosen-plaintext The attacker has an opportunity to have any messages of their choosing to be en-

crypted under the unknown key.

1 The Data Encryption Standard (DES) block cipher has a key length of 56 bits and was broken by brute-force in June 1997.

2

Adaptive chosen-plaintext The attacker has the unlimited capability to have messages of their choos-

ing to be encrypted under the unknown key. We expect that an adaptive chosen plaintext attack

would require less encryptions than a real chosen plaintext attack.

The designer follows Kerckhoff ™s assumption; that the attacker has full knowledge of the workings of

the cipher system. The security of the cipher should rest entirely in the key.

2.1 Confusion And Diffusion

Except for small message block or key lengths, it is infeasible for the block cipher designer to explic-

itly specify a plaintext to ciphertext mapping for every possible key; this would be like specifying 2k

codebooks. It is far more practical to specify the block cipher as an equation or an algorithm. So for

example, a simple block cipher with parameters (m, k) = (64, 64) might be speci¬ed by

= P • K,

C

(2)

= C • K.

P

The problem with the block cipher of equation 2 is that it is trivially broken with one known plaintext

by

= P • C.

K

This block cipher is weak because it is purely linear and thus easily solvable. By using both linear and

nonlinear operations we make the block cipher somewhat more dif¬cult to manipulate by simple

algebra. So for example, a slightly better idea would be the (m, k) = (64, 128) block cipher,

= (P • K0 ) K1 ,

C

(3)

= (C K1 ) • K0 ,

P

where K0 and K1 are subkeys, i.e., key-dependent variables. In this case, each subkey is half of the key

K, and thus has length 64 bits.

To recover the key K an attacker would have to solve equation 3. As there are two unknowns,

a unique solution would not be found with only one known plaintext. However, with two known

plaintexts, (P, C) and (P , C ), we have equations

= (P • K0 )

C K1 ,

= (P • K0 )

C K1 .

The attacker could subtract (modulo 232 ) one ciphertext from another, obtaining

= (P • K0 ) (P • K0 ), (4)

C C

where the 64-bit subkey K1 term has been eliminated. However, equation 4 cannot be manipulated

further to an equation of the remaining subkey K0 in terms of the plaintext and ciphertext blocks

because the operations • and do not follow the distributive law. Furthermore, there is no simple

algebraic relationship between addition modulo 2m and exclusive-or of m-bit vectors since the groups

(Z2m , ) and (Fm , •) are not isomorphic [8].

2

The idea of mixing linear and nonlinear operations in order to obscure the relationship between

the plaintext, ciphertext and key, is called confusion and is an important principle of cipher design [1,

8].

An equally important principle of block cipher design is that of diffusion, i.e., the idea that every

bit of the ciphertext should depend on every bit of the plaintext and every bit of the key [1, 8]. This

3

ensures that the statistics of the plaintext are dissipated within the ciphertext so that an attacker can-

not predict the plaintext that corresponds to a particular ciphertext, even after observing a number

of “similar” plaintexts and their corresponding ciphertexts.

A simple method of achieving confusion and diffusion in a block cipher is by repeatedly apply-

ing keyed substitutions and permutations to the message. The substitutions are used to introduce

nonlinearity into the message (confusion) and the permutations are required to ensure that bits are

affected by different substitutions on subsequent iterations (diffusion). A block cipher based on this

principle is called an iterated cipher.

In practice, the designer develops a function ρ, known as the round function, which has inputs of a

message block X and a subkey K, and outputs a partially-encrypted message block Y = ρ(X, K). The

round function is responsible for satisfying the basic confusion and diffusion requirements, hence we

would want each bit of X and each bit of K to in¬‚uence each bit of Y in a nonlinear but invertible

manner. For example, the round function de¬ned by

def

(5)

ρ(X, K) = (X K) < 3

<<

ful¬ls the confusion requirement by mixing the nonlinear integer addition with the linear bitwise per-

mutation, and the diffusion requirement by the bitwise permuatation. Note that this round function,

by itself, is unsuitable as a block cipher because it is easily solvable2 .

By iterating the round function a ¬xed number of times we automatically obtain some security as

a consequence of the fact that, after each iteration (or round), the output bits become more and more

dependent on the input bits. We can use different subkeys in each iteration so that, for a 4-round

block cipher, the encryption function becomes

C = E(P, K) = ρ(ρ(ρ(ρ(P, K1 ), K2 ), K3 ), K4 ).

Similarly, decryption would be acheived by

P = D(C, K) = ρ’1 (ρ’1 (ρ’1 (ρ’1 (C, K4 ), K3 ), K2 ), K1 ).

The subkeys would be derived from the key by the key schedule algorithm (which would also need

to be designed carefully). Determining the number of rounds required for a suitable level of crypto-

graphic security is not trivial. It depends on the design and security provided by the round function.

Whilst choosing a large number of rounds may defeat most modern cryptanalytic attacks, it may also

make the cipher undesirably slow for many practical purposes. Block cipher designers tend to ¬x

the number of rounds after investigating the susceptibility of the cipher to various general attacks. A

“conservative” number of rounds is usually chosen, which is a few rounds more than the minimum

number of rounds required (i.e., the number of rounds which would cause the cipher to fall to some

type of attack).

The need for a separate decryption function can be avoided by designing the round function to be

an involution (i.e., ρ’1 = ρ). To decrypt, the encryption function would be applied to the ciphertext

but with the subkeys inverted (with respect to whatever operation is used to combine them with the

data) and the order of the subkeys reversed. Effectively,

’1 ’1 ’1 ’1

P = D(C, K) = ρ(ρ(ρ(ρ(C, K4 ), K3 ), K2 ), K1 ).

This may involve some additional work in computing the decryption subkeys from the encryption

subkeys (as in the case of the IDEA cipher [8, 9]), but this would be handled by the key schedule

def

of equation 5 is given by ρ’1 (Y, K) = (Y > 3)

2 The inverse >> K.

4

algorithm and would be transparent to the encryption function. A cipher which has this property is

called E/D similar [8].

One problem caused by this cipher structure is that it allows for the possibility of a one-round

encryption of the message followed by its one-round decryption simply by choosing bad subkeys.

In particular, a round may cancel the effect of its previous round if its subkey is the inverse of the

’1

previous round subkey (i.e., if Ki = Ki’1 for round i). If this occurs then two rounds are wasted (they

would have no effect on the message block) and so this weakness may lower the overall security of

the block cipher. There are two ways of correcting this design. First, by designing a key schedule

that guarantees that any round subkey is never the inverse of its previous round subkey. Second,

by composing the round function of involutions (to maintain E/D similarity), but ensuring that the

round function itself is not an involution. The second option is usually preferable over the ¬rst (the

cipher should be reasonably strong, independent of the key schedule).

E/D similar ciphers are “symmetrical” in their design and we can use a more convienient notation

to illustrate this point by giving the function ρ an index denoting the subkey which is used in that

particular round. For example,

C = E(P, K) = ρ1 (ρ2 (ρ3 (ρ4 (P )))),

P = D(C, K) = ρ4 (ρ3 (ρ2 (ρ1 (C)))).

If the round function is not an involution then the ¬nal round would be followed by an output trans-

formation whose purpose is to cause the cipher to be symmetrical (and hence E/D similar).

A number of modern block ciphers use the same “general” round function as the DES cipher,

because it has the useful property that the encryption function is E/D similar. These are known as

Feistel ciphers.

2.2 Feistel Ciphers

The basic principle of Feistel ciphers is that the plaintext block is split into two halves and each half

is used to encrypt the other half over a predetermined number of rounds. The result is the ciphertext

block composed of the two encrypted half-blocks.

The round function consists of an involutary substitution and an involutary permutation operat-

ing on two blocks, each of length m . The substitution part of the round function, which we denote by