Comment by mmalone | Hacker News Reader

Comment by mmalone | Hacker News Reader

Parent Full thread

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...

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.

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.

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.

"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.

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.

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.

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.

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?

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.

If you're using 384 bits of state as with ChaCha20, you do not need to reseed for quality reasons.

Adding in more is nice of the kernel but not necessary. If the pool doesn't already have enough entropy to last the lifetime of the computer, I would prefer not to trust it yet.

Oh, one more thought since I didn't really address state leak. Let's pretend we're in a C-like language that is not memory safe. You're not reseeding and you don't have forward secrecy. Someone finds a buffer overflow and manages to get your CSPRNG state. Now they can recover the sequence of randomness you've handed out in the past (maybe they're access tokens, for instance). It's not a trivial attack, but it's plausible.

If you don't like the buffer overflow example, let's make it a misconfigured website that leaks the state in an error message or stack trace served to an end user.

The simpler design is probably to just fill a pool of entropy from urandom in user-space and give out numbers from that pool, thus amortizing the syscall overhead. Even that would be not-quite-as-good-as-urandom (still more that could go wrong), but it's probably as close as you can easily get.

Reply on news.ycombinator.com