i=j=0

A=B=0

do 3n times (where n is the maximum of 2(r + 1) and c):

A = Si = (Si + A + B) <<< 3

B = Lj = (Lj + A + B) <<< (A + B)

i = (i + 1) mod 2(r + 1)

j = (j + 1) mod c

RC5 is actually a family of algorithms. We just defined RC5 with a 32-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 0xb7e151628aed2a6b and 0x9e3779b97f4a7c15, 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 plaintext bit affects at least one rotation.

There is a differential attack that requires 224 chosen plaintexts for 5 rounds, 245 for 10 rounds, 253

for 12 rounds, and 268 for 15 rounds. Of course, there are only 264 possible 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 [1325]. This number may

change.

RSADSI is in the process of patenting RC5, and the name is trademarked. The company claims that

license fees will be very small, but you™d better check with them.

Page 287 of 666

Applied Cryptography: Second Edition - Bruce Schneier

14.9 Other Block Algorithms

There is an algorithm called CRYPTO-MECCANO in the literature [301]; it is insecure. Four

Japanese cryptographers presented an algorithm based on chaotic maps at Eurocrypt ™91 [687, 688];

Biham cryptanalyzed the algorithm at the same conference [157]. 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 [1292,733,1504,1291,1056,1057,1058,1293], variants of the Rao-Nam algorithm

[464,749,1503], and the Li-Wang algorithm [964,1561]”they are all insecure. CALC is insecure

[1109]. 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

[189]; 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 interests 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 relationship 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 cryptanalysis more difficult.

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: 1020 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. Sometimes 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

Page 288 of 666

Applied Cryptography: Second Edition - Bruce Schneier

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 output of the ith round is determined from the output of

the previous round:

Li = Ri - 1

Ri = Li - 1 f(Ri - 1,Ki)

Ki 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 f(Ri - 1,Ki) f(Ri - 1,Ki) = 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 decryption. The structure of a Feistel network takes care of all this

automatically.

Simple Relations

DES has the property that if EK(P) = C, then EK™(P™) = C™, where P™, C™, and K™ are the bit-wise

complements of P, C, and K. This property reduces the complexity of a 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 EK(P) = C, then Ef(K) (g(P,K)) = h(C,K)

where f, g, and h are simple functions. By simple I mean that they are easy to compute, 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 complement 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

Page 289 of 666

Applied Cryptography: Second Edition - Bruce Schneier

are the ciphertext blocks with each possible key, and the group operation is composition. Looking at

an algorithmos 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 wouldnot 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 number of weak keys, like

DES, are generally no problem. The odds of picking one at random 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 function (see Section 18.11).

Strength against Differential and Linear 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 differentials

[702,161,927,858,860] and partial differentials [860]. Higher-order differentials seem to apply only to

ciphers with a small number of rounds, but partial differentials 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 [1270]; [938] tries to combine linear and differential cryptanalysis into one attack. It

