1 Catacomb's random number generators
4 Catacomb contains a large number of pseudorandom number
5 generators. Some are dedicated to generating pseudorandom
6 numbers; others are ciphers in output-feedback mode. Some are
7 cryptographically strong, others are fast or simple. All have
8 been statistically tested and come out OK.
13 Cryptographic applications need a source of true random data.
14 The `rand' generator is Catacomb's true-random-data source.
16 The design is my own. I wasn't happy with any existing designs,
17 and I'm still not -- even Counterpane's Yarrow gives me an
18 uneasy feeling[1]. I'm not aware of any cryptanalytic attack
19 against my generator, and I'd very much like to hear if anyone
20 else knows differently.
22 The generator's state is held in an object of type `rand_pool'.
23 Data can be added into the pool using the `rand_add' function.
24 Random numbers can be extracted by calling `rand_get'.
26 It's possible to attach a `noise acquisition' function to a
27 rand_pool. The function `rand_getgood' extracts a number of
28 bytes from the generator, calling the noise acquisition function
29 if it thinks it's low on randomness. This shouldn't actually be
30 necessary once the generator has been topped up once. It makes
31 the generator very slow.
33 It's also possible to key the generator. The output
34 transformation then depends on the key, making it even harder
35 for an adversary to work out anything useful about the
38 The underlying transformation used by the generator is
42 i.e., hash, use the hash as a key, and encrypt.
45 [1] The Yarrow paper states that it offers 160 bits-worth of
46 security, and that an adversary can't distinguish its output
47 from real random bits. I have an attack which takes about
48 2^64 64-bit outputs and tells the difference between
49 Yarrow-160 and real random data, by analysing the frequency
50 of adjacent 64-bit blocks being equal.
53 Non-cryptographic generators
55 Two pseudorandom-number generators are supplied which have no
56 cryptographic strength whatever. They are, respectively, a
57 traditional linear-congruential generator (lcrand) and a
58 Fibonacci generator (fibrand).
60 The linear-congruential generator has three (fixed) parameters,
61 a, c and p, and calculates
63 x[i] = (a x[i - 1] + c) mod p
65 The prime p is fairly large (2^32 - 5, in fact), and a and c are
66 carefully chosen. The generator has a period of p - 1. There
67 is one fixed point (i.e., it transforms to itself rather than
68 being in the cycle) which must be avoided.
70 The Fibonacci generator works by adding together old results:
72 x[i] = (x[i - 24] + x[i - 55]) mod 2^32
74 It has a very long period, and is the fastest pseudorandom
75 number generator in Catacomb.
77 These two generators are very useful when the cryptographic
78 strength of the output isn't important, for example when
79 choosing random numbers for primality testing.
82 The Blum-Blum-Shub generator
84 This is by far the strongest and by even further the slowest
85 pseudorandom-number generator in Catacomb. Its output has been
86 proven to be indistinguishable from random data by *any*
87 polynomial-time test, assuming that factoring large numbers is
90 Use the BBS generator when you're feeling really paranoid, and
91 you've got a few hours with nothing to do.
94 Output-feedback ciphers
96 Ciphers in output-feedback mode simply emit a pseudorandom
97 stream. To construct a cipher, you XOR the stream with the
98 plaintext. It's even easier just to use the output as random
104 There's a fairly comprehensive generic interface for Catacomb's
107 Each generator provides a function which returns a pointer to a
108 `generic pseudorandom-number generator', of type `grand'.
110 A `grand' is a structured type containing one member, `ops',
111 which is a pointer to various useful things. Let `r' be a
112 pointer to a generic pseudorandom-number generator; then,
114 r->ops->name The name of the generator.
116 r->ops->max One greater than the maximum output of
117 the `raw' function, or zero if it just
120 r->ops->misc(r, op, ...)
121 Performs a miscellaneous operation. The
122 various standard `op' values are
125 r->ops->destroy(r) Destroy the generic generator.
127 r->ops->raw(r) Return a raw output from the generator.
128 For `lcrand', this is an integer in the
129 range [0, p); for other generators, it's
132 r->ops->byte(r) Return an octet. The result is
133 uniformly distributed over the integers
134 in the interval [0, 256).
136 r->ops->word(r) Returns a word. The result is uniformly
137 distributed over the integers in the
140 r->ops->range(r, l) Returns an integer uniformly distributed
141 in the interval [0, l), l < 2^32.
143 r->ops->fill(r, p, sz) Fill the sz bytes at address p with
144 uniformly distributed bytes (i.e.,
145 integers in the interval [0, 256).
147 All of these operations are supported by all generators. Some
148 may be inefficient, however, since they're synthesized using
149 operations more suited to the particular generator. For
150 example, `word' is not efficient on the linear-congruential
151 generator, but is for the Fibonacci generator.
153 The misc-ops are as follows:
155 misc(r, GRAND_CHECK, op) Return nonzero if `op' is a
156 recognized misc-op for this
159 misc(r, GRAND_SEEDINT, s) Seed the generator using the
162 misc(r, GRAND_SEEDUINT32, s) Seed the generator using the
165 misc(r, GRAND_SEEDBLOCK, p, sz) Seed the generator using the
166 block of sz bytes starting at
169 misc(r, GRAND_SEEDMP, m) Seed the generator using the
170 multiprecision integer m.
172 misc(r, GRAND_SEEDRAND, r') Seed the generator using some
173 output from the generic pseudo-
174 random number generator r'.
179 I generated 10M of data with each of Catacomb's random number
180 generators, and tested them with George Marsaglia's DIEHARD
181 suite. While the random data is not included here, the
182 following trivial Bourne shell script will generate the exact
183 output streams I used, assuming that the supplied `rspit'
184 program is in the current PATH:
186 for i in des 3des idea blowfish rc5 rc4; do
187 rspit $i -kseed -z10m -o$i.rand
189 for i in lcrand fibrand; do
190 rspit $i -p -s0 -z10m -o$i.rand
192 rspit rand -p -z10m -orand.rand
193 nice rspit bbs -p -s2 -z10m -obbs.rand
195 (Note that generating the BBS output data can take over an
196 hour. Make sure you have a good book to read.)
198 Looking at the results, I think that they all passed the tests
199 relatively convincingly.
201 I've not actually included the DIEHARD output files in the
202 distribution, because they're quite large, and anyone can
203 reproduce my results exactly using the publicly available
204 DIEHARD distribution and the code supplied. If you do actually
205 want them, send me some mail and I'll send you a 60K tar.gz
206 file by (approximate) return.