[Haskell-cafe] Re: Splittable random numbers

[Tyson Whitehead]

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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 198 bytes
Desc: This is a digitally signed message part.
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20101104/1de70803/attachment.bin