is unclear what design techniques 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 cryptanalysis [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

Page 290 of 666

Applied Cryptography: Second Edition - Bruce Schneier

The strength of various Feistel networks”and specifically their resistance to differential 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. Previously 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 algorithm; 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 cryptanalysis”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 G

2m “ m, then there is definitely a linear relation of the input and output bits of the S-box. And if n G

2m, then there is a linear relation of only the output bits [164].

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

independently 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 complicated

[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 output 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 criteria, 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 [1640].

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 [172]. Actually, a

better approach is making sure that the maximum differential is as small as possible. Kwangjo Kim

proposed 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.

Page 291 of 666

Applied Cryptography: Second Edition - Bruce Schneier

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” [1262].

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

[1179] 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 S-boxes and S-boxes with certain

properties. Certainly the latter approach has the advantage of being optimal against known attacks”

linear and differential cryptanalysis”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

[1018]. 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 permutation 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 is 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 512 bits,

you really donot care if there are key-complementation properties.

The real trick”and the reason that real-world block cipher design is very difficult”is to design a

block cipher with the smallest possible key, the smallest possible 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 ciphertext block

concatenated with the key, then XoR the result with the current plaintext block:

Ci = Pi H(K,Ci - 1)

Pi = Ci H(K,Ci - 1)

Page 292 of 666

Applied Cryptography: Second Edition - Bruce Schneier

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 construction can use the one-way function in OFB

mode:

Ci = Pi Si; Si = H(K,Ci - 1)

Pi = Ci Si; Si = 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.

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: P1 and Pr. Then, split the key into two 48-

byte halves: K1 and Kr.

P = P1,Pr

K = K1,Kr

Append K1 to P1 and hash it with a one-way hash function, then XoR the result of the hash with Pr to

produce Cr, the right half of the ciphertext. Then, append Kr to Cr and hash it with the one-way hash

function. XoR the result with P1 to produce C1. Finally, append Cr to C1 to produce the ciphertext.

Cr = Pr H(P1,K 1)

C1 = P1 H(Cr,Kr)

C = C1,Cr

To decrypt, simply reverse the process. Append Kr to Cr, hash and XoR with C1 to produce P1.

Append K1 to P1, hash and XoR with Cr to produce Pr.

P1 = C1 H(Cr,Kr)

Pr = Cr H(P1,K1)

P = P1,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 algorithm 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.

Luby-Rackoff

Page 293 of 666

Applied Cryptography: Second Edition - Bruce Schneier

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: H1, H2, and H3. Further work shows that H1 can equal H2, or that H2 can equal H3, but

not both [1193]. Also, H1, H2, and H3 cannot be based on iterating the same basic function [1643].

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: K1 and Kr.

(2) Divide the plaintext block into two halves: L0 and R0.

(3) Append K1 to L0 and hash it. XoR the result of the hash with R0 to produce R1:

R1 = R0 H(K1,L0)

(4) Append Kr to R1 and hash it. XOR the result of the hash with L0 to produce L1:

L1 = L0 H(Kr,R1)

(5) Append K1 to L1 and hash it. XOR the result of the hash with R1 to produce R2:

R2 = R1 H(K1,L1)

(6) Append L1 to R1 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 512-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 512-bit 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 others. It is unpatented.

Anyone can use it at any time, in any way, royalty-free [676].

However, I donot 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 512-bit “key,” and uses this to learn some information about the 512-

bit key used. Since the designers didnot have to worry about this, it seems like a bad idea to count on

your cipher being able to resist this attack.

Page 294 of 666

Applied Cryptography: Second Edition - Bruce Schneier

Security of Ciphers Based on one-Way Hash Functions

While these constructions can be secure, they depend on the choice of the underlying one-way hash

function. A good one-way hash function doesnot 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-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.

Figure 14.5 Message Digest Cipher (MDC).

14.12 Choosing a Block Algorithm

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 governments, use triple-DES with three independent keys.

The other algorithms arenot 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 recommendation is that the NSA almost

certainly has an array of impressive cryptanalytic techniques that are still classified, and I donot

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 128-bit key, combined with its resistance to any public means of

cryptanalysis, gives me a warm, fuzzy feeling about the algorithm. The algorithm has been analyzed

by a lot of different groups, and no serious results have been announced yet. Barring extraordinary

cryptanalytic news tomorrow, I am betting on IDEA today.

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) 135 MDC (using MD5) 135

Page 295 of 666

Applied Cryptography: Second Edition - Bruce Schneier

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-32/20 52

Khufu (24 rounds) 153 SAFER (6 rounds) 81

Khufu (32 rounds) 115 SAFER (8 rounds) 61

Luby-Rackoff (using 47 SAFER (10 rounds) 49

MD4)

Luby-Rackoff (using 34 SAFER (12 rounds) 41

MD5)

Luby-Rackoff (using 11 3-Way 25

SHA)

Lucifer 52 Triple-DES 12

Chapter 15

Combining Block Ciphers

There are many ways to combine block algorithms to get new algorithms. The impetus behind these

schemes is to try to increase security without going through the trouble of designing a new algorithm.

DES is a secure algorithm; it has been cryptanalyzed for a good 20 years and the most practical way

to break it is still brute force. However, the key is too short. Wouldn™t it be nice to use DES as a

building block for another algorithm with a longer key? We™d have the best of both worlds: the

assurance of two decades of cryptanalysis plus a long key.

Multiple encryption is one combination technique: using an algorithm to encrypt the same plaintext

block multiple times with multiple keys. Cascading is like multiple encryption, but uses different

algorithms. There are other techniques.

Encrypting a plaintext block twice with the same key, whether with the same algorithm or a different

one, is not smart. For the same algorithm, it does not affect the complexity of a brute-force search.

(Remember, you assume a cryptanalyst knows the algorithm including the number of encryptions

used.) For different algorithms, it may or may not. If you are going to use any of the techniques in this

chapter, make sure the multiple keys are different and independent.

15.1 Double Encryption

A na¬ve way of improving the security of a block algorithm is to encrypt a block twice with two

different keys. First encrypt a block with the first key, then encrypt the resulting ciphertext with the

second key. Decryption is the reverse process.

C = EK2(EK1(P))

P = DK1(DK2(C))

Page 296 of 666

Applied Cryptography: Second Edition - Bruce Schneier

If the block algorithm is a group (see Section 11.3), then there is always a K3 such that

C = EK2(EK1(P)) = EK3(P)

If this is not the case, the resultant doubly-encrypted ciphertext block should be much harder to

break using an exhaustive search. Instead of 2n attempts (where n is the bit length of the key), it

would require 22n attempts. If the algorithm is a 64-bit algorithm, the doubly-encrypted ciphertext

would require 2128 attempts to find the key.

This turns out not to be true for a known-plaintext attack. Merkle and Hellman [1075] developed a

time-memory trade-off that could break this double-encryption scheme in 2n + 1 encryptions, not in

22n encryptions. (They showed this for DES, but the result can be generalized to any block algorithm.)

The attack is called a meet-in-the-middle attack; it works by encrypting from one end, decrypting

from the other, and matching the results in the middle.

In this attack, the cryptanalyst knows P1, C1, P2, and C2, such that

C1 = EK2(EK1(P1))

C2 = EK2(EK1(P2))

For each possible K, he computes EK(P1) and stores the result in memory. After collecting them all, he

computes DK(C1) for each K and looks for the same result in memory. If he finds it, it is possible that

the current key is K2 and the key in memory is K1. He tries encrypting P2 with K1 and K2; if he gets C2

he can be pretty sure (with a probability of success of 1 in 22m “ 2n, where m is the block size) that he

has both K1 and K2. If not, he keeps looking. The maximum number of encryption trials he will

probably have to run is 2*2n, or 2n + 1. If the probability of error is too large, he can use a third

ciphertext block to get a probability of success of 1 in 23m “ 2n. There are still other optimizations

[912].

This attack requires a lot of memory: 2n blocks. For a 56-bit algorithm, this translates to 256 64-bit

blocks, or 1017 bytes. This is still considerably more memory storage than one could comfortably

comprehend, but it™s enough to convince the most paranoid of cryptographers that double encryption

is not worth anything.

For a 128-bit key, the amount of memory required is an enormous 1039 bytes. If we assume that a way

exists to store a bit of information on a single atom of aluminum, the memory device required to

launch this attack would be a cube of solid aluminum over a kilometer on a side. And then you need

some place to put it! The meet-in-the middle attack seems infeasible for keys this size.

Another double-encryption method, sometimes called Davies-Price, is a variant of CBC [435].

Ci = EK1(Pi EK2(Ci - 1))

Pi = DK1(Ci) EK2(Ci - 1)

They claim “no special virtue of this mode,” but it seems to be vulnerable to the same meet-in-the-

middle attacks as other double-encryption modes.

Page 297 of 666

Applied Cryptography: Second Edition - Bruce Schneier

15.2 Triple Encryption

Triple Encryption with Two Keys

A better idea, proposed by Tuchman in [1551], operates on a block three times with two keys: with the

first key, then with the second key, and finally with the first key again. He suggested that the sender

first encrypt with the first key, then decrypt with the second key, and finally encrypt with the first

key. The receiver decrypts with the first key, then encrypts with the second key, and finally decrypts

with the first key.

C = EK1(DK2(EK1(P)))

P = DK1(EK2(DK1(C)))

This is sometimes called encrypt-decrypt-encrypt (EDE) mode [55]. If the block algorithm has an n-

bit key, then this scheme has a 2n-bit key. The curious encrypt-decrypt-encrypt pattern was designed

by IBM to preserve compatibility with conventional implementations of the algorithm: Setting the two

keys equal to each other is identical to encrypting once with the key. There is no security inherent in

the encrypt-decrypt-encrypt pattern, but this mode has been adopted to improve the DES algorithm

in the X9.17 and ISO 8732 standards [55,761].

K1 and K2 alternate to prevent the meet-in-the-middle attack previously described. If C = EK2(EK1

(EK1(P))), then a cryptanalyst could precompute EK1(EK1(P))) for every possible K1 and then proceed

with the attack. It only requires 2n + 2 encryptions.

Triple encryption with two keys is not susceptible to the same meet-in-the-middle attack described

earlier. But Merkle and Hellman developed another time-memory trade-off that could break this

technique in 2n - 1 steps using 2n blocks of memory [1075].

For each possible K2, decrypt 0 and store the result in memory. Then, decrypt 0 with each possible K1

to get P. Triple-encrypt P to get C, and then decrypt C with K1. If that decryption is a decryption of 0

with a K2 (stored in memory), the K1 K2 pair is a possible candidate. Check if it is right. If it™s not,

keep looking.

This is a chosen-plaintext attack, requiring an enormous amount of chosen plaintext to mount. It

requires 2n time and memory, and 2m chosen plaintexts. It is not very practical, but it is a weakness.

Paul van Oorschot and Michael Wiener converted this to a known-plaintext attack, requiring p

known plaintexts. This example assumes EDE mode.

(1) Guess the first intermediate value, a.

(2) Tabulate, for each possible K1, the second intermediate value, b, when the first

intermediate value is a, using known plaintext:

b = DK1(C)

where C is the resulting ciphertext from a known plaintext.

(3) Look up in the table, for each possible K2, elements with a matching second

intermediate value, b:

Page 298 of 666

Applied Cryptography: Second Edition - Bruce Schneier

b = EK2(a)

(4) The probability of success is p/m, where p is the number of known plaintexts and m is

the block size. If there is no match, try another a and start again.

The attack requires 2n + m/p time and p memory. For DES, this is 2120/p [1558]. For p greater than

256, this attack is faster than exhaustive search.

Triple Encryption with Three Keys

If you are going to use triple encryption, I recommend three different keys. The key length is longer,

but key storage is usually not a problem. Bits are cheap.

C = EK3(DK2(EK1(P)))

P = DK1(EK2(DK3(C)))

The best time-memory trade-off attack takes 22n steps and requires 2n blocks of memory; it™s a meet-

in-the-middle attack [1075]. Triple encryption, with three independent keys, is as secure as one might

naïvely expect double encryption to be.

Triple Encryption with Minimum Key (TEMK)

There is a secure way of using triple encryption with two keys that prevents the previous attack,

called Triple Encryption with Minimum Key (TEMK) [858]. The trick is to derive three keys from

two: X1 and X2:

K1 = EX1(DX2(EX1(T1)))

K2 = EX1(DX2(EX1(T2)))

K3 = EX1(DX2(EX1(T3)))

T1, T2, and T3 are constants, which do not have to be secret. This is a special construction that

guarantees that for any particular pair of keys, the best attack is a known-plaintext attack.

Triple-Encryption Modes

It™s not enough to just specify triple encryption; there are several ways to do it. The decision of which

to use affects both security and efficiency.

Here are two possible triple-encryption modes:

Inner-CBC: Encrypt the entire file in CBC mode three different times (see Figure 15.1a).

This requires three different IVs.

Ci = EK3(Si Ci - 1); Si = DK2(Ti Si - 1); Ti = EK1(Pi Ti - 1)

Pi = Ti - 1 DK1(Ti); Ti = Si - 1 EK2(Si); Si = Ci - 1 DK3(Ci)

C0, S0, and T0 are IVs.

Outer-CBC: Triple-encrypt the entire file in CBC mode (see Figure 15.1b). This requires

one IV.

Ci = EK3(DK2(EK1(Pi Ci - 1)))

Page 299 of 666

Applied Cryptography: Second Edition - Bruce Schneier

Pi = Ci - 1 DK1(EK2(DK3(Ci)))

Both modes require more resources than single encryption: more hardware or more time. However,

given three encryption chips, the throughput of inner-CBC is no slower than single encryption. Since

the three CBC encryptions are independent, three chips can be kept busy all the time, each feeding

back into itself.

On the other hand, outer-CBC feedback is outside the three encryptions. This means that even with

three chips, the throughput is only one-third that of single encryption. To get the same throughput

with outer-CBC, you need to interleave IVs (see Section 9.12):

Figure 15.1 Triple encryption in CBC mode.

Ci = EK3(DK2(EK1(Pi Ci-3)))

In this case C0, C-1, and C-2 are IVs. This doesn™t help software implementations any, unless you have

a parallel machine.

Unfortunately, the simpler mode is also the least secure. Biham analyzed various modes with respect

to chosen-ciphertext differential cryptanalysis and found that inner-CBC is only slightly more secure

than single encryption against a differential attack. If you think of triple encryption as a single larger

algorithm, then inner feedbacks allow the introduction of external and known information into the

inner workings of the algorithm; this facilitates cryptanalysis. The differential attacks require

enormous amounts of chosen ciphertext to mount and are not very practical, but the results should be

enough to give the most paranoid pause. Another analysis against meet-in-the-middle and brute-force

attacks concludes that they are all equally secure [806].

There are other modes, as well. You can encrypt the entire file once in ECB, then twice in CBC; or

once in CBC, once in ECB, and once in CBC; or twice in CBC and once in ECB. Biham showed that

these variants are no more secure than single DES against a chosen-plaintext differential

cryptanalysis attack [162]. And he doesn™t have high hopes for any other variants. If you are going to

use triple encryption, use modes with outer feedback.

Variants on Triple Encryption

Before there were proofs that DES does not form a group, several schemes were proposed for multiple

encryption. One way to guarantee that triple encryption doesn™t reduce to single encryption is to

change the effective block size. One simple method is to add a bit of padding. Pad the text with a

string of random bits, half a block in length, between the first and second and between the second and

Page 300 of 666

Applied Cryptography: Second Edition - Bruce Schneier

third encryptions (see Figure 15.2). If p is the padding function, then:

C = EK3(p(EK2(p(EK1(P)))))

This padding not only disrupts patterns, but also overlaps encrypted blocks like bricks. It only adds

one block to the length of the message.

Another technique, proposed by Carl Ellison, is to use some kind of keyless permutation function

between the three encryptions. The permutation could work on large blocks”8 kilobytes or so”and

would effectively give this variant a block size of 8 kilobytes. Assuming that the permutation is fast,

this variant is not much slower than basic triple encryption.

C = EK3(T(EK2(T(EK1(P)))))

T collects a block of input (up to 8 kilobytes in length) and uses a pseudo-random-number generator

to transpose it. A 1-bit change in the input causes 8 changed output bytes after the first encryption, up

to 64 changed output bytes after the second encryption, and up to 512 changed output bytes after the

third encryption. If each block algorithm is in CBC mode, as originally proposed, then the effect of a

single changed input bit is likely to be the entire 8 kilobyte block, even in blocks other than the first.

Figure 15.2 Triple encryption with padding.

The most recent variant of this scheme responded to Biham™s attack on inner-CBC by including a

whitening pass to hide plaintext patterns. That pass is a stream XOR with a cryptographically secure

random-number generator called R below. The T on either side of it prevents the cryptanalyst from

knowing a priori which key was used to encrypt any given byte on input to the last encryption. The

second encryption is labelled nE (encryption with one of n different keys, used cyclically):

C = EK3(R(T(nEK2(T(EK1(R))))))

All encryptions are in ECB mode and keys are provided at least for the n + 2 encryption keys and the

cryptographically secure random-number generator.

This scheme was proposed with DES, but works with any block algorithm. I know of no analysis of

the security of this scheme.

15.3 Doubling the Block Length

There is some argument in the academic community whether a 64-bit block is long enough. On the

one hand, a 64-bit block length only diffuses plaintext over 8 bytes of ciphertext. On the other hand, a

longer block length makes it harder to hide patterns securely; there is more room to make mistakes.

Page 301 of 666

Applied Cryptography: Second Edition - Bruce Schneier

Some propose doubling the block length of an algorithm using multiple encryptions [299]. Before

implementing any of these, look for the possibility of meet-in-the-middle attacks. Richard

