LinuxLists.cc - Why does reading from /dev/urandom deplete entropy so much?

[permalink] [raw]

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

On Tue, Dec 04, 2007 at 08:54:52AM -0800, Ray Lee wrote:
> (Why hasn't anyone been cc:ing Matt on this?)
>
> On Dec 4, 2007 8:18 AM, Adrian Bunk <[email protected]> wrote:
> > On Tue, Dec 04, 2007 at 12:41:25PM +0100, Marc Haber wrote:
> >
> > > 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
> >
> > > 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.
>
> 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:
>
> > 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).

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.

--
Mathematics is the supreme nostalgia of our time.

2007-12-04 18:03:42

[permalink] [raw]

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

On Tue, Dec 04, 2007 at 04:55:02PM +0000, Alan Cox wrote:
> > 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.

--
Mathematics is the supreme nostalgia of our time.

2007-12-04 18:18:21

by Eric Dumazet

[permalink] [raw]

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

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 5fee056..6eccfc9 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -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;

Attachments:

random.patch (1.77 kB)

2007-12-04 19:13:20

by Russ Dill

[permalink] [raw]

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

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.

2007-12-04 19:50:55

[permalink] [raw]

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

On Tue, Dec 04, 2007 at 12:02:37PM -0600, Matt Mackall wrote:
> On Tue, Dec 04, 2007 at 04:55:02PM +0000, Alan Cox wrote:
> > > 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.

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.

2007-12-04 20:38:10

[permalink] [raw]

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

On Tue, Dec 04, 2007 at 02:50:21PM -0500, Theodore Tso wrote:
> On Tue, Dec 04, 2007 at 12:02:37PM -0600, Matt Mackall wrote:
> > On Tue, Dec 04, 2007 at 04:55:02PM +0000, Alan Cox wrote:
> > > > 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.
>
> 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..

--
Mathematics is the supreme nostalgia of our time.

2007-12-04 20:46:21

by Alan

[permalink] [raw]

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

> 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

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

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

2007-12-04 20:53:48

[permalink] [raw]

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

Alan Cox wrote:
>> 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.
>>
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

2007-12-04 21:16:27

[permalink] [raw]

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

On Tue, Dec 04, 2007 at 08:40:36PM +0000, Alan Cox wrote:
> > 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
>
> > 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.

> 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?

> We seen a huge number of duplicates for certain values:
>
> >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.

--
Mathematics is the supreme nostalgia of our time.

2007-12-04 21:24:25

[permalink] [raw]

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

Matt Mackall wrote:
> 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.

>> We seen a huge number of duplicates for certain values:
>>
>> >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.
>

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

2007-12-04 21:55:40

[permalink] [raw]

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

On Tue, Dec 04, 2007 at 02:48:12PM -0600, Mike McGrath wrote:
> Alan Cox wrote:
> >>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.
> >>
> 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.

--
Mathematics is the supreme nostalgia of our time.

2007-12-04 22:04:04

[permalink] [raw]

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

2007-12-04 22:17:05

[permalink] [raw]

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

On Tue, Dec 04, 2007 at 03:18:27PM -0600, Mike McGrath wrote:
> Matt Mackall wrote:
> >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.

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

> 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

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.

--
Mathematics is the supreme nostalgia of our time.

2007-12-04 22:18:47

[permalink] [raw]

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

Theodore Tso wrote:
> On Tue, Dec 04, 2007 at 02:48:12PM -0600, Mike McGrath wrote:
>
>> Alan Cox wrote:
>>
>>>> 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.
>>>>
>>>>
>> 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....
>

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

2007-12-04 22:28:57

[permalink] [raw]

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

Matt Mackall wrote:
> On Tue, Dec 04, 2007 at 03:18:27PM -0600, Mike McGrath wrote:
>
>> Matt Mackall wrote:
>>
>>> 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.
>

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

2007-12-04 22:29:19

[permalink] [raw]

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

