Re: [Haskell-cafe] why is Random in System?

The problem with Mersenne twister is that it doesn't split well. The main reason for crypto prng in this package would not be to advertise to people that "System.Random can be used for security-related apps" *but to make splitting reasonably safe*. It's not good enough to have a known-bad generator under splitting provided as the default. And I think we need splitting, especially as more Haskell programs become parallel. Would it address your concerns to not mention the crypto nature of the standard implementation in the System.Random documentation? I think there's also a reasonable argument to lean towards *correctness* over performance in Haskell's defaults. For example, unconstrained Num bindings default to Integer and likewise random numbers could be as strong as possible by default, and those looking for raw rands/sec throughput could make other informed choices. I had thought that maybe we could bifurcate the "stdgen" concept into a fast and a strong version, which could be say Mersenne Twister and AES respectively. But, again, the problem comes if the fast version is expected to be splittable as well. With "SplittableGen" factored out from "RandomGen" I suppose it would be possible for the fast version to NOT offer splitting. However, Mersenne Twister is best used with an imperative interface, you can see the tension in the pure version of the mersenne package on hackage: http://hackage.haskell.org/package/mersenne-random-pure64-0.2.0.3 Please also see Burton Smith's comments below in response to my proposal to offer a MT + AES combination. Best, -Ryan ---------- Forwarded message ---------- From: Burton Smith Date: Tue, Jun 28, 2011 at 1:28 PM Subject: RE: AESNI-based splittable random number generation for Haskell To: "Newton, Ryan R" Mersenne Twister (MT)is a poor choice in my opinion. First, the generator state is large (2496 bytes) and it must be copied on each call to next. Split is worse; it will generate twice as many bytes per call as next will. Second, I see no good way to guarantee independence of the two generators emanating from a split. MT is hard to initialize anyway, and giant-stepping it to define the newly split generator (as we did back in the 80's paper) is not only hard for an LFSR like MT but, worse yet, it doesn't work for Haskell or other fine-grain concurrent languages because split and next will commute. Other tree RNGs, e.g. SPRNG, have the same commutativity issue. Block ciphers address this issue head-on by reducing the split independence problem to a crypto problem. A better choice might be some block cipher other than AES. Two possibilities are XTEA and RC4. Both are in Wikipedia. RC4 has 256 bytes of key "state", still bigger than I would like. Another scheme is to make the number of rounds an option. With AESNI, this could scream. Burton On Wed, Aug 17, 2011 at 12:26 PM, Ertugrul Soeylemez wrote:

Ryan Newton wrote:

Using a cryptographically strong random number generator here is probably a very bad idea. Two reasons:

Firstly while being faster than the current implementation an AES-based implementation will still be considerably slower than the Mersenne Twister algorithm. This may or may not be true, if hardware AES support is there, but don't just assume that everybody has AES instructions now. For example I don't have them.

Secondly there is no standard requiring that the default random number generator is cryptographically safe. Changing this particular implementation, which is the one most people use, to a CSPRNG will make people take for granted that System.Random is safe to use in security-related products, because it would be very convenient. This will render strong security products trivially weak, when compiled with the wrong Haskell distribution, and you will find packages with statements like: "We assume that you use Ryan Newton's distribution of the random package."

I would rather propose the Mersenne Twister as the default random number generator. You could add AES as a secondary generator for people requiring cryptographic strength, but then do it properly, i.e. impure, because most people, when reading about a PRNG with "AES" anywhere in its name, will just assume that it's a CSPRNG.

Greets, Ertugrul

-- nightmare = unsafePerformIO (getWrongWife >>= sex) http://ertes.de/

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe