Splittable random numbers
Thomas DuBuisson
thomas.dubuisson at gmail.com
Thu Nov 4 14:08:00 EDT 2010
> 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
More information about the Libraries
mailing list