On Tue, Dec 04, 2007 at 04:12:51PM -0600, Mike McGrath wrote:
> Theodore Tso wrote:
> >On Tue, Dec 04, 2007 at 02:48:12PM -0600, Mike McGrath wrote:
> >
> >>Alan Cox wrote:
> >>
> >>>>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.
> >>>>
> >>>>
> >>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....
> >
>
> 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.

--
Mathematics is the supreme nostalgia of our time.

2007-12-04 22:35:20

[permalink] [raw]

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

On Tue, Dec 04, 2007 at 04:23:12PM -0600, Mike McGrath wrote:
> Matt Mackall wrote:
> >On Tue, Dec 04, 2007 at 03:18:27PM -0600, Mike McGrath wrote:
> >
> >>Matt Mackall wrote:
> >>
> >>>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.
> >
>
> 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.

--
Mathematics is the supreme nostalgia of our time.

2007-12-05 12:23:40

[permalink] [raw]

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

On Tue, Dec 04, 2007 at 08:54:52AM -0800, Ray Lee wrote:
> (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.

> > On Tue, Dec 04, 2007 at 12:41:25PM +0100, Marc Haber wrote:
> A PRNG is clearly unacceptable.

Would a PRNG that is frequently re-seeded from true entropy be
unacceptable as well?

Greetings
Marc

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

2007-12-05 12:29:21

[permalink] [raw]

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

On Tue, Dec 04, 2007 at 05:18:11PM +0100, Adrian Bunk wrote:
> On Tue, Dec 04, 2007 at 12:41:25PM +0100, Marc Haber wrote:
> > 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

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

2007-12-05 13:33:32

[permalink] [raw]

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

On Wed, Dec 05, 2007 at 01:29:12PM +0100, Marc Haber wrote:
> On Tue, Dec 04, 2007 at 05:18:11PM +0100, Adrian Bunk wrote:
> > On Tue, Dec 04, 2007 at 12:41:25PM +0100, Marc Haber wrote:
> > > 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.

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

2007-12-05 14:31:54

[permalink] [raw]

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

Matt Mackall wrote:
> On Tue, Dec 04, 2007 at 04:23:12PM -0600, Mike McGrath wrote:
>
>> Matt Mackall wrote:
>>
>>> On Tue, Dec 04, 2007 at 03:18:27PM -0600, Mike McGrath wrote:
>>>
>>>
>>>> Matt Mackall wrote:
>>>>
>>>>
>>>>> 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.
>>>
>>>
>> 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

2007-12-05 14:50:27

[permalink] [raw]

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

On Wed, Dec 05, 2007 at 08:26:19AM -0600, Mike McGrath wrote:
>
> 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

2007-12-05 15:10:46

[permalink] [raw]

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

On Wed, Dec 05, 2007 at 08:33:20AM -0500, Theodore Tso wrote:
> 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

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

2007-12-05 21:28:36

[permalink] [raw]

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

On Tue, Dec 04, 2007 at 07:17:58PM +0100, Eric Dumazet wrote:
> Alan Cox a ?crit :
> >>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.

> 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?

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

--
Mathematics is the supreme nostalgia of our time.

2007-12-06 07:03:30

by Eric Dumazet

[permalink] [raw]

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

Matt Mackall a ?crit :
> On Tue, Dec 04, 2007 at 07:17:58PM +0100, Eric Dumazet wrote:
>> Alan Cox a ?crit :
>>>> 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)

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

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

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

2007-12-06 16:10:59

[permalink] [raw]

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

On Thu, Dec 06, 2007 at 08:02:33AM +0100, Eric Dumazet wrote:
> Matt Mackall a ?crit :
> >On Tue, Dec 04, 2007 at 07:17:58PM +0100, Eric Dumazet wrote:
> >>Alan Cox a ?crit :
> >>>>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.

Dave and I are both a bit stubborn on this point. I've been meaning to
respin those patches..

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

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

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

