Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter




CHAPTER 14 ............................................... 330
Still Other Block Ciphers .......................... 330
14.1 GOST ................................................ 330
Description GOST ........................................ 330
Table 14.1 Use of GOST Subkeys in ........... 332
Cryptanalysis of GOST ................................. 332
Table 14.2 GOST S-Boxes .......................... 332
CAST ........................................................ 333
BLOWFISH .............................................. 335
Description of Blowfish ................................. 335
Security of Blowfish ...................................... 338
SAFER ...................................................... 338
Description of SAFER K-64 .......................... 338
SAFER K-128 ............................................... 340
Security SAFER K-64 ................................... 340
3-WAY ...................................................... 340
Description 3-Way ........................................ 341
CRAES ..................................................... 341
SXALS/MBAL ........................................... 343
RC5 ........................................................... 343
OTHER BLOCK ALGORITHMS .............. 345
THEORY OF BLOCK CIPHER ................. 345
Feistel Networks ........................................... 346
Simple Relations ........................................... 346
Group Structure ............................................ 347
Weak Keys ................................................... 347
Strength against Differential and ................... 347
S-Box Design ................................................ 348
Designing a Block Cipher ............................. 350
USING ONE-WAY HASH FUNCTIONS .. 350
Karn .............................................................. 350
Lwby-Rackoff ................................................ 351
Message Digest Cipher (MDC) ..................... 352
Security Ciphers Based on One-Way Hash ... 352
Figure 14.5 Message Digest Cipher .............. 353
CHOOSING A BLOCK ALGORITHM ...... 353
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter



Table 14.3 Encryption Speeds of Some ....... 354
Page 330
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter




14
CHAPTER


Still Other Block Ciphers


14.1 GOST
GOST is a block algorithm from the former Soviet Union [655,1393]. “GOST” is an
acronym for “Gosudarstvennyi Standard,” or Government Standard, sort of similar
to a FIB, except that it can (and does) refer to just about any kind of standard. (Actu-
ally, the full name is Gosudarstvennyi Standard Soyuza SSR, or Government Stan-
dard of the Union of Soviet Socialist Republics.) This standard is number 28147-89.
The Government Committee for Standards of the USSR authorized the standard,
whoever they were.
I don™t know whether GOST 28147-89 was used for classified traffic or just for
civilian encryption. A remark at its beginning states that the algorithm “satisfies all
cryptographic requirements and not limits the grade of information to be pro-
tected.” I have heard claims that it was initially used for very high-grade communi-
cations, including classified military communications, but I have no confirmation.
of GOST
Description
GOST is a 64-bit block algorithm with a 256-bit key. GOST also has some addi-
tional key material that will be discussed later. The algorithm iterates a simple
encryption algorithm for 32 rounds.
To encrypt, first break the text up into a left half, L, and a right half, R. The sub-
key for round i is Kie A round, i, of GOST is:
Li=Ri-1
Ri = Li - 1 0 f(Ri - 1, Ki)
Figure 14.1 is a single round of GOST. Function f is straightforward. First, the
right half and the ith subkey are added modulo 232 The result is broken into eight
.
4-bit chunks, and each chunk becomes the input to a different S-box. There are eight
different S-boxes in GOST; the first 4 bits go into the first S-box, the second 4 bits go
Page 331
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
CHAPTER14 Still Other Block Ciphers




Choose One Subkey




S-Box Substitution



Left Circular Shift




Figure 14.1 One round of GOST.


into the second S-box, and so on. Each S-box is a permutation of the numbers 0
through 15. For example, an S-box might be:
7, 10, 2, 4, 15, 9, 0, 3, 6, 12, 5, 13, 1, 8, 11
In this case, if the input to the S-box is 0, the output is 7. If the input is 1, the out-
put is 10, and so on. All eight S-boxes are different; these are considered additional
key material. The S-boxes are to be kept secret.
The outputs of the eight S-boxes are recombined into a 32-bit word, then the
entire word undergoes an 11-bit left circular shift. Finally, the result XORed to the
left half to become the new right half, and the right half becomes the new left half.
Do this 32 times and you™re done.
The subkeys are generated simply. The 256-bit key is divided into eight 32-bit
blocks: kl, kz, . . . , k,. Each round uses a different subkey, as shown in Table 14.1.
Decryption is the same as encryption with the order of the kis reversed.
The GOST standard does not discuss how to generate the S-boxes, only that they
are somehow supplied [655]. This has led to speculation that some Soviet organiza-
tion would supply good S-boxes to those organizations it liked and bad S-boxes to
those organizations it wished to eavesdrop on. This may very well be true, but fur-
ther conversations with a GOST chip manufacturer within Russia offered another
alternative. He generated the S-box permutations himself, using a random-number
generator.
Page 332
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
14.1 GOST


Table 14.1
Use of GOST Subkeys in Different Rounds
4 56 7 8 9 10 11 12 13 14 15 16
Round: 1 2 3
4 5 6 78 123 4 5 6 78
Subkey: 1 2 3
19 20 21 22 23 24 25 26 27 28 29 30 31 32
Round: 17 18
4 5 67887654321
Subkev: 1 2 3


More recently, a set of S-boxes used in an application for the Central Bank of the
Russian Federation surfaced. These S-boxes are also used in the GOST one-way
hash function (see section 18.11) [657].They are listed in Table 14.2.
Cryptanalysis of GOST
These are the major differences between DES and GOST.

- DES has a complicated procedure for generating the subkeys from the
keys. GOST has a very simple procedure.
- DES has a 56-bit key; GOST has a 256-bit key. If you add in the secret
S-box permutations, GOST has a total of about 610 bits of secret
information.


Table 14.2
GOST S-Boxes
S-box 1:
13 8 11 1 5 3
4 10 9 2 0 14 6 12 7 15
S-box 2:
3 5 9
6 13 15 10 2 8 1 0 7
14 11 4 12
S-box 3:
9 11
15 12 7 6 0
10 3 4 2 14
5 8 1 13
S-box 4:
5 3
7 13 10 0 8 9 4 6 1211 2
1 15 14
S-box 5:
11 2
10 9 14 0 3
5 15 13 8 4
6 12 7 1
S-box 6:
15 14
6 8 5 9 12
7 2 1 13 3
4 11 10 0
S-box 7:
2 12
10 14 7 6 8
315 5 9 0
13 11 4 1
S-box 8:
1 15 13 0 5 8 12
7 10 4 9 2 3 14 6 11
Page 333
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
Still Other Block Ciphers
CHAPTER 14


