<<

. 27
( 36 .)



>>

mends to fill each table with different numbers from the set {0,1,. . . ,15}
permuted randomly. The content of the tables forms an extra secret pa-
rameter that may be common for a large group of users. Note that in DES
the similar S-boxes are fixed and publicly known.
The following operations are used in the cipher:


+ addition modulo 232;
* cyclic shift left the specified number of bits;
bitwise “exclusive or” of two words, i.e. bitwise addition modulo 2.
@
Modern Secret Key Ciphers 143


Algorithm 8.1 BASIC CYCLE GOST 28147-89.
OF

Block L, R, round key W .
INPUT:
OUTPUT: Transformed block L, R.
FOR i = 0, 1,. . . ,31 DO
1.
k +- R+ Wi, k = ( k 7 - ” k 0 ) 1 6 ;
2.
FOR j = 0,1,. . . ,7 DO
3.
4.

-
kj +- Sj[kj];
L 6 L 6 ( k + 11);
5. 3
R;
L
6.
RETURN L, R.
7.

(At Step 4 of the algorithm distinct 4-bit elements of variable k are used.)
The described LLbasic cycle” is used for encryption and decryption. To
encrypt a block X, construct the round key




put X and W to the input and obtain the encrypted block Y as the output.
To decrypt a block, construct the round key




i.e. (8.5) in the reverse order, input W , Y and obtain X as output.
A program implementation usually requires to rework the loop begin-
ning at Step 3 of Algorithm 8.1 since operating with half-bytes is inefficient.
It is clear that the same transformation can be performed with the use of
4 tables, 256 bytes each, or two tables, 65536 half-words each. For in-
stance, when working with bytes, we have k = (ks.. . k0)256 and Steps 3-4
o Algorithm 8.1 are rewritten as follows:
f

FOR j = 0,1,2,3 DO
3.
kj t T 3 [ k j ] .
4.

The tables Tj, j = 0,1,2,3, are computed beforehand from S-boxes:

FOR i = 0,1,. . . ,255 DO
+
Tj[i]+ Szj[i mod 161 16S˜j+l[i 161.
div
Basics of Contemporary Cryptography for IT Practitioners
144


The standard says nothing about the rules of generating the keying
information except the claim that each S-box should contain a permutation
of different numbers. Yet, it can be seen that, for example, zero key or
trivially defined S-boxes (mapping k to itself) do not provide the security
of the cipher.


The RC5 and RC6 Ciphers
8.2.2
The RC5 and RC6 are modern block ciphers designed by Ron Rivest in 1995
and 1998, respectively. The cipher RC5 (see [Menezes et al. (1996)l) has
been a touchstone for many new cryptanalytic methods. We shall describe
one of the attacks involving RC5 in Sec. 9.5. It must be said that RC5 was
not completely broken by either of the attacks but some of its “weak spots”
were demonstrated followed by increasing demands for parameter values.
As a response to these attacks, the cipher RC6 [Rivest et al. (1998)] was
suggested which may be viewed as an enhanced version of RC5. RC6 took
part in the competition for the new US block cipher standard carried out
in years 1999-2001, had passed to the finals but lost the first place to
another cipher (Rijndael). Nevertheless, intensive investigations of RC6 in
the course of competition do not reveal in it any weakness and this cipher
is highly esteemed by the specialists. For the sake of completeness and for
further references, we shall describe both ciphers but discuss the design
rationale only for RC6.
In RC5, the user specifies the word size w (16, 32, or 64 bits), the
number of rounds r, and the key length 1 in bytes. A particular variant of
the cipher is denoted by the template RC5-w/r/Z, e.g. RC5-32/20/16. The
block always contains two words. The same round key W of 2 r + 2 words
is used in encryption and decryption.
The cipher uses the following operations (all on w-bit words):

+, - addition and subtraction modulo 2”;
@ bitwise “exclusive or” of two words (the sum modulo 2);
*, ˜f cyclic left and right shifts by a specified number of bits (note that

given the word size of w bits the number of shift positions is re-
duced modulo w, such a reduction being usually done automati-
cally at machine level - the processor uses only low-order logw
bits of the number defining the shift amount).

The encryption algorithm is as follows.
145
Modern Secret K e y Ciphers


Algorithm 8.2 RC5: ENCRYPTION.

Two-word block ( a ,b ) , round key W .
INPUT:
OUTPUT: Encrypted block ( a ,b).
1. ata+Wo,btb+Wl;
FOR i = 1,2,. . . ,T DO
2.
+
a + ( ( a 63 b) * b) WZi,
3.
+
b + ( ( b ‚¬9 a ) * a ) w2i+1;
4.
RETURN ( a , b ) .
5.

To decrypt, undone the process in reverse order.


Algorithm 8.3 RC5: DECRYPTION.

Two-word block ( a ,b), round key W
INPUT:
OUTPUT: Decrypted block ( a ,b).
FOR i = T , T - 1,.. . ,1 DO
1.
2. ( ( b - WZi+l) C-t a ) 63 a,
b +

u t ( ( u - Wzi) 6) 63 6;
3.
w,;
b c b - WI, a + a -
4.
RETURN (a,b).
5.

The process of round key formation (round key schedule) is more com-
plicated in RC5 and RC6 than in GOST 28147-89, which is typical for most
of modern ciphers. In fact, the secret key K is expanded to a longer pseudo-
random sequence W in order to harden the cryptanalysis of a cipher.
Denote by c the number of words in the key, c = 81/w. With the round
key schedule algorithm the secret key K is expanded to the round key W :




The following “magic” numbers are used in the algorithm: P,, the first w
bits of the binary expansion for e - 2 where e = 2.718281828.. . is the base
of natural logarithm, and Q,, the first w bits of the binary expansion for
- 1 where C#J = ( - 1)/2 is the golden section. In Table 8.1 the values
6
of P, and Qw are given in hexadecimal system for various word lengths.
With all this in mind, the algorithm of round key formation for RC5 is
written down as follows.
Basics of Contemporary Cryptography for IT Practitioners
146


Algorithm 8.4 RC5: ROUND KEY SCHEDULE.

Secret key K .
INPUT:
OUTPUT: Round key W .
w Pw;
o
1. +-



F O R i = 1 , 2 ,..., 2 r + 1 DOWi+Wi-l+Q,;
2.
a +- 0, b t 0, i +- 0, j +- 0;
3.
+
k +- 3max(c, 2r 2);
4.
DO k times
5.
++
Wi +- (Wi u b) Q 3, a +- Wi,
6.
Kj + ( K j + a + b ) ˜ ( ˜ + b ) b + K j ,
,
7.
+
i t i + 1mod 2r 2, j + j + 1mod c;
8.
RETURN W .
9.

Now we describe the cipher RC6. It is quite close to RC5. In RC6, the
user also specifies the word size w (16, 32, or 64 bits), the number of rounds
r, and the key length 1 in bytes (from 0 to 255). But, in contrast to RC5, the
block consists of 4 words and the round key W of 2r+4 words. A particular
variant of the cipher is denoted similarly by the template RCG-w/r/l. For
example, RC6-32/20/16 is the variant with the blocksize and key length
128 bits, 20 rounds (this variant had been proposed a a candidate for the
s
US standard).
The cipher uses the same operations as RC5 but one new operation is
added:
* multiplication modulo 2"


Algorithm 8.5 RC6: ENCRYPTION.

Four-word block ( a ,b, c, d ) , round key W .
INPUT:
OUTPUT: Encrypted block (a,b, c, d).
b+-b+Wl, d + d + W 1 ;
1.
FOR i = 1 , 2 , . . . , r DO
2.
+
t +- ( b * (2b 1))c ' logw,
3. -
4. u t ( d * ( 2 d + 1 ) ) c-'logw,
+
a +- ( ( a C t ) u) WZi,
5. B Q


C+- ( ( a 4 t ) + W 2 i + l ,
6. *
( a ,b, c, 4 ( 4 c, d , a ) ;
7. +




+ +
8. a a W2rf27 c c W2rf3;
RETURN (a,b,c,d).
9.
Modern Secret Key Ciphers 147


To decrypt, as in RC5, undo the process in reverse order.

Algorithm 8.6 RC6: DECRYPTION.
Four-word block (a,b, c, d ) , round key W .
INPUT:
OUTPUT: Decrypted block ( a ,b, c, d ) .
c c - W 2 r f 3 , a +-a - Wzr+2;
1. +-



<<

. 27
( 36 .)



>>