Mercurial > dropbear

comparison notes/tech0004.txt @ 143:5d99163f7e32 libtomcrypt-orig

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
import of libtomcrypt 0.99
author Matt Johnston <matt@ucc.asn.au>
date Sun, 19 Dec 2004 11:34:45 +0000
parents
children
comparison
equal deleted inserted replaced
15:6362d3854bb4 143:5d99163f7e32
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