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