ńňđ. 1 |

Next Page

Prev. page

Next Page Next Chapter

CHAPTER 13 ................................................ 302

Other Block Ciphers ................................... 302

LUCIFER .................................................. 302

Description of Madryga ................................. 304

Figure 13.1 One iteration of Madryga. ........... 304

MAJDRYGA ............................................. 305

Figure 13.2 NewDES. .................................... 306

Cryptanalysis of Madryga .............................. 307

NEWDES .................................................. 307

Figure 13.4 Function f. ................................... 308

FEAL ......................................................... 309

Description FEAL .......................................... 309

Figure 13.3 One round of FEAL. .................... 309

Cryptanalysis of FEAL .................................... 310

Patents ........................................................... 310

REDOC ..................................................... 310

Figure 13.7 FEAL-NX key schedule. .............. 311

REDOC III ...................................................... 312

Patents and Licenses .................................... 312

LOKI .......................................................... 313

LOKZ91 ......................................................... 313

Description LOK191 ...................................... 313

Figure 13.8 LOKI91. ....................................... 314

Table 13.1 Expansion Permutation .............. 314

Table 13.2 P, ................................................ 315

Cryptanalysis LOK191 .................................. 315

Patents and Licenses .................................... 315

KHUFU AND KHAFRE .............................. 315

Table 13.3 P-Box Permutation ..................... 315

Khufu ............................................................. 316

Khafre ............................................................ 316

Patents .......................................................... 317

RC2 ........................................................... 317

IDEA .......................................................... 318

Oueruiew ....................................................... 319

Description IDEA ........................................... 319

Figure 13.9 IDEA. ........................................... 320

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

Speed IDEA .................................................. 321

Table 13.4 IDEA Encryption and ................... 321

Cryptanalysis IDEA ....................................... 322

IDEA Modes Operation and Variants ............ 322

Figure 13.10 PES. .......................................... 323

Caveat Emptor .............................................. 324

Patents and Licenses .................................... 324

MMB .......................................................... 324

Security MMB ................................................ 325

CA-1.1 ....................................................... 326

SKIPJACK ................................................ 327

Page 302

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

13

CHAPTER

Other Block Ciphers

13.1 LUCIFER

In the late 1960s led by Horst Feistel and later by Walt Tuchman, IBM initiated a

research program in computer cryptography called Lucifer. Lucifer is also the name

of a block algorithm that came out of that program in the early 1970s [1482,1484].

In fact, there are at least two different algorithms with that name [552,1492]. And

[552] leaves some gaps in the specification of the algorithm. All this has led to more

than a little confusion.

Lucifer is a substitution-permutation network, with building blocks similar to

DES. In DES, the output of the function f is XORed with the input of the previous

round to form the input of the next round. Luciferâ€™s S-boxes have 4bit inputs and

4-bit outputs; the input of the S-boxes is the bit-permuted output of the S-boxes of

the previous round; the input of the S-boxes of the first round is the plaintext. A key

bit is used to choose the actual S-box from two possible S-boxes. (Lucifer represents

this as a single T-box with 9 bits in and 8 bits out.) Unlike DES, there is no swapping

between rounds and no block halves are used. Lucifer has 16 rounds, 128-bit blocks,

and a key schedule simpler than DES.

Using differential cryptanalysis against the first incarnation of Lucifer, Biham and

Shamir [170,172] sh owed that Lucifer, with 32-bit blocks and 8 rounds, can be bro-

ken with 40 chosen plaintexts and 229steps; the same attack can break Lucifer with

128-bit blocks and 8 rounds with 60 chosen plaintexts and 253steps. Another differ-

ential cryptanalytic attack breaks 18-round, 128-bit Lucifer with 24 chosen plain-

texts in 2â€™l steps. All of these attacks used the strong DES S-boxes. Using differential

cryptanalysis against the second incarnation, they found the S-boxes to be much

weaker than DES. Further analysis showed that over half the possible keys are inse-

cure [lI2]. Related-key cryptanalysis can break 128-bit Lucifer, with any number of

rounds, with 233chosen-key chosen plaintexts, or with 265chosen-key known plain-

