ńňđ. 15 |

Applied Cryptography: Second Edition - Bruce Schneier

349 1213 2099 3037 4019

373 1229 2131 3067 4021

379 1237 2141 3083 4091

389 1259 2213 3187 4093

419 1277 2221 3203 4099

421 1283 2237 3253 4133

443 1291 2243 3299 4139

461 1301 2267 3307 4157

467 1307 2269 3323 4219

491 1373 2293 3347 4229

509 1381 2309 3371 4243

523 1427 2333 3413 4253

541 1451 2339 3461 4259

547 1453 2357 3467 4261

557 1483 2371 3469 4283

563 1493 2389 3491 4349

587 1499 2437 3499 4357

613 1523 2459 3517 4363

619 1531 2467 3533 4373

4397 5693 6781 7717 8861

4451 5701 6803 7757 8867

4483 5717 6827 7789 8923

4493 5741 6829 7829 8933

4507 5749 6869 7853 8963

4517 5779 6883 7877 8971

4547 5813 6899 7883 9011

4603 5827 6907 7901 9029

4621 5843 6917 7907 9059

4637 5851 6947 7933 9173

4691 5869 6949 7949 9181

4723 5923 6971 8053 9203

4787 5939 7013 8069 9221

4789 5987 7019 8093 9227

4813 6011 7027 8117 9283

4877 6029 7043 8123 9293

4933 6053 7069 8147 9323

4957 6067 7109 8171 9341

4973 6101 7187 8179 9349

4987 6131 7211 8219 9371

5003 6173 7219 8221 9397

5011 6197 7229 8237 9419

5051 6203 7237 8243 9421

5059 6211 7243 8269 9437

5077 6229 7253 8291 9467

Page 337 of 666

Applied Cryptography: Second Edition - Bruce Schneier

5099 6269 7283 8293 9491

5107 6277 7307 8363 9533

5147 6299 7331 8387 9539

5171 6317 7349 8429 9547

5179 6323 7411 8443 9587

5189 6373 7451 8467 9613

5227 6379 7459 8539 9619

5261 6389 7477 8563 9629

5309 6397 7499 8573 9643

5333 6469 7507 8597 9661

5387 6491 7517 8627 9677

5443 6547 7523 8669 9733

5477 6619 7541 8677 9749

5483 6637 7547 8693 9803

5501 6653 7549 8699 9851

5507 6659 7573 8731 9859

5557 6691 7589 8741 9883

5563 6701 7603 8747 9901

5573 6709 7621 8803 9907

5651 6733 7643 8819 9923

5659 6763 7669 8821 9941

5683 6779 7691 8837 9949

Table 17.2

Tap Sequences for Maximal-length FCSRs

(32, 6, 3, 2) (64, 24, 19, 2) (64, 59, 28, 2) (96, 55, 53, 2)

(32, 7, 5, 2) (64, 25, 3, 2) (64, 59, 38, 2) (96, 56, 9, 2)

(32, 8, 3, 2) (64, 25, 4, 2) (64, 59, 44, 2) (96, 56, 51, 2)

(32, 13, 8, 2) (64, 25, 11, 2) (64, 60, 49, 2) (96, 57, 3, 2)

(32, 13, 12, 2) (64, 25, 19, 2) (64, 61, 51, 2) (96, 57, 17, 2)

(32, 15, 6, 2) (64, 27, 5, 2) (64, 63, 8, 2) (96, 57, 47, 2)

(32, 16, 2, 1) (64, 27, 16, 2) (64, 63, 13, 2) (96, 58, 35, 2)

(32, 16, 3, 2) (64, 27, 22, 2) (64, 63, 61, 2) (96, 59, 46, 2)

(32, 16, 5, 2) (64, 28, 19, 2) (96, 60, 29, 2)

(32, 17, 5, 2) (64, 28, 25, 2) (96, 15, 5, 2) (96, 60, 41, 2)

(32, 19, 2, 1) (64, 29, 16, 2) (96, 21, 17, 2) (96, 60, 45, 2)

(32, 19, 5, 2) (64, 29, 28, 2) (96, 25, 19, 2) (96, 61, 17, 2)

(32, 19, 9, 2) (64, 31, 12, 2) (96, 25, 20, 2) (96, 63, 20, 2)

(32, 19, 12, 2) (64, 32, 21, 2) (96, 29, 15, 2) (96, 65, 12, 2)

(32, 19, 17, 2) (64, 35, 29, 2) (96, 29, 17, 2) (96, 65, 39, 2)

(32, 20, 17, 2) (64, 36, 7, 2) (96, 30, 3, 2) (96, 65, 51, 2)

(32, 21, 9, 2) (64, 37, 2, 1) (96, 32, 21, 2) (96, 67, 5, 2)

Page 338 of 666

Applied Cryptography: Second Edition - Bruce Schneier

(32, 21, 15, 2) (64, 37, 11, 2) (96, 32, 27, 2) (96, 67, 25, 2)

(32, 23, 8, 2) (64, 39, 4, 2) (96, 33, 5, 2) (96, 67, 34, 2)

(32, 23, 21, 2) (64, 39, 25, 2) (96, 35, 17, 2) (96, 68, 5, 2)

(32, 25, 5, 2) (64, 41, 5, 2) (96, 35, 33, 2) (96, 68, 19, 2)

(32, 25, 12, 2) (64, 41, 11, 2) (96, 39, 21, 2) (96, 69, 17, 2)

(32, 27, 25, 2) (64, 41, 27, 2) (96, 40, 25, 2) (96, 69, 36, 2)

(32, 29, 19, 2) (64, 43, 21, 2) (96, 41, 12, 2) (96, 70, 23, 2)

(32, 29, 20, 2) (64, 43, 28, 2) (96, 41, 27, 2) (96, 71, 6, 2)

(32, 30, 3, 2) (64, 45, 28, 2) (96, 41, 35, 2) (96, 71, 40, 2)

(32, 30, 7, 2) (64, 45, 41, 2) (96, 42, 35, 2) (96, 72, 53, 2)

(32, 31, 5, 2) (64, 47, 5, 2) (96, 43, 14, 2) (96, 73, 32, 2)

(32, 31, 9, 2) (64, 47, 21, 2) (96, 44, 23, 2) (96, 77, 27, 2)

(32, 31, 30, 2) (64, 47, 30, 2) (96, 45, 41, 2) (96, 77, 31, 2)

(64, 49, 19, 2) (96, 47, 36, 2) (96, 77, 32, 2)

(64, 3, 2, 1) (64, 49, 20, 2) (96, 49, 31, 2) (96, 77, 33, 2)

(64, 14, 3, 2) (64, 52, 29, 2) (96, 51, 30, 2) (96, 77, 71, 2)

(64, 15, 8, 2) (64, 53, 8, 2) (96, 53, 17, 2) (96, 78, 39, 2)

(64, 17, 2, 1) (64, 53, 43, 2) (96, 53, 19, 2) (96, 79, 4, 2)

(64, 17, 9, 2) (64, 56, 39, 2) (96, 53, 32, 2) (96, 81, 80, 2)

(64, 17, 16, 2) (64, 56, 45, 2) (96, 53, 48, 2) (96, 83, 14, 2)

(64, 19, 2, 1) (64, 59, 5, 2) (96, 54, 15, 2) (96, 83, 26, 2)

(64, 19, 18, 2) (64, 59, 8, 2) (96, 55, 44, 2) (96, 83, 54, 2)

(96, 83, 60, 2) (128, 31, 25, 2) (128, 81, 55, 2) (128, 105, 11, 2)

(96, 83, 65, 2) (128, 33, 21, 2) (128, 82, 67, 2) (128, 105, 31, 2)

(96, 83, 78, 2) (128, 35, 22, 2) (128, 83, 60, 2) (128, 105, 48, 2)

