209

Lets say I want to create a cookie for a user. Would simply generating a 1024 bit string by using /dev/urandom, and checking if it already exists (looping until I get a unique one) suffice?

Should I be generating the key based on something else? Is this prone to an exploit somehow?

Community
  • 1
Incognito
  • 5,204
  • 5
  • 27
  • 31
  • 4
    Checking for uniqueness is slow. A better choice is to ensure uniqueness. Append the time stamp to the string, down as far as you can. This will ensure that no two strings are ever the same, even if somehow the randomness is the same. – DampeS8N Sep 16 '11 at 20:40
  • 30
    @DampeS8N You're assuming that repeatedly retrieving a timestamp yields a monotonically increasing value. This is far from true: the timestamp can remain constant during a fast sequence of operations, and can go backwards because the clock is reset for some reason. (Recommended reading: [Cryptography Engineering](http://www.schneier.com/book-ce.html) ch. 16.) A counter is a reliable (and fast) way of ensuring uniqueness, if you can store it in non-volatile memory. A crypto-quality (P)RNG does ensure (crypto-quality) uniqueness, no additional technique is needed. – Gilles 'SO- stop being evil' Oct 04 '11 at 20:40
  • 3
    @Gilles: Agreed. A counter is always a better choice. But it should be known that we are talking about the VERY rare time when both the randomness and the timestamp are the same. And with dev/urandom/ we are talking a once in a universe event. – DampeS8N Oct 04 '11 at 20:45
  • 9
    @DampeS8N If `/dev/urandom` gives you repeats, you have a security problem that merely appending a counter won't fix. As our conversation is wandering away from the question, I suggest that we take any continuation to [chat](chat.stackexchange.com/rooms/info/151). – Gilles 'SO- stop being evil' Oct 04 '11 at 21:34
  • 42
    All this seems academic. The probability of randomly generating two identical 1024 bit messages is so absurdly low that it doesn't even bear consideration. – Nick Johnson Oct 25 '11 at 03:04
  • 3
    @NickJohnson run the following command on any linux machine: `cat /dev/urandom | rngtest -c 1000` several times. IF its a vm (as many server environments are now) you'll fail FIPS compliance about every other run. – avgvstvs Oct 17 '14 at 18:29
  • 3
    @NickJohnson, That depends on the **consequence** of a non-unique clash. If the consequence is End-Of-Universe, then yes it makes sense to check for uniqueness. – Pacerier Dec 12 '14 at 10:18
  • 9
    @Pacerier If we're the only intelligent beings in the universe, then each failure to check incurs an average of 6e9 / 2^512 = 4.5e-145 deaths. There's not even an SI suffix for a number that small. We should focus on higher risk activities, like being struck by lightning from a clear sky while skydiving on the day you win the lottery. – Nick Johnson Dec 12 '14 at 13:01
  • 3
    @NickJohnson, You are confusing the probability to win with the expected value. The expectation will be 4.5e-145, which is the average over many runs. But each run could well end up somewhere else, in this case: 0 * consequence or 1 * consequence. Some random people getting struck by lightning from a clear sky is less than insignificant compared to End-Of-Universe. – Pacerier Dec 12 '14 at 14:11
  • 4
    @Pacerier It's statistically valid to extrapolate the probability to an expected value, particularly for statistical purposes like this. If you were to hand me a revolver with 4.5e145 chambers and one bullet and offer me $1 per pull, I'd take you up on it any day. – Nick Johnson Dec 17 '14 at 09:39
  • 1
    @NickJohnson, Not if you would live forever. You would take up the offer only and only because there's a fixed amount of time that you could live anyway and thus that life has a **limited** value. End-Of-Universe here is however assumed equal to an **unlimited** / infinite value. – Pacerier Feb 17 '18 at 22:18
  • 1
    @Gilles, NickJohnson, Re "academic"; Yea but not all cookies are 1024 bits. Some are only 36^16 ones. And it essentially depends fully on how many cookies he's generating. If he's generating 700*6b*9t cookies per microsecond, and still getting exponentially *faster* with each passing microsecond, sooner or later there would be a hit. – Pacerier Feb 17 '18 at 22:18
  • @Pacerier Even if the consequences are end-of-universe, it doesn't make sense to check for uniqueness. It is overwhelmingly more likely that all life on Earth is destroyed by a meteor than a unique value is ever released. – forest Apr 07 '18 at 01:41

