/dev/random on Linux

/dev/random on Linux

[Jonathan Day]

Hi,

For the three people who don't monitor the security
websites, there are claims that Linux' random number
generator has problems that could potentially be
exploited by an attacker to compromise encryption
algorithms, etc.

http://www.securiteam.com/unixfocus/5RP0E0AIKK.html

(Just because something is claimed does not make it
so, but it's usually worth checking.)

I know there have been patches around for ages to
improve the entropy of the random number generator,
but how active is work on this section of the code?


__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
http://mail.yahoo.com 

Re: /dev/random on Linux

[Alan Cox]

On Llu, 2006-05-15 at 14:39 -0700, Jonathan Day wrote:
> http://www.securiteam.com/unixfocus/5RP0E0AIKK.html
> 
> (Just because something is claimed does not make it
> so, but it's usually worth checking.)

"Holes in the Linux Random Number Generator"

[I would cc the authors but they seem to have forgotten to include their
email addresses. I've cc'd the IEEE instead, especially as the paper
gets a trademark incorrect and that wants fixing before printing.]

Indeed. 

A paper by people who can't work out how to mail linux-kernel or
vendor-sec, or follow "REPORTING-BUGS" in the source, and think the
person found in a file called MAINTAINERS is in fact a "moderator"
doesn't initial inspire confidence. The also got the "Red Hat" name
wrong. It is "Red Hat" and it is a registered trademark.

Certainly there are lot of errors in the background but then their
expertise appears to be random numbers and that part of the material
looks much more solid.

> I know there have been patches around for ages to
> improve the entropy of the random number generator,
> but how active is work on this section of the code?

Going through the claims

I would dismiss 2.2 for the cases of things like Knoppix because CDs
introduce significant randomness because each time you boot the CD is
subtly differently positioned. The OpenWRT case seems more credible. The
hard disk patching one is basically irrelevant, at that point you
already own the box and its game over since you can just do a
virtualisation attack or patch the OS to record anything you want.

2.3 Collecting Entropy

Appears to misdescribe the behaviour of get_random_bytes. The authors
description is incorrect. The case where cycle times are not available
is processors lacking TSC support (pre pentium). This is of course more
relevant for some embedded platforms which do lack cycle times and thus
show the behaviour described. There are some platforms that therefore
show the properties they are commenting on so it is still a relevant
discussion in those cases.

3.4 Security Engineering

The denial of service when no true entropy exists is intentional and
long discussed. User consumption of entropy can be controlled by
conventional file permissions, acls and SELinux already, or by a policy
daemon or combinations thereof. It is clearly better to refuse to give
out entropy to people than to give false entropy.

Unix/Linux philosophy is "policy belongs outside the kernel", therefore
a daemon is the correct implementation if required. The paper perhaps
makes an interesting case for this.


Generally

The random number mathematics involved is not for me to comment on,
several of the points raised are certainly good, and I will forward the
paper URL on to vendor-sec to ensure other relevant folk see it.

Thanks for forwarding it.

Alan

Re: /dev/random on Linux

[Muli Ben-Yehuda]

On Mon, May 15, 2006 at 11:41:07PM +0100, Alan Cox wrote:
> On Llu, 2006-05-15 at 14:39 -0700, Jonathan Day wrote:
> > http://www.securiteam.com/unixfocus/5RP0E0AIKK.html
> > 
> > (Just because something is claimed does not make it
> > so, but it's usually worth checking.)
> 
> "Holes in the Linux Random Number Generator"
> 
> [I would cc the authors but they seem to have forgotten to include their
> email addresses. I've cc'd the IEEE instead, especially as the paper
> gets a trademark incorrect and that wants fixing before printing.]

Zvi Gutterman CC'd.

> Indeed. 
> 
> A paper by people who can't work out how to mail linux-kernel or
> vendor-sec, or follow "REPORTING-BUGS" in the source,

Zvi did contact Matt Mackall, the current /dev/random maintainer, and
was very keen on discussing the paper with him. I don't think he got
any response.

> and think the
> person found in a file called MAINTAINERS is in fact a "moderator"
> doesn't initial inspire confidence.

I wouldn't read much (or anything) into that thinko.

[not trimming the rest for Zvi's benefit]

> The also got the "Red Hat" name
> wrong. It is "Red Hat" and it is a registered trademark.
> 
> Certainly there are lot of errors in the background but then their
> expertise appears to be random numbers and that part of the material
> looks much more solid.
> 
> > I know there have been patches around for ages to
> > improve the entropy of the random number generator,
> > but how active is work on this section of the code?
> 
> Going through the claims
> 
> I would dismiss 2.2 for the cases of things like Knoppix because CDs
> introduce significant randomness because each time you boot the CD is
> subtly differently positioned. The OpenWRT case seems more credible. The
> hard disk patching one is basically irrelevant, at that point you
> already own the box and its game over since you can just do a
> virtualisation attack or patch the OS to record anything you want.
> 
> 2.3 Collecting Entropy
> 
> Appears to misdescribe the behaviour of get_random_bytes. The authors
> description is incorrect. The case where cycle times are not available
> is processors lacking TSC support (pre pentium). This is of course more
> relevant for some embedded platforms which do lack cycle times and thus
> show the behaviour described. There are some platforms that therefore
> show the properties they are commenting on so it is still a relevant
> discussion in those cases.
> 
> 3.4 Security Engineering
> 
> The denial of service when no true entropy exists is intentional and
> long discussed. User consumption of entropy can be controlled by
> conventional file permissions, acls and SELinux already, or by a policy
> daemon or combinations thereof. It is clearly better to refuse to give
> out entropy to people than to give false entropy.
> 
> Unix/Linux philosophy is "policy belongs outside the kernel", therefore
> a daemon is the correct implementation if required. The paper perhaps
> makes an interesting case for this.
> 
> 
> Generally
> 
> The random number mathematics involved is not for me to comment on,
> several of the points raised are certainly good, and I will forward the
> paper URL on to vendor-sec to ensure other relevant folk see it.
> 
> Thanks for forwarding it.
> 
> Alan
> 
> -
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/

Re: /dev/random on Linux

[Kyle Moffett]

On May 15, 2006, at 22:50, Muli Ben-Yehuda wrote:
> On Mon, May 15, 2006 at 11:41:07PM +0100, Alan Cox wrote:
>> A paper by people who can't work out how to mail linux-kernel or  
>> vendor-sec, or follow "REPORTING-BUGS" in the source,
>
> Zvi did contact Matt Mackall, the current /dev/random maintainer,  
> and was very keen on discussing the paper with him. I don't think  
> he got any response.

So he's demanding that one person spend time responding to his  
paper?  The "maintainer" for any given piece of the kernel is the  
entry in MAINTAINERS *and* linux-kernel@vger.kernel.org *and* the  
appropriate sub-mailing-list.  If you want a quick response, it's  
typically correct to CC all 2 or 3, although that certainly doesn't  
guarantee one if people find your emails rude or unhelpful.

>>> I know there have been patches around for ages to improve the  
>>> entropy of the random number generator, but how active is work on  
>>> this section of the code?
>>
>> Going through the claims
>>
>> I would dismiss 2.2 for the cases of things like Knoppix because  
>> CDs introduce significant randomness because each time you boot  
>> the CD is subtly differently positioned. The OpenWRT case seems  
>> more credible. The hard disk patching one is basically irrelevant,  
>> at that point you already own the box and its game over since you  
>> can just do a virtualization attack or patch the OS to record  
>> anything you want.

Any system with a cycle counter has a vast amount of entropy  
available by the time the system even gets through the BIOS.  Various  
things like memory timing, power initialization, BIOS tests, etc are  
all sufficiently variable in terms of CPU clock cycles that the value  
of the cycle counter at the first bootloader instruction executed has  
several bits of randomness.  By the time the bootloader has  
optionally waited for user input and loaded the kernel off the disk,  
chaotic variability in the disk access for HDDs, CDROMs, etc will  
make many bits of the cycle counter sufficiently random.  At that  
point there's a decently random seed, especially once you start  
getting further-randomized cycle-counter-based disk interrupts.  I  
believe there was a paper that discussed how air turbulence in a disk  
drive was sufficient on a several hundered MHz CPU to provide lots of  
entropy per interrupt from the cycle counter alone.

This is totally untrue for an embedded flash-based system; but for  
such a system the only way to get any kind of entropy at all is with  
a hardware RNG anyways, so I don't really see this as being a problem.

I was unsure about the purported forward-security-breakage claims  
because I don't know how to validate those, but I seem to recall  
(from personal knowledge and the paper) that the kernel does an SHA1  
hash of the contents of the pool and the current cycle-counter when  
reading, uses that as input for the next pool state and returns it  
as /dev/random output.  Since the exact cycle-counter value is never  
exposed outside the kernel and only a small window of the previous  
pool state is exposed, I don't see how you could compute an SHA1  
preimage that would reveal a significant portion of the previous  
pool's state, especially given that the best known attack against  
SHA1 is an extremely hard first-preimage attack which only gets a  
single possible preimage, not the set of all possible preimages as  
required to break the kernel algorithm.

>> 2.3 Collecting Entropy
>>
>> Appears to misdescribe the behaviour of get_random_bytes. The  
>> authors description is incorrect. The case where cycle times are  
>> not available is processors lacking TSC support (pre pentium).  
>> This is of course more relevant for some embedded platforms which  
>> do lack cycle times and thus show the behaviour described. There  
>> are some platforms that therefore show the properties they are  
>> commenting on so it is still a relevant discussion in those cases.

Agreed.  I talked to this some above.

>> 3.4 Security Engineering
>>
>> The denial of service when no true entropy exists is intentional  
>> and long discussed. User consumption of entropy can be controlled  
>> by conventional file permissions, acls and SELinux already, or by  
>> a policy daemon or combinations thereof. It is clearly better to  
>> refuse to give out entropy to people than to give false entropy.

Agreed.  If you really want to secure random-number-generation from  
userspace, make a userspace daemon that opens a /dev/user_random  
socket and uses a private root-only /dev/random device.  Then  
implement user quotas and such on the socket; requiring credential- 
passing or whatever other security mechanism you require.  Then you  
can even have the daemon read from /dev/hwrng and from user data  
sources and verify the randomness of the input data before sending it  
to the kernel.  None of that is the kernel's business and could be  
more securely and efficiently done in userspace.

Likewise the talk in the paper about shipping a daemon with the  
kernel is bogus; people will use whatever daemons they want to.  If  
it really matters for your system and the kernel doesn't provide a  
good enough interrupt-based RNG, then you should use one of the many  
available RNG daemons (or write your own) based on your exact  
requirements.

Cheers,
Kyle Moffett

--
Somone asked me why I work on this free (http://www.fsf.org/ 
philosophy/) software stuff and not get a real job. Charles Schulz  
had the best answer:

"Why do musicians compose symphonies and poets write poems? They do  
it because life wouldn't have any meaning for them if they didn't.  
That's why I draw cartoons. It's my life."
   -- Charles Schulz

Re: /dev/random on Linux

[Muli Ben-Yehuda]

On Tue, May 16, 2006 at 04:15:19AM -0400, Kyle Moffett wrote:
> On May 15, 2006, at 22:50, Muli Ben-Yehuda wrote:
> >On Mon, May 15, 2006 at 11:41:07PM +0100, Alan Cox wrote:
> >>A paper by people who can't work out how to mail linux-kernel or  
> >>vendor-sec, or follow "REPORTING-BUGS" in the source,
> >
> >Zvi did contact Matt Mackall, the current /dev/random maintainer,  
> >and was very keen on discussing the paper with him. I don't think  
> >he got any response.
> 
> So he's demanding that one person spend time responding to his  
> paper? 

Who said anything about demanding? he wanted to discuss the paper. He
received no response (AFAIK). Please don't read more into it.

> The "maintainer" for any given piece of the kernel is the  
> entry in MAINTAINERS *and* linux-kernel@vger.kernel.org *and* the  
> appropriate sub-mailing-list.

For security related information, it is sometimes best not to tell the
whole world about it immediately (although you should definitely tell
the whole world about it eventually). It should've probably been
posted to lkml when mpm didn't respond, I agree. I'll take the blame
for not suggesting that to Zvi.

Cheers,
Muli

Re: /dev/random on Linux

[Kyle Moffett]

On May 16, 2006, at 04:28, Muli Ben-Yehuda wrote:
> On Tue, May 16, 2006 at 04:15:19AM -0400, Kyle Moffett wrote:
>> On May 15, 2006, at 22:50, Muli Ben-Yehuda wrote:
>>> On Mon, May 15, 2006 at 11:41:07PM +0100, Alan Cox wrote:
>>>> A paper by people who can't work out how to mail linux-kernel or  
>>>> vendor-sec, or follow "REPORTING-BUGS" in the source,
>>>
>>> Zvi did contact Matt Mackall, the current /dev/random maintainer,  
>>> and was very keen on discussing the paper with him. I don't think  
>>> he got any response.
>>
>> So he's demanding that one person spend time responding to his paper?
>
> Who said anything about demanding? he wanted to discuss the paper.  
> He received no response (AFAIK). Please don't read more into it.

Pardon; my wording was overly harsh, but I still want to point out  
that assuming an unresponsive MAINTAINERS entry indicates that the  
person doesn't care is totally wrong.  Given the volume of email a  
lot of these people receive, it's very easy for it to go unnoticed or  
be trapped by a spam filter.  Publishing to the LKML is virtually  
always OK; even if you have a security problem, the average  
turnaround for "critical" security fixes like theoretical local root  
exploits is around 24 hours or so.  We went through about 8 stable  
"releases" over the course of a little more than a week because of  
several fairly urgent security fixes during that time.

>> The "maintainer" for any given piece of the kernel is the entry in  
>> MAINTAINERS *and* linux-kernel@vger.kernel.org *and* the  
>> appropriate sub-mailing-list.
>
> For security related information, it is sometimes best not to tell  
> the whole world about it immediately (although you should  
> definitely tell the whole world about it eventually). It should've  
> probably been posted to lkml when mpm didn't respond, I agree. I'll  
> take the blame for not suggesting that to Zvi.

As I said above, even the LKML is probably ok if you think you've  
found an actual explot.  If you really feel nervous about exposing  
it, I believe there's a security@kernel.org email where you can send  
such information which will even tenatively agree to a coordinated  
disclosure if you can prove that it's an urgent security problem.

Cheers,
Kyle Moffett

--
Premature optimization is the root of all evil in programming
   -- C.A.R. Hoare

RE: /dev/random on Linux

[Zvi Gutterman]

Hello All,

I did not get any answer from Matt and was sure that it was of no interest.
This was my mistake, sorry for not sending it earlier to more people.
 
I will be very happy to discuss any aspect of the paper and we do suggest
ways we think can improve the /dev/random security (a very simple issue for
example is implementing quotas on the consumption of random numbers)

Thanks,

Zvi
 

-----Original Message-----
From: Muli Ben-Yehuda [mailto:muli@il.ibm.com] 
Sent: Tuesday, May 16, 2006 11:29 AM
To: Kyle Moffett
Cc: Alan Cox; Jonathan Day; linux-kernel@vger.kernel.org; Zvika Gutterman
Subject: Re: /dev/random on Linux

On Tue, May 16, 2006 at 04:15:19AM -0400, Kyle Moffett wrote:
> On May 15, 2006, at 22:50, Muli Ben-Yehuda wrote:
> >On Mon, May 15, 2006 at 11:41:07PM +0100, Alan Cox wrote:
> >>A paper by people who can't work out how to mail linux-kernel or  
> >>vendor-sec, or follow "REPORTING-BUGS" in the source,
> >
> >Zvi did contact Matt Mackall, the current /dev/random maintainer,  
> >and was very keen on discussing the paper with him. I don't think  
> >he got any response.
> 
> So he's demanding that one person spend time responding to his  
> paper? 

Who said anything about demanding? he wanted to discuss the paper. He
received no response (AFAIK). Please don't read more into it.

> The "maintainer" for any given piece of the kernel is the  
> entry in MAINTAINERS *and* linux-kernel@vger.kernel.org *and* the  
> appropriate sub-mailing-list.

For security related information, it is sometimes best not to tell the
whole world about it immediately (although you should definitely tell
the whole world about it eventually). It should've probably been
posted to lkml when mpm didn't respond, I agree. I'll take the blame
for not suggesting that to Zvi.

Cheers,
Muli

Re: /dev/random on Linux

[Theodore Tso]

On Tue, May 16, 2006 at 04:54:00PM +0300, Zvi Gutterman wrote:
> 
> I did not get any answer from Matt and was sure that it was of no interest.
> This was my mistake, sorry for not sending it earlier to more people.

Note that Matt toke over maintainance from me, but I was the original
designer of most of the /dev/random algorithms (with much help from
Colin Plumb).  I haven't had time to do a full analysis of the paper,
but let me give a couple comments to set the context.

First of all, the Linux /dev/random generator has been around for a
long time; I did the original implementation back in 1994, back when
the crypto iron curtain was still being maintained by the US
Government.  (As far as I know, the Linux /dev/random driver was the
first OS-based RNG and predates efforts present in other systems such
as OpenBSD, et. al.  Not being an academic trying to get tenure, I
never bothered to write a paper back in '94, so I guess that means I
don't get any credit, which is probably fair if you're playing the
academic game.  Publish or perish, after all.  :-)  In any case,
because of the U.S.  export controls on cryptographic algorithms at
that time, in particular anything relating to encryption algorithms, I
chose to use cryptogaphic hashes as its primary non-linear component,
since these were not problematic from an export control perspective.

In addition, the design philosophy is somewhat different from what has
been considered the general wisdom at least in academic circles.
First of all, as noted above, export controls were a major issue.  In
addition, in that time period, flaws in MD4 and MD5 were coming to
light, and it was clear that some cryptographic algorithms provided by
the US government (in particular, DSA) were deliberately designed to
prevent their usefulness in anything other than their released context
(i.e., There are many who believe that one of the DSA primary design
criteria was that it could only be used for digital signatures, and
*not* provide encryption functionality).  So one of the key design
criteria was that /dev/random use its cryptographic primitives in ways
that were non-brittle --- that is, even if the primary use of that
cryptographic primitive were compromised (e.g., the recent collision
attacks against SHA-1), the security of the system would not be
compromised.

One of the reasons why I did not choose a construction such as Bruce
Schneier's Yarrow, which encrypts an incrementing counter as its
output stage, is that repeated encryptions of plaintexts that have
differ from each other by a small hamming distance is one of the
things that cryptographers look for when attacking a cipher.  Maybe
modern encryption systems are so good that we don't have to worry
about such things any more (and certainly most academic papers ignore
such engineering considerations), but I like to take a much more
humble attitude towards making such assumptions, since I *know* the
cryptographers at the NSA know more than I do, and underestimating
them or any other state-sponsored cryptoanalytic organization is
generally not a good idea.  In any case, while if AES is perfect, yes,
using a key to encrypt a counter might be probably good enough --- but
I'm not sure I want to make that assumption.

Secondly, attacks that assume that the attacker can obtain the
contents of the pool were not a major consideration, mainly because
practically speaking, if an attacker can obtain the contents of the
internal state of the RNG, the attacker generally has enough
privileges that the entire system has been compromised, meaning that
the system can be rooted to a fare-thee-well --- all future session
keys and data to be encrypted can then be collected, etc.  So attacks
of the form, "assume that the attack gains access to the pool, but has
no other illicit access to the system" are particularly practical in
the real world, and are mostly of concern to academics.

This is particularly tree of the criteria put forward by the designers
of the Yarrow RNG, where they were concerned about how quickly the RNG
could recover after the pool state got compromised.  My argument was
always that if an attacker had enough privileges to compromise the
internal state of the RNG, in the real world, recovery would require
re-installing from trusted media.

The desire for forward security is different, admittedly; here the
concern is that if the system has already been compromised, you don't
want to make it easy the attacker to find previously generated session
keys or even long-term keys.  However, it should be noted that it
takes O(2**64) operations to go back a single turn of the crank--- but
that only helps you get the last 10 bytes (80 bits) that were last
generated.  In order to get the next 80 bits, you have to do another
O(2**64) amount of work, and sooner or later (within 18 turns of the
crank, best case) you will run into one of the "unlucky" indexes where
it will take you at least O(2**96) of work effort.  To put this in
perspective, generating a 1024 bit RSA key will require approximately
14 turns of the crank, so if you are lucky with the positioning of the
index *and* you penetrate the machine and capture the state of the
pool (which as I mentioned, probably means you've rooted the box and
the system will probably have to be reinstalled from trusted media
anyway), *and* a 1024-bit RSA key had just been generated, you would
be able to determine that 1024-bit RSA key with a work factor of
approximately O(2**68) if you are lucky (probability 1 in 8), and
O(2**96) if you are not.  Should we try do better, sure, but this is
not the sort of thing where you have to keep a secret and only talk to
the official maintainer about it.

I would also note that one of the things Matt did after he took over
maintainership from me is that he took out a call to
add_timer_randomness() from the extract entropy code.  This bit of
code would have also significantly complicated practical attacks on
backtracking attacks, since it mixes in the TSC cycle counter at the
time of the entropy extraction into the pool.  So even if you capture
the state of the pool, unless you know exactly *when* each of the
various entropy extractions took place, you wouldn't be able to easily
calculate the various candidate pools.

More critically, the paper is seriously flawed in its analysis of
reversing the primary pool.  The only reason why the generic attack
takes only 2**96 when the secondary and urandom pools are only 32
words long, is that the entropy extraction routine is only calls
add_entropy_words ceil(n/32)+1 times.  However, the primary entropy
pool is 128 words long, which means that add_entropy_words() is called
9 times.  The paper recognizes this in Appendix B, which shows that j,
j-1, j-2, ... j-8 is modiified when extracting entropy from the
primary pool.  This makes the generic attack take work factor
O(2**288), and the optimized attack also has to be seriously reworked
before it can be carried out on the primary pool.  This also points
out that the simple expedient of doubling the size of the secondary
and urandom pool would effectively eliminate the practicality of
carrying out an forward attack.

In section 3.4, a comment is made about guessable passwords to seed
the entropy pool, and a recommendation was made to remove the value of
the keyboard from the input to the pool.  I would reject that
recommendation, since the entropy estimated is calulated based only on
the timing of the key, and the inter-key timing values is mixed into
*in* *addition* *to* the value of the keys typed.  If the user types a
known or guessable password, the yes, the value of what is typed is no
help in adding entropy to the pool --- but it doesn't hurt, either.  I
have no argument with the observation that main source of entropy
added is the inter-key arrival time, and even there we are extremely
conservative on estimating the amount of entropy found since obviously
the "fist" of a typist could be analyzed and used to provide some
information about inter-key arrival times, particularly if a
high-resolution time source is not available.

Speaking generally about usage scenarios such as the OpenWRT Linux
distribution, if there is no hard disk and relatively little user
input, the amount of entropy that can be gathered will suffer.  That
however isn't the fault of the /dev/random driver, but how it is put
to use.  One of the things which I would strongly recommend to
security applications, such as those found in the OpenWRT Linux
distribution, is to calculate the cryptographic hash of data which is
to be sent out encrypted, and write that into /dev/random, thus mixing
that hash into the entropy pool.  This will not provide any entropy
credits (since at least one entity would have knowledge of the value
of the hash).  However, to attackers that do *not* have access to the
plaintext of the encrypted communications sent out by the application,
this unknown data will significantly complicate the life of attackers
attempting to analyze the state of the random number generator.  In
the absence of hard drive-generated entropy or human-generated timing
data from a keyboard or pointing device, it's certainly better than
nothing, and in practice is quite effective.

All of this being said, I think the paper does make a number of good
points, and I would recommend making the following changes to Linux's
/dev/random:

1) Restore the add_timer_randomess() call to the entropy extraction
function.  This prevents the forward security attack unless the
attacker can know the exact time when each of the entropy extractions
took place, which in general is going to be quite impractical.

2) Double the size of the secondary and urandom pools from 128 to 256
bytes.

3) Investigate the possibility of adding quotas to /dev/random.  This
is actually much more trickier that the paper suggests, since you want
to allow the user to be able to extract enough entropy to create a
2048 bit (or at least a 1024-bit) RSA key.  The problem is that's a
lot of entropy!  Maybe it would be OK to only allow a 1024-bit RSA key
to be generated every 12 or 24 hours, but suppose someone is
experimenting with GPG and screws up (say they forget their
passphrase); do you tell them that sorry, you can't generating another
key until tomorrow?  So now we have to have an interface so the root
user can reset the user's entropy quota....  And even with a 24-hour
limit, on a diskless system, you don't get a lot of entropy, so even a
1024-bit RSA key could seriously deplete your supply of entropy.   

This last point is a good example of the concerns one faces when
trying to design a working system in the real word, as opposed to the
concerns of academicians, where the presence or lack of forward
security in the event of a pool compromise is issue of massive urgency
and oh-my-goodness-we-can-only-tell-the-maintainer-because-it's-such-a-
critical-security-hole attitude.  Where as my attitude is, "yeah, we
should fix it, but I doubt anyone has actually been harmed by this in
real life", which puts it in a different category than a buffer
overrun attack which is accessible from a publically available network 
service.

						- Ted

Re: /dev/random on Linux

[Chase Venters]

On Tue, 16 May 2006, Theodore Tso wrote:
B>
> 3) Investigate the possibility of adding quotas to /dev/random.  This
> is actually much more trickier that the paper suggests, since you want
> to allow the user to be able to extract enough entropy to create a
> 2048 bit (or at least a 1024-bit) RSA key.  The problem is that's a
> lot of entropy!  Maybe it would be OK to only allow a 1024-bit RSA key
> to be generated every 12 or 24 hours, but suppose someone is
> experimenting with GPG and screws up (say they forget their
> passphrase); do you tell them that sorry, you can't generating another
> key until tomorrow?  So now we have to have an interface so the root
> user can reset the user's entropy quota....  And even with a 24-hour
> limit, on a diskless system, you don't get a lot of entropy, so even a
> 1024-bit RSA key could seriously deplete your supply of entropy.

