Skip to contentSkip to conversation

Why does reading from /dev/urandom deplete entropy so much?

DISCUSSION Marc Haber 18 participants 77 messages Dec 4, 2007 – Dec 26, 2007 Random number driver

lore
Share & tools
lore

Marc Haber

author
#0 lore raw

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
#1 lore raw
Quoted 16 lines · Marc Haber

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.

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/urandom more than once in a while?

Greetings
Marc

#2 lore raw
In reply to Marc Haber
Quoted 5 lines · Marc Haber

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.

man 4 random

Quoted 6 lines

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

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 Seed
#3 lore raw
Quoted 3 lines

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.

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.

#4 lore raw
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/urandom is 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
index 5fee056..6eccfc9 100644
@@ -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;
#5 lore raw
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/urandom is 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 (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.

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.
#6 lore raw
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/urandom is 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/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.

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

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/random go through me, not through Dave.

Why ? David is the network maintainer, and he was the one who rejected your previous patches.

#7 lore raw
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/urandom is 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/urandom but not /dev/random at all. (ie not calling credit_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 typical x86_64 platform.

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/random go 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.
author
#8 lore raw
In reply to Matt Mackall
Quoted 3 lines · Matt Mackall

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.

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
#9 lore raw
Quoted 7 lines · Marc Haber
Quoted 3 lines · Matt Mackall

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.

But currently, people who use /dev/urandom to 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.
author
#10 lore raw
Quoted 10 lines · Matt Mackall
Quoted 7 lines · Marc Haber
Quoted 3 lines · Matt Mackall

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.

But currently, people who use /dev/urandom to 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
#11 lore raw
Quoted 10 lines · Marc Haber
Quoted 9 lines · Matt Mackall
Quoted 7 lines · Marc Haber
Quoted 3 lines · Matt Mackall

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.

But currently, people who use /dev/urandom to 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/random without 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.
maintainer
#12 lore raw
Quoted 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/random without 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.

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

#13 lore raw
Quoted 4 lines · Theodore Tso

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.

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?

#14 lore raw
Quoted 9 lines · Phillip Susi
Quoted 4 lines · Theodore Tso

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.

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.

#15 lore raw
In reply to Phillip Susi
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

#16 lore raw
In reply to Adrian Bunk

(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/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.

man 4 random

Quoted 4 lines

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.

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/urandom is 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/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.

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

#17 lore raw
Quoted 4 lines

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

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

#18 lore raw
Quoted 10 lines · Alan Cox
Quoted 4 lines

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

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.

Pointer, please.

Signature · 1 line
Mathematics is the supreme nostalgia of our time.
maintainer
#19 lore raw
Quoted 7 lines · Matt Mackall
Quoted 6 lines · Alan Cox
Quoted 4 lines

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

Quoted 6 lines
Quoted 4 lines

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.

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.

#20 lore raw
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/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).

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.

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.
#21 lore raw
In reply to Theodore Tso
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-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.

#22 lore raw
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

#23 lore raw
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-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.

Quoted 8 lines

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.

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.
maintainer
#24 lore raw
In reply to Mike McGrath
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-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.

Quoted 8 lines

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.

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

#25 lore raw
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-795addb45280
Quoted 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-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.

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

#26 lore raw
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-795addb45280

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

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.
#27 lore raw
In reply to Alan Cox
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-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.

Signature · 1 line
Mathematics is the supreme nostalgia of our time.
#28 lore raw
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-795addb45280
o_s: Fedora release 7.92 (Rawhide)
platform: i686
bogomips: 3660.33
system_memory: 2025
system_swap: 964
vendor: Sony Corporation
system: VGN-FE31Z C3LMPJWX
cpu_vendor: GenuineIntel
cpu_model: Intel(R) Core(TM)2 CPU T
num_cp_us: 2
cpu_speed: 1833
language: en_US.UT
default_runlevel: 5
kernel_version: 2.6.23.1-23.fc8
formfactor: laptop
last_modified: 2007-10-02 04:22:42
rating: 3
selinux_enabled: 1
selinux_enforce: targeted

I'll grab the suspect UUID profiles over time to see what we end up with.

-Mike

#29 lore raw
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-795addb45280
o_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.33
system_memory: 2025
system_swap: 964

Quoted 8 lines

vendor: Sony Corporation
system: VGN-FE31Z C3LMPJWX
cpu_vendor: GenuineIntel
cpu_model: Intel(R) Core(TM)2 CPU T
num_cp_us: 2
cpu_speed: 1833
language: en_US.UT
default_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.
#30 lore raw
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

#31 lore raw
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.
#32 lore raw
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

maintainer
#33 lore raw
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.

- Ted

#34 lore raw
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.

maintainer
#35 lore raw
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.

Huh? What's the concern? All you are submitting is a list of hardware devices in your system. That's hardly anything sensitive....

- Ted

#36 lore raw
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

maintainer
#37 lore raw
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 :-/

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

#38 lore raw
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.

#39 lore raw
In reply to Theodore Tso
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.
maintainer
#40 lore raw
Quoted 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

#41 lore raw

entropy gathering (was Re: Why does reading from /dev/urandom deplete entropy so much?)

In reply to Matt Mackall

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.

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

#42 lore raw

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.
#43 lore raw

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

#44 lore raw

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.

#45 lore raw

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

maintainer
#46 lore raw

Re: entropy gathering (was Re: Why does reading from /dev/urandom deplete entropy so much?)

In reply to Jeff Garzik
Quoted 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

#47 lore raw

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.c for how to set up /etc/init.d/random is 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...)

#48 lore raw

Re: entropy gathering (was Re: Why does reading from /dev/urandom deplete entropy so much?)

In reply to Jeff Garzik
Quoted 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

maintainer
#49 lore raw

Re: 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

#50 lore raw

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.

#51 lore raw
In reply to Theodore Tso
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

#52 lore raw
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

#53 lore raw
In reply to Theodore Tso
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.
#54 lore raw
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.

maintainer
#55 lore raw
In reply to Matt Mackall
Quoted 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

#56 lore raw
In reply to Theodore Tso
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.

#57 lore raw
In reply to Theodore Tso
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
#58 lore raw
In reply to Ray Lee
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/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.

man 4 random

Quoted 4 lines

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.

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/urandom is 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/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.

Quoted 7 lines

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

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.
#59 lore raw
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/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.

man 4 random

Quoted 4 lines

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.

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/urandom is 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/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.

Quoted 7 lines

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

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.

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

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/random side 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
author
#60 lore raw
In reply to Ray Lee
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
author
#61 lore raw
In reply to Adrian Bunk
Quoted 8 lines · Adrian Bunk
Quoted 5 lines · Marc Haber

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.

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
maintainer
#62 lore raw
Quoted 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/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.

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

author
#63 lore raw
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
#64 lore raw
In reply to Adrian Bunk
Quoted 14 lines · Adrian Bunk
Quoted 5 lines · Marc Haber

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.

man 4 random

Quoted 4 lines

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.

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/urandom is 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
#65 lore raw
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 Seed
#66 lore raw

Sunday 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/random is readable for all users there's no reason to use /dev/urandom for 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.
maintainer
#67 lore raw
Quoted 5 lines · Ismail Dönmez
Quoted 2 lines

As long as /dev/random is readable for all users there's no reason to use /dev/urandom for 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.

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

#68 lore raw
Quoted 7 lines · Theodore Tso
Quoted 5 lines · Ismail Dönmez
Quoted 2 lines

As long as /dev/random is readable for all users there's no reason to use /dev/urandom for 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.

Quoted 6 lines

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.

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

#69 lore raw
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.

#70 lore raw
In reply to Theodore Tso

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/random is readable for all users there's no reason to use /dev/urandom for 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.

Quoted 6 lines

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.

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.
maintainer
#71 lore raw
Quoted 3 lines · Ismail Dönmez

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?

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

#72 lore raw

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/urandom any futher reads from /dev/urandom will result in data which is not random at all. Is that wrong?

Quoted 7 lines

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.

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.
#73 lore raw
In reply to Adrian Bunk
Quoted 8 lines · Adrian Bunk
Quoted 3 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...

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 
author
#74 lore raw
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
#75 lore raw
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.

#76 lore raw
In reply to Marc Haber
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/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.

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.