How to safely generate a random number(sockpuppet.org)
sockpuppet.org
How to safely generate a random number
http://sockpuppet.org/blog/2014/02/25/safely-generate-random-numbers/
11 comments
So, what specifically did Matt Green disagree with?
Anyone want to give a total count of wrong assertions in this article?
I prefer the Munroe-Hatguy entropy collection method for pseudorandom number generation [1].
[1] http://xkcd.com/221/
[1] http://xkcd.com/221/
I knew that link was going to show up. It's predictable that way.
I liked the part that said "urandom".
So rather than using a function in the core library of the language that calls /dev/urandom, we should instead write our own wrapper around /dev/urandom? And this is supposed to be less prone to error?
If you know that's all your library does, as in the case of Golang crypto/rand, then use the library. But don't just assume that's all your library is doing.
Where does this article say that?
The article lists several userspace libraries (OpenSSL, SecureRandom) and then says not to use them. I had the same question as weavejester.
No. OpenSSL RAND_bytes and Java SecureRandom aren't simply libraries that "call /dev/urandom"; they are full-fledged CSPRNG designs, and must themselves avoid all the possible bugs a CSPRNG can have, in addition to their usual reliance on urandom not itself being vulnerable.
The NativePRNG algorithm for SecureRandom XORs /dev/urandom with a SHA1PRNG seeded from /dev/urandom, so as long as the XOR is correct, it should be no less secure than reading from /dev/urandom directly.
I would definitely avoid Java's SecureRandom. It means too many different things depending on what platform you're on. Meanwhile, XORing SHA1PRNG against /dev/urandom seems cryptographically nonsensical.
> XORing SHA1PRNG against /dev/urandom seems cryptographically nonsensical.
Untrue! Assuming that the two (/dev/urandom and SHA1PRNG) are not correlated, the resulting output will be at least as secure as the most secure of the two. This means that (for example) if SHA1PRNG is found to be breakable, SecureRandom will still be at least as secure as /dev/urandom, and vice versa.
Untrue! Assuming that the two (/dev/urandom and SHA1PRNG) are not correlated, the resulting output will be at least as secure as the most secure of the two. This means that (for example) if SHA1PRNG is found to be breakable, SecureRandom will still be at least as secure as /dev/urandom, and vice versa.
This is a rabbit hole I don't want to go down and so I will concede the point about NativePRNG, while sticking to my guns on "avoid the Java SecureRandom interface".
If you want a cross-platform secure random source, you can't rely on /dev/urandom existing, so I'm not sure what alternative you're suggesting here.
You can't on the one hand say that OpenJDK Unix SecureRandom uses urandom so it's OK while on the other hand saying that SecureRandom is preferable because it works on platforms without urandom. That's the problem with SecureRandom: it's hard to know exactly what it's doing, as the Android team discovered last year.
(On Windows, I'd use CryptGenRandom, although it inspires even less confidence than Linux /dev/random).
(On Windows, I'd use CryptGenRandom, although it inspires even less confidence than Linux /dev/random).
I don't see any contradiction. SecureRandom uses urandom where it's available, and the next best alternative where it's not. Again, I'd like to know what your suggested solution is. The way I see it, you can either:
1) Don't write cross-platform code
2) Use the language implementation
3) Write your own cross-platform code
Assuming (1) isn't an option, it comes down to using SecureRandom or writing your own version of SecureRandom, which strikes me as plain crazy.
1) Don't write cross-platform code
2) Use the language implementation
3) Write your own cross-platform code
Assuming (1) isn't an option, it comes down to using SecureRandom or writing your own version of SecureRandom, which strikes me as plain crazy.
If SecureRandom was simply "pull bytes from urandom" on Linux and "pull bytes from CryptGenRandom" on Windows, I wouldn't care enough to argue. But it's not. It's not even "pull bytes from urandom" on Linux; depending on the specific details of your platform, it can be dramatically different than that.
I'm absolutely not recommending that people write their own version of SecureRandom; I'm advising the opposite. Avoid userspace CSPRNGs. Use the system CSPRNG.
I'm absolutely not recommending that people write their own version of SecureRandom; I'm advising the opposite. Avoid userspace CSPRNGs. Use the system CSPRNG.
So I should write my own cross-platform interface to the system PRNG? Doesn't that strike you as more prone to error than relying on SecureRandom, which at least has the advantage of having many eyes on it.
NO. Relying on SecureRandom is riskier than writing the 5-10 lines of code it takes to read from urandom. Prefer urandom to SecureRandom.
Look what "many eyes" did for the Harmony PRNG.
Look what "many eyes" did for the Harmony PRNG.
If you're ever in Redmond, stop by and we'll go inspire some confidence with the folks maintaining it.
Two immediate questions: forward secrecy and CryptGenRandom's state relative to other WinAPI processes. As in, I'm very clear how the Unix security model protects /dev/random, and less clear about Windows. Some of my C.G.R. thoughts are probably dated. But it's the system CSPRNG, and I think, just use the system CSPRNG.
You have my email right? If you'd like to send me some specific questions and concerns I can try to put them to people who know.
The forward security issues have been fixed for a long time (since Vista I believe): they now use SP800-90A's CTR_DRBG. But the generator continues to be unprotected in user mode, seeded from kernel.
That makes more sense. So which of the following is true:
1) I shouldn't be using OpenSSL to generate keys without somehow injecting bytes directly /dev/urandom
2) The article is wrong, using OpenSSL's CSPRNG is fine.
3) I still don't get it.
The article doesn't care how you use the OpenSSL commands; it's concerned with code you write that might need a CSPRNG. If you're writing code, don't use OpenSSL's CSPRNG.
So code that I write that generates keys using OpenSSL isn't indirectly depending on OpenSSL's CSPRNG?
Sorry for all the questions. I just want to make sure I'm doing it right and I suspect I'm not the only one that is confused by the article's assertions.
Sorry for all the questions. I just want to make sure I'm doing it right and I suspect I'm not the only one that is confused by the article's assertions.
The article (I'm its author) is about programming; it doesn't have strong opinions about how you e.g. configure nginx.
As for keys: it depends on the kinds of keys you're generating. If you're building on OpenSSL's primitives --- which, don't --- it'll be hard to get an RSA key without invoking the OpenSSL CSPRNG. But it's not at all hard to avoid OpenSSL's CSPRNG for AES.
As for keys: it depends on the kinds of keys you're generating. If you're building on OpenSSL's primitives --- which, don't --- it'll be hard to get an RSA key without invoking the OpenSSL CSPRNG. But it's not at all hard to avoid OpenSSL's CSPRNG for AES.
Thanks for clarifying.
My project depends on bitcoin-ruby, which uses OpenSSL's EC_KEY_generate_key to generate keys. EC_KEY_generate_key, as far as I can tell, uses OpenSSLs internal PRNG. If I understand you correctly, this is unsafe and it would be better to derive a key from urandom.
My project depends on bitcoin-ruby, which uses OpenSSL's EC_KEY_generate_key to generate keys. EC_KEY_generate_key, as far as I can tell, uses OpenSSLs internal PRNG. If I understand you correctly, this is unsafe and it would be better to derive a key from urandom.
Reliance on OpenSSL's CSPRNG isn't a hair-on-fire problem; if it was, your hair would literally be on fire right now, because lots of things do. I just don't think it's a great idea for new code to perpetuate the habit.
Use urandom, but that's not the end of it. It may be that urandom supports non-blocking reads. Most implementations only check if read() returns -1 then abort, without checking for EAGAIN, not to mention EINTR, or some other subtleties like making sure not to request more than SSIZE_MAX bytes. The randombytes function in NaCl does it right, unfortunately libsodium did their own thing.
If you use Python, read from os.urandom, which is a wrapper to the system's CSPRNG. Don't use random.randint or random.getrandbits...
If you use Python, read from os.urandom, which is a wrapper to the system's CSPRNG. Don't use random.randint or random.getrandbits...
> The randombytes function in NaCl does it right, unfortunately libsodium did their own thing.
I don't know what you're talking about. Sodium does the same thing as NaCl, while also being more portable.
I don't know what you're talking about. Sodium does the same thing as NaCl, while also being more portable.
No, libsodium does not do the same thing as NaCl.
NaCl:
https://gist.github.com/anonymous/9234738
libsodium:
https://github.com/jedisct1/libsodium/blob/master/src/libsod...
NaCl:
https://gist.github.com/anonymous/9234738
libsodium:
https://github.com/jedisct1/libsodium/blob/master/src/libsod...
I'm aware that the implementations are not strictly equal, but how is libsodium doing it 'wrong'? Is it because it does not partition reads into smaller chunks (avoiding the unspecified >= SSIZE_MAX read)? I consider any reasonable answer a valid bug report.
I should also point out that randombytes is technically not part of NaCl. The authors maintain that random byte generation is out of scope for NaCl, and what actually happens is that randombytes.o is bundled separately from libnacl.a [1]. In TweetNacl the randombytes implementation is completely omitted.
[1] https://bugs.debian.org/cgi-bin/bugreport.cgi?msg=20;bug=694...
I should also point out that randombytes is technically not part of NaCl. The authors maintain that random byte generation is out of scope for NaCl, and what actually happens is that randombytes.o is bundled separately from libnacl.a [1]. In TweetNacl the randombytes implementation is completely omitted.
[1] https://bugs.debian.org/cgi-bin/bugreport.cgi?msg=20;bug=694...
Don't take my word for it, check libsodium with Frama-C (as NaCl was) and file the bug report yourself.
You can also use random.SystemRandom, which gives you the same interface as random.Random (and the random module) but as a wrapper around os.urandom.
/dev/urandom is slow. So don't use it if you need lots of non secure random numbers. For example for game, or for a screensaver, etc.
If you want fast non-secure random numbers use Mersenne Twister: http://en.wikipedia.org/wiki/Mersenne_twister
You can also get much faster secure random numbers.
> For cryptography, you don’t usually want “true random”.
Wait what? I thought I wanted actually random numbers.
Wait what? I thought I wanted actually random numbers.
I thought the same thing. This comment on crypto.stackexchange.com[1] shed a bit of light for me:
Yup, entropy sources may even have a particular bias to bits valued 0 or 1.
Normally you need at least a whitening technique to get something looking
like a random number. Feeding that as a seed into a PRNG is certainly
helping to get the right quality. Be careful not to confuse a source of
entropy with a secure random number generator.
What about haveged? Is that good enough for crypto? http://www.issihosts.com/haveged/
Why is urandom meant to be more secure?
I read this: "So I'm the maintainer for Linux's /dev/random driver. "... "The main thing which I am much more worried about is that on various embedded systems, which do not have a fine-grained clock, and which is reading from flash which has a much more deterministic timing for their operations, is that when userspace tries to generate long-term public keys immediately after the machine is taken out of the box and plugged in, that there isn't a sufficient amount of entropy, and since most userspace applications use /dev/urandom since they don't want to block, that they end up with keys that aren't very random." - https://www.schneier.com/blog/archives/2013/10/insecurities_...
Is that out of date?
Why so insistent? Why not provide reasons that people can openly verify?
I read this: "So I'm the maintainer for Linux's /dev/random driver. "... "The main thing which I am much more worried about is that on various embedded systems, which do not have a fine-grained clock, and which is reading from flash which has a much more deterministic timing for their operations, is that when userspace tries to generate long-term public keys immediately after the machine is taken out of the box and plugged in, that there isn't a sufficient amount of entropy, and since most userspace applications use /dev/urandom since they don't want to block, that they end up with keys that aren't very random." - https://www.schneier.com/blog/archives/2013/10/insecurities_...
Is that out of date?
Why so insistent? Why not provide reasons that people can openly verify?
urandom and /dev/random aren't two different CSPRNGs. They aren't really even two different designs. They are two different pools into which the same kinds of raw entropy are mixed; the interface to /dev/random's pool happens to have a weird gate on it that tries to determine how much "entropy" is "left" in the pool. I'm oversimplifying a little, but that's the gist of it.
So the problem here is, if you're on a solid state embedded system that doesn't generate enough entropy to drive urandom, you're not doing enough to drive /dev/random either --- except, owing to a design flaw in Linux, on first-boot-ever, where /dev/random's entropy estimator gate saves from you from the bug that is Linux's willingness to give you output from an unseeded RNG. It shouldn't do that. FreeBSD doesn't. But if you're worried about that problem, the correct fix is to explicitly seed urandom from /dev/random on boot, not to use /dev/random in your code!
Once the CSPRNG is seeded, the idea of a "sufficient amount of entropy" is silly. Think of a CSPRNG as a stream cipher. Think of its output as you would the keystream of that cipher. What does it mean, within reason (ie, not hundreds of terabytes) for a keystream to have "sufficient" key in it? Because that's essentially the same question the maintainer for /dev/random is asking.
So the problem here is, if you're on a solid state embedded system that doesn't generate enough entropy to drive urandom, you're not doing enough to drive /dev/random either --- except, owing to a design flaw in Linux, on first-boot-ever, where /dev/random's entropy estimator gate saves from you from the bug that is Linux's willingness to give you output from an unseeded RNG. It shouldn't do that. FreeBSD doesn't. But if you're worried about that problem, the correct fix is to explicitly seed urandom from /dev/random on boot, not to use /dev/random in your code!
Once the CSPRNG is seeded, the idea of a "sufficient amount of entropy" is silly. Think of a CSPRNG as a stream cipher. Think of its output as you would the keystream of that cipher. What does it mean, within reason (ie, not hundreds of terabytes) for a keystream to have "sufficient" key in it? Because that's essentially the same question the maintainer for /dev/random is asking.
How do we know there isn't some predictable pattern from common urandom sources?
What is meant to make the state non-predictable anyway?
If I cared about it, someone could just add a library on top of it that combines them with more entropy sources. Like camera noise, temperature changes, audio static etc.
For some reason the author says not to build libraries on top of urandom because they might be hacked.
Well if something has compromised your system anyway, why does that matter?
"The urandom sources"? What do you think that means? The code is right there.
I'm talking about the sources of it's random input, not it's source code.
You can call it a bug or design flaw if you'd like, but this behaviour is documented, well known, and it's how every single Linux system operates.
urandom simply isn't guaranteed to be random enough for cryptographic keys. Misusing it for this causes real-world problems.
You are telling people to write insecure software. That it could be secure if Linux worked differently from how it actually works is completely irrelevant and bordering on denialism.
If you want to fix Linux to be more like the other systems, great! Then /dev/random will be non-blocking and everyone can use that. Meanwhile, I'd much rather block than find myself sharing prime factors with random strangers.
urandom simply isn't guaranteed to be random enough for cryptographic keys. Misusing it for this causes real-world problems.
You are telling people to write insecure software. That it could be secure if Linux worked differently from how it actually works is completely irrelevant and bordering on denialism.
If you want to fix Linux to be more like the other systems, great! Then /dev/random will be non-blocking and everyone can use that. Meanwhile, I'd much rather block than find myself sharing prime factors with random strangers.
On the one hand you have Nacl, from Daniel J. Bernstein, Tanja Lange, and Peter Schwabe, the gold standard of misuse-resistant crypto libraries, relying entirely on urandom and documenting why.
On the other, you have HN's 'tveita, saying that urandom "isn't guaranteed to be random enough for cryptographic keys".
I could continue the argument, but since the whole post you're commenting on is that argument, I'd be repeating myself. So instead, I'll just ask: what specific assertion in that post do you disagree with?
On the other, you have HN's 'tveita, saying that urandom "isn't guaranteed to be random enough for cryptographic keys".
I could continue the argument, but since the whole post you're commenting on is that argument, I'd be repeating myself. So instead, I'll just ask: what specific assertion in that post do you disagree with?
How about the very post I replied to?
> the bug that is Linux's willingness to give you output from an unseeded RNG
So there you have it. But don't worry, no one uses this "Linux" thing, certainly not in embedded systems.
https://factorable.net/
> the bug that is Linux's willingness to give you output from an unseeded RNG
So there you have it. But don't worry, no one uses this "Linux" thing, certainly not in embedded systems.
https://factorable.net/
Keep reading. I think you stopped too early.
I read it all, don't be a jerk.
When you're writing a program for generic use, you can't trust the underlying system to be set up above and beyond a stock install. If you want to use seeding as a workaround, it should be done from every program that requires secure randomness. That doesn't seem to be what you're advocating. And if you're just generating a key, why not read it directly from random instead?
You can pretend that urandom gives good randomness and be surprised when you get key collisions. Just like you can pretend that strncpy null-terminates strings and be surprised when you get a buffer overflow vulnerability. That makes you a menace.
For what's it's worth, I agree that an adequately seeded CSPRNG should never 'run out' of entropy, and I wouldn't mind if Linux got a BSD-style shared random/urandom. But as it stands, urandom is not guaranteed to be adequately seeded, and I have no idea why you would advocate taking that risk.
When you're writing a program for generic use, you can't trust the underlying system to be set up above and beyond a stock install. If you want to use seeding as a workaround, it should be done from every program that requires secure randomness. That doesn't seem to be what you're advocating. And if you're just generating a key, why not read it directly from random instead?
You can pretend that urandom gives good randomness and be surprised when you get key collisions. Just like you can pretend that strncpy null-terminates strings and be surprised when you get a buffer overflow vulnerability. That makes you a menace.
For what's it's worth, I agree that an adequately seeded CSPRNG should never 'run out' of entropy, and I wouldn't mind if Linux got a BSD-style shared random/urandom. But as it stands, urandom is not guaranteed to be adequately seeded, and I have no idea why you would advocate taking that risk.
Oh, we're talking past each other. Sorry. When I said "post", I meant the story this thread links to, not the comment thread. I believe you read the comments in their entirety. I think if you reread the post, you'd see that it rebuts your argument.
For encryption, the only way to be really secure is to have the same amount of randomness as there is data to encrypt, as a shared key. (A one time pad.)
This isn't that hard to do so long as you can give it to the people that need it ahead of time, and should solve all kinds of theoretical problems.
Mailing memory cards sealed in photoed glitter paint could work well too. It would be fun to 3D print a replica though.
This rant does more harm than good. Telling people not to use a library csprng is quite silly. Everything uses these and it's fine.
Yeah I mean, there's probably never been a urandom-based vulnerability in ordinary software, and "library csprngs" are the reason every Debian SSH was compromised and the reason Android Bitcoin wallets were generating colliding keys, but sure. Everything's fine.