6 ms·

It seems to me that defaulting to a non-CSPRNG these days is a premature optimization: for many purposes a decent CSPRNG (e.g. Fortuna) is fast enough, and avoi

by zeveb 11y ago

It seems to me that defaulting to a non-CSPRNG these days is a premature optimization: for many purposes a decent CSPRNG (e.g. Fortuna) is fast enough, and avoids all the pitfalls of a non-secure or poorly-random generator. Maybe it's time to have Math.random and equivalents call a CSPRNG, with a Math.insecurerandom when performance matters?

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 ago
  One 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 ago
    Hash 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 ago
        Check 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/
- 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.
admax88q 11y ago
Yes please. It's pretty silly and dangerous to have the most accessible random number generator not be cryptographically strong. It's really not that much of a cost performance wise. Safe defaults, make the developer go out of their way to use something less safe if they really know what they're doing.
vox_mollis 11y ago
Right, well, Ptacek and Kaminsky have hashed and rehashed this argument over and over ad nauseum in a different context. I don't think the community will ever agree on this.
eliteraspberrie 11y ago
I'm the average Javascript programmer. I'm writing some web app and I need to do some cryptography. Let's see, there's Math.random and Crypto.getRandomValues. Let's go with Math.random, for shiggles. I'm probably copy-pasting from Stack Overflow. 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: http://bitwiseshiftleft.github.io/sjcl/ http://bitwiseshiftleft.github.io/sjcl/ http://dchest.github.io/tweetnacl-js/ http://dchest.github.io/tweetnacl-js/
- strangecasts 11y ago
  Out of curiosity: in which scenario is JS crypto preferable to TLS?
  - sneak 11y ago
    Well, in his web app example above, it's not - but these days more and more clientside apps (which remain on the client - e.g. mobile apps built with React Native) are implemented fully in JS. Also, installed browser extensions are download-once and may need cryptographic functionality.
  - granos 11y ago
    When you (or the recipient) don't want the recipient to be able to read the data, but only to store/transfer it somewhere. 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.
  - buu700 11y ago
    I can name exactly one. Cyph (cyph.com) accomplishes secure E2E encrypted messaging by pinning a bootstrap in the browser that validates and executes cryptographically signed packages.
cpeterso 11y ago
Applications that require a better randomness should use window.crypto.getRandomValues(). https://developer.mozilla.org/en-US/docs/Web/API/RandomSource/getRandomValues https://developer.mozilla.org/en-US/docs/Web/API/RandomSourc...

by zeveb 11y ago

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 ago
One 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 ago
  Hash 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 ago
      Check 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/
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.

admax88q 11y ago

Yes please. It's pretty silly and dangerous to have the most accessible random number generator not be cryptographically strong. It's really not that much of a cost performance wise. Safe defaults, make the developer go out of their way to use something less safe if they really know what they're doing.

vox_mollis 11y ago

Right, well, Ptacek and Kaminsky have hashed and rehashed this argument over and over ad nauseum in a different context. I don't think the community will ever agree on this.

eliteraspberrie 11y ago

I'm the average Javascript programmer. I'm writing some web app and I need to do some cryptography. Let's see, there's Math.random and Crypto.getRandomValues. Let's go with Math.random, for shiggles. I'm probably copy-pasting from Stack Overflow. 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: http://bitwiseshiftleft.github.io/sjcl/ http://bitwiseshiftleft.github.io/sjcl/ http://dchest.github.io/tweetnacl-js/ http://dchest.github.io/tweetnacl-js/

strangecasts 11y ago
Out of curiosity: in which scenario is JS crypto preferable to TLS?
- sneak 11y ago
  Well, in his web app example above, it's not - but these days more and more clientside apps (which remain on the client - e.g. mobile apps built with React Native) are implemented fully in JS. Also, installed browser extensions are download-once and may need cryptographic functionality.
- granos 11y ago
  When you (or the recipient) don't want the recipient to be able to read the data, but only to store/transfer it somewhere. 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.
- buu700 11y ago
  I can name exactly one. Cyph (cyph.com) accomplishes secure E2E encrypted messaging by pinning a bootstrap in the browser that validates and executes cryptographically signed packages.

cpeterso 11y ago

Applications that require a better randomness should use window.crypto.getRandomValues(). https://developer.mozilla.org/en-US/docs/Web/API/RandomSource/getRandomValues https://developer.mozilla.org/en-US/docs/Web/API/RandomSourc...