#3 is fine if it's out of the kernel. This isn't just policy - it's 
complicated policy, as you point out quite well.

> This last point is a good example of the concerns one faces when
> trying to design a working system in the real word, as opposed to the
> concerns of academicians, where the presence or lack of forward
> security in the event of a pool compromise is issue of massive urgency
> and oh-my-goodness-we-can-only-tell-the-maintainer-because-it's-such-a-
> critical-security-hole attitude.  Where as my attitude is, "yeah, we
> should fix it, but I doubt anyone has actually been harmed by this in
> real life", which puts it in a different category than a buffer
> overrun attack which is accessible from a publically available network
> service.
>

Slashdot headline about Linux's weak-ass rng should be up shortly, next to 
the news post discussing what Linus had for breakfast this morning.

> 						- Ted

Thanks,
Chase

Re: /dev/random on Linux

[Theodore Tso]

Upon re-reading my response, I found a number of typo's that may have
obscured the meaning of my message:

On Tue, May 16, 2006 at 04:17:49PM -0400, Theodore Tso wrote:
> On Tue, May 16, 2006 at 04:54:00PM +0300, Zvi Gutterman wrote:
> > 
> > I did not get any answer from Matt and was sure that it was of no interest.
> > This was my mistake, sorry for not sending it earlier to more people.
> 
> Note that Matt toke over maintainance from me, but I was the original
> designer of most of the /dev/random algorithms (with much help from
> Colin Plumb).  I haven't had time to do a full analysis of the paper,
> but let me give a couple comments to set the context.
> 
> First of all, the Linux /dev/random generator has been around for a
> long time; I did the original implementation back in 1994, back when
> the crypto iron curtain was still being maintained by the US
> Government.  (As far as I know, the Linux /dev/random driver was the
> first OS-based RNG and predates efforts present in other systems such
> as OpenBSD, et. al.  Not being an academic trying to get tenure, I
> never bothered to write a paper back in '94, so I guess that means I
> don't get any credit, which is probably fair if you're playing the
> academic game.  Publish or perish, after all.  :-)  In any case,
> because of the U.S.  export controls on cryptographic algorithms at
> that time, in particular anything relating to encryption algorithms, I
> chose to use cryptogaphic hashes as its primary non-linear component,
> since these were not problematic from an export control perspective.
> 
> In addition, the design philosophy is somewhat different from what has
> been considered the general wisdom at least in academic circles.
> First of all, as noted above, export controls were a major issue.  In
> addition, in that time period, flaws in MD4 and MD5 were coming to
> light, and it was clear that some cryptographic algorithms provided by
> the US government (in particular, DSA) were deliberately designed to
> prevent their usefulness in anything other than their released context
> (i.e., There are many who believe that one of the DSA primary design
> criteria was that it could only be used for digital signatures, and
> *not* provide encryption functionality).  So one of the key design
> criteria was that /dev/random use its cryptographic primitives in ways
> that were non-brittle --- that is, even if the primary use of that
> cryptographic primitive were compromised (e.g., the recent collision
> attacks against SHA-1), the security of the system would not be
> compromised.
> 
> One of the reasons why I did not choose a construction such as Bruce
> Schneier's Yarrow, which encrypts an incrementing counter as its
> output stage, is that repeated encryptions of plaintexts that have
> differ from each other by a small hamming distance is one of the
> things that cryptographers look for when attacking a cipher.  Maybe
> modern encryption systems are so good that we don't have to worry
> about such things any more (and certainly most academic papers ignore
> such engineering considerations), but I like to take a much more
> humble attitude towards making such assumptions, since I *know* the
> cryptographers at the NSA know more than I do, and underestimating
> them or any other state-sponsored cryptoanalytic organization is
> generally not a good idea.  In any case, while if AES is perfect, yes,
> using a key to encrypt a counter might be probably good enough --- but
> I'm not sure I want to make that assumption.
> 
> Secondly, attacks that assume that the attacker can obtain the
> contents of the pool were not a major consideration, mainly because
> practically speaking, if an attacker can obtain the contents of the
> internal state of the RNG, the attacker generally has enough
> privileges that the entire system has been compromised, meaning that
> the system can be rooted to a fare-thee-well --- all future session
> keys and data to be encrypted can then be collected, etc.  So attacks
> of the form, "assume that the attack gains access to the pool, but has
> no other illicit access to the system" are particularly practical in
                                         ^^^^^^^^^^^^^^^^
				        are NOT particularly
