It seeds a CSPRNG with 256 bits, then uses the CSPRNG to generate the RSA key. According to most of the estimates listed on http://www.keylength.com/ an RSA key needs to be somewhere around 15360 bits to provide a level of security equivalent to a 256 bit symmetric key.
This assumes OpenSSL's CSPRNG is solid, and that /dev/urandom is returning 32 bytes of data that can't be guessed in less than brute force time. I'd be curious to know how big the internal state of that CSPRNG is, actually.
I'm unclear on the argument that says OpenSSL's CSPRNG is inadequate for the generation of two 7680-bit numbers (there may be one, I just don't know what it is). I don't like the OpenSSL CSPRNG and think OpenSSL would be better if all the random bits just came directly from urandom, but I think OpenSSL's RAND_ functions are up to the task of 15360 bit keys.
What I'm trying to say is that by the best estimates I am aware of, the point at which it becomes less work to brute force the 256 bit seed than it would take to factor the modulus comes at around 15360 bits.
I see that several people (even in this thread, which you'd expect better of) still expressing the prevalence of incoherent and inconsistent-with-reality beliefs about /dev/random and /dev/urandom.
This quote in particular struck me as very strange.
> From: Florian Weimer <fw@deneb.enyo.de>
> To: Thorsten Glaser <tg@mirbsd.de>
> Cc: 742145@bugs.debian.org
> Subject: Re: openssl: uses only 32 bytes (256 bit) for key generation
> Date: Wed, 19 Mar 2014 21:33:10 +0100
>
> * Thorsten Glaser:
>
> >>Historically, the OpenSSL command line tools have been intended for
> >>debugging only.
> >
> > I disagree,
>
> It's what I was told by the OpenSSL developers.
>
> > Also, what do other tools (that do not invoke openssl(1)
> > unlike most of these I saw, which were shell wrappers
> > around it) do, entropy-wise?
>
> There are different choices. Some use more bits from /dev/urandom,
> some even block on /dev/random. The latter is quite problematic for
> non-interactive key generation during package isntallation.
1. I would doubt most actually block on /dev/random, but why? /dev/urandom
should be Good Enough For Everyone, except in very narrow circumstances. But why
isn't someone with a firm grasp of crypto setting a safe default? Why are
implementers and consumers of these components making these choices of entropy
size ("some use more bits") and underlying sources ("some even block..."). This
is ridiculous, I don't trust the average developer to make safe choices in this
respect. Why is it okay? This is incoherent. Either OpenSSL has safe defaults,
or it doesn't. Leaving it up to consumers to do it correctly is giving up - and
leads me to believe it's done unsafely by default.
2. The inconsistency alluded to by referring to non-interactive key generation
and "some even block on" startles me. I don't know why developers think blocking
on key generation is generally safer, but if they do, why are other (perhaps the
same?) developers sacrificing that safety when generating keys on package
installation for the sake of user experience? If /dev/random is safer, it should
be used, and if not, it shouldn't be (because of the blocking issue.) The lack
of guidance from crypto-savvy developers is deeply concerning.
Numbers can't be more or less random, either both are unsafe, or both work. Both use exactly the same algorithms (on Linux) to generate numbers, and the numbers come from the same pool.
This is probably a stupid question, as I don't know much about /dev/random and /dev/urandom (and that article doesn't seems to address it fully), but I'll ask anyway: Doesn't /dev/random block only when it estimates that the entropy pool is empty, aka when it would create unsafe numbers? The article says that the estimate is likely wrong and there is still enough entropy left, but what if it's actually empty?
If this is true, then /dev/urandom might split out unsafe bits (as unlikely it is), which to me sounds like a terrible idea when creating a key or similar very importants secrets.
> If this is true, then /dev/urandom might split out unsafe bits (as unlikely it is), which to me sounds like a terrible idea when creating a key or similar very importants secrets.
CSPRNGs such as /dev/urandom use the same cryptographic primitives that symmetric ciphers (such as AES, Twofish, Salsa20, ChaCha20, etc.) use. In the unlikely event that our CSPRNGs are broken (meaning /dev/urandom outputs "unsafe bits"), our symmetric ciphers will all be broken too. Therefore there is absolutely no point in insisting on using /dev/random to generate keys that will be used with symmetric ciphers.
(That's a little hand-wavy but I hope you get the general idea.)
You should read the article to answer your own question in depth. The short version is: on Linux, both /dev/random and /dev/urandom are fed from the same CSPRNG. A CSPRNG only needs to be seeded with a few bits of entropy to generate a whole stream of unpredictable numbers. After the CSPRNG is seeded (at system boot) it no longer matters that you run out of entropy.
I have (actually, twice. Once when it was posted sometimes ago on HN, and once now before writing the comment).
What threw me off was that part: "Still, if you insist on never handing out random numbers that are not “backed” by sufficient entropy, you might be nervous here. I'm sleeping sound because I don't care about the entropy estimate."
I was missing the fact that the CSPRNG only needs to be seeded once to be safe, and reseeding is only a "nice thing" that's not really needed. To be fair, the article cover this, I guess I just didn't understand that part really well.
I've got it now, and it actually make sense. Thanks to you, and everyone else that used some time to educate me.
No, the entropy estimator in /dev/random does not keep /dev/random from spitting out unsafe bits while allowing /dev/urandom to do that. A CSPRNG is akin to a stream cipher. The keystream of a stream cipher is as secure at it's 0th bit as it is at its 18446744073709551616th. An AES-CTR keystream doesn't "run out" of key, and /dev/urandom doesn't "run out" of entropy.
It's frustrating the the Linux random man page implies otherwise, because the idea is cryptographically nonsensical.
Randomness is not any physical entity and thus "entropy" here is just a word for data that cannot be derived from a system state. When it is not available, the attacker still has to know the seed of kernel's PRNG to be able to re-create the keys you generated in this state. To this end, she/he has to either sniff some impractically large amount of the PRNG output (and if this is possible your machine is likely already compromised), be able to set it to a given value (see above), or to know it from some prior knowledge, for instance has an image of the VM you use or knows the default value set on boot when no entropy is available whatsoever.
In other words, if the seed hasn't leaked it is easier to brute-force the key than to fit the CPRNG output that generated it.
>If you are unsure about whether you should use /dev/random or /dev/urandom, then probably you want to use the latter. As a general rule, /dev/urandom should be used for everything except long-lived GPG/SSL/SSH keys
Later:
>While some safety margin above that minimum is reasonable, as a guard against flaws in the CPRNG algorithm, no cryptographic primitive available today can hope to promise more than 256 bits of security, so if any program reads more than 256 bits (32 bytes) from the kernel random pool per invocation, or per reasonable reseed interval (not less than one minute), that should be taken as a sign that its cryptography is not skilfully implemented.
What exactly is the problem with blocking IO if you can't read faster than 32 bytes/min (or slower)?
/edit:
In your link:
>About 256 bits of entropy are enough to get computationally secure numbers for a long, long time.
I'm not a cryptology expert and therefor delegate that stuff to qualified people. But this sounds like utter bullshit. If your OpenSSL needs n bits of entropy, it does need it, and feeding it with more pseudo random numbers from that pools seems like a horrible idea. This post convinces me that /dev/random is the right thing, and not /dev/urandom, since blocking seems to be a very, very important feature. While I wouldn't trust me to get random generators right, i'd trust that blog a way less.
Once you get enough entropy into your crypto-random generator you are fine for a very, very long time. They basically use the same algorithms that are used for encryption itself (AES, etc.) and are of equal strength.
That means if you can't trust to these generators then you can't trust your encryption (i.e. you are screwed anyway).
Yes, that's why I made my reply. The lack of consistency with regards to choice of /dev/random and /dev/urandom, as well as the lack of authority and safe defaults seems like a recipe for disaster.
Why is no one authoritative on cryptography setting these defaults so that determining "what programs do with OpenSSL" is so random. Why is OpenSSL leaving these choices to programmers by default?
It seems like a terrible, terrible thing that people are micro-optimizing how big their seed is, what their source is, etc. This can not be good for security.
You don't know what you are saying. I suppose you speak about RSA-4096, which is about prime numbers. The 256 bits are just used as a seed to find large prime numbers. The 256bit entropy is more than enough to be secure, and 4096 bit prime numbers are never as secure as 256 bit entropy.
Even 64 bits would be sufficient as long as the entropy is good. It just needs to be large enough that bruteforcing 2^N isn't feasible. 256 seems like a perfectly safe amount to me.
Yeah I should have elaborated a little more. I was in a rush. I wasn't trying to endorse 64 bits, but think for a second about what it would take to attack weak entropy here. For every possible entropy state:
1. Put the random number in that state
2. Use that randomness to build a RSA key pair
3. Do an RSA decryption of the captured key exchange using this key
4. See if the symmetric key we get decrypts into sensible plaintext
The thing to note is that steps 2 and 3 are both expensive -- especially step 2. This isn't nearly as easy as scanning a 64-bit key on a symmetric cipher! So suppose for a second that you've got a huge data center full of machines at your disposal and you can do a billion tests per second -- a full sweep of the 64-bit space would still take 584 years. So you better hope you'd get lucky.
Now would that be enough protection? Of course not -- computers get faster, and a determined enough adversary could build special hardware. (Although, again, it would be orders of magnitude more complicated than just SHA-512 bruteforcing)
The point I was trying to make is that even if they were somehow only using 64 bits of entropy, a practical attack would still be difficult to mount. I'd say that each test would be at least 2^16 times more computation than a typical symmetric cipher check. Therefore I think it would be about as hard as bruteforcing a 80-bit symmetric key.
In general, discussion about encryption is usually bad because most people don't understand all the underlying principles of encryption. Encryption is something everyone uses so everyone has an opinion on it, but very very few people understand its implementation. When you have a blog post about encryption, 99% of the people commenting on it probably won't be making the right kind of comment.
The "256 bits" (in this case) are used as a seed for the OpenSSL CSPRNG.
OpenSSL's RSA generation asks for two prime numbers each (bitlen/2) long. OpenSSL's primegen works by iterating over random numbers, here each (bitlen/2) long (of which (bitlen/2-2) are random), looking for primes.
What is really troubling is not the amount of entropy, 256 is fine for everything up to paranoia. What is troubling and reflects the sad status and detachment from reality of the project is this:
>Historically, the OpenSSL command line tools have been intended for debugging only.
Apart from genrsa, what exactly have you used the openssl cli for in the past?
My answer would be the exact same as you quoted, the openssl cli tools are quite horrendous to use and you certainly wouldn't use them if you were a CA. If you are a CA or deal with certificates, openssl does provide sweet inspection dumping tools for asn1 and certs.
If you have an application which generates keys or certificates, why would you system exec openssl cli when your language of choice has a Crypto implementation, or glue to OpenSSL.
So I ask openly, run `history | grep openssl` and see. Even running `openssl help` is daunting unless you're familiar with most symmetric block modes.
I use the openssl cli every time I generate a CSR or a self-signed certificate. If you Google "generate csr" you'll find lots of sites, including companies that issue SSL certificates, instructing you to use the openssl cli.
I've used them a ton for ASN.1 parsing, base64 encoding/decoding, hashing, certificate dumping and the occasional RSA decryption or signature check. The command-line interface is horrendous, but man is that a useful crypto toolbox.
> What is troubling and reflects the sad status and detachment from reality of the project
A random comment by one Debian developer do not constitute the position of the Debian project. On top of that, consider the subsequent comment that the information in question came from an OpenSSL developer.
The 32 bytes it gets goes back into a similar CSPRNG as the CSPRNG it came out of.
So instead of requesting 4096 bits from a CSPRNG, it requests 256 bits from a CSPRNG and uses that to initialize another CSPRNG which it reads 4096 bits from. Cryptographically speaking it's the exact same thing.
The question to be asking is whether the output from either CSPRNG is predictable.
Cryptographically speaking you are completely wrong :) You need both: good algorithm and enough entropy. Ad absurdum if you read 1 one byte and feed it into your CSPRNG, you may get up to 256 random streams of 4096 bits, which is easily enumerable and hardly secure.
I don't know what you're trying to say here, but feeding 256 bits to a CSPRNG and then pulling 4096 bits of output from that CSPRNG is not "cryptographically completely wrong".
This thread seems to be generating a lot of fuss, so let me weigh in quickly.
This seems to be expected behaviour for generating RSA keys. An RSA key of length 4096b does not provide you with a security level of 4096b. That is, you don't have to straight-up guess the keys, you work at it via factorisation.
The issue is arising from the fact that entopy and key length are both commonly measured in bits. The entropy of an RSA key is much lower than the key length. 256b of entropy seems to be more than reasonable at first glance.
Normally, I would not defend openSSL, but I will do so here, having not even looked at the responsible code (nor has the submitter of this bug), and not even looked at the mailing list link.
Seriously, do not panic, let the cryptographers look at this and decide if it's really an issue. It's probably good that they're getting 256b of entropy from urandom, it's likely that they're seeding a CSPRNG for prime generation & testing.
I would wager some small sum on this being closed by the end of the week, and us looking back on this and shaking our heads at the uninformed knee-jerk reaction of people in here:
"If I ask for a 4096-bit key, I should get one, or an error message. I shouldn't get a 256-bit key that looks like a 4096-bit key." -- taejo, 15 minutes ago
RSA keys aren't just random strings (unlike symmetric keys, which are short random strings, generally 128 or 256 bits now).
You start with two random primes. Generally to generate these what you do is pick a range of numbers in the right size, then test the odd ones with a prime sieve (vs small primes), then do probabilistic primality test on the winners. This doesn't need 4096 bits of randomness.
Once you have the primes, you don't need any more random numbers to generate the key; it's purely deterministic calculation at that point.
For primes of current acceptable size (>= 1024 bits), you might as well drop those extra checks. The elliptic curve method gives you around 2^512 attempts at doing the exact same thing, each one with the same probability of having a smooth p-1 or p+1. The paper you link to reaches essentially the same conclusion.
OpenSSL doesn't always retrieve all its random bytes from urandom; it seeds its own local PRNG with urandom, and feeds raw random bytes from its own state.
There are no simple answers in public key crypto: the idea that you only need 256 bits of random data can blow your head off if you use something other than RSA. For instance, if you fill only some of the bits of a DSA k value, attackers can extract your private key from a series of public signatures.
Some of the comments on that bug thread are batty, though. The OpenSSL CLI tool doesn't implement its own randomness or key generation; it's a CLI wrapper around the core OpenSSL functions. The CLI might be for "debugging purposes" (but obviously not really, since most instructions for generating SSL certificates involve using that CLI), but the core routines surely aren't.
There's also a possibly-not-completly-wrong table on that other TLS library's website (http://www.gnutls.org/manual/gnutls.html#Selecting-cryptogra...) that takes a stab at estimating the relative security levels of (correctly-used) public key algorithms.
68 comments
[ 2.6 ms ] story [ 450 ms ] threadhttps://www.schneier.com/blog/archives/2008/05/random_number...
Edit: oh right, it led to the SSH blacklist. Sorry.
This assumes OpenSSL's CSPRNG is solid, and that /dev/urandom is returning 32 bytes of data that can't be guessed in less than brute force time. I'd be curious to know how big the internal state of that CSPRNG is, actually.
>Historically, the OpenSSL command line tools have been intended for debugging only.
This seems rather out-of-touch with reality.
This quote in particular struck me as very strange.
> From: Florian Weimer <fw@deneb.enyo.de>
> To: Thorsten Glaser <tg@mirbsd.de>
> Cc: 742145@bugs.debian.org
> Subject: Re: openssl: uses only 32 bytes (256 bit) for key generation
> Date: Wed, 19 Mar 2014 21:33:10 +0100
>
> * Thorsten Glaser:
>
> >>Historically, the OpenSSL command line tools have been intended for
> >>debugging only.
> >
> > I disagree,
>
> It's what I was told by the OpenSSL developers.
>
> > Also, what do other tools (that do not invoke openssl(1)
> > unlike most of these I saw, which were shell wrappers
> > around it) do, entropy-wise?
>
> There are different choices. Some use more bits from /dev/urandom,
> some even block on /dev/random. The latter is quite problematic for
> non-interactive key generation during package isntallation.
1. I would doubt most actually block on /dev/random, but why? /dev/urandom should be Good Enough For Everyone, except in very narrow circumstances. But why isn't someone with a firm grasp of crypto setting a safe default? Why are implementers and consumers of these components making these choices of entropy size ("some use more bits") and underlying sources ("some even block..."). This is ridiculous, I don't trust the average developer to make safe choices in this respect. Why is it okay? This is incoherent. Either OpenSSL has safe defaults, or it doesn't. Leaving it up to consumers to do it correctly is giving up - and leads me to believe it's done unsafely by default.
2. The inconsistency alluded to by referring to non-interactive key generation and "some even block on" startles me. I don't know why developers think blocking on key generation is generally safer, but if they do, why are other (perhaps the same?) developers sacrificing that safety when generating keys on package installation for the sake of user experience? If /dev/random is safer, it should be used, and if not, it shouldn't be (because of the blocking issue.) The lack of guidance from crypto-savvy developers is deeply concerning.
Numbers can't be more or less random, either both are unsafe, or both work. Both use exactly the same algorithms (on Linux) to generate numbers, and the numbers come from the same pool.
More in depth analysis: http://www.2uo.de/myths-about-urandom/
If this is true, then /dev/urandom might split out unsafe bits (as unlikely it is), which to me sounds like a terrible idea when creating a key or similar very importants secrets.
CSPRNGs such as /dev/urandom use the same cryptographic primitives that symmetric ciphers (such as AES, Twofish, Salsa20, ChaCha20, etc.) use. In the unlikely event that our CSPRNGs are broken (meaning /dev/urandom outputs "unsafe bits"), our symmetric ciphers will all be broken too. Therefore there is absolutely no point in insisting on using /dev/random to generate keys that will be used with symmetric ciphers.
(That's a little hand-wavy but I hope you get the general idea.)
Disclaimer: I am not a cryptographer.
What threw me off was that part: "Still, if you insist on never handing out random numbers that are not “backed” by sufficient entropy, you might be nervous here. I'm sleeping sound because I don't care about the entropy estimate."
I was missing the fact that the CSPRNG only needs to be seeded once to be safe, and reseeding is only a "nice thing" that's not really needed. To be fair, the article cover this, I guess I just didn't understand that part really well.
I've got it now, and it actually make sense. Thanks to you, and everyone else that used some time to educate me.
It's frustrating the the Linux random man page implies otherwise, because the idea is cryptographically nonsensical.
In other words, if the seed hasn't leaked it is easier to brute-force the key than to fit the CPRNG output that generated it.
>If you are unsure about whether you should use /dev/random or /dev/urandom, then probably you want to use the latter. As a general rule, /dev/urandom should be used for everything except long-lived GPG/SSL/SSH keys
Later:
>While some safety margin above that minimum is reasonable, as a guard against flaws in the CPRNG algorithm, no cryptographic primitive available today can hope to promise more than 256 bits of security, so if any program reads more than 256 bits (32 bytes) from the kernel random pool per invocation, or per reasonable reseed interval (not less than one minute), that should be taken as a sign that its cryptography is not skilfully implemented.
What exactly is the problem with blocking IO if you can't read faster than 32 bytes/min (or slower)?
/edit:
In your link:
>About 256 bits of entropy are enough to get computationally secure numbers for a long, long time.
I'm not a cryptology expert and therefor delegate that stuff to qualified people. But this sounds like utter bullshit. If your OpenSSL needs n bits of entropy, it does need it, and feeding it with more pseudo random numbers from that pools seems like a horrible idea. This post convinces me that /dev/random is the right thing, and not /dev/urandom, since blocking seems to be a very, very important feature. While I wouldn't trust me to get random generators right, i'd trust that blog a way less.
http://sockpuppet.org/blog/2014/02/25/safely-generate-random...
That means if you can't trust to these generators then you can't trust your encryption (i.e. you are screwed anyway).
Why is no one authoritative on cryptography setting these defaults so that determining "what programs do with OpenSSL" is so random. Why is OpenSSL leaving these choices to programmers by default?
It seems like a terrible, terrible thing that people are micro-optimizing how big their seed is, what their source is, etc. This can not be good for security.
Now would that be enough protection? Of course not -- computers get faster, and a determined enough adversary could build special hardware. (Although, again, it would be orders of magnitude more complicated than just SHA-512 bruteforcing)
The point I was trying to make is that even if they were somehow only using 64 bits of entropy, a practical attack would still be difficult to mount. I'd say that each test would be at least 2^16 times more computation than a typical symmetric cipher check. Therefore I think it would be about as hard as bruteforcing a 80-bit symmetric key.
In other words, 256 is way more than plenty.
The "256 bits" (in this case) are used as a seed for the OpenSSL CSPRNG.
OpenSSL's RSA generation asks for two prime numbers each (bitlen/2) long. OpenSSL's primegen works by iterating over random numbers, here each (bitlen/2) long (of which (bitlen/2-2) are random), looking for primes.
As for the strength of 256 bits, the Wikipedia page on brute force attacks should tell you how infeasible attacking even a 128 bit key is: http://en.wikipedia.org/wiki/Brute-force_attack
>Historically, the OpenSSL command line tools have been intended for debugging only.
My answer would be the exact same as you quoted, the openssl cli tools are quite horrendous to use and you certainly wouldn't use them if you were a CA. If you are a CA or deal with certificates, openssl does provide sweet inspection dumping tools for asn1 and certs.
If you have an application which generates keys or certificates, why would you system exec openssl cli when your language of choice has a Crypto implementation, or glue to OpenSSL.
So I ask openly, run `history | grep openssl` and see. Even running `openssl help` is daunting unless you're familiar with most symmetric block modes.
A random comment by one Debian developer do not constitute the position of the Debian project. On top of that, consider the subsequent comment that the information in question came from an OpenSSL developer.
> debugging only.
That very much surprises me. Can someone explain, elaborate, or source this idea?
Obviously the tools are useful for debugging purposes, testing tls connections, dumping cert information and asn1.
I've now been made aware that tools wrap the openssl cli instead of using it's programmatic API.
Once I tried to use the ca functions of the tool, found the whole tool entirely too cumbersome and wrote my own using libopenssl.
What do you use it for extensively if I might ask?
http://blog.gosquadron.com/use-tls
The 32 bytes it gets goes back into a similar CSPRNG as the CSPRNG it came out of.
So instead of requesting 4096 bits from a CSPRNG, it requests 256 bits from a CSPRNG and uses that to initialize another CSPRNG which it reads 4096 bits from. Cryptographically speaking it's the exact same thing.
The question to be asking is whether the output from either CSPRNG is predictable.
This seems to be expected behaviour for generating RSA keys. An RSA key of length 4096b does not provide you with a security level of 4096b. That is, you don't have to straight-up guess the keys, you work at it via factorisation.
The issue is arising from the fact that entopy and key length are both commonly measured in bits. The entropy of an RSA key is much lower than the key length. 256b of entropy seems to be more than reasonable at first glance.
Normally, I would not defend openSSL, but I will do so here, having not even looked at the responsible code (nor has the submitter of this bug), and not even looked at the mailing list link.
Seriously, do not panic, let the cryptographers look at this and decide if it's really an issue. It's probably good that they're getting 256b of entropy from urandom, it's likely that they're seeding a CSPRNG for prime generation & testing.
I would wager some small sum on this being closed by the end of the week, and us looking back on this and shaking our heads at the uninformed knee-jerk reaction of people in here:
"If I ask for a 4096-bit key, I should get one, or an error message. I shouldn't get a 256-bit key that looks like a 4096-bit key." -- taejo, 15 minutes ago
You start with two random primes. Generally to generate these what you do is pick a range of numbers in the right size, then test the odd ones with a prime sieve (vs small primes), then do probabilistic primality test on the winners. This doesn't need 4096 bits of randomness.
Once you have the primes, you don't need any more random numbers to generate the key; it's purely deterministic calculation at that point.
OpenSSL doesn't always retrieve all its random bytes from urandom; it seeds its own local PRNG with urandom, and feeds raw random bytes from its own state.
There are no simple answers in public key crypto: the idea that you only need 256 bits of random data can blow your head off if you use something other than RSA. For instance, if you fill only some of the bits of a DSA k value, attackers can extract your private key from a series of public signatures.
Some of the comments on that bug thread are batty, though. The OpenSSL CLI tool doesn't implement its own randomness or key generation; it's a CLI wrapper around the core OpenSSL functions. The CLI might be for "debugging purposes" (but obviously not really, since most instructions for generating SSL certificates involve using that CLI), but the core routines surely aren't.
The remaining questions are
1. Is openssl(1) really only intended for "debugging purposes"?
2. http://www.philandstuff.com/2013/03/14/why-does-gpg-need-so-...