<<

. 5
( 11 .)



>>

Cryptology”CRYPTO™92, Lecture Notes in Com- tacks, which is still the best known design princi-
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

<<

. 5
( 11 .)



>>