> the real world, and are mostly of concern to academics.
> 
> This is particularly tree of the criteria put forward by the designers
> of the Yarrow RNG, where they were concerned about how quickly the RNG
> could recover after the pool state got compromised.  My argument was
> always that if an attacker had enough privileges to compromise the
> internal state of the RNG, in the real world, recovery would require
> re-installing from trusted media.
> 
> The desire for forward security is different, admittedly; here the
> concern is that if the system has already been compromised, you don't
> want to make it easy the attacker to find previously generated session
> keys or even long-term keys.  However, it should be noted that it
> takes O(2**64) operations to go back a single turn of the crank--- but
> that only helps you get the last 10 bytes (80 bits) that were last
> generated.  In order to get the next 80 bits, you have to do another
> O(2**64) amount of work, and sooner or later (within 18 turns of the
> crank, best case) you will run into one of the "unlucky" indexes where
> it will take you at least O(2**96) of work effort.  To put this in
> perspective, generating a 1024 bit RSA key will require approximately
> 14 turns of the crank, so if you are lucky with the positioning of the
> index *and* you penetrate the machine and capture the state of the
> pool (which as I mentioned, probably means you've rooted the box and
> the system will probably have to be reinstalled from trusted media
> anyway), *and* a 1024-bit RSA key had just been generated, you would
> be able to determine that 1024-bit RSA key with a work factor of
> approximately O(2**68) if you are lucky (probability 1 in 8), and
> O(2**96) if you are not.  Should we try do better, sure, but this is
> not the sort of thing where you have to keep a secret and only talk to
> the official maintainer about it.
> 
> I would also note that one of the things Matt did after he took over
> maintainership from me is that he took out a call to
> add_timer_randomness() from the extract entropy code.  This bit of
> code would have also significantly complicated practical attacks on
> backtracking attacks, since it mixes in the TSC cycle counter at the
> time of the entropy extraction into the pool.  So even if you capture
> the state of the pool, unless you know exactly *when* each of the
> various entropy extractions took place, you wouldn't be able to easily
> calculate the various candidate pools.
> 
> More critically, the paper is seriously flawed in its analysis of
> reversing the primary pool.  The only reason why the generic attack
> takes only 2**96 when the secondary and urandom pools are only 32
> words long, is that the entropy extraction routine is only calls
> add_entropy_words ceil(n/32)+1 times.  However, the primary entropy
                    ^^^^^^^^^^^^^
                    ceil(n/16)+1 times, where n is the number of words 
	in the pool.
