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