--
Mathematics is the supreme nostalgia of our time.

2007-12-06 19:15:26

by Bill Davidsen

[permalink] [raw]

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

Adrian Bunk wrote:
> On Tue, Dec 04, 2007 at 12:41:25PM +0100, Marc Haber wrote:
>
>> 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
>
>> 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.

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

--
Bill Davidsen <[email protected]>
"We have more to fear from the bungling of the incompetent than from
the machinations of the wicked." - from Slashdot

2007-12-06 19:52:17

by Bill Davidsen

[permalink] [raw]

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

Matt Mackall wrote:
> On Tue, Dec 04, 2007 at 08:54:52AM -0800, Ray Lee wrote:
>> (Why hasn't anyone been cc:ing Matt on this?)
>>
>> On Dec 4, 2007 8:18 AM, Adrian Bunk <[email protected]> wrote:
>>> On Tue, Dec 04, 2007 at 12:41:25PM +0100, Marc Haber wrote:
>>>
>>>> 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
>>>
>>>> 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.
>> 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:
>>
>>> 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).
>
> 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/.
>
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.

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

--
Bill Davidsen <[email protected]>
"We have more to fear from the bungling of the incompetent than from
the machinations of the wicked." - from Slashdot

2007-12-08 07:39:01

[permalink] [raw]

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

On Wed, 2007-12-05 at 09:49 -0500, Theodore Tso wrote:
> On Wed, Dec 05, 2007 at 08:26:19AM -0600, Mike McGrath wrote:
> >
> > 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.

2007-12-08 17:33:23

[permalink] [raw]

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

On Sat, Dec 08, 2007 at 02:37:57AM -0500, Jon Masters wrote:
> > 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

2007-12-08 17:41:18

[permalink] [raw]

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

Theodore Tso wrote:
> On Sat, Dec 08, 2007 at 02:37:57AM -0500, Jon Masters wrote:
>
>>> 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....
>

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

2007-12-08 17:46:08

[permalink] [raw]

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

On Sat, Dec 08, 2007 at 12:32:04PM -0500, Theodore Tso wrote:
> On Sat, Dec 08, 2007 at 02:37:57AM -0500, Jon Masters wrote:
> > > 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....

Using MAC addresses -does- de-anonymize things though and presumably
anonymous collection is a stated goal.

--
Mathematics is the supreme nostalgia of our time.

2007-12-08 17:46:46

[permalink] [raw]

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

On Sat, 2007-12-08 at 12:32 -0500, Theodore Tso wrote:
> On Sat, Dec 08, 2007 at 02:37:57AM -0500, Jon Masters wrote:
> > > 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....

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.

2007-12-08 17:48:21

[permalink] [raw]

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

On Sat, 2007-12-08 at 11:43 -0600, Matt Mackall wrote:
> On Sat, Dec 08, 2007 at 12:32:04PM -0500, Theodore Tso wrote:
> > On Sat, Dec 08, 2007 at 02:37:57AM -0500, Jon Masters wrote:
> > > > 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....
>
> 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.

2007-12-08 17:50:28

[permalink] [raw]

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

On Sat, Dec 08, 2007 at 11:33:57AM -0600, Mike McGrath wrote:
>> 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

2007-12-08 17:55:39

[permalink] [raw]

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

On Sat, 2007-12-08 at 12:49 -0500, Theodore Tso wrote:
> On Sat, Dec 08, 2007 at 11:33:57AM -0600, Mike McGrath wrote:
> >> 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.

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.

2007-12-08 18:07:18

[permalink] [raw]

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

On Sat, Dec 08, 2007 at 11:43:43AM -0600, Matt Mackall wrote:
> > 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

2007-12-08 18:17:32

[permalink] [raw]

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

On Sat, Dec 08, 2007 at 12:49:08PM -0500, Theodore Tso wrote:
> On Sat, Dec 08, 2007 at 11:33:57AM -0600, Mike McGrath wrote:
> >> 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.