(96, 84, 65, 2) (128, 37, 8, 2) (128, 83, 61, 2) (128, 107, 40, 2)

(96, 85, 17, 2) (128, 41, 12, 2) (128, 83, 77, 2) (128, 107, 62, 2)

(96, 85, 31, 2) (128, 42, 35, 2) (128, 84, 15, 2) (128,, 107102, 2)

(96, 85, 76, 2) (128, 43, 25, 2) (128, 84, 43, 2) (128, 108, 35, 2)

(96, 85, 79, 2) (128, 43, 42, 2) (128, 85, 63, 2) (128, 108, 73, 2)

(96, 86, 39, 2) (128, 45, 17, 2) (128, 87, 57, 2) (128, 108, 75, 2)

(96, 86, 71, 2) (128, 45, 27, 2) (128, 87, 81, 2) (128, 108, 89, 2)

(96, 87, 9, 2) (128, 49, 9, 2) (128, 89, 81, 2) (128, 109, 11, 2)

(96, 87, 44, 2) (128, 51, 9, 2) (128, 90, 43, 2) (128,, 109108, 2)

(96, 87, 45, 2) (128, 54, 51, 2) (128, 91, 9, 2) (128, 110, 23, 2)

(96, 88, 19, 2) (128, 55, 45, 2) (128, 91, 13, 2) (128, 111, 61, 2)

(96, 88, 35, 2) (128, 56, 15, 2) (128, 91, 44, 2) (128, 113, 59, 2)

(96, 88, 43, 2) (128, 56, 19, 2) (128, 92, 35, 2) (128, 114, 83, 2)

(96, 88, 79, 2) (128, 56, 55, 2) (128, 95, 94, 2) (128, 115, 73, 2)

(96, 89, 35, 2) (128, 57, 21, 2) (128, 96, 23, 2) (128,, 117105, 2)

(96, 89, 51, 2) (128, 57, 37, 2) (128, 96, 61, 2) (128, 119, 30, 2)

(96, 89, 69, 2) (128, 59, 29, 2) (128, 97, 25, 2) (128,, 119101, 2)

(96, 89, 87, 2) (128, 59, 49, 2) (128, 97, 68, 2) (128, 120, 9, 2)

(96, 92, 51, 2) (128, 60, 57, 2) (128, 97, 72, 2) (128, 120, 27, 2)

Page 339 of 666

Applied Cryptography: Second Edition - Bruce Schneier

(96, 92, 71, 2) (128, 61, 9, 2) (128, 97, 75, 2) (128, 120, 37, 2)

(96, 93, 32, 2) (128, 61, 23, 2) (128, 99, 13, 2) (128, 120, 41, 2)

(96, 93, 39, 2) (128, 61, 52, 2) (128, 99, 14, 2) (128, 120, 79, 2)

(96, 94, 35, 2) (128, 63, 40, 2) (128, 99, 26, 2) (128, 120, 81, 2)

(96, 95, 4, 2) (128, 63, 62, 2) (128, 99, 54, 2) (128, 121, 5, 2)

(96, 95, 16, 2) (128, 67, 41, 2) (128, 99, 56, 2) (128, 121, 67, 2)

(96, 95, 32, 2) (128, 69, 33, 2) (128, 99, 78, 2) (128, 121, 95, 2)

(96, 95, 44, 2) (128, 71, 53, 2) (128, 100, 13, 2) (128, 121, 96, 2)

(96, 95, 45, 2) (128, 72, 15, 2) (128, 100, 39, 2) (128, 123, 40, 2)

(128, 72, 41, 2) (128, 101, 44, 2) (128, 123, 78, 2)

(128, 5, 4, 2) (128, 73, 5, 2) (128, 101, 97, 2) (128, 124, 41, 2)

(128, 15, 4, 2) (128, 73, 65, 2) (128, 103, 46, 2) (128, 124, 69, 2)

(128, 21, 19, 2) (128, 73, 67, 2) (128, 104, 13, 2) (128, 124, 81, 2)

(128, 25, 5, 2) (128, 75, 13, 2) (128, 104, 19, 2) (128, 125, 33, 2)

(128, 26, 11, 2) (128, 80, 39, 2) (128, 104, 35, 2) (128, 125, 43, 2)

(128, 27, 25, 2) (128, 80, 53, 2) (128, 105, 7, 2) (128, 127, 121, 2)

Figure 17.5 Combining Generators.

LFSR/FCSR Summation/Parity Cascade

The theory is that addition with carry destroys the algebraic properties of LFSRs, and that XOR

destroys the algebraic properties of FCSRs. This generator combines those ideas, as used in the

LFSR/FCSR Summation Generator and the LFSR/FCSR Parity Generator just listed, with the

Gollmann cascade.

The generator is a series of arrays of registers, with the clock of each array controlled by the output of

the previous array. Figure 17.6 is one stage of this generator. The first array of LFSRs is clocked and

the results are combined using addition with carry. If the output of this combining function is 1, then

the next array (of FCSRs) is clocked and the output of those FCSRs is combined with the output of

the previous combining function using XOR. If the output of the first combining function is 0, then

the array of FCSRs is not clocked and the output is simply added to the carry from the previous

round. If the output of this second combining function is 1, then the third array of LFSRs is clocked,

and so on.

This generator uses a lot of registers: n*m, where n is the number of stages and m is the number of

registers per stage. I recommend n = 10 and m = 5.

Alternating Stop-and-Go Generators

Page 340 of 666

Applied Cryptography: Second Edition - Bruce Schneier

These generators are stop-and-go generators with FCSRs instead of some LFSRs. Additionally, the

XOR operation can be replaced with an addition with carry (see Figure 17.7).

â€” FCSR Stop-and-Go Generator. Register-1, Register-2, and Register-3 are FCSRs. The

combining operation is XOR.

â€” FCSR/LFSR Stop-and-Go Generator. Register-1 is a FCSR, and Registers-2 and -3 are

LFSRs. The combining operation is addition with carry.

Figure 17.6 Concoction Generator.

â€” LFSR/FCSR Stop-and-Go Generator. Register-1 is a LFSR, and Registers-2 and -3 are

FCSRs. The combining operation is XOR.

Shrinking Generators

There are four basic generator types using FCSRs:

â€” FCSR Shrinking Generator. A shrinking generator with FCSRs instead of LFSRs.

â€” FCSR/LFSR Shrinking Generator. A shrinking generator with a LFSR shrinking a

FCSR.

â€” LFSR/FCSR Shrinking Generator: A shrinking generator with a FCSR shrinking a

LFSR.

Figure 17.7 Alternating stop-and-go generators.

â€” FCSR Self-Shrinking Generator. A self-shrinking generator with a FCSR instead of a

LFSR.

17.6 Nonlinear-Feedback Shift Registers

It is easy to imagine a more complicated feedback sequence than the ones used in LFSRs or FCSRs.

The problem is that there isnâ€™t any mathematical theory that can analyze them. Youâ€™ll get something,

but who knows what it is? In particular, here are some problems with nonlinear-feedback shift

register sequences.

â€” There may be biases, such as more ones than zeros or fewer runs than expected, in the

output sequence.

Page 341 of 666

Applied Cryptography: Second Edition - Bruce Schneier

â€” The maximum period of the sequence may be much lower than expected.

â€” The period of the sequence might be different for different starting values.

â€” The sequence may appear random for a while, but then â€śdead endâ€ť into a single value.

(This can easily be solved by XORing the nonlinear function with the rightmost bit.)

On the plus side, if there is no theory to analyze nonlinear-feedback shift registers for security, there

are few tools to cryptanalyze stream ciphers based on them. We can use nonlinear-feedback shift

registers in stream-cipher design, but we have to be careful.

