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