Outerbridge™s scheme [300], illustrated in Figure 15.3, is no more secure than single-block, two-key

triple encryption [859].

However, I advise against this sort of thing. It isn™t faster than conventional triple encryption: six

encryptions are still required to encrypt two blocks of data. We know the characteristics of triple

encryption; constructions like this often have hidden problems.

15.4 Other Multiple Encryption Schemes

The problem with two-key triple encryption is that it only doubles the size of the keyspace, but it

requires three encryptions per block of plaintext. Wouldn™t it be nice to find some clever way of

combining two encryptions that would double the size of the keyspace?

Double OFB/Counter

This method uses a block algorithm to generate two keystreams, which are then used to encrypt the

plaintext.

Si = EK1(Si - 1 I1); I1 = I1 + 1

Ti = EK2(Ti - 1 I2); I2 = I2 + 1

Ci = Pi Si Ti

Figure 15.3 Doubling the block length.

Si and Ti are internal variables, and I1 and I2 are counters. Two copies of the block algorithm run in a

kind of hybrid OFB/counter mode, and the plaintext, Si, and Ti are XORed together. The two keys, K1

and K2, are independent. I know of no cryptanalysis of this variant.

ECB + OFB

This method was designed for encrypting multiple messages of a fixed length, for example, disk blocks

[186,188]. Use two keys: K1 and K2. First, use the algorithm and K1 to generate a mask of the required

block length. This mask will be used repeatedly to encrypt messages with the same keys. Then, XOR

the plaintext message with the mask. Finally, encrypt the XORed plaintext with the algorithm and K2

Page 302 of 666

Applied Cryptography: Second Edition - Bruce Schneier

in ECB mode.

This mode has not been analyzed outside the paper in which it was proposed. Clearly it is at least as

strong as a single ECB encryption and may be as strong as two passes with the algorithm. Possibly, a

cryptanalyst could search for the two keys independently, if several known plaintext files are

encrypted with the same key.

To thwart analysis of identical blocks in the same positions of different messages, you can add an IV.

Unlike an IV in any other mode, here the IV is XORed with every block of the message before ECB

encryption.

Matt Blaze designed this mode for his UNIX Cryptographic File System (CFS). It is a nice mode

because the latency is only one encryption in ECB mode; the mask can be generated once and stored.

In CFS, DES is the block algorithm.

xDESi

In [1644,1645], DES is used as a building block for a series of block algorithms with both larger key

sizes and larger block sizes. These constructions do not depend on DES in any way and can be used

with any block algorithm.

The first, xDES1, is simply a Luby-Rackoff construction with the block cipher as the underlying

function (see Section 14.11). The block size is twice the size of the underlying block cipher and the key

size is three times the size of the underlying block cipher. In each of 3 rounds, encrypt the right half

with the block algorithm and one of the keys, XOR the result with the left half, and swap the two

halves.

This is faster than conventional triple encryption, since three encryptions encrypt a block twice as

large as the underlying algorithm. But there is also a simple meet-in-the-middle attack that finds the

key with a table the size of 2k, where k is the key size of the underlying algorithm. Encrypt the right

half of a plaintext block with all possible values of K1, XOR the left half of the plaintext, and store

these values in a table. Then, encrypt the right half of the ciphertext with all possible values of K3 and

look for a match in the table. If you find one, the key pair K1 and K3 are possible candidates for the

right key. Repeat the attack a few times, and only one candidate will remain. This shows that xDES1

is not an ideal solution. Even worse, there is a chosen plaintext attack that proves xDES1 is not much

stronger than the underlying block cipher [858].

xDES2 extends this idea to a 5-round algorithm with a block size 4 times that of the underlying block

cipher and a key size 10 times that of the underlying block cipher. Figure 15.4 is one round of xDES2;

each of the four sub-blocks are the size of the underlying block ciphers and all 10 keys are

independent.

This scheme is also faster than triple encryption: Ten encryptions are used to encrypt a block four

times the size of the underlying block cipher. However, it is vulnerable to differential cryptanalysis

[858] and should not be used. The scheme is even vulnerable if DES with independent round keys is

used.

Page 303 of 666

Applied Cryptography: Second Edition - Bruce Schneier

Figure 15.4 One round of xDES2.

For i G xDESi is probably too big to be useful as a block algorithm. For example, the block size for

G3,

xDES3 is 6 times that of the underlying cipher, the key size is 21 times, and 21 encryptions are

required to encrypt a block 6 times that of the underlying block cipher. Triple encryption is faster.

Quintuple Encryption

If triple encryption isn™t secure enough”perhaps you need to encrypt triple-encryption keys using an

even stronger algorithm”then higher multiples might be in order. Quintuple encryption is very

strong against meet-in-the-middle attacks. (Similar arguments to the ones used with double

encryption can show that quadruple encryption provides minimal security improvements over triple

encryption.)

C = EK1(DK2(EK3(DK2(EK1(P)))))

P = DK1(EK2(DK3(EK2(DK1(C)))))

This construction is backwards compatible with triple encryption if K2 = K3, and is backwards

compatible with single encryption if K1 = K2 = K3. Of course, it would be even stronger if all five keys

were independent.

15.5 CDMF Key Shortening

