Maybe it's time to have Math.random and equivalents call a CSPRNG, with a Math.insecurerandom when performance matters?
Last time this came up on HN, I measured individual reads from /dev/urandom, and those are fast enough for many large-scale applications, like one per tweet: https://news.ycombinator.com/item?id=10608843
(Obviously there are bad CSPRNGs, but there are also bad non-CS PRNGs. So let's not count those.)
The same problem exists with hash functions.
First, apparently that was unclear and I left it unspecified so note that my mention was intended about general hash functions (as you'd use in a hash table, which could easily bottleneck a benchmark without its developer realising it) not specifically cryptographic ones.
Second, so are number generators and more or less everything else (aside from KDFs), the issue is none of these are only supposed to be fast, and while they should be as fast it's usually more important that they're good, yet the incentive for language developer is to ignore good (whatever that is for the domain) and focus solely on fast. That is what my comment was about.
Basically the idea is that you have a seed which is used as an encryption key, and then you encrypt a counter value to produce an output. Using the next counter value represents the second output from the generator, and so forth. Different seeds produce different output sequences. If you accept that the encryption algorithm works properly, then the output is uncorrelated for a given counter sequence or seed sequence (although seed sequences are slightly less random than counter sequences).
You don't need to store state, and you can seek to an arbitrary position in the PRNG stream in O(1) time simply by recomputing the output for the desired counter value. For non-cryptographic applications, you can derive the seed value from some unique property of your dataset (eg id number of an item being operated upon) and then you don't even need to explicitly store the key value.
On AES-NI compatible hardware the cryptographically strong varients outperform even crushable PRNGs like Mersenne Twister. These are a fantastic choice where you have that acceleration. Your computer is built to do it really fast, and this lets you utilize that.
They also offer non-cryptographic but crush-resistant variants that roughly double that performance. These algorithms parallelize really well and those advantages are even more significant on GPUs, where memory is at a premium and cryptographic acceleration is usually not available.
http://www.thesalmons.org/john/random123/papers/random123sc1...
http://www.thesalmons.org/john/random123/releases/1.06/docs/
In oversimplified pseudo-code:
def encrypt(data, key):
counter = 0
for block in data:
yield block ^ mix(counter, key)
counter += 1
def generate(key):
counter = 0
while True:
yield mix(counter, key)
counter += 1
def hash(data, key):
state = 0
for block in data:
state = block ^ mix(state, key)
return state
When you encrypt something, the output is the same size as the input. The key is not mutated. You have to be able to go the other way if you know the key (for symmetric encryption).
When you hash something, the input is variable but the output length is fixed. Typically this is one-way - you should not be able to reconstruct the input for a given output.
When you have a stateful PRNG you get a fixed-length output but you have some internal state that gets changed with every call. So its inputs are generate(state) and you yield output and newstate. Going the other way is possible in theory but not typical.
The state for PRNGs is usually larger than the amount of output yielded, sometimes by quite a lot. E.g. Mersenne Twister has about 2.5 KB of state but yields only 32 bits of output per iteration. You generally want to store newstate every time, because setting them up is often expensive (MT takes a lot of calls before it's fully initialized and providing good randomness) and iterating through N-1 steps every time can take a very long time in a long-running program.
Usually you want PRNGs to be fast (but strongly random), but encryption and hashing should sometimes be slow (eg to protect passwords in a DB, or as a proof-of-work as in Bitcoin/Hashcash). It all depends on what role you're using them in.
You can sorta compose them into each other - like you can make a stateful PRNG by doing a hash on some internal state and then mixing some of it back into the state (eg like RDRAND). Or by encrypting a counter with a seed to make a PRNG (like Random123). Here be dragons, though - there's nothing guaranteeing your hand-rolled encryption algorithm will actually resist an attack, or whatever. So stay with a known, tested implementation.
More fundamentally it's keyed, and finding a way to make this work for an unkeyed hash is somewhat more complicated. But yes, I'm pretty sure that a secure stream cipher and a secure deterministic CSPRNG are basically the same thing.
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 failures come when you try to seed in userspace. Not when you use urandom to seed a standard algorithm, with no customizations.
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.
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?
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.
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.
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.
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$ 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
>
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
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.
Safe defaults, make the developer go out of their way to use something less safe if they really know what they're doing.
https://developer.mozilla.org/en-US/docs/Web/API/RandomSourc...
Will renaming a function or two fix my bad behaviour?
The answer to "Should I use Math.random or X" is neither! I should be using a cryptography library like SJCL or tweetnacl-js:
Also, installed browser extensions are download-once and may need cryptographic functionality.
In some cases its impossibly/impractical to create a direct connection between 2 computers: you must use some kind of relay. If you don't want the relay to comprehend the data then you can use client side crypto on the payload. TLS still matters because it prevents 3rd parties from peeking at the communication.
Imagine a secure chat app where you want to guarantee that only you and your friend can read the communications, but want to be able to send offline messages to each other that get delivered upon connection.
One valid use, I think, could be around ensuring you don't pollute your backend with user data to avoid liability.
For example, if you wanted to use a distributed database in your backend and needed guarantees that when you delete data it is deleted everywhere at once, you could use JS crypto to do client-side encryption of the data and only have to delete the key to render the distributed data inert.
I heard about this through an article that was on HN a few weeks back (https://blog.balboa.io/yet-another.html)