- The S-boxes in DES have 6-bit inputs and 4-bit outputs; the S-boxes
in GOST have 4-bit inputs and outputs. Both algorithms have eight
S-boxes, but an S-box in GOST is one-fourth the size of an S-box in
DES.
- DES has an irregular permutation, called a P-box; GOST uses an 1 l-
bit left circular shift.
- DES has 16 rounds; GOST has 32 rounds.

If there is no better way to break GOST other than brute force, it is a very secure
algorithm. GOST has a 256-bit key-longer if you count the secret S-boxes. Against
differential and linear cryptanalysis, GOST is probably stronger than DES. Although
the random S-boxes in GOST are probably weaker than the fixed S-boxes in DES,
their secrecy adds to GOST™s resistance against differential and linear attacks. Also,
both of these attacks depend on the number of rounds: the more rounds, the more
difficult the attack. GOST has twice as many rounds as DES; this alone probably
makes both differential and linear cryptanalysis infeasible.
The other parts of GOST are either on par or worse than DES. COST doesn™t have
the same expansion permutation that DES has. Deleting this permutation from
DES weakens it by reducing the avalanche effect; it is reasonable to believe that
GOST is weaker for not having it. GOST™s use of addition instead is no less secure
than DES™s XOR.
The greatest difference between them seems to be GOST™s cyclic shift instead of a
permutation. The DES permutation increases the avalanche effect. In GOST a change
in one input bit affects one S-box in one round, which then affects two S-boxes in the
next round, three the round after that, and so on. GOST requires 8 rounds before a sin-
gle change in an input affects every output bit; DES only requires 5 rounds. This is cer-
tainly a weakness. But remember: COST has 32 rounds to DES™s 16.
GOST™s designers tried to achieve a balance between efficiency and security. They
modified DES™s basic design to create an algorithm that is better suited for software
implementation. They seem to have been less sure of their algorithm™s security, and
have tried to compensate by making the key length very large, keeping the S-boxes
secret, and doubling the number of iterations. Whether their efforts have resulted in
an algorithm more secure than DES remains to be seen.

14.2 CAST
CAST was designed in Canada by Carlisle Adams and Stafford Tavares [10,7]. They
claim that the name refers to their design procedure and should conjure up images
of randomness, but note the authors™ initials. The example CAST algorithm uses a
64-bit block size and a 64-bit key.
The structure of CAST should be familiar. The algorithm uses six S-boxes with an
8-bit input and a 32-bit output. Construction of these S-boxes is implementation-
dependent and complicated; see the references for details.
Page 334
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
14.3 CAST


To encrypt, first divide the plaintext block into a left half and a right half. The
algorithm has 8 rounds. In each round the right half is combined with some key
material using function f and then XORed with the left half to form the new right
half. The original right half (before the round) becomes the new left half. After 8
rounds (don™t switch the left and right halves after the eighth round), the two halves
are concatenated to form the ciphertext.
Function f is simple:
(1) Divide the 32-bit input into four 8-bit quarters: a, b, c, d.
(2) Divide the 16-bit subkey into two 8-bit halves: e, f.
(3) Process a through S-box 1, b through S-box 2, c through S-box 3, d through
S-box 4, e through S-box 5, and f through S-box 6.
(4) XOR the six S-box outputs together to get the final 32-bit output.
Alternatively, the 32-bit input can be XORed with 32 bits of key, divided into four
8-bit quarters, processed through the S-boxes, and then XORed together [7]. N
rounds of this appears to be as secure as N + 2 rounds of the other option.
The 16-bit subkey for each round is easily calculated from the 64-bit key. If kl,
h, . . . , k, are the 8 bytes of the key, then the subkeys for each round are:
Round 1: kl, k,
Round 2: k3, k,
Round 3: kg, k,
Round 4: k,, k8
Round 5: kG k3
Round 6: k2, k,
Round 7: kg, k,
Round 8: kg, k5
The strength of this algorithm lies in its S-boxes. CAST does not have fixed S-boxes;
new ones are constructed for each application. Design criteria are in [lo]; bent func-
tions are the S-box columns, selected for a number of desirable S-box properties
(see Section 14.10). Once a set of S-boxes has been constructed for a given imple-
mentation of CAST, they are fixed for all time. The S-boxes are implementation-
dependent, but not key-dependent.
It was shown in [lo] that CAST is resistant to differential cryptanalysis and in
[728] that CAST is resistant to linear cryptanalysis. There is no known way to break
CAST other than brute force.
Northern Telecom is using CAST in their Entrust security software package for
Macintoshes, PCs, and UNIX workstations. The particular S-boxes they chose are
not public. The Canadian government is evaluating CAST as a new encryption stan-
dard. CAST is patent-pending.
Page 335
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
CHAPTER14 Still Other Block Ciphers


14.3 BLOWFISH
Blowfish is an algorithm of my own design, intended for implementation on large
microprocessors [ 1388,1389]. The algorithm is unpatented, and the C code in the
back of this book is in the public domain. I designed Blowfish to meet the following
design criteria.

1. Fast. Blowfish encrypts data on 32-bit microprocessors at a rate of 26 clock
cycles per byte.
2. Compact. Blowfish can run in less than 5K of memory.
3. Simple. Blowfish uses only simple operations: addition, XORs, and table
lookups on 32-bit operands. Its design is easy to analyze which makes it
resistant to implementation errors [ 13911.
4. Variably Secure. Blowfish™s key length is variable and can be as long as
448 bits.

Blowfish is optimized for applications where the key does not change often, like a
communications link or an automatic file encryptor. It is significantly faster than
DES when implemented on 32-bit microprocessors with large data caches, such as
the Pentium and the PowerPC. Blowfish is not suitable for applications, such as
packet switching, with frequent key changes, or as a one-way hash function. Its
large memory requirement makes it infeasible for smart card applications.
Description of Blowfish
Blowfish is a 64-bit block cipher with a variable-length key. The algorithm con-
sists of two parts: key expansion and data encryption. Key expansion converts a key
of up to 448 bits into several subkey arrays totaling 4168 bytes.
Data encryption consists of a simple function iterated 16 times. Each round con-
sists of a key-dependent permutation, and a key- and data-dependent substitution.
All operations are additions and XORs on 32-bit words. The only additional opera-
tions are four indexed array data lookups per round.
Blowfish uses a large number of subkeys. These keys must be precomputed before
any data encryption or decryption.
The P-array consists of 18 32-bit subkeys:
PI, P2, . * . , PI8
Four 32-bit S-boxes have 256 entries each:
SW, SW . . . , Sl,Z55
sz.09&Jr . . . >sz.255
SW3&Jr . . . 7 &,255
s˜w, &Jr . . f 7 s4255
The exact method used to calculate these subkeys will be described later in this
section.
Page 336
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter




1 Plaintext ]




