4 ms·

My layman's understanding of the two is that /dev/urandom will happily output more bits than it has been seeded with, and so is unsuitable for use in cryptograp

My layman's understanding of the two is that /dev/urandom will happily output more bits than it has been seeded with, and so is unsuitable for use in cryptography, as it can output correlated values. Is my understanding here incorrect?

segfaultbuserr 8y ago
(edit: I see my parent post is being downvoted. How can this be? The commenter is just asking a question...) It is incorrect. Both /dev/urandom and /dev/random are connected to a CSPRNG. Once a CSPRNG is initialized by SUFFICIENT unpredictable inputs, it's forever unpredictable for (practically) unlimited output (something 2^128). If the CSPRNG algorithm is cryptographically-secure, and the implementation doesn't leak its internal state, it would be safe to use it for almost all cryptographic purposes. However, the original design in the Linux kernel was paranoid enough, it blocks /dev/random (even if a CSPRNG can output unlimited random bytes) if the kernel thinks the the output has exceeded the estimated uncertainty from all the random events. Most cryptographers believe if a broken CSPRNG is something you need to protect yourself from, you already have a bigger trouble, and it's unnecessary from a cryptographic point-of-view to be paranoid about a properly-initialized CSPRNG. /dev/random found on other BSDs is (almost) equivalent to Linux's /dev/urandom. However, /dev/urandom has its own issues on Linux. Unlike BSD's implementation, it doesn't block even if the CSPRNG is NOT initialized during early boot. If you automatically generate a key for, e.g. SSH, at this point, you'll have serious troubles - predictable keys, so reading from /dev/random still has a point, although not for 90% of the programs. I think it's a prefect example of being overly-paranoid about unlikely dangers, while overlooking straightforward problems that are likely to occur. The current recommended practice is to call getrandom() system call (and arc4random()* on BSDs) when it's available, instead of reading from raw /dev/random or /dev/urandom. It blocks, until the CSPRNG is initialized, otherwise it always outputs something. *and no, it's not RC4-based, but ChaCha20-based on new systems.
- loeg 8y ago
  > /dev/random found on other BSDs is equivalent to Linux's /dev/urandom. This isn't quite true. The BSDs random (and urandom) block until initially seeded, unlike Linux's urandom. Then they don't block. (Like the getrandom/getentropy behavior.) > The current recommended practice is to call getrandom() system call (and arc4random() on BSDs) when it's available, instead of reading from raw /dev/random or /dev/urandom. It blocks when the CSPRNG is initialized, but otherwise it always outputs something. +1 (I'd phrase that as "blocks until the CSPRNG is initialized," which for non-embedded systems will always be before userland programs can even run, and for embedded should not take long after system start either).
  - segfaultbuserr 8y ago
    Thanks for the correction, fixed. It was a bit difficult for me to paraphrase it...
- int_19h 8y ago
  Python had an internal fight of its own about how to handle it right, too. https://www.python.org/dev/peps/pep-0524/ https://www.python.org/dev/peps/pep-0524/
- nullc 8y ago
  > it blocks /dev/random (even if a CSPRNG can output unlimited random bytes) if the kernel thinks the the output has exceeded the estimated uncertainty from all the random events. Most cryptographers believe if a broken CSPRNG is something you need to protect yourself from, you already have a bigger trouble, Not just that, but if you have a threat model where you actually need information theoretic security (e.g. you're conjecturing a computationally unbounded attacker or at least a quantum computer)-- the /dev/random output is _still_ just a CSPRNG and simply rate limiting it doesn't actually make a strong guarantee about the information theoretic randomness of the output. To provide information theoretic security the function design would need to guarantee that at least some known fraction of the entropy going in actually made it to the output. Common CSPRNGs don't do this. So you could debate if information theoretic security is something someone actually ever actually needs-- but if you do need it, /dev/random doesn't give it to you regardless. [And as you note, urandom doesn't block when not adequately seeded ... so the decision to make /dev/random block probably actually exposed a lot of parties to exploit and probably doesn't provide strong protection even against fantasy land attacks :(]
  - bscphil 8y ago
    > simply rate limiting it doesn't actually make a strong guarantee about the information theoretic randomness of the output. To provide information theoretic security the function design would need to guarantee that at least some known fraction of the entropy going in actually made it to the output. Common CSPRNGs don't do this. This is an interesting point I hadn't thought about before, so thanks for that. I suppose if you're generating a OTP or something like that, there might be some small advantage to using /dev/random, but the probability of it making a difference is pretty remote. The one thing I haven't been able to figure out is why Linux hasn't "fixed" both /dev/random and /dev/urandom to block until they have sufficient entropy at boot and then never block again. That seems like obviously the optimal behavior.
    - nullc 8y ago
      Blocking could potentially result in the system getting stuck during boot and simply staying that way. Compatiblity is a bear. The getentropy syscall does the reasonable thing.
- kccqzy 8y ago
  I think getrandom(2) is a fine choice, but if you are using the C library (as opposed to using asm directives to make syscalls), getentropy(3) is even better. No need to think about the third `flags` handler or read a long section about interruption by a signal handler.
- zeveb 8y ago
  It's important to note here that Linux's behaviour is broken, plain and simple: /dev/random blocks even if properly seeded, and /dev/urandom doesn't block even if improperly seeded. The Real Solution™ is to make /dev/random and /dev/urandom the same thing, and make them both block until properly seeded. And replace the current ad-hoc CSPRNG with a decent one, e.g. Fortuna. There were patches almost 15 years ago implementing this (https://lwn.net/Articles/103653/ https://lwn.net/Articles/103653/), but they were rejected. There's simply no good reason not to fix Linux's CSPRNG.
gizmo686 8y ago
Yes and no. Much of cryptography is based on psuedorandom number generators, which output more bits than they are seeded with. If these PRNGs are not secure, then almost any piece of cryptography you actually use would be insecure independent of your choice to use random or urandom. Unless all of your cryptography is information-theoretically secure, there is no problem using a PRNG. If you happen to be using a an information-theoretically secure algorithm than you are theoretically weaker using a limited entropy PRNG; but there is no practical implications of this.
- throwawaymath 8y ago
  The only information theoretically secure encryption algorithm is a one-time pad seeded with true randomness. In fact, you cannot achieve information theoretic security using a pseudorandom generator of any kind.
  - gizmo686 8y ago
    Its not an encryption algorithm, but Shamirinformation theoretically secure 's secret sharing is also information theoretically secure.

segfaultbuserr 8y ago

(edit: I see my parent post is being downvoted. How can this be? The commenter is just asking a question...) It is incorrect. Both /dev/urandom and /dev/random are connected to a CSPRNG. Once a CSPRNG is initialized by SUFFICIENT unpredictable inputs, it's forever unpredictable for (practically) unlimited output (something 2^128). If the CSPRNG algorithm is cryptographically-secure, and the implementation doesn't leak its internal state, it would be safe to use it for almost all cryptographic purposes. However, the original design in the Linux kernel was paranoid enough, it blocks /dev/random (even if a CSPRNG can output unlimited random bytes) if the kernel thinks the the output has exceeded the estimated uncertainty from all the random events. Most cryptographers believe if a broken CSPRNG is something you need to protect yourself from, you already have a bigger trouble, and it's unnecessary from a cryptographic point-of-view to be paranoid about a properly-initialized CSPRNG. /dev/random found on other BSDs is (almost) equivalent to Linux's /dev/urandom. However, /dev/urandom has its own issues on Linux. Unlike BSD's implementation, it doesn't block even if the CSPRNG is NOT initialized during early boot. If you automatically generate a key for, e.g. SSH, at this point, you'll have serious troubles - predictable keys, so reading from /dev/random still has a point, although not for 90% of the programs. I think it's a prefect example of being overly-paranoid about unlikely dangers, while overlooking straightforward problems that are likely to occur. The current recommended practice is to call getrandom() system call (and arc4random()* on BSDs) when it's available, instead of reading from raw /dev/random or /dev/urandom. It blocks, until the CSPRNG is initialized, otherwise it always outputs something. *and no, it's not RC4-based, but ChaCha20-based on new systems.

loeg 8y ago
> /dev/random found on other BSDs is equivalent to Linux's /dev/urandom. This isn't quite true. The BSDs random (and urandom) block until initially seeded, unlike Linux's urandom. Then they don't block. (Like the getrandom/getentropy behavior.) > The current recommended practice is to call getrandom() system call (and arc4random() on BSDs) when it's available, instead of reading from raw /dev/random or /dev/urandom. It blocks when the CSPRNG is initialized, but otherwise it always outputs something. +1 (I'd phrase that as "blocks until the CSPRNG is initialized," which for non-embedded systems will always be before userland programs can even run, and for embedded should not take long after system start either).
- segfaultbuserr 8y ago
  Thanks for the correction, fixed. It was a bit difficult for me to paraphrase it...
int_19h 8y ago
Python had an internal fight of its own about how to handle it right, too. https://www.python.org/dev/peps/pep-0524/ https://www.python.org/dev/peps/pep-0524/
nullc 8y ago
> it blocks /dev/random (even if a CSPRNG can output unlimited random bytes) if the kernel thinks the the output has exceeded the estimated uncertainty from all the random events. Most cryptographers believe if a broken CSPRNG is something you need to protect yourself from, you already have a bigger trouble, Not just that, but if you have a threat model where you actually need information theoretic security (e.g. you're conjecturing a computationally unbounded attacker or at least a quantum computer)-- the /dev/random output is _still_ just a CSPRNG and simply rate limiting it doesn't actually make a strong guarantee about the information theoretic randomness of the output. To provide information theoretic security the function design would need to guarantee that at least some known fraction of the entropy going in actually made it to the output. Common CSPRNGs don't do this. So you could debate if information theoretic security is something someone actually ever actually needs-- but if you do need it, /dev/random doesn't give it to you regardless. [And as you note, urandom doesn't block when not adequately seeded ... so the decision to make /dev/random block probably actually exposed a lot of parties to exploit and probably doesn't provide strong protection even against fantasy land attacks :(]
- bscphil 8y ago
  > simply rate limiting it doesn't actually make a strong guarantee about the information theoretic randomness of the output. To provide information theoretic security the function design would need to guarantee that at least some known fraction of the entropy going in actually made it to the output. Common CSPRNGs don't do this. This is an interesting point I hadn't thought about before, so thanks for that. I suppose if you're generating a OTP or something like that, there might be some small advantage to using /dev/random, but the probability of it making a difference is pretty remote. The one thing I haven't been able to figure out is why Linux hasn't "fixed" both /dev/random and /dev/urandom to block until they have sufficient entropy at boot and then never block again. That seems like obviously the optimal behavior.
  - nullc 8y ago
    Blocking could potentially result in the system getting stuck during boot and simply staying that way. Compatiblity is a bear. The getentropy syscall does the reasonable thing.
kccqzy 8y ago
I think getrandom(2) is a fine choice, but if you are using the C library (as opposed to using asm directives to make syscalls), getentropy(3) is even better. No need to think about the third `flags` handler or read a long section about interruption by a signal handler.
zeveb 8y ago
It's important to note here that Linux's behaviour is broken, plain and simple: /dev/random blocks even if properly seeded, and /dev/urandom doesn't block even if improperly seeded. The Real Solution™ is to make /dev/random and /dev/urandom the same thing, and make them both block until properly seeded. And replace the current ad-hoc CSPRNG with a decent one, e.g. Fortuna. There were patches almost 15 years ago implementing this (https://lwn.net/Articles/103653/ https://lwn.net/Articles/103653/), but they were rejected. There's simply no good reason not to fix Linux's CSPRNG.

gizmo686 8y ago

Yes and no. Much of cryptography is based on psuedorandom number generators, which output more bits than they are seeded with. If these PRNGs are not secure, then almost any piece of cryptography you actually use would be insecure independent of your choice to use random or urandom. Unless all of your cryptography is information-theoretically secure, there is no problem using a PRNG. If you happen to be using a an information-theoretically secure algorithm than you are theoretically weaker using a limited entropy PRNG; but there is no practical implications of this.

throwawaymath 8y ago
The only information theoretically secure encryption algorithm is a one-time pad seeded with true randomness. In fact, you cannot achieve information theoretic security using a pseudorandom generator of any kind.
- gizmo686 8y ago
  Its not an encryption algorithm, but Shamirinformation theoretically secure 's secret sharing is also information theoretically secure.