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.

11 The `rand' generator

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

36 generator.

38 The underlying transformation used by the generator is

40 x' = E_{H(x)}(x)

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

88 difficult.

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

99 numbers.

102 Generic interface

104 There's a fairly comprehensive generic interface for Catacomb's

105 various generators.

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

118 emits words.

120 r->ops->misc(r, op, ...)

121 Performs a miscellaneous operation. The

122 various standard `op' values are

123 described below.

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

130 the same as `word'.

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

138 interval [0, 2^32).

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

157 generator.

159 misc(r, GRAND_SEEDINT, s) Seed the generator using the

160 integer s.

162 misc(r, GRAND_SEEDUINT32, s) Seed the generator using the

163 32-bit word s.

165 misc(r, GRAND_SEEDBLOCK, p, sz) Seed the generator using the

166 block of sz bytes starting at

167 address p.

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'.

177 Statistical testing

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

188 done

189 for i in lcrand fibrand; do

190 rspit $i -p -s0 -z10m -o$i.rand

191 done

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.

208 -- [mdw]

210 \f

211 Local variables:

212 mode: text

213 End: