P ( u ) = 0.14, P(b) = 0.06, P(c) = 0.8, 8 = bbabbcab,
(c)
P(u) = 0.7, P(b) = 0.05, P(c)= 0.25, E = C C C U C ˜ ˜ C ,
(d)
P(a) = 0.1, P(b) = 0.7, P(c) = 0.2, 8 = abbbbab.
(e)
7.3 For the cipher and sources of Problem 7.2, compute the entropy and
unicity distance.
7.4 Given the ciphertext find the a posteriori probabilities of keys and
corresponding messages if it is known that the cipher of Example 7.3
was used and the messages are generated by the Markov source de
scribed in Example 7.5:
(a) 2 = bcacbcacc,
(b) E = caaabaaba,
(c) B = aacabcaac,
(d) E =˜CUUU˜CUU,
(e) 8 = aaacaaaca.
Chapter 8
Modern Secret Key Ciphers
Introduction
8.1
In this chapter, we shall consider computationally secure secretkey ciphers
which can theoretically be broken but this will require a huge amount of
computations, e.g. lozo years for a supercomputer. The main advantage of
these ciphers is their fast operation. Actually, they encrypt and decrypt
data essentially faster than publickey and theoretically secure ciphers. In
the subsequent sections we shall describe the most popular ciphers and the
modes of operation, but before that, to explain the principles of construc
tion of such ciphers we continue the example with the Caesar cipher from
Chap. 1.
In Chap. 1 we have considered the ciphertextonly attack on the Caesar
cipher. It was shown that in case of redundant messages, this cipher can
be easily broken by the exhaustive key search. Let™s look for the means of
increasing the security of the Caesar cipher. May be, the first thing that
comes to mind is to increase the number of possible keys. In this case, Eve
will spend more time while searching for a correct key.
The natural way to increase the number of possible keys for the Caesar
cipher is to use different keys for different symbols of the message. For
instance, we may encrypt every odd letter with the key kl and every even
letter with the key kz. Then the secret key k = (kl,kz) will consist of two
integers and the number of possible keys will be 26™ = 676. Let™s encrypt
the same message as in Chapter 1 with the key k = (3,5):
SEQUENCE %VJTZHSFJ . (8.1)
This scheme can easily be extended to an arbitrary secret key length
137
Basics of Contemporary Cryptography f o r IT Practitioners
138
k = ( k l ,k z , . . ,k t ) z 6 . With t about 10 or more the exhaustive key search
becomes infeasible.
Nevertheless, this cipher is easily disclosed by the socalled frequency
analysis. This analysis is based on statistics of the language in which the
message is written. The key search begins with the keys corresponding to
the most frequent letters of combinations. For instance, it is known that
in a typical text in English, the letter E occurs more frequently than the
other letters. Look at VJTZHSFJ in (8.1) and determine what letters are
more frequent at odd and even positions. At even positions, this is the
letter J. Make an assumption that it substitutes for the letter E and hence
kz = J  E = 5. At odd positions, all letters are different (just because the
message taken for the example is too small). Try to find Icl, as before, by the
exhaustive search. After several trials we find Icl = 3. So, in this particular
example, to recover the message from the ciphertext we had to check only
4 keys out of 676 (specifically, we have checked (0,5), (1,5), (2,5), (3,5)).
Let™s try to slightly improve the cipher in order t o complicate the fre
quency analysis. We need somehow to intermingle the letters, to make
them affect each other to hide the individual frequencies of occurrence. As
before, we shall use the key k = ( k l ,k z ) and encrypt the message in two
letter blocks mi, mi+l. One of the simplest variants of the cipher may look
like this:
(all operations are modulo 26). Here mi is an odd letter of the message,
mi+l is the even letter, k l , k2 are the key digits, and ci, ci+l the resulting
symbols of ciphertext. For instance, the pair of symbols SE is encrypted
under the key k = (3,5) by the following way:
i.e. SE converts to ZF.
Note that this cipher is decipherable. The decryption algorithm usually
Modern Secret Key Caphers 139
called the inverse cipher is written a follows:
s
 k2
