Why does reading from /dev/urandom deplete entropy so much?
While debugging Exim4's GnuTLS interface, I recently found out that reading from /dev/urandom depletes entropy as much as reading from /dev/random would. This has somehow surprised me since I have always believed that /dev/urandom has lower quality entropy than /dev/random, but lots of it.
This also means that I can "sabotage" applications reading from /dev/random just by continuously reading from /dev/urandom, even not meaning to do any harm.
Before I file a bug on bugzilla, can I ask why /dev/urandom wasn't implemented as a PRNG which is periodically (say, every 1024 bytes or even more) seeded from /dev/random? That way, /dev/random has a much higher chance of holding enough entropy for applications that really need "good" entropy.
Entropy depletion has become an issue on Linux systems since the network was removed from the group of entropy sources a few years ago. Of the around 20 Linux systems that I currently have root privileges on, only two have a hardware RNG.
What can I do to keep sufficiently high entropy pools even if I read from /dev/urandom more than once in a while?
Greetings
Marc
Signature · 4 lines
----------------------------------------------------------------------------- Marc Haber | "I don't trust Computers. They | Mailadresse im Header Mannheim, Germany | lose things." Winona Ryder | Fon: *49 621 72739834 Nordisch by Nature | How to make an American Quilt | Fax: *49 3221 2323190
Quoted 16 lines · Marc Haber
While debugging Exim4's GnuTLS interface, I recently found out that reading from
/dev/urandomdepletes entropy as much as reading from/dev/randomwould. This has somehow surprised me since I have always believed that/dev/urandomhas lower quality entropy than/dev/random, but lots of it.This also means that I can "sabotage" applications reading from
/dev/randomjust by continuously reading from/dev/urandom, even not meaning to do any harm.Before I file a bug on bugzilla, can I ask why
/dev/urandomwasn't implemented as a PRNG which is periodically (say, every 1024 bytes or even more) seeded from/dev/random? That way,/dev/randomhas a much higher chance of holding enough entropy for applications that really need "good" entropy.
Quoted 5 lines
Entropy depletion has become an issue on Linux systems since the network was removed from the group of entropy sources a few years ago. Of the around 20 Linux systems that I currently have root privileges on, only two have a hardware RNG.
Some network drivers still feed entropy pools :
$ find drivers/net | xargs grep -n IRQF_SAMPLE_RANDOM
drivers/net/mv643xx_eth.c:1336: IRQF_SHARED | IRQF_SAMPLE_RANDOM, dev->name, dev);
drivers/net/3c527.c:437: err = request_irq(dev->irq, &mc32_interrupt, IRQF_SHARED | IRQF_SAMPLE_RANDOM, DRV_NAME, dev);
drivers/net/xen-netfront.c:1371: IRQF_SAMPLE_RANDOM, netdev->name,
drivers/net/macb.c:1131: err = request_irq(dev->irq, macb_interrupt, IRQF_SAMPLE_RANDOM,
drivers/net/tg3.c:7268: flags = IRQF_SAMPLE_RANDOM;
drivers/net/tg3.c:7273: flags = IRQF_SHARED | IRQF_SAMPLE_RANDOM;
drivers/net/tg3.c:7291: IRQF_SHARED | IRQF_SAMPLE_RANDOM, dev->name, dev);
drivers/net/qla3xxx.c:3648: unsigned long irq_flags = IRQF_SAMPLE_RANDOM | IRQF_SHARED;
drivers/net/3c523.c:292: ret = request_irq(dev->irq, &elmc_interrupt, IRQF_SHARED | IRQF_SAMPLE_RANDOM,
drivers/net/cris/eth_v10.c:704: IRQF_SAMPLE_RANDOM, cardname, (void *)dev)) {
drivers/net/atl1/atl1_main.c:1967: int irq_flags = IRQF_SAMPLE_RANDOM;
drivers/net/niu.c:4647: IRQF_SHARED | IRQF_SAMPLE_RANDOM,
drivers/net/netxen/netxen_nic_main.c:866: IRQF_SHARED|IRQF_SAMPLE_RANDOM, netdev->name,
drivers/net/ibmlana.c:784: result = request_irq(priv->realirq, irq_handler, IRQF_SHARED | IRQF_SAMPLE_RANDOM, dev->name, dev);So I guess you could patch your kernel to get more entropy sources (even if they are not *perfect* for some purists)
Quoted 7 lines
What can I do to keep sufficiently high entropy pools even if I read from
/dev/urandommore than once in a while?Greetings
Marc
Quoted 5 lines · Marc Haber
While debugging Exim4's GnuTLS interface, I recently found out that reading from
/dev/urandomdepletes entropy as much as reading from/dev/randomwould. This has somehow surprised me since I have always believed that/dev/urandomhas lower quality entropy than/dev/random, but lots of it.
man 4 random
Quoted 6 lines
This also means that I can "sabotage" applications reading from
/dev/randomjust by continuously reading from/dev/urandom, even not meaning to do any harm.Before I file a bug on bugzilla,
...
The bug would be closed as invalid.
No matter what you consider as being better, changing a 12 years old and widely used userspace interface like /dev/urandom is simply not an option.
Quoted 2 lines
Greetings
Marc
cu
Adrian
Signature · 4 lines
"Is there not promise of rain?" Ling Tan asked suddenly out
of the darkness. There had been need of rain for many days.
"Only a promise," Lao Er said.
Pearl S. Buck - Dragon SeedQuoted 3 lines
No matter what you consider as being better, changing a 12 years old and widely used userspace interface like
/dev/urandomis simply not an option.
Fixing it to be more efficient in its use of entropy and also fixing the fact its not actually a good random number source would be worth looking at however.
Quoted 7 lines · Alan Cox
Quoted 2 lines
No matter what you consider as being better, changing a 12 years old and widely used userspace interface like
/dev/urandomis simply not an option.Fixing it to be more efficient in its use of entropy and also fixing the fact its not actually a good random number source would be worth looking at however.
Yes, since current behavior on network irq is very pessimistic.
If you have some trafic, (ie more than HZ/2 interrupts per second), then add_timer_randomness() feeds some entropy but gives no credit (calling credit_entropy_store() with nbits=0)
This is because we take into account only the jiffies difference, and not the get_cycles() that should give us more entropy on most plaforms.
In this patch, I suggest that we feed only one u32 word of entropy, combination of the previous distinct words (with some of them being constant or so), so that the nbits estimation is less pessimistic, but also to avoid injecting false entropy.
drivers/char/random.c +20 -10
@@ -550,8 +550,8 @@ static void credit_entropy_store(struct entropy_store *r, int nbits)/* There is one of these per entropy source */ struct timer_rand_state { -cycles_t last_time; -long last_delta,last_delta2; +u32 last_word; +int last_delta,last_delta2;unsigned dont_count_entropy:1 ; };
@@ -570,12 +570,17 @@ static struct timer_rand_state *irq_timer_state[NR_IRQS];*/ static void add_timer_randomness (struct timer_rand_state *state,unsigned num) { -struct { -cycles_t cycles; -long jiffies; -unsigned num; +union { +struct { +cycles_t cycles; +long jiffies; +unsigned num; + }; +u32 words[1 ]; } sample; -long delta, delta2, delta3; +u32 word; +unsigned int ui; +int delta, delta2, delta3;preempt_disable ();/* if over the trickle threshold, use only 1 in 4096 samples */
@@ -586,7 +591,12 @@ static void add_timer_randomness(struct timer_rand_state *state, unsigned num) sample.jiffies = jiffies; sample.cycles =get_cycles (); sample.num = num; -add_entropy_words (&input_pool, (u32 *)&sample,sizeof (sample)/4 ); + + word = sample.words[0 ]; +for (ui =1 ; ui <sizeof (sample)/4 ; ui++) + word += sample.words[ui]; + +add_entropy_words (&input_pool, &word,1 );/* * Calculate number of bits of randomness we probably added.
@@ -595,8 +605,8 @@ static void add_timer_randomness(struct timer_rand_state *state, unsigned num)*/ if (!state->dont_count_entropy) { - delta = sample.jiffies - state->last_time; - state->last_time = sample.jiffies; + delta = word - state->last_word; + state->last_word = word; delta2 = delta - state->last_delta; state->last_delta = delta;
Quoted 11 lines · Eric Dumazet
Alan Cox a ?crit :
Quoted 9 lines
Quoted 4 lines
No matter what you consider as being better, changing a 12 years old and widely used userspace interface like
/dev/urandomis simply not an option.Fixing it to be more efficient in its use of entropy and also fixing the fact its not actually a good random number source would be worth looking at however.
Yes, since current behavior on network irq is very pessimistic.
No, it's very optimistic. The network should not be trusted.
The distinction between /dev/random and /dev/urandom boils down to one
word: paranoia. If you are not paranoid enough to mistrust your network, then /dev/random IS NOT FOR YOU. Use /dev/urandom. Do not send patches to make /dev/random less paranoid, kthxbye.
Quoted 8 lines
If you have some trafic, (ie more than HZ/2 interrupts per second), then
add_timer_randomness()feeds
some entropy but gives no credit (callingcredit_entropy_store()with nbits=0)This is because we take into account only the jiffies difference, and not the
get_cycles()that should give
us more entropy on most plaforms.
If we cannot measure a difference, we should nonetheless assume there is one?
Quoted 5 lines
In this patch, I suggest that we feed only one u32 word of entropy, combination of the previous distinct
words (with some of them being constant or so), so that the nbits estimation is less pessimistic, but also to
avoid injecting false entropy.
Umm.. no, that's not how it works at all.
Also, for future reference, patches for /dev/random go through me, not through Dave.
Signature · 1 line
Mathematics is the supreme nostalgia of our time.
Quoted 11 lines · Matt Mackall
Quoted 8 lines · Eric Dumazet
Alan Cox a ?crit :
Quoted 6 lines
Quoted 2 lines
No matter what you consider as being better, changing a 12 years old and widely used userspace interface like
/dev/urandomis simply not an option.Fixing it to be more efficient in its use of entropy and also fixing the fact its not actually a good random number source would be worth looking at however.
Yes, since current behavior on network irq is very pessimistic.
No, it's very optimistic. The network should not be trusted.
You keep saying that. I am refering to your previous attempts last year to remove net drivers from sources of entropy. No real changes were done.
If the network should not be trusted, then a patch should make sure network interrupts feed /dev/urandom but not /dev/random at all. (ie not calling credit_entropy_store() at all)
Quoted 5 lines
The distinction between
/dev/randomand/dev/urandomboils down to one
word: paranoia. If you are not paranoid enough to mistrust your network, then/dev/randomIS NOT FOR YOU. Use/dev/urandom. Do not send patches to make/dev/randomless paranoid, kthxbye.
I have many tg3 adapters on my servers, receiving thousand of interrupts per second, and calling add_timer_randomness(). I would like to either :
- Make sure this stuff is doing usefull job.
- Make improvements to reduce cpu time used.
I do not use /dev/urandom or/and /dev/random, but I know David wont accept a patch to remove IRQF_SAMPLE_RANDOM from tg3.c
Currently, I see that current implementation is suboptimal because it calls credit_entropy_store( nbits=0) forever.
Quoted 9 lines
Quoted 6 lines
If you have some trafic, (ie more than HZ/2 interrupts per second), then
add_timer_randomness()feeds some entropy but gives no credit (callingcredit_entropy_store()with nbits=0)This is because we take into account only the jiffies difference, and not the
get_cycles()that should give us more entropy on most plaforms.If we cannot measure a difference, we should nonetheless assume there is one?
There is a big difference on get_cycles() and jiffies. You should try to measure it on a typical x86_64 platform.
Quoted 10 lines
Quoted 4 lines
In this patch, I suggest that we feed only one u32 word of entropy, combination of the previous distinct words (with some of them being constant or so), so that the nbits estimation is less pessimistic, but also to avoid injecting false entropy.
Umm.. no, that's not how it works at all.
Also, for future reference, patches for
/dev/randomgo through me, not through Dave.
Why ? David is the network maintainer, and he was the one who rejected your previous patches.
Quoted 11 lines · Eric Dumazet
Matt Mackall a ?crit :
Quoted 10 lines · Eric Dumazet
Quoted 9 lines
Alan Cox a ?crit :
Quoted 8 lines
Quoted 4 lines
No matter what you consider as being better, changing a 12 years old and widely used userspace interface like
/dev/urandomis simply not an option.Fixing it to be more efficient in its use of entropy and also fixing the fact its not actually a good random number source would be worth looking at however.
Quoted 6 lines
Quoted 3 lines
Quoted 1 line
Yes, since current behavior on network irq is very pessimistic.
No, it's very optimistic. The network should not be trusted.
You keep saying that. I am refering to your previous attempts last year to remove net drivers from sources of entropy. No real changes were done.
Dave and I are both a bit stubborn on this point. I've been meaning to respin those patches..
Quoted 3 lines
If the network should not be trusted, then a patch should make sure network interrupts feed
/dev/urandombut not/dev/randomat all. (ie not callingcredit_entropy_store()at all)
Yes. My plan is to change the interface from SA_SAMPLE_RANDOM to add_network_entropy. The SA_SAMPLE_RANDOM interface sucks because it doesn't tell the core what kind of source it's dealing with.
Quoted 2 lines
There is a big difference on
get_cycles()and jiffies. You should try to measure it on a typicalx86_64platform.
I'm well aware of that. We'd use get_cycles() exclusively, but it returns zero on lots of platforms. We used to use sched_clock(), I can't remember why that got changed.
Quoted 5 lines
Quoted 2 lines
Also, for future reference, patches for
/dev/randomgo through me, not through Dave.Why ? David is the network maintainer, and he was the one who rejected your previous patches.
Because I'm the /dev/random maintainer and it's considered the polite thing to do, damnit.
Signature · 1 line
Mathematics is the supreme nostalgia of our time.
Quoted 3 lines · Matt Mackall
The distinction between
/dev/randomand/dev/urandomboils down to one
word: paranoia. If you are not paranoid enough to mistrust your network, then/dev/randomIS NOT FOR YOU. Use/dev/urandom.
But currently, people who use /dev/urandom to obtain low-quality entropy do a DoS for the paranoid people.
Greetings
Marc
Signature · 4 lines
----------------------------------------------------------------------------- Marc Haber | "I don't trust Computers. They | Mailadresse im Header Mannheim, Germany | lose things." Winona Ryder | Fon: *49 621 72739834 Nordisch by Nature | How to make an American Quilt | Fax: *49 3221 2323190
Quoted 7 lines · Marc Haber
Quoted 3 lines · Matt Mackall
The distinction between
/dev/randomand/dev/urandomboils down to one
word: paranoia. If you are not paranoid enough to mistrust your network, then/dev/randomIS NOT FOR YOU. Use/dev/urandom.But currently, people who use
/dev/urandomto obtain low-quality entropy do a DoS for the paranoid people.
Not true, as I've already pointed out in this thread.
Signature · 1 line
Mathematics is the supreme nostalgia of our time.
Quoted 10 lines · Matt Mackall
Quoted 7 lines · Marc Haber
Quoted 3 lines · Matt Mackall
The distinction between
/dev/randomand/dev/urandomboils down to one
word: paranoia. If you are not paranoid enough to mistrust your network, then/dev/randomIS NOT FOR YOU. Use/dev/urandom.But currently, people who use
/dev/urandomto obtain low-quality entropy do a DoS for the paranoid people.Not true, as I've already pointed out in this thread.
I must have missed this. Can you please explain again? For a layman it looks like a paranoid application cannot read 500 Bytes from /dev/random without blocking if some other application has previously read 10 Kilobytes from /dev/urandom.
Greetings
Marc
Signature · 4 lines
----------------------------------------------------------------------------- Marc Haber | "I don't trust Computers. They | Mailadresse im Header Mannheim, Germany | lose things." Winona Ryder | Fon: *49 621 72739834 Nordisch by Nature | How to make an American Quilt | Fax: *49 3221 2323190
Quoted 10 lines · Marc Haber
Quoted 9 lines · Matt Mackall
Quoted 7 lines · Marc Haber
Quoted 3 lines · Matt Mackall
The distinction between
/dev/randomand/dev/urandomboils down to one
word: paranoia. If you are not paranoid enough to mistrust your network, then/dev/randomIS NOT FOR YOU. Use/dev/urandom.But currently, people who use
/dev/urandomto obtain low-quality entropy do a DoS for the paranoid people.
Quoted 6 lines
Quoted 1 line
Not true, as I've already pointed out in this thread.
I must have missed this. Can you please explain again? For a layman it looks like a paranoid application cannot read 500 Bytes from
/dev/randomwithout blocking if some other application has previously read 10 Kilobytes from/dev/urandom.
/dev/urandom always leaves enough entropy in the input pool for /dev/random to reseed. Thus, as long as entropy is coming in, it is not possible for /dev/urandom readers to starve /dev/random readers. But /dev/random readers may still block temporarily and they should damn well expect to block if they read 500 bytes out of a 512 byte pool.
Signature · 1 line
Mathematics is the supreme nostalgia of our time.
Theodore Tso
maintainerQuoted 11 lines · Matt Mackall
Quoted 4 lines
I must have missed this. Can you please explain again? For a layman it looks like a paranoid application cannot read 500 Bytes from
/dev/randomwithout blocking if some other application has previously read 10 Kilobytes from/dev/urandom.
/dev/urandomalways leaves enough entropy in the input pool for/dev/randomto reseed. Thus, as long as entropy is coming in, it is not possible for/dev/urandomreaders to starve/dev/randomreaders. But/dev/randomreaders may still block temporarily and they should damn well expect to block if they read 500 bytes out of a 512 byte pool.
A paranoid application should only need to read ~500 bytes if it is generating a long-term RSA private key, and in that case, it would do well to use a non-blocking read, and if it can't get enough bytes, it should prompt the user to move the mouse around or bang on the keyboard. /dev/random is *not* magic where you can assume that you will always get an unlimited amount of good randomness. Applications who assume this are broken, and it has nothing to do with DOS attacks.
Note that even paranoid applicatons should not be using /dev/random for session keys; again, /dev/random isn't magic, and entropy isn't unlimited. Instead, such an application should pull 16 bytes or so, and then use it to seed a cryptographic random number generator.
- Ted
Quoted 4 lines · Theodore Tso
Note that even paranoid applicatons should not be using
/dev/randomfor session keys; again,/dev/randomisn't magic, and entropy isn't unlimited. Instead, such an application should pull 16 bytes or so, and then use it to seed a cryptographic random number generator.
What good does using multiple levels of RNG do? Why seed one RNG from another? Wouldn't it be better to have just one RNG that everybody uses? Doesn't the act of reading from the RNG add entropy to it, since no one reader has any idea how often and at what times other readers are stirring the pool?
Quoted 9 lines · Phillip Susi
Quoted 4 lines · Theodore Tso
Note that even paranoid applicatons should not be using
/dev/randomfor session keys; again,/dev/randomisn't magic, and entropy isn't unlimited. Instead, such an application should pull 16 bytes or so, and then use it to seed a cryptographic random number generator.What good does using multiple levels of RNG do? Why seed one RNG from another? Wouldn't it be better to have just one RNG that everybody uses?
Not all applications need cryptographically secure random numbers. Sometimes, you just want a random number to seed your game RNG or a monte carlo simulator.
Quoted 5 lines · Phillip Susi
What good does using multiple levels of RNG do? Why seed one RNG from another? Wouldn't it be better to have just one RNG that everybody uses? Doesn't the act of reading from the RNG add entropy to it, since no one reader has any idea how often and at what times other readers are stirring the pool?
No, unfortunately. The problem is that while in most typical cases may be true, the estimate of how much entropy we have has to be based on the assumption that everything we've done up to that point has been carefully orchestrated by the mortal enemy of whatever is currently asking us for entropy.
While I don't have any easy solutions with obvious irrefutable technical brilliance or that will make everyone happy, I do think that one of the problems is that neither /dev/random nor /dev/urandom are guaranteed to provide what most people want. In the most common use case, you want crypographically-strong randomness even under the assumption that all previous activity is orchestrated by the enemy. Unfortunately, /dev/urandom will happily give you randomness worse than this while /dev/random will block even when you have it.
DS
(Why hasn't anyone been cc:ing Matt on this?)
Quoted 14 lines · Adrian Bunk
Quoted 5 lines · Marc Haber
While debugging Exim4's GnuTLS interface, I recently found out that reading from
/dev/urandomdepletes entropy as much as reading from/dev/randomwould. This has somehow surprised me since I have always believed that/dev/urandomhas lower quality entropy than/dev/random, but lots of it.man 4 random
Quoted 4 lines
This also means that I can "sabotage" applications reading from
/dev/randomjust by continuously reading from/dev/urandom, even not meaning to do any harm.
Quoted 8 lines
Quoted 2 lines
Before I file a bug on bugzilla,
...The bug would be closed as invalid.
No matter what you consider as being better, changing a 12 years old and widely used userspace interface like
/dev/urandomis simply not an option.
You seem to be confused. He's not talking about changing any userspace interface, merely how the /dev/urandom data is generated.
For Matt's benefit, part of the original posting:
Quoted 5 lines
Before I file a bug on bugzilla, can I ask why
/dev/urandomwasn't implemented as a PRNG which is periodically (say, every 1024 bytes or even more) seeded from/dev/random? That way,/dev/randomhas a much higher chance of holding enough entropy for applications that really need "good" entropy.
A PRNG is clearly unacceptable. But roughly restated, why not have /dev/urandom supply merely cryptographically strong random numbers, rather than a mix between the 'true' random of /dev/random down to the cryptographically strong stream it'll provide when /dev/random is tapped? In principle, this'd leave more entropy available for applications that really need it, especially on platforms that don't generate a lot of entropy in the first place (servers).
Ray
Quoted 4 lines
cryptographically strong stream it'll provide when
/dev/randomis tapped? In principle, this'd leave more entropy available for applications that really need it, especially on platforms that don't generate a lot of entropy in the first place (servers).
As reported about a month ago, the evidence is that the /dev/random stream is not cryptographically strong. Collecting uuids generated from the kernel uuid random generator from the random generator in the kernel shows abnormal patterns of duplicates.
Alan
Quoted 10 lines · Alan Cox
Quoted 4 lines
cryptographically strong stream it'll provide when
/dev/randomis tapped? In principle, this'd leave more entropy available for applications that really need it, especially on platforms that don't generate a lot of entropy in the first place (servers).As reported about a month ago, the evidence is that the
/dev/randomstream is not cryptographically strong. Collecting uuids generated from the kernel uuid random generator from the random generator in the kernel shows abnormal patterns of duplicates.
Pointer, please.
Signature · 1 line
Mathematics is the supreme nostalgia of our time.
Theodore Tso
maintainerQuoted 7 lines · Matt Mackall
Quoted 6 lines · Alan Cox
Quoted 4 lines
cryptographically strong stream it'll provide when
/dev/randomis tapped? In principle, this'd leave more entropy available for applications that really need it, especially on platforms that don't generate a lot of entropy in the first place (servers).
Quoted 6 lines
Quoted 4 lines
As reported about a month ago, the evidence is that the
/dev/randomstream is not cryptographically strong. Collecting uuids generated from the kernel uuid random generator from the random generator in the kernel shows abnormal patterns of duplicates.Pointer, please.
Alan, are you sure you're not talking about Helge Deller's attempt to push a Time-based UUID generator into the kernel because you can get duplicates from the current userspace library?
I've not heard of *any* claim where the kernel uuid random generator has been returning duplicates.
- Ted
P.S. Probably the right approach for Helge is to create a daemon started at boot time with privileges to write the appropriate state file to prevent duplicates across reboots, and then to change the uuid library to use the daemon if it is available (accessed via a Unix domain socket), or to use its existing algorithm (which is fine unless you have multiple threads wanting to generate large numbers of UUIDs per second in parallel), and you want to use time-based UUID's because they have better b-tree characteristics when you use them as indexes into a database.
Quoted 13 lines · Theodore Tso
Quoted 12 lines · Matt Mackall
Quoted 10 lines · Alan Cox
Quoted 4 lines
cryptographically strong stream it'll provide when
/dev/randomis tapped? In principle, this'd leave more entropy available for applications that really need it, especially on platforms that don't generate a lot of entropy in the first place (servers).As reported about a month ago, the evidence is that the
/dev/randomstream is not cryptographically strong. Collecting uuids generated from the kernel uuid random generator from the random generator in the kernel shows abnormal patterns of duplicates.
Quoted 8 lines
Quoted 1 line
Pointer, please.
Alan, are you sure you're not talking about Helge Deller's attempt to push a Time-based UUID generator into the kernel because you can get duplicates from the current userspace library?
I've not heard of *any* claim where the kernel uuid random generator has been returning duplicates.
Before we added proper locking, it could theoretically happen on SMP with readers in lockstep. That was early 2.6.
The only serious critique I know of is the Gutterman-Pinkas-Reinman paper which was a year out of date before publication. Now that another year has passed, perhaps I should respond to it..
Signature · 1 line
Mathematics is the supreme nostalgia of our time.
Quoted 3 lines
Alan, are you sure you're not talking about Helge Deller's attempt to push a Time-based UUID generator into the kernel because you can get duplicates from the current userspace library?
Yes
Quoted 2 lines
I've not heard of *any* claim where the kernel uuid random generator has been returning duplicates.
Then the original reports got lost somewhere.
The Fedora tools use a kernel random uuid for system identifiers (to preserve anonymity while allowing system profiles etc to be generated and to know which are duplicates).
We seen a huge number of duplicates for certain values:
Quoted 15 lines
From Mike McGrath (added to Cc)
Here's the top 5:
266 28caf2c3-9766-4fe1-9e4c-d6b0ba8a0132 336 810e7126-1c69-4aff-b8b1-9db0fa8aa15a 402 c8dbb9d3-a9bd-4ba6-b92e-4a294ba5a95f 884 06e84493-e024-44b1-9b32-32d78af04039 931 e2b67e1d-e325-4740-b938-795addb45280The left number is times this month someone has submitted a profile with that UUID. If we take the last one as an example has come from over 800 IP's in the last 20 days. It seems very unlikely that one person would find his way to 800 different IP's this month. Let me know if you'd like more.
Quoted 8 lines · Alan Cox
Quoted 8 lines
Here's the top 5:
266 28caf2c3-9766-4fe1-9e4c-d6b0ba8a0132 336 810e7126-1c69-4aff-b8b1-9db0fa8aa15a 402 c8dbb9d3-a9bd-4ba6-b92e-4a294ba5a95f 884 06e84493-e024-44b1-9b32-32d78af04039 931 e2b67e1d-e325-4740-b938-795addb45280
Quoted 6 lines
Quoted 6 lines
The left number is times this month someone has submitted a profile with that UUID. If we take the last one as an example has come from over 800 IP's in the last 20 days. It seems very unlikely that one person would find his way to 800 different IP's this month. Let me know if you'd like more.
Background - Smolt runs this during its install:
/bin/cat /proc/sys/kernel/random/uuid > /etc/sysconfig/hw-uuid
For most users this would be run by the RPM %post scripts during install from anaconda. For some reason there are some UUID's (like those listed above) that come up more often then it seems they should if they are truly random.
-Mike
Quoted 15 lines · Mike McGrath
Quoted 8 lines · Alan Cox
Quoted 8 lines
Here's the top 5:
266 28caf2c3-9766-4fe1-9e4c-d6b0ba8a0132
336 810e7126-1c69-4aff-b8b1-9db0fa8aa15a
402 c8dbb9d3-a9bd-4ba6-b92e-4a294ba5a95f
884 06e84493-e024-44b1-9b32-32d78af04039
931 e2b67e1d-e325-4740-b938-795addb45280Quoted 6 lines
Quoted 6 lines
The left number is times this month someone has submitted a profile with that UUID. If we take the last one as an example has come from over 800 IP's in the last 20 days. It seems very unlikely that one person would find his way to 800 different IP's this month. Let me know if you'd like more.
Quoted 8 lines
Background - Smolt runs this during its install:
/bin/cat/proc/sys/kernel/random/uuid>/etc/sysconfig/hw-uuidFor most users this would be run by the RPM %post scripts during install from anaconda. For some reason there are some UUID's (like those listed above) that come up more often then it seems they should if they are truly random.
Ok, this sounds like it's run from install from CD or NFS, very early in the boot process. Presumably it gets run during hands-free install as well.
So a) we don't have a useful random seed file and b) we may have no entropy. We should probably dredge up some more system data for the initial pool seed (perhaps by passing in entropy from device probing).
The random seed file weakness is quite substantial. It affects basically everything on RO media. We can probably implement a loop something like the following to extract bits of entropy from the system timing for those systems with no RW media:
int get_raw_timing_bit(void)
{
int parity = 0;
int start = clock();
while(start == clock()) {
parity ^= 1;
}
return parity;
}int get_whitened_timing_bit(void) {
int a, b;
while (1) {
a = get_raw_timing_bit();
b = get_raw_timing_bit();
if (a > b)
return 0;
if (b > a)
return 1;
}
}int main(void)
{
int i;
for (i = 0; i < 64; i++)
printf("%d", get_whitened_timing_bit());
printf("\n");
}That's gonna average about 4 clock edges per bit bits, so if the external clock is running at 100HZ, we're looking at ~2.5 seconds for 64 bits of clock skew and scheduling "entropy".
The above can be done in userspace of course.
Signature · 1 line
Mathematics is the supreme nostalgia of our time.
Theodore Tso
maintainerQuoted 15 lines · Mike McGrath
Quoted 8 lines · Alan Cox
Quoted 8 lines
Here's the top 5:
266 28caf2c3-9766-4fe1-9e4c-d6b0ba8a0132 336 810e7126-1c69-4aff-b8b1-9db0fa8aa15a 402 c8dbb9d3-a9bd-4ba6-b92e-4a294ba5a95f 884 06e84493-e024-44b1-9b32-32d78af04039 931 e2b67e1d-e325-4740-b938-795addb45280Quoted 6 lines
Quoted 6 lines
The left number is times this month someone has submitted a profile with that UUID. If we take the last one as an example has come from over 800 IP's in the last 20 days. It seems very unlikely that one person would find his way to 800 different IP's this month. Let me know if you'd like more.
Quoted 8 lines
Background - Smolt runs this during its install:
/bin/cat/proc/sys/kernel/random/uuid>/etc/sysconfig/hw-uuidFor most users this would be run by the RPM %post scripts during install from anaconda. For some reason there are some UUID's (like those listed above) that come up more often then it seems they should if they are truly random.
Would this be by any chance using kickstart where there is no user interaction, and no way of gathering entropy during the install process? The random number generator isn't *magic* you know....
- Ted
Quoted 21 lines · Theodore Tso
Quoted 19 lines · Mike McGrath
Quoted 8 lines · Alan Cox
Quoted 8 lines
Here's the top 5:
266 28caf2c3-9766-4fe1-9e4c-d6b0ba8a0132 336 810e7126-1c69-4aff-b8b1-9db0fa8aa15a 402 c8dbb9d3-a9bd-4ba6-b92e-4a294ba5a95f 884 06e84493-e024-44b1-9b32-32d78af04039 931 e2b67e1d-e325-4740-b938-795addb45280Quoted 7 lines
Quoted 7 lines
The left number is times this month someone has submitted a profile with that UUID. If we take the last one as an example has come from over 800 IP's in the last 20 days. It seems very unlikely that one person would find his way to 800 different IP's this month. Let me know if you'd like more.
Background - Smolt runs this during its install:
Quoted 9 lines
Quoted 4 lines
/bin/cat/proc/sys/kernel/random/uuid>/etc/sysconfig/hw-uuidFor most users this would be run by the RPM %post scripts during install from anaconda. For some reason there are some UUID's (like those listed above) that come up more often then it seems they should if they are truly random.
Would this be by any chance using kickstart where there is no user interaction, and no way of gathering entropy during the install process? The random number generator isn't *magic* you know....
This is certainly possible but I think its unlikely. Not many people know about smolt. Most of our profiles come from prompting people during firstboot which gets skipped when people are running kickstart. I'll make sure to follow up with people that report a duplicate.
-Mike
Quoted 35 lines · Mike McGrath
Quoted 29 lines · Theodore Tso
Quoted 17 lines · Mike McGrath
Quoted 8 lines · Alan Cox
Quoted 8 lines
Here's the top 5:
266 28caf2c3-9766-4fe1-9e4c-d6b0ba8a0132
336 810e7126-1c69-4aff-b8b1-9db0fa8aa15a
402 c8dbb9d3-a9bd-4ba6-b92e-4a294ba5a95f
884 06e84493-e024-44b1-9b32-32d78af04039
931 e2b67e1d-e325-4740-b938-795addb45280Quoted 7 lines
Quoted 7 lines
The left number is times this month someone has submitted a profile with that UUID. If we take the last one as an example has come from over 800 IP's in the last 20 days. It seems very unlikely that one person would find his way to 800 different IP's this month. Let me know if you'd like more.
Quoted 9 lines
Background - Smolt runs this during its install:
/bin/cat/proc/sys/kernel/random/uuid>/etc/sysconfig/hw-uuidFor most users this would be run by the RPM %post scripts during install from anaconda. For some reason there are some UUID's (like those listed above) that come up more often then it seems they should if they are truly random.
Quoted 4 lines
Would this be by any chance using kickstart where there is no user interaction, and no way of gathering entropy during the install process? The random number generator isn't *magic* you know....
Quoted 4 lines
This is certainly possible but I think its unlikely. Not many people know about smolt. Most of our profiles come from prompting people during firstboot which gets skipped when people are running kickstart. I'll make sure to follow up with people that report a duplicate.
Please describe the process from boot to writing the UUID. Are we typically booting from R/O media? Is a random reseed done in the startup scripts? What is the source of the seed? How much user interaction is there?
If we have entropy input below the reseed threshold, we can get duplicates. That means we could have like a dozen or more keystrokes. Serial consoles and the like will also be problematic.
Signature · 1 line
Mathematics is the supreme nostalgia of our time.
Quoted 10 lines · Alan Cox
Quoted 3 lines
Alan, are you sure you're not talking about Helge Deller's attempt to push a Time-based UUID generator into the kernel because you can get duplicates from the current userspace library?
Yes
Quoted 2 lines
I've not heard of *any* claim where the kernel uuid random generator has been returning duplicates.
Then the original reports got lost somewhere.
Pretty sad that such an interesting security bug didn't make it to either of the /dev/random maintainers.
Quoted 3 lines
The Fedora tools use a kernel random uuid for system identifiers (to preserve anonymity while allowing system profiles etc to be generated and to know which are duplicates).
It's possible that on machines with no real entropy, the initial startup seeds were having no effect on the /dev/urandom output. That's fixed here:
http://www.kernel.org/hg/linux-2.6/rev/8298e254985e
which would have been in v2.6.22-rc4 through the normal CVE process. The only other bits in there are wall time and utsname, so systems with no CMOS clock would behave repeatably. Can we find out what kernels are affected?
Quoted 17 lines
We seen a huge number of duplicates for certain values:
Quoted 15 lines
From Mike McGrath (added to Cc)
Here's the top 5:
266 28caf2c3-9766-4fe1-9e4c-d6b0ba8a0132 336 810e7126-1c69-4aff-b8b1-9db0fa8aa15a 402 c8dbb9d3-a9bd-4ba6-b92e-4a294ba5a95f 884 06e84493-e024-44b1-9b32-32d78af04039 931 e2b67e1d-e325-4740-b938-795addb45280The left number is times this month someone has submitted a profile with that UUID. If we take the last one as an example has come from over 800 IP's in the last 20 days. It seems very unlikely that one person would find his way to 800 different IP's this month. Let me know if you'd like more.
Any other details would be interesting.
Signature · 1 line
Mathematics is the supreme nostalgia of our time.
Quoted 6 lines · Matt Mackall
which would have been in v2.6.22-rc4 through the normal CVE process. The only other bits in there are wall time and utsname, so systems with no CMOS clock would behave repeatably. Can we find out what kernels are affected?
We can but it will likely take a few weeks to get a good sampling. UUID is unique in the db so when someone checks in with the same UUID, the old one gets overwritten. I'll have to do regular copies of what the UUID holds over time. Smolt schedules a monthly check in which we literally just missed a few days ago.
Quoted 13 lines
Quoted 13 lines
We seen a huge number of duplicates for certain values:
Quoted 11 lines
From Mike McGrath (added to Cc)
Here's the top 5:
266 28caf2c3-9766-4fe1-9e4c-d6b0ba8a0132 336 810e7126-1c69-4aff-b8b1-9db0fa8aa15a 402 c8dbb9d3-a9bd-4ba6-b92e-4a294ba5a95f 884 06e84493-e024-44b1-9b32-32d78af04039 931 e2b67e1d-e325-4740-b938-795addb45280
Quoted 9 lines
Quoted 6 lines
Quoted 6 lines
The left number is times this month someone has submitted a profile with that UUID. If we take the last one as an example has come from over 800 IP's in the last 20 days. It seems very unlikely that one person would find his way to 800 different IP's this month. Let me know if you'd like more.
Any other details would be interesting.
We'll be able to get lots of stuff. Here's a profile of whats currently in e2b67e1d-e325-4740-b938-795addb45280.
u_u_id: e2b67e1d-e325-4740-b938-795addb45280o_s: Fedora release 7.92 (Rawhide)
platform: i686
bogomips: 3660.33system_memory: 2025system_swap: 964
vendor: Sony Corporation
system: VGN-FE31Z C3LMPJWXcpu_vendor: GenuineIntelcpu_model: Intel(R) Core(TM)2 CPU Tnum_cp_us: 2cpu_speed: 1833
language: en_US.UTdefault_runlevel: 5kernel_version: 2.6.23.1-23.fc8
formfactor: laptoplast_modified: 2007-10-02 04:22:42
rating: 3selinux_enabled: 1selinux_enforce: targeted
I'll grab the suspect UUID profiles over time to see what we end up with.
-Mike
Quoted 10 lines · Mike McGrath
Quoted 6 lines · Matt Mackall
which would have been in v2.6.22-rc4 through the normal CVE process. The only other bits in there are wall time and utsname, so systems with no CMOS clock would behave repeatably. Can we find out what kernels are affected?
We can but it will likely take a few weeks to get a good sampling. UUID is unique in the db so when someone checks in with the same UUID, the old one gets overwritten.
We can probably assume that for whatever reason the two things with duplicate UUID had the same seed. If not, we've got -much- bigger problems.
Quoted 15 lines
Quoted 9 lines
Quoted 7 lines
Quoted 7 lines
931 e2b67e1d-e325-4740-b938-795addb45280
The left number is times this month someone has submitted a profile with that UUID. If we take the last one as an example has come from over 800 IP's in the last 20 days. It seems very unlikely that one person would find his way to 800 different IP's this month. Let me know if you'd like more.
Any other details would be interesting.
We'll be able to get lots of stuff. Here's a profile of whats currently in e2b67e1d-e325-4740-b938-795addb45280.
u_u_id: e2b67e1d-e325-4740-b938-795addb45280o_s: Fedora release 7.92 (Rawhide)
..
Quoted 1 line
kernel_version: 2.6.23.1-23.fc8
Hmmm, a kernel where the fingered bug is already fixed.
So what's being used for the seed here? I assume you either ship all CDs with no seed file or the same seed file, yes? That leaves utsname, presumably a constant across a large number of machines and time of day. Still possible, I suppose, that's it's 931 boxes booted with the same time of day. How many total machines are you tracking?
If it is a time of day weirdness (ie N machines with dead CMOS batteries or no CMOS clock at all), then you'd expect to see a normal distribution of collisions around the average time to get to the initialization function, with a rapid falloff on either side. Or, looked at from a histogram of collision counts, a round peak rapidly rolling off.
Other failure modes would tend to give you a much more uniform (and therefore likely invisible) distribution.
Quoted 4 lines
platform: i686
bogomips: 3660.33system_memory: 2025system_swap: 964
Quoted 8 lines
vendor: Sony Corporation
system: VGN-FE31Z C3LMPJWXcpu_vendor: GenuineIntelcpu_model: Intel(R) Core(TM)2 CPU Tnum_cp_us: 2cpu_speed: 1833
language: en_US.UTdefault_runlevel: 5
Some bastard snuck a patch in to use ktime_get_real() in the pool init function, so we should have nanosecond resolution here, but only a) if TSC actually works and b) if all the clock sources get initialized before the RNG. Otherwise, we might be using jiffies or worse here.
Signature · 1 line
Mathematics is the supreme nostalgia of our time.
Quoted 11 lines · Matt Mackall
Quoted 9 lines · Mike McGrath
Quoted 7 lines · Matt Mackall
which would have been in v2.6.22-rc4 through the normal CVE process. The only other bits in there are wall time and utsname, so systems with no CMOS clock would behave repeatably. Can we find out what kernels are affected?
Quoted 7 lines
Quoted 2 lines
We can but it will likely take a few weeks to get a good sampling. UUID is unique in the db so when someone checks in with the same UUID, the old one gets overwritten.
We can probably assume that for whatever reason the two things with duplicate UUID had the same seed. If not, we've got -much- bigger problems.
Ok, I think I see whats going on here. I have some further investigation to do but it seems that the way our Live CD installer works is causing these issues. I'm going to try to grab some live CD's and hardware to confirm but at this point it seems thats whats going on.
-Mike
Quoted 22 lines · Mike McGrath
Quoted 11 lines · Matt Mackall
Quoted 9 lines · Mike McGrath
Quoted 7 lines · Matt Mackall
which would have been in v2.6.22-rc4 through the normal CVE process. The only other bits in there are wall time and utsname, so systems with no CMOS clock would behave repeatably. Can we find out what kernels are affected?
Quoted 9 lines
Quoted 4 lines
We can but it will likely take a few weeks to get a good sampling. UUID is unique in the db so when someone checks in with the same UUID, the old one gets overwritten.
We can probably assume that for whatever reason the two things with duplicate UUID had the same seed. If not, we've got -much- bigger problems.
Quoted 4 lines
Ok, I think I see whats going on here. I have some further investigation to do but it seems that the way our Live CD installer works is causing these issues. I'm going to try to grab some live CD's and hardware to confirm but at this point it seems thats whats going on.
Alright, keep me posted. We probably need a scheme to make the initial seed more robust regardless of what you find out.
Signature · 1 line
Mathematics is the supreme nostalgia of our time.
Quoted 26 lines · Matt Mackall
Quoted 24 lines · Mike McGrath
Quoted 22 lines · Matt Mackall
Quoted 11 lines · Mike McGrath
Quoted 8 lines · Matt Mackall
which would have been in v2.6.22-rc4 through the normal CVE process. The only other bits in there are wall time and utsname, so systems with no CMOS clock would behave repeatably. Can we find out what kernels are affected?
Quoted 3 lines
We can but it will likely take a few weeks to get a good sampling. UUID is unique in the db so when someone checks in with the same UUID, the old one gets overwritten.
We can probably assume that for whatever reason the two things with duplicate UUID had the same seed. If not, we've got -much- bigger problems.
Quoted 5 lines
Quoted 2 lines
Ok, I think I see whats going on here. I have some further investigation to do but it seems that the way our Live CD installer works is causing these issues. I'm going to try to grab some live CD's and hardware to confirm but at this point it seems thats whats going on.
Alright, keep me posted. We probably need a scheme to make the initial seed more robust regardless of what you find out
Ok, whats going on here is an issue with how the smolt RPM installs the UUID and how Fedora's Live CD does an install. It's a complete false alarm on the kernel side, sorry for the confusion.
-Mike
Theodore Tso
maintainerQuoted 4 lines · Mike McGrath
Ok, whats going on here is an issue with how the smolt RPM installs the UUID and how Fedora's Live CD does an install. It's a complete false alarm on the kernel side, sorry for the confusion.
BTW, You may be better off using "uuidgen -t" to generate the UUID in the smolt RPM, since that will use 12 bits of randomness from /dev/random, plus the MAC, address and timestamp. So even if there is zero randomness in /dev/random, and the time is January 1, 1970, at least the MAC will contribute some uniqueness to the UUID.
- Ted
Quoted 11 lines · Theodore Tso
Quoted 4 lines · Mike McGrath
Ok, whats going on here is an issue with how the smolt RPM installs the UUID and how Fedora's Live CD does an install. It's a complete false alarm on the kernel side, sorry for the confusion.
BTW, You may be better off using "uuidgen -t" to generate the UUID in the smolt RPM, since that will use 12 bits of randomness from
/dev/random, plus the MAC, address and timestamp. So even if there is zero randomness in/dev/random, and the time is January 1, 1970, at least the MAC will contribute some uniqueness to the UUID.
I haven't checked how uuidgen uses the MAC, but I would suggest that that is not something Fedora should jump at doing - although it would help ensure unique UUIDs, it also contributes to the tinfoil hat responses that usually come up with things like smolt.
Jon.
Theodore Tso
maintainerQuoted 10 lines · Jon Masters
Quoted 5 lines
BTW, You may be better off using "uuidgen -t" to generate the UUID in the smolt RPM, since that will use 12 bits of randomness from
/dev/random, plus the MAC, address and timestamp. So even if there is zero randomness in/dev/random, and the time is January 1, 1970, at least the MAC will contribute some uniqueness to the UUID.I haven't checked how uuidgen uses the MAC, but I would suggest that that is not something Fedora should jump at doing - although it would help ensure unique UUIDs, it also contributes to the tinfoil hat responses that usually come up with things like smolt.
Huh? What's the concern? All you are submitting is a list of hardware devices in your system. That's hardly anything sensitive....
- Ted
Quoted 8 lines · Theodore Tso
Quoted 6 lines · Jon Masters
Quoted 6 lines
BTW, You may be better off using "uuidgen -t" to generate the UUID in the smolt RPM, since that will use 12 bits of randomness from
/dev/random, plus the MAC, address and timestamp. So even if there is zero randomness in/dev/random, and the time is January 1, 1970, at least the MAC will contribute some uniqueness to the UUID.
Quoted 9 lines
Quoted 5 lines
I haven't checked how uuidgen uses the MAC, but I would suggest that that is not something Fedora should jump at doing - although it would help ensure unique UUIDs, it also contributes to the tinfoil hat responses that usually come up with things like smolt.
Huh? What's the concern? All you are submitting is a list of hardware devices in your system. That's hardly anything sensitive....
We actually had a very vocal minority about all of that which ended up putting us in the unfortunate position of generating a random UUID instead of using a hardware UUID from hal :-/
-Mike
Theodore Tso
maintainerQuoted 6 lines · Mike McGrath
Quoted 2 lines
Huh? What's the concern? All you are submitting is a list of hardware devices in your system. That's hardly anything sensitive....
We actually had a very vocal minority about all of that which ended up putting us in the unfortunate position of generating a random UUID instead of using a hardware UUID from hal :-/
Tinfoil hat responses indeed! Ok, if those folks are really that crazy, my suggestion then would be to do a "ifconfig -a > /dev/random" before generating the UUID, and/or waiting until you just about to send the first profile, and/or if you don't yet have a UUID, generating it at that very moment. The first will mix in the MAC address into the random pool, which will help guarantee uniqueness, and waiting until just before you send the result will mean it is much more likely that the random pool will have collected some entropy from user I/O, thus making the random UUID not only unique, but also unpredictable.
- Ted
Quoted 8 lines · Theodore Tso
Quoted 6 lines · Mike McGrath
Quoted 2 lines
Huh? What's the concern? All you are submitting is a list of hardware devices in your system. That's hardly anything sensitive....
We actually had a very vocal minority about all of that which ended up putting us in the unfortunate position of generating a random UUID instead of using a hardware UUID from hal :-/
Quoted 10 lines
Tinfoil hat responses indeed! Ok, if those folks are really that crazy, my suggestion then would be to do a "ifconfig -a >
/dev/random" before generating the UUID, and/or waiting until you just about to send the first profile, and/or if you don't yet have a UUID, generating it at that very moment. The first will mix in the MAC address into the random pool, which will help guarantee uniqueness, and waiting until just before you send the result will mean it is much more likely that the random pool will have collected some entropy from user I/O, thus making the random UUID not only unique, but also unpredictable.
I do like that idea, and it could be combined with the DMI data for the system containing things like asset tracking numbers, etc. Could use HAL to generate a UUID based on hardware IDs and feed that in as entropy ;-)
Jon.
Quoted 8 lines · Theodore Tso
Quoted 6 lines · Mike McGrath
Quoted 2 lines
Huh? What's the concern? All you are submitting is a list of hardware devices in your system. That's hardly anything sensitive....
We actually had a very vocal minority about all of that which ended up putting us in the unfortunate position of generating a random UUID instead of using a hardware UUID from hal :-/
Quoted 10 lines
Tinfoil hat responses indeed! Ok, if those folks are really that crazy, my suggestion then would be to do a "ifconfig -a >
/dev/random" before generating the UUID, and/or waiting until you just about to send the first profile, and/or if you don't yet have a UUID, generating it at that very moment. The first will mix in the MAC address into the random pool, which will help guarantee uniqueness, and waiting until just before you send the result will mean it is much more likely that the random pool will have collected some entropy from user I/O, thus making the random UUID not only unique, but also unpredictable.
It might be better for us to just improve the pool initialization. That'll improve the out of the box experience for everyone.
Signature · 1 line
Mathematics is the supreme nostalgia of our time.
Theodore Tso
maintainerQuoted 4 lines · Matt Mackall
It might be better for us to just improve the pool initialization. That'll improve the out of the box experience for everyone.
Yeah, I agree. Although keep in mind, doing things like mixing in MAC address and DMI information (which we can either do in the kernel or by trying to get all of the distro's to add that into their /etc/init.d/random script --- all several hundred or thousand distro's in the world :-), will help improve things like UUID uniqueness, it doesn't necessarily guarantee /dev/urandom and UUID *unpredictability*. In order to do that we really do need to improve the amount of hardware entropy we can mix into the system. This is a hard problem, but as more people are relying on these facilities, it's something we need to think about quite a bit more!
- Ted
entropy gathering (was Re: Why does reading from /dev/urandom deplete entropy so much?)
In reply to Matt MackallAs an aside...
Speaking as the maintainer rng-tools, which is the home of the hardware RNG entropy gathering daemon...
I wish somebody (not me) would take rngd and several other projects, and combine them into a single actively maintained "entropy gathering" package.
IMO entropy gathering has been a long-standing need for headless network servers (and now virtual machines).
In addition to rngd for hardware RNGs, I've been daemons out there that gather from audio and video sources (generally open wires/channels with nothing plugged in), thermal sources, etc. There is a lot of entropy that could be gathered via userland, if you think creatively.
Jeff
Re: entropy gathering (was Re: Why does reading from /dev/urandom deplete entropy so much?)
Quoted 8 lines · Jeff Garzik
As an aside...
Speaking as the maintainer rng-tools, which is the home of the hardware RNG entropy gathering daemon...
I wish somebody (not me) would take rngd and several other projects, and combine them into a single actively maintained "entropy gathering" package.
I think we should re-evaluate having an internal path from the hwrngs to /dev/[u]random, which will reduce the need for userspace config that can go wrong.
Signature · 1 line
Mathematics is the supreme nostalgia of our time.
Re: entropy gathering (was Re: Why does reading from /dev/urandom deplete entropy so much?)
Quoted 10 lines · Matt Mackall
Quoted 5 lines · Jeff Garzik
As an aside...
Speaking as the maintainer rng-tools, which is the home of the hardware RNG entropy gathering daemon...
I wish somebody (not me) would take rngd and several other projects, and combine them into a single actively maintained "entropy gathering" package.
I think we should re-evaluate having an internal path from the hwrngs to /dev/[u]random, which will reduce the need for userspace config that can go wrong.
That's a bit of a tangent on a tangent. :) Most people don't have a hardware RNG.
But as long as there are adequate safeguards against common hardware failures (read: FIPS testing inside the kernel), go for it.
Jeff
Re: entropy gathering (was Re: Why does reading from /dev/urandom deplete entropy so much?)
Quoted 15 lines · Jeff Garzik
Quoted 6 lines · Matt Mackall
Quoted 5 lines · Jeff Garzik
As an aside...
Speaking as the maintainer rng-tools, which is the home of the hardware RNG entropy gathering daemon...
Quoted 7 lines
Quoted 3 lines
I wish somebody (not me) would take rngd and several other projects, and combine them into a single actively maintained "entropy gathering" package.
I think we should re-evaluate having an internal path from the hwrngs to /dev/[u]random, which will reduce the need for userspace config that can go wrong.
Quoted 5 lines
That's a bit of a tangent on a tangent. :) Most people don't have a hardware RNG.
But as long as there are adequate safeguards against common hardware failures (read: FIPS testing inside the kernel), go for it.
We can do some internal whitening and some other basic tests (obviously not the full FIPS battery). The basic von Neumann whitening will do a great job of shutting off the spigot when an RNG fails in a non-nefarious way. And FIPS stuff is no defense against the nefarious failures anyway.
But I think simply dividing our entropy estimate by 10 or so will go an awfully long way.
--
Mathematics is the supreme nostalgia of our time.
Re: entropy gathering (was Re: Why does reading from /dev/urandom deplete entropy so much?)
Quoted 22 lines · Matt Mackall
Quoted 15 lines · Jeff Garzik
Quoted 6 lines · Matt Mackall
Quoted 5 lines · Jeff Garzik
As an aside...
Speaking as the maintainer rng-tools, which is the home of the hardware RNG entropy gathering daemon...
Quoted 7 lines
Quoted 3 lines
I wish somebody (not me) would take rngd and several other projects, and combine them into a single actively maintained "entropy gathering" package.
I think we should re-evaluate having an internal path from the hwrngs to /dev/[u]random, which will reduce the need for userspace config that can go wrong.
Quoted 5 lines
That's a bit of a tangent on a tangent. :) Most people don't have a hardware RNG.
But as long as there are adequate safeguards against common hardware failures (read: FIPS testing inside the kernel), go for it.
Quoted 8 lines
We can do some internal whitening and some other basic tests (obviously not the full FIPS battery). The basic von Neumann whitening will do a great job of shutting off the spigot when an RNG fails in a non-nefarious way. And FIPS stuff is no defense against the nefarious failures anyway.
But I think simply dividing our entropy estimate by 10 or so will go an awfully long way.
Agreed. The example program you posted does a very good job. I intuitively thought that it would show best results where CPU clock >>> system clock, but even with a faster clock (gettimeofday()) and a few tricks, it provides an excellent whitened output even at high speed. In fact, it has the advantage of automatically adjusting its speed to the source clock resolution, which ensures we don't return long runs of zeroes or ones. Here's my slightly modified version to extract large amounts of data from gettimeofday(), followed by test results :
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
int get_clock()
{
struct timeval tv;
unsigned i;
gettimeofday(&tv, NULL);
i = tv.tv_usec ^ tv.tv_sec;
i = (i ^ (i >> 16)) & 0xffff;
i = (i ^ (i >> 8)) & 0xff;
i = (i ^ (i >> 4)) & 0xf;
i = (i ^ (i >> 2)) & 0x3;
i = (i ^ (i >> 1)) & 0x1;
return i;
}int get_raw_timing_bit(void)
{
int parity = 0;
int start = get_clock();
while(start == get_clock()) {
parity++;
}
return parity & 1;
}int get_whitened_timing_bit(void) {
int a, b;
while (1) {
// ensure we restart without the time offset from the
// failed tests.
get_raw_timing_bit();
a = get_raw_timing_bit();
b = get_raw_timing_bit();
if (a > b)
return 1;
if (b > a)
return 0;
}
}int main(void)
{
int i;
while (1) {
for (i = 0; i < 64; i++) {
int j, k;
// variable-length eating 2N values per bit, looking
// for changing values.
do {
j = get_whitened_timing_bit();
k = get_whitened_timing_bit();
} while (j == k);
printf("%d", j);
}
printf("\n");
}
}On my athlon 1.5 GHz with HZ=250, it produces about 40 kb/second. On an IXP420 at 266 MHz with HZ=100, it produces about 6 kb/s. On a VAX VLC4000 at around 60 MHz under openbsd, it produces about 6 bits/s. In all cases, the output data looks well distributed :
willy@pcw:~$ for i in entropy.out.*; do echo $i :;z=$(tr -cd '0' <$i|wc -c); o=$(tr -cd '1' <$i|wc -c); echo $z zeroes, $o ones;done entropy.out.k7 : 159811 zeroes, 166861 ones entropy.out.nslu2 : 23786 zeroes, 24610 ones entropy.out.vax : 687 zeroes, 657 ones
And there are very few long runs, the data is not compressible :
willy@pcw:~$ for i in entropy.out.*; do echo -n "$i : ";u=$(tr -d '01' -c <$i|wc -c); c=$(tr -d '01' -c <$i | gzip -c9|wc -c); echo $(echo $u/$c|bc -l) digits/gzip byte;done entropy.out.k7 : 6.67672246407913830809 digits/gzip byte entropy.out.nslu2 : 6.27460132244262932711 digits/gzip byte entropy.out.vax : 4.74911660777385159010 digits/gzip byte
Here are the 4 first output lines of the k7 version :
0100011111001100111011100100100011011101010011110111100011111000 1111101101010110101011101000011010001011010001101101000101011011 1100111100100101000011000011010011101010010101101100011000011000 0100001100101001101000100100101110001001001011000110100111000000
I found no unique line out of 10000. I think the fact that the clock source used by gettimeofday() is not completely coupled with the TSC makes this possible. If we had used rdtsc() instead of gettimeofday(), we might have gotten really strange patterns. It's possible that peeking around out-of-cache memory data would add random bus latency to the numbers in such a case, but it's hard to know what memory size to map to ensure staying out of the cache.
Regards,
Willy
Theodore Tso
maintainerRe: entropy gathering (was Re: Why does reading from /dev/urandom deplete entropy so much?)
In reply to Jeff GarzikQuoted 2 lines · Jeff Garzik
That's a bit of a tangent on a tangent. :) Most people don't have a hardware RNG.
Actually, most Business class laptops from IBM/Lenovo, HP, Dell, Fujitsu, and Sony laptops *do* have TPM chips that among other things, contain a slow but (supposedly, if the TPM microprocessors are to be believed) secure hardware random number generator for use as a session key generator. This is thanks to various US legal mandates, such as HIPPA for the medical industry, and not just the paranoid ravings of the MPAA and RIAA. :-)
The problem is enabling the TPM isn't trivial, and life gets harder if you want the TPM chip to simultaneously work on dual-boot machines for both Windows and Linux, but it is certainly doable.
Quoted 3 lines
Quoted 3 lines
I think we should re-evaluate having an internal path from the hwrngs to /dev/[u]random, which will reduce the need for userspace config that can go wrong.
I think the userspace config problems were mainly due to the fact that there wasn't a single official userspace utility package for the random number package. Comments in drivers/char/random.c for how to set up /etc/init.d/random is Just Not Enough.
If we had a single, official random number generator package that contained the configuration, init.d script, as well as the daemon that can do all sorts of different things that you really, Really, REALLY want to do in userspace, including:
* FIPS testing (as Jeff suggested --- making sure what you think is randomness isn't 60Hz hum is a Really Good Idea :-)
* access to TPM (if available --- I have a vague memory that you may need access to the TPM key to access any of its functions, and the the TPM key is stored in the filesystem)
So.... anyone interested in belling the metaphorical cat? :-)
- Ted
Re: entropy gathering (was Re: Why does reading from /dev/urandom deplete entropy so much?)
Quoted 4 lines · Theodore Tso
I think the userspace config problems were mainly due to the fact that there wasn't a single official userspace utility package for the random number package. Comments in
drivers/char/random.cfor how to set up/etc/init.d/randomis Just Not Enough.
Absolutely.
Quoted 10 lines
If we had a single, official random number generator package that contained the configuration, init.d script, as well as the daemon that can do all sorts of different things that you really, Really, REALLY want to do in userspace, including:
* FIPS testing (as Jeff suggested --- making sure what you think is randomness isn't 60Hz hum is a Really Good Idea :-)
* access to TPM (if available --- I have a vague memory that you may need access to the TPM key to access any of its functions, and the the TPM key is stored in the filesystem)
+1 agreed
(not volunteering, but I will cheer on the hearty soul who undertakes this endeavor...)
Re: entropy gathering (was Re: Why does reading from /dev/urandom deplete entropy so much?)
In reply to Jeff GarzikQuoted 9 lines · Jeff Garzik
As an aside...
Speaking as the maintainer rng-tools, which is the home of the hardware RNG entropy gathering daemon...
I wish somebody (not me) would take rngd and several other projects, and combine them into a single actively maintained "entropy gathering" package.
Quoted 7 lines
IMO entropy gathering has been a long-standing need for headless network servers (and now virtual machines).
In addition to rngd for hardware RNGs, I've been daemons out there that gather from audio and video sources (generally open wires/channels with nothing plugged in), thermal sources, etc. There is a lot of entropy that could be gathered via userland, if you think creatively.
I remember having installed openssh on an AIX machines years ago, and being amazed by the number of sources it collected entropy from. Simple commands such as "ifconfig -a", "netstat -i" and "du -a", "ps -ef", "w" provided a lot of entropy.
Regards,
Willy
Theodore Tso
maintainerRe: entropy gathering (was Re: Why does reading from /dev/urandom deplete entropy so much?)
Quoted 4 lines · Willy Tarreau
I remember having installed openssh on an AIX machines years ago, and being amazed by the number of sources it collected entropy from. Simple commands such as "ifconfig -a", "netstat -i" and "du -a", "ps -ef", "w" provided a lot of entropy.
Well.... not as many bits of entropy as you might think. But every little bit helps, especially if some of it is not available to adversary.
- Ted
Re: entropy gathering (was Re: Why does reading from /dev/urandom deplete entropy so much?)
Quoted 9 lines · Theodore Tso
Quoted 4 lines · Willy Tarreau
I remember having installed openssh on an AIX machines years ago, and being amazed by the number of sources it collected entropy from. Simple commands such as "ifconfig -a", "netstat -i" and "du -a", "ps -ef", "w" provided a lot of entropy.
Well.... not as many bits of entropy as you might think. But every little bit helps, especially if some of it is not available to adversary.
I was always especially fond of the "du" entropy source with Solaris installations of OpenSSH (the PRNG used commands like "du" too). It was always amusing that a single network outage at the University would prevent anyone from ssh'ing into the "UNIX" machines. So yeah, if we want to take a giant leap backwards, I suggest jumping at this.
Lots of these are not actually random - you can guess the free space on a network drive in some certain cases, you know what processes are likely to be created on a LiveCD, and many dmesg outputs are very similar, especially when there aren't precie timestamps included.
But I do think it's time some of this got addressed :-)
Cheers,
Jon.
Quoted 7 lines · Theodore Tso
Quoted 3 lines · Mike McGrath
Quoted 2 lines
Huh? What's the concern? All you are submitting is a list of hardware devices in your system. That's hardly anything sensitive....
We actually had a very vocal minority about all of that which ended up putting us in the unfortunate position of generating a random UUID instead of using a hardware UUID from hal :-/
Tinfoil hat responses indeed! Ok, if those folks are really that crazy, my suggestion then would be to do a "ifconfig -a >
/dev/random"
heh, along those lines you could also do
dmesg > /dev/random
<grin>
dmesg often has machine-unique identifiers of all sorts (including the MAC address, if you have an ethernet driver loaded)
Jeff
Quoted 11 lines
heh, along those lines you could also do
dmesg >
/dev/random<grin>
dmesg often has machine-unique identifiers of all sorts (including the MAC address, if you have an ethernet driver loaded)
Jeff
A good three-part solution would be:
1) Encourage distributions to do "dmesg > /dev/random" in their startup scripts. This could even be added to the kernel (as a one-time dump of the kernel message buffer just before init is started).
2) Encourage drivers to output any unique information to the kernel log. I believe all/most Ethernet drivers already do this with MAC addresses. Perhaps we can get the kernel to include CPU serial numbers and we can get the IDE/SATA drivers to include hard drive serial numbers. We can also use the TSC, where available, in early bootup, which measures exactly how long it took to get the kernel going, which should have some entropy in it.
3) Add more entropy to the kernel's pool at early startup, even if the quality of that entropy is low. Track it appropriately, of course.
This should be enough to get cryptographically-strong random numbers that would hold up against anyone who didn't have access to the 'dmesg' output.
DS
Quoted 7 lines · Theodore Tso
Quoted 6 lines · Jon Masters
Quoted 5 lines
BTW, You may be better off using "uuidgen -t" to generate the UUID in the smolt RPM, since that will use 12 bits of randomness from
/dev/random, plus the MAC, address and timestamp. So even if there is zero randomness in/dev/random, and the time is January 1, 1970, at least the MAC will contribute some uniqueness to the UUID.
Quoted 7 lines
Quoted 4 lines
I haven't checked how uuidgen uses the MAC, but I would suggest that that is not something Fedora should jump at doing - although it would help ensure unique UUIDs, it also contributes to the tinfoil hat responses that usually come up with things like smolt.
Huh? What's the concern? All you are submitting is a list of hardware devices in your system. That's hardly anything sensitive....
Using MAC addresses -does- de-anonymize things though and presumably anonymous collection is a stated goal.
Signature · 1 line
Mathematics is the supreme nostalgia of our time.
Quoted 13 lines · Matt Mackall
Quoted 12 lines · Theodore Tso
Quoted 10 lines · Jon Masters
Quoted 5 lines
BTW, You may be better off using "uuidgen -t" to generate the UUID in the smolt RPM, since that will use 12 bits of randomness from
/dev/random, plus the MAC, address and timestamp. So even if there is zero randomness in/dev/random, and the time is January 1, 1970, at least the MAC will contribute some uniqueness to the UUID.I haven't checked how uuidgen uses the MAC, but I would suggest that that is not something Fedora should jump at doing - although it would help ensure unique UUIDs, it also contributes to the tinfoil hat responses that usually come up with things like smolt.
Quoted 5 lines
Quoted 2 lines
Huh? What's the concern? All you are submitting is a list of hardware devices in your system. That's hardly anything sensitive....
Using MAC addresses -does- de-anonymize things though and presumably anonymous collection is a stated goal.
Right. And the more I think about it, the more I think the solution is going to be for the smolt server to generate the UUID and tell the client about it. Anything else seems to be based on hope, especially when you're installing via kickstart or similar type of process.
Jon.
Theodore Tso
maintainerQuoted 5 lines · Matt Mackall
Quoted 2 lines
Huh? What's the concern? All you are submitting is a list of hardware devices in your system. That's hardly anything sensitive....
Using MAC addresses -does- de-anonymize things though and presumably anonymous collection is a stated goal.
True, but for many machines, the MAC address is enough for someone knowledgeable to (at least) determine what the manufacturer of your machine is, and in many cases, the model number of your laptop (since MAC addresses are assigned sequentially) and thus people can have a very good idea of the contents of your PCI tree ---- if for some reason anyone would even care, of course!
- Ted
Quoted 7 lines · Theodore Tso
Quoted 6 lines · Jon Masters
Quoted 5 lines
BTW, You may be better off using "uuidgen -t" to generate the UUID in the smolt RPM, since that will use 12 bits of randomness from
/dev/random, plus the MAC, address and timestamp. So even if there is zero randomness in/dev/random, and the time is January 1, 1970, at least the MAC will contribute some uniqueness to the UUID.
Quoted 7 lines
Quoted 4 lines
I haven't checked how uuidgen uses the MAC, but I would suggest that that is not something Fedora should jump at doing - although it would help ensure unique UUIDs, it also contributes to the tinfoil hat responses that usually come up with things like smolt.
Huh? What's the concern? All you are submitting is a list of hardware devices in your system. That's hardly anything sensitive....
Right, but the MAC is globally unique (well, that's normally true) so it is an identifiable user characteristic, moreso than just a list of PCI device IDs sitting on a particular bus. It's silly, but there it is.
Jon.
Quoted 11 lines · Theodore Tso
Quoted 4 lines · Mike McGrath
Ok, whats going on here is an issue with how the smolt RPM installs the UUID and how Fedora's Live CD does an install. It's a complete false alarm on the kernel side, sorry for the confusion.
BTW, You may be better off using "uuidgen -t" to generate the UUID in the smolt RPM, since that will use 12 bits of randomness from
/dev/random, plus the MAC, address and timestamp. So even if there is zero randomness in/dev/random, and the time is January 1, 1970, at least the MAC will contribute some uniqueness to the UUID.
I thought that /dev/random blocks when 0 entropy is available...? I'd expect uuid generation to block, not to issue duplicates.
Signature · 2 lines
(english) http://www.livejournal.com/~pavelmachek (cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html
Quoted 37 lines · Ray Lee
(Why hasn't anyone been cc:ing Matt on this?)
Quoted 14 lines · Adrian Bunk
Quoted 5 lines · Marc Haber
While debugging Exim4's GnuTLS interface, I recently found out that reading from
/dev/urandomdepletes entropy as much as reading from/dev/randomwould. This has somehow surprised me since I have always believed that/dev/urandomhas lower quality entropy than/dev/random, but lots of it.man 4 random
Quoted 4 lines
This also means that I can "sabotage" applications reading from
/dev/randomjust by continuously reading from/dev/urandom, even not meaning to do any harm.Quoted 8 lines
Quoted 2 lines
Before I file a bug on bugzilla,
...The bug would be closed as invalid.
No matter what you consider as being better, changing a 12 years old and widely used userspace interface like
/dev/urandomis simply not an option.You seem to be confused. He's not talking about changing any userspace interface, merely how the
/dev/urandomdata is generated.For Matt's benefit, part of the original posting:
Quoted 5 lines
Before I file a bug on bugzilla, can I ask why
/dev/urandomwasn't implemented as a PRNG which is periodically (say, every 1024 bytes or even more) seeded from/dev/random? That way,/dev/randomhas a much higher chance of holding enough entropy for applications that really need "good" entropy.
Quoted 7 lines
A PRNG is clearly unacceptable. But roughly restated, why not have
/dev/urandomsupply merely cryptographically strong random numbers, rather than a mix between the 'true' random of/dev/randomdown to the cryptographically strong stream it'll provide when/dev/randomis tapped? In principle, this'd leave more entropy available for applications that really need it, especially on platforms that don't generate a lot of entropy in the first place (servers).
The original /dev/urandom behavior was to use all the entropy that was available, and then degrade into a pure PRNG when it was gone. The intent is for /dev/urandom to be precisely as strong as /dev/random when entropy is readily available.
The current behavior is to deplete the pool when there is a large amount of entropy, but to always leave enough entropy for /dev/random to be read. This means we never completely starve the /dev/random side. The default amount is twice the read wakeup threshold (128 bits), settable in /proc/sys/kernel/random/.
But there's really not much point in changing this threshold. If you're reading the /dev/random side at the same rate or more often that entropy is appearing, you'll run out regardless of how big your buffer is.
Signature · 1 line
Mathematics is the supreme nostalgia of our time.
Quoted 47 lines · Matt Mackall
Quoted 33 lines · Ray Lee
(Why hasn't anyone been cc:ing Matt on this?)
Quoted 13 lines · Adrian Bunk
Quoted 5 lines · Marc Haber
While debugging Exim4's GnuTLS interface, I recently found out that reading from
/dev/urandomdepletes entropy as much as reading from/dev/randomwould. This has somehow surprised me since I have always believed that/dev/urandomhas lower quality entropy than/dev/random, but lots of it.man 4 random
Quoted 4 lines
This also means that I can "sabotage" applications reading from
/dev/randomjust by continuously reading from/dev/urandom, even not meaning to do any harm.Quoted 7 lines
Quoted 2 lines
Before I file a bug on bugzilla,
...The bug would be closed as invalid.
No matter what you consider as being better, changing a 12 years old and widely used userspace interface like
/dev/urandomis simply not an option.You seem to be confused. He's not talking about changing any userspace interface, merely how the
/dev/urandomdata is generated.For Matt's benefit, part of the original posting:
Quoted 5 lines
Before I file a bug on bugzilla, can I ask why
/dev/urandomwasn't implemented as a PRNG which is periodically (say, every 1024 bytes or even more) seeded from/dev/random? That way,/dev/randomhas a much higher chance of holding enough entropy for applications that really need "good" entropy.Quoted 7 lines
A PRNG is clearly unacceptable. But roughly restated, why not have
/dev/urandomsupply merely cryptographically strong random numbers, rather than a mix between the 'true' random of/dev/randomdown to the cryptographically strong stream it'll provide when/dev/randomis tapped? In principle, this'd leave more entropy available for applications that really need it, especially on platforms that don't generate a lot of entropy in the first place (servers).The original
/dev/urandombehavior was to use all the entropy that was available, and then degrade into a pure PRNG when it was gone. The intent is for/dev/urandomto be precisely as strong as/dev/randomwhen entropy is readily available.
Quoted 6 lines
The current behavior is to deplete the pool when there is a large amount of entropy, but to always leave enough entropy for
/dev/randomto be read. This means we never completely starve the/dev/randomside. The default amount is twice the read wakeup threshold (128 bits), settable in/proc/sys/kernel/random/.
In another post I suggested having a minimum bound (use not entropy) and a maximum bound (grab some entropy) with the idea that between these values some limited entropy could be used. I have to wonder if the entropy available is at least as unpredictable as the entropy itself.
Quoted 5 lines
But there's really not much point in changing this threshold. If you're reading the
/dev/randomside at the same rate or more often that entropy is appearing, you'll run out regardless of how big your buffer is.
Right, my thought is to throttle user + urandom use such that the total stays below the available entropy. I had forgotten that that was a lower bound, although it's kind of an on-off toggle rather than proportional. Clearly if you care about this a *lot* you will use a hardware RNG.
Thanks for the reminder on read_wakeup.
Signature · 3 lines
Bill Davidsen <[email protected]> "We have more to fear from the bungling of the incompetent than from the machinations of the wicked." - from Slashdot
Quoted 1 line · Ray Lee
(Why hasn't anyone been cc:ing Matt on this?)
I didn't because I am not a regularly enough visitor of this mailing list to know who is in charge of what.
Quoted 2 lines
Quoted 1 line · Marc Haber
A PRNG is clearly unacceptable.
Would a PRNG that is frequently re-seeded from true entropy be unacceptable as well?
Greetings
Marc
Signature · 4 lines
----------------------------------------------------------------------------- Marc Haber | "I don't trust Computers. They | Mailadresse im Header Mannheim, Germany | lose things." Winona Ryder | Fon: *49 621 72739834 Nordisch by Nature | How to make an American Quilt | Fax: *49 3221 2323190
Quoted 8 lines · Adrian Bunk
Quoted 5 lines · Marc Haber
While debugging Exim4's GnuTLS interface, I recently found out that reading from
/dev/urandomdepletes entropy as much as reading from/dev/randomwould. This has somehow surprised me since I have always believed that/dev/urandomhas lower quality entropy than/dev/random, but lots of it.man 4 random
Thanks for this pointer, I was not aware of the documentation. After reading this thread and the docs, I am now convinced that GnuTLS should seed a PRNG from /dev/(u)random instead of using the entropy directly. I will go filing a bug against GnuTLS.
Greetings
Marc
Signature · 4 lines
----------------------------------------------------------------------------- Marc Haber | "I don't trust Computers. They | Mailadresse im Header Mannheim, Germany | lose things." Winona Ryder | Fon: *49 621 72739834 Nordisch by Nature | How to make an American Quilt | Fax: *49 3221 2323190
Theodore Tso
maintainerQuoted 8 lines · Marc Haber
Quoted 7 lines · Adrian Bunk
Quoted 5 lines · Marc Haber
While debugging Exim4's GnuTLS interface, I recently found out that reading from
/dev/urandomdepletes entropy as much as reading from/dev/randomwould. This has somehow surprised me since I have always believed that/dev/urandomhas lower quality entropy than/dev/random, but lots of it.
Quoted 6 lines
Quoted 1 line
man 4 random
Thanks for this pointer, I was not aware of the documentation. After reading this thread and the docs, I am now convinced that GnuTLS should seed a PRNG from /dev/(u)random instead of using the entropy directly. I will go filing a bug against GnuTLS.
BTW, note that it would be a polite thing for GnuTLS when it is encrpyting data, which represents information which might not be available to an adversary, and SHA1 hash it (out of paranoia) and feed it to /dev/random.
This won't give any "credits" to the random entropy counter, but to the extent that is information that isn't available to the adversary, it adds additional uncertainty to the random pool.
- Ted
Quoted 8 lines · Theodore Tso
BTW, note that it would be a polite thing for GnuTLS when it is encrpyting data, which represents information which might not be available to an adversary, and SHA1 hash it (out of paranoia) and feed it to
/dev/random.This won't give any "credits" to the random entropy counter, but to the extent that is information that isn't available to the adversary, it adds additional uncertainty to the random pool.
I have filed this as https://savannah.gnu.org/support/index.php?106113
Thanks for suggesting.
Greetings
Marc
Signature · 4 lines
----------------------------------------------------------------------------- Marc Haber | "I don't trust Computers. They | Mailadresse im Header Mannheim, Germany | lose things." Winona Ryder | Fon: *49 621 72739834 Nordisch by Nature | How to make an American Quilt | Fax: *49 3221 2323190
Quoted 14 lines · Adrian Bunk
Quoted 5 lines · Marc Haber
While debugging Exim4's GnuTLS interface, I recently found out that reading from
/dev/urandomdepletes entropy as much as reading from/dev/randomwould. This has somehow surprised me since I have always believed that/dev/urandomhas lower quality entropy than/dev/random, but lots of it.man 4 random
Quoted 4 lines
This also means that I can "sabotage" applications reading from
/dev/randomjust by continuously reading from/dev/urandom, even not meaning to do any harm.
Quoted 6 lines
Quoted 2 lines
Before I file a bug on bugzilla,
...The bug would be closed as invalid.
No matter what you consider as being better, changing a 12 years old and widely used userspace interface like
/dev/urandomis simply not an option.
I don't see that he is proposing to change the interface, just how it gets the data it provides. Any program which depends on the actual data values it gets from urandom is pretty broken, anyway. I think that getting some entropy from network is a good thing, even if it's used only in urandom, and I would like a rational discussion of checking the random pool available when urandom is about to get random data, and perhaps having a lower and upper bound for pool size.
That is, if there is more than Nmax random data urandom would take some, if there was less than Nmin it wouldn't, and between them it would take data, but less often. This would improve the urandom quality in the best case, and protect against depleting the /dev/random entropy in low entropy systems. Where's the downside?
There has also been a lot of discussion over the years about improving the quality of urandom data, I don't personally think making the quality higher constitutes "changing a 12 years old and widely used userspace interface like /dev/urandom" either.
Sounds like a local DoS attack point to me...
Signature · 3 lines
Bill Davidsen <[email protected]> "We have more to fear from the bungling of the incompetent than from the machinations of the wicked." - from Slashdot
Quoted 2 lines · Bill Davidsen
...
Sounds like a local DoS attack point to me...
As long as /dev/random is readable for all users there's no reason to use /dev/urandom for a local DoS...
cu
Adrian
Signature · 4 lines
"Is there not promise of rain?" Ling Tan asked suddenly out
of the darkness. There had been need of rain for many days.
"Only a promise," Lao Er said.
Pearl S. Buck - Dragon SeedSunday 09 December 2007 00:03:45 tarihinde Adrian Bunk şunları yazmıştı:
Quoted 6 lines · Bill Davidsen
Quoted 2 lines
...
Sounds like a local DoS attack point to me...As long as
/dev/randomis readable for all users there's no reason to use/dev/urandomfor a local DoS...
Draining entropy in /dev/urandom means that insecure and possibly not random data will be used and well thats a security bug if not a DoS bug.
And yes this is by design, sigh.
Signature · 1 line
Never learn by your mistakes, if you do you may never dare to try again.
Theodore Tso
maintainerQuoted 5 lines · Ismail Dönmez
Quoted 2 lines
As long as
/dev/randomis readable for all users there's no reason to use/dev/urandomfor a local DoS...Draining entropy in
/dev/urandommeans that insecure and possibly not random data will be used and well thats a security bug if not a DoS bug.
Actually in modern 2.6 kernels there are two separate output entropy pools for /dev/random and /dev/urandom. So assuming that the adversary doesn't know the contents of the current state of the entropy pool (i.e., the RNG is well seeded with entropy), you can read all you want from /dev/urandom and that won't give an adversary successful information to attack /dev/random.
- Ted
Quoted 7 lines · Theodore Tso
Quoted 5 lines · Ismail Dönmez
Quoted 2 lines
As long as
/dev/randomis readable for all users there's no reason to use/dev/urandomfor a local DoS...Draining entropy in
/dev/urandommeans that insecure and possibly not random data will be used and well thats a security bug if not a DoS bug.
Quoted 6 lines
Actually in modern 2.6 kernels there are two separate output entropy pools for
/dev/randomand/dev/urandom. So assuming that the adversary doesn't know the contents of the current state of the entropy pool (i.e., the RNG is well seeded with entropy), you can read all you want from/dev/urandomand that won't give an adversary successful information to attack/dev/random.
Wouldn't it be possible to mix the data with the pid+uid of the reading process so that even if another one tries to collect data from urandom, he cannot predict what another process will get ? BTW, I think that the tuple (pid,uid,timestamp of open) is unpredictable and uncontrollable enough to provide one or even a few bits of entropy by itself.
Regards,
Willy
Quoted 5 lines · Willy Tarreau
Wouldn't it be possible to mix the data with the pid+uid of the reading process so that even if another one tries to collect data from urandom, he cannot predict what another process will get ? BTW, I think that the tuple (pid,uid,timestamp of open) is unpredictable and uncontrollable enough to provide one or even a few bits of entropy by itself.
Timestamp perhaps, but pid/uid are trivially guessable in automated environments, such as LiveCDs. And if you're also running on an embedded system without a RTC (common, folks like to save a few cents) then it's all pretty much "trivially" guessable on some level.
Jon.
Sunday 09 December 2007 01:46:12 tarihinde Theodore Tso şunları yazmıştı:
Quoted 7 lines · Ismail Dönmez
Quoted 5 lines
Quoted 2 lines
As long as
/dev/randomis readable for all users there's no reason to use/dev/urandomfor a local DoS...Draining entropy in
/dev/urandommeans that insecure and possibly not random data will be used and well thats a security bug if not a DoS bug.
Quoted 6 lines
Actually in modern 2.6 kernels there are two separate output entropy pools for
/dev/randomand/dev/urandom. So assuming that the adversary doesn't know the contents of the current state of the entropy pool (i.e., the RNG is well seeded with entropy), you can read all you want from/dev/urandomand that won't give an adversary successful information to attack/dev/random.
My understanding was if you can drain entropy from /dev/urandom any futher reads from /dev/urandom will result in data which is not random at all. Is that wrong?
Regards,
ismail
Signature · 1 line
Never learn by your mistakes, if you do you may never dare to try again.
Theodore Tso
maintainerQuoted 3 lines · Ismail Dönmez
My understanding was if you can drain entropy from
/dev/urandomany futher reads from/dev/urandomwill result in data which is not random at all. Is that wrong?
Past a certain point /dev/urandom will stat returning results which are cryptographically random. At that point, you are depending on the strength of the SHA hash algorithm, and actually being able to not just to find hash collisions, but being able to trivially find all or most possible pre-images for a particular SHA hash algorithm. If that were to happen, it's highly likely that all digital signatures and openssh would be totally broken.
- Ted
Sunday 09 December 2007 14:31:47 tarihinde Theodore Tso şunları yazmıştı:
Quoted 5 lines · Ismail Dönmez
Quoted 3 lines
My understanding was if you can drain entropy from
/dev/urandomany futher reads from/dev/urandomwill result in data which is not random at all. Is that wrong?
Quoted 7 lines
Past a certain point
/dev/urandomwill stat returning results which are cryptographically random. At that point, you are depending on the strength of the SHA hash algorithm, and actually being able to not just to find hash collisions, but being able to trivially find all or most possible pre-images for a particular SHA hash algorithm. If that were to happen, it's highly likely that all digital signatures and openssh would be totally broken.
Thats very good news, thanks for the detailed explanation. Time to update common misconceptions.
Regards,
ismail
Signature · 1 line
Never learn by your mistakes, if you do you may never dare to try again.
Quoted 8 lines · Adrian Bunk
Quoted 3 lines · Bill Davidsen
...
Sounds like a local DoS attack point to me...As long as
/dev/randomis readable for all users there's no reason to use/dev/urandomfor a local DoS...
The original point was that urandom draws entropy from random, and that it is an an inobvious and unintentional drain on the entropy pool. At least that's how I read it. I certainly have programs which draw on urandom simply because it's a convenient source of meaningless data. I have several fewer since this discussion started, though, now that I have looked at the easy alternatives.
Signature · 3 lines
Bill Davidsen <[email protected]> "Woe unto the statesman who makes war without a reason that will still be valid when the war is over..." Otto von Bismark
Quoted 3 lines · Bill Davidsen
The original point was that urandom draws entropy from random, and that it is an an inobvious and unintentional drain on the entropy pool. At least that's how I read it.
And you are reading it correct. At least one of the major TLS libraries does it this way, putting unnecessary stress on the kernel entropy pool. While I now consider this a bug in the library, there surely are gazillions of similiarily flawed applications out there in the wild.
Greetings
Marc
Signature · 4 lines
----------------------------------------------------------------------------- Marc Haber | "I don't trust Computers. They | Mailadresse im Header Mannheim, Germany | lose things." Winona Ryder | Fon: *49 621 72739834 Nordisch by Nature | How to make an American Quilt | Fax: *49 3221 2323190
Quoted 8 lines · Marc Haber
Quoted 1 line · Bill Davidsen
The original point was that urandom draws entropy from random, and that it is an an inobvious and unintentional drain on the entropy pool. At least that's how I read it.
And you are reading it correct. At least one of the major TLS libraries does it this way, putting unnecessary stress on the kernel entropy pool. While I now consider this a bug in the library, there surely are gazillions of similiarily flawed applications out there in the wild.
It seems to me that reading from (u)random disturbs the entropy pool, so the more consumers reading from the pool in unpredictable ways, the better. As it is currently implemented, it lowers the entropy estimate, but the pool will have MORE entropy if several applications keep reading /dev/random periodically when they need random bytes instead of just reading it once to seed their own prng. IMHO, it is the entropy estimate that is broken, not the TLS library.
Quoted 10 lines · Marc Haber <mh+linux-kernel <at> zugschlus.de> writes:
While debugging Exim4's GnuTLS interface, I recently found out that reading from
/dev/urandomdepletes entropy as much as reading from/dev/randomwould. This has somehow surprised me since I have always believed that/dev/urandomhas lower quality entropy than/dev/random, but lots of it.This also means that I can "sabotage" applications reading from
/dev/randomjust by continuously reading from/dev/urandom, even not meaning to do any harm.
An application either needs to be cryptographically secure, or it doesn't. If it doesn't, then just use /dev/urandom to seed a PRNG.