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

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