This method was designed by IBM for their Commercial Data Masking Facility or CDMF (see Section

24.8) to shrink a 56-bit DES key to a 40-bit key suitable for export [785]. It assumes that the original

DES key includes the parity bits.

(1) Zero the parity bits: bits 8, 16, 24, 32, 40, 48, 56, 64.

(2) Encrypt the output of step (1) with DES and the key 0xc408b0540ba1e0ae, and XOR

the result with the output of step (1).

(3) Take the output of step (2) and zero the following bits: 1, 2, 3, 4, 8, 16, 17, 18, 19, 20,

24, 32, 33, 34, 35, 36, 40, 48, 49, 50, 51, 52, 56, 64.

(4) Encrypt the output of step (3) with DES and the following key: 0xef2c041ce6382fe6.

This key is then used for message encryption.

Remember that this method shortens the key length, and thereby weakens the algorithm.

15.6 Whitening

Whitening is the name given to the technique of XORing some key material with the input to a block

algorithm, and XORing some other key material with the output. This was first done in the DESX

variant developed by RSA Data Security, Inc., and then (presumably independently) in Khufu and

Page 304 of 666

Applied Cryptography: Second Edition - Bruce Schneier

Khafre. (Rivest named this technique; it™s a nonstandard usage of the word.)

The idea is to prevent a cryptanalyst from obtaining a plaintext/ciphertext pair for the underlying

algorithm. The technique forces a cryptanalyst to guess not only the algorithm key, but also one of the

whitening values. Since there is an XOR both before and after the block algorithm, this technique is

not susceptible to a meet-in-the-middle attack.

C = K3 EK2(P K1 )

P = K1 DK2(C K3 )

If K1 = K3, then a brute-force attack requires 2n + m/p operations, where n is the key size, m is the

block size, and p is the number of known plaintexts. If K1 and K3 are different, then a brute-force

attack requires 2n + m + 1 operations with three known plaintexts. Against differential and linear

cryptanalysis, these measures only provide a few key bits of protection. But computationally this is a

very cheap way to increase the security of a block algorithm.

15.7 Cascading Multiple Block Algorithms

What about encrypting a message once with Algorithm A and key KA, then again with Algorithm B

and key KB? Maybe Alice and Bob have different ideas about which algorithms are secure: Alice

wants to use Algorithm A and Bob wants to use Algorithm B. This technique is sometimes called

cascading, and can be extended far beyond only two algorithms and keys.

Pessimists have said that there is no guarantee that the two algorithms will work together to increase

security. There may be subtle interactions between the two algorithms that actually decrease security.

Even triple encryption with three different algorithms may not be as secure as you think.

Cryptography is a black art; if you don™t know what you are doing, you can easily get into trouble.

Reality is much rosier. The previous warnings are true only if the different keys are related to each

other. If all of the multiple keys are independent, then the resultant cascade is at least as difficult to

break as the first algorithm in the cascade [1033]. If the second algorithm is vulnerable to a chosen-

plaintext attack, then the first algorithm might facilitate that attack and make the second algorithm

vulnerable to a known-plaintext attack when used in a cascade. This potential attack is not limited to

encryption algorithms: If you let someone else specify any algorithm which is used on your message

before encryption, then you had better be sure that your encryption will withstand a chosen-plaintext

attack. (Note that the most common algorithm used for compressing and digitizing speech to modem

speeds, used before any encryption, is CELP”designed by the NSA.)

This can be better phrased: Using a chosen-plaintext attack, a cascade of ciphers is at least as hard to

break as any of its component ciphers [858]. A previous result showed that the cascade is at least as

difficult to break as the strongest algorithm, but that result is based on some unstated assumptions

[528]. Only if the algorithms commute, as they do in the case of cascaded stream ciphers (or block

ciphers in OFB mode), is the cascade at least as strong as the strongest algorithm.

If Alice and Bob do not trust each other™s algorithms, they can use a cascade. If these are stream

algorithms, the order doesn™t matter. If they are block algorithms, Alice can first use Algorithm A and

then use Algorithm B. Bob, who trusts Algorithm B more, can use Algorithm B followed by Algorithm

A. They might even add a good stream cipher between the two algorithms; it can™t hurt and could

very well increase security.

Page 305 of 666

Applied Cryptography: Second Edition - Bruce Schneier

Remember that the keys for each algorithm in the cascade must be independent. If Algorithm A has a

64-bit key and Algorithm B has a 128-bit key, then the resultant cascade must have a 192-bit key. If

you don™t use independent keys, then the pessimists are much more likely to be right.

15.8 Combining Multiple Block Algorithms

Here™s another way to combine multiple block algorithms, one that is guaranteed to be at least as

secure as both algorithms. With two algorithms (and two independent keys):

(1) Generate a random-bit string, R, the same size as the message M.

(2) Encrypt R with the first algorithm.

(3) Encrypt M R with the second algorithm.

(4) The ciphertext message is the results of steps (2) and (3).

Assuming the random-bit string is indeed random, this method encrypts M with a one-time pad and

then encrypts both the pad and the encrypted message with each of the two algorithms. Since both are

required to reconstruct M, a cryptanalyst must break both algorithms. The drawback is that the

ciphertext is twice the size of the plaintext.

This method can be extended to multiple algorithms, but the ciphertext expands with each additional

