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
signature.asc
Description: This is a digitally signed message part.
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
