Splittable random numbers

[Thomas DuBuisson]

> Does anyone feel like taking the idea and turning it into a Haskell
> library?   (Or even a Haskell Wiki page?)  I’m taking the liberty of
> cross-posting to the libraries list.

If no one else does, and the pseudo-code is made sufficiently
concrete, I will probably do this in December.

> The generator G is a pair comprising a crypto key G.k and an integer counter
> (the “message”) G.c.
> The (next G) operation returns a pair: 1. a random
> integer r obtained by encrypting G.c with G.k, and 2. a new generator G’
> such that G’.k = G.k and G’.c = G.c + 1.
> The (split G) operation is
> similar, returning the same G’, except that instead of returning a random
> integer r it returns a third generator G’’ such that G’’.k = r and G’’.c =
> 0.

In short (pseudo Haskell):
-------
type G g = (g, Integer)
gen k (G (g,c)) = let (bytes, g') = genBytes k g in (bytes, G g' (c+1))

split gen@(G (g,c)) =
    let (bytes, g') = genBytes (genSeedLength `for` gen)
         componentGen = G (newGen bytes, 0)
    in (componentGen, G g' (c+1))
-------

At first blush, this could probably be done in an afternoon in much
the same manner as BufferedGen, GenXor and GenAutoReseed from the DRBG
package I released earlier this week.  It would take a bit longer to
decide on a good API.

> A suitable block cipher system might be 128-bit AES (Rijndael).

DRBG only support hash based CPRNGs right now, but I guess that's not
really important in this discussion.

> Other crypto options exist.

Right.

> Is this standard?

NIST SP 800-90 section 10.2... but I see he said that later.

> (1)    Limit the counter to 2^32 steps (paradox has 2^-64 probability) or
> even 2^16 (2^-96), then rekey; or

The CryptoRandomGen class allows for failure (Either GenError g) so
this is doable.

> (2)    XOR 2 such encrypted counters, with different keys; or

This already exists for any generator that is an instance of
CryptoRandomGen.  See GenXor in Crypto.Random.DRBG in the DRBG
package.

> (3)    XOR 3 successive values for the same counter (just possibly cheaper;
> top-of-head idea).

And composition of GenXor is possible.

Tolga said:
> The DRBG constructions based on hash functions and block
> ciphers are even standardized in NIST publication SP800-90 (even though I
> may not recommend every one of them).

This intrigues me, was there any more discussion here?



Cheers,
Thomas