ñòð. 30 |

Secret key K of c words.

INPUT:

+

OUTPUT: Round key W of 4(r 1) words.

W +- K ( c words);

1.

+

+

FOR i = C, c 1,. . . , 4 ( ˜ 1) - 1 DO

2.

3. t t wi-1;

IF i mod c = 0 THEN

4.

t c SubWord(RotWord(t)) @ Rcon[i div c];

5.

ELSE IF c = 8 AND i mod c = 4 THEN

6.

7. t t SubWord(t);

8. wi +- W i - C @ t;

RETURN ˜ 0 * * * ˜ 4 ( ˜ + 1 ) - 1 .

9.

In this algorithm, SubWord(t) is a function applying the S-box of the

cipher to each byte of the word t

[to,tirt2,t3] [s[ti],s[tz],s[t3],s[to]].

-+

The transformation RotWord(t) is performed by the cyclic shift of word t

Basics of Contemporary Cryptography for IT Practitioners

158

left one byte

[to,ti,t2,t3] [ti,t2,t3,t01.

+

The array of round constants Rcon contains the words

Rcon[i] = [yi,O,O, 01

where

modm(z).

y. - &-l

The chosen method for round key schedule must facilitate solving the

following problems:

(1) to impede the attack to the cipher if the secret key is partially known

or related keys (connected by the common rules of construction) are

used;

(2) to eliminate any symmetries within the cipher round and between the

rounds (the array of round constants Rcon is used for that purpose).

As we have noted when considering the inverse cipher, to produce

the round key for decryption one have to apply the transformation

MixColumns-' to the blocks of W from the first t o the next-to-last.

Main Modes of Operation of Block Ciphers

8.3

The block ciphers are used for solving many problems in cryptography. In

this section, we shall consider the main modes of their usage.

In the previous section, the examples of real block ciphers were given.

Now we can think of an (idealised) block cipher as a transformation of input

block X into output block Y depending on secret key K ,

the following requirements being fulfilled:

(1) given a known Y , but unknown K , it is practically impossible to recover

x;

(2) given arbitrary known X and Y , but unknown K , it is practically

impossible to learn K .

First we consider the classical problem of encrypting messages by the

use of block ciphers.

Modern Secret Key Ciphers 159

ECB Mode

8.3.1

The acronym ECB comes from Electronic Code Book. In this mode, the

message X is split into the blocks X = X I ,X 2 , . . . ,Xt. Each block is

encrypted by the block cipher

15 i 5 t .

r, = E K ( X i ) ,

We obtain the ciphertext Y = Y,,Y2,. . . ,Yt. Decryption is carried out by

the scheme

It is easy to see that one can perform decryption by selecting the ci-

phertext blocks in arbitrary order. This mode is convenient in many cases

because it is easy to change or delete some fragments of data independently

of the others and to decrypt starting at any point. This is particularly im-

portant for database applications.

However, there may be problems in some situations because the similar

records will have the similar ciphertexts. We can say that the ECB mode

preserves the data pattern. It may provide some information to the ad-

versary. For instance, if the number of difeerent records in a database is

small then the adversary can make a dictionary of ciphertexts and break

the database using the frequency analysis. Note that she will not need to

break the cipher.

CBC Mode

8.3.2

The acronym CBC comes from Cipher-Block Chaining. In this mode, the

ciphertext is produced by the following rule:

r, = E K ( X i @ r , - 1 ) , 15 i 5 t ,

i.e. each successive plaintext block is covered by the previous ciphertext

block prior to encryption. The word Y (often called the initialisation

o

vector) must be specified in advance and known to both encrypter and

decrypter. The resulting ciphertext can be decrypted by the following way:

x = y,-l@ E F y q ,

i 1 5 i _< t .

With the CBC mode, we obtain the ciphertext in which each successive

block depends on all of the previous. This mode destroys any data patterns.

I T Practitioners

Basics of Contemporary Cryptography

160 fOT

Even if all plaintext blocks are identical, the ciphertext will consist of dif-

ferent blocks. The CBC mode is preferable when encrypting the messages

whose length exceeds the blocksize. The drawback, however, is the absence

of direct access capability: the message can be decrypted only sequentially,

starting at the first block.

Two other block cipher modes will be considered in the context of the

stream ciphers.

8.4 Stream Ciphers

In Sec. 7.3, we have considered the Vernam cipher and established its perfect

secrecy, i.e. such property that the adversary intercepting the ciphertext

obtains no information about the message. In the Vernam cipher, the

ciphertext y 1 ,y2, . . . ,Y k is produced from the message x1,x2, . . . ,Zk under

the key 21,z2,. . . ,Zk by the following encrypting operation:

, i = 1,2, . . . ,k . (8.10)

yi = xi CB˜i

This cipher is perfect only if the key z l , z 2 , . . . ,Z k consists of equiproba-

ble and independent bits and is used only once. This leads to the need of

generating random sequences of very large size and transmitting them over

secure channels which is highly difficult. Therefore, the idea arose to use

instead of truly random sequences the sequences generated by the so-called

pseudo-random number generators. In this case, one may use the initial

state of the generator as the secret key. Of course, the resulting cryptosys-

tem will not be perfect anymore. The maximum of what we may expect is

that breaking such cryptosystem will require an enormous amount of time

(e.g. it will require the exhaustive search through all possible initial states

of the generator). As the compensation for the lost of perfection we obtain

the possibility to use short secret keys (say, several hundred bytes) which

are significantly easier to maintain and distribute (e.g. they may be created

by means of public-key techniques).

The cipher based upon (8.10) where the key sequence z1, z 2 , . . . , zk is

generated by some deterministic algorithm (e.g. pseudo-random number

generator) is called the stream cipher. As a rule, the source message and

the key sequence are independent streams of bits. Since the encrypting

and decrypting transformations are the same for all stream ciphers, the

latter differ only in the way of construction of pseudo-random number gen-

erators. Indeed, to recover the message x1,x2,. . . , Xk from the ciphertext

161

M o d e r n Secret K e y C i p h e r s

,

y 1 , yz, . . . y k produced by (8.10) one needs to generate the same sequence

z ˜ , z z , . ,Zk

.. as in encryption, and use the formula

i = 1 , 2 ,..., k . (8.11)

Zi=yz@Zi,

Example 8.1 One of the simplest pseudo-random number generators

called the linear congruential generator operates according to the recur-

rence

+ b) mod c (8.12)

= (aui

uitl

where a, b, c are some constants and ui, u + the elements of the produced

il

pseudo-random sequence. The initial state is u g . Take, for instance, a = 5,

b = 12, c = 23, and let u = 4. Compute several elements of the sequence:

o

+ 12) mod 23 = 9,

(4.5

u=

1

+

212 = ( 9 . 5 12) mod 23 = 1 1 ,

+

u g = (11 a 5 12) mod 23 = 2 1 ,

+ 12) mod 23 = 2 ,

u4 = (21 . 5

+ 12) mod 23 = 2 2 ,

u5 = ( 2 . 5

+ 12) mod 23 = 7 ,

' 1 = (22 5

16

+ 12) mod 23