texts [ 1581. The second incarnation of Lucifer is even weaker [ 170,172,112].

Page 303

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

Page 304

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

variable-length key would surely silence those who thought 56 bits was too low.

They could implement this algorithm with any key length they desired. And, for

anyone who has ever attempted to implement DES in software, an algorithm that

took software implementations into account would be welcomed.

Description of Madryga

Madryga consists of two nested cycles. The outer cycle repeats eight times

(although this could be increased if security warrants) and consists of an applica-

tion of the inner cycle to the plaintext. The inner cycle transforms plaintext to

ciphertext and repeats once for each 8-bit block (byte) of the plaintext. Thus, the

algorithm passes through the entire plaintext eight successive times.

An iteration of the inner cycle operates on a 3-byte window of data, called the

working frame (see Figure 13.1). This window advances 1 byte for each iteration.

(The data are considered circular when dealing with the last 2 bytes.) The first 2

bytes of the working frame are together rotated a variable number of positions,

while the last byte is XORed with some key bits. As the working frame advances,

all bytes are successively rotated and XORed with key material. Successive rota-

tions overlap the results of a previous XOR and rotation, and data from the XOR is

used to influence the rotation. This makes the entire process reversible.

Because every byte of data influences the 2 bytes to its left and the 1 byte to its

right, after eight passes every byte of the ciphertext is dependent on 16 bytes to the

left and 8 bytes to the right.

When encrypting, each iteration of the inner cycle starts the working frame at the

next-to-last byte of the plaintext and advances circularly through to the third-to-last

Text 1 2 3 4 5 6 ... TL-2 TL-1 TL

--

Movi?g

â€˜$g&k

pay

Transposition â€˜* wi

16 bits 3 bits

Translation

\ XOR /.

Key KL

123 ...

XOR

KL

123 ...

Key Hash

Figure 13.1 One iteration of Madryga.

Page 305

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

13 Other Block Ciphers

CHAPTER

Some people feel that Lucifer is more secure than DES because of the longer key

length and lack of published results. This is clearly not the case.

Lucifer is the subject of several U.S. patents: [553,554,555,1483]. They have all

expired.

13.2 MAJDRYGA

W. E. Madryga proposed this block algorithm in 1984 [999]. It is efficient for soft-

ware: It has no irritating permutations and all its operations work on bytes.

His design objectives are worth repeating:

1. The plaintext cannot be derived from the ciphertext without using the key.

(This just means that the algorithm is secure.)

2. The number of operations required to determine the key from a sample of

plaintext and ciphertext should be statistically equal to the product of the

operations in an encryption times the number of possible keys. (This

means that no plaintext attack should be better than brute force.)

3. Knowledge of the algorithm should not defeat the strength of the cipher.

(All the security should rest in the key.)

4. A one-bit change of the key should produce a radical change in the cipher-

text using the same plaintext, and a l-bit change of the plaintext should

produce a radical change in the ciphertext using the same key. (This is the

avalanche effect.)

5. The algorithm should contain a noncommutative combination of substi-

tution and permutation.

6. The algorithm should include substitutions and permutations under the

control of both the input data and the key.

7. Redundant bit groups in the plaintext should be totally obscured in the

ciphertext.

8. The length of the ciphertext should be the same length as the plaintext.

9. There should be no simple relationships between any possible keys and

ciphertext effects.

10. Any possible key should produce a strong cipher. (There should be no

weak keys.)

11. The length of the key and the text should be adjustable to meet varying

security requirements.

12. The algorithm should be efficiently implementable in software on large

mainframes, minicomputers, and microcomputers, and in discrete logic.

(In fact, the functions used in the algorithm are limited to XOR and bit-

shifting.)

DES had already met objectives one through nine, but the next three were new.

Assuming that the best way to break the algorithm was through brute force, a

Page 306

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

13.3 NewDES

substituted with another byte via an f function, and then XORed with another sub-

block to become that sub-block. The 120-bit key is divided into 15 key sub-blocks:

Ko, K,, . . . , K13, K14. The process is easier to understand visually than to describe.

Figure 13.2 shows the NewDES encryption algorithm.

The f-function is derived from the Declaration of Independence. See [1405] for

details.

Scott showed that every bit of the plaintext block affects every bit of the cipher-

text block after only 7 rounds. He also analyzed the f function and found no obvious

problems. NewDES has the same complementation property that DES has [364]: If

Bo BI 82 83 B4 85 86 87

Round

K2

K3

I

Round 2

â€™ K4

I

H I

(Rounds 3-l 5)

K9

KIO

Round 17

KI I

K12

Kl3

Kl4

BO BI 6-2 83 84 B5 86 87

Figure 13.2 NewDES.

Page 307

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

13 Other Block Ciphers

CHAPTER

byte of the plaintext. First, the entire key is XORed with a random constant and

then rotated to the left 3 bits. The low-order 3 bits of the low-order byte of the work-

ing frame are saved; they will control the rotation of the other 2 bytes. Then, the

low-order byte of the working frame is XORed with the low-order byte of the key.

Next, the concatenation of the 2 high-order bytes are rotated to the left the variable

number of bits (0 to 7). Finally, the working frame is shifted to the right 1 byte and

the whole process repeats.

The point of the random constant is to turn the key into a pseudo-random

sequence. The length of this constant must be equal to the length of the key and

must be the same for everyone who wishes to communicate with one another. For

a 64-bit key, Madryga recommends the constant OxOfle2d3c4b5a6978.

Decryption reverses this process. Each iteration of the inner cycle starts the work-

ing frame at the third-to-last byte of the ciphertext and advances in the reverse

direction circularly through to the second-to-last byte of the ciphertext. Both the

key and the 2 ciphertext bytes are shifted to the right. And the XOR is done before

the rotations.

Cryptanalysis of Madryga

Researchers at Queensland University of Technology [675] examined Madryga,

along with several other block ciphers. They observed that the algorithm didnâ€™t

exhibit the plaintext-ciphertext avalanche effect. Additionally, many ciphertexts

had a higher percentage of ones than zeros.

Although I know of no formal analysis of the algorithm, it doesnâ€™t look terribly

secure. A cursory review by Eli Biham led to the following observations [ 1601:

The algorithm consists only of linear operations (rotations and XOR), which are

slightly modified depending on the data.

There is nothing like the strength of DESâ€™s S-boxes.

The parity of all the bits of the plaintext and the ciphertext is a constant,

depending only on the key. So, if you have one plaintext and its corresponding

ciphertext, you can predict the parity of the ciphertext for any plaintext.

None of this is damning in itself, but it doesnâ€™t leave me with a good feeling about

the algorithm. I do not recommend Madryga.

13.3 NEwDES

NewDES was designed in 1985 by Robert Scott as a possible DES replacement

[ 1405,364]. The algorithm is not a DES variant, as its name might imply. It operates

on 64-bit blocks of plaintext, but it has a 120-bit key. NewDES is simpler than DES,

with no initial or final permutations. All operations are on entire bytes. (Actually,

NewDES isnâ€™t anything like a new version of DES; the name is unfortunate.)

The plaintext block is divided into eight l-byte sub-blocks: Bo, B1, . . . , B6, B,.

Then the sub-blocks go through 17 rounds. Each round has eight steps. In each step,

one of the sub-blocks is XORed with some key material (there is one exception),

Page 308

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

13.4 FEAL

data block is then split into a left half and a right half. The left half is XORed with

the right half to form a new right half. The left and new right halves go through n

rounds (four, initially). In each round the right half is combined with 16 bits of key

material (using function f) and XORed with the left half to form the new right half.

The original right half (before the round) forms the new left half. After n rounds

(remember not to switch the left and right halves after the nth round] the left half is

again XORed with the right half to form a new right half, and then the left and right

halves are concatenated together to form a 64-bit whole. The data block is XORed

with another 64 bits of key material, and the algorithm terminates.

Function f takes the 32 bits of data and 16 bits of key material and mixes them

together. First the data block is broken up into g-bit chunks, then the chunks are

XORed and substituted with each other. Figure 13.4 is a block diagram of function f.

The two functions Soand S1,are defined as:

S,(a,b) = rotate left two bits ((a + b) mod 256)

S,(a,b) = rotate left two bits ((a + b + 1) mod 256)

The same algorithm can be used for decryption. The only difference is: When

decrypting, the key material must be used in the reverse order.

Figure 13.5 is a block diagram of the key-generating function. First the 64-bit key

is divided into two halves. The halves are XORed and operated on by function Q as

indicated in the diagram. Figure 13.6 is a block diagram of function fk. The two 32-

bit inputs are broken up into &bit blocks and combined and substituted as shown.

So and S1 are defined as just shown. The 16-bit key blocks are then used in the

encryption/decryption algorithm.

On a 10 megahertz 80286 microprocessor, an assembly-language implementation

of FEAL-32 can encrypt data at a speed of 220 kilobits per second. FEAL-64 can

encrypt data at a speed of 120 kilobits per second [1104].

a3

f.

Figure 13.4 Function

Page 309

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

13 Other Block Ciphers

CHAPTER

E,(P) = C, then &(Pâ€™) = câ€™. This reduces the work required for a brute-force attack

from 21zo steps to 2119

steps. Biham noticed that any change of a full byte, applied to

all the key and data bytes, leads to another complementation property [160]. This

reduces a brute-force attack further to 2â€™12 steps.

This is not damning, but Bihamâ€™s related-key cryptanalytic attack can break

NewDES with 233 chosen-key chosen-plaintexts in 248 steps (1601. While this

attack is time-consuming and largely theoretical, it shows that NewDES is weaker

than DES.

13.4 FEAL

FEAL was designed by Akihiro Shimizu and Shoji Miyaguchi from NTT Japan

[ 14351.It uses a 64-bit block and a 64-bit key. The idea was to make a DES-like algo-

rithm with a stronger round function. Needing fewer rounds, the algorithm would

run faster. Unfortunately, reality fell far short of the design goals.

of FEAL

Description

Figure 13.3 is a block diagram of one round of FEAL. The encryption process starts

with a 64-bit block of plaintext. First, the data block is XORed with 64 key bits. The

( Plaintext -I

\

â€™ (K8, K9, KlO, Kll)

64 bits

((K12, K13, K14, K15))

64 bits

32 bits (32 bits

(K12, K13, K14, K15)

((K8, K9, KlO, Kll)}

0: Deciphering

Ciphertext

c-

Figure 13.3 One round of FEAL.

Page 310

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

13.5 REDOC

of FEAL

Cryptanalysis

FEAL-4, FEAL with four rounds, was successfully cryptanalyzed with a chosen-

plaintext attack in [ZOl] and later demolished in [ 11321. This latter attack, by Sean

Murphy, was the first published differential-cryptanalysis attack and required only

20 chosen plaintexts. The designers retaliated with 8-round FEAL [ 1436,1437,1108]

which Biham and Shamir cryptanalyzed at the SECURICOM â€˜89 conference [ 14241.

Another chosen-plaintext attack, using only 10,000 blocks, against FEAL-8 [610]

forced the designers to throw up their hands and define FEAL-N [ 1102,1104], with a

variable number of rounds (greater than 8, of course).

Biham and Shamir used differential cryptanalysis against FEAL-N; they could break

it more quickly than by brute force (with fewer than 2h4chosen plaintext encryptions)

for N less than 32 (1691. FEAL-16 required 228chosen plaintexts or 246.5 known plain-

texts to break. FEAL-8 required 2000 chosen plaintexts or 237.5 known plaintexts to

break. FEAL-4 could be broken with just eight carefully selected chosen plaintexts.

The FEAL designers also defined FEAL-NX, a modification of FEAL, that accepts

128-bit keys (see Figure 13.7) [ 1103,1104]. Biham and Shamir showed that FEAL-NX

with a 128-bit key is just as easy to break as FEAL-N with a 64-bit key, for any value

of N [ 1691. Recently FEAL-N(X)S has been proposed, which strengthens FEAL with

a dynamic swapping function [ 15251.

Thereâ€™s more. Another attack against FEAL-4, requiring only 1000 known plain-

texts, and against FEAL-8, requiring only 20,000 known plaintexts, was published in

[ 15201. Other attacks are in [ 1549,1550]. The best attack is by Mitsuru Matsui and

Atshuiro Yamagishi [ 10201.This is the first use of linear cryptanalysis, and can break

FEAL-4 with 5 known plaintexts, FEAL-6 with 100 known plaintexts and FEAL-8

with 215known plaintexts. Further refinements are in [64]. Differential-linear crypt-

analysis can break FEAL-8 with only 12 chosen plaintexts 162).Whenever someone

discovers a new cryptanalytic attack, he always seems to try it out on FEAL first.

Patents

FEAL is patented in the United States [ 14381and has patents pending in England,

France, and Germany. Anyone wishing to license the algorithm should contact the

Intellectual Property Department, NTT, l-6 Uchisaiwai-cho, 1-chome, Chiyoda-ku,

100 Japan.

13.5 REDOC

REDOC II is another block algorithm, designed by Michael Wood for Cryptech, Inc.

[ 1613,400]. It has a 20-byte (160-bit) key and an 80-bit block.

REDOC II performs all of its manipulations-permutations, substitutions, and

key XORs-on bytes; the algorithm is efficient in software. REDOC II uses variable

function tables. Unlike DES, which has a fixed (albeit optimized for security) set of

permutation and substitution tables, REDOC II uses a key-dependent and plaintext-

dependent set of tables (S-boxes, actually). REDOC II has 10 rounds; each round is a

complicated series of manipulations on the block.

Page 311

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

13 Other Block Ciphers

CHAPTER

KeyBlock IKR:128

(KL bits)

,32bits K˜i-3

L

(Kg. KI)

*I +

Q2

Wâ€˜

fK

1r

(K2.Kg *

(KN+˜, KN+˜) *

Wâ€˜ 32 bits i--da v I I

â€śRI -â€˜W2 I I

(KN+˜. KN+T) 4

KRI Km

K2(,. 1): left half of Br (16 bits) Qr=KR˜@Km. r=l.4.7 ,...

Kz(˜.t j+ t : right half of Br (16 bits)

Numberofiterationsis (N/2)+4

Figure 13.7 FEAL-NX key schedule.

Another unique feature in the design is the use of masks. These are numbers

derived from the key table that are used to select the tables in a given function

within a given round. Both the value of the data and the masks are used together to

select the function tables.

Assuming that brute force is the most efficient means of attack, REDOC II is very

secure: 2lâ€ťO operations are required to recover the key. Thomas Cusick cryptana-

lyzed 1 round of REDOC II, but he was unable to extend the attack to multiple

rounds [400]. Using differential cryptanalysis, Biham and Shamir were able to suc-

Page 312

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

13.5 REDOC

cessfully cryptanalyze 1 round of REDOC II with 2300 chosen-plaintexts [ 170). This

attack cannot be extended to multiple rounds, but they were able to obtain three

mask values after 4 rounds. I know of no other cryptanalysis.

REDOC 111

REDOC III is a streamlined version of REDOC II, also designed by Michael Wood

[ 16151. It operates on an go-bit block. The key length is variable and can be as large

as 2560 bytes (20,480 bits). The algorithm consists solely of XORing key bytes with

message bytes; there are no permutations or substitutions.

(1) Create a key table of 256 lo-byte keys, using the secret key.

(2) Create two lo-byte mask blocks, Ml and M2. Ml is the XOR of the first 128

IO-byte keys; M2 is the XOR of the second 128 lo-byte keys.

(3) To encrypt a lo-byte block:

(a) XOR the first byte of the data block with the first byte of Ml. Select a

key from the key table computed in step (1). Use the computed XOR

as the index into the table. XOR each byte in the data block with the

corresponding byte in the chosen key, except for the first data byte.

(b) XOR the second byte of the data block with the second byte of Ml.

Select a key from the key table computed in step (1). Use the computed

XOR as the index into the table. XOR each byte in the data block with

the corresponding byte in the chosen key, except for the second data

byte.

(c) Continue with the entire block (bytes 3 through lo), until each byte

has been used to select a key from the key table after XORing it with

the corresponding Ml value. Then XOR each byte with the key except

for the byte used to select the key.

(d) Repeat steps (a) through (c) with M2.

The algorithm is easy and fast. On a 33 megahertz 80386, the algorithm encrypts

data at 2.75 megabits per second. Wood estimates that a VLSI-pipelined design, with

a 64-bit data path, woud encrypt data at over 1.28 gigabits per second with a 20

megahertz clock.

REDOC III is not secure [1440]. It is vulnerable to differential cryptanalysis. Only

about 223chosen plaintexts are required to reconstruct both masks.

Pa tents and Licenses

Both REDOC versions are patented in the United States [1614]. Foreign patents

are pending. Anyone interested in licensing either REDOC II or REDOC III should

contact Michael C. Wood, Delta Computec, Inc., 6647 Old Thompson Rd., Syra-

cuse, NY 13211.

Page 313

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CHAPTER13 Other Block Ciphers

13.6 LOKI

LOKI is Australian and was first presented in 1990 as a potential alternative to DES

[273]. It uses a 64-bit block and a 64-bit key. The general structure of the algorithm

and key schedule were based on [274,275], and the design of the S-boxes was based

on [ 12471.

Using differential cryptanalysis, Biham and Shamir were able to break LOKI with

11 or fewer rounds faster than by brute force [ 1701. Furthermore, there is an g-bit

complementation property, which reduces the complexity of a brute-force attack by

a factor of 256 [170,916,917].

Lars Knudsen showed that LOKI, with 14 rounds or fewer, is vulnerable to dif-

ferential cryptanalysis [852,853]. Additionally, if LOKI is implemented with alter-

nate S-boxes, the resulting cipher will probably be vulnerable to differential

cryptanalysis.

LOKZ91

In response to these attacks, LOKIâ€™s designers went back to the drawing board and

revised their algorithm. The result is LOK191 [272]. (The previous version of LOKI

was renamed LOK189.)

To make the algorithm more resistant to differential cryptanalysis and to remove

the complementation property, the following changes were made to the original

design:

1. The subkey generation algorithm was changed so that the halves were

swapped every second round, not every round.

2. The subkey generation algorithm was changed so that the rotation of the

left subkey alternated between 12 and 13 bits to the left.

3. The initial and final XOR of the block with the key were eliminated.

4. The S-box function was altered to flatten out their XOR profile (to improve

their resistance to differential cryptanalysis), and to eliminate any value of

x such that f(x) = 0, where f is the combination of the E-, S-, and P-boxes.

of LOK191

Description

The mechanics of LOK191 are similar to DES (see Figure 13.8). The data block is

then divided into a left half and a right half and goes through 16 rounds, much like

DES. In each round, the right half is first XORed with a piece of the key, then sent

through an expansion permutation (see Table 13.1).

The 48-bit output is divided into four 12-bit blocks, and each block is sent through

an S-box substitution. The S-box substitution is as follows: Take each 12-bit input;

use the 2 left-most bits and the 2 right-most bits to form the number r, and the 8

innermost bits and form the number c. The output of the S-box, 0, is as follows:

O(w) = (c + ((r* 17) 0 Oxff) & Oxff)â€śâ€™ mod lJ1

Page 314

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

13.6 LOKI

I Ciphertext

Figure 13.8 LOKI91.

PI is given in Table 13.2.

Then, the four 8-bit outputs are recombined to form a single 3%bit number and

sent through the permutation described in Table 13.3. Finally, the right half is

XORed with the left half to become the new left half, and the left half becomes the

new right half. After 16 rounds, the block is again XORed with the key to produce

the ciphertext.

The subkeys are generated from the key in a straightforward manner. The 64-bit

key is split into a left half and a right half. In each round, the subkey is the left half.

This left half is then rotated 12 or 13 bits to the left, and then every two rounds the

left and right halves are exchanged. As with DES, the same algorithm can be used for

both encryption and decryption, with some modification in how the subkeys are used.

Table 13.1

Expansion Permutation

4, 3, 2, 1, 32, 31, 20, 29, 28, 27, 26, 25,

28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17,

20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9,

12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1

Page 315

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

13 Other Block Ciphers

CHAPTER

Table 13.2

P,

1, 8, 9, 10, 11, 12, 13, 14, 15, 16

2, 3, 4, 5, 6, 7,

I:

Iâ€™,: 375, 379, 391, 395, 397, 415, 419, 425, 433, 445, 451, 463, 471, 477, 487, 499

of LOK191

Cryptanalysis

Knudsen attempted to cryptanalyze LOK191 [854,858], but found it secure against

differential cryptanalysis. However, he found a related-key chosen-plaintext attack

that reduces the complexity of a brute-force search by almost a factor of four. This

attack exploits a weakness in the key schedule and may also apply if the algorithm

is used as a one-way hash function (see Section 18.11).

Another attack on related keys can break LOK191 with 232 chosen-key chosen

plaintexts, or 248chosen-key known plaintexts [158]. The attack is independent of

the number of rounds of the algorithm. (In the same paper, Biham breaks LOK189

with 217 chosen-key chosen plaintexts or 233 known-key known plaintexts using

related-key cryptanalysis.) Itâ€™s easy to make LOK191 resistant to this attack; avoid

the simple key schedule.

Patents and Licenses

LOKI is not patented. Anyone can implement the algorithm and use it. The

source code implementation in this book is copyrighted by the University of New

South Wales. Anyone interested in using this implementation (or their other imple-

mentation, which is several orders of magnitude faster) in a commercial product

should contact Director CITRAD, Department of Computer Science, University

College, UNSW, Australian Defense Force Academy, Canberra ACT 2600, Aus-

tralia; FAX: +61 6 268 858 1.

13.7 KHAFRE

KHUFU AND

In 1990 Ralph Merkle proposed two algorithms. The basic design principles behind

them are [ 10711:

1. DESâ€™s 56-bit key size is too small. Considering the negligible cost of increas-

ing the key size (computer memory is cheap and plentiful), it should be

increased.

2. DESâ€™s extensive use of permutations, while suitable for hardware imple-

mentations, is very difficult to implement in software. The faster software

Table 13.3

P-Box Permutation

29, 21, 13, 5,

30, 22, 14, 6,

31, 23, 15, 7,

32, 24, 16, 8,

25, 17, 9, 1

26, 18, 10, 2,

27, 19, 11, 3,

2% 20, 12, 4,

Page 316

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

implementations of DES implement the permutations by table lookup.

Table lookup can provide the same â€śdiffusionâ€ť characteristics as permuta-

tion and can be much more flexible.

3. The S-boxes in DES are small, with only 64 4-bit entries per box. Now that

memory is larger, S-boxes should grow. Moreover, all eight S-boxes are

used simultaneously. While this is suitable for hardware, it seems like an

unreasonable restriction in software. A larger S-box size and sequential

(rather than parallel) S-box usage should be employed.

4. The initial and final permutations in DES are widely viewed as crypto-

graphically pointless and should be discarded.

5. All the faster implementations of DES precompute the keys for each

round. Given this fact, there is no reason not to make this computation

more complicated.

6. Unlike DES, the S-box design criteria should be public.

To this list, Merkle would probably now add â€śresistant to differential cryptanaly-

sis and to linear attacks,â€ť but those attacks were still unknown at the time.

Khufu

Khufu is a 64-bit block cipher. The 64-bit plaintext is first divided into two 32-bit

halves, L and R. First, both halves are XORed with some key material. Then, they

are subjected to a series of rounds similar to DES. In each round, the least significant

byte of L is used as the input to an S-box. Each S-box has 8 input bits and 32 output

bits. The selected 32-bit entry in the S-box is then XORed with R. L is then rotated

some multiple of 8 bits, L and R are swapped, and the round ends. The S-box itself

is not static, but changes every 8 rounds. Finally, after the last round, L and R are

XORed with more key material, and then combined to form the ciphertext block.

Although parts of the key are XORed with the encryption block at the beginning

and end of the algorithm, the primary purpose of the key is to generate the S-boxes.

These S-boxes are secret and, in essence, part of the key. Khufu calls for a total key

size of 5 12 bits (64 bytes) and gives an algorithm for generating S-boxes from the key.

The number of rounds for the algorithm is left open. Merkle mentioned that 8-round

Khufu is susceptible to a chosen-plaintext attack and recommended 16, 24, or 32

rounds [1071]. (He restricted the choice of rounds to a multiple of eight.)

Because Khufu has key-dependent and secret S-boxes, it is resistant to differential

cryptanalysis. There is a differential attack against 16-round Khufu that recovers the

key after 231chosen plaintexts [611], but it cannot be extended to more rounds. If

brute-force is the best way to attack Khufu, it is impressively secure. A 512-bit key

gives a complexity of 2512 -inconceivable under any circumstances.

Khafre

Khafre is the second of two cryptosystems proposed by Merkle [1071]. (Khufu and

Khafre are names of Egyptian pharaohs.) It is similar in design to Khufu, except that

it was designed for applications without precomputation time. The S-boxes are not

Page 317

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

13 Other Block Ciphers

CHAPTER

key-dependent. Instead, Khafre uses fixed S-boxes. And the key is XORed with the

encryption block not only before the first round and after the last round, but also

after every 8 rounds of encryption.

Merkle speculated that key sizes of 64- or 128-bits would be used for Khafre and

that more rounds of encryption would be required for Khafre than for Khufu. This,

combined with the fact that each round of Khafre is more complex than for Khufu,

makes Khafre slower. In compensation, Khafre does not require any precomputation

and will encrypt small amounts of data more quickly.

In 1990 Biham and Shamir turned their differential cryptanalysis techniques

against Khafre [170]. They were able to break 16-round Khafre with a chosen-

plaintext attack using about 1500 different encryptions. It took about an hour, using

their personal computer. Converting that to a known-plaintext attack would require

about 238encryptions. Khafre with 24 rounds can be broken by a chosen-plaintext

attack using 253encryptions, and a known-plaintext attack using 259encryptions.

Patents

Both Khufu and Khafre are patented [1072]. Source code for the algorithms are

in the patent. Anyone interested in licensing either or both algorithms should con-

tact Director of Licensing, Xerox Corporation, P.O. Box 1600, Stamford, CT,

06904-1600.

13.8 RC2

RC2 is a variable-key-size encryption algorithm designed by Ron Rivest for RSA

Data Security, Inc. (RSADSI). Apparently, â€śRCâ€ť stands for â€śRonâ€™s Code,â€ť although

it officially stands for â€śRivest Cipher.â€ť (RC3 was broken at RSADSI during devel-

opment; RCl never got further than Rivestâ€™s notebook.) It is proprietary, and its

details have not been published. Donâ€™t think for a minute that this helps security.

RC2 has already appeared in commercial products. As far as I know, RC2 has not

been patented and is only protected as a trade secret.

RC2 is a variable-key-size 64-bit block cipher, designed to be a replacement for

DES. According to the company, software implementations of RC2 are three times

faster than DES. The algorithm accepts a variable-length key, from 0 bytes to the

maximum string length the computer system supports; encryption speed is inde-

pendent of key size. This key is preprocessed to yield a key-dependent table of 128

bytes. So the number of effectively different keys is 21Â°z4.

RC2 has no S-boxes [805];

the two operations are â€śmixâ€ť and â€śmash,â€ť and one is chosen in each round. Accord-

ing to their literature [ 13341:

RC2 is not an iterative block cipher. This suggests that RC2 offers more pro-

tection against differential and linear cryptanalysis than other block ciphers

which have relied for their security on copying the design of DES.

RSADSIâ€™s refusal to make RC2 public casts doubt on their claims. They are will-

ing to provide details of the algorithm to most anyone willing to sign a nondisclo-

Page 318

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

13.9 IDEA

sure agreement, and have claimed to allow cryptanalysts to publish any negative

results they find. I donâ€™t know of any cryptanalyst outside the employ of the com-

pany who studied it, since it would amount to doing their analysis work for them.

Still, Ron Rivest is not the usual snake-oil peddler. Heâ€™s a respected and compe-

tent cryptographer. I would put a fair degree of trust in the algorithm, even though I

havenâ€™t personally inspected the code. RC4, once the proprietary intellectual prop-

erty of RSADSI, was posted to the Internet (see Section 17.1), and itâ€™s probably just

a matter of time before RC2 is posted as well.

An agreement between the Software Publishers Association (SPA) and the U.S.

government gave RC2 and RC4 (see Section 17.1) special export status (see Section

25.14). Products that implement one of these two algorithms have a much simpler

export approval process, provided that the keys are no more than 40 bits long.

Is a 40-bit key enough? There are a total of one trillion possible keys. Assuming

that brute force is the most efficient method of cryptanalysis (a big assumption, con-

sidering that the algorithm has never been published), and assuming that a brute-

force cryptanalysis chip can test one million keys per second, it will take him 12.7

days to find the correct key. One thousand machines working in parallel can pro-

duce the key in twenty minutes.

RSA Data Security, Inc., maintains that while encryption and decryption are

quick, exhaustive key search is not. A significant amount of time is spent setting up

the key schedule. While this time is negligible when encrypting and decrypting

messages, it is not when trying every possible key.

The U.S. government would never allow export of any algorithm it couldnâ€™t, at

least in theory, break. They could create a magnetic tape or CD of a specific plain-

text block encrypted with every possible key. To break a given message, they could

just run the tape and compare the ciphertext blocks in the message with the cipher-

text blocks on the tape. If there is a match, they could try the candidate key and see

if the message makes any sense. If they choose a common plaintext block (all zeros,

the ASCII characters for a space, etc.), this method should work. The storage

requirement for a 64-bit plaintext block encrypted with all 1012possible keys is 8

terabytes-certainly possible.

For information on licensing RC2, contact RSADSI (see Section 25.4).

13.9 IDEA

The first incarnation of the IDEA cipher, by Xuejia Lai and James Massey, surfaced

in 1990 [929]. It was called PES (Proposed Encryption Standard). The next year, after

Biham and Shamirâ€™s demonstrated differential cryptanalysis, the authors strength-

ened their cipher against the attack and called the new algorithm IPES (Improved

Proposed Encryption Standard) [931,924]. IPES changed its name to IDEA (Interna-

tional Data Encryption Algorithm) in 1992 [925].

IDEA is based on some impressive theoretical foundations and, although crypt-

analysis has made some progress against reduced-round variants, the algorithm still

seems strong. In my opinion, it is the best and most secure block algorithm avail-

able to the public at this time.

Page 319

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CHAPTER13 Other Block Ciphers

The future of IDEA is not yet clear. There has been no rush to adopt it as a replace-

ment to DES, partly because it is patented and must be licensed for commercial

applications, and partly because people are still waiting to see how well the algo-

rithm fares during the coming years of cryptanalysis. Its current claim to fame is

that it is part of PGP (see Section 24.12).

of lDEA

Oueruiew

IDEA is a block cipher; it operates on 64-bit plaintext blocks. The key is 128 bits

long. The same algorithm is used for both encryption and decryption.

As with all the other block ciphers weâ€™ve seen, IDEA uses both confusion and dif-

fusion. The design philosophy behind the algorithm is one of â€śmixing operations

from different algebraic groups.â€ť Three algebraic groups are being mixed, and they

are all easily implemented in both hardware and software:

- XOR

- Addition modulo 216

- Multiplication modulo 216 + 1. (This operation can be viewed as

IDEAâ€™s S-box.)

All these operations (and these are the only operations in the algorithm-there are

no bit-level permutations) operate on 16-bit sub-blocks. This algorithm is even effi-

cient on 16-bit processors.

of IDEA

Description

Figure 13.9 is an overview of IDEA. The 64-bit data block is divided into four 16-

bit sub-blocks: X1, X2, X3, and X4. These four sub-blocks become the input to the first

round of the algorithm. There are eight rounds total. In each round the four sub-

blocks are XORed, added, and multiplied with one another and with six 16-bit sub-

keys. Between rounds, the second and third sub-blocks are swapped. Finally, the

four sub-blocks are combined with four subkeys in an output transformation.

In each round, the sequence of events is as follows:

(1) Multiply X1 and the first subkey.

(2) Add X2 and the second subkey.

(3) Add X3 and the third subkey.

(4) Multiply X4 and the fourth subkey.

(5) XOR the results of steps (1) and (3).

(6) XOR the results of steps (2) and (4).

(7) Multiply the results of step (5) with the fifth subkey.

(8) Add the results of steps (6) and (7).

(9) Multiply the results of step (8) with the sixth subkey.

(10) Add the results of steps (7) and (9).

Page 320

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

13.9 IDEA

one

round

j

seven

y2 y3 y4

Xi : 16-bitplaintextsub-block

Vi : 16-bitciphertextsub-block

Z; cr): 16-bit key sub-block

@: bit-by-bit exclusive-or (XOR)of 16-bitsub-blocks

q : addition modulo˜l6of l&bit integers

0: multiplicationmodulo216+1 of 16-bitintegers

with thezerosub-blockcorrespondingto216

Figure 13.9 IDEA.

(11) XOR the results of steps (1) and (9).

(12) XOR the results of steps (3) and (9).

(13) XOR the results of steps (2) and (10).

(14) XOR the results of steps (4) and (10).

The output of the round is the four sub-blocks that are the results of steps (1 l),

(12), (13), and (14). Swap the two inner blocks (except for the last round) and thatâ€™s

the input to the next round.

After the eighth round, there is a final output transformation:

(1) Multiply X1 and the first subkey.

Page 321

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CHAPTER13 Other Block Ciphers

(2) Add X2 and the second subkey.

(3) Add X, and the third subkey.

(4) Multiply X, and the fourth subkey.

Finally, the four sub-blocks are reattached to produce the ciphertext.

Creating the subkeys is also easy. The algorithm uses 52 of them (six for each of

the eight rounds and four more for the output transformation). First, the 128-bit key

is divided into eight 16-bit subkeys. These are the first eight subkeys for the algo-

rithm (the six for the first round, and the first two for the second round). Then, the

key is rotated 25 bits to the left and again divided into eight subkeys. The first four

are used in round 2; the last four are used in round 3. The key is rotated another 2.5

bits to the left for the next eight subkeys, and so on until the end of the algorithm.

Decryption is exactly the same, except that the subkeys are reversed and slightly

different. The decryption subkeys are either the additive or multiplicative inverses

of the encryption subkeys. (For the purposes of IDEA, the all-zero sub-block is con-

sidered to represent 216= -1 for multiplication modulo 216+ 1; thus the multiplica-

tive inverse of 0 is 0.) Calculating these takes some doing, but you only have to do

it once for each decryption key. Table 13.4 shows the encryption subkeys and the

corresponding decryption subkeys.

of IDEA

Speed

Current software implementations of IDEA are about twice as fast as DES. IDEA

on a 33 megahertz 386 machine encrypts data at 880 kilobits per second, and 2400

kilobits per second on a 66 megahertz 486 machine. You might think IDEA should

be faster, but multiplications arenâ€™t cheap. To multiply two 32-bit numbers on a 486

requires 40 clock cycles (10 on a Pentium).

A VLSI implementation of PES encrypts data at 55 megabits per second at 25

megahertz [208,398]. Another VLSI chip developed at ETH Zurich, consisting of

251,000 transistors on a chip 107.8 square millimeters, encrypts data using the

Table 13.4

IDEA Encryption and Decryption Subkeys

Round Encryption Subkeys Decryption Subkeys

&Iâ€™1 -&ill z3i11

-&Ill z5111

ZJll

1st 21191 - 1 -z2(91 -z,r91 7J9l - 1 z51U &I81

2nd ˜˜181 1 -zPl

z,lZ -&I21 2,121 7J21 -

25121 ,&I21 -z˜W ˜4181- 1 25171 2271

3rd 21131 z2131 2,131 24131 25131 Z6i31 ˜,I71 - 1 .˜&I71 -&I71 -&I71 - 1 z5lW '&I61

4th 56) - 1 47,1614361 &bl - 1 ˜˜1% &El

Zli4l z2(4) z3141 z4(4l z5(4l 2241

5th &lSl z5151z&5)

Z,lSl -&El 2,151 Z,lSl - 1 -z3151 -2451 &I51 - 1 z5141 z6(4l

6th ˜,I61 Ql z3161z4161@5l &@I &I41 - 1 q3r4r -z2(4l z4(4l - 1 2513) &I31

7th &i7l &I71 23â€™7â€™ z4(71 z5(7l &Iâ€™) -&I31 - 1 -z3131 g72(3l 24131 - 1 z5121 2221

8th ˜,I81 -Ql &PI z4(8) z5181 z6(8) -&PI +I21 z4(2l - I Z5lll p-6111

zp - 1

output &19l &I91 z3191 Zq(9l Z,lll - 1 qJ1l -z3111 Zq(ll -1

transformation

Page 322

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

13.9 IDEA

algorithm at a 177 megabit-per-second data rate when clocked at 25 mega-

IDEA

hertz (926,207,397].

of IDEA

Cryptanalysis

IDEAâ€™s key length is 128 bits-over twice as long as DES. Assuming that a brute-

force attack is the most efficient, it would require 2 12*( 1038)encryptions to recover

the key. Design a chip that can test a billion keys per second and throw a billion of

them at the problem, and it will still take 1013years-thatâ€™s longer than the age of

the universe. An array of 1O24 such chips can find the key in a day, but there arenâ€™t

enough silicon atoms in the universe to build such a machine. Now weâ€™re getting

somewhere-although Iâ€™d keep my eye on the dark matter debate.

Perhaps brute force isnâ€™t the best way to attack IDEA. The algorithm is still too

new for any definitive cryptanalytic results. The designers have done their best to

make the algorithm immune to differential cryptanalysis; they defined the concept

of a Markov cipher and showed that resistance to differential cryptanalysis can be

modeled and quantified [93 1,925]. (Figure 13.10 shows the original PES algorithm to

be contrasted with the IDEA algorithm of Figure 13.9 which was strengthened

against differential cryptanalysis. Itâ€™s amazing how a few subtle changes can make

such a big difference.) In [925], Lai argued (he gave evidence, not a proof) that IDEA

is immune to differential cryptanalysis after only 4 of its 8 rounds. According to

Biham, his related-key cryptanalytic attack doesnâ€™t work against IDEA, either [ 1601.

Willi Meier examined the three algebraic operations of IDEA, and pointed out that

while they are incompatible, there are instances where they can be simplified in

such a way as to facilitate cryptanalysis some percentage of the time [ 1050). His

attack is more efficient than brute-force for 2-round IDEA (242operations), but less

efficient for 3-round IDEA or higher. Normal IDEA, with 8 rounds, is safe.

Joan Daemen discovered a class of weak keys for IDEA [406,409]. These are not

weak keys in the sense of the DES weak keys; that is, the encryption function is self-

inverse. They are weak in the sense that if they are used, an attacker can easily iden-

tify them in a chosen-plaintext attack. For example, a weak key is (in hex]:

oooo,oooo,oxoo,oooo,oooo,ooox,xxxx,xooo

The number at the positions of â€śxâ€ť can be any number. If this key is used, the bit-

wise XOR of certain plaintext pairs guarantees the bit-wise XOR of the resultant

ciphertext pairs.

In any case, the chance of accidentally generating one of these weak keys is very

small: one in 296.There is no danger if you choose keys at random. And it is easy to

modify IDEA so that it doesnâ€™t have any weak keys: XOR every subkey with the

value OxOdae[409].

I know of no other cryptanalytic results against IDEA, although many people

have tried.

of Operation

1DEA Modes and Variants

IDEA can work within any block cipher mode discussed in Chapter 9. Any dou-

ble-IDEA implementation would be susceptible to the same meet-in-the-middle

Page 323

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CHAPTER13 Other Block Ciphers

one

round

seven >

more :

rounds

Z,(9)

Z,(9) * Z*(9) . Z$9)

Output Transformation

+ ++

44

y4

Xi : 16-bit plaintext sub-block y3

Yl y2

Vi : 16-bit ciphertext sub-block

Zi (0 : 16-bit key sub-block

@: bit-by-bit exclusive-or (XOR) of 16-bit sub-blocks

a: addition modulo2 16of16-bit integers

0: multiplication modulo 2 16+1 of 16-bit integers

with the zero sub-block corresponding to 216

Figure 13.10 PES.

attack as DES (see Section 15.1). However, because IDEAâ€™s key length is more than

double DESâ€™s, the attack is impractical. It would require a storage space of 64*212*

bits, or 1O39 bytes. Maybe thereâ€™s enough matter in the universe to create a memory

device that large, but I doubt it.

If youâ€™re worried about parallel universes as well, use a triple-IDEA implementa-

tion (see Section 15.2):

C = EK˜(DKJEK,(PI))

It is immune to the meet-in-the-middle attack.

Thereâ€™s also no reason why you canâ€™t implement IDEA with independent subkeys,

especially if you have key-management tools to handle the longer key. IDEA needs

a total of 52 16-bit keys, for a total key length of 832 bits. This variant is definitely

more secure, but no one knows by how much.

Page 324

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

13.10 MMB

A naiâ€™ve variation might double the block size. The algorithm would work just as

well with 32-bit sub-blocks instead of 16-bit sub-blocks, and a 256-bit key. Encryp-

tion would be quicker and security would increase 232times. Or would it? The the-

ory behind the algorithm hinges on the fact that 216+ 1 is prime; 232+ 1 is not.

Perhaps the algorithm could be modified to work, but it would have very different

security properties. Lai says it would be difficult to make it work [926].

While IDEA appears to be significantly more secure than DES, it isnâ€™t always easy

to substitute one for the other in an existing application. If your database and mes-

sage templates are hardwired to accept a 64-bit key, it may be impossible to imple-

ment IDEAâ€™s 128-bit key.

For those applications, generate a 128-bit key by concatenating the 64-bit key

with itself. Remember that IDEA is weakened considerably by this modification.

If you are more concerned with speed than security, you might consider a variant

of IDEA with fewer rounds. Currently the best attack against IDEA is faster than

brute force only for 2.5 rounds or less [ 10501; 4 round IDEA would be twice as fast

and, as far as I know, just as secure.

Caveat Emptor

IDEA is a relatively new algorithm, and many questions remain. Is IDEA a group?

(Lai thinks not (9261.)Are there any still-undiscovered ways of breaking this cipher?

IDEA has a firm theoretical basis, but time and time again secure-looking algo-

rithms have fallen to new forms of cryptanalysis. Several academic and military

groups have cryptanalyzed IDEA. None of them has gone public about any successes

they might have had. One might-someday.

Patents and Licenses

IDEA is patented in Europe and the United States [1012,1013]. The patent is held

by Ascom-Tech AG. No license fee is required for non-commercial use. Commercial

users interested in licensing the algorithm should contact Ascom Systec AG, Dept

CMW, Gewerbepark, CH-5506, MHgenwil, Switzerland; +41 64 56 59 83; Fax: +41

64 56 59 90; idea@ascom.ch.

13.10 MMB

A complaint against IDEA, that it uses a 64-bit encryption block, was addressed by

Joan Daemen in an algorithm called MMB (Modular Multiplication-based Block

cipher) [385,405,406]. MMB is based on the same basic theory as IDEA: mixing oper-

ations of different algebraic groups. MMB is an iterative algorithm that mainly con-

sists of linear steps (XOR and key applications) and the parallel applications of four

large nonlinear invertible substitutions. These substitutions are determined by a

multiplication modulo 232- 1 with constant factors. The result is an algorithm that

has both a 128-bit key and a 128-bit block size.

MMB operates on 32-bit sub-blocks of text (x0, xl, x2, x3) and 32-bit sub-blocks of

key (k,, kI, k2, k3). This makes the algorithm well suited for implementation on

modern, 32-bit processors. A nonlinear function, f, is applied six times alternating

with XORing. Here it is (all index operations are mod 4):

Page 325

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CHAPTER13 Other Block Ciphers

Xi=XiOki,fori=Oto3

f(XoJ*J*J3)

X, = Xi $ ki + 1, for i = 0 to 3

f(xo,xl˜x2˜x3˜

Xi = xi 0 ki + 2, for i = 0 to 3

f(xo&x2J3)

Xi = X, 0 ki, for i = 0 to 3

f(xoJlJ27x3)

Xl=XiOk,+i,fori=Oto3

f(XO>X,>X2J3˜

Xi = Xi 0 ki +2, for i = 0 to 3

f(XO>XlJ2J3)

The function f has three steps:

Ill Xi = c, x,, for i = 0 to 3 (If the input to the multiplication is all Is, the out-

l

put is also all 1s.)

PI If the least significant bit of x0 = 1, then x0 = x0 0 C. If the least significant

byte of x3 = 0, then x3 = x3 0 C.

(31 X,=X,-iOX˜OXi+i,fori=Oto3

All index operations are mod 4. The multiplication operation in step (1) is modulo

232- 1. For the purposes of the algorithm, if the second operand is 232- 1, then the

result is 232- 1. The various constants are:

C = 2aaaaaaa

co = 025f lcdb

Cl =2 * co

c2 =23 l co

c3 = 27 l co

The constant C is the â€śsimplestâ€ť constant with a high ternary weight, a least-

significant bit of zero, and no circular symmetry. The constant co has certain other

characteristics. The constants cl, c2, and c3 are shifted versions of co, preventing

attacks based on symmetry. See [405] for more details.

Decryption is the reverse process. Steps (2) and (3) are their own inverse. Step (1)

uses c,-â€™ instead of ci. The value of co-â€™ is Odad4694.

of MMB

Security

The design of MMB ensures that each round has considerable diffusion indepen-

dent of the key. In IDEA, the amount of diffusion is to some extent dependent on the

particular subkeys. MMB was also designed not to have any weak keys as IDEA has.

Page 326

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

13.11 CA-l.1

MMB is dead [402]. Although no cryptanalysis has been published, this is true for

several reasons. First, it was not designed to be resistant to linear cryptanalysis. The

multiplication factors were chosen to be resistant to differential cryptanalysis, but

the algorithmâ€™s authors were unaware of linear cryptanalysis.

Second, Eli Biham has an effective chosen-key attack [160], which exploits the

fact that all rounds are identical and that the key schedule is just a cyclic shift by 32

bits. Third, even though MMB would be very efficient in software, the algorithm

would be less efficient than DES in hardware.

Daemen suggests that anyone interested in improving MMB should first do an

analysis of modular multiplication with respect to linear cryptanalysis and choose a

new multiplication factor, and then make the constant C different for each round

[402]. Then, improve the key scheduling by adding constants to the round keys to

remove the bias. Heâ€™s not going to do it; he designed 3-Way instead (see Section 14.5).

13.11 CA-l.1

CA is a block cipher built on cellular automata, designed by Howard Gutowitz

[677,678,679]. It encrypts plaintext in 384-bit blocks and has a 108%bit key (itâ€™s

really two keys, a 1024-bit key and a 64-bit key). Because of the nature of cellular

automata, the algorithm is most efficient when implemented in massively parallel

integrated circuits.

CA-l. 1 uses both reversible and irreversible cellular automaton rules. Under a

reversible rule, each state of the lattice comes from a unique predecessor state,

while under an irreversible rule, each state can have many predecessor states. Dur-

ing encryption, irreversible rules are iterated backward in time. To go backward

from a given state, one of the possible predecessor states is selected at random. This

process can be repeated many times. Backward iteration thus serves to mix random

information with the message information. CA-1 .l uses a particular kind of par-

tially linear irreversible rule, which is such that a random predecessor state for any

given state can be rapidly built. Reversible rules are also used for some stages of

encryption.

The reversible rules (simple parallel permutations on sub-blocks of the state) are

nonlinear. The irreversible rules are derived entirely from information in the key,

while the reversible rules depend both on key information and on the random infor-

mation inserted during the stages of encryption with irreversible rules.

CA-l. 1 is built around a block-link structure. That is, the processing of the mes-

sage block is partially segregated from the processing of the stream of random infor-

mation inserted during encryption. This random information serves to link stages of

encryption together. It can also be used to chain together a ciphertext stream. The

information in the link is generated as part of encryption.

Because CA- 1.1 is a new algorithm, it is too early to make any pronouncements on

its security. Gutowitz discusses some possible attacks, including differential crypt-

analysis, but is unable to break the algorithm. As an incentive, Gutowitz has offered

a $1000 prize to â€śthe first person who develops a tractable procedure to break CA- 1.1.â€ť

Page 327

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CHAPTER13 Other Block Ciphers

CA-l.1 is patented [678], but is available free for non-commercial use. Anyone

interested in either licensing the algorithm or in the cryptanalysis prize should con-

tact Howard Gutowitz, ESPCI, Laboratoire dâ€™Electronique, 10 rue Vauquelin, 75005

Paris, France.

13.12 SKIPJACK

Skipjack is the NSA-developed encryption algorithm for the Clipper and Capstone

chips (see Sections 24.16 and 24.17). Since the algorithm is classified Secret, its details

have never been published. It will only be implemented in tamperproof hardware.

The algorithm is classified Secret, not because that enhances its security, but

because the NSA doesnâ€™t want Skipjack being used without the Clipper key-escrow

mechanism. They donâ€™t want the algorithm implemented in software and spread

around the world.

Is Skipjack secure? If the NSA wants to produce a secure algorithm, they presum-

ably can. On the other hand, if the NSA wants to design an algorithm with a trap-

door, they can do that as well.

Hereâ€™s what has been published [ 1154,462).

- Itâ€™s an iterative block cipher.

- The block size is 64 bits.

- It has an 80-bit key.

- It can be used in ECB, CBC, 64-bit OFB, or l-, 8-, 16-, 32- or 64-bit CFB

modes.

- There are 32 rounds of processing per single encrypt or decrypt oper-

ation.

- NSA started the design in 1985 and completed the evaluation in 1990.

The documentation for the Mykotronx Clipper chip says that the latency for the

Skipjack algorithm is 64 clock cycles. This means that each round consists of two

clock cycles: presumably one for the S-box substitution and another for the final

XOR at the end of the round. (Remember: permutations take no time in hardware.)

The Mykotronx documentation calls this two-clock-cycle operation a â€śG-box,â€ť and

the whole thing a â€śshift.â€ť (Some part of the G-box is called an â€śF-table,â€ť probably a

table of constants but maybe a table of functions.)

I heard a rumor that Skipjack uses 16 S-boxes, and another that the total memory

requirement for storing the S-boxes is 128 bytes. It is unlikely that both of these

rumors are true.

Another rumor implies that Skipjackâ€™s rounds, unlike DESâ€™s, do not operate on

half of the block size. This, combined with the notion of â€śshifts,â€ť an inadvertent

statement made at Crypto â€˜94 that Skipjack has â€śa 48-bit internal structure,â€ť

implies that it is similar in design to SHA (see Section 18.7) but with four 16-bit sub-

blocks: three sub-blocks go through a key-dependent one-way function to produce

ńňđ. 1 |