In a nonlinear-feedback shift register, the feedback function can be anything you want (see Figure

17.8).

Figure 17.8 A nonlinear-feedback shift register (probably insecure).

Figure 17.9 3-bit nonlinear feedback shift register.

Figure 17.9 is a 3-bit shift register with the following feedback function: The new bit is the first bit

times the second bit. If it is initialized with the value 110, it produces the following sequence of

internal states:

110

011

101

010

001

000

000

And so on forever.

The output sequence is the string of least significant bits:

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

This isnâ€™t terribly useful.

It gets even worse. If the initial value is 100, it produces 010, 001, then repeats forever at 000. If the

initial value is 111, it repeats itself forever right from the start.

Some work has been done on computing the linear complexity of the product of two LFSRs

[1650,726,1364,630,658,659]. A construction that involved computing LFSRs over a field of odd

Page 342 of 666

Applied Cryptography: Second Edition - Bruce Schneier

characteristic [310] is insecure [842].

17.7 Other Stream Ciphers

Many other stream ciphers have appeared in the literature here and there. Here are some of them.

Pless Generator

This generator is designed around the capabilities of the J-K flip-flop [1250]. Eight LFSRs drive four

J-K flip-flops; each flip-flop acts as a nonlinear combiner for two of the LFSRs. To avoid the problem

that knowledge of an output of the flip-flop identifies both the source and value of the next output bit,

clock the four flip-flops and then interleave the outputs to yield the final keystream.

This algorithm has been cryptanalyzed by attacking each of the four flip-flops independently [1356].

Additionally, combining J-K flip-flops is cryptographically weak; generators of this type succumb to

correlation attacks [1451].

Cellular Automaton Generator

In [1608,1609], Steve Wolfram proposed using a one-dimensional cellular automaton as a pseudo-

random-number generator. Cellular automata is not the subject of this book, but Wolframâ€™s

generator consisted of a one-dimensional array of bits, a1, a2, a3,..., ak,..., an, and an update function:

aâ€˜k = ak-1 (ak ak+1)

The bit is extracted from one of the ak values; which one really doesnâ€™t matter.

The generatorâ€™s behavior appears to be quite random. However, there is a known-plaintext attack

against these generators [1052]. This attack works on a PC with values of n up to 500 bits.

Additionally, Paul Bardell proved that the output of a cellular automaton can also be generated by a

linear-feedback shift register of equal length and is therefore no more secure [83].

1/p Generator

This generator was proposed, and then cryptanalyzed, in [193]. If the internal state of the generator at

time t is xt, then

xt+1 = bxt mod p

The output of the generator is the least significant bit of xt div p, where div is the truncated integer

division. For maximum period, the constants b and p should be chosen so that p is prime and b is a

primitive root mod p. Unfortunately, this generator isnâ€™t secure. (Note that for b = 2, an FCSR with a

connection integer p outputs the reverse of this sequence.)

crypt(1)

The original UNIX encryption algorithm, crypt(1), is a stream cipher based on the same ideas as the

Enigma. This is a 256-element, single-rotor substitution cipher with a reflector. Both the rotor and the

reflector are generated from the key. This algorithm is far simpler than the World War II German

Page 343 of 666

Applied Cryptography: Second Edition - Bruce Schneier

Enigma and, for a skilled cryptanalyst, very easy to break [1576,1299]. A public-domain UNIX

program, called Crypt Breakers Workbench (CBW), can be used to break files encrypted with crypt

(1).

Other Schemes

Another generator is based on the knapsack problem (see Section 19.2) [1363]. CRYPTO-LEGGO is

insecure [301]. Joan Daemen has developed SubStream, Jam, and StepRightUp [402]; they are all too

new to comment on. Many other algorithms are described in the literature, and even more are kept

secret and incorporated into equipment.

17.8 System-Theoretic Approach to Stream-Cipher Design

In practice, stream-cipher design is a lot like block-cipher design. It involves more mathematical

theory, but in the end a cryptographer proposes a design and then tries to analyze it.

According to Rainer Rueppel, there are four different approaches to the construction of stream

ciphers [1360,1362]:

â€” System-theoretic approach. Try to make sure that each design creates a difficult and

unknown problem for the cryptanalyst, using a set of fundamental design principles and

criteria.

â€” Information-theoretic approach. Try to keep the cryptanalyst in the dark about the

plaintext. No matter how much work the cryptanalyst invests, he will never get a unique

solution.

â€” Complexity-theoretic approach. Try to base the cryptosystem on, or make it equivalent

to, some known and difficult problem such as factoring or taking discrete logarithms.

â€” Randomized approach. Try to generate an unmanageably large problem by forcing the

cryptanalyst to examine lots of useless data in his attempts at cryptanalysis.

The approaches differ in their assumptions about the capabilities and opportunities of the

cryptanalyst, the definition of cryptographic success, and the notion of security. Most of the research

in this field is theoretical, but there are some good stream ciphers among the impractical ones.

The system-theoretic approach was used in all the stream ciphers previously listed; it produces most

of the stream ciphers that are practical enough to be used in the real world. A cryptographer designs

keystream generators that have testable security propertiesâ€”period, distribution of bit patterns,

linear complexity, and so onâ€”and not ciphers based on mathematical theory. The cryptographer also

studies various cryptanalytic techniques against these generators and makes sure the generators are

immune to these attacks.

Over the years, the approach has resulted in a set of design criteria for stream ciphers

[1432,99,1357,1249]. These were discussed by Rueppel in [1362], in which he details the theory behind

them.

â€” Long period, no repetitions.

â€” Linear complexity criteriaâ€”large linear complexity, linear complexity profile, local

linear complexity, and so forth.

â€” Statistical criteria such as ideal k-tuple distributions.

â€” Confusionâ€”every keystream bit must be a complex transformation of all or most of the

key bits.

â€” Diffusionâ€”redundancies in substructures must be dissipated into long-range statistics.

Page 344 of 666

Applied Cryptography: Second Edition - Bruce Schneier

â€” Nonlinearity criteria for Boolean functions like mth-order correlation immunity,

distance to linear functions, avalanche criterion, and so on.

This list of design criteria is not unique for stream ciphers designed by the system-theoretic approach;

it is true for all stream ciphers. It is even true for all block ciphers. The unique point about the

system-theoretic approach is that stream ciphers are designed to satisfy these goals directly.

The major problem with these cryptosystems is that nothing can be proven about their security; the

design criteria have never been proved to be either necessary or sufficient for security. A keystream

generator may satisfy all the design principles, but could still turn out to be insecure. Another could

turn out to be secure. There is still some magic to the process.

On the other hand, breaking each of these keystream generators is a different problem for a

cryptanalyst. If enough different generators are out there, it may not be worth the cryptanalystâ€™s time

to try to break each one. He may better achieve fame and glory by figuring out better ways to factor

large numbers or calculating discrete logarithms.

17.9 Complexity-Theoretic Approach to Stream-Cipher Design

Rueppel also delineated a complexity-theoretic approach to stream-cipher design. Here, a

cryptographer attempts to use complexity theory to prove that his generators are secure.

Consequently, the generators tend to be more complicated, based on the same sorts of hard problems

as public-key cryptography. And like public-key algorithms, they tend to be slow and cumbersome.

Shamirâ€™s Pseudo-Random-Number Generator

Adi Shamir used the RSA algorithm as a pseudo-random-number generator [1417]. While Shamir

showed that predicting the output of the pseudo-random-number generator is equivalent to breaking

RSA, potential biases in the output were demonstrated in [1401,200].

Blum-Micali Generator

This generator gets its security from the difficulty of computing discrete logarithms [200]. Let g be a

prime and p be an odd prime. A key x0, starts off the process:

xi+1 = gxi mod p

