4 ms·

An Analysis of OpenSSL's Random Number Generator

77 points by randombit 10y ago

RRRA 10y ago
Are any OpenSSL fork vulnerable in the same way?
- Titanous 10y ago
  No. Both BoringSSL and LibreSSL use substantially different (and safer) systems for their CSPRNG. https://boringssl.googlesource.com/boringssl.git/+/refs/heads/master/crypto/rand/rand.c https://boringssl.googlesource.com/boringssl.git/+/refs/head... https://github.com/libressl-portable/openbsd/blob/master/src/lib/libc/crypt/arc4random.3 https://github.com/libressl-portable/openbsd/blob/master/src...
ryuuchin 10y ago
I can't understand Why OpenSSL continues to use it's own PRNG implimentation when we have /dev/urandom and CryptGenRandom which are known to be good. This is basically what BoringSSL does (although if you have rdrand then it will get filtered through a ChaCha20 instance). I'm pretty sure OpenSSL doesn't even reseed its PRNG on Windows unless the calling application does it so I'm not sure how that's safe either. If you look at applications using OpenSSL like OpenVPN I don't see any calls to the PRNG init function to ensure it has enough entropy. I'm not sure of the security impact of this.
- cyphar 10y ago
  I think you mean /dev/random. On unixes, /dev/urandom produces a stream of random bytes that may not have high entropy, while /dev/random will block on reads until there's enough entropy in the pool.
  - anaphor 10y ago
    nope, that's a myth http://www.2uo.de/myths-about-urandom/ http://www.2uo.de/myths-about-urandom/
    - cyphar 10y ago
      Interesting. I picked up that misconception from a Linux kernel comment a while ago. Thanks for telling me it's a myth. I knew that the two outputs came from the same source, I just assumed that the blocking had more-than-negligible effects.
    - slavik81 10y ago
      That link appears to confirm cyphar's assertion that /dev/urandom may produce a low-entropy output stream in certain circumstances. > Linux's /dev/urandom happily gives you not-so-random numbers before the kernel even had the chance to gather entropy. When is that? At system start, booting the computer.
      - geofft 10y ago
        One of the very early initscripts (on Debian, /etc/rcS.d/urandom or /lib/systemd/system/urandom.service, both of which happen well before normal initscripts) restores a random seed that was saved at last shutdown. After this script runs, the numbers are back to being cryptographically pseudorandom. Before this script runs, lots of other stuff isn't set up -- no networking, no remote filesystems, possibly not even swap -- so if you're writing code that needs to run there, you hopefully know that the system is in a weird state. And if you're writing something that runs a service that needs secure random numbers that early in the boot process, you're definitely doing something nonstandard and possibly misguided, and it's reasonable for the burden to be on you to take appropriate precautions, or switch to doing something normal. For normal application developers, who tend to wait until after the network is up to interact with the network, this special case doesn't apply.
        slavik81 10y ago
        The usual time I've been concerned has been after creating a new virtual machine. Right after creating a new DO droplet I need to do a bunch of things to set up my application, like seed my CSRF token generator. Of course, /dev/random would block for ages at that point, so I instead generate the seed on a different machine.
  - ryuuchin 10y ago
    No I definitly mean /dev/urandom[1] or the getrandom syscall which would be equal to /dev/urandom. [1] http://sockpuppet.org/blog/2014/02/25/safely-generate-random-numbers/ http://sockpuppet.org/blog/2014/02/25/safely-generate-random...
- rootw0rm 10y ago
  It depends upon which of the many functions you call to get your bits, iirc. I've been studying it a bit, though i've taken a little break, so i'd need to find my notes. it's certainly terrible on windows, but not completely broken...only semi-broken, lol. i think i remember there being some ancient reseeding mechanism that only works on XP in there somewhere too, but fuck it i'm drunk.
  - erichurkman 10y ago
    Isn't 'semi-broken' equal to 'broken' for cryptographic purposes?
