puter Science, vol. 740, ed. E.F. Brickell. Springer- ple for secret-key ciphers today.

Verlag, Berlin, 89“105. A block cipher with n-bit blocks and a κ-bit key is

[8] Okamoto, Tatsuaki and Kazuo Ohta (1989). “Di- a selection of 2κ permutations (bijective mappings)

vertible zero-knowledge interactive proofs and com-

of n bits. For any given key k, the block cipher

mutative random self-reducibility.” Advances in

speci¬es an encryption algorithm for computing

Cryptology”EUROCRYPT™89, Lecture Notes in

the n-bit ciphertext for a given n-bit plaintext, to-

Computer Science, vol. 434, eds. J.-J. Quisquater

gether with a decryption algorithm for computing

and J. Vandewalle. Springer-Verlag, Berlin, 134“

the n-bit plaintext corresponding to a given n-bit

149.

ciphertext.

The number of permutations of n-bit blocks

is n

√ 2 !, which using Stirlings approximationn is

√

BLOCK CIPHERS n n

n

2π 2n ( 2e )2 <

2π2n ( 2e )2 for large n. Since

n

2(n’1)2 for n ≥ 3, with κ = (n ’ 1)2n one could

INTRODUCTION: In his milestone paper in 1949 cover all n-bit permutations, but typically κ is cho-

[43] Shannon de¬nes perfect secrecy for secret-key sen much smaller for practical reasons. For ex-

systems and shows that they exist. A secret-key ci- ample, for the AES (see Rijndael/AES and [38])

one option is the parameters κ = n = 128 in which

pher obtains perfect secrecy if for all plaintexts x

and all ciphertexts y it holds that Pr(x) = Pr(x|y) case (n ’ 1)2n 2135 .

(see Information Theory and [43]). In other words, Most block ciphers are so-called iterated ciphers

a ciphertext y gives no information about the where the output is computed by applying in an

plaintext. This de¬nition leads to the following iterative fashion a ¬xed key-dependent function r

result. times to the input. We say that such a cipher is

an r -round iterated (block) cipher. A key-schedule

algorithm takes as input the user-selected κ-bit

COROLLARY 1. A cipher with perfect secrecy is

unconditionally secure against a ciphertext-only key and produces a set of subkeys.

attack. Let g be a function which is invertible when the

¬rst of its two arguments is ¬xed. De¬ne the se-

As noted by Shannon the Vernam cipher, also quence zi recursively by

called the one-time pad, obtains perfect secrecy.

zi = g(ki , zi’1 ), (1)

In the one-time pad the plaintext characters are

added with independent key characters to pro- where z0 is the plaintext, ki is the ith subkey, and

duce the ciphertexts. However, the practical appli- zr is the ciphertext. The function g is called the

cations of perfect secret-key ciphers are limited, round function.

since it requires as many digits of secret key as

k1 k2 kr

there are digits to be enciphered. A more desir- “ “ “

z0 ’ g ’ z1 ’ g ’ z2 · · · ’ zr ’1 ’ g ’ zr

able situation would be if the same key could be

used to encrypt texts of many more bits.

Two generally accepted design principles for In many block ciphers g consists of a layer of sub-

practical ciphers are the principles of confusion stitution boxes, or S-boxes, and a layer of bit per-

and diffusion that were suggested by Shannon. mutations. Such ciphers are called SP-networks

Confusion: “the ciphertext statistics should de- (see substitution-permutation (SP) network).

pend on the plaintext statistics in a manner too A special kind of iterated ciphers are the Feistel

complicated to be exploited by the cryptanalyst.” ciphers [10], which are de¬ned as follows. Let n

42 Block ciphers

Known plaintext attack. A obtains x1 , x2 , . . . , xs

(even) be the block size and assume the cipher

and y1 , y2 , . . . , ys , a set of s plaintexts and the

L R

runs in r rounds. Let z0 and z0 be the left and

right halves of the plaintext, respectively, each of corresponding ciphertexts.

n/2 bits. The round function g operates as follows: Chosen plaintext attack. A chooses a priori a set

of s plaintexts x1 , x2 , . . . , xs and obtains in some

ziL = zi’1

R

way the corresponding ciphertexts y1 , y2 , . . . , ys .

ziR = f(ki , zi’1 ) + zi’1 ,

R L

Adaptively chosen plaintext attack. Achooses a set

of plaintexts x1 , x2 , . . . , xs interactively as he ob-

R

and the ciphertext is the concatenation of zr and