The output of the generator is 1 if xi < (p - 1)/2, and 0 otherwise.

If p is large enough so that computing discrete logarithms mod p is infeasible, then this generator is

secure. Additional theoretical results can be found in [1627,986,985,1237,896,799].

RSA

This RSA generator [35,36] is a modification of [200]. The initial parameters are a modulus N which

is the product of two large primes p and q, an integer e which is relatively prime to (p - 1) (q - 1), and a

random seed x0, where x0 is less than N.

xi+1 = xei mod N

Page 345 of 666

Applied Cryptography: Second Edition - Bruce Schneier

The output of the generator is the least significant bit of xi. The security of this generator is based on

the difficulty of breaking RSA. If N is large enough, then the generator is secure. Additional theory

can be found in [1569,1570,1571,30,354].

Blum, Blum, and Shub

The simplest and most efficient complexity-theoretic generator is called the Blum, Blum, and Shub

generator, after its inventors. Mercifully, we shall abbreviate it to BBS, although it is sometimes called

the quadratic residue generator [193].

The theory behind the BBS generator has to do with quadratic residues modulo n (see Section 11.3).

Hereâ€™s how it works.

First find two large prime numbers, p and q, which are congruent to 3 modulo 4. The product of those

numbers, n, is a Blum integer. Choose another random integer, x, which is relatively prime to n.

Compute

x0 = x2 mod n

Thatâ€™s the seed for the generator.

Now you can start computing bits. The ith pseudo-random bit is the least significant bit of xi, where

xi = xi-12 mod n

The most intriguing property of this generator is that you donâ€™t have to iterate through all i - 1 bits to

get the ith bit. If you know p and q, you can compute the ith bit directly.

bi is the least significant bit of xi, where xi = x0(2i) mod ((p-1)(q-1))

This property means you can use this cryptographically strong pseudo-random-bit generator as a

stream cryptosystem for a random-access file.

The security of this scheme rests on the difficulty of factoring n. You can make n public, so anyone

can generate bits using the generator. However, unless a cryptanalyst can factor n, he can never

predict the output of the generatorâ€”not even with a statement like: â€śThe next bit has a 51 percent

chance of being a 1.â€ť

More strongly, the BBS generator is unpredictable to the left and unpredictable to the right. This

means that given a sequence generated by the generator, a cryptanalyst cannot predict the next bit in

the sequence nor the previous bit in the sequence. This is not security based on some complicated bit

generator that no one understands, but the mathematics behind factoring n.

This algorithm is slow, but there are speedups. As it turns out, you can use more than the least

significant bit of each xi as a pseudo-random bit. According to [1569,1570,1571,35,36], if n is the

length of xi, the least significant log2n bits of xi can be used. The BBS generator is comparatively slow

and isnâ€™t useful for stream ciphers. However, for high-security applications, such as key generation,

Page 346 of 666

Applied Cryptography: Second Edition - Bruce Schneier

this generator is the best of the lot.

17.10 Other Approaches to Stream-Cipher Design

In an information-theoretic approach to stream ciphers, the cryptanalyst is assumed to have

unlimited time and computing power. The only practical stream cipher that is secure against an

adversary like this is a one-time pad (see Section 1.5). Since bits would be impractical on a pad, this is

sometimes called a one-time tape. Two magnetic tapes, one at the encryption end and the other at the

decryption end, would have the same random keystream on them. To encrypt, simply XOR the

plaintext with the bits on the tape. To decrypt, XOR the ciphertext with the bits on the other,

identical, tape. You never use the same keystream bits twice. Since the keystream bits are truly

random, no one can predict the keystream. If you burn the tapes when you are through with them,

youâ€™ve got perfect secrecy (assuming no one else has copies of the tape).

Another information-theoretic stream cipher, developed by Claus Schnorr, assumes that the

cryptanalyst only has access to a limited number of ciphertext bits [1395]. The results are highly

theoretical and have no practical value, at least not yet. For more details, consult [1361,1643,1193].

In a randomized stream cipher, the cryptographer tries to ensure that the cryptanalyst has an

infeasibly large problem to solve. The objective is to increase the number of bits the cryptanalyst has

to work with, while keeping the secret key small. This can be done by making use of a large public

random string for encryption and decryption. The key would specify which parts of the large random

string are to be used for encryption and decryption. The cryptanalyst, not knowing the key, is forced

to pursue a brute-force search through the random string. The security of this sort of cipher can be

expressed by the average number of bits a cryptanalyst must examine before the chances of

determining the key improve over pure guessing.

Rip van Winkle Cipher

James Massey and Ingemar Ingemarsson proposed the Rip van Winkle cipher [1011], so named

because the receiver has to receive 2n bits of ciphertext before attempting decryption. The algorithm,

illustrated in Figure 17.10, is simple to implement, provably secure, and completely impractical.

Simply XOR the plaintext with the keystream, and delay the keystream by 0 to 20 yearsâ€”the exact

delay is part of the key. In Masseyâ€™s words: â€śOne can easily guarantee that the enemy cryptanalyst

will need thousands of years to break the cipher, if one is willing to wait millions of years to read the

plaintext.â€ť Further work on this idea can be found in [1577,755].

Figure 17.10 Rip van Winkle cipher.

Diffieâ€™s Randomized Stream Cipher

This scheme was first proposed by Whitfield Diffie [1362]. The data are 2n random sequences. The

key is k, a random n-bit string. To encrypt a message, Alice uses the kth random string as a one-time

pad. She then sends the ciphertext plus the 2n random strings over 2n + 1 different communications

channels.

Page 347 of 666

Applied Cryptography: Second Edition - Bruce Schneier

Bob knows k, so he can easily choose which one-time pad to decrypt the message with. Eve has no

choice but to examine the random sequences one at a time until she finds the correct one-time pad.

Any attack must examine an expected number of bits which is in O(2n). Rueppel points out that if you

send n random strings instead of 2n, and if the key is used to specify a linear combination of those

random strings, the security is the same.

Maurerâ€™s Randomized Stream Cipher

Ueli Maurer described a scheme based on XORing the plaintext with several large public random-bit

sequences [1034,1029,1030]. The key is the set of starting positions within each sequence. This turns

out to be provably almost secure, with a calculable probability of being broken based on how much

memory the attacker has at his disposal, without regard to the amount of computing power he has.

Maurer claims that this scheme would be practical with about 100 different sequences of 1020 random

bits each. Digitizing the face of the moon might be one way to get this many bits.

17.11 Cascading Multiple Stream Ciphers

If performance is no issue, thereâ€™s no reason not to choose multiple stream ciphers and cascade them.

Simply XOR the output of each generator with the plaintext to get the ciphertext. Ueli Maurerâ€™s result

(see Section 15.7) says that if the generators have independent keys, then the security of the cascade is

at least as secure as the strongest algorithm in the cascade. It is probably much more secure than that.

Stream ciphers can be combined in all the same ways as block ciphers (see Chapter 15). Stream

ciphers can be cascaded (see Section 15.7) with other stream ciphers, or together with block ciphers.

A clever trick is to use one algorithm, either a block or stream algorithm, to frequently rekey a fast

stream algorithm (which could even be a block algorithm in OFB mode). The fast algorithm could be

weak, since a cryptanalyst would never see very much plaintext encrypted with any one key.

Thereâ€™s a trade-off between the size of the fast algorithmâ€™s internal state (which may impact security)

and how often you can afford to rekey. The rekey needs to be relatively fast; algorithms that have a

long key setup routine arenâ€™t suitable for this kind of application. And the rekeying should be

independent of the internal state of the fast algorithm.

17.12 Choosing a Stream Cipher

If the study of stream ciphers offers any lessons, itâ€™s that new types of attacks are invented with

alarming regularity. Classically, stream ciphers have been based on considerable mathematical

