redundancy of the texts allows in most cases to recover both messages.

The OFB Block Cipher Mode

8.4.1

The acronym OFB comes from Output FeedBack. In this mode, the block

cipher, parametrised by the secret key K and initialisation vector Yo, pro-

duces a pseudo-random sequence of r-bit numbers z1 , z2 , . . . , Zk which can

be used in (8.10) and (8.11) for encryption and decryption, respectively.

We shall assume, as before, that the blocksize of the cipher is n bits.

The pseudo-random sequence is produced by the scheme

Y , = EK(Y2-1) ,

z = r high-order bits of Y , , 1 I i 5 lc

i

(here r, 1 I r _< n, is a parameter of the method).

If a secure block cipher is used, we obtain a secure generator that meets

all the above given requirements. More exactly, the average value of the

sequence™s period (under randomly chosen K and Yo)is about ˜ 2 bits ˜ - ˜

(see [Menezes et al. (1996)l). Besides, the pseudo-random sequence is

unpredictable in the sense that the adversary cannot predict (or compute)

zi+l if she has zl,. . . ,zi. The possibility of such prediction would mean for

163

Modern Secret K e y Ciphers

the block cipher to be insecure with respect to the known-plaintext attack.

The prediction of zi+l is an even more difficult problem than breaking the

block cipher if r < n [Menezes et al. (1996)].

In the OFB mode, the decryption can be carried out only from the be-

ginning since it is not possible to obtain an arbitrary element of the sequence

z without having computed the preceding elements. In this sense, the mode

is similar to CBC. The advantage of the OFB mode is that the sequence z

can be formed in advance in order to encrypt or decrypt data maximally

fast when they arrive. It is of importance for the systems processing data

in real time.

The CTR Block Cipher Mode

842

..

The name of this mode comes from the word CounTeR. This mode resem-

bles the OFB. The difference is that not the previous output of the cipher

but simply a counter is enciphered. More exactly, the scheme is

+ , i = 1,2,3,.. .

z = T high-order bits of EK(Yo i)

i

where r and Y are parameters.

o

If the “ideal” block cipher is used, this mode ensures the same security

level as the OFB mode. The advantage of the CTR mode is the possibil-

ity of direct computation of any element of the sequence z . It allows for

encrypting and decrypting any fragments of the message independently of

each other.

8.4.3 The RCJ Algorithm

The algorithm RC4 suggested by Rivest in 1994 (see [Schneier (1996)]) is

a representative of a class of customised methods designed specially for

stream ciphers. The pseudo-random generators constructed using such al-

gorithms are usually much faster than the generators based on block ci-

phers.

The RC4 algorithm operates with n-bit words (usually, n = 8). All com-

putations are performed modulo 2” (the remainder z mod 2” is computed

extremely fast by masking all but n low-order bits in 2 using logical “and”

operation) RC4 uses the L-word key K = KoKl . . . K L - ˜ and generates

the sequence of words ii = ˜ 1 ˜ 2 ˜ .3 determined by that K . The state of

..

the generator is defined by the table S of 2” words and by two variables i

and j . At each time instance table S contains all n-bit numbers (from 0

IT Practitioners

164 Basics of Contemporary Cryptography for

to 2" - 1) somehow mixed. Since every element of the table may take on

values in the interval [0, 2" - 11, it may be treated in two ways, either

as a number or as an index to the other element in the table. The secret

key determines only the initial permutation of numbers in the table. This

initial permutation is formed by the following algorithm:

jt-0, S t ( 0 , l )..., 2"- 1);

FOR i = 0,1,. . . ,2" - 1 DO

++

j + ( j s K m o d L) mod 2n,

ii

si;

sj H

jto.

ico,

After this is done, the generator is ready to work. The generation of

a pseudo-random word u i , i = 1,2,3,. . . is performed by the following

algorithm:

+ 1) mod 2";

i (i

+-

+ Si)mod 2n;

j (j

t-

s;

i

sj 4-i

t + (Si+ S j ) mod 2";

s,.

u +-

z

Example 8.2 Let n = 3, K = ( 2 5 ) ˜ L = 2).

(

Form the initial permutation of numbers in table S (perform all com-

putations modulo 8):

s = (0,1,2,3,4,5,6,7),

j = 0,

i=O, j=O+O+2=2, S=(2,1,0,3,4,5,6,7),

i=l, j=2+1+5=0, S=(l,2,0,3,4,5,6,7),

i=2, j=O+O+2=2, S=(l,2,0,3,4,5,6,7),

i=3, j = 2 + 3 + 5 = 2 , S=(l,2,3,0,4,5,6,7),

Z=4, j = 2 + 4 + 2 = 0 , S = ( 4 , 2 , 3 , 0 , 1 , 5 , 6 , 7 ) ,

i = 5 , j = O + 5 + 5 = 2 , S=(4,2,5,0,1,3,6,7),

++

Z = 6, j = 2 6 2 = 2, S = (4,2,6,0,1,3,5,7),

i=7, j=2+7+5=6, S=(4,2,6,0,1,3,7,5).

Modern Secret Key Ciphers 165

Now compute several elements of the pseudo-random sequence E :

S=(4,6,2,0,1,3,7,5), t = 2 + 6 = 0 , ˜1˜4,

i=I,j=O+2=2,

˜2˜0,

i=2,j=2+2=4, S=(4,6,1,0,2,3,7,5), t = 1 + 2 = 3 ,

i=3,j=4+0=4, S=(4,6,1,2,0,3,7,5), t = 2 + 0 = 2 , ug=l,

i=4,j=4+0=4, S=(4,6,1,2,0,3,7,5), t = O + O = O , ˜4˜4,

S = (4,6,1,2,0,5,7,3), t = 5 + 3 = 0,

Z 5, j = 4 + 3 = 7, ˜5 =z 4,

i=6,j=7+7=6, s=(4,6,1,2,0,5,7,3), t = 7 + 7 = 6 , 21657.

To apply Eq. (8.10) for encrypting write the numbers u in binary sys-

i

tem. In our example, each number u is represented by 3 bits, so we obtain

i

...

z=100000001100100111

Cryptographic Hash Functions

8.5

We have already met the notion of hash function in Chap. 4 where hash

functions were parts of digital signature schemes. In those schemes, hash

functions were used as the “digests” or “representatives” of the messages

to be signed. The signature was actually produced on the hash function

value and it was assumed that this value essentially depends on all symbols

of the message and one cannot alter the message without affecting the

hash function value. In this section, we shall more strictly formulate the

requirements and consider one method of construction of cryptographic

hash functions.

Definition 8.1 Any function y = h ( q z 2 . ..x,) which maps the string

(message) ˜ 1 x 2 ..z of arbitrary length n into the word (or number) y of

.,

a fixed length is called the hash function.

The example of hash function is the checksum for the message. In this

case

h ( x l z 2 , ..x,) = (21 + 2 2 + . . . + x ) mod 2w

,

where w is the size of machine word. The length of the number that contains

the value of this function is w bits regardless of the length of the message.

The checksums are often used for detecting unintentional (random) errors

in the message (it is assumed that upon the error the checksum will change

with high probability). Nevertheless it is very easy to make an intentional

error preserving the checksum value. If such hash function had been used in

Basics of Contemporary Cryptography f o r IT Practitioners

166

a digital signature scheme, it would have been possible to alter the signed

document, Therefore, the presented checksum hash function is unsuitable

for cryptographic use.

Let™s formulate the main requirements that any cryptographically secure

hash function must meet. Let z be some string (message). Then

(1) for any given IC, the computation h(s) must be relatively fast;

(2) given y, it must be computationally infeasible to find a message z such

that y = ˜ ( I c ) ;

(3) given IC, it must be computationally infeasible to find any other IC™ # z

such that h(z™) = ˜ ( I c ) ;

(4) it must be computationally infeasible to find any pair of distinct mes-

sages z and IC™ for which h ( ˜ ™= h ( ˜ ) .

)

Notice that the first requirement must always be fulfilled since, other-

wise, the hash function looses any practical meaning. The other require-

ments are important for various applications. For instance, if the passwords

are stored in the form of hash function values then the hash function must

meet the second requirement. For the digital signature schemes, the third

requirement is important. The fourth requirement is needed in some cryp-

tographic protocols. Notice that the fourth requirement is stronger than

the third (i.e. the fulfilment of the fourth implies the fulfilment of the third).

Designing hash functions that would meet all four requirements is not

a simple task. Nowadays a number of hash functions are suggested and

used (e.g. MD5, SHA-1, RIPEMD-160, see (FIPS 180-1 (1995); Menezes

et al. (1996)l) that are believed to be secure (but this is not proved). The

descriptions of these and the similar functions are rather bulky. So we shall

only consider the universal scheme of constructing hash functions based on

block ciphers.

Let there be given a block cipher E which maps the input block X into

the output block Y under the key K ,

Y =EK(X).

We present two algorithms for which the length of hash function value

equals the blocksize of cipher but note that constructions are known that

allow for the length of hash function value to be a multiple to the blocksize.

167

Modern Secret Key Ciphers

In the first algorithm, the message is represented as a sequence of blocks

X I ,X2, . . . ,X,. The last block is padded by zeroes, and sometimes the

length of the message is written thereto. The value of hash function h

results from the following iterative process:

h +-- 0;

F O R i = l , 2 , ..., n DO

h +- E h ( X i ) @Xi.

The initial value of h may be some “magic” number rather than zero,

but it is not important. In this algorithm, the value of h obtained in the

previous iteration is used as the key to the cipher in the next iteration.

Therefore, it is assumed implicitly that the length of key is equal to the

blocksize. However, as we have seen in case of RC6, the length of key can be

significantly greater than the blocksize (in RC6 the length of key can be as

large as 255 bytes). In such cases the second algorithm is more appropriate.

In the second algorithm, the message is represented as a sequence

X I ,X 2 , . . . , X,,, in which the length of each element equals the length of

cipher key. The last element is padded in the same way as in the first

algorithm. The value of hash function h is computed as follows:

h t 0;

F O R i =1,2, ..., m DO

h +- E&(h) @ h.

Here the message elements play the role of keys for the cipher.

The presented algorithms satisfy all the requirements to cryptographic

hash functions provided the underlying block ciphers are secure (see [Gold-

wasser and Bellare (2001); Menezes e t al. (1996)I).

This page intentionally left blank

Chapter 9

Random Numbers in Cryptography

9 1 Introduction

.

We have seen in the previous chapters that random and pseudo-random

numbers play an important role in cryptography. Actually, all cryptosys-

tems that we have described rely on random choice of the keys and various

parameters. Recall also that perfect secrecy of the Vernam cipher is based