It might be better for us to just improve the pool initialization.
That'll improve the out of the box experience for everyone.

--
Mathematics is the supreme nostalgia of our time.

2007-12-08 18:25:44

[permalink] [raw]

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

On Sat, Dec 08, 2007 at 12:15:25PM -0600, Matt Mackall wrote:
>
> 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

2007-12-08 18:32:18

[permalink] [raw]

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

Theodore Tso wrote:
> On Sat, Dec 08, 2007 at 11:33:57AM -0600, Mike McGrath wrote:
>>> 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

2007-12-08 19:37:29

[permalink] [raw]

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

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

2007-12-08 19:56:26

[permalink] [raw]

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

2007-12-08 20:05:45

[permalink] [raw]

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

Matt Mackall wrote:
> On Sat, Dec 08, 2007 at 02:36:33PM -0500, Jeff Garzik wrote:
>> 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

2007-12-08 20:24:20

[permalink] [raw]

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

On Sat, Dec 08, 2007 at 03:04:32PM -0500, Jeff Garzik wrote:
> Matt Mackall wrote:
> >On Sat, Dec 08, 2007 at 02:36:33PM -0500, Jeff Garzik wrote:
> >>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.

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.

2007-12-08 20:27:27

by David Schwartz

[permalink] [raw]

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

> 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

2007-12-08 20:32:34

[permalink] [raw]

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

On Sat, Dec 08, 2007 at 03:04:32PM -0500, Jeff Garzik wrote:
> 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.

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

2007-12-08 20:44:51

by Willy Tarreau

[permalink] [raw]

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

On Sat, Dec 08, 2007 at 02:36:33PM -0500, Jeff Garzik wrote:
>
> 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.

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

2007-12-08 20:48:52

[permalink] [raw]

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

Theodore Tso wrote:
> 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.

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

2007-12-08 21:10:41

by Willy Tarreau

[permalink] [raw]

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

On Sat, Dec 08, 2007 at 02:19:54PM -0600, Matt Mackall wrote:
> On Sat, Dec 08, 2007 at 03:04:32PM -0500, Jeff Garzik wrote:
> > Matt Mackall wrote:
> > >On Sat, Dec 08, 2007 at 02:36:33PM -0500, Jeff Garzik wrote:
> > >>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.
>
> 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

2007-12-08 22:03:54

by Adrian Bunk

[permalink] [raw]

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

On Thu, Dec 06, 2007 at 02:32:05PM -0500, Bill Davidsen wrote:
>...
> 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

--

"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

2007-12-08 22:09:19

by Ismail Dönmez

[permalink] [raw]

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

Sunday 09 December 2007 00:03:45 tarihinde Adrian Bunk şunları yazmıştı:
> On Thu, Dec 06, 2007 at 02:32:05PM -0500, Bill Davidsen wrote:
> >...
> > 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.

--
Never learn by your mistakes, if you do you may never dare to try again.

2007-12-08 23:46:50

[permalink] [raw]

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

On Sun, Dec 09, 2007 at 12:10:10AM +0200, Ismail D?nmez wrote:
> > 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

2007-12-08 23:48:27

[permalink] [raw]

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

On Sat, Dec 08, 2007 at 09:42:39PM +0100, Willy Tarreau wrote:
> 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

2007-12-09 01:09:20

[permalink] [raw]

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

On Sat, 2007-12-08 at 18:47 -0500, Theodore Tso wrote:
> On Sat, Dec 08, 2007 at 09:42:39PM +0100, Willy Tarreau wrote:
> > 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.

2007-12-09 05:22:59

by Willy Tarreau

[permalink] [raw]

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

On Sat, Dec 08, 2007 at 06:46:12PM -0500, Theodore Tso wrote:
> On Sun, Dec 09, 2007 at 12:10:10AM +0200, Ismail D?nmez wrote:
> > > 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.

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

2007-12-09 06:20:25

by Ismail Dönmez

