Dedicated Conventional Cryptographic Primitives - A Classical Introduction to Cryptography: Applications for Communications Security - page 94

Input : B 0 , B 1 ,...

Output : m
1: start with i = k + 1

2: repeat
3: γ i B i = i − 1 get a linear relationship

j = 0 γ j B j

with integers

γ 0 ,...,γ i with a gcd equal to 1

= i − 1

compute x

j = 0 γ j s j

4:

pick m = x − γ i s i

5:

repeat

6:

increment i 7:

if m = 0 then

8:

γ i B i ≡ i − 1

get a linear relationship γ j B j (mod m ) with

9:

j = 0

integers γ 0 ,...,γ i with a gcd equal to 1 and where γ i is a

factor of m

= i − 1
j

compute x γ j s j mod m

10:

= 0

replace m by the gcd of m and x − γ i s i

11:

12: end if
13: until m is stable or equal to 0
14: until m

= 0

15: output m

Figure 3.16. Attack on the linear congruential pseudorandom generator.

defined by

J = Enc(timestamp)

r = Enc( J ⊕ Seed)

and the seed is replaced by

NextSeed = Enc( J ⊕ r ) .

Finally we mention the Yarrow-160 dedicated generator as proposed by John
Kelsey, Bruce Schneier, and Niels Ferguson from the Counterpane System Company
(see Ref. [101]). Here, there are two layers of pseudorandom generators. In the bot-
tom layer, the generation is simply Enc K (counter), where counter is incremented after
each generation and K is a pseudorandom secret generated by the upper layer. This
key is changed regularly (every 10 generations in Yarrow-160). In the upper layer, the
generated key is simply the hashed value of a counter and an “entropy accumulator.”
This accumulator is fed, for instance, by all interrupt information from the hardware
which are supposed to be random, with odd distribution. The aim of this generator is to
accumulate the randomness and to convert it to a random key with a purer distribution.
This is an example of a nondeterministic pseudorandom generator. A similar approach
was adopted for Linux in the random.c library.

Some other ad hoc examples will be seen in Chapter 12.