. 1
( 6 .)



>>

Block Ciphers And Cryptanalysis
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

. 1
( 6 .)



>>