4 Answers4

251

The short answer is yes. The long answer is also yes. /dev/urandom yields data which is indistinguishable from true randomness, given existing technology. Getting "better" randomness than what /dev/urandom provides is meaningless, unless you are using one of the few "information theoretic" cryptographic algorithm, which is not your case (you would know it).

The man page for urandom is somewhat misleading, arguably downright wrong, when it suggests that /dev/urandom may "run out of entropy" and /dev/random should be preferred; the only instant where /dev/urandom might imply a security issue due to low entropy is during the first moments of a fresh, automated OS install; if the machine booted up to a point where it has begun having some network activity then it has gathered enough physical randomness to provide randomness of high enough quality for all practical usages (I am talking about Linux here; on FreeBSD, that momentary instant of slight weakness does not occur at all). On the other hand, /dev/random has a tendency of blocking at inopportune times, leading to very real and irksome usability issues. Or, to say it in less words: use /dev/urandom and be happy; use /dev/random and be sorry.

(Edit: this Web page explains the differences between /dev/random and /dev/urandom quite clearly.)

For the purpose of producing a "cookie": such a cookie should be such that no two users share the same cookie, and that it is computationally infeasible for anybody to "guess" the value of an existing cookie. A sequence of random bytes does that well, provided that it uses randomness of adequate quality (/dev/urandom is fine) and that it is long enough. As a rule of thumb, if you have less than 2n users (n = 33 if the whole Earth population could use your system), then a sequence of n+128 bits is wide enough; you do not even have to check for a collision with existing values: you will not see it in your lifetime. 161 bits fits in 21 bytes.

There are some tricks which are doable if you want shorter cookies and still wish to avoid looking up for collisions in your database. But this should hardly be necessary for a cookie (I assume a Web-based context). Also, remember to keep your cookies confidential (i.e. use HTTPS, and set the cookie "secure" and "HttpOnly" flags).

Kevin Burke
  • 96
  • 1
  • 2
  • 10
