Skip to contentSkip to conversation

/dev/random on Linux

DISCUSSION Jonathan Day 11 participants 15 messages May 15, 2006 – May 17, 2006

lore
Share & tools
lore
#0 lore raw

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

#1 lore raw
Quoted 4 lines · Jonathan Day

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.

Quoted 3 lines

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

#2 lore raw
Quoted 11 lines · Alan Cox
Quoted 4 lines · Jonathan Day

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.

Quoted 4 lines

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.

Quoted 3 lines

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]

Quoted 58 lines

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.

Quoted 3 lines

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 [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

#3 lore raw
Quoted 4 lines · Muli Ben-Yehuda
Quoted 1 line · Alan Cox

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* [email protected] *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.

Quoted 5 lines
Quoted 5 lines
Quoted 1 line

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.

Quoted 3 lines
Quoted 3 lines

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.

Quoted 3 lines
Quoted 3 lines

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

#4 lore raw
Quoted 11 lines · Kyle Moffett
Quoted 7 lines · Muli Ben-Yehuda
Quoted 2 lines · Alan Cox

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.

Quoted 3 lines

The "maintainer" for any given piece of the kernel is the entry in MAINTAINERS *and* [email protected] *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

#5 lore raw
Quoted 10 lines · Muli Ben-Yehuda
Quoted 7 lines · Kyle Moffett
Quoted 4 lines · Muli Ben-Yehuda
Quoted 1 line · Alan Cox

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.

Quoted 3 lines
Quoted 1 line

The "maintainer" for any given piece of the kernel is the entry in MAINTAINERS *and* [email protected] *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 [email protected] 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

#6 lore raw
In reply to Muli Ben-Yehuda

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:[email protected]]
Sent: Tuesday, May 16, 2006 11:29 AM
To: Kyle Moffett
Cc: Alan Cox; Jonathan Day; [email protected]; Zvika Gutterman
Subject: Re: /dev/random on Linux

Quoted 11 lines · Kyle Moffett
Quoted 7 lines · Muli Ben-Yehuda
Quoted 2 lines · Alan Cox

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.

Quoted 3 lines

The "maintainer" for any given piece of the kernel is the entry in MAINTAINERS *and* [email protected] *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

#7 lore raw
Quoted 3 lines · Zvi Gutterman

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

#8 lore raw

On Tue, 16 May 2006, Theodore Tso wrote:
B>

Quoted 4 lines

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

Quoted 8 lines

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.

Quoted 11 lines

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.

Quoted 1 line

- Ted

Thanks,
Chase

#9 lore raw
In reply to Theodore Tso

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

Quoted 55 lines · Theodore Tso
Quoted 3 lines · Zvi Gutterman

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.

Quoted 9 lines

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

Quoted 41 lines

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.

Quoted 5 lines

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.

Quoted 80 lines

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

#10 lore raw
In reply to Kyle Moffett
Quoted 6 lines · Kyle Moffett
Quoted 3 lines

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

#11 lore raw
In reply to Kyle Moffett

Hi!

Quoted 27 lines
Quoted 7 lines
Quoted 7 lines

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.

Quoted 7 lines

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

Signature · 2 lines
(english) http://www.livejournal.com/~pavelmachek
(cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html
#12 lore raw
Quoted 5 lines · Pavel Machek
Quoted 1 line

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

#13 lore raw
In reply to Kyle Moffett
Quoted 4 lines · you
Quoted 4 lines
Quoted 4 lines

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

#14 lore raw
Quoted 6 lines · Michael Buesch

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