. 31
( 36 .)


in the past [Menezes et al. (1996)I. The statistical analysis based on the
redundancy of the texts allows in most cases to recover both messages.

The OFB Block Cipher Mode
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
(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
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
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)

where r and Y are parameters.
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-
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,
sj H


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

+ 1) mod 2";
i (i
+ Si)mod 2n;
j (j
sj 4-i

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

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=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-
tem. In our example, each number u is represented by 3 bits, so we obtain


Cryptographic Hash Functions

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
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

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.
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


. 31
( 36 .)