Thomas Pornin
  • 320,799
  • 57
  • 780
  • 949
  • 3
    On the topic of urandom "running out", you're only sort of right. On a system with a poor entropy source (such as a VM) and a high rate of entropy use (lots of SSH connections, VPN tunnels, etc), urandom will return less random data instead of blocking. "Less random" is a loose term, but it means that you're more likely to see repetition. Is that a problem? Matters on your application :) In this case, urandom is probably fine. – Bill Weiss May 26 '11 at 14:40
  • 32
    @Bill, that is *not* correct. The chances of seeing repetition from `/dev/urandom`, due to high use of entropy, are essentially nil. (To be precise, by "repetition" I mean an amount of repetition that is statistically significantly higher than expected by chance.) There is essentially no risk that `/dev/urandom` ever "runs out" within your lifetime. – D.W. May 27 '11 at 06:20
  • Good answer, nice coverage of the whole question including the cookie aspect. Instead of checking the random value against other random values, use a chi-square test to check the output of the generator. Fourmilab has a program [ent](http://www.fourmilab.ch/random/) which test the entropy of a generator and includes the chi-square test. – this.josh Jul 01 '11 at 18:04
  • 1
    What it means when /dev/urandom runs out of entropy is that it produces a more predictable randomness, by that it means that an attacker with enough processing power can theoretically do statistical analysis of your random numbers to determine the internal state of the PRNG, and therefore predict your future random output. This is easier said than done though. – Lie Ryan Jan 09 '14 at 08:08
  • 5
    You might want to watch the talk "Fast Internet-wide Scanning and its Security Applications" given by J. Alex Halderman at 30C3. They did a large scan for SSH keys and basically found many duplicate keys. It turns out that many devices were embedded systems (like routers) which lack good sources of entropy (mouse, keyboard, etc.) and will usually generate the SSH key right after the boot. They determined that for /dev/urandom there is an "entropy gap" which can take 60 seconds (!) after the system startup, during which the output is actually predictable. – dog Feb 06 '14 at 22:05
  • 7
    @dog Before the CSPRNG has been seeded by enough entropy, its output will always be predictable, no matter how little data you read. Once it has been seeded with enough entropy, it will never be (practically) predictable no matter how much data you read. "Running out of entropy" isn't a thing. (CSPRNGs do have theoretical limits about how much data can be generated without a reseed, but you'll never hit them unless the CSPRNG in question sucks.) – Matt Nordhoff Apr 19 '14 at 05:22
  • 1
    @Thomas, Why does Schneier https://www.schneier.com/blog/archives/2013/10/insecurities_in.html contradict with your answer? – Pacerier Dec 12 '14 at 11:41
  • 9
    There is no contradiction (also, Schneier is merely quoting an article written by other people). The research paper worries about _recovering from an internal state compromise_, an already rotten situation. If your system was utterly compromised, you should have nuked it from orbit, rather than keeping on generating keys with it; what the article says is that _if_ you do the wrong thing (keep on using the compromised machine "as is" and pray for the best) then the PRNG used in /dev/random (and urandom) won't save your skin -- but, realistically, nothing would have. – Thomas Pornin Dec 12 '14 at 12:31
  • @ThomasPornin, re "begun having some network activity"; What about airgapped devices? – Pacerier Feb 17 '18 at 22:25
  • @D.W., re "not correct"; And which OS? – Pacerier Feb 17 '18 at 22:30
  • @MattNordhoff, re "its output will always be predictable"; You're missing the point. the point is that if you use `urandom` **you get insecure output** as demonstrated by J. Alex Halderman above. If you instead use `random`, it would block until it is safe so the output is secure. ¶ Context and use case would determine if something is (in)secure, In short: for some cases, use `random` and be happy; use `urandom` and be sorry. – Pacerier Feb 17 '18 at 22:45
  • Does this answer hold true for MacOS ? I am interested in the context of cryptocurrency wallet software that relies on OS entropy for the generation of private keys. – Scratcha Jan 10 '19 at 17:56
  • @Scratcha, MacOS is based on FreeBSD, so unless they changed the implementation of those two devices (`/dev/random` and `/dev/urandom`) and assuming your wallet software uses them adequately, then you're good. – Alexis Wilke Jan 22 '19 at 18:49
26

Yes, it's a great way.

@Thomas's explanation nails it. And he is completely right to criticize the /dev/urandom man page. Spot on.

But skip "checking if it already exists". That check is pointless. It ain't gonna happen. (The chances of that happening are lower than the probability of being struck by lightning -- multiple times -- in the same day.)

D.W.
  • 98,420
  • 30
  • 267
  • 572
  • 1
    So who is right, This page or https://www.schneier.com/blog/archives/2013/10/insecurities_in.html ? – Pacerier Dec 12 '14 at 10:25
  • 4
    @Pacerier, there's not enough space in this comment to give a nuanced explanation. Suffice it to say that the practical implications of that paper for this question are extremely limited. See e.g. https://www.mail-archive.com/cryptography@metzdowd.com/msg13301.html (focus on the technical content). See also https://www.mail-archive.com/cypherpunks%40cpunks.org/msg01390.html and https://www.mail-archive.com/cypherpunks%40cpunks.org/msg01365.html. If you want to understand better, ask a separate question on Crypto.SE. Please don't use comments to ask questions; post a new question. – D.W. Dec 12 '14 at 18:23
1

Be aware of edge-cases if you're using Linux or NetBSD.

On Linux, you'd want make sure that enough entropy has been gained after boot to properly seed the CSPRNG, or use the getrandom() system call to read from /dev/urandom and only block in the rare event that sufficient post-boot initial seed entropy is unavailable.

In NetBSD, you'd want to read from /dev/random at least once before reading from /dev/urandom to ensure it has been seeded properly.

