|
143
|
1 Tech Note 0004
|
|
|
2 Using Yarrow, Fortuna and SOBER-128
|
|
|
3 Tom St Denis
|
|
|
4
|
|
|
5 Introduction
|
|
|
6 ------------
|
|
|
7
|
|
|
8 This tech note explains how to use three of the more useful pseudo random number generators and their
|
|
|
9 own little "issues". While all of the PRNGs have the same API and are roughly used in the same
|
|
|
10 manner their effectiveness really depends on the user knowing how they work.
|
|
|
11
|
|
|
12
|
|
|
13 Yarrow
|
|
|
14 ------
|
|
|
15
|
|
|
16 Yarrow is by far the simplest of the PRNGs. It gathers bits of entropy by hashing the pool state
|
|
|
17 plus the additional bits storing the message digest back in the pool. E.g.
|
|
|
18
|
|
|
19 pool = hash(pool || newbits)
|
|
|
20
|
|
|
21 Simply dump bits into the PRNG via yarrow_add_entropy() and call yarrow_ready() when you want to
|
|
|
22 put them to use. This PRNG while simple is not entirely safe. An attacker who learns the state
|
|
|
23 of the pool and can control future events can control the PRNG. This requires an active attacker but
|
|
|
24 isn't entire impossible.
|
|
|
25
|
|
|
26 The pool is then used as a key for a cipher that is used in CTR mode.
|
|
|
27
|
|
|
28 Yarrow is mostly meant for short-term programs [e.g. like file utils]. This particular implementation
|
|
|
29 is not meant for long-term usage.
|
|
|
30
|
|
|
31 Fortuna
|
|
|
32 -------
|
|
|
33
|
|
|
34 Fortuna was designed by Niels Fergusson and Bruce Schneier [Bruce is also the guy who invented Yarrow]. It
|
|
|
35 operates on a more defensive level than Yarrow. Instead of 1 entropy pool it has 32 and the new entropy
|
|
|
36 is spread [round robin] in all of the pools.
|
|
|
37
|
|
|
38 That is, each call to fortuna_add_entropy() puts the bits in the next [in the sequenece] pool of entropy.
|
|
|
39 Effective bits are added to the pool by sending them through a hash [but not terminating the hash].
|
|
|
40
|
|
|
41 Here's the main catch though. When the PRNG must be reseeded [so that you can extract bits from it] only
|
|
|
42 certain pools are used. More precisely the i'th pool is used every 2**i'th reseeding. For example, pool[0]
|
|
|
43 is always used. pool[1] is used every second reseeding, pool[2] every fourth.
|
|
|
44
|
|
|
45 The pools are hashed together along with the current key and the result is the new key for a cipher which
|
|
|
46 operates in CTR mode [more about that in a sec].
|
|
|
47
|
|
|
48 Now this may seem odd at first however there is a good reason behind it. An attacker who learns pool[0] won't
|
|
|
49 strictly know the other pools. So the recovery rate of is not 0. In fact pool[0] can be completely
|
|
|
50 compromised and the PRNG will still eventually recover. The value FORTUNA_WD is the "WatchDog" counter.
|
|
|
51 Every FORTUNA_WD calls to fortuna_read will invoke the reseed operation. By default this is set to 10 which
|
|
|
52 means after 10 calls the PRNG will reseed itself.
|
|
|
53
|
|
|
54 The pools are combined with the running cipher key [256 bits] so that a cipher in CTR mode can produce
|
|
|
55 the stream. Unlike Yarrow the cipher is re-keyed after every call to fortuna_read() [so one big call
|
|
|
56 would be faster than many smaller calls]. This prevents too much data being encrypted under the same
|
|
|
57 key [and mitigates a flaw in CTR mode that the same block can't be emitted twice under the same key].
|
|
|
58
|
|
|
59 Fortuna is really meant for a kernel-level PRNG. The more sources [and often] you feed into it the
|
|
|
60 healthier it will be. It's also meant to be used for long term purposes. Since it can recover from
|
|
|
61 compromises it is harder to control it.
|
|
|
62
|
|
|
63 SOBER-128
|
|
|
64 ------
|
|
|
65
|
|
|
66 SOBER-128 is actually a stream cipher but like most ciphers can easily be modelled in the context of a PRNG.
|
|
|
67 This PRNG is extremely fast [4 cycles/byte on a P4] and was designed by a well known cryptographer [Greg Rose].
|
|
|
68
|
|
|
69 SOBER-128 doesn't really "act" like the other two PRNGs. It's meant to be seeded once and then read as
|
|
|
70 required. In such a sense it isn't a "system PRNG" but useful short term purposes. In particular
|
|
|
71 the sober128_read() function actually XORs against the input buffer you specify. This allows the
|
|
|
72 read() function to be used as an "encrypt" function as well.
|
|
|
73
|
|
|
74 You can only key SOBER-128 once [by calling sober128_add_entropy()]. Once it it is keyed subsequent
|
|
|
75 calls to add_entropy() will be considered a "re-IV" operation. Changing the IV allows you to use same
|
|
|
76 initial key and not produce the same output stream. It also lets you differentiate packets. E.g. each
|
|
|
77 packet has it's own IV.
|
|
|
78
|
|
|
79 All inputs to sober128_add_entropy() must have a length that is a multiple of four.
|
|
|
80
|
|
|
81 Overall
|
|
|
82 -------
|
|
|
83
|
|
|
84 Since SOBER-128 is *much* faster than the other two PRNGs a good setup would be to use Fortuna as your
|
|
|
85 system-wide PRNG and use SOBER-128 [key'ed from Fortuna] for encrypting streams or as a PRNG for
|
|
|
86 simulations.
|
|
|
87
|
|
|
88 Yarrow is still a good candidate but only for "short lived" programs. However, since Fortuna is faster
|
|
|
89 [by about 10 cycles/byte on a P4] I'd use Fortuna anyways...
|
|
|
90
|
|
|
91 Tom |