- miles 10y ago
  "/dev/urandom and CryptGenRandom which are known to be good" Check out "A good idea with bad usage: /dev/urandom": http://insanecoding.blogspot.com/2014/05/a-good-idea-with-bad-usage-devurandom.html http://insanecoding.blogspot.com/2014/05/a-good-idea-with-ba... Just stumbled onto it in the new submissions queue: https://news.ycombinator.com/item?id=11485876 https://news.ycombinator.com/item?id=11485876
  - geofft 10y ago
    ... I'm not sure I can take an article seriously that suggests "but what if the attacker can modify files in /dev?". In any case, the meaningful concerns from that article have been addressed with the getrandom syscall on Linux, introduced a few months after this article was written: https://lwn.net/Articles/606141/ https://lwn.net/Articles/606141/ Perhaps we should start saying "getrandom" / "getentropy" instead of "/dev/urandom", but they're the same underlying CSPRNG (although getrandom has the distinct advantage of allowing you to tell if the urandom pool has been initialized, which /dev/urandom doesn't let you do), so I can understand being sloppy with usage. I would sort of assume anyone in a position to patch OpenSSL's RNG either upstream or in a distro is aware of getrandom and why it exists, but maybe that's a bad assumption.
    - ryuuchin 10y ago
      I forgot about the new getrandom syscall but yes that would be preferred if supported.
  - maxerickson 10y ago
    That article says //Continue filling with other sources where it should say //exit with an error.
- neerdowell 10y ago
  /dev/urandom isn't reliable; it fails in a chroot, if file handles are exhausted, etc.
  - jjnoakes 10y ago
    It fails in a poorly set up chroot, not any old chroot. It also fails in a poorly set up root file system in the same way. No chroot needed. I can't remember ever running out of file descriptors unless a program had a leak. But if you want to argue that position too, make sure you mention that cputime and memory could also be exhausted, leading to... well... any other method failing in a similar fashion. A system call definitely has some minor benefits over a file in /dev, bit the reverse is also true (access from shells, or any language really, with no built in support). But calling /dev/urandom unreliable is a little bit intellectually dishonest.
    - neerdowell 10y ago
      > It fails in a poorly set up chroot, not any old chroot. It fails for any program that calls chroot(2) and chroots to a location that hasn't had /dev/urandom constructed, which is... almost every program that sandboxes by calling chroot(2). > I can't remember ever running out of file descriptors unless a program had a leak. You've probably never used ulimits or login groups then. > But if you want to argue that position too, make sure you mention that cputime and memory could also be exhausted, leading to... well... any other method failing in a similar fashion. You're writing a library and in one of the functions you call arc4random(3). How would you handle memory being exhausted at the time when arc4random is called? Hint: you wouldn't. You'd let the OS handle it, probably by terminating something. Which might be the running process or another process. New situation, you're writing a library and in one of the functions you open() a file handle and read() from it. How would you handle that operation failing? Thought about it? Got your answer? Good. Now see the comments in LibreSSL for why your answer to that is wrong: https://github.com/libressl-portable/openbsd/blob/cb62fd8b9b1d3f0cdfb5445d0c53b560707a3376/src/lib/libcrypto/crypto/getentropy_linux.c#L120-L163 https://github.com/libressl-portable/openbsd/blob/cb62fd8b9b... > But calling /dev/urandom unreliable is a little bit intellectually dishonest. /dev/urandom is not a high-availability randomness source, therefore it is unreliable. It is not intellectually dishonest, it is a statement of fact.
- caf 10y ago
  Seeding a userspace CSPRNG from /dev/urandom or getrandom(2) is actually the right approach. The kernel pool is a resource shared among all processes, with the locking and therefore scalability constraints that implies.
  - KMag 10y ago
    Also, it's a good idea to reseed your userspace CSPRNG from the kernel's entropy source periodically. This is precisely what OpenBSD did with their arc4random and arc4random_buf library calls. (Don't worry, they now use ChaCha20 instead of arcfour/RC-4, but have kept the function name unchanged, since it's a backward-compatible change... the only way a caller can tell RC-4 from ChaCha20 is by detecting small statistical biases in RC-4's outputs.)
zer01 10y ago
Reminds me of one of my favorite commit logs from the LibreSSL project: "Do not feed RSA private key information to the random subsystem as entropy. It might be fed to a pluggable random subsystem…. What were they thinking?!" http://opensslrampage.org/post/83007010531/well-even-if-time-isnt-random-your-rsa http://opensslrampage.org/post/83007010531/well-even-if-time...
- plaguuuuuu 10y ago
  that sounds unsafe
  - Natanael_L 10y ago
    A hash of the private key isn't actually bad to use for entropy. It's what's done in deterministic EC signatures, deriving the k value from the private key + message.
    - Natanael_L 10y ago
      As long as the hash function is strong, why exactly would this be weak? Downvoting me implies you believe these people are wrong too; https://tools.ietf.org/html/rfc6979 https://tools.ietf.org/html/rfc6979 > It is possible to turn DSA and ECDSA into deterministic schemes by using a deterministic process for generating the "random" value k. That process must fulfill some cryptographic characteristics in order to maintain the properties of verifiability and unforgeability expected from signature schemes; namely, for whoever does not know the signature private key, the mapping from input messages to the corresponding k values must be computationally indistinguishable from what a randomly and uniformly chosen function (from the set of messages to the set of possible k values) would return. > d. Set: > K = HMAC_K(V || 0x00 || int2octets(x) || bits2octets(h1)) > where '||' denotes concatenation. In other words, we compute HMAC with key K, over the concatenation of the following, in order: the current value of V, a sequence of eight bits of value 0, the encoding of the (EC)DSA private key x, and the hashed message (possibly truncated and extended as specified by the bits2octets transform). The HMAC result is the new value of K. Note that the private key x is in the [1, q-1] range, hence a proper input for int2octets, yielding rlen bits of output, i.e., an integral number of octets (rlen is a multiple of 8).
rootw0rm 10y ago
I actually have several TB of OpenSSL PRNG output (256 bit len) that I've been analyzing. A fairly modest sample size, but I've come across some interesting patterns at the bit level. It's kind of a pain in the ass to write efficient analytics for a binary 256 bit pattern as a matter of fact.
- dchest 10y ago
  That's numerology, you just have many outputs of SHA1 with different inputs.
- ICallsBS 10y ago
  10^9 out of 10^25 different combinations is a significant sample size? Wouldn't the law of small numbers apply in this case?

77 points by randombit 10y ago

RRRA 10y ago

Are any OpenSSL fork vulnerable in the same way?

Titanous 10y ago
No. Both BoringSSL and LibreSSL use substantially different (and safer) systems for their CSPRNG. https://boringssl.googlesource.com/boringssl.git/+/refs/heads/master/crypto/rand/rand.c https://boringssl.googlesource.com/boringssl.git/+/refs/head... https://github.com/libressl-portable/openbsd/blob/master/src/lib/libc/crypt/arc4random.3 https://github.com/libressl-portable/openbsd/blob/master/src...

ryuuchin 10y ago

I can't understand Why OpenSSL continues to use it's own PRNG implimentation when we have /dev/urandom and CryptGenRandom which are known to be good. This is basically what BoringSSL does (although if you have rdrand then it will get filtered through a ChaCha20 instance). I'm pretty sure OpenSSL doesn't even reseed its PRNG on Windows unless the calling application does it so I'm not sure how that's safe either. If you look at applications using OpenSSL like OpenVPN I don't see any calls to the PRNG init function to ensure it has enough entropy. I'm not sure of the security impact of this.

cyphar 10y ago
I think you mean /dev/random. On unixes, /dev/urandom produces a stream of random bytes that may not have high entropy, while /dev/random will block on reads until there's enough entropy in the pool.
- anaphor 10y ago
  nope, that's a myth http://www.2uo.de/myths-about-urandom/ http://www.2uo.de/myths-about-urandom/
  - cyphar 10y ago
    Interesting. I picked up that misconception from a Linux kernel comment a while ago. Thanks for telling me it's a myth. I knew that the two outputs came from the same source, I just assumed that the blocking had more-than-negligible effects.
  - slavik81 10y ago
    That link appears to confirm cyphar's assertion that /dev/urandom may produce a low-entropy output stream in certain circumstances. > Linux's /dev/urandom happily gives you not-so-random numbers before the kernel even had the chance to gather entropy. When is that? At system start, booting the computer.
    - geofft 10y ago
      One of the very early initscripts (on Debian, /etc/rcS.d/urandom or /lib/systemd/system/urandom.service, both of which happen well before normal initscripts) restores a random seed that was saved at last shutdown. After this script runs, the numbers are back to being cryptographically pseudorandom. Before this script runs, lots of other stuff isn't set up -- no networking, no remote filesystems, possibly not even swap -- so if you're writing code that needs to run there, you hopefully know that the system is in a weird state. And if you're writing something that runs a service that needs secure random numbers that early in the boot process, you're definitely doing something nonstandard and possibly misguided, and it's reasonable for the burden to be on you to take appropriate precautions, or switch to doing something normal. For normal application developers, who tend to wait until after the network is up to interact with the network, this special case doesn't apply.
      - slavik81 10y ago
        The usual time I've been concerned has been after creating a new virtual machine. Right after creating a new DO droplet I need to do a bunch of things to set up my application, like seed my CSRF token generator. Of course, /dev/random would block for ages at that point, so I instead generate the seed on a different machine.
- ryuuchin 10y ago
  No I definitly mean /dev/urandom[1] or the getrandom syscall which would be equal to /dev/urandom. [1] http://sockpuppet.org/blog/2014/02/25/safely-generate-random-numbers/ http://sockpuppet.org/blog/2014/02/25/safely-generate-random...
rootw0rm 10y ago
It depends upon which of the many functions you call to get your bits, iirc. I've been studying it a bit, though i've taken a little break, so i'd need to find my notes. it's certainly terrible on windows, but not completely broken...only semi-broken, lol. i think i remember there being some ancient reseeding mechanism that only works on XP in there somewhere too, but fuck it i'm drunk.
- erichurkman 10y ago
  Isn't 'semi-broken' equal to 'broken' for cryptographic purposes?
miles 10y ago
"/dev/urandom and CryptGenRandom which are known to be good" Check out "A good idea with bad usage: /dev/urandom": http://insanecoding.blogspot.com/2014/05/a-good-idea-with-bad-usage-devurandom.html http://insanecoding.blogspot.com/2014/05/a-good-idea-with-ba... Just stumbled onto it in the new submissions queue: https://news.ycombinator.com/item?id=11485876 https://news.ycombinator.com/item?id=11485876
- geofft 10y ago
  ... I'm not sure I can take an article seriously that suggests "but what if the attacker can modify files in /dev?". In any case, the meaningful concerns from that article have been addressed with the getrandom syscall on Linux, introduced a few months after this article was written: https://lwn.net/Articles/606141/ https://lwn.net/Articles/606141/ Perhaps we should start saying "getrandom" / "getentropy" instead of "/dev/urandom", but they're the same underlying CSPRNG (although getrandom has the distinct advantage of allowing you to tell if the urandom pool has been initialized, which /dev/urandom doesn't let you do), so I can understand being sloppy with usage. I would sort of assume anyone in a position to patch OpenSSL's RNG either upstream or in a distro is aware of getrandom and why it exists, but maybe that's a bad assumption.
  - ryuuchin 10y ago
    I forgot about the new getrandom syscall but yes that would be preferred if supported.
- maxerickson 10y ago
  That article says //Continue filling with other sources where it should say //exit with an error.
neerdowell 10y ago
/dev/urandom isn't reliable; it fails in a chroot, if file handles are exhausted, etc.
- jjnoakes 10y ago
  It fails in a poorly set up chroot, not any old chroot. It also fails in a poorly set up root file system in the same way. No chroot needed. I can't remember ever running out of file descriptors unless a program had a leak. But if you want to argue that position too, make sure you mention that cputime and memory could also be exhausted, leading to... well... any other method failing in a similar fashion. A system call definitely has some minor benefits over a file in /dev, bit the reverse is also true (access from shells, or any language really, with no built in support). But calling /dev/urandom unreliable is a little bit intellectually dishonest.
  - neerdowell 10y ago
    > It fails in a poorly set up chroot, not any old chroot. It fails for any program that calls chroot(2) and chroots to a location that hasn't had /dev/urandom constructed, which is... almost every program that sandboxes by calling chroot(2). > I can't remember ever running out of file descriptors unless a program had a leak. You've probably never used ulimits or login groups then. > But if you want to argue that position too, make sure you mention that cputime and memory could also be exhausted, leading to... well... any other method failing in a similar fashion. You're writing a library and in one of the functions you call arc4random(3). How would you handle memory being exhausted at the time when arc4random is called? Hint: you wouldn't. You'd let the OS handle it, probably by terminating something. Which might be the running process or another process. New situation, you're writing a library and in one of the functions you open() a file handle and read() from it. How would you handle that operation failing? Thought about it? Got your answer? Good. Now see the comments in LibreSSL for why your answer to that is wrong: https://github.com/libressl-portable/openbsd/blob/cb62fd8b9b1d3f0cdfb5445d0c53b560707a3376/src/lib/libcrypto/crypto/getentropy_linux.c#L120-L163 https://github.com/libressl-portable/openbsd/blob/cb62fd8b9b... > But calling /dev/urandom unreliable is a little bit intellectually dishonest. /dev/urandom is not a high-availability randomness source, therefore it is unreliable. It is not intellectually dishonest, it is a statement of fact.
caf 10y ago
Seeding a userspace CSPRNG from /dev/urandom or getrandom(2) is actually the right approach. The kernel pool is a resource shared among all processes, with the locking and therefore scalability constraints that implies.
- KMag 10y ago
  Also, it's a good idea to reseed your userspace CSPRNG from the kernel's entropy source periodically. This is precisely what OpenBSD did with their arc4random and arc4random_buf library calls. (Don't worry, they now use ChaCha20 instead of arcfour/RC-4, but have kept the function name unchanged, since it's a backward-compatible change... the only way a caller can tell RC-4 from ChaCha20 is by detecting small statistical biases in RC-4's outputs.)

zer01 10y ago

Reminds me of one of my favorite commit logs from the LibreSSL project: "Do not feed RSA private key information to the random subsystem as entropy. It might be fed to a pluggable random subsystem…. What were they thinking?!" http://opensslrampage.org/post/83007010531/well-even-if-time-isnt-random-your-rsa http://opensslrampage.org/post/83007010531/well-even-if-time...

plaguuuuuu 10y ago
that sounds unsafe
- Natanael_L 10y ago
  A hash of the private key isn't actually bad to use for entropy. It's what's done in deterministic EC signatures, deriving the k value from the private key + message.
  - Natanael_L 10y ago
    As long as the hash function is strong, why exactly would this be weak? Downvoting me implies you believe these people are wrong too; https://tools.ietf.org/html/rfc6979 https://tools.ietf.org/html/rfc6979 > It is possible to turn DSA and ECDSA into deterministic schemes by using a deterministic process for generating the "random" value k. That process must fulfill some cryptographic characteristics in order to maintain the properties of verifiability and unforgeability expected from signature schemes; namely, for whoever does not know the signature private key, the mapping from input messages to the corresponding k values must be computationally indistinguishable from what a randomly and uniformly chosen function (from the set of messages to the set of possible k values) would return. > d. Set: > K = HMAC_K(V || 0x00 || int2octets(x) || bits2octets(h1)) > where '||' denotes concatenation. In other words, we compute HMAC with key K, over the concatenation of the following, in order: the current value of V, a sequence of eight bits of value 0, the encoding of the (EC)DSA private key x, and the hashed message (possibly truncated and extended as specified by the bits2octets transform). The HMAC result is the new value of K. Note that the private key x is in the [1, q-1] range, hence a proper input for int2octets, yielding rlen bits of output, i.e., an integral number of octets (rlen is a multiple of 8).

rootw0rm 10y ago

I actually have several TB of OpenSSL PRNG output (256 bit len) that I've been analyzing. A fairly modest sample size, but I've come across some interesting patterns at the bit level. It's kind of a pain in the ass to write efficient analytics for a binary 256 bit pattern as a matter of fact.

dchest 10y ago
That's numerology, you just have many outputs of SHA1 with different inputs.
ICallsBS 10y ago
10^9 out of 10^25 different combinations is a significant sample size? Wouldn't the law of small numbers apply in this case?