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