3 ms·

It's complicated. For starters, if you're looking for a _secure_ PRNG most practitioners would strongly advise _against_ the system you described[1]. There's a

by mmalone 11y ago

It's complicated. For starters, if you're looking for a _secure_ PRNG most practitioners would strongly advise _against_ the system you described[1]. There's a difference between a cryptographically secure algorithm and a secure system. For the overall system to be secure you need to make sure the seed data is secured, which you're bound to fail at unless you really know what you're doing. Providing a "cryptographically secure but not really secure" alternative implemented in user space alongside a "really secure" alternative that's been thoroughly vetted would likely just add to the confusion. If you _really_ need secure numbers you should be using the really secure one. The really secure one is almost definitely going to require a syscall worth of overhead, at least, so it's _definitely_ going to be slower than a PRNG like xorshift128+ which literally takes a single digit number of CPU cycles. Now to answer your question, if you're just talking about a CSPRNG algorithm they're probably fast enough for almost every use case. I think there's still an argument for some things like array shuffling, but those implementations could go out of their way to use the non-CS algorithm as an optimization. Unfortunately in Javascript land there's aren't many batteries included, so if you switched Math.random() to use a CSPRNG most people would end up using it for trivial stuff like shuffling arrays. If you're talking about a secure system... it's probably still fast enough for most things, but it's less obvious. [1]http://sockpuppet.org/blog/2014/02/25/safely-generate-random-numbers/ http://sockpuppet.org/blog/2014/02/25/safely-generate-random...

Dylan16807 11y ago
"good CSPRNG, with a fixed 256-bit seed at process startup from /dev/urandom" does describe a secure system. It doesn't take a syscall, and it's not fake-secure. The failures come when you try to seed in userspace. Not when you use urandom to seed a standard algorithm, with no customizations.
- geofft 11y ago
  To be fair, the failures in that article are from userspace CSPRNGs that got even that part wrong. Debian's problem was commenting out the lines that seeded the RNG from /dev/urandom, and Android's problem was developers that used the RNG unseeded. They trouble wasn't re-seeding -- they weren't seeding in the first place. However, if we are going to decide as an industry that we need a userspace CSPRNG, it's not that hard of a job to write a single, high-quality, cross-platform implementation of a seeded-once CSPRNG that introduces no vulnerabilities beyond the kernel CSPRNG.
  - Dylan16807 11y ago
    You could do that, but the code to do something like create an instance of ChaCha20, fill the parameters from urandom, and pull numbers from it is a handful of trivial lines.
- mmalone 11y ago
  It's not just the initial seeding, you also need correct reseeding, you need to make sure the state doesn't leak somehow, and you need to make sure you're actually getting the seed data securely. If you're doing something that's crypto related there really are a lot of things you can screw up in user space. Using urandom directly is your best bet. It's not fake secure, it's just non-trivial to get right.
  - Dylan16807 11y ago
    You don't need to reseed. If the only access is a function that spits out a random number it's trivial to not let the state leak. If you can't figure out how to open urandom securely to get the seed data, how are you going to use urandom every time you need a number?
    - mmalone 11y ago
      Incorrect. You may be thinking of the "/dev/random vs. /dev/urandom" argument, which says it's stupid to _block_ on reseeding based on some arbitrary heuristic (and which I agree with). However, that doesn't mean reseeding is unnecessary. Even a CSPRNG cycles and you need to reseed before it does so or the wheels start to come off. Generators become less random looking even before cycling. The general rule is that you shouldn't use more than sqrt(cycle length) from a single generator. If you use a secure n-bit block cipher in counter mode, for instance (generally considered a "good CSPRNG") then the generated numbers start to become distinguishable from random after 2^(n/2) generated blocks due to lack of collisions. This is a weak statement, but the point is any proofs that assume randomness (likely all proofs of hardness of crypto reversal) no longer hold. If you don't reseed before this point then you're doing it wrong. Other desirable characteristics of CSPRNGs, like forward secrecy, may require periodic (or frequent) reseeding depending on algorithm. Best practice for a source of secure "randomness" is to use an entropy accumulator that finds as much "true entropy" as it can and constantly mixes that into a pool (while protecting against injection attacks), then to use a good CSPRNG algorithm to "stretch" the available entropy since true entropy is a scarce resource. That's what urandom and OpenSSL do, for instance (see Yarrow/Fortuna for a good design). A lot of thought has been put into the design of urandom. Pulling one random seed from urandom and stretching it forever in user-space is _not_ equivalent. You could probably design something in user-space that _is_ as secure, but it's not trivial.