> pool is 128 words long, which means that add_entropy_words() is called
> 9 times.  The paper recognizes this in Appendix B, which shows that j,
> j-1, j-2, ... j-8 is modiified when extracting entropy from the
> primary pool.  This makes the generic attack take work factor
> O(2**288), and the optimized attack also has to be seriously reworked
> before it can be carried out on the primary pool.  This also points
> out that the simple expedient of doubling the size of the secondary
> and urandom pool would effectively eliminate the practicality of
> carrying out an forward attack.
> 
> In section 3.4, a comment is made about guessable passwords to seed
> the entropy pool, and a recommendation was made to remove the value of
> the keyboard from the input to the pool.  I would reject that
> recommendation, since the entropy estimated is calulated based only on
> the timing of the key, and the inter-key timing values is mixed into
> *in* *addition* *to* the value of the keys typed.  If the user types a
> known or guessable password, the yes, the value of what is typed is no
> help in adding entropy to the pool --- but it doesn't hurt, either.  I
> have no argument with the observation that main source of entropy
> added is the inter-key arrival time, and even there we are extremely
> conservative on estimating the amount of entropy found since obviously
> the "fist" of a typist could be analyzed and used to provide some
> information about inter-key arrival times, particularly if a
> high-resolution time source is not available.
> 
> Speaking generally about usage scenarios such as the OpenWRT Linux
> distribution, if there is no hard disk and relatively little user
> input, the amount of entropy that can be gathered will suffer.  That
> however isn't the fault of the /dev/random driver, but how it is put
> to use.  One of the things which I would strongly recommend to
> security applications, such as those found in the OpenWRT Linux
> distribution, is to calculate the cryptographic hash of data which is
> to be sent out encrypted, and write that into /dev/random, thus mixing
> that hash into the entropy pool.  This will not provide any entropy
> credits (since at least one entity would have knowledge of the value
> of the hash).  However, to attackers that do *not* have access to the
> plaintext of the encrypted communications sent out by the application,
> this unknown data will significantly complicate the life of attackers
> attempting to analyze the state of the random number generator.  In
> the absence of hard drive-generated entropy or human-generated timing
> data from a keyboard or pointing device, it's certainly better than
> nothing, and in practice is quite effective.
> 
> All of this being said, I think the paper does make a number of good
> points, and I would recommend making the following changes to Linux's
> /dev/random:
> 
> 1) Restore the add_timer_randomess() call to the entropy extraction
> function.  This prevents the forward security attack unless the
> attacker can know the exact time when each of the entropy extractions
> took place, which in general is going to be quite impractical.
> 
> 2) Double the size of the secondary and urandom pools from 128 to 256
> bytes.
> 
> 3) Investigate the possibility of adding quotas to /dev/random.  This
> is actually much more trickier that the paper suggests, since you want
> to allow the user to be able to extract enough entropy to create a
> 2048 bit (or at least a 1024-bit) RSA key.  The problem is that's a
> lot of entropy!  Maybe it would be OK to only allow a 1024-bit RSA key
> to be generated every 12 or 24 hours, but suppose someone is
> experimenting with GPG and screws up (say they forget their
> passphrase); do you tell them that sorry, you can't generating another
> key until tomorrow?  So now we have to have an interface so the root
> user can reset the user's entropy quota....  And even with a 24-hour
> limit, on a diskless system, you don't get a lot of entropy, so even a
> 1024-bit RSA key could seriously deplete your supply of entropy.   
> 
> This last point is a good example of the concerns one faces when
> trying to design a working system in the real word, as opposed to the
> concerns of academicians, where the presence or lack of forward
> security in the event of a pool compromise is issue of massive urgency
> and oh-my-goodness-we-can-only-tell-the-maintainer-because-it's-such-a-
> critical-security-hole attitude.  Where as my attitude is, "yeah, we
> should fix it, but I doubt anyone has actually been harmed by this in
> real life", which puts it in a different category than a buffer
> overrun attack which is accessible from a publically available network 
> service.
> 
> 						- Ted

