<<

. 30
( 36 .)



>>

Algorithm 8.12 RIJNDAEL: ROUND KEY SCHEDULE.

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
( 36 .)



>>