geofft 11y ago
The benchmarks I linked to imply that even getting your random numbers straight out of /dev/urandom is fine, even for the "trivial stuff". On my current machine (Chrome 47, new-ish MacBook Pro), it takes me 4 seconds to run `for (var i = 0; i < 1000000; i++) {Math.random()}`. Each call to Math.random() generates an 8-byte floating point number, and it takes 0.6 seconds to `dd if=/dev/urandom bs=8 count=1000000 of=/dev/null`. If you don't want to buffer, and switch it to a million 8-byte reads, it goes up to 1.5 seconds. I don't think the system call overhead is a problem here.
- mmalone 11y ago
  Eh, I'm not sure where you're getting your numbers. Here's a quick test using node 0.10.40 on my machine: mmalone$ node > var f = function() { ... s = Date.now() ... for (var i = 0; i < 1000000; i++) {Math.random()} ... return Date.now() - s ... } undefined > f() 3 > f() 1 > f() 1 > So I'm getting a couple milliseconds for 1,000,000 numbers. I'm also toying around with a PRNG package in Go currently so I have some numbers there too: BenchmarkXorshift128p-8 500000000 2.98 ns/op BenchmarkXorshift1024s-8 300000000 4.62 ns/op BenchmarkXorshift4096s-8 300000000 4.44 ns/op BenchmarkXorshift4096ss-8 200000000 6.29 ns/op BenchmarkUint64sFromCryptoRandIdiomatic-8 200000 10736 ns/op BenchmarkUint64sFromCryptoRandUnsafe-8 200000 8081 ns/op Go's crypto source pulls from urandom. This is more like what I'd expect in terms of performance. The difference is orders of magnitude, but we're still talking about microseconds so I think your argument is still valid. A proper CSPRNG is not "as fast" but it is probably "fast enough" for most use cases.
  - geofft 11y ago
    Probably me not actually knowing what I'm doing. :) I was testing in the Chrome JS console, and if I define your function, it's way faster than the standalone for loop. But yeah, I think my underlying argument is roughly that if you do a naive / obvious shuffle of a list in JS using Math.floor(Math.random() * list.length), given the inherent overhead of manipulating a JS list, you aren't going to notice the overhead of a proper CSPRNG. I'm not totally sure if it's true, but I think it is likely to be true.

by mmalone 11y ago

Dylan16807 11y ago

"good CSPRNG, with a fixed 256-bit seed at process startup from /dev/urandom" does describe a secure system. It doesn't take a syscall, and it's not fake-secure. The failures come when you try to seed in userspace. Not when you use urandom to seed a standard algorithm, with no customizations.

geofft 11y ago
To be fair, the failures in that article are from userspace CSPRNGs that got even that part wrong. Debian's problem was commenting out the lines that seeded the RNG from /dev/urandom, and Android's problem was developers that used the RNG unseeded. They trouble wasn't re-seeding -- they weren't seeding in the first place. However, if we are going to decide as an industry that we need a userspace CSPRNG, it's not that hard of a job to write a single, high-quality, cross-platform implementation of a seeded-once CSPRNG that introduces no vulnerabilities beyond the kernel CSPRNG.
- Dylan16807 11y ago
  You could do that, but the code to do something like create an instance of ChaCha20, fill the parameters from urandom, and pull numbers from it is a handful of trivial lines.
