X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/blobdiff_plain/674cd11ec63b56561980249cb19a0db54bacfa86..759513d1c2f79d94abe726682f43a28f363229cc:/README.random diff --git a/README.random b/README.random new file mode 100644 index 0000000..6fd95eb --- /dev/null +++ b/README.random @@ -0,0 +1,213 @@ +Catacomb's random number generators + + + Catacomb contains a large number of pseudorandom number + generators. Some are dedicated to generating pseudorandom + numbers; others are ciphers in output-feedback mode. Some are + cryptographically strong, others are fast or simple. All have + been statistically tested and come out OK. + + +The `rand' generator + + Cryptographic applications need a source of true random data. + The `rand' generator is Catacomb's true-random-data source. + + The design is my own. I wasn't happy with any existing designs, + and I'm still not -- even Counterpane's Yarrow gives me an + uneasy feeling[1]. I'm not aware of any cryptanalytic attack + against my generator, and I'd very much like to hear if anyone + else knows differently. + + The generator's state is held in an object of type `rand_pool'. + Data can be added into the pool using the `rand_add' function. + Random numbers can be extracted by calling `rand_get'. + + It's possible to attach a `noise acquisition' function to a + rand_pool. The function `rand_getgood' extracts a number of + bytes from the generator, calling the noise acquisition function + if it thinks it's low on randomness. This shouldn't actually be + necessary once the generator has been topped up once. It makes + the generator very slow. + + It's also possible to key the generator. The output + transformation then depends on the key, making it even harder + for an adversary to work out anything useful about the + generator. + + The underlying transformation used by the generator is + + x' = E_{H(x)}(x) + + i.e., hash, use the hash as a key, and encrypt. + + + [1] The Yarrow paper states that it offers 160 bits-worth of + security, and that an adversary can't distinguish its output + from real random bits. I have an attack which takes about + 2^64 64-bit outputs and tells the difference between + Yarrow-160 and real random data, by analysing the frequency + of adjacent 64-bit blocks being equal. + + +Noncryptographic generators + + Two pseudorandom-number generators are supplied which have no + cryptographic strength whatever. They are, respectively, a + traditional linear-congruential generator (lcrand) and a + Fibonacci generator (fibrand). + + The linear-congruential generator has three (fixed) parameters, + a, c and p, and calculates + + x[i] = (a x[i - 1] + c) mod p + + The prime p is fairly large (2^32 - 5, in fact), and a and c are + carefully chosen. The generator has a period of p - 1. There + is one fixed point (i.e., it transforms to itself rather than + being in the cycle) which must be avoided. + + The Fibonacci generator works by adding together old results: + + x[i] = (x[i - 24] + x[i - 55]) mod 2^32 + + It has a very long period, and is the fastest pseudorandom + number generator in Catacomb. + + These two generators are very useful when the cryptographic + strength of the output isn't important, for example when + choosing random numbers for primality testing. + + +The Blum-Blum-Shub generator + + This is by far the strongest and by even further the slowest + pseudorandom-number generator in Catacomb. Its output has been + proven to be indistinguishable from random data by *any* + polynomial-time test, assuming that factoring large numbers is + difficult. + + Use the BBS generator when you're feeling really paranoid, and + you've got a few hours with nothing to do. + + +Output-feedback ciphers + + Ciphers in output-feedback mode simply emit a pseudorandom + stream. To construct a cipher, you XOR the stream with the + plaintext. It's even easier just to use the output as random + numbers. + + +Generic interface + + There's a fairly comprehensive generic interface for Catacomb's + various generators. + + Each generator provides a function which returns a pointer to a + `generic pseudorandom-number generator', of type `grand'. + + A `grand' is a structured type containing one member, `ops', + which is a pointer to various useful things. Let `r' be a + pointer to a generic pseudorandom-number generator; then, + + r->ops->name The name of the generator. + + r->ops->max One greater than the maximum output of + the `raw' function, or zero if it just + emits words. + + r->ops->misc(r, op, ...) + Performs a miscellaneous operation. The + various standard `op' values are + described below. + + r->ops->destroy(r) Destroy the generic generator. + + r->ops->raw(r) Return a raw output from the generator. + For `lcrand', this is an integer in the + range [0, p); for other generators, it's + the same as `word'. + + r->ops->byte(r) Return an octet. The result is + uniformly distributed over the integers + in the interval [0, 256). + + r->ops->word(r) Returns a word. The result is uniformly + distributed over the integers in the + interval [0, 2^32). + + r->ops->range(r, l) Returns an integer unformly distributed + in the interval [0, l), l < 2^32. + + r->ops->fill(r, p, sz) Fill the sz bytes at address p with + uniformly distributed bytes (i.e., + integers in the interval [0, 256). + + All of these operations are supported by all generators. Some + may be inefficient, however, since they're synthesized using + operations more suited to the particular generator. For + example, `word' is not efficient on the linear-congruential + generator, but is for the Fibonacci generator. + + The misc-ops are as follows: + + misc(r, GRAND_CHECK, op) Return nonzero if `op' is a + recognized misc-op for this + generator. + + misc(r, GRAND_SEEDINT, s) Seed the generator using the + integer s. + + misc(r, GRAND_SEEDUINT32, s) Seed the generator using the + 32-bit word s. + + misc(r, GRAND_SEEDBLOCK, p, sz) Seed the generator using the + block of sz bytes starting at + address p. + + misc(r, GRAND_SEEDMP, m) Seed the generator using the + multiprecision integer m. + + misc(r, GRAND_SEEDRAND, r') Seed the generator using some + output from the generic pseudo- + random number generator r'. + + +Statistical testing + + I generated 10M of data with each of Catacomb's random number + generators, and tested them with George Marsaglia's DIEHARD + suite. While the random data is not included here, the + following trivial Bourne shell script will generate the exact + output streams I used, assuming that the supplied `rspit' + program is in the current PATH: + + for i in des 3des idea blowfish rc5 rc4; do + rspit $i -kseed -z10m -o$i.rand + done + for i in lcrand fibrand; do + rspit $i -p -s0 -z10m -o$i.rand + done + rspit rand -p -z10m -orand.rand + nice rspit bbs -p -s2 -z10m -obbs.rand + + (Note that generating the BBS output data can take over an + hour. Make sure you have a good book to read.) + + Looking at the results, I think that they all passed the tests + relatively convincingly. + + I've not actually included the DIEHARD output files in the + distribution, because they're quite large, and anyone can + reproduce my results exactly using the publically available + DIEHARD distribution and the code supplied. If you do actually + want them, send me some mail and I'll send you a 60K tar.gz + file by (approximate) return. +-- +[mdw] + + +Local variables: +mode: text +End: