On November 4, 2010 13:38:12 Simon Peyton-Jones wrote:
From: Gideon Yuval (Gideon Yuval) Sent: Wednesday, November 03, 2010 7:15 AM To: Simon Peyton-Jones; Burton Smith Cc: Tolga Acar Subject: RE: Random number generation
As long as the key, and the non-counting part of the counter, are kept" secret", anyone who can distinguish these pseudorandoms from real random, in less than 2^128 steps, has a nice paper for crypto-2011 (this is known as "provable security") concerning a weakness in AES128.
One exception: real randoms have a birthday paradox; the pseudorandoms suggested do not. If you care, you can:
(1) Limit the counter to 2^32 steps (paradox has 2^-64 probability) or even 2^16 (2^-96), then rekey; or
(2) XOR 2 such encrypted counters, with different keys; or
(3) XOR 3 successive values for the same counter (just possibly cheaper; top-of-head idea).
More hard-core: swap the position of key & message: encrypting a constant "secret" with 1,2,3,4.... Gives pseudorandoms with no birthday paradox.
Am I correct in understanding that the birthday paradox reference is that a pseudo random permutation (which this must be as the block crypto function has to be one-to-one) can't repeat numbers, unlike a random sequence. I would think this is quite related to a lot of what is discussed on Wikipedia under "block cipher modes of operation" http://en.wikipedia.org/wiki/Block_cipher_modes_of_operation and is presumably well researched. In particular, I see there are some common solutions (e.g., cipher-block chaining -- xor your previous ciphertext [random value] with your next bit of plain text [the incrementing counter]). Cheers! -Tyson