theory. This theory can be used to prove good properties about the cipher, but can also be used to find

new attacks against the cipher. I worry about any stream cipher based solely on LFSRs for this

reason.

I prefer stream ciphers that are designed more along the lines of block ciphers: nonlinear

transformations, large S-boxes, and so on. RC4 is my favorite, and SEAL is a close second. I would be

very interested in seeing cryptanalytic results against my generators that combine LFSRs and FCSRs;

this seems to be a very fruitful area of stream-cipher research to mine for actual designs. Or, you can

use a block cipher in OFB or CFB to get a stream cipher.

Table 17.3 gives some timing measurements for some algorithms. These are meant for comparison

purposes only.

Page 348 of 666

Applied Cryptography: Second Edition - Bruce Schneier

17.13 Generating Multiple Streams from a Single Pseudo-Random-Sequence Generator

If you need to encrypt multiple channels of communications in a single boxâ€”a multiplexer, for

exampleâ€”the easy solution is to use a different pseudo-random-sequence generator for each stream.

This has two problems: It requires more hardware, and all the different generators have to be

synchronized. It would be simpler to use a single generator.

Table 17.3

Encryption Speeds of Some Stream Ciphers on a 33MHz

486SX

Algorithm Encryption Speed (Kilobytes/Second)

A5 5

PIKE 62

RC4 164

SEAL 381

One solution is to clock the generator multiple times. If you want three independent streams, clock the

generator three times and send 1 bit into each stream. This technique works, but you may have

trouble clocking the generator as fast as you would like. For example, if you can only clock the

generator three times as fast as the data stream, you can only create three streams. Another way is to

use the same sequence for each channelâ€”perhaps with a variable time delay. This is insecure.

A really clever idea [1489], patented by the NSA, is shown in Figure 17.11. Dump the output of your

favorite generator into an m-bit simple shift register. At each clock pulse, shift the register one to the

right. Then, for each output stream, AND the register with a different m-bit control vector viewed as a

unique identifier for the desired output stream, then XOR all the bits together to get the output bit for

that stream. If you want several output streams in parallel, you need a separate control vector and an

XOR/AND logic array for each output stream.

There are some things to watch out for. If any of the streams are linear combinations of other

streams, then the system can be broken. But if you are clever, this is an easy and secure way to solve

the problem.

17.14 Real Random-Sequence Generators

Sometimes cryptographically secure pseudo-random numbers are not good enough. Many times in

cryptography, you want real random numbers. Key generation is a prime example. Itâ€™s fine to

generate random cryptographic keys based on a pseudo-random sequence generator, but if an

adversary gets a copy of that generator and the master key, the adversary can create the same keys

and break your cryptosystem, no matter how secure your algorithms are. A random-sequence

generatorâ€™s sequences cannot be reproduced. No one, not even you, can reproduce the bit sequence

out of those generators.

Page 349 of 666

Applied Cryptography: Second Edition - Bruce Schneier

Figure 17.11 Multiple-bit generator.

There is a large philosophical debate over whether any of these techniques actually produces real

random bits. I am not going to address that debate. The point here is to produce bits that have the

same statistical properties as random bits and are not reproducible.

The important thing about any real random-sequence generator is that it be tested. There is a wealth

of literature on this topic. Tests of randomness can be found in [863,99]. Maurer showed that all these

tests can be derived from trying to compress the sequence [1031,1032]. If you can compress a random

sequence, then it is not truly random.

Anyhow, what we have here is a whole lot of black magic. The primary point is to generate a sequence

of bits that your adversary is unlikely to guess. It doesnâ€™t sound like much, but itâ€™s harder than you

think. I canâ€™t prove that any of these techniques generates random bits. These techniques produce a

sequence of bits that cannot be easily reproduced. For some details, see [1375,1376,511].

RAND Tables

Back in 1955, when computers were still new, the Rand Corporation published a book that contained

a million random digits [1289]. Their method is described in the book:

The random digits in the book were produced by rerandomization of a basic table

generated by an electronic roulette wheel. Briefly, a random frequency pulse source,

providing on the average about 100,000 pulses per second, was gated about once per

second by a constant frequency pulse. Pulse standardization circuits passed the pulses

through a 5-place binary counter. In principle the machine was a 32-place roulette wheel

which made, on the average, about 3000 revolutions per trial and produced one number

per second. A binary-to-decimal converter was used which converted 20 of the 32

numbers (the other twelve were discarded) and retained only the final digit of two-digit

numbers; this final digit was fed into an IBM punch to produce finally a punched card

table of random digits.

The book goes on to discuss the results of various randomness tests on the data. It also suggests how to

use the book to find a random number:

The lines of the digit table are numbered from 00000 to 19999. In any use of the table, one

should first find a random starting position. A common procedure for doing this is to open

the book to an unselected page of the digit table and blindly choose a five-digit number;

this number with the first digit reduced modulo 2 determines the starting line; the two

Page 350 of 666

Applied Cryptography: Second Edition - Bruce Schneier

digits to the right of the initially selected five-digit number are reduced modulo 50 to

determine the starting column in the starting line. To guard against the tendency of books

to open repeatedly at the same page and the natural tendency of a person to choose a

number toward the center of the page: every five-digit number used to determine a

starting position should be marked and not used a second time for this purpose.

The meat of the book is the â€śTable of Random Digits.â€ť It lists them in 5-digit groupsâ€”â€ś10097 32533

76520 13586...â€ťâ€”50 on a line and 50 lines on a page. The table goes on for 400 pages and, except for a

particularly racy section on page 283 which reads â€ś69696,â€ť makes for a boring read. The book also

includes a table of 100,000 normal deviates.

The interesting thing about the RAND book is not its million random digits, but that they were

created before the computer revolution. Many cryptographic algorithms use arbitrary constantsâ€”so-

called â€śmagic numbers.â€ť Choosing magic numbers from the RAND tables ensures that they havenâ€™t

been specially chosen for some nefarious reason. Khafre does this, for example.

Using Random Noise

The best way to collect a large number of random bits is to tap the natural randomness of the real

world. Often this method requires specialized hardware, but you can play tricks with computers.

Find an event that happens regularly but randomly: atmospheric noise peaking at a certain threshold,

a toddler falling while learning to walk, or some such. Measure the time interval between one event

and the next event. Record it. Measure the time interval between the second event and the third event.

Record it as well. If the first time interval is greater than the second, output 1 as the bit. If the second

time interval is greater than the first, output 0 as the event. Do it again for the next event.

Throw a dart at the New York Stock Exchange closing prices in your local newspaper. Compare the

closing price of the stock you hit with the closing price of the stock directly above it. If the one you hit

is more, output 0; if it less, output 1.

Hook a Geiger counter up to your computer, count emissions over a fixed time interval, and keep the

least significant bit. Or measure the time between successive ticks. (Since the radioactive source is

decaying, the average time between successive ticks is continuously getting longer. You want to choose

a source with the half life long enough to make this negligibleâ€”like plutonium. Or, if youâ€™re worried

about your health, you can apply appropriate statistical corrections.)

G. B. Agnew proposed a real random-bit generator, suitable for integration into a VLSI device [21]. It

is a metal insulator semiconduction capacitor (MISC). Two of them are placed in close proximity, and

the random bit is a function of the difference in charge between the two. Another random-number

generator generates a random-bit stream based on the frequency instability in a free-running

oscillator [535]. A commercial chip from AT&T generates random numbers from the same

phenomenon [67]. M. Gude built a random-number generator that collected random bits from

physical phenomena, such as radioactive decay [668,669]. Manfield Richter developed a random-

number generator based on thermal noise from a semiconductor diode [1309].

Supposedly the time intervals between successive 2e4 light emissions from a trapped mercury atom

are random. Use that. Better yet, find a semiconductor company that makes random-number-