mmalone 11y ago
It's not just the initial seeding, you also need correct reseeding, you need to make sure the state doesn't leak somehow, and you need to make sure you're actually getting the seed data securely. If you're doing something that's crypto related there really are a lot of things you can screw up in user space. Using urandom directly is your best bet. It's not fake secure, it's just non-trivial to get right.
- Dylan16807 11y ago
  You don't need to reseed. If the only access is a function that spits out a random number it's trivial to not let the state leak. If you can't figure out how to open urandom securely to get the seed data, how are you going to use urandom every time you need a number?
  - mmalone 11y ago
    Incorrect. You may be thinking of the "/dev/random vs. /dev/urandom" argument, which says it's stupid to _block_ on reseeding based on some arbitrary heuristic (and which I agree with). However, that doesn't mean reseeding is unnecessary. Even a CSPRNG cycles and you need to reseed before it does so or the wheels start to come off. Generators become less random looking even before cycling. The general rule is that you shouldn't use more than sqrt(cycle length) from a single generator. If you use a secure n-bit block cipher in counter mode, for instance (generally considered a "good CSPRNG") then the generated numbers start to become distinguishable from random after 2^(n/2) generated blocks due to lack of collisions. This is a weak statement, but the point is any proofs that assume randomness (likely all proofs of hardness of crypto reversal) no longer hold. If you don't reseed before this point then you're doing it wrong. Other desirable characteristics of CSPRNGs, like forward secrecy, may require periodic (or frequent) reseeding depending on algorithm. Best practice for a source of secure "randomness" is to use an entropy accumulator that finds as much "true entropy" as it can and constantly mixes that into a pool (while protecting against injection attacks), then to use a good CSPRNG algorithm to "stretch" the available entropy since true entropy is a scarce resource. That's what urandom and OpenSSL do, for instance (see Yarrow/Fortuna for a good design). A lot of thought has been put into the design of urandom. Pulling one random seed from urandom and stretching it forever in user-space is _not_ equivalent. You could probably design something in user-space that _is_ as secure, but it's not trivial.

geofft 11y ago

The benchmarks I linked to imply that even getting your random numbers straight out of /dev/urandom is fine, even for the "trivial stuff". On my current machine (Chrome 47, new-ish MacBook Pro), it takes me 4 seconds to run `for (var i = 0; i < 1000000; i++) {Math.random()}`. Each call to Math.random() generates an 8-byte floating point number, and it takes 0.6 seconds to `dd if=/dev/urandom bs=8 count=1000000 of=/dev/null`. If you don't want to buffer, and switch it to a million 8-byte reads, it goes up to 1.5 seconds. I don't think the system call overhead is a problem here.

mmalone 11y ago
Eh, I'm not sure where you're getting your numbers. Here's a quick test using node 0.10.40 on my machine: mmalone$ node > var f = function() { ... s = Date.now() ... for (var i = 0; i < 1000000; i++) {Math.random()} ... return Date.now() - s ... } undefined > f() 3 > f() 1 > f() 1 > So I'm getting a couple milliseconds for 1,000,000 numbers. I'm also toying around with a PRNG package in Go currently so I have some numbers there too: BenchmarkXorshift128p-8 500000000 2.98 ns/op BenchmarkXorshift1024s-8 300000000 4.62 ns/op BenchmarkXorshift4096s-8 300000000 4.44 ns/op BenchmarkXorshift4096ss-8 200000000 6.29 ns/op BenchmarkUint64sFromCryptoRandIdiomatic-8 200000 10736 ns/op BenchmarkUint64sFromCryptoRandUnsafe-8 200000 8081 ns/op Go's crypto source pulls from urandom. This is more like what I'd expect in terms of performance. The difference is orders of magnitude, but we're still talking about microseconds so I think your argument is still valid. A proper CSPRNG is not "as fast" but it is probably "fast enough" for most use cases.
- geofft 11y ago
  Probably me not actually knowing what I'm doing. :) I was testing in the Chrome JS console, and if I define your function, it's way faster than the standalone for loop. But yeah, I think my underlying argument is roughly that if you do a naive / obvious shuffle of a list in JS using Math.floor(Math.random() * list.length), given the inherent overhead of manipulating a JS list, you aren't going to notice the overhead of a proper CSPRNG. I'm not totally sure if it's true, but I think it is likely to be true.