p, 32 Bits=+:1




L /J
13 More Iterations




)32Bits , 64Bi2Bits)



ri Figure 14.2 Blowfish.
Cipher-text




Blowfish is a Feistel network (see Section 14.10) consisting of 16 rounds. The
input is a 64-bit data element, x. To encrypt:
Divide x into two 32-bit halves: xL, xR
For i = 1 to 16:
XL = XL 0 PI
XR = F(xJ @x,

Swap xL and xR
Swap xL and xR (Undo the last swap.]
@PIT
XR=XR

XL = XL 0 PI8
Recombine xL and xR
Page 337
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
14 Still Other Block Ciphers
CHAPTER




8 Bits Is-Box2 Bitsn

32 Bits

S-Box 3 32 Bits
8 Bits

32 Bits

32 Bits
8 Bits
S-Box 4


Figure 14.3 Function F.


Function F is as follows (see Figure 14.3):
Divide xL into four eight-bit quarters:
a, b, c, and d F(xr) = ((S,,, + S2.,,mod 232)0 S,,,) + S4,dmod 232
Decryption is exactly the same as encryption, except that Pi, PZ, . . . , Pi8 are used
in the reverse order.
Implementations of Blowfish that require the fastest speeds should unroll the
loop and ensure that all subkeys are stored in cache. See [568] for details.
The subkeys are calculated using the Blowfish algorithm. The exact method
follows.

(1) Initialize first the P-array and then the four S-boxes, in order, with a fixed
string. This string consists of the hexadecimal digits of rc.
(2) XOR Pi with the first 32 bits of the key, XOR P2with the second 32-bits of
the key, and so on for all bits of the key (up to Pi*). Repeatedly cycle
through the key bits until the entire P-array has been XORed with key bits.
(3) Encrypt the all-zero string with the Blowfish algorithm, using the subkeys
described in steps (1) and (2).
(4) Replace PI and P2 with the output of step (3).
(5) Encrypt the output of step (3) using the Blowfish algorithm with the mod-
ified subkeys.
(6) Replace P3 and Pd with the output of step (5).
(7) Continue the process, replacing all elements of the P-array, and then all
four S-boxes in order, with the output of the continuously changing Blow-
fish algorithm.
Page 338
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
14.4 SAFER


In total, 521 iterations are required to generate all required subkeys. Applica-
tions can store the subkeys-there™s no need to execute this derivation process
multiple times.

Security of Blowfish
Serge Vaudenay examined Blowfish with known S-boxes and r rounds; a differen-
tial attack can recover the P-array with 2” + ™ chosen plaintexts [ 15681. For certain
weak keys that generate bad S-boxes (the odds of getting them randomly are 1 in 214),
the same attack requires only 2” + ™ chosen plaintexts to recover the P-array. With
unknown S-boxes this attack can detect whether a weak key is being used, but can-
not determine what it is (neither the S-boxes nor the P-array). This attack only
works against reduced-round variants; it is completely ineffective against 16-round
Blowfish.
Of course, the discovery of weak keys is significant, even though they seem
impossible to exploit. A weak key is one in which two entries for a given S-box are
identical. There is no way to check for weak keys before doing the key expansion. If
you are worried, you have to do the key expansion and check for identical S-box
entries. I don™t think this is necessary, though.
I know of no successful cryptanalysis against Blowfish. To be safe, do not imple-
ment Blowfish with a reduced number of rounds.
Kent Marsh Ltd. has incorporated Blowfish in their FolderBolt security product for
Microsoft Windows and Macintosh. It is also part of Nautilus and PGPfone.

14.4 SAFER
SAFER K-64 stands for Secure And Fast Encryption Routine with a Key of 64 bits
[ 10091. James Massey produced this nonproprietary algorithm for Cylink Corp. and
it is incorporated into some of their products. The government of Singapore is plan-
ning to use this algorithm-with a 128-bit key [ lOlO]-for a wide variety of applica-
tions. There are no patent, copyright, or other restrictions on its use.
The algorithm has a block and key size of 64 bits. It is not a Feistel network like
DES (see Section 14.10) but an iterated block cipher: The same function is applied
for some number of rounds. Each round uses two 64-bit subkeys, and the algorithm
only uses operations on bytes.
Description of SAFER K-64
The plaintext block is divided into eight byte-length sub-blocks: B,, B2, . . . , B7,
B8. Then the sub-blocks go through r rounds. Finally, an output transformation is
applied to the sub-blocks. Each round uses two subkeys: Kii _ i and Kzi.
Figure 14.4 shows one round of SAFER K-64. First, sub-blocks are either XORed or
added with bytes of subkey Kli - i. Then, the eight sub-blocks are subjected to one of
two nonlinear transformations:
y = 45” mod 257. (If x = 128, then y = 0.)
y=log45x. (Ifx=O, theny= 128.)
Page 339
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
14 Still Other Block Ciphers
CHAPTER


These are operations in the finite field GF(257), and 45 is a primitive element in
that field. In practical implementations of SAFER K-64, it is quicker to implement
this in a lookup table than to calculate new results all the time.
Then, sub-blocks are either XORed or added with bytes of subkey Kzr. The results
of this operation are fed through three layers of linear operations designed to
increase the avalanche effect. Each operation is called a Pseudo-Hadamard Trans-
form (PHT). If the inputs to a PHT are u1 and a2, then the outputs are:
bl = (2a, + a2) mod 256
b2 = (aI + az) mod 256
After r rounds, there is a final output transformation. This is the same as the first
step of each round. B,, B4, B5, and B8 are XORed with the corresponding bytes of the
last subkey, and B2, B3, B6, and B, are added to the corresponding bytes of the last
subkey. The result is the ciphertext.




fK2i- I




- K2i




Figure 14.4 One round of SAFER
Page 340
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
14.5 3-Way


Decryption is the reverse process: the output transformation (with subtraction
instead of addition), then r reverse rounds. The Inverse PHT (IPHT) is:
al = (b, - b,) mod 256
a2 = (-bl + 2bz) mod 256
Massey recommends 6 rounds, but you can increase that if you want greater
security.
Generating subkeys is easy. The first subkey, K1, is simply the user key. Subse-
quent subkeys are generated by the following procedure:
Ki+l=(K1<<<3i)+ci
The symbol “<<<” is a left circular shift or a left rotation. The rotation is byte by
byte, and c, is a round constant. If cii is the jth byte of the ith round constant, then
you can calculate all of the round constants by the formula
257
c,, = 4545V9i + il mod 256) mod 257 mod
11

Generally, these values are stored in a table.

SAFER K-128
This alternate key schedule was developed by the Ministry of Home Affairs in
Singapore, and then incorporated into SAFER by Massey [lOlO]. It uses two keys, K,
and Kb, each 64-bits long. The trick is to generate two subkey sequences in parallel,
and then alternate subkeys from each sequence. This means that if you choose K, =
Kb, then the 128-bit key is compatible with the 64-bit key K,.

of SAFER K-64
Security
Massey showed that SAFER K-64 is immune to differential cryptanalysis after 8
rounds and is adequately secure against the attack after 6 rounds. After only 3
rounds linear cryptanalysis is ineffective against this algorithm [lOlO].
Knudsen found a weakness in the key schedule: For virtually every key, there
exists at least one (and sometimes as many as nine) other key that encrypts some
different plaintext to identical ciphertexts [862]. The number of different plaintexts
that encrypt to identical ciphertexts after 6 rounds is anywhere from 222 to 228.
While this attack may not impact SAFER™s security when used as an encryption
algorithm, it greatly reduces its security when used as a one-way hash function. In
any case, Knudsen recommends at least 8 rounds.
SAFER was designed for Cylink, and Cylink is tainted by the NSA [80]. I recom-
mend years of intense cryptanalysis before using SAFER in any form,


14.5 3-WAY

3-Way is a block cipher designed by Joan Daemen [402,410]. It has a 96-bit block
length and key length, and is designed to be very efficient in hardware.
Page 341
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
CHAPTER14 Still Other Block Ciphers


3-Way is not a Feistel network, but it is an iterated block cipher. 3-Way can have
n rounds; Daemen recommends 11.
of 3-Way
Description
The algorithm is simple to describe. To encrypt a plaintext block, x:
Fori=Oton- 1
x=xXORK,
x = theta (x)
x = pi - 1 (x)
x = gamma (x)
x = pi - 2 (x)
x=xOK,
x = theta (x)
The functions are:
- theta(x) is a linear substitution function-basically a bunch of circu-
lar shifts and XORs.
- pi-l(x) and pi-2(x) are simple permutations.
- gamma(x) is a nonlinear substitution function. This is the step that
gives 3-Way its name; it is the parallel execution of the substitution
step on 3-bit blocks of the input.

Decryption is similar to encryption, except that the bits of the input have to be
reversed and the bits of the output have to be reversed. Code to implement 3-Way
can be found in the back of this book.
So far, there has been no successful cryptanalysis of 3-Way. The algorithm is
unpatented.

14.6 CRAES
This algorithm was developed by Burt Kaliski and Matt Robshaw of RSA Laborato-
ries (8101. The idea behind Crab is to use techniques from one-way hash functions
to make a fast encryption algorithm. Hence, Crab is very similar to MD5, and this
section assumes you are familiar with Section 18.5.
Crab has a very large block: 1024 bytes. Since Crab is presented more as a research
contribution than a real algorithm, no definitive key-generation routines are pre-
sented. The authors suggest a method that could turn an 80-bit key into three req-
uisite subkeys, although the algorithm could easily accept variable-length keys.
Crab uses two sets of large subkeys:
A permutation of the numbers 0 through 255: PO,PI, P2, . , Pps5.
A 2048-entry array of 32-bit numbers: So,SI, Sp,. . . , S2047.
Page 342
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
14.6 Crab


These subkeys must all be calculated before encryption or decryption.
To encrypt a 1024-byte block X:

(1) Divide X into 256 32-bit sub-blocks: X0, X1, Xx, . . . , X1,,.
(2) Permute the sub-blocks of X according to l?
(3) For r = 0 to 3
Forg=Oto63
A = X,,, <<< 21
11 21
<<<
B =X148+
c = xi4g +2)<<< 21
D = -q, +3) <c-c 21
For step s = 0 to 7
A = A 0 (B + f,(B,C,D) + Smr + 8g ,I
+
TEMP = D
D=C
C=B
B=A<<<5
A = TEMP
2r-A
<<< -
x,4,1

<<< -B
21 -
X14g.+11


+2)<<< = c
2r
x,,


+31<<< zr = D
X,4,


(4) Recombine X0, Xi, X,, . . . , X,,, to form the ciphertext.

The functions f,(B,C,D) are similar to those used in MD5:
f,(B,C,D) = (B A C) v ((7 B) AD)
f,(B,C,D) = (B AD) v (C A (7 D))
f,(B,C,D) =B0 C0 D
f,(B,C,D) = C 0 (B v (7 D))
Decryption is the reverse process.
Generating the subkeys is a large task. Here is how the permutation array, P,
could be generated from an 80-bit key, K.

(1) Initialize K,, K1, Kz, . . . , Kg with the 10 bytes of K.
(2) For i = 10 to 255
K,=K˜-zOK˜-,OK˜-˜OK˜-,,
(3) For i = 0 to 255, P, = i
Page 343
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter

14 Still Other Block Ciphers
CHAPTER


(4) m = 0
(5) For j = 0 to 1
For i = 256 to 1 step -1
m=(K256-i+K25,-i)modi
K257-i=K257-i<<<3
Swap Pi and PI - 1
The S-array of 2048 32-bit words could be generated in a similar manner, either
from the same 80-bit key or from another key. The authors caution that these
details should “be viewed as motivational; there may very well be alternative
schemes which are both more efficient and offer improved security” [810].
Crab was proposed as a testbed of new ideas and not as a working algorithm. It
uses many of the same techniques as MD.5. Biham has argued that a very large block
size makes an algorithm easier to cryptanalyze [ 1601.On the other hand, Crab may
make efficient use of a very large key. In such a case, “easier to cryptanalyze” might
not mean much.

14.7 SXALS/MBAL
This is a 64-bit block algorithm from Japan [769]. SXAL8 is the basic algorithm;
MBAL is an expanded version with a variable block length. Since MBAL does some
clever things internally, the authors claim that they can get adequate security with
only a few rounds. With a block length of 1024 bytes, MBAL is about 70 times faster
than DES. Unfortunately, [ 11741 shows that MBAL is susceptible to differential
cryptanalysis, and [865] shows that it is susceptible to linear cryptanalysis.

14.8 RC5
RC5 is a block cipher with a variety of parameters: block size, key size, and num-
ber of rounds. It was invented by Ron Rivest and analyzed by RSA Laboratories
[ 1324,1325].
There are three operations: XOR, addition, and rotations. Rotations are constant-
time operations on most processors and variable rotations are a nonlinear function.
These rotations, which depend on both the key and the data, are the interesting
operation.
RC5 has a variable-length block, but this example will focus on a 64-bit data
block. Encryption uses 2r + 2 key-dependent 32-bit words-&,, Sr, ST,. . . , Sti + 1-
where r is the number of rounds. We™ll generate those words later. To encrypt, first
divide the plaintext block into two 32-bit words: A and B. (RC5 assumes a little-
endian convention for packing bytes into words: The first byte goes into the low-
order bit positions of register A, etc.) Then:
A=A+$
B=B+S,
Page 344
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter

14.8 RC5


For i = 1 to r:
A = ((A 0 B) <<< B) + Sli
B=((BOA)<<<A)+Sli+l
The output is in the registers A and B.
Decryption is just as easy. Divide the plaintext block into two words, A and B,
and then:
Fori=rdownto 1:
B = ((B - Szi+ 1)>>> A) $ A
A = ((A - S,,) >>> B) Q9B
B=B-S1
A=A-So
The symbol “>>>” is a right circular shift. Of course, all addition and subtraction
are mod 232.
Creating the array of keys is more complicated, but also straightforward. First,
copy the bytes of the key into an array, L, of c 32-bit words, padding the final word
with zeros if necessary. Then, initialize an array, S, using a linear congruential gen-
erator mod 2j2:
so = P
fori= 1 to2(r+ l)- 1:
Si = (Si - I+ Q) mod 232
P = Oxb7e15163 and Q = Ox9e3779b9; these constants are based on the binary rep-
resentation of e and phi.
Finally, mix L into S:
i=j=fJ

A=B=O
do 3n times (where n is the maximum of 2(r + 1) and c):
A=Si=(Si+A+B)<<<3
B=Li=(Li+A+B)<<<(A+B)
i=(i+ 1) mod2(r+ 1)
j=(j+ 1)modc
RC5 is actually a family of algorithms. We just defined RC5 with a %-bit word
size and 64-bit block; there™s no reason why the same algorithm can™t have a 64-bit
word size and 128-bit block size. For w = 64, P and Q are Oxb7e15 1628aed2a6b and
Ox9e3779b97f4a7c15, respectively. Rivest designates particular implementations of
RC5 as RC5-w/r/b, where w is the word size, r is the number of rounds, and b is the
length of the key in bytes.
RC5 is new, but RSA Laboratories has spent considerable time analyzing it with
a 64-bit block. After 5 rounds, the statistics look very good. After 8 rounds, every
Page 345
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter

CHAPTER14 Still Other Block Ciphers


plaintext bit affects at least one rotation. There is a differential attack that requires
224chosen plaintexts for 5 rounds, 245for 10 rounds, 253for 12 rounds, and 268for 15
rounds. Of course, there are only 264possible chosen plaintexts, so this attack won™t
work for 15 or more rounds. Linear cryptanalysis estimates indicate that it is secure
after 6 rounds. Rivest recommends at least 12 rounds, and possibly 16 [ 13251. This
number may change.
RSADSI is in the process of patenting RC5, and the name is trademarked. The com-
pany claims that license fees will be very small, but you™d better check with them.

14.9 OTHER BLOCK ALGORITHMS
There is an algorithm called CRYPTO-MECCANO in the literature [301]; it is inse-
cure. Four Japanese cryptographers presented an algorithm based on chaotic maps at
Eurocrypt ˜91 [687,688]; Biham cryptanalyzed the algorithm at the same conference
[ 1571.Another algorithm relies on subsets of a particular set of random codes [693].
There are several algorithms based on the theory of error-correcting codes: a variant
of the McEliece algorithm (see Section 19.7) [786,1290], the Rao-Nam algorithm
variants of the Rao-Nam algorithm
[1292,733,1504,1291,1056,1057,1058,1293],
[464,749,1503], and the Li-Wang algorithm [964,1561]-they are all insecure. CALC
is insecure [ 11091. An algorithm called TEA, for Tiny Encryption Algorithm, is too
new to comment on [1592]. Vino is another algorithm [503]. MacGuffin, a block
algorithm by Matt Blaze and me, is also insecure [ 1891; it was broken at the same
conference it was proposed. BaseKing, similar in design philosophy as 3-way but
with a 192-bit block [402], is too new to comment on.
There are many more block algorithms outside the cryptology community. Some
are used by various government and military organizations. I have no information
about any of those. There are also dozens of proprietary commercial algorithms.
Some might be good; most are probably not. If companies do not feel that their inter-
ests are served by making their algorithms public, it is best to assume they™re right
and avoid the algorithm.

14.10 THEORY OF BLOCK CIPHER DESIGN
In Section 11.1, I described Shannon™s principles of confusion and diffusion. Fifty
years after these principles were first written, they remain the cornerstone of good
block cipher design.
Confusion serves to hide any relationship between the plaintext, the ciphertext,
and the key. Remember how linear and differential cryptanalysis can exploit even
a slight relationship between these three things? Good confusion makes the rela-
tionship statistics so complicated that even these powerful cryptanalytic tools
won™t work.
Diffusion spreads the influence of individual plaintext or key bits over as much of
the ciphertext as possible. This also hides statistical relationships and makes crypt-
analysis more difficult.
Page 346
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter




Confusion alone is enough for security. An algorithm consisting of a single key-
dependent lookup table of 64 bits of plaintext to 64 bits of ciphertext would be
plenty strong. The problem is that large lookup tables require lots of memory to
implement: 10” bytes of memory for the table just mentioned. The whole point of
block cipher design is to create something that looks like a large lookup table, but
with much smaller memory requirements.
The trick is to repeatedly mix confusion (with much smaller tables) and diffusion
in a single cipher in different combinations. This is called a product cipher. Some-
times a block cipher that incorporates layers of substitution and permutation is
called a substitution-permutation network, or even an SP network.
Look back at function f of DES. The expansion permutation and P-box perform
diffusion; the S-boxes perform confusion. The expansion permutation and P-box are
linear; the S-boxes are nonlinear. Each operation is pretty simple on its own;
together they work pretty well.
DES also illustrates a few more principles of block cipher design. The first is the
idea of an iterated block cipher. This simply means taking a simple round function
and iterating it multiple times. Two-round DES isn™t very strong; it takes 5 rounds
before all of the output bits are dependent on all of the input bits and all of the key
bits [ 1078,1080]. Sixteen-round DES is strong; 32-round DES is even stronger.

Feistel Networks
Most block algorithms are Feistel networks. This idea dates from the early 1970s
[552,553]. Take a block of length n and divide it into two halves of length n/2: L and
R. Of course, n must be even. You can define an iterated block cipher where the out-
put of the ith round is determined from the output of the previous round:
L, = R, _ 1
Ri = Li - 1 0 f(Ri -1,Ki)
K, is the subkey used in the ith round and f is an arbitrary round function.
You™ve seen this concept in DES, Lucifer, FEAL, Khufu, Khafre, LOKI, GOST,
CAST, Blowfish, and others. Why is it such a big deal? The function is guaranteed
to be reversible. Because XOR is used to combine the left half with the output of the
round function, it is necessarily true that
Li - 1 0 f(R, - ,yKi) 0 f(Ri - 1pKi)= Li - 1
A cipher that uses this construction is guaranteed to be invertible as long as the
inputs to f in each round can be reconstructed. It doesn™t matter what f is; f need not
be invertible. We can design f to be as complicated as we please, and we don™t have
to implement two different algorithms-one for encryption and another for decryp-
tion. The structure of a Feistel network takes care of all this automatically.

Simple Relations
DES has the property that if E,(P) = C, then E,(P™) = C™, where P™, C™, and R are the
bit-wise complements of P, C, and K. This property reduces the complexity of a
Page 347
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter

CHAPTER14 Still Other Block Ciphers


brute-force attack by a factor of two. LOKI has complementation properties that
reduce the complexity of a brute-force attack by a factor of 256.
A simple relation can be defined as [857]:
If E,(P) = C, then Efi,, (g(F™,K))= h( C, K)
where f, g, and h are simple functions. By simple I mean that they are easy to com-
pute, much easier than an iteration of the block cipher. In DES, f is the bit-wise
complement of K, g is the bit-wise complement of P, and h is the bit-wise comple-
ment of C. This is a result of XORing the key into part of the text.
In a good block cipher, there are no simple relations. Methods for finding some of
these weaknesses are in [917].
Group Structure
When discussing an algorithm, the question of whether it is a group arises. The
elements of the group are the ciphertext blocks with each possible key, and the
group operation is composition. Looking at an algorithm™s group structure is an
attempt to get a handle on just how much extra scrambling happens under multiple
encryption.
The useful question is, however, not whether an algorithm is actually a group, but
just how close to a group it is. If it were only lacking one element, it wouldn™t be a
group; but double encryption would be-statistically speaking-a waste of time.
The work on DES showed that DES is very far away from being a group. There are
still some interesting questions about the semigroup that DES encryption generates.
Does it contain the identity: That is, does it even generate a group? To put it another
way, does some combination of encryption (not decryption) operations eventually
generate the identity function? If so, how long is the shortest such combination?
The goal is to estimate the size of the keyspace for a theoretical brute-force attack,
and the result is a greatest lower bound on the keyspace entropy.
Weak Keys
In a good block cipher, all keys are equally strong. Algorithms with a small num-
ber of weak keys, like DES, are generally no problem. The odds of picking one at ran-
dom are very small, and it™s easy to test for and discard them. However, these weak
keys can sometimes be exploited if the block cipher is used as a one-way hash func-
tion (see Section 18.11).
and Linear
Strength against Differential Cryptanalysis
The study of differential and linear cryptanalysis has shed significant light on the
theory of good block cipher design. The inventors of IDEA introduced the concept
of differentials, a generalization of the basic idea of characteristics [931]. They
argued that block ciphers can be designed to resist this attack; IDEA is the result of
that work [931]. This concept was further formalized in [ 1181,1182], when Kaisa
Nyberg and Lars Knudsen showed how to make block ciphers provably secure
against differential cryptanalysis. This theory has extensions to higher-order differ-
entials [702,161,927,858,860] and partial differentials [860]. Higher-order differen-
Page 348
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
14.10 Theory of Block Cipher Design


tials seem to apply only to ciphers with a small number of rounds, but partial dif-
ferentials combine nicely with differentials.
Linear cryptanalysis is newer, and is still being improved. Notions of key ranking
[1019] and multiple approximations [811,812] have been defined. Other work that
extends the idea of linear cryptanalysis can be found in [ 12701; [938] tries to combine
linear and differential cryptanalysis into one attack. It is unclear what design tech-
niques will protect against these sorts of attacks.
Knudsen has made some progress, considering some necessary (but not perhaps
sufficient) criteria for what he calls practically secure Feistel networks: ciphers that
resist both linear and differential cryptanalysis [857]. Nyberg introduced in linear
cryptanalysis an analogy to the concept of differentials from differential cryptanaly-
sis [1180].
Interestingly enough, there seems to be a duality between differential and linear
cryptanalysis. This duality becomes apparent both in the design of techniques to
construct good differential characteristics and linear approximations [ 164,1018], and
also in the design criteria for making algorithms that are secure against both attacks
[307]. Exactly where this line of research will lead is still unknown. As a start,
Daemen has developed an algorithm-design strategy based on linear and differential
cryptanalysis [402].
S-Box Design
The strength of various Feistel networks-and specifically their resistance to dif-
ferential and linear cryptanalysis-is tied directly to their S-boxes. This has
prompted a spate of research on what constitutes a good S-box.
An S-box is simply a substitution: a mapping of m-bit inputs to n-bit outputs. Pre-
viously I talked about one large lookup table of 64-bit inputs to 64-bit outputs; that
would be a 64*64-bit S-box. An S-box with an m-bit input and an n-bit output is
called a m*n-bit S-box. S-boxes are generally the only nonlinear step in an algo-
rithm; they are what give a block cipher its security. In general, the bigger they are,
the better.
DES has eight different 6*4-bit S-boxes. Khufu and Khafre have a single 8*32-bit
S-box, LOKI has a 12*8-bit S-box, and both Blowfish and CAST have 8*32-bit
S-boxes. In IDEA the modular multiplication step is effectively the S-box; it is a
16* 16-bit S-box. The larger this S-box, the harder it is to find useful statistics to
attack using either differential or linear cryptanalysis [653,729,1626]. Also, while
random S-boxes are usually not optimal to protect against differential and linear
attacks, it is easier to find strong S-boxes if the S-boxes are larger. Most random
S-boxes are nonlinear, nondegenerate, and have strong resistance to linear crypt-
analysis-and the fraction that does not goes down rapidly as the number of input
bits decreases [1185,1186,1187].
The size of m is more important than the size of n. Increasing the size of n
reduces the effectiveness of differential cryptanalysis, but greatly increases the
effectiveness of linear cryptanalysis. In fact, if n 2 2” - m, then there is definitely a
linear relation of the input and output bits of the S-box. And if n 2 2”, then there is
a linear relation of only the output bits [ 1641.
Page 349
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter

Still Other Block Ciphers
CHAPTER 14



Much of this work involves the study of Boolean functions [94,1098,1262,1408].
In order to be secure, the Boolean functions used in S-boxes must satisfy specific
conditions. They should not be linear or affine, nor even close to linear or affine
[9,1177,1178,1188]. There should be a balance of zeros and ones, and no correlations
between different combinations of bits. The output bits should behave indepen-
dently when any single input bit is complemented. These design criteria are also
related to the study of bent functions: functions which can be shown to be optimally
nonlinear. Although their definition is simple and natural, their study is very com-
plicated [1344,1216,947,905,1176,1271,295,296,297,149,349,471,298].
One property that seems very important is the avalanche effect: how many out-
put bits of an S-box change when some subset of the input bits are changed. It™s easy
to impose conditions on Boolean functions so that they satisfy certain avalanche cri-
teria, but constructing them is a harder task. The strict avalanche criteria (SAC)
guarantees that exactly half of the output bits change when one input bit changes
[1586]. See also [982,571,1262,399]. One paper attempts to look at all these criteria
in terms of information leakage [ 16401.
A few years ago cryptographers proposed choosing S-boxes so that the difference
distribution table for each S-box is uniform. This would provide immunity against
differential cryptanalysis by smoothing out the differentials in any particular round
[6,443,444,1177]. LOKI is an example of this design. However, this approach can
sometimes aid in differential cryptanalysis [ 1721.Actually, a better approach is mak-
ing sure that the maximum differential is as small as possible. Kwangjo Kim pro-
posed five criteria for the construction of S-boxes [834], similar to the design criteria
for the DES S-boxes.
Choosing good S-boxes is not an easy task; there are many competing ideas on
how to do it. Four general approaches can be identified.

1. Choose randomly. It is clear that small random S-boxes are insecure, but
large random S-boxes may be good enough. Random S-boxes with eight or
more inputs are quite strong [ 1186,1187]. Twelve-bit S-boxes are better.
Even more strength is added if the S-boxes are both random and key-
dependent. IDEA uses both large and key-dependent S-boxes.
2. Choose and test. Some ciphers generate random S-boxes and then test
them for the requisite properties. See [9,729] for examples of this approach.
3. Man-made. This technique uses little mathematics: S-boxes are generated
using more intuitive techniques. Bart Preneel stated that “. . . theoretically
interesting criteria are not sufficient [for choosing Boolean functions for
S-boxes] . . .” and that “. . . ad hoc design criteria are required” [ 12621.
4. Math-made. Generate S-boxes according to mathematical principles so
that they have proven security against differential and linear cryptanalysis,
and good diffusive properties. See [ 11791 for an excellent example of this
approach.

There has been some call for a combination of the “math-made” and “man-made”
approaches [1334], but the real debate seems to be between randomly chosen
Page 350
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter




S-boxes and S-boxes with certain properties. Certainly the latter approach has the
advantage of being optimal against known attacks-linear and differential crypt-
analysis-but it offers unknown protection against unknown attacks. The designers
of DES knew about differential cryptanalysis, and its S-boxes were optimized
against it. They did not seem to know about linear cryptanalysis, and the DES
S-boxes are very weak against it [ 10181.Randomly selected S-boxes in DES would be
weaker against differential cryptanalysis and stronger against linear cryptanalysis.
On the other hand, random S-boxes may not be optimal against these attacks, but
they can be made sufficiently large and therefore sufficiently resistant. Also, they
are more likely to be sufficiently resistant against unknown attacks. The debate is
still raging, but my personal feeling is that S-boxes should be as large as possible,
random, and key-dependent.
Designing a Block Cipher
It is easy to design a block cipher. If you think of a 64-bit block cipher as a per-
mutation of the 64-bit numbers, it is clear that almost all of those permutations are
secure. What is difficult is to design a block cipher that is not only secure, but can
also be easily described and simply implemented.
It™s easy to design a block cipher if you have sufficient memory for 48 *32 S-boxes.
It™s hard to design an insecure DES variant if you iterate it for 128 rounds. If the
length of your key is 5 12 bits, you really don™t care if there are key-complementation
properties.
The real trick-and the reason that real-world block cipher design is very diffi-
cult-is to design a block cipher with the smallest possible key, the smallest possi-
ble memory requirement, and the fastest possible running time.

14.11 USING ONE-WAY HASH FUNCTIONS
The simplest way to encrypt with a one-way function is to hash the previous cipher-
text block concatenated with the key, then XOR the result with the current plain-
text block:
Ci=Pi 0 H(K,Ci- 1)
Pi=Cj@H(K,Ci-1)
Set the block length equal to the output of the one-way hash function. This, in
effect uses the one-way function as a block cipher in CFB mode. A similar con-
struction can use the one-way function in OFB mode:
Ci=PiOSijSi=H(K,Ci-I)
P,=CiOsi;s,=H(K,Ci-1)
The security of this scheme depends on the security of the one-way function.
Karn
This method, invented by Phil Karn and placed in the public domain, makes an
invertible encryption algorithm out of certain one-way hash functions.
Page 351
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter

CHAPTER 14 Still Other Block Ciphers



The algorithm operates on plaintext and ciphertext in 32-byte blocks. The key can
be any length, although certain key lengths will be more efficient for certain one-
way hash functions. For the one-way hash functions MD4 and MD5, 96-byte keys
work best.
To encrypt, first split the plaintext into two 16-byte halves: P1and PI. Then, split
the key into two 4%byte halves: Kl and K,.
P = l+,Pr
K = K],K,
Append KI to PI and hash it with a one-way hash function, then XOR the result of
the hash with Pr to produce C,, the right half of the ciphertext. Then, append K, to
C, and hash it with the one-way hash function. XOR the result with PI to produce
Cl. Finally, append C, to Cl to produce the ciphertext.
C, = I: QJHh, KI)
CI = PI 0 H( C, K,)
c = C],C,
To decrypt, simply reverse the process. Append K, to C,, hash and XOR with CI to
produce P,. Append KI to PI, hash and XOR with C, to produce Pr.
PI = Cz @ H(C,,K,)
Pr = C, 0 fU3, KI)
P = P],Pr
The overall structure of Karn is the same as many of the other block algorithms
discussed in this section. It has only two rounds, because the complexity of the algo-
rithm is embedded in the one-way hash function. And since the key is used only as
the input to the hash function, it cannot be recovered even using a chosen-plaintext
attack-assuming, of course, that the one-way hash function is secure.
Lwby-Rackoff
Michael Luby and Charles Rackoff showed that Karn is not secure [992]. Consider
two single-block messages: AB and AC. If a cryptanalyst knows both the plaintext
and the ciphertext of the first message, and knows the first half of the plaintext of
the second message, then he can easily compute the entire second message. This
known-plaintext attack is useful only in certain circumstances, but it is a major
security problem.
A three-round encryption algorithm avoids this problem [992,1643,1644]. It uses
three different hash functions: Hi, H,, and H3. Further work shows that Hi can equal
Hz, or that H2 can equal H3, but not both [ 11931.Also, HI, Hz, and H3 cannot be based
on iterating the same basic function [ 16431. Anyway, assuming that H(k,x) behaves
like a pseudo-random function, here is a three-round version:

(1) Divide the key into two halves: KI and K,.
(2) Divide the plaintext block into two halves: Lo and RO.
Page 352
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter




(3) Append KI to Lo and hash it. XOR the result of the hash with R,, to pro-
duce RI:
RI = Ro 0 H(Kl,L,)
(4) Append K, to RI and hash it. XOR the result of the hash with Lo to pro-
duce L,:
LI = Lo 0 H(K,RII
(5) Append Kl to L1 and hash it. XOR the result of the hash with RI to pro-
duce R2:
Rz = RI 0 H(Kl,LJ
(6) Append L1 to Rz to generate the message.
Message Digest Cipher (MDC)
MDC, invented by Peter Gutmann [676], is a means of turning one-way hash
functions into a block cipher that runs in CFB mode. The cipher runs almost as fast
as the hash function and is at least as secure as the hash function. The rest of this
section assumes you are familiar with Chapter 18.
Hash functions such as MD5 and SHA use a 512-bit text block to transform an
input value (128 bits with MD5, and 160 bits with SHA) into an output value of
equal size. This transformation is not reversible, but it is perfect for CFB mode: The
same operation is used for both encryption and decryption.
Let™s look at MDC with SHA. MDC has a 160-bit block size and a 5 12-bit key. The
hash function is run “sideways,” with the old hash state as the input plaintext block
(160 bits) and the 512-bit hash input as a key (see Figure 14.5). Normally, when
using the hash to simply hash some input, the 512-bit input to the hash is varied as
each new 512bit block is hashed. But in this case the 512-bit input becomes an
unchanging key.
MDC can be used with any one-way hash function: MD4, MD5, Snefru, and oth-
ers. It is unpatented. Anyone can use it at any time, in any way, royalty-free [676].
However, I don™t trust this construction. It is possible to attack the hash function
in a way that hash functions are not designed to withstand. It is not important for
hash functions to be able to resist a chosen-plaintext attack, where a cryptanalyst
chooses several of those starting 160-bit values, has them “encrypted” by the same
512bit “key,” and uses this to learn some information about the 512-bit key used.
Since the designers didn™t have to worry about this, it seems like a bad idea to count
on your cipher being able to resist this attack.
of Ciphers Based on One-Way Hash Functions
Security
While these constructions can be secure, they depend on the choice of the under-
lying one-way hash function. A good one-way hash function doesn™t necessarily
make a secure encryption algorithm. Cryptographic requirements are different. For
example, linear cryptanalysis is not a viable attack against one-way hash functions,
but works against encryption algorithms. A one-way hash function such as SHA
could have linear characteristics which, while not affecting its security as a one-
Page 353
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter
14 Still Other Block Ciphers
CHAPTER



Message
Block Key



output
input Hash
Value
Value Function
-IA-


b Ciphertext
(b) Hash Function as a Block
(a) Hash Function
Cipher in CFB


Figure 14.5 Message Digest Cipher (MDC).


way hash function, could make it insecure in an encryption algorithm such as
MDC. I know of no cryptanalytic analysis of particular one-way hash functions as
block ciphers; wait for such analysis before you trust any of them.


14.12 CHOOSINGABLOCKALGORITHM
It™s a tough decision. DES is almost certainly insecure against the major governments
of the world unless you only encrypt very small chunks of data for a single key. It™s
probably all right against anyone else, but that is changing soon. Brute-force DES key
search machines will quickly become economical for all sorts of organizations.
Biham™s key-dependent S-boxes for DES should be secure for at least a few years
against all but the most well-funded adversaries, and possibly even from them. If
you need security that lasts decades or fear the cryptanalytic efforts of major gov-
ernments, use triple-DES with three independent keys.
The other algorithms aren™t worthless. I like Blowfish because it is fast and I wrote
it. 3-WAY looks good, and GOST is probably okay. The problem with any recom-
mendation is that the NSA almost certainly has an array of impressive cryptanalytic
techniques that are still classified, and I don™t know which algorithms they can break
with them. Table 14.3 gives timing measurements for some algorithms. These are
meant for comparison purposes only.
My favorite algorithm is IDEA. Its 12%bit key, combined with its resistance to
any public means of cryptanalysis, gives me a warm, fuzzy feeling about the algo-
rithm. The algorithm has been analyzed by a lot of different groups, and no serious
results have been announced yet. Barring extraordinary cryptanalytic news tomor-
row, I am betting on IDEA today.
Page 354
Prev. Chapter Home Previous Page
Next Page
Prev. page
Next Page Next Chapter

14.12 Choosing a Block Algorithm


Table 14.3
Encryption Speeds of Some Block Ciphers on a 33 MHz 486SX
Encryption Speed Encryption Speed
Algorithm (Kilobytes/second) Algorithm (Kilobytes/second)
Blowfish (12 rounds) 182 MDC (using MD4) 186
Blowfish (16 rounds) 13.5 MDC (using MD5) 135
Blowfish (20 rounds) 110 MDC (using SHA) 23
DES 35 NewDES 233
FEAL-8 300 REDOC II 1
FEAL- 16 161 REDOC III 78
FEAL-32 91 RC5-32/8 127
GOST 53 RC5-32/12 86
IDEA 70 RC5-32/16 65
Khufu (16 rounds) 221 RC5-32120 52
Khufu (24 rounds) 153 SAFER (6 rounds) 81
Khufu (32 rounds) 115 SAFER (8 rounds) 61
Luby-Rackoff (using MD4) 47 SAFER (10 rounds) 49
Luby-Rackoff (using MD5) 34 SAFER ( 12 rounds) 41
Luby-Rackoff (using SHA) 11 a-Way 25
Lucifer 52 Triple-DES 12