<<

. 13
( 29)



>>


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


<<

. 13
( 29)



>>