On FreeBSD and MacOS there is no difference between /dev/random and /dev/urandom.

The short answer is still to use /dev/urandom.

See When to use /dev/random vs /dev/urandom for further details.

Community
  • 1
Tom Hale
  • 2,545
  • 3
  • 9
  • 11
-4

From http://www.linuxfromscratch.org/hints/downloads/files/entropy.txt "Generating true entropy in a computer is fairly difficult because nothing, outside of quantum physics, is random. The Linux kernel uses keyboard, mouse, network, and disc activities, with a cryptographic algorithm (SHA1), to generate data for the /dev/random device. One of the problems with this is that the input is not constant, so the kernel entropy pool can easily become empty." "Another problem with using the keyboard, mouse, network, and disc activity is that on idle, unmanned, and disc-less systems there is very little, or no, input of this kind."

To me it looks real possible that /dev/urandom will run out because /dev/random feeds it.

Buktop
  • 47
  • 2
  • 6
    Did you read [Thomas's answer](http://security.stackexchange.com/a/3939/5947)? If so, why do you think it's wrong? – Keith Thompson Aug 13 '13 at 22:29
  • 1
    Yes, Keith, I did read. When /dev/random is blocked cause the entropy pool depletes then /dev/urandom provides a random bites by using the same entropy for each new request. If you don't care about prediction resistance you may use /dev/urandom as the simple to use source of random bits (it always answers, no blocking). However, if you care that an each next new key generated (as example) was based on less predictable random bits than use /dev/random and feed the entropy pool by generating a system events in a case /dev/random blocks. – Buktop Aug 15 '13 at 20:25
  • 4
    Thomas's point seems to be that `/dev/urandom` "running out of entropy" just isn't a problem. It continues to generate random bytes by other means, but in practice that doesn't affect predictability. I don't know enough about the issues to judge whether he's correct (though what he says agrees with things I've read elsewhere). Do you have specific evidence (or solid theory) that suggests draining the entropy pool is a real problem for `/dev/urandom`? Code that actually predicts the output of `/dev/urandom` with better results than chance would be good evidence. – Keith Thompson Aug 15 '13 at 20:32
  • 1
    I agree, that when /dev/random blocks cause of not enought entropy in the pool then we may use /dev/urandom - it continues to respond. However its outputs are based on the same entropy (run through SHA-1) and are potentially predictable if an attacker collects what /dev/urandom produces or even if he/she collects what has been generated by using the entropy obtained from /dev/urandom. All of that for the case when the entropy pool has not enough data to feed /dev/random. – Buktop Aug 20 '13 at 20:02
  • 4
    "/dev/urandom uses small amounts of data from /dev/random to seed a secondary entropy pool. This has the effect of inflating the real entropy so it can be conserved. Using /dev/urandom can cause /dev/random's pool to become empty, but if this happens /dev/urandom will not block, and it will continue using the last available seed. This makes /dev/urandom theoretically vulnerable to outputting repeating data, depending on the limitations of the algorithm used, but this is extremely rare and to my knowledge has never actually happened. – Buktop Aug 20 '13 at 20:10
  • 3
    /dev/urandom is widely considered safe for all cryptographic purposes, except by the most paranoid people." – Buktop Aug 20 '13 at 20:11
  • 5
    Your recent comments almost seem to contradict your answer. – Keith Thompson Aug 20 '13 at 20:20
  • "Using the last available seed" does not mean the output repeats. It is still cryptographically secure output, and will be essentially forever unless someone compromises the kernel and reads the seed out of memory. – forest Dec 19 '17 at 10:54
  • If outputs repeats how it can be cryptographically secure? FIPS140-2 communicates that clearly. I love being in minus with the only right answer in the thread. NIST does not accept /dev/urandom. NIST accepts only 128 bits from /dev/random (does NIST actually still accept that much?). But smarties know better. – Buktop Dec 20 '17 at 23:31
  • /dev/urandom repeats outputs when no events happen on the system. /dev/random provides no outputs in this case. Thus cryptographically /dev/random is more secure. – Buktop Dec 27 '17 at 20:28