tains the corresponding ciphertexts y1, y2, . . . , ys .

L

zr . Here f can be any function taking as arguments

Chosen ciphertext attacks. These are similar to

an n/2-bit text and a round key ki and producing

those of chosen plaintext attack and adaptively

n/2 bits. ˜+™ is a commutative group operation on

chosen plaintext attack, where the roles of plain-

the set of n/2-bit blocks. If not speci¬ed otherwise,

texts and ciphertexts are interchanged.

it will be assumed that ˜+™ is bitwise addition mod-

Also, one can consider any combination of the

ulo 2 (or in other terms, the exclusive-or operation

above attacks. The chosen text attacks are obvi-

denoted by •). Also, variants where the texts are

ously the most powerful attacks. In many appli-

split into two parts not of equal lengths and vari-

cations they are however also unrealistic attacks.

ants where the texts are split into more than two

If the plaintext space contains redundancy (see

parts have been suggested.

Information Theory),1 it may be hard for an at-

Two of the most important block ciphers are the

tacker to ˜trick™ a legitimate sender into encrypt-

Feistel cipher Data Encryption Standard (DES)

ing nonmeaningful plaintexts and similarly hard

[35] and the SP-network Advanced Encryption

to get ciphertexts decrypted, which do not yield

Standard (Rijndael/AES) [37].

meaningful plaintexts. But if a system is secure

In the following ek (·) and dk (·) denote, respec-

against an adaptively chosen plaintext/ciphertext

tively the encryption operation and the decryption

attack, then it is also secure against all other

operation of a block cipher of block length n using

attacks. An ideal situation for a designer would

the κ-bit key k.

be to prove that his system is secure against an

We shall now describe Shannon™s model which is

adaptively chosen text attack, although an at-

standard in secret-key cryptology. The sender and

tacker may never be able to mount more than a

the receiver share a common key k, which has been

ciphertext-only attack.

transmitted over a secure channel. The sender en-

The unicity distance of a block cipher is the

crypts a plaintext x using the secret key k and

smallest integer s such that essentially only one

sends the ciphertext y over an insecure channel

value of the secret key k could have encrypted a

to the receiver, who restores y into x using k. The

random selection of s plaintext blocks to the corre-

attacker has access to the insecure channel and

sponding ciphertext blocks. The unicity distance

can intercept the ciphertexts (cryptograms) sent

depends on both the key size and on the redun-

from the sender to the receiver. To avoid an at-

dancy in the plaintext space. However, the unic-

tacker to speculate in how the legitimate parties

ity distance gives no indication of the computa-

have constructed their common key, the following

tional dif¬culty in breaking a cipher, it is merely

assumption is often made.

a lower bound on the amount of ciphertext blocks

needed in a ciphertext-only attack to be able to (at

ASSUMPTION 1. All keys are equally likely and a

least in theory) identify a unique key. Let κ and n

key k is always chosen uniformly at random.

be the number of bits in the secret key respectively

Also it is often assumed that all details about the in the plaintexts and ciphertexts and assume that

cryptographic algorithm used by the sender and the keys are always chosen uniformly at random.

receiver are known to the attacker, except for the In a ciphertext-only attack the unicity distance

value of the secret key. Assumption 2 is known as is de¬ned as nu = κ/(nr L), where r L is the redun-

Kerckhoffs™s assumption (see [17] or maxims). dancy of the plaintexts, see e.g., [44]. The concept

can be adapted also to the known or chosen plain-

ASSUMPTION 2. The enemy cryptanalyst knows all

text scenarios. In these cases the redundancy of

details of the enciphering process and deciphering

the plaintexts from the attacker™s point of view is

process except for the value of the secret key.

100%. The unicity distance in a known or chosen

plaintext attack is nv = κ/n .

The possible attacks against a block cipher are

classi¬ed as follows, where A is the attacker.

Ciphertext-only attack. A intercepts a set of ci- 1 Redundancy is an effect of the fact that certain sequences of

phertexts. plaintext characters appear more frequently than others.

Block ciphers 43

The results of the cryptanalytic effort of the at- Subsequently, imagine that an attacker has in-

tercepted the ciphertext y = ek (x0 ). Let w0 = y and

tacker A can be grouped as follows [21].

Total break. A ¬nds the secret key k. check if w0 is a second component in T. If, say,

w0 = zt , the attacker can ¬nd a candidate for the

Global deduction. A ¬nds an algorithm F, func-