[permalink] [raw]

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

Sunday 09 December 2007 01:46:12 tarihinde Theodore Tso şunları yazmıştı:
> On Sun, Dec 09, 2007 at 12:10:10AM +0200, Ismail Dönmez wrote:
> > > 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.

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

--
Never learn by your mistakes, if you do you may never dare to try again.

2007-12-09 06:55:13

[permalink] [raw]

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

On Sun, 2007-12-09 at 06:21 +0100, Willy Tarreau wrote:

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

2007-12-09 12:32:25

[permalink] [raw]

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

On Sun, Dec 09, 2007 at 08:21:16AM +0200, Ismail D?nmez wrote:
> 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

2007-12-09 12:42:34

[permalink] [raw]

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

On Wed, Dec 05, 2007 at 03:26:47PM -0600, Matt Mackall wrote:
> 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

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

2007-12-09 14:05:52

by Ismail Dönmez

[permalink] [raw]

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

Sunday 09 December 2007 14:31:47 tarihinde Theodore Tso şunları yazmıştı:
> On Sun, Dec 09, 2007 at 08:21:16AM +0200, Ismail Dönmez wrote:
> > 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.

Thats very good news, thanks for the detailed explanation. Time to update
common misconceptions.

Regards,
ismail

--
Never learn by your mistakes, if you do you may never dare to try again.

2007-12-09 16:17:56

[permalink] [raw]

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

On Sun, Dec 09, 2007 at 01:42:00PM +0100, Marc Haber wrote:
> On Wed, Dec 05, 2007 at 03:26:47PM -0600, Matt Mackall wrote:
> > 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.

--
Mathematics is the supreme nostalgia of our time.

2007-12-10 23:07:25

[permalink] [raw]

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

On Sun, Dec 09, 2007 at 10:16:05AM -0600, Matt Mackall wrote:
> On Sun, Dec 09, 2007 at 01:42:00PM +0100, Marc Haber wrote:
> > On Wed, Dec 05, 2007 at 03:26:47PM -0600, Matt Mackall wrote:
> > > 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

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

2007-12-10 23:37:32

[permalink] [raw]

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

On Tue, Dec 11, 2007 at 12:06:43AM +0100, Marc Haber wrote:
> On Sun, Dec 09, 2007 at 10:16:05AM -0600, Matt Mackall wrote:
> > On Sun, Dec 09, 2007 at 01:42:00PM +0100, Marc Haber wrote:
> > > On Wed, Dec 05, 2007 at 03:26:47PM -0600, Matt Mackall wrote:
> > > > 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.

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

--
Mathematics is the supreme nostalgia of our time.

2007-12-11 01:35:25

[permalink] [raw]

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

On Mon, Dec 10, 2007 at 05:35:25PM -0600, Matt Mackall wrote:
> > 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

2007-12-11 13:58:36

by Pavel Machek

[permalink] [raw]

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

On Wed 2007-12-05 09:49:34, Theodore Tso wrote:
> On Wed, Dec 05, 2007 at 08:26:19AM -0600, Mike McGrath wrote:
> >
> > 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.

--
(english) http://www.livejournal.com/~pavelmachek
(cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html

2007-12-11 15:25:26

by Bill Davidsen

[permalink] [raw]

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

Adrian Bunk wrote:
> On Thu, Dec 06, 2007 at 02:32:05PM -0500, Bill Davidsen wrote:
>
>> ...
>> 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.

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

2007-12-11 19:46:49

by Phillip Susi

[permalink] [raw]

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

Theodore Tso wrote:
> 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?

2007-12-11 20:09:18

by Ray Lee

[permalink] [raw]

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

On Dec 11, 2007 11:46 AM, Phillip Susi <[email protected]> wrote:
> Theodore Tso wrote:
> > 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.

2007-12-12 05:35:32

by David Schwartz

[permalink] [raw]

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

Phillip Susi wrote:

> 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

2007-12-20 22:27:53