generation chips; they are out there.

There is also a random-number generator that uses the computerâ€™s disk drive [439]. It measures the

time required to read a disk block and uses the variation in that time as a random number source. It

filters the timing data to remove structure that comes from quantization, then applies a fast Fourier

Page 351 of 666

Applied Cryptography: Second Edition - Bruce Schneier

transform to vectors of the numbers. This removes bias and correlation. Finally, it uses the spectral

angles for frequencies in (0, Ď€), normalized to the unit interval, as the random bits. A large part of the

variation in disk rotation speed is caused by air turbulence, so there is randomness in the system.

There are caveats, though. If you keep too many bits of the output, you are using the fast Fourier

transform as a random-number generator and risk predictability. And itâ€™s best to read the same disk

block over and over, so that your filtering doesnâ€™t have to remove structure that comes from the disk-

scheduler. An implementation of this system was able to collect about 100 bits per minute [439].

Using the Computerâ€™s Clock

If you want a single random bit (or even a few), take the least significant bit from any clock register.

This might not be terribly random in a UNIX system because of various potential synchronizations,

but it works on some personal computers.

Beware of getting too many bits this way. Executing the same subroutine several times in succession

could easily skew bits generated in this manner. For example, if each bit generation subroutine takes

an even number of clock ticks to execute, you will get an endless stream of the same bit out of the

generator. If each subroutine takes an odd number of clock ticks to execute, you will get an endless

stream of alternating bits out of the generator. Even if the resonance isnâ€™t this obvious, the resultant

bit stream will be far from random.

One random-number generator works this way [918]:

Our truly random number generator...works by setting an alarm and then incrementing a

counter register rapidly in the CPU until an interrupt occurs. The contents of the register

are then XORed with the contents of an output buffer byte (truncating the registerâ€™s data

to 8 bits). After each byte of the output buffer is filled, the buffer is further processed by

doing a right, circular shift of each character by 2 bits. This has the effect of moving the

most active (and random) least significant bits into the most significant positions. The

entire process is then repeated 3 times. Finally each character of the buffer has been

touched by the two most random bits of the counter register after interrupts. That is 4n

interrupts have occurred where n is the number of desired random bytes.

This method is very sensitive to the randomness of system interrupts and the granularity of the clock.

The output looked pretty good when tested on real UNIX machines.

Measuring Keyboard Latency

Peopleâ€™s typing patterns are both random and nonrandom. They are nonrandom enough that they

can be used as a means of identification, but they are random enough that they can be used to

generate random bits. Measure the time between successive keystrokes, then take the least significant

bits of those measurements. These bits are going to be pretty random. This technique may not work

on a UNIX terminal, since the keystrokes pass through filters and other mechanisms before they get to

your program, but it will work on most personal computers.

Ideally, you only want to collect one random bit per keystroke. Collecting more may skew the results,

depending on how good a typist is sitting at the keyboard. This technique is limited, though. While itâ€™s

easy to have someone type 100 words or so when it is time to generate a key, it isnâ€™t reasonable to ask

the typist to type a 100,000-word essay to generate a keystream for a one-time pad.

Biases and Correlations

Page 352 of 666

Applied Cryptography: Second Edition - Bruce Schneier

A major problem with all these systems is that there could be nonrandomness in the generated

sequence. The underlying physical processes might be random, but many kinds of measuring

instruments are between the digital part of the computer and the physical process. Those instruments

could easily introduce problems.

A way to eliminate bias, or skew, is to XOR several bits together. If a random bit is biased toward 0

by a factor e, then the probability of 0 can be written as:

P(0) = .5 + e

XORing two of these bits together yields:

P(0) = (.5 + e)2 + (.5 - e)2 = .5 + 2e2

By the same calculation, XORing 4 bits together yields:

P(0) = .5 + 8e4

XORing m bits will exponentially converge to an equal probability of 0 and 1. If you know the

maximum bias you are willing to accept for your application, you can calculate how many bits you

need to XOR together to get random bits below that bias.

An even better method is to look at the bits in pairs. If the 2 bits are the same, discard them and look

at the next pair. If the 2 bits are different, take the first bit as the output of the generator. This

eliminates bias completely. Other techniques for reducing bias use transition mappings, compression,

and fast Fourier transforms [511].

The potential problem with both methods is that if there is a correlation between adjacent bits, then

these methods will increase the bias. One way to correct this is to use multiple random sources. Take

four different random sources and XOR the bits together; or take two random sources, and look at

those bits in pairs.

For example, take a radioactive source and hook a Geiger counter to your computer. Take a pair of

noisy diodes and record as an event every time the noise exceeds a certain peak. Measure atmospheric

noise. Get a random bit from each and XOR them together to produce the random bit. The

possibilities are endless.

The mere fact that a random-number generator has a bias does not necessarily mean that it is

unusable. It just means that it is less secure. For example, consider the problem of Alice generating a

triple-DES 168-bit key. All she has is a random-bit generator with a bias toward 0: It produces 55

percent 0s and 45 percent 1s. This means that there are only 0.99277 bits of entropy per key bit, as

opposed to 1 bit of entropy if the generator were perfect. Mallory, trying to break the key, can

optimize his brute-force search to try the most probable key first (000...0), and work toward the least

probable key (111...1). Because of the bias, Mallory can expect to find the key in 2109 attempts. If

there were no bias, Mallory would expect to make 2111 attempts. The resultant key is less secure, but

not appreciably so.

Distilling Randomness

In general, the best way to generate random numbers is to find a whole lot of seemingly random

events and distill randomness from them. This randomness can then be stored in a pool or reservoir

Page 353 of 666

Applied Cryptography: Second Edition - Bruce Schneier

that applications can draw on as needed. One-way hash functions are ready-made for the job; theyâ€™re

fast, so you can shovel quite a bit through them without worrying too much about performance or the

actual randomness of each observation. Hash almost anything you can find that has at least some

randomness. Try:

â€” A copy of every keystroke

â€” Mouse commands

â€” The sector number, time of day, and seek latency for every disk operation

â€” Actual mouse position

â€” Number of current scanline of monitor

â€” Contents of the actually displayed image

â€” Contents of FATs, kernel tables, and so on

â€” Access/modify times of /dev/tty

â€” CPU load

â€” Arrival times of network packets

â€” Input from a microphone

â€” /dev/audio without a microphone attached

If your system uses separate crystal oscillators for its CPU and time-of-day clocks, try reading the

time of day in a tight loop. On some (but not all) systems this will reflect the random phase jitter

between the two oscillators.

Since much of the randomness in these events is in their timing, use the most finely grained time-of-

day clock you can find. A standard PC uses an Intel 8254 clock chip (or equivalent) driven at

1.1931818 megahertz, so reading the counter register directly gives you 838-nanosecond resolution. To

avoid skewing the results, avoid taking your event samples on a timer interrupt.

Here is the process in C with MD5 (see Section 18.5) as the hash function:

char Randpool[16];

/* Call early and call often on a wide variety of random or semi-

* random system events to churn the randomness pool.

* The exact format and length of randevent doesnâ€™t matter as long as

* its contents are at least somewhat unpredictable.

*/

void churnrand(char *randevent,unsigned int randlen)

{

MD5_CTX md5;

MD5Init(&md5);

MD5Update(&md5,Randpool,sizeof(Randpool));

MD5Update(&md5,randevent,randlen);

MD5Final(Randpool,&md5);

}

After calling churnrand() enough to build up sufficient randomness in Randpool, you can now

generate random bits from it. MD5 again comes in handy, this time as a counter-mode pseudo-

random byte-stream generator.

long Randcnt;

void genrand(char *buf,unsigned int buflen)

