4 ms·
Are there any use cases for which a good CSPRNG, with a fixed 256-bit seed at process startup from /dev/urandom or equivalent, is not fast enough? Last time th
by geofft 11y ago
Are there any use cases for which a good CSPRNG, with a fixed 256-bit seed at process startup from /dev/urandom or equivalent, is not fast enough?
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 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.)
- masklinn 11y agoOne major issue is much of the "fast enough" problem is about benchmarks, and possibly even microbenchmarks. When a popular benchmark (or some rando's microbenchmark) really just exercises the RNG, the headline will still be "$FOO IS SLOW AS MOLASSES AND THAT'S BULLSHIT" not "$foo courageously uses a non-garbage RNG by default despite some performance impact in RNG-heavy scenarios". So the primary incentive for language/stdlib developers is to have a fast rng, not to have a good one. They probably aren't going to sabotage the rng entirely, but given the choice between "fast and same as everybody else" or "excellent but not as fast" chances are the first one will win, even if it's crap. The same problem exists with hash functions.
- geofft 11y agoHash functions are supposed to be fast, though. (If you need something slow like a keystretching function, you iterate a hash function, and you pick the number of iterations based on wall clock time on a representative machine.) BLAKE2 is competitive with MD5 and way, way more secure, for instance: https://blake2.net/ https://blake2.net/
- masklinn 11y ago> Hash functions are supposed to be fast, though. 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.
- paulmd 11y agoCheck out Random123, an implementation of counter-based random number generators. It won best-of-conference at the ACM Supercomputing '11 conference. 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/random123sc11.pdf http://www.thesalmons.org/john/random123/papers/random123sc1... http://www.thesalmons.org/john/random123/releases/1.06/docs/ http://www.thesalmons.org/john/random123/releases/1.06/docs/
- altern 11y agoSomewhat off-topic I guess, but aren't PRNG, hashing and (symmetric) encryption in some sense all the same thing? If you have some magic, keyed mixing function that permutes a block of data without leaking information about the key, it seems like you can implement any of the three operations. 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 And similarly, if you have any one of those functions you can implement the rest. Xor with an unpredictable stream of numbers is a good encryption method, encrypting a string of zeroes should give you unpredictable random numbers and the hash can be used as the mix function when implementing the others, etc.
- mmalone 11y agoIt'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 agoTo 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.