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