{

MD5_CTX md5;

char tmp[16];

unsigned int n;

while(buflen != 0) {

Page 354 of 666

Applied Cryptography: Second Edition - Bruce Schneier

/* Hash the pool with a counter */

MD5Init(&md5);

MD5Update(&md5,Randpool,sizeof(Randpool));

MD5Update(&md5,(unsigned char *)&Randcnt,sizeof(Randcnt));

MD5Final(tmp,&md5);

Randcnt++; /* Increment counter */

/* Copy 16 bytes or requested amount, whichever is less,

* to the userâ€™s buffer */

n = (buflen < 16) ? buflen : 16;

memcpy(buf,tmp,n);

buf += n;

buflen -= n;

}

}

The hash function is crucial here for several reasons. First, it provides an easy way to generate an

arbitrary amount of pseudo-random data without having to call churnrand() each time. In effect, the

system degrades gracefully from perfect to practical randomness when the demand exceeds the

supply. In this case it becomes theoretically possible to use the result from one genrand() call to

determine a previous or subsequent result. But this requires inverting MD5, which is computationally

infeasible.

This is important since the routine doesnâ€™t know what each caller will do with the random data it

returns. One call might generate a random number for a protocol that is sent in the clear, perhaps in

response to a direct request by an attacker. The very next call might generate a secret key for an

unrelated session that the attacker wishes to penetrate. Obviously, it is very important that an

attacker not be able to deduce the secret key from the nonce.

One problem remains. There must be sufficient randomness in the Randpool[] array before the first

call to genrand(). If the system has been running for a while with a local user typing on the keyboard,

no problem. But what about a standalone system that reboots automatically without seeing any

keyboard or mouse input?

This is a tough one. A partial solution would require the operator to type for a while after the very

first reboot, and to create a seed file on disk before shutting down to carry the randomness in

Randseed[] across reboots. But do not save the Randseed[] array directly. An attacker who steals this

file could determine all of the results from genrand() after the last call to churnrand() prior to the file

being created.

The fix to this problem is to hash the Randseed[] array before storing it, perhaps by just calling

genrand(). When the system reboots, you read in the seed file, pass it to churnrand(), then promptly

destroy it. Unfortunately, this does not deal with the threat of someone stealing the seed file between

reboots and using it to guess future values of the genrand() function. I see no solution to this problem

other than to wait until enough external random events have taken place after a reboot before

allowing genrand() to produce results.

Chapter 18

One-Way Hash Functions

18.1 Background

A one-way hash function, H(M), operates on an arbitrary-length pre-image message, M. It returns a

fixed-length hash value, h.

Page 355 of 666

Applied Cryptography: Second Edition - Bruce Schneier

h = H(M), where h is of length m

Many functions can take an arbitrary-length input and return an output of fixed length, but one-way

hash functions have additional characteristics that make them one-way [1065]:

Given M, it is easy to compute h.

Given h, it is hard to compute M such that H(M)= h.

Given M, it is hard to find another message, Mâ€™, such that H(M) = H(Mâ€™).

If Mallory could do the hard things, he would undermine the security of every protocol that uses the

one-way hash function. The whole point of the one-way hash function is to provide a â€śfingerprintâ€ť of

M that is unique. If Alice signed M by using a digital signature algorithm on H(M), and Bob could

produce Mâ€™, another message different from M where H(M) = H(Mâ€™), then Bob could claim that Alice

signed Mâ€™.

In some applications, one-wayness is insufficient; we need an additional requirement called collision-

resistance.

It is hard to find two random messages, M and Mâ€™, such that H(M) = H(Mâ€™).

Remember the birthday attack from Section 7.4? It is not based on finding another message Mâ€™, such

that H(M) = H(Mâ€™), but based on finding two random messages, M and Mâ€™, such that H(M) = H(Mâ€™).

The following protocol, first described by Gideon Yuval [1635], shows howâ€”if the previous

requirement were not trueâ€”Alice could use the birthday attack to swindle Bob.

(1) Alice prepares two versions of a contract: one is favorable to Bob; the other bankrupts

him.

(2) Alice makes several subtle changes to each document and calculates the hash value for

each. (These changes could be things like: replacing SPACE with SPACE-BACKSPACE-

SPACE, putting a space or two before a carriage return, and so on. By either making or not

making a single change on each of 32 lines, Alice can easily generate 232 different documents.)

(3) Alice compares the hash values for each change in each of the two documents, looking

for a pair that matches. (If the hash function only outputs a 64-bit value, she would usually find

a matching pair with 232 versions of each.) She reconstructs the two documents that hash to the

same value.

(4) Alice has Bob sign the version of the contract that is favorable to him, using a protocol

in which he only signs the hash value.

(5) At some time in the future, Alice substitutes the contract Bob signed with the one that

he didnâ€™t. Now she can convince an adjudicator that Bob signed the other contract.

This is a big problem. (One moral is to always make a cosmetic change to any document you sign.)

Other similar attacks could be mounted assuming a successful birthday attack. For example, an

adversary could send an automated control system (on a satellite, perhaps) random message strings

with random signature strings. Eventually, one of those random messages will have a valid signature.

The adversary would have no idea what the command would do, but if his only objective was to

tamper with the satellite, this would do it.

Length of One-Way Hash Functions

Page 356 of 666

Applied Cryptography: Second Edition - Bruce Schneier

Hash functions of 64 bits are just too small to survive a birthday attack. Most practical one-way hash

functions produce 128-bit hashes. This forces anyone attempting the birthday attack to hash 264

random documents to find two that hash to the same value, not enough for lasting security. NIST, in

its Secure Hash Standard (SHS), uses a 160-bit hash value. This makes the birthday attack even

harder, requiring 280 random hashes.

The following method has been proposed to generate a longer hash value than a given hash function

produces.

(1) Generate the hash value of a message, using a one-way hash function listed in this

book.

(2) Prepend the hash value to the message.

(3) Generate the hash value of the concatenation of the message and the hash value.

(4) Create a larger hash value consisting of the hash value generated in step (1)

concatenated with the hash value generated in step (3).

(5) Repeat steps (1) through (3) as many times as you wish, concatenating as you go.

Although this method has never been proved to be either secure or insecure, various people have some

serious reservations about it [1262, 859].

Overview of One-Way Hash Functions

Itâ€™s not easy to design a function that accepts an arbitrary-length input, let alone make it one-way. In

the real world, one-way hash functions are built on the idea of a compression function . This one-way

function outputs a hash value of length n given an input of some larger length m [1069, 414]. The

inputs to the compression function are a message block and the output of the previous blocks of text

(see Figure 18.1). The output is the hash of all blocks up to that point. That is, the hash of block Mi is

hi = f(Mi,hi- 1)

This hash value, along with the next message block, becomes the next input to the compression

function. The hash of the entire message is the hash of the last block.

The pre-image should contain some kind of binary representation of the length of the entire message.

This technique overcomes a potential security problem resulting from messages with different lengths

possibly hashing to the same value [1069, 414]. This technique is sometimes called MD-strengthening

[930].

Various researchers have theorized that if the compression function is secure, then this method of

hashing an arbitrary-length pre-image is also secureâ€”but nothing has been proved [1138, 1070, 414].

A lot has been written on the design of one-way hash functions. For more mathematical information,

consult [1028, 793, 791, 1138, 1069, 414, 91, 858, 1264]. Bart Preneelâ€™s thesis [1262] is probably the

most comprehensive treatment of one-way hash functions.

Figure 18.1 One-way function.

18.2 Snefru

Page 357 of 666

Applied Cryptography: Second Edition - Bruce Schneier

Snefru is a one-way hash function designed by Ralph Merkle [1070]. (Snefru, like Khufu and Khafre,

was an Egyptian pharaoh.) Snefru hashes arbitrary-length messages into either 128-bit or 256-bit

values.

