Re: [Python-ideas] Should our default random number generator be secure?
[Tim, on parallel PRNGs]
There are some clean and easy approaches to this based on crypto-inspired schemes, but giving up crypto strength for speed. If you haven't read it, this paper is delightful:
http://www.thesalmons.org/john/random123/papers/random123sc11.pdf
[Nathaniel Smith]
It really is! As AES acceleration instructions become more common (they're now standard IIUC on x86, x86-64, and even recent ARM?), even just using AES in CTR mode becomes pretty compelling -- it's fast, deterministic, provably equidistributed, *and* cryptographically secure enough for many purposes.
Excellent - we're going to have a hard time finding something real to disagree about :-)
(Compared to a true state-of-the-art CPRNG the naive version fails due to lack of incremental mixing, and the use of a reversible transition function. But even these are mostly only important to protect against attackers who have access to your memory -- which is not trivial as heartbleed shows, but still, it's *waaay* ahead of something like MT on basically every important axis.)
Except for wide adoption. Most people I bump into never even heard of this kind of approach. Nobody ever got fired for buying IBM, and nobody ever got fired for recommending MT - it's darned near a checklist item when shopping for a language. I may have to sneak the code in while you distract Guido with a provocative rant about the inherent perfidy of the Dutch character ;-)
On Wed, Sep 9, 2015 at 9:47 PM, Tim Peters tim.peters@gmail.com wrote:
[Tim, on parallel PRNGs]
There are some clean and easy approaches to this based on crypto-inspired schemes, but giving up crypto strength for speed. If you haven't read it, this paper is delightful:
http://www.thesalmons.org/john/random123/papers/random123sc11.pdf[Nathaniel Smith]
It really is! As AES acceleration instructions become more common (they're now standard IIUC on x86, x86-64, and even recent ARM?), even just using AES in CTR mode becomes pretty compelling -- it's fast, deterministic, provably equidistributed, *and* cryptographically secure enough for many purposes.
Excellent - we're going to have a hard time finding something real to disagree about :-)
(Compared to a true state-of-the-art CPRNG the naive version fails due to lack of incremental mixing, and the use of a reversible transition function. But even these are mostly only important to protect against attackers who have access to your memory -- which is not trivial as heartbleed shows, but still, it's *waaay* ahead of something like MT on basically every important axis.)
Except for wide adoption. Most people I bump into never even heard of this kind of approach. Nobody ever got fired for buying IBM, and nobody ever got fired for recommending MT - it's darned near a checklist item when shopping for a language. I may have to sneak the code in while you distract Guido with a provocative rant about the inherent perfidy of the Dutch character ;-)
:-)
Srsly though, we've talked about switching to some kind of CTR-mode RNG as the default in NumPy (where speed differences are pretty visible, b/c we support generating big blocks of random numbers at once), and would probably accept a patch. (Just in case Guido is undisturbed by scurrilous allegations.)
participants (2)
-
Nathaniel Smith -
Tim Peters