algorithm. It™s a good idea, but I don™t think it™s very practical.

Chapter 16

Pseudo-Random-Sequence Generators and Stream Ciphers

16.1 Linear Congruential Generators

Linear congruential generators are pseudo-random-sequence generators of the form

Xn = (aXn-1 + b) mod m

in which Xn is the nth number of the sequence, and Xn-1 is the previous number of the sequence. The

variables a, b, and m are constants: a is the multiplier, b is the increment, and m is the modulus. The

key, or seed, is the value of X0.

This generator has a period no greater than m. If a, b, and m are properly chosen, then the generator

will be a maximal period generator (sometimes called maximal length) and have period of m. (For

example, b should be relatively prime to m.) Details on choosing constants to ensure maximal period

can be found in [863,942]. Another good article on linear congruential generators and their theory is

[1446].

Table 16.1, taken from [1272], gives a list of good constants for linear congruential generators. They

all produce maximal period generators and even more important, pass the spectral test for

randomness for dimensions 2, 3, 4, 5, and 6 [385,863]. They are organized by the largest product that

does not overflow a specific word length.

The advantage of linear congruential generators is that they are fast, requiring few operations per bit.

Page 306 of 666

Applied Cryptography: Second Edition - Bruce Schneier

Unfortunately, linear congruential generators cannot be used for cryptography; they are predictable.

Linear congruential generators were first broken by Jim Reeds [1294,1295,1296] and then by Joan

Boyar [1251]. She also broke quadratic generators:

Xn = (aXn-12 + bXn-1 + c) mod m

and cubic generators:

Xn = (aXn-13 + bXn-12 + cXn-1 + d) mod m

Other researchers extended Boyar™s work to break any polynomial congruential generator

[923,899,900]. Truncated linear congruential generators were also broken [581,705,580], as were

truncated linear congruential generators with unknown parameters [1500,212]. The preponderance of

evidence is that congruential generators aren™t useful for cryptography.

Table 16.1

Constants for Linear Congruential Generators

Overflow At: a b m

220 106 1283 6075

221 211 1663 7875

222 421 1663 7875

223 430 2531 11979

936 1399 6655

1366 1283 6075

224 171 11213 53125

859 2531 11979

419 6173 29282

967 3041 14406

225 141 28411 134456

625 6571 31104

1541 2957 14000

1741 2731 12960

1291 4621 21870

205 29573 139968

226 421 17117 81000

1255 6173 29282

281 28411 134456

227 1093 18257 86436

421 54773 259200

1021 24631 116640

1021 25673 121500

228 1277 24749 117128

Page 307 of 666

Applied Cryptography: Second Edition - Bruce Schneier

741 66037 312500

2041 25673 121500

229 2311 25367 120050

1807 45289 214326

1597 51749 244944

1861 49297 233280

2661 36979 175000

4081 25673 121500

3661 30809 145800

230 3877 29573 139968

3613 45289 214326

1366 150889 714025

231 8121 28411 134456

4561 51349 243000

7141 54773 259200

232 9301 49297 233280

4096 150889 714025

233 2416 374441 1771875

234 17221 107839 510300

36261 66037 312500

235 84589 45989 217728

Linear congruential generators remain useful for noncryptographic applications, however, such as

simulations. They are efficient and show good statistical behavior with respect to most reasonable

empirical tests. Considerable information on linear congruential generators and their

implementations can be found in [942].

Combining Linear Congruential Generators

Various people examined the combination of linear congruential generators [1595,941]. The results

are no more cryptographically secure, but the combinations have longer periods and perform better

in some randomness tests.

Use this generator for 32-bit computers [941]:

static long s1 = 1 ; /* A “long” must be 32 bits long. */ static long s2 = 1 ;

#define MODMULT(a,b,c,m,s) q = s/a; s = b*(s-a*q) - c*q; if (s<0) s+=m ;

/* MODMULT(a,b,c,m,s) computes s*b mod m, provided that m=a*b+c and 0 <= c < m. */

/* combinedLCG returns a pseudorandom real value in the range

* (0,1). It combines linear congruential generators with

* periods of 231-85 and 231-249, and has a period that is the

* product of these two prime numbers. */

double combinedLCG ( void )

{

long q ;

Page 308 of 666

Applied Cryptography: Second Edition - Bruce Schneier

long z ;

MODMULT ( 53668, 40014, 12211, 2147483563L, s1 )

MODMULT ( 52774, 40692, 3791, 2147483399L, s2 )

z = s1 - s2 ;

if ( z < 1 )

z += 2147483562 ;

return z * 4.656613e-10 ;

}

/* In general, call initLCG before using combinedLCG. */

void initLCG ( long InitS1, long InitS2 )

{

s1 = InitS1 ;

s2 = InitS2 ;

}

This generator works as long as the machine can represent all integers between-231 + 85 and 231 - 85.

The variables, s1 and s2, are global; they hold the current state of the generator. Before the first call,

they must be initialized. The variable s1 needs an initial value between 1 and 2147483562; the variable

s2 needs an initial value between 1 and 2147483398. The generator has a period somewhere in the

neighborhood of 1018.

If you only have a 16-bit computer, use this generator instead:

static int s1 = 1 ; /* An “int” must be 16 bits long. */

static int s2 = 1 ;

static int s3 = 1 ;

#define MODMULT(a,b,c,m,s) q = s/a; s = b*(s-a*q) - c*q; if

(s<0) s+=m ;

/* combined LCG returns a pseudorandom real value in the

range

* (0,1). It combines linear congruential generators with

* periods of 215-405, 215-1041, and 215-1111, and has a period

* that is the product of these three prime numbers. */

double combinedLCG ( void )

{

int q ;

int z ;

MODMULT ( 206, 157, 21, 32363, s1 )

MODMULT ( 217, 146, 45, 31727, s2 )

MODMULT ( 222, 142, 133, 31657, s3 )

z = s1 - s2 ;

if ( z > 706 )

z -= 32362 ;

z += s3 ;

if ( z < 1 )

z += 32362 ;

return z * 3.0899e-5 ;

}

/* In general, call initLCG before using combinedLCG. */

void initLCG ( int InitS1, int InitS2, InitS3 )

{

s1 = InitS1 ;

s2 = InitS2 ;

s3 = InitS3 ;

}

Page 309 of 666

Applied Cryptography: Second Edition - Bruce Schneier

This generator works as long as the machine can represent all integers between-32363 and 32363. The

variables, s1, s2, and s3, are global; they hold the current state of the generator. Before the first call,

they must be initialized. The variable s1 needs an initial value between 1 and 32362. The variable s2

needs an initial value between 1 and 31726. The variable s3 needs an initial value between 1 and

31656. This generator has a period of 1.6*1013.

For both of these generators, the constant term b in the linear congruence is 0.

16.2 Linear Feedback Shift Registers

Shift register sequences are used in both cryptography and coding theory. There is a wealth of theory

about them; stream ciphers based on shift registers have been the workhorse of military cryptography

since the beginnings of electronics.

A feedback shift register is made up of two parts: a shift register and a feedback function (see Figure

16.1). The shift register is a sequence of bits. (The length of a shift register is figured in bits; if it is n

bits long, it is called an n-bit shift register.) Each time a bit is needed, all of the bits in the shift register

are shifted 1 bit to the right. The new left-most bit is computed as a function of the other bits in the

register. The output of the shift register is 1 bit, often the least significant bit. The period of a shift

register is the length of the output sequence before it starts repeating.

Cryptographers have liked stream ciphers made up of shift registers: They are easily implemented in

digital hardware. I will only touch on the mathematical theory. Ernst Selmer, the Norwegian

government™s chief cryptographer, worked out the theory of shift register sequences in 1965 [1411].

Solomon Golomb, an NSA mathematician, wrote a book with Selmer™s results and some of his own

[643]. See also [970,971,1647].

The simplest kind of feedback shift register is a linear feedback shift register, or LFSR (see Figure

16.2). The feedback function is simply the XOR of certain bits in the register; the list of these bits is

called a tap sequence. Sometimes this is called a Fibonacci configuration. Because of the simple

feedback sequence, a large body of mathematical theory can be applied to analyzing LFSRs.

Cryptographers like to analyze sequences to convince themselves that they are random enough to be

secure. LFSRs are the most common type of shift registers used in cryptography.

Figure 16.3 is a 4-bit LFSR tapped at the first and fourth bit. If it is initialized with the value 1111, it

produces the following sequence of internal states before repeating:

1111

0111

1011

0101

1010

1101

0110

0011

1001

0100

0010

0001

1000

Page 310 of 666

Applied Cryptography: Second Edition - Bruce Schneier

1100

1110

Figure 16.1 Feedback shift register.

Figure 16.2 Linear feedback shift register.

The output sequence is the string of least significant bits:

1 1 1 1 0 1 0 1 1 0 0 1 0 0 0....

An n-bit LFSR can be in one of 2n - 1 internal states. This means that it can, in theory, generate a 2n -

1-bit-long pseudo-random sequence before repeating. (It™s 2n - 1 and not 2n because a shift register

filled with zeros will cause the LFSR to output a neverending stream of zeros”this is not particularly

useful.) Only LFSRs with certain tap sequences will cycle through all 2n - 1 internal states; these are

the maximal-period LFSRs. The resulting output sequence is called an m-sequence.

In order for a particular LFSR to be a maximal-period LFSR, the polynomial formed from a tap

sequence plus the constant 1 must be a primitive polynomial mod 2. The degree of the polynomial is

the length of the shift register. A primitive polynomial of degree n is an irreducible polynomial that

divides x2n-1 + 1, but not xd + 1 for any d that divides 2n - 1 (see Section 11.3). For the mathematical

theory behind all this, consult [643,1649,1648].

Figure 16.3 4-bit LFSR.

In general, there is no easy way to generate primitive polynomials mod 2 for a given degree. The

easiest way is to choose a random polynomial and test whether it is primitive. This is complicated”

something like testing random numbers for primality”but many mathematical software packages do

this. See [970,971] for some methods.

Table 16.2 lists some, but by no means all, primitive polynomials mod 2 of varying degrees

[1583,643,1649,1648,1272,691]. For example, the listing (32, 7, 5, 3, 2, 1, 0) means that the following

polynomial is primitive modulo 2:

x32 + x7 + x5 + x3 + x2 + x + 1

Page 311 of 666

Applied Cryptography: Second Edition - Bruce Schneier