tionally equivalent to ek (·) (or dk (·)) without key k by computing forward from z0 . If this does

not lead to success, compute wi = f(wi’1 ) and re-

knowing the key k.

peat the above test for wi for i = 1, 2, . . . , t.

Local deduction. A ¬nds the plaintext (ciphertext)

of an intercepted ciphertext (plaintext), which A close analysis [14] shows that if m and t are

chosen such that mt 2 ≈ 2κ , there is a probability of

he did not obtain from the legitimate sender.

about mt/2κ that in the above computations of {zi } k

Distinguishing algorithm. A is given access to a

black-box containing either the block cipher for the secret key has been used. If this is the case, the

a randomly chosen key or a randomly chosen attack will ¬nd the secret key. If it is not the case,

permutation. He is able to distinguish between the attack fails. The probability of success can be

increased by repeating the attack, e.g., with 2κ/3

these two cases.

iterations each time with m = t = 2κ/3 one obtains

Clearly, this classi¬cation is hierarchical, that

is, if a total break is possible, then a global deduc- a probability of success of more than 1/2.

In summary, with κ = n the attack ¬nds the se-

tion is possible and so on.

cret key with good probability after 22κ/3 encryp-

tions using 22κ/3 words of memory. The 22κ/3 words

CRYPTANALYSIS: We begin by listing some at-

of memory are computed in a preprocessing phase,

tacks which apply to all block ciphers.

which takes the time of about 2κ encryptions.

Exhaustive key search: this attack requires the

To estimate the complexity of a cryptanalytic at-

computation of about 2κ encryptions and re-

tack, one must consider at least the time it takes,

quires nu ciphertexts (ciphertext-only attack) or

the amount of data that is needed, and the storage

nv plaintext/ciphertext pairs (known and chosen

requirements. For an n-bit block cipher the follow-

plaintext attack), where nu and nv are the unic-

ing complexities should be considered.

ity distances, cf. above.

Data complexity: the amount of data needed as in-

Table attack: encrypt in a precomputation phase a

put to an attack. Units are measured in blocks

¬xed plaintext x under all possible keys, sort,

of length n.

and store all ciphertexts. Thereafter, a total

Processing complexity: the time needed to perform

break is possible requiring one chosen plaintext.

an attack. Time units are measured as the num-

Dictionary attack: intercept and store all possible

ber of encryptions an attacker has to do himself.

plaintext/ciphertext pairs. The running time of

Storage complexity: the words of memory needed

a deduction is the time of one table look-up.

to do the attack. Units are measured in blocks

Matching ciphertext attack: this attack applies to

of length n.

encryption using the (ecb), (cbc), and (cfb) modes

The complexity of an attack is often taken as the

of operation, see modes of operation for a block

maximum of the three complexities above; how-

cipher or [40]. Collect s ciphertext blocks and

ever, in most scenarios the amount of data en-

check for collisions. For example, if yi , y j are n-

crypted with the same secret key is often limited

bit blocks encrypted (using the same key) in the

and for most attackers the available storage is

(cbc) mode, then if yi = y j, then ek (xi • yi’1 ) =

small.

ek (x j • y j’1 ) ’ yi’1 • y j’1 = xi • x j, thus infor-

mation about the plaintexts is leaked. With s ≈

Iterated Attacks

2n/2 the probability of ¬nding matching cipher-

texts is about 1/2, see birthday paradox.

Let x and y denote the plaintext and the cipher-

Time-memory trade-off attack [14]: let us assume

text, respectively. In most modern attacks on iter-

for the sake of exposition that the key space

ated ciphers, the attacker repeats his attack for all

of the attacked cipher equals the ciphertext

possible values of (a subset of) the bits in the last-

space, that is, κ = n. Fix some plaintext block

round key. The idea is that when he guesses the

x0 . De¬ne the function f(z) = ez (x0 ). Select m

correct values of the key bits, he can compute the

randomly chosen values z0 , . . . , zm’1 . For each

value of some bits of the ciphertexts before the last

j j

j ∈ {0, . . . , m} compute the values zi = f(zi’1 ) for

round, whereas when he guesses wrongly, these

j

i = 1, . . . , t, where z j = z0 ; store the pairs (start bits will correspond to ciphertext bits encrypted

j j

and end results) (z0 , zt ) for j = 0, . . . , m in a ta- with a wrong key. If one can distinguish between

ble T and sort the elements on the second com- these two cases, one might be able to extract bits of

ponents. the last-round key. The wrong key randomization

44 Block ciphers