u =(7.5 = 1.

7

The produced sequence look much like random (it can be converted to

a bitstream by using binary representations of numbers, or by extracting

particular bits, etc.).

For the use in cryptographic applications, the generator must meet the

following main requirements:

(1) the period of the generated sequence must be large;

(2) the determination of zi+l given the preceding elements of the sequence

must be a hard, infeasible problem;

(3) the sequence generated must be indistinguishable from a truly random

sequence by statistical tests.

The above considered linear congruential generator is completely un-

suitable for cryptographic purposes since the algorithms are known that

allow to recover all the generator's parameters by examining only a few

elements of the sequence generated [Plumstead (1982)].

As the examples of cryptographically secure pseudo-random number

generators, we shall consider the OFB and CTR block cipher modes and

the algorithm RC4.

Basics of Contemporary Cryptography f o r IT Practitioners

162

But first, letâ€™s pay attention to one peculiarity which is important for all

stream ciphers. For encrypting any other message, one must use different

key K and/or initialisation vector Yo. Otherwise, several messages will be

encrypted using the same sequence z and such a cipher can be disclosed.

742,. . . ,Uk

Letâ€™s explain the essence of the problem. Let two messages U I ,

u2,.. . , uk be encrypted using the same sequence z. Then the ci-

and ul,

phertexts will be of the form:

@ z1,uz @ ZZ,. . . , u k @ %k and

UI

@ 2â€™2,.. . ,Yk @ zk

u1 @ z1,u2

Add one ciphertext t o the other and, taking into account the equalities

z @ z = 0,obtain the sequence

i i

@ 01, @ 212, . . . ,Uk @ uk .

U2

U1

We have obtained the analogue of the so-called running-key cipher in which

one text is encrypted using the other text taken from a certain place of a

certain book. It is known that this cipher is insecure although it w s used

a

ñòð. 30 |