First the message is broken into chunks, each 512-m in length. (The variable m is the length of the

hash value.) If the output is a 128-bit hash value, then the chunks are each 384 bits long; if the output

is a 256-bit hash value, then the chunks are each 256 bits long.

The heart of the algorithm is function H, which hashes a 512-bit value into an m-bit value. The first m

bits of Hâ€™s output are the hash of the block; the rest are discarded. The next block is appended to the

hash of the previous block and hashed again. (The initial block is appended to a string of zeros.) After

the last block (if the message isnâ€™t an integer number of blocks long, zeros are used to pad the last

block), the first m bits are appended to a binary representation of the length of the message and

hashed one final time.

Function H is based on E, which is a reversible block-cipher function that operates on 512-bit blocks.

H is the last m bits of the output of E XORed with the first m bits of the input of E.

The security of Snefru resides in function E, which randomizes data in several passes. Each pass is

composed of 64 randomizing rounds. In each round a different byte of the data is used as an input to

an S-box; the output word of the S-box is XORed with two neighboring words of the message. The S-

boxes are constructed in a manner similar to those in Khafre (see Section 13.7). Some rotations are

thrown in, too. Originally Snefru was designed with two passes.

Cryptanalysis of Snefru

Using differential cryptanalysis, Biham and Shamir demonstrated the insecurity of two-pass Snefru

(128-bit hash value) [172]. Their attack finds pairs of messages that hash to the same value within

minutes.

On 128-bit Snefru, their attacks work better than brute force for four passes or less. A birthday

attack against Snefru takes 264 operations; differential cryptanalysis can find a pair of messages that

hash to the same value in 228.5 operations for three-pass Snefru and 244.5 operations for four-pass

Snefru. Finding a message that hashes to a given value by brute force requires 2128 operations;

differential cryptanalysis takes 256 operations for three-pass Snefru and 288 operations for four-pass

Snefru.

Although Biham and Shamir didnâ€™t analyze 256-bit hash values, they extended their analysis to 224-

bit hash values. Compared to a birthday attack that requires 2112 operations, they can find messages

that hash to the same value in 212.5 operations for two-pass Snefru, 233 operations for three-pass

Snefru, and 281 operations for four-pass Snefru.

Currently, Merkle recommends using Snefru with at least eight passes [1073]. However, with this

many passes the algorithm is significantly slower than either MD5 or SHA.

18.3 N- Hash

N-Hash is an algorithm invented by researchers at Nippon Telephone and Telegraph, the same people

who invented FEAL, in 1990 [1105, 1106]. N-Hash uses 128-bit message blocks, a complicated

Page 358 of 666

Applied Cryptography: Second Edition - Bruce Schneier

randomizing function similar to FEALâ€™s, and produces a 128-bit hash value.

The hash of each 128-bit block is a function of the block and the hash of the previous block.

H0 = I, where I is a random initial value

Hi = g(Mi,Hi- 1) Mi Hi- 1

The hash of the entire message is the hash of the last message block. The random initial value, I, can

be any value determined by the user (even all zeros).

The function g is a complicated one. Figure 18.2 is an overview of the algorithm. Initially, the 128-bit

hash of the previous message block, Hi-1, has its 64-bit left half and 64-bit right half swapped; it is

then XORed with a repeating one/zero pattern (128 bits worth), and then XORed with the current

message block, Mi. This value then cascades into N(N = 8 in the figures) processing stages. The other

input to the processing stage is the previous hash value XORed with one of eight binary constant

values.

Figure 18.2 Outline of N-Hash.

One processing stage is given in Figure 18.3. The message block is broken into four 32-bit values. The

previous hash value is also broken into four 32-bit values. The function f is given in Figure 18.4.

Functions S0 and S1 are the same as they were in FEAL.

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

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

The output of one processing stage becomes the input to the next processing stage. After the last

processing stage, the output is XORed with the Mi and Hi-1, and then the next block is ready to be

hashed.

Cryptanalysis of N- Hash

Bert den Boer discovered a way to produce collisions in the round function of N-Hash [1262]. Biham

and Shamir used differential cryptanalysis to break 6-round N-Hash [169, 172]. Their particular

Page 359 of 666

Applied Cryptography: Second Edition - Bruce Schneier

attack (there certainly could be others) works for any N that is divisible by 3, and is more efficient

than the birthday attack for any N less than 15.

Figure 18.3 One processing stage of N-Hash.

Figure 18.4 Function f.

The same attack can find pairs of messages that hash to the same value for 12-round N-Hash in 256

operations, compared to 264 operations for a brute-force attack. N-hash with 15 rounds is safe from

differential cryptanalysis: The attack requires 272 operations.

The algorithmâ€™s designers recommend using N-Hash with at least 8 rounds [1106]. Given the proven

insecurity of N-Hash and FEAL (and its speed with 8 rounds), I recommend using another algorithm

entirely.

18.4 MD4

MD4 is a one-way hash function designed by Ron Rivest [1318, 1319, 1321]. MD stands for Message

Digest; the algorithm produces a 128-bit hash, or message digest, of the input message.

In [1319], Rivest outlined his design goals for the algorithm:

Security. It is computationally infeasible to find two messages that hashed to the same

value. No attack is more efficient than brute force.

Direct Security. MD4â€™s security is not based on any assumption, like the difficulty of

Page 360 of 666

Applied Cryptography: Second Edition - Bruce Schneier

factoring.

Speed. MD4 is suitable for high-speed software implementations. It is based on a simple

set of bit manipulations on 32-bit operands.

Simplicity and Compactness. MD4 is as simple as possible, without large data structures or

a complicated program.

Favor Little-Endian Architectures. MD4 is optimized for microprocessor architectures

(specifically Intel microprocessors); larger and faster computers make any necessary

translations.

After the algorithm was first introduced, Bert den Boer and Antoon Bosselaers successfully

cryptanalyzed the last two of the algorithmâ€™s three rounds [202]. In an unrelated cryptanalytic result,

Ralph Merkle successfully attacked the first two rounds [202]. Eli Biham discussed a differential

cryptanalysis attack against the first two rounds of MD4 [159]. Even though these attacks could not

be extended to the full algorithm, Rivest strengthened the algorithm. The result is MD5.

18.5 MD5

MD5 is an improved version of MD4 [1386, 1322]. Although more complex than MD4, it is similar in

design and also produces a 128-bit hash.

Description of MD5

After some initial processing, MD5 processes the input text in 512-bit blocks, divided into 16 32-bit

sub-blocks. The output of the algorithm is a set of four 32-bit blocks, which concatenate to form a

single 128-bit hash value.

First, the message is padded so that its length is just 64 bits short of being a multiple of 512. This

padding is a single 1-bit added to the end of the message, followed by as many zeros as are required.

Then, a 64-bit representation of the messageâ€™s length (before padding bits were added) is appended to

the result. These two steps serve to make the message length an exact multiple of 512 bits in length

(required for the rest of the algorithm), while ensuring that different messages will not look the same

after padding.

Four 32-bit variables are initialized:

A = 0x01234567

B = 0x89abcdef

C = 0xfedcba98

D = 0x76543210

These are called chaining variables.

Now, the main loop of the algorithm begins. This loop continues for as many 512-bit blocks as are in

the message.

The four variables are copied into different variables: a gets A, b gets B, c gets C, and d gets D.

The main loop has four rounds (MD4 had only three rounds), all very similar. Each round uses a

different operation 16 times. Each operation performs a nonlinear function on three of a, b, c, and d.

Then it adds that result to the fourth variable, a sub-block of the text and a constant. Then it rotates

that result to the right a variable number of bits and adds the result to one of a, b, c, or d. Finally the

result replaces one of a, b, c, or d. See Figures 18.5 and 18.6.

ńňđ. 15 |