Re: /dev/random on Linux

[Alan Cox]

On Maw, 2006-05-16 at 04:15 -0400, Kyle Moffett wrote:
> > Zvi did contact Matt Mackall, the current /dev/random maintainer,  
> > and was very keen on discussing the paper with him. I don't think  
> > he got any response.
> 
> So he's demanding that one person spend time responding to his  
> paper? 

Relying on email to one person getting through is a bit bogus, but I
don't see a single demand from anyone that someone respond to the paper.
I'm very glad the work was done, it would have been nicer to have known
up front but it didn't work out.

Also if the maintainer doesn't respond and the paper authors didn't know
where to go next that in itself needs addressing because the same may be
true for others finding problems.

Don't blame the messenger when it might be useful to think about whether
the MAINTAINERS file could do with an extra paragraph or two...

Alan

Re: /dev/random on Linux

[Pavel Machek]

Hi!

> >>I would dismiss 2.2 for the cases of things like Knoppix because  
> >>CDs introduce significant randomness because each time you boot  
> >>the CD is subtly differently positioned. The OpenWRT case seems  
> >>more credible. The hard disk patching one is basically irrelevant,  
> >>at that point you already own the box and its game over since you  
> >>can just do a virtualization attack or patch the OS to record  
> >>anything you want.
> 
> Any system with a cycle counter has a vast amount of entropy  
> available by the time the system even gets through the BIOS.  Various  
> things like memory timing, power initialization, BIOS tests, etc are  
> all sufficiently variable in terms of CPU clock cycles that the value  
> of the cycle counter at the first bootloader instruction executed has  
> several bits of randomness.  By the time the bootloader has  
> optionally waited for user input and loaded the kernel off the disk,  
> chaotic variability in the disk access for HDDs, CDROMs, etc will  
> make many bits of the cycle counter sufficiently random.  At that  
> point there's a decently random seed, especially once you start  
> getting further-randomized cycle-counter-based disk interrupts.  I  
> believe there was a paper that discussed how air turbulence in a disk  
> drive was sufficient on a several hundered MHz CPU to provide lots of  
> entropy per interrupt from the cycle counter alone.
> 
> This is totally untrue for an embedded flash-based system; but for  
> such a system the only way to get any kind of entropy at all is with  
> a hardware RNG anyways, so I don't really see this as being a problem.
> 
> I was unsure about the purported forward-security-breakage claims  
> because I don't know how to validate those, but I seem to recall  
> (from personal knowledge and the paper) that the kernel does an SHA1  
> hash of the contents of the pool and the current cycle-counter when  
> reading, uses that as input for the next pool state and returns it  
> as /dev/random output.  Since the exact cycle-counter value is never  
> exposed outside the kernel and only a small window of the previous  