= ci+l
&+I
=ciIC1,
?iii
(8.3)
mi+1 = % i + 1  ?hi,
mi (mod 26).
mi =  mi+l

Applying the cipher (8.2) to our message under the key (3,5) we obtain
3ZFNJUJJP .
SEQUENCE WAKEREGK
Here, for clearness, after the first arrow, the intermediate result is shown
obtained after the first two operations in (8.2) (this is an “intermingled” but
not yet encrypted text). We can see that this cipher hides the frequencies of
letters which complicates the frequency analysis. Of course, the frequencies
of the pairs (digrams) are preserved but we can conceal they too if encrypt
in blocks of 3 letters etc.
So, we have considered two ways of improving the cipher: increasing the
length of the key and combining symbols into blocks with mixing transfor
mations. Both methods are widely used in real modern ciphers. Now we
shall consider one more trick which is also used in practice. For the sake of
simplicity, we proceed with the same example.
The cipher (8.2) is more complicated t o Eve compared to the cipher (8.1)
and gives us the opportunity to consider another scenario of attack. Up to
this point we considered the ciphertextonly attacks. But what will happen
if Eve has somehow procured the plaintext corresponding to a ciphertext
transmitted earlier? Here we have a situation of the knownplaintext at
tack (see Chap. 1, p. 5 . For instance, Eve has the pair (SEQUENCE,
)
VJTZHSFJ) for the cipher (8.1). Then she immediately computes the se
cret key kl = V  S = 3, k2 = J  E = 5 and is able to decrypt all further
messages from Alice to Bob. When the cipher (8.2) is used, the pair (SE
QUENCE, ZFNJUJJP) does not allow for such obvious solution, although
all is simple too. Eve performs the first two operations from (8.2), which do
not require the secret key, to the word SEQUENCE, obtains the interme
diate word WAKEREGK and using the pair (WAKEREGK, ZFNJUJJP),
as in the previous case, finds the key k = 3,s.
How one can hamper the Eve™s actions? The idea is simple. In encryp
tion, we shall use the cipher (8.2) twice. So we obtain:
SEQUENCE 3ZFNJUJJP %HOZKGRBS . (8.4)
Basics of Contemporary Cryptography f o r I T Practitioners
140
Now having the pair (SEQUENCE, HOZKGRBS) Eve cannot derive the
key, at least, her algorithm is not obvious (she cannot obtain the interme
diate word ZFNJUJJP since it was constructed with the use of secret key
unknown to her).
In the scheme (8.4), the single realisation of the algorithm (8.2) is called
the round of cipher.
We have illustrated the relation between the security of cipher and such
parameters as the length of key, the blocklength, the number of rounds.
We have also showed the necessity of “intermingling” transformations. The
real ciphers employ the same techniques though enhanced to withstand the
advanced methods of cryptanalysis, such as differential and linear crypt
analysis (the reader may consult [Schneier (2000)l as a guide to modern
cryptanalytic methods).
Block Ciphers
8.2
The block cipher can be defined as a transformation of a word (or a block) X
of length n bits dependent on the key K . We shall denote the transformed
word by Y . For all ciphers considered in this section, the length of word Y
is equal to the length of word X .
In other words, the block cipher is an invertible function E (i.e. a func
tion for which an inverse function exists). The specific look EK of this
function is determined by the key K ,
y =EK(X),
x x.
= E K ˜ ( Y )for all
Here EE1 denotes the deciphering transformation and is often called the
inverse cipher.
For cryptographic applications, a block cipher must meet a number of
requirements depending on the situation in which it is used. In most cases
it is enough to claim that the cipher be secure with respect to the chosen
plaintext attack. It automatically assumes its security with respect to the
knownplaintext and ciphertextonly attacks. One should notice that in the
chosenplaintext attack, the cipher can always be broken by the exhaustive
key search. Therefore the requirement for the cipher to be secure may be
reformulated as follows.
The cipher is secure (under the chosenplaintext attack) if there exist
no algorithms for breaking it essentially more efficient than the exhaustive
Modern Secret Key Ciphers 141
key search.
We shall content ourselves with this loose definition of security. In fact,
the compliance to this definition is not proved for any cipher which is in
use today. To be more realistic we should mention the following.
The cipher is believed to be secure (under the chosenplaintext attack)
if there are no algorithms known for breaking it essentially faster than the
exhaustive key search.
In the rest of the section we consider some popular modern block ci
phers. Our task is not just to give the description of the algorithms as
it may be found in the literature but also to explain the basic principles
of construction of the block ciphers. Besides, our discussion will be help
ful for better understanding of the matters set forth in official documents
(standards). Then we shall study the techniques of using block ciphers for
solving various cryptographic problems.
Until recently, no book on cryptography could do without description of
the cipher DES (Data Encryption Standard). This cipher was adopted as a
standard of USA in 1977. Its main parameters are: block size 64 bits, key
length 56 bits, 16 rounds. This cipher was intensively used for more than
20 years and even today can be met in many working systems. Despite
numerous attacks on DES it has not be broken. However, the high level
of computer performance today enables one to break DES by exhaustive
key search. For instance, in 1993 a technical description was published of
the system which costed 1 million dollars and allowed to disclose the DES
key for 7 hours. As a result, DES is not recommended to use in newly
created cryptosystems. So we do not describe DES. In 2001, after a special
competition, a new block cipher standard was adopted in USA, called AES
(Advanced Encryption Standard), which is based on the Rijndael block
cipher developed by Belgian specialists Vincent Rijmen and Joan Daemen.
The majority of modern block ciphers are constructed by the schemes
significantly different from DES. Nevertheless, there is (at least) one active
cipher built on the same principles as DES. This is the Russian standard
block cipher, GOST 2814789. Due to its extremely simple design and by
historical reasons it will be convenient to begin with.
The GOST 2814789 Block Cipher
8.2.1
The cipher GOST 2814789, as follows from its designation, was adopted
as a standard in 1989 in the USSR and is now used as a standard in Russia
(the word GOST is an acronym to Governmental STandard). The main
142 Basics of Contemporary Cryptography for IT Practitioners
parameters of GOST 2814789 are: key length 256 bits, block size 64 bits,
number of rounds 32. GOST 2814789 is more convenient for program
implementation than DES, there are notices about the gain in 1.5 times.
Unlike DES, GOST 2814789 was seemingly not a subject of as thorough
analysis by the world “open” cryptographic community. Nevertheless, as
the specialists conclude, the conservative design and the size of main param
eters (the key length, the blocklength, and the number of rounds) allow to
believe that the cipher cannot be weak (see [Schneier (1996)l). No effective
attacks against GOST 2814789 have been published.
GOST 2814789, as well as DES, is based on the socalled Feistel struc
ture [Feistel (1973)]. The block is split into two equal parts, the right R
and the left L. The right half is combined with the key element and by a
certain algorithm encrypts the left half. Before the next round the parts
are replaced with each other. Such a structure allows one t o use the same
algorithm for decryption as for encryption. It is of special importance in
case of hardware implementation because the direct and the inverse ciphers
are produced by one and the same device (only the order of feeding key
elements differs).
Proceed to the description of GOST 2814789. Introduce necessary
notation and definitions. The sequence of 32 bits is called a word. The
plaintext block X (64 bits), as well as the ciphertext block Y ,consists of
two words, the left L and the right R, L being the highorder word and
R loworder. The secret key K (256 bits) is considered to consist of 8
words K = KoK1. . . K7. It provides the basis for construction of the so
called round key W = WOW1 . . . W3, that contains 32 words (the method
of constructing the round key will be given further on).
There are 8 tables needed for the cipher operation So, S1, . . . , S, (also
called Sboxes). Each table contains 16 4bit elements, numbered from 0 to
15. Denote by Si[j]the j t h element of the ith table. The standard recom