[Haskell-cafe] Re: Splittable random numbers
Tyson Whitehead
twhitehead at gmail.com
Thu Nov 4 14:45:47 EDT 2010
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
More information about the Haskell-Cafe
mailing list