Are you sure? For vsyscalls to work, rdtsc has to be available from
userspace, no?
								Pavel
-- 
(english) http://www.livejournal.com/~pavelmachek
(cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html

Re: /dev/random on Linux

[Christopher Friesen]

Pavel Machek wrote:

>>I was unsure about the purported forward-security-breakage claims  
>>because I don't know how to validate those, but I seem to recall  
>>(from personal knowledge and the paper) that the kernel does an SHA1  
>>hash of the contents of the pool and the current cycle-counter when  
>>reading, uses that as input for the next pool state and returns it  
>>as /dev/random output.  Since the exact cycle-counter value is never  
>>exposed outside the kernel and only a small window of the previous  
> 
> 
> Are you sure? For vsyscalls to work, rdtsc has to be available from
> userspace, no?

I suspect he means "the exact cycle counter value at the time of reading 
the contents of the pool" is never exposed outside the kernel.

"rdtsc" is of course available in userspace on x86.

Chris

Re: /dev/random on Linux

[Michael Buesch]

On Tuesday 16 May 2006 10:15, you wrote:
> >> I would dismiss 2.2 for the cases of things like Knoppix because  
> >> CDs introduce significant randomness because each time you boot  
> >> the CD is subtly differently positioned. The OpenWRT case seems  
> >> more credible.

I think most (all?) of the machines, OpenWRT runs on, are running
a bcm43xx wireless chip. This chip has a hardware random number
generator. patches to utilize it recently went into -mm.
But I must admit, we don't know how it generates random numbers.
But someone did some RNG tests on it in the past (I think it was
Johannes).

Re: /dev/random on Linux

[Johannes Berg]

[-- Attachment #1: Type: text/plain, Size: 799 bytes --]

On Tue, 2006-05-16 at 16:58 +0200, Michael Buesch wrote:

> I think most (all?) of the machines, OpenWRT runs on, are running
> a bcm43xx wireless chip. This chip has a hardware random number
> generator. patches to utilize it recently went into -mm.
> But I must admit, we don't know how it generates random numbers.
> But someone did some RNG tests on it in the past (I think it was
> Johannes).

I did, but no predictability tests, only FIPS 140-2 or so. It checked
out pretty well but someone claimed that the RNG was predictable because
it was probably only used for some of the coding for wireless. I don't
know how to test this hypothesis as I don't know enough about QAM and
whatever codings are used there (nor do I know where you'd need
(pseudo-)random numbers)

johannes

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 793 bytes --]