Tell me more ×
IT Security Stack Exchange is a question and answer site for IT security professionals. It's 100% free, no registration required.
up vote 31 down vote favorite
5

Lets say I want to cookie for a user, would simply going to /dev/urandom, generating a 1024 bit string, checking if it already exists (and looping till I get a unique one) suffice? Or should I be generating the key based on something else, because this is prone to a exploit somehow?

share|improve this question
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
1  
@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 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 Oct 4 '11 at 20:40
1  
@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 4 '11 at 20:45
2  
@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 IT Security Chat(chat.stackexchange.com/rooms/info/151). – Gilles Oct 4 '11 at 21:34
6  
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 3:04

2 Answers

up vote 40 down vote accepted

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.

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" flag).

share|improve this answer
1  
a pragmatic answer +1 – VP. May 19 '11 at 9:32
2  
...and the HTTP-only flag. – SLaks May 20 '11 at 11:21
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
5  
@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 6: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 which test the entropy of a generator and includes the chi-square test. – this.josh Jul 1 '11 at 18:04
up vote 6 down vote

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.)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.