* /dev/urandom uses uninit bytes, leaks user data @ 2007-12-14 19:34 John Reiser 2007-12-14 20:13 ` Matt Mackall 0 siblings, 1 reply; 39+ messages in thread From: John Reiser @ 2007-12-14 19:34 UTC (permalink / raw) To: Matt Mackall; +Cc: linux-kernel, security xfer_secondary_pool() in drivers/char/random.c tells add_entropy_words() to use uninitialized tmp[] whenever bytes is not a multiple of 4. Besides being unfriendly to automated dynamic checkers, this is a potential leak of user data into the output stream. When called from extract_entropy_user, then uninit tmp[] can capture leftover data from a previous copy_from_user(). Signed off by: jreiser@BitWagon.com --- ./drivers/char/random.c.orig 2007-12-14 11:06:03.000000000 -0800 +++ ./drivers/char/random.c 2007-12-14 11:06:57.000000000 -0800 @@ -708,7 +708,19 @@ bytes=extract_entropy(r->pull, tmp, bytes, random_read_wakeup_thresh / 8, rsvd); - add_entropy_words(r, tmp, (bytes + 3) / 4); + /* + * 2007-12-13 (valgrind/memcheck) Do not use undefined bytes. + * Avoid info leak when called from extract_entropy_user: + * uninit tmp[] can have data from previous copy_from_user(). + * Instead: fill last word using first bytes. + */ + { + __u8 *src = (__u8 *)&tmp[0]; + __u8 *dst = bytes + src; + for (; 0!=(3 & bytes); ++bytes) + *dst++ = *src++; + } + add_entropy_words(r, tmp, bytes>>2); credit_entropy_store(r, bytes*8); } -- John Reiser, jreiser@BitWagon.com ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: /dev/urandom uses uninit bytes, leaks user data 2007-12-14 19:34 /dev/urandom uses uninit bytes, leaks user data John Reiser @ 2007-12-14 20:13 ` Matt Mackall 2007-12-14 20:45 ` John Reiser 0 siblings, 1 reply; 39+ messages in thread From: Matt Mackall @ 2007-12-14 20:13 UTC (permalink / raw) To: John Reiser; +Cc: linux-kernel, security On Fri, Dec 14, 2007 at 11:34:09AM -0800, John Reiser wrote: > xfer_secondary_pool() in drivers/char/random.c tells add_entropy_words() > to use uninitialized tmp[] whenever bytes is not a multiple of 4. > Besides being unfriendly to automated dynamic checkers, this is a > potential leak of user data into the output stream. When called from > extract_entropy_user, then uninit tmp[] can capture leftover data > from a previous copy_from_user(). Yes, we use uninitialized data. But it's not a leak in any useful sense. To the extent the previous data is secret, this actually improves our entropy. It's getting folded into the random number pool, where it will be impossible to recover it unless you already know what was in the pool. And if you know what's in the pool, you've already broken into the kernel. But I'm sympathetic to making Valgrind happy. > --- ./drivers/char/random.c.orig 2007-12-14 11:06:03.000000000 -0800 > +++ ./drivers/char/random.c 2007-12-14 11:06:57.000000000 -0800 > @@ -708,7 +708,19 @@ > > bytes=extract_entropy(r->pull, tmp, bytes, > random_read_wakeup_thresh / 8, rsvd); > - add_entropy_words(r, tmp, (bytes + 3) / 4); > + /* > + * 2007-12-13 (valgrind/memcheck) Do not use undefined bytes. > + * Avoid info leak when called from extract_entropy_user: > + * uninit tmp[] can have data from previous copy_from_user(). > + * Instead: fill last word using first bytes. > + */ > + { > + __u8 *src = (__u8 *)&tmp[0]; > + __u8 *dst = bytes + src; > + for (; 0!=(3 & bytes); ++bytes) > + *dst++ = *src++; > + } That's hideous. How about a memset instead: /* clear uninitialized bytes at the end to make valgrind happy */ memset((char *)tmp + bytes, 0, -bytes & 3); Also, don't bother putting dates or the like in comments. We've got a version control system for that. > + add_entropy_words(r, tmp, bytes>>2); And that change is broken.. > credit_entropy_store(r, bytes*8); ..because it makes this line wrong. We have to add precisely the number of bytes returned by extract_entropy to keep the books balanced. -- Mathematics is the supreme nostalgia of our time. ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: /dev/urandom uses uninit bytes, leaks user data 2007-12-14 20:13 ` Matt Mackall @ 2007-12-14 20:45 ` John Reiser 2007-12-14 23:23 ` Theodore Tso 0 siblings, 1 reply; 39+ messages in thread From: John Reiser @ 2007-12-14 20:45 UTC (permalink / raw) To: Matt Mackall; +Cc: linux-kernel, security Matt Mackall wrote: > Yes, we use uninitialized data. But it's not a leak in any useful > sense. To the extent the previous data is secret, this actually > improves our entropy. > > It's getting folded into the random number pool, where it will be > impossible to recover it unless you already know what was in the > pool. And if you know what's in the pool, you've already broken into > the kernel. The combination of capturing data from other users, plus seeding the pool with your own data, just might be powerful enough to help steal secrets, sometime in the next five years, from data that is recorded today. > But I'm sympathetic to making Valgrind happy. ... > [The code in John's patch is] hideous. How about a memset instead ... > And [John's] change is broken.. We have to add precisely the > number of bytes returned by extract_entropy to keep the books > balanced. Matt is correct. The rolled-up result follows. Signed off by: jreiser@BitWagon.com --- ./drivers/char/random.c.orig 2007-12-14 11:06:03.000000000 -0800 +++ ./drivers/char/random.c 2007-12-14 12:27:23.000000000 -0800 @@ -708,6 +708,8 @@ bytes=extract_entropy(r->pull, tmp, bytes, random_read_wakeup_thresh / 8, rsvd); + /* clear uninitialized bytes at the end to make valgrind happy */ + memset((char *)tmp + bytes, 0, -bytes & 3); add_entropy_words(r, tmp, (bytes + 3) / 4); credit_entropy_store(r, bytes*8); } -- John Reiser, jreiser@BitWagon.com ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: /dev/urandom uses uninit bytes, leaks user data 2007-12-14 20:45 ` John Reiser @ 2007-12-14 23:23 ` Theodore Tso 2007-12-15 0:30 ` John Reiser 0 siblings, 1 reply; 39+ messages in thread From: Theodore Tso @ 2007-12-14 23:23 UTC (permalink / raw) To: John Reiser; +Cc: Matt Mackall, linux-kernel, security On Fri, Dec 14, 2007 at 12:45:23PM -0800, John Reiser wrote: > > It's getting folded into the random number pool, where it will be > > impossible to recover it unless you already know what was in the > > pool. And if you know what's in the pool, you've already broken into > > the kernel. > > The combination of capturing data from other users, plus seeding > the pool with your own data, just might be powerful enough to help > steal secrets, sometime in the next five years, from data that is > recorded today. Um, no. Just seeding the pool with your own data won't help, since that still won't tell you the initial contents of the pool. And if you know the initial contents of the pool, then you've broken root. And being able to steal from the pool also assumes that you've broken into the system; it is never, ever exported to userspace, even if you're root (unless you use something like /dev/kmem). Furthermore, if you don't know the previous contents of the pool, you'll never be able to recover the information, either now or five years in the future, since information is XOR'ed into the pool. > > But I'm sympathetic to making Valgrind happy. ... How about wrapping it in a #ifdef CONFIG_UML, which is the only way you can use Valgrind? The memset will slow down things unnecessarily, and mixing in the unknown previous contents of the stack (a) doesn't hurt, and (b) could make life more complicated for an attacker. - Ted ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: /dev/urandom uses uninit bytes, leaks user data 2007-12-14 23:23 ` Theodore Tso @ 2007-12-15 0:30 ` John Reiser 2007-12-15 4:32 ` Theodore Tso 2007-12-15 7:13 ` Herbert Xu 0 siblings, 2 replies; 39+ messages in thread From: John Reiser @ 2007-12-15 0:30 UTC (permalink / raw) To: Theodore Tso; +Cc: Matt Mackall, linux-kernel, security Theodore Tso wrote: > On Fri, Dec 14, 2007 at 12:45:23PM -0800, John Reiser wrote: > >>>It's getting folded into the random number pool, where it will be >>>impossible to recover it unless you already know what was in the >>>pool. And if you know what's in the pool, you've already broken into >>>the kernel. >> >>The combination of capturing data from other users, plus seeding >>the pool with your own data, just might be powerful enough to help >>steal secrets, sometime in the next five years, from data that is >>recorded today. > > > Um, no. Just seeding the pool with your own data won't help, since > that still won't tell you the initial contents of the pool. And if > you know the initial contents of the pool, then you've broken root. > And being able to steal from the pool also assumes that you've broken > into the system; it is never, ever exported to userspace, even if > you're root (unless you use something like /dev/kmem). Furthermore, > if you don't know the previous contents of the pool, you'll never be > able to recover the information, either now or five years in the > future, since information is XOR'ed into the pool. There is a path that goes from user data into the pool. This path is subject to manipulation by an attacker, for both reading and writing. Are you going to guarantee that in five years nobody will discover a way to take advantage of it? Five years ago there were no public attacks against MD5 except brute force; now MD5 is on the "weak" list. >>>But I'm sympathetic to making Valgrind happy. ... > > > How about wrapping it in a #ifdef CONFIG_UML, which is the only way > you can use Valgrind? The memset will slow down things unnecessarily, > and mixing in the unknown previous contents of the stack (a) doesn't > hurt, and (b) could make life more complicated for an attacker. If speed matters that much, then please recoup 33 cycles on x86 by using shifts instead of three divides, such as (gcc 4.1.2): add_entropy_words(r, tmp, (bytes + 3) / 4); 0x8140689 <xfer_secondary_pool+206>: lea 0x3(%esi),%eax 0x814068c <xfer_secondary_pool+209>: mov $0x4,%dl 0x814068e <xfer_secondary_pool+211>: mov %edx,%edi 0x8140690 <xfer_secondary_pool+213>: cltd 0x8140691 <xfer_secondary_pool+214>: idiv %edi -- John Reiser, jreiser@BitWagon.com ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: /dev/urandom uses uninit bytes, leaks user data 2007-12-15 0:30 ` John Reiser @ 2007-12-15 4:32 ` Theodore Tso 2007-12-17 16:30 ` John Reiser 2007-12-15 7:13 ` Herbert Xu 1 sibling, 1 reply; 39+ messages in thread From: Theodore Tso @ 2007-12-15 4:32 UTC (permalink / raw) To: John Reiser; +Cc: Matt Mackall, linux-kernel, security On Fri, Dec 14, 2007 at 04:30:08PM -0800, John Reiser wrote: > There is a path that goes from user data into the pool. This path > is subject to manipulation by an attacker, for both reading and > writing. Are you going to guarantee that in five years nobody > will discover a way to take advantage of it? Five years ago > there were no public attacks against MD5 except brute force; > now MD5 is on the "weak" list. Yep, I'm confident about making such a guarantee. Very confident. First of all, keep in mind that the attacks on MD5 are about being able to find hash collisions. The way the cryptographic hash is being used in /dev/random, merely being able to find hash collision means squat. You need to be able to carry out a preimage attack; which no one has been able to do yet. And even if you could figure out how to do a pre-image attack (which none of the "successful attacks" on MD4, MD5, SHA-0, HAVAL-128, RIPEMD, et. al have been able to acomplish), we don't give you the entire hash output; instead, what you get is the hash folded in half via XOR, so you only get the two halves of the SHA hash XOR'ed together to form 80 bits. So given one of these folded 80 bits of hash, you need to figure out a large number of the possible combinations 1024 bits that were in secondry entropy pool could have resulted in the folded hash image. And using the pigeon-hole princple and assuming that SHA approximates a random function, you need to figure out which one of the 2**944 possible combination of 1024 bits was the correct pool pre-image that generated those 80 bits. That's a hard problem. But secondly, even *that's* not enough. As I said earlier, the pool is simply unavailable to the attacker; we never make it available, except by revealing 80 bit hashes of the pool. So you can't read the initial or current state of the pool without first breaking root --- and after 3 bytes of kernel stack is mixed into the pool, via an XOR operation, there is no way to read out the pool. And if you don't know the initial contents of the pool --- funny thing, but UNKNOWN XOR KNOWN == UNKNOWN. So here I'm not even relying on cryptographers of the future not being able to find preimage attacks. I'm just relying on simple logic. - Ted ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: /dev/urandom uses uninit bytes, leaks user data 2007-12-15 4:32 ` Theodore Tso @ 2007-12-17 16:30 ` John Reiser 2007-12-17 17:36 ` Theodore Tso 2007-12-17 20:59 ` David Schwartz 0 siblings, 2 replies; 39+ messages in thread From: John Reiser @ 2007-12-17 16:30 UTC (permalink / raw) To: Theodore Tso; +Cc: Matt Mackall, linux-kernel, security Theodore Tso wrote: > On Fri, Dec 14, 2007 at 04:30:08PM -0800, John Reiser wrote: > >>There is a path that goes from user data into the pool. Note particularly that the path includes data from other users. Under the current implementation, anyone who accesses /dev/urandom is subject to having some bytes from their address space being captured and mixed into the pool. >> This path >>is subject to manipulation by an attacker, for both reading and >>writing. Are you going to guarantee that in five years nobody >>will discover a way to take advantage of it? > Yep, I'm confident about making such a guarantee. Very confident. A direct attack (determining the specific values or partial values of some captured bytes) is not the only way to steal secrets. An indirect attack, such as traffic analysis, also may be effective. Here is one idea. Use output from /dev/urandom to generate a random permutation group. Analyze the group: determine all its subgroups, etc. If the structure of those groups has different properties depending on the captured bytes, even after SHA1 and folding and twisting, then that may be enough to help steal secrets. Indirect attacks may be subject to "exponent doubling." The state modulo 2**(2n) may correspond to a system of 2**n congruences in 2**n variables. So a property modulo 2**n might be hoisted to a related property modulo 2**(2n). This might make 2**1024 seem to be not so big. Also, "getting lucky" is allowed, both via initial conditions and via other coincidences. Running on a newly-booted, newly-installed system might be especially advantageous. A completely formal Goedel-numbering proof often has a formal checker that is logarithmic in the length of the proof. If such a logarithmic property applies every once in a while to /dev/urandom, then that might be enough. The bottom line: At a cost of at most three unpredictable branches (whether to clear the bytes in the last word with indices congruent to 1, 2, or 3 modulo 4), then the code can reduce the risk from something small but positive, to zero. This is very inexpensive insurance. -- John Reiser, jreiser@BitWagon.com ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: /dev/urandom uses uninit bytes, leaks user data 2007-12-17 16:30 ` John Reiser @ 2007-12-17 17:36 ` Theodore Tso 2007-12-18 0:52 ` Andy Lutomirski 2007-12-17 20:59 ` David Schwartz 1 sibling, 1 reply; 39+ messages in thread From: Theodore Tso @ 2007-12-17 17:36 UTC (permalink / raw) To: John Reiser; +Cc: Matt Mackall, linux-kernel, security On Mon, Dec 17, 2007 at 08:30:05AM -0800, John Reiser wrote: > >>[You have yet to show that...] > >>There is a path that goes from user data into the pool. > > Note particularly that the path includes data from other users. > Under the current implementation, anyone who accesses /dev/urandom > is subject to having some bytes from their address space being captured > and mixed into the pool. Again, you haven't *proven* this yet. > A direct attack (determining the specific values or partial values > of some captured bytes) is not the only way to steal secrets. > An indirect attack, such as traffic analysis, also may be effective. > > Here is one idea. Use output from /dev/urandom to generate a random > permutation group. Analyze the group: determine all its subgroups, etc. > If the structure of those groups has different properties depending > on the captured bytes, even after SHA1 and folding and twisting, > then that may be enough to help steal secrets. Generate a random permutation group *how*? This sounds suspiciously like "reverse the polarity of the neutron flow" technobabble to me. What are you going to compare the groups against? What subgroup? How big of a group do you think it is going to be? So you really think the output of SHA is going to produce a group with subgroups? > Indirect attacks may be subject to "exponent doubling." The state > modulo 2**(2n) may correspond to a system of 2**n congruences > in 2**n variables. So a property modulo 2**n might be hoisted to a > related property modulo 2**(2n). This might make 2**1024 seem to be > not so big. > A completely formal > Goedel-numbering proof often has a formal checker that is logarithmic > in the length of the proof. If such a logarithmic property applies > every once in a while to /dev/urandom, then that might be enough. References, please and exactly how this would apply to the situation at hand? This sounds like math babble to me, and I have taken enough abstract algebra and other math class that this sounds suspiciously to me like the sort of stuff that Star Trek actors make up when the script says "insert technobabble here". Of course, I'm not a math major, so I'm willing to accept the possibility that you know what you're talking about --- but I do know enough that I should be able to evaluate any proofs and math papers you want to throw at me. - Ted ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: /dev/urandom uses uninit bytes, leaks user data 2007-12-17 17:36 ` Theodore Tso @ 2007-12-18 0:52 ` Andy Lutomirski 2007-12-18 3:05 ` Theodore Tso 2007-12-18 5:12 ` David Schwartz 0 siblings, 2 replies; 39+ messages in thread From: Andy Lutomirski @ 2007-12-18 0:52 UTC (permalink / raw) To: Theodore Tso, John Reiser, Matt Mackall, linux-kernel, security Theodore Tso wrote: > On Mon, Dec 17, 2007 at 08:30:05AM -0800, John Reiser wrote: >>>> [You have yet to show that...] >>>> There is a path that goes from user data into the pool. >> Note particularly that the path includes data from other users. >> Under the current implementation, anyone who accesses /dev/urandom >> is subject to having some bytes from their address space being captured >> and mixed into the pool. > > Again, you haven't *proven* this yet. Has anyone *proven* that using uninitialized data this way is safe? As a *user* of this stuff, I'm *very* hesitant to trust Linux's RNG when I hear things like this. (Hint: most protocols are considered insecure until proven otherwise, not the other way around.) Consider: add_entropy_words is reversible [1], presumably in the sense that words could be removed, so, if there added words are independent of the state, there is no loss of entropy. But it also appears reversible in the sense that if the pool has a known state and entropy words are added, most of which are known, the unknown ones can be found (if nothing else, if there are only a few bits of entropy there, you can try all possibilities). Now imagine a security program. It runs some forward secret protocol and it's very safe not to leak data that would break forward secrecy (mlockall, memset when done with stuff, etc). It runs on a freshly booted machine (no DSA involved, so we're not automatically hosed), so an attacker knows the initial pool state. Conveniently, some *secret* (say an ephemeral key, or, worse, a password) gets mixed in to the pool. There are apparently at most three bytes of extra data mixed in, but suppose the attacker knows add the words that were supposed to get mixed in. Now the program clears all its state to "ensure" forward secrecy, and *then* the machine gets hacked. Now the attacker can learn (with at most 2^24 guesses worth of computation) 24 bits worth of a secret, which could quite easily reduce the work involved in breaking whatever forward secret protocol was involved from intractable to somewhat easy. Or it could leak three bytes of password. Or whatever. Sorry for the somewhat inflammatory email, but this is absurd. --Andy [1] http://www.mail-archive.com/linux-kernel@vger.kernel.org/msg238406.html ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: /dev/urandom uses uninit bytes, leaks user data 2007-12-18 0:52 ` Andy Lutomirski @ 2007-12-18 3:05 ` Theodore Tso 2007-12-18 3:13 ` David Newall 2007-12-18 5:12 ` David Schwartz 1 sibling, 1 reply; 39+ messages in thread From: Theodore Tso @ 2007-12-18 3:05 UTC (permalink / raw) To: Andy Lutomirski; +Cc: John Reiser, Matt Mackall, linux-kernel, security On Mon, Dec 17, 2007 at 07:52:53PM -0500, Andy Lutomirski wrote: > It runs on a freshly booted machine (no > DSA involved, so we're not automatically hosed), so an attacker knows the > initial pool state. Not just a freshly booted system. The system has to be a freshly booted, AND freshly installed system. Normally you mix in a random seed at boot time. And during the boot sequence, the block I/O will be mixing randomness into the entropy pool, and as the user logs in, the keyboard and mouse will be mixing more entropy into the pool. So you'll have to assume that all entropy inputs have somehow been disabled as well. BUT --- if the pool state is totally known, you're really, REALLY, REALLY hosed, since normally /dev/random might get used to initialize a CRNG to *generate* the ephmeral key. So the danger is not *3* *bytes* of the empheral key accidentally getting mixed into the entropy pool, followed by an attacker managing to crack the system so bad that he or she has read access into kernel memory (without managing to mix more entropy into the pool), and then doing sophisticated cryptoanalytic attacks with an O(2**24) order time, to try to leak the *3* *bytes* of emphemeral key. No, the problem is that the attacker, with access to the known initial state of the pool, will be able to find out *THE* *ENTIRE* *EMPHERAL* *KEY*, since it was probably generated via /dev/random --- and without needing to break into the system with sufficient privs to be able to read kernel memory. So it is your argument which is absurd. If you're going to assume a completely known pool state, and then assume some program is using /dev/random, the danger is not in change that some previous kernel stack state might contain something secret that could theoretically be revealed after an attacker manages to break into machine as root. No, the real danger is in what this presumably cryptographically sensitive program did with the predictable data from /dev/random. So the real answer is that there needs to be sufficient randomness mixed into /dev/random. For a typical Linux system, it's there. There are some potential configuration (say a pure diskless system with NFS remote filesystems and no keyboard or mouse) being used in some kind of security-sensitive system. Now, someone who wanted to say, run a remote certificate signing server or IPSEC key management system on such a system would arguably be performing security malpractice, and the lack of entropy for /dev/random is probably the least of such a system's security problems. But in any case, instead of trying to worry about these sorts of hypothetical worries, the much better use of time and energy is the userspace daemon that can sample entropy from a sound device, or some other hardware entropy available to the system. The real issue is being able to make sure the pool is *not* knowable to an attacker. - Ted ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: /dev/urandom uses uninit bytes, leaks user data 2007-12-18 3:05 ` Theodore Tso @ 2007-12-18 3:13 ` David Newall 2007-12-18 3:46 ` Theodore Tso 0 siblings, 1 reply; 39+ messages in thread From: David Newall @ 2007-12-18 3:13 UTC (permalink / raw) To: Theodore Tso, Andy Lutomirski, John Reiser, Matt Mackall, linux-kernel, security Theodore Tso wrote: > On Mon, Dec 17, 2007 at 07:52:53PM -0500, Andy Lutomirski wrote: > >> It runs on a freshly booted machine (no >> DSA involved, so we're not automatically hosed), so an attacker knows the >> initial pool state. >> > > Not just a freshly booted system. The system has to be a freshly > booted, AND freshly installed system. Normally you mix in a random > seed at boot time. And during the boot sequence, the block I/O will > be mixing randomness into the entropy pool, and as the user logs in, > the keyboard and mouse will be mixing more entropy into the pool. So > you'll have to assume that all entropy inputs have somehow been > disabled as well. > On a server, keyboard and mouse are rarely used. As you've described it, that leaves only the disk, and during the boot process, disk accesses and timing are somewhat predictable. Whether this is sufficient to break the RNG is (clearly) a matter of debate. ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: /dev/urandom uses uninit bytes, leaks user data 2007-12-18 3:13 ` David Newall @ 2007-12-18 3:46 ` Theodore Tso 2007-12-18 4:09 ` David Newall 2007-12-20 4:18 ` Andrew Lutomirski 0 siblings, 2 replies; 39+ messages in thread From: Theodore Tso @ 2007-12-18 3:46 UTC (permalink / raw) To: David Newall Cc: Andy Lutomirski, John Reiser, Matt Mackall, linux-kernel, security On Tue, Dec 18, 2007 at 01:43:28PM +1030, David Newall wrote: > On a server, keyboard and mouse are rarely used. As you've described it, > that leaves only the disk, and during the boot process, disk accesses and > timing are somewhat predictable. Whether this is sufficient to break the > RNG is (clearly) a matter of debate. In normal operaiton, entropy is accumlated on the system, extracted via /dev/urandom at shutdown, and then loaded back into the system when it boots up. So this will help in everything but the freshly installed system case (and in that case things will get better as the system has a chance to operate). If you have a system with insufficent entropy inputs, you're in trouble, of course. There are "catastrophic reseeds" that attempt to mitigrate some of worse attacks, but at the end of the day, /dev/random isn't magic. In any case, the problem if you have insufficent entropy is not esoteric attacks that presume an attacker can break into the system and read out kernel memory. The problem will be /dev/random's entropy output. And there are techniques that cryptographic applications can do to help. For example, if it is about to encrypt data, it can SHA-1 hash data that it is about to be sent out encrypted, and feed the SHA-1 hash into /dev/random. This won't increase entropy credit counter, but if the attacker doesn't have access to the unecrypted plaintext, mixing in the SHA-1 hash into /dev/random can only help. If you have a server, the best thing you can do is use a hardware random number generator, if it exists. Fortunately a number of hardware platforms, such as IBM blades and Thinkpads, come with TPM modules that include hardware RNG's. That's ultimately the best way to solve these issues. - Ted ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: /dev/urandom uses uninit bytes, leaks user data 2007-12-18 3:46 ` Theodore Tso @ 2007-12-18 4:09 ` David Newall 2007-12-18 4:23 ` Theodore Tso 2007-12-19 22:40 ` Bill Davidsen 2007-12-20 4:18 ` Andrew Lutomirski 1 sibling, 2 replies; 39+ messages in thread From: David Newall @ 2007-12-18 4:09 UTC (permalink / raw) To: Theodore Tso, David Newall, Andy Lutomirski, John Reiser, Matt Mackall, linux-kernel, security Theodore Tso wrote: > On Tue, Dec 18, 2007 at 01:43:28PM +1030, David Newall wrote: > >> On a server, keyboard and mouse are rarely used. As you've described it, >> that leaves only the disk, and during the boot process, disk accesses and >> timing are somewhat predictable. Whether this is sufficient to break the >> RNG is (clearly) a matter of debate. >> > > In normal operaiton, entropy is accumlated on the system, extracted > via /dev/urandom at shutdown, and then loaded back into the system > when it boots up. Thus, the entropy saved at shutdown can be known at boot-time. (You can examine the saved entropy on disk.) > If you have a server, the best thing you can do is use a hardware > random number generator, if it exists. Fortunately a number of > hardware platforms, such as IBM blades and Thinkpads, come with TPM > modules that include hardware RNG's. That's ultimately the best way > to solve these issues. Just how random are they? Do they turn out to be quite predictable if you're IBM? ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: /dev/urandom uses uninit bytes, leaks user data 2007-12-18 4:09 ` David Newall @ 2007-12-18 4:23 ` Theodore Tso 2007-12-19 22:43 ` Bill Davidsen 2007-12-19 22:40 ` Bill Davidsen 1 sibling, 1 reply; 39+ messages in thread From: Theodore Tso @ 2007-12-18 4:23 UTC (permalink / raw) To: David Newall Cc: Andy Lutomirski, John Reiser, Matt Mackall, linux-kernel, security On Tue, Dec 18, 2007 at 02:39:00PM +1030, David Newall wrote: > > Thus, the entropy saved at shutdown can be known at boot-time. (You can > examine the saved entropy on disk.) > If you can examine the saved entropy on disk, you can also introduce a trojan horse kernel that logs all keystrokes and all generated entropy to the FBI carnivore server --- you can replace the gpg binary with one which ships copies of the session keys to the CIA --- and you can replace the freeswan server with one which generates emphermal keys by encrypting the current timestamp with a key known only by the NSA. So if the attacker has access to your disk between shutdown and boot up, you are *done*. /dev/random is the least of your worries. Really, why is it that people are so enamored about proposing these totally bogus scenarios? Yes, if you have direct physical access to your machine, you can compromise it. But there are far easier ways that such a vulnerability can be exploited, rather than making it easy to carry out an cryptoanalytic attack on /dev/random. (And yes, after using the saved state to load the entropy at boot-time, the saved state file is overwritten, and if you're paranoid, you can scrub the disk after it is read and mixed into the entropy pool. And yes, the saved state is *not* the entropy pool used during the previous boot, but entropy extracted using SHA-1 based CRNG.) >> If you have a server, the best thing you can do is use a hardware >> random number generator, if it exists. Fortunately a number of >> hardware platforms, such as IBM blades and Thinkpads, come with TPM >> modules that include hardware RNG's. That's ultimately the best way >> to solve these issues. > > Just how random are they? Do they turn out to be quite predictable if > you're IBM? They use a noise diode, so they are as good as any other hardware random number generator. Of course, you ultimately have to trust the supplier of your hardware not to do something screwy, and Thinkpads are now made by Lenovo, which has caused some US Government types to get paranoid --- but that's why the best way to do things is to get entropy from as many places as possible, and mix it all into /dev/random. If any one of them is unknown to the attacker, he's stuck. And if you are sufficiently paranoid, you obviously can't use commodity hardware, and how do you know that some time along time ago, someone snuck in a evil secret code into the C compiler that was designed to survive a bootstrap process[1]? And how do you know that your keyboard controller hasn't been gimmicked to record your key strokes and then send them out by adding jitter that can be read by an attacker looking at the timing of your ssh packets[2]? But seriously, if you are that paranoid, better build your hardware from scratch, and then hand assemble your compiler, and then do a line-by-line audit of all of your source code. It's going to be the only way to be sure.... - Ted [1] Ken Thompson, Reflections on Trusting Trust. http://cm.bell-labs.com/who/ken/trust.html [2] Gaurav Shah, Andres Molina and Matt Blaze, Keyboards and Covert Channels. http://www.usenix.org/events/sec06/tech/shah/shah_html/index.html ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: /dev/urandom uses uninit bytes, leaks user data 2007-12-18 4:23 ` Theodore Tso @ 2007-12-19 22:43 ` Bill Davidsen 0 siblings, 0 replies; 39+ messages in thread From: Bill Davidsen @ 2007-12-19 22:43 UTC (permalink / raw) To: Theodore Tso, David Newall, Andy Lutomirski, John Reiser, Matt Mackall, linux-kernel, security Theodore Tso wrote: > On Tue, Dec 18, 2007 at 02:39:00PM +1030, David Newall wrote: >> Thus, the entropy saved at shutdown can be known at boot-time. (You can >> examine the saved entropy on disk.) >> > > If you can examine the saved entropy on disk, you can also introduce a > trojan horse kernel that logs all keystrokes and all generated entropy > to the FBI carnivore server --- you can replace the gpg binary with > one which ships copies of the session keys to the CIA --- and you can > replace the freeswan server with one which generates emphermal keys by > encrypting the current timestamp with a key known only by the NSA. So > if the attacker has access to your disk between shutdown and boot up, > you are *done*. /dev/random is the least of your worries. > > Really, why is it that people are so enamored about proposing these > totally bogus scenarios? Yes, if you have direct physical access to > your machine, you can compromise it. But there are far easier ways > that such a vulnerability can be exploited, rather than making it easy > to carry out an cryptoanalytic attack on /dev/random. > > (And yes, after using the saved state to load the entropy at > boot-time, the saved state file is overwritten, and if you're > paranoid, you can scrub the disk after it is read and mixed into the > entropy pool. And yes, the saved state is *not* the entropy pool used > during the previous boot, but entropy extracted using SHA-1 based > CRNG.) > >>> If you have a server, the best thing you can do is use a hardware >>> random number generator, if it exists. Fortunately a number of >>> hardware platforms, such as IBM blades and Thinkpads, come with TPM >>> modules that include hardware RNG's. That's ultimately the best way >>> to solve these issues. >> Just how random are they? Do they turn out to be quite predictable if >> you're IBM? > > They use a noise diode, so they are as good as any other hardware > random number generator. Of course, you ultimately have to trust the > supplier of your hardware not to do something screwy, and Thinkpads > are now made by Lenovo, which has caused some US Government types to > get paranoid --- but that's why the best way to do things is to get > entropy from as many places as possible, and mix it all into > /dev/random. If any one of them is unknown to the attacker, he's stuck. > In another thread I believe I mentioned things an attacker can't know (unless your system is already compromised) like fan speed, CPU temperature, etc. -- Bill Davidsen <davidsen@tmr.com> "We have more to fear from the bungling of the incompetent than from the machinations of the wicked." - from Slashdot ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: /dev/urandom uses uninit bytes, leaks user data 2007-12-18 4:09 ` David Newall 2007-12-18 4:23 ` Theodore Tso @ 2007-12-19 22:40 ` Bill Davidsen 1 sibling, 0 replies; 39+ messages in thread From: Bill Davidsen @ 2007-12-19 22:40 UTC (permalink / raw) To: David Newall Cc: Theodore Tso, Andy Lutomirski, John Reiser, Matt Mackall, Linux Kernel mailing List David Newall wrote: > Theodore Tso wrote: >> On Tue, Dec 18, 2007 at 01:43:28PM +1030, David Newall wrote: >> >>> On a server, keyboard and mouse are rarely used. As you've described >>> it, that leaves only the disk, and during the boot process, disk >>> accesses and timing are somewhat predictable. Whether this is >>> sufficient to break the RNG is (clearly) a matter of debate. >>> >> >> In normal operaiton, entropy is accumlated on the system, extracted >> via /dev/urandom at shutdown, and then loaded back into the system >> when it boots up. > > Thus, the entropy saved at shutdown can be known at boot-time. (You can > examine the saved entropy on disk.) > > >> If you have a server, the best thing you can do is use a hardware >> random number generator, if it exists. Fortunately a number of >> hardware platforms, such as IBM blades and Thinkpads, come with TPM >> modules that include hardware RNG's. That's ultimately the best way >> to solve these issues. > > Just how random are they? Do they turn out to be quite predictable if > you're IBM? The typical RNG is a noise diode or other similar hardware using thermal noise, so it's unlikely that anyone but God could predict it. There are some USB devices which supposedly use radioactive decay, I'm unsure if that's better but I don't want to carry the dongle in my pants pocket. The hotbits network site uses radioactive decay to generate it's numbers. -- Bill Davidsen <davidsen@tmr.com> "We have more to fear from the bungling of the incompetent than from the machinations of the wicked." - from Slashdot ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: /dev/urandom uses uninit bytes, leaks user data 2007-12-18 3:46 ` Theodore Tso 2007-12-18 4:09 ` David Newall @ 2007-12-20 4:18 ` Andrew Lutomirski 2007-12-20 20:17 ` Phillip Susi 2007-12-20 20:36 ` Theodore Tso 1 sibling, 2 replies; 39+ messages in thread From: Andrew Lutomirski @ 2007-12-20 4:18 UTC (permalink / raw) To: Theodore Tso, David Newall, Andy Lutomirski, John Reiser, Matt Mackall, linux-kernel, security On Dec 17, 2007 10:46 PM, Theodore Tso <tytso@mit.edu> wrote: > If you have a system with insufficent entropy inputs, you're in > trouble, of course. There are "catastrophic reseeds" that attempt to > mitigrate some of worse attacks, but at the end of the day, > /dev/random isn't magic. > I understand that there's no way that /dev/random can provide good output if there's insufficient entropy. But it still shouldn't leak arbitrary bits of user data that were never meant to be put into the pool at all. (My hypothetical attack is a lot hypothetical than I thought at first. An attacker does not need to break into the kernel and steal the state of the pool. It may be as easy as this to trigger: Step 1: Boot a system without a usable entropy source. Step 2: add some (predictable) "entropy" from userspace which isn't a multiple of 4, so up to three extra bytes get added. Step 3: Read a few bytes of /dev/random and send them over the network. An attacker can now try all possibilities of the three extra bytes and guess them pretty quickly. No compromise needed. This is, IMHO, bad. (It's one thing for the "random" numbers to be weak. It's another thing entirely for them to reveal data that never belonged in the pool in the first place.) Actually, perhaps there should be a policy that we try never to reseed the pool at all until there is enough entropy around to prevent attacks like these. (In theory the state of the pool might contain 2^(smallish number) bits of data interesting to the attacker even without the uninitialized data issue.) This would make the situation even worse for low-entropy systems, though. --Andy ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: /dev/urandom uses uninit bytes, leaks user data 2007-12-20 4:18 ` Andrew Lutomirski @ 2007-12-20 20:17 ` Phillip Susi 2007-12-21 16:10 ` Andrew Lutomirski 2007-12-20 20:36 ` Theodore Tso 1 sibling, 1 reply; 39+ messages in thread From: Phillip Susi @ 2007-12-20 20:17 UTC (permalink / raw) To: Andrew Lutomirski Cc: Theodore Tso, David Newall, John Reiser, Matt Mackall, linux-kernel, security Andrew Lutomirski wrote: > I understand that there's no way that /dev/random can provide good > output if there's insufficient entropy. But it still shouldn't leak > arbitrary bits of user data that were never meant to be put into the > pool at all. It doesn't leak it though, it consumes it, and it then vanishes into the entropy pool, never to be seen again. > Step 1: Boot a system without a usable entropy source. > Step 2: add some (predictable) "entropy" from userspace which isn't a > multiple of 4, so up to three extra bytes get added. > Step 3: Read a few bytes of /dev/random and send them over the network. Only root can do 1 and 2, at which point, it's already game over. ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: /dev/urandom uses uninit bytes, leaks user data 2007-12-20 20:17 ` Phillip Susi @ 2007-12-21 16:10 ` Andrew Lutomirski 2007-12-22 1:14 ` Theodore Tso 2007-12-26 18:30 ` Phillip Susi 0 siblings, 2 replies; 39+ messages in thread From: Andrew Lutomirski @ 2007-12-21 16:10 UTC (permalink / raw) To: Phillip Susi Cc: Theodore Tso, David Newall, John Reiser, Matt Mackall, linux-kernel, security On Dec 20, 2007 3:17 PM, Phillip Susi <psusi@cfl.rr.com> wrote: > Andrew Lutomirski wrote: > > I understand that there's no way that /dev/random can provide good > > output if there's insufficient entropy. But it still shouldn't leak > > arbitrary bits of user data that were never meant to be put into the > > pool at all. > > It doesn't leak it though, it consumes it, and it then vanishes into the > entropy pool, never to be seen again. No, it's there, and if there's little enough entropy around it can be recovered by brute force. > > > Step 1: Boot a system without a usable entropy source. > > Step 2: add some (predictable) "entropy" from userspace which isn't a > > multiple of 4, so up to three extra bytes get added. > > Step 3: Read a few bytes of /dev/random and send them over the network. > > Only root can do 1 and 2, at which point, it's already game over. Again, no. Root could do this accidentally. Step 1 happens all the time (see the comments on non-unique UUIDs). Step 2 just requires a program to put data which it things is OK to go into the pool next to data that shouldn't be there in memory. I'm OK with the entropy pool being insecure in cases where it cannot possibly be secure. But it should not leak information that never belonged in it in the first place. (Remember, the entire justification for Linux's model of the entropy pool seems to be that it should be as secure as possible even against computationally unbounded attackers or attackers who can find SHA preimages. A brute force attack that works sometimes and only requires 2^24 brute force iterations certainly fits into this threat model.) --Andy ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: /dev/urandom uses uninit bytes, leaks user data 2007-12-21 16:10 ` Andrew Lutomirski @ 2007-12-22 1:14 ` Theodore Tso 2007-12-26 18:30 ` Phillip Susi 1 sibling, 0 replies; 39+ messages in thread From: Theodore Tso @ 2007-12-22 1:14 UTC (permalink / raw) To: Andrew Lutomirski Cc: Phillip Susi, David Newall, John Reiser, Matt Mackall, linux-kernel, security On Fri, Dec 21, 2007 at 11:10:36AM -0500, Andrew Lutomirski wrote: > > > Step 1: Boot a system without a usable entropy source. > > > Step 2: add some (predictable) "entropy" from userspace which isn't a > > > multiple of 4, so up to three extra bytes get added. > > > Step 3: Read a few bytes of /dev/random and send them over the network. > > > > Only root can do 1 and 2, at which point, it's already game over. > > Again, no. Root could do this accidentally. Step 1 happens all the > time (see the comments on non-unique UUIDs). Actually, it doesn't happen *all* the time. That was a situation of an rpm post-install script trying to use a random UUID generation facility from a kick-start install where there was no keyboard activity and apparently no other entropy added. (Note that in such an environment, generation of host ssh keys at install time without any entropy is an even bigger problem, and that *is* something that people should be thinking about.) > Step 2 just requires a > program to put data which it things is OK to go into the pool next to > data that shouldn't be there in memory. Um, no, that's incorrect. Simply putting data which is OK to put into the pool next to data that shouldn't isn't enough. First of all, the issue is using unitialized kernel stack garbage. Read that again, slowly --- kernel stack. How you arrange your data in user memory doesn't matter. Secondly, as I've said earlier, I'm not aware of any program that actually tries to write into the entropy pool on most modern Linux systems other than dd in /etc/init.d/random which initializes the random pool from pre-seeded entropy on disk. - Ted ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: /dev/urandom uses uninit bytes, leaks user data 2007-12-21 16:10 ` Andrew Lutomirski 2007-12-22 1:14 ` Theodore Tso @ 2007-12-26 18:30 ` Phillip Susi 1 sibling, 0 replies; 39+ messages in thread From: Phillip Susi @ 2007-12-26 18:30 UTC (permalink / raw) To: Andrew Lutomirski Cc: Theodore Tso, David Newall, John Reiser, Matt Mackall, linux-kernel, security Andrew Lutomirski wrote: > No, it's there, and if there's little enough entropy around it can be > recovered by brute force. A little entropy is enough to prevent a brute force attack. You would have to have ZERO entropy after a cold boot so the attacker would know exactly the contents of the pool, AND know that one and ONLY one other task has read from /dev/urandom, AND exactly what time that task did so, AND how many bytes it read. Only then could the attacker read from urandom and based on those bytes and the previous known pool state, brute force the 3 bytes that came from some unknown location in the other task's memory. >>> Step 1: Boot a system without a usable entropy source. >>> Step 2: add some (predictable) "entropy" from userspace which isn't a >>> multiple of 4, so up to three extra bytes get added. >>> Step 3: Read a few bytes of /dev/random and send them over the network. >> Only root can do 1 and 2, at which point, it's already game over. > > Again, no. Root could do this accidentally. Step 1 happens all the > time (see the comments on non-unique UUIDs). Step 2 just requires a It does not happen all the time. It happens on a system that has just been cold booted from read only distribution media with a broken cmos clock, no user keyboard interaction, and no hardware rng and that's it. Every other system is going to have some entropy from the last boot at least. ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: /dev/urandom uses uninit bytes, leaks user data 2007-12-20 4:18 ` Andrew Lutomirski 2007-12-20 20:17 ` Phillip Susi @ 2007-12-20 20:36 ` Theodore Tso 2007-12-27 10:44 ` Pavel Machek 1 sibling, 1 reply; 39+ messages in thread From: Theodore Tso @ 2007-12-20 20:36 UTC (permalink / raw) To: Andrew Lutomirski Cc: David Newall, John Reiser, Matt Mackall, linux-kernel, security On Wed, Dec 19, 2007 at 11:18:54PM -0500, Andrew Lutomirski wrote: > I understand that there's no way that /dev/random can provide good > output if there's insufficient entropy. But it still shouldn't leak > arbitrary bits of user data that were never meant to be put into the > pool at all. Let's be clear here. It's not arbitrary bits of user data. It's at most three bytes of kernel stack garbage from the process which is adding entropy to /dev/random from userspace. And the attacker doesn't get to pick which 3 bytes they are, either! That means they are not "arbitrary bits". > (My hypothetical attack is a lot hypothetical than I thought at first. > An attacker does not need to break into the kernel and steal the > state of the pool. It may be as easy as this to trigger: > > Step 1: Boot a system without a usable entropy source. > Step 2: add some (predictable) "entropy" from userspace which isn't a > multiple of 4, so up to three extra bytes get added. > Step 3: Read a few bytes of /dev/random and send them over the network. So Step 1 assumes a system without a random seed file, or any usable entropy source. As I've mentioned, this means that any cryptographic users of /dev/random --- like, say, openssh daemon --- are in deep, DEEP, trouble. This is a very serious problem, and in my opinion, far more serious and far more REAL that your hypothetical attack. So we need to address Step 1 anyway, and more urgently. In step 2, what program are you expecting will be writing to /dev/random? Very few programs do so today, and none that are commonly installed on most Linux distributions, other than the dd program run out of /etc/init.d/random to initialize /dev/random from the random seed file. But, oh wait --- you're assuming that doesn't exist, even though all major distributions have it. Why would a legitimate program read a few bytes of /dev/random and send them on the network in step 3? Or are you assuming your hypothetical attacker has a shell account on the system? In which case there is probably far more concerns about information leakage than 3 bytes of kernel stack garbage, which might or might not contain user data. And note that this attack can only be done for 3 bytes. After that, the work factors involved become intractable. So yes, there is a theoretical hole given your assumptions, but the problem started the "system without any intial entropy", and there are far worse problems that result in that case. So that is the problem we should be addressing. That being said, write_pool() is hardly a fastpath, and the memset isn't going to make any difference. So if it makes people feel better, I don't object to adding it. I'm just pointing out that the assumption is either pretty silly (since all of the distributions do use the random seed file, and in practice *someone* has logged into the console to add some amount of entropy at some point in the machine's lifetime, even it if was when the machine was initially installed) and/or points out a more critical issue, which is we need to make sure that we do have a reasonable entropy source on all machines. - Ted ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: /dev/urandom uses uninit bytes, leaks user data 2007-12-20 20:36 ` Theodore Tso @ 2007-12-27 10:44 ` Pavel Machek 0 siblings, 0 replies; 39+ messages in thread From: Pavel Machek @ 2007-12-27 10:44 UTC (permalink / raw) To: Theodore Tso, Andrew Lutomirski, David Newall, John Reiser, Matt Mackall, linux-kernel, security On Thu 2007-12-20 15:36:01, Theodore Tso wrote: > On Wed, Dec 19, 2007 at 11:18:54PM -0500, Andrew Lutomirski wrote: > > I understand that there's no way that /dev/random can provide good > > output if there's insufficient entropy. But it still shouldn't leak > > arbitrary bits of user data that were never meant to be put into the > > pool at all. > > Let's be clear here. It's not arbitrary bits of user data. It's at > most three bytes of kernel stack garbage from the process which is > adding entropy to /dev/random from userspace. And the attacker > doesn't get to pick which 3 bytes they are, either! That means they > are not "arbitrary bits". > > > (My hypothetical attack is a lot hypothetical than I thought at first. > > An attacker does not need to break into the kernel and steal the > > state of the pool. It may be as easy as this to trigger: > > > > Step 1: Boot a system without a usable entropy source. > > Step 2: add some (predictable) "entropy" from userspace which isn't a > > multiple of 4, so up to three extra bytes get added. > > Step 3: Read a few bytes of /dev/random and send them over the network. > > So Step 1 assumes a system without a random seed file, or any usable > entropy source. As I've mentioned, this means that any cryptographic > users of /dev/random --- like, say, openssh daemon --- are in deep, > DEEP, trouble. This is a very serious problem, and in my opinion, far > more serious and far more REAL that your hypothetical attack. So we > need to address Step 1 anyway, and more urgently. > > In step 2, what program are you expecting will be writing to > /dev/random? Very few programs do so today, and none that are > commonly installed on most Linux distributions, other than the dd > program run out of /etc/init.d/random to initialize /dev/random from > the random seed file. But, oh wait --- you're assuming that doesn't > exist, even though all major distributions have it. > > Why would a legitimate program read a few bytes of /dev/random and > send them on the network in step 3? Or are you assuming your > hypothetical attacker has a shell account on the system? In which > case there is probably far more concerns about information leakage > than 3 bytes of kernel stack garbage, which might or might not contain > user data. > > And note that this attack can only be done for 3 bytes. After that, > the work factors involved become intractable. > > So yes, there is a theoretical hole given your assumptions, but the > problem started the "system without any intial entropy", and there are > far worse problems that result in that case. So that is the problem > we should be addressing. > > That being said, write_pool() is hardly a fastpath, and the memset > isn't going to make any difference. So if it makes people feel > better, I don't object to adding it. I'm just pointing out that the > assumption is either pretty silly (since all of the distributions do > use the random seed file, and in practice *someone* has logged into > the console to add some amount of entropy at some point in the > machine's lifetime, even it if was when the machine was initially > installed) and/or points out a more critical issue, which is we need > to make sure that we do have a reasonable entropy source on all > machines. Lets memset. It is not a fastpath, and code will be more obvious that way. -- (english) http://www.livejournal.com/~pavelmachek (cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html ^ permalink raw reply [flat|nested] 39+ messages in thread
* RE: /dev/urandom uses uninit bytes, leaks user data 2007-12-18 0:52 ` Andy Lutomirski 2007-12-18 3:05 ` Theodore Tso @ 2007-12-18 5:12 ` David Schwartz 1 sibling, 0 replies; 39+ messages in thread From: David Schwartz @ 2007-12-18 5:12 UTC (permalink / raw) To: Theodore Tso, John Reiser, Matt Mackall, linux-kernel, security > Has anyone *proven* that using uninitialized data this way is safe? You can probably find dozens of things in the Linux kernel that have not been proven to be safe. That means nothing. > As > a *user* of this stuff, I'm *very* hesitant to trust Linux's RNG when I > hear things like this. (Hint: most protocols are considered insecure > until proven otherwise, not the other way around.) There's no reason whatsoever to think this is unsafe. First, you can't access the pool directly. Second, even if you could, it's mixed in securely. > Now imagine a security program. It runs some forward secret protocol > and it's very safe not to leak data that would break forward secrecy > (mlockall, memset when done with stuff, etc). It runs on a freshly > booted machine (no DSA involved, so we're not automatically hosed), so > an attacker knows the initial pool state. Conveniently, some *secret* > (say an ephemeral key, or, worse, a password) gets mixed in to the pool. > There are apparently at most three bytes of extra data mixed in, but > suppose the attacker knows add the words that were supposed to get mixed > in. Now the program clears all its state to "ensure" forward secrecy, > and *then* the machine gets hacked. Now the attacker can learn (with at > most 2^24 guesses worth of computation) 24 bits worth of a secret, which > could quite easily reduce the work involved in breaking whatever forward > secret protocol was involved from intractable to somewhat easy. Or it > could leak three bytes of password. Or whatever. This is no more precise than "imagine there's some vulnerability in the RNG". Yes, if there's a vulnerability, then we're vulnerable. An attacker can always (at least in principle) get the pool out of the kernel. The RNG's design is premised on the notion that it is computationally infeasbile to get the input entropy out of the pool. If an attacker can watch data going into the pool, he needn't get it out of the pool. > Sorry for the somewhat inflammatory email, but this is absurd. I agree. DS ^ permalink raw reply [flat|nested] 39+ messages in thread
* RE: /dev/urandom uses uninit bytes, leaks user data 2007-12-17 16:30 ` John Reiser 2007-12-17 17:36 ` Theodore Tso @ 2007-12-17 20:59 ` David Schwartz 1 sibling, 0 replies; 39+ messages in thread From: David Schwartz @ 2007-12-17 20:59 UTC (permalink / raw) To: Theodore Tso, jreiser; +Cc: Matt Mackall, linux-kernel, security > The bottom line: At a cost of at most three unpredictable branches > (whether to clear the bytes in the last word with indices congruent > to 1, 2, or 3 modulo 4), then the code can reduce the risk from something > small but positive, to zero. This is very inexpensive insurance. > John Reiser, jreiser@BitWagon.com Even if you're right, the change isn't free. You've simply presented evidence of one non-zero benefit of it. You've given no ability to assess the size of this benefit and no way to figure if it exceeds the cost. There is also a non-zero *security* cost to this change. DS ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: /dev/urandom uses uninit bytes, leaks user data 2007-12-15 0:30 ` John Reiser 2007-12-15 4:32 ` Theodore Tso @ 2007-12-15 7:13 ` Herbert Xu 2007-12-15 16:30 ` Matt Mackall 2007-12-17 17:28 ` Signed divides vs shifts (Re: [Security] /dev/urandom uses uninit bytes, leaks user data) Linus Torvalds 1 sibling, 2 replies; 39+ messages in thread From: Herbert Xu @ 2007-12-15 7:13 UTC (permalink / raw) To: John Reiser, akpm; +Cc: tytso, mpm, linux-kernel, security John Reiser <jreiser@bitwagon.com> wrote: > > If speed matters that much, then please recoup 33 cycles on x86 > by using shifts instead of three divides, such as (gcc 4.1.2): > > add_entropy_words(r, tmp, (bytes + 3) / 4); > > 0x8140689 <xfer_secondary_pool+206>: lea 0x3(%esi),%eax > 0x814068c <xfer_secondary_pool+209>: mov $0x4,%dl > 0x814068e <xfer_secondary_pool+211>: mov %edx,%edi > 0x8140690 <xfer_secondary_pool+213>: cltd > 0x8140691 <xfer_secondary_pool+214>: idiv %edi There ought to be a warning about this sort of thing. [CHAR] random: Avoid signed integer division Joihn Reiser pointed out that we use signed integer divisions unnecessarily in random.c. This is bad because the C compiler is obliged to consider the case of a negative dividend. This patch changes all the relevant divisions and modulus operations to use unsigned arithmetic. Signed-off: Herbert Xu <herbert@gondor.apana.org.au> Thanks, -- Visit Openswan at http://www.openswan.org/ Email: Herbert Xu ~{PmV>HI~} <herbert@gondor.apana.org.au> Home Page: http://gondor.apana.org.au/~herbert/ PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt -- diff --git a/drivers/char/random.c b/drivers/char/random.c index 5fee056..6c70bfb 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -694,11 +694,11 @@ static void xfer_secondary_pool(struct entropy_store *r, size_t nbytes) if (r->pull && r->entropy_count < nbytes * 8 && r->entropy_count < r->poolinfo->POOLBITS) { /* If we're limited, always leave two wakeup worth's BITS */ - int rsvd = r->limit ? 0 : random_read_wakeup_thresh/4; + int rsvd = r->limit ? 0 : random_read_wakeup_thresh / 4u; int bytes = nbytes; /* pull at least as many as BYTES as wakeup BITS */ - bytes = max_t(int, bytes, random_read_wakeup_thresh / 8); + bytes = max_t(int, bytes, random_read_wakeup_thresh / 8u); /* but never more than the buffer size */ bytes = min_t(int, bytes, sizeof(tmp)); @@ -707,8 +707,8 @@ static void xfer_secondary_pool(struct entropy_store *r, size_t nbytes) r->name, bytes * 8, nbytes * 8, r->entropy_count); bytes=extract_entropy(r->pull, tmp, bytes, - random_read_wakeup_thresh / 8, rsvd); - add_entropy_words(r, tmp, (bytes + 3) / 4); + random_read_wakeup_thresh / 8u, rsvd); + add_entropy_words(r, tmp, (bytes + 3) / 4u); credit_entropy_store(r, bytes*8); } } @@ -739,14 +739,14 @@ static size_t account(struct entropy_store *r, size_t nbytes, int min, nbytes * 8, r->name); /* Can we pull enough? */ - if (r->entropy_count / 8 < min + reserved) { + if (r->entropy_count / 8u < min + reserved) { nbytes = 0; } else { /* If limited, never pull more than available */ - if (r->limit && nbytes + reserved >= r->entropy_count / 8) - nbytes = r->entropy_count/8 - reserved; + if (r->limit && nbytes + reserved >= r->entropy_count / 8u) + nbytes = r->entropy_count / 8u - reserved; - if(r->entropy_count / 8 >= nbytes + reserved) + if(r->entropy_count / 8u >= nbytes + reserved) r->entropy_count -= nbytes*8; else r->entropy_count = reserved; @@ -781,7 +781,7 @@ static void extract_buf(struct entropy_store *r, __u8 *out) /* hash blocks of 16 words = 512 bits */ sha_transform(buf, (__u8 *)(r->pool + i), buf + 5); /* feed back portion of the resulting hash */ - add_entropy_words(r, &buf[i % 5], 1); + add_entropy_words(r, &buf[i % 5u], 1); } /* @@ -789,7 +789,7 @@ static void extract_buf(struct entropy_store *r, __u8 *out) * portion of the pool while mixing, and hash one * final time. */ - __add_entropy_words(r, &buf[i % 5], 1, data); + __add_entropy_words(r, &buf[i % 5u], 1, data); sha_transform(buf, (__u8 *)data, buf + 5); /* @@ -1040,7 +1040,7 @@ write_pool(struct entropy_store *r, const char __user *buffer, size_t count) count -= bytes; p += bytes; - add_entropy_words(r, buf, (bytes + 3) / 4); + add_entropy_words(r, buf, (bytes + 3) / 4u); } return 0; ^ permalink raw reply related [flat|nested] 39+ messages in thread
* Re: /dev/urandom uses uninit bytes, leaks user data 2007-12-15 7:13 ` Herbert Xu @ 2007-12-15 16:30 ` Matt Mackall 2007-12-17 17:28 ` Signed divides vs shifts (Re: [Security] /dev/urandom uses uninit bytes, leaks user data) Linus Torvalds 1 sibling, 0 replies; 39+ messages in thread From: Matt Mackall @ 2007-12-15 16:30 UTC (permalink / raw) To: Herbert Xu; +Cc: John Reiser, akpm, tytso, linux-kernel On Sat, Dec 15, 2007 at 03:13:19PM +0800, Herbert Xu wrote: > John Reiser <jreiser@bitwagon.com> wrote: > > > > If speed matters that much, then please recoup 33 cycles on x86 > > by using shifts instead of three divides, such as (gcc 4.1.2): > > > > add_entropy_words(r, tmp, (bytes + 3) / 4); > > > > 0x8140689 <xfer_secondary_pool+206>: lea 0x3(%esi),%eax > > 0x814068c <xfer_secondary_pool+209>: mov $0x4,%dl > > 0x814068e <xfer_secondary_pool+211>: mov %edx,%edi > > 0x8140690 <xfer_secondary_pool+213>: cltd > > 0x8140691 <xfer_secondary_pool+214>: idiv %edi > > There ought to be a warning about this sort of thing. Indeed. Seems it would be better to adjust the types appropriately. Anyway, this is no longer relevant to security@. -- Mathematics is the supreme nostalgia of our time. ^ permalink raw reply [flat|nested] 39+ messages in thread
* Signed divides vs shifts (Re: [Security] /dev/urandom uses uninit bytes, leaks user data) 2007-12-15 7:13 ` Herbert Xu 2007-12-15 16:30 ` Matt Mackall @ 2007-12-17 17:28 ` Linus Torvalds 2007-12-17 17:48 ` Al Viro 2007-12-17 17:55 ` Eric Dumazet 1 sibling, 2 replies; 39+ messages in thread From: Linus Torvalds @ 2007-12-17 17:28 UTC (permalink / raw) To: Herbert Xu Cc: John Reiser, Andrew Morton, security, tytso, Linux Kernel Mailing List, mpm, linux-sparse On Sat, 15 Dec 2007, Herbert Xu wrote: > > There ought to be a warning about this sort of thing. We could add it to sparse. The appended (untested) patch seems to say there's a lot of those signed divides-by-power-of-twos. However, the problem with such warnings is that it encourages people to do the simple fix that may be *wrong*. For example, you fixed it with patches like > - int rsvd = r->limit ? 0 : random_read_wakeup_thresh/4; > + int rsvd = r->limit ? 0 : random_read_wakeup_thresh / 4u; which is really quite dangerous for several reasons: - it depends intimately on the type of the thing being divided (try it: it will do nothing at all if the thing you divide is larger than "unsigned int", since then the "4u" will be turned into a _signed_ larger type by the C type expansion). So in general, the above doesn't even do what it's supposed to do on a 64-bit architecture if the thing to be divided is 64-bit! - it changes behaviour. If that thing really is signed and can be negative, that "trivial" patch just changed the divide to be fundamentally something totally different. so I think this patch is horribly wrong. The *correct* way to fix signed divisions is by doing one of two things: - really make the data we divide be unsigned. With all the thinking that involves! This is the good change, but it does involve making sure that there are no tests against zero and that the value really cannot go negative. Usually the unsigned types are (a) faster and (b) more robust, but if somebody is depending on signs, unsigned types are obviously not appropriate. - change a divide-by-power-of-2 into a signed shift instead. Yes, this also changes the end result for negative values, but it changes it in a sane and generally good way (ie it will still be a "valid" divide, it will just be a divide that rounds differently, and is more likely than turning it into an unsigned divide to generally result in working code). Hmm? Linus --- simplify.c | 30 ++++++++++++++++++++++++++++++ 1 files changed, 30 insertions(+), 0 deletions(-) diff --git a/simplify.c b/simplify.c index 94e14d2..91f1120 100644 --- a/simplify.c +++ b/simplify.c @@ -286,6 +286,36 @@ static int simplify_constant_rightside(struct instruction *insn) if (!value) return replace_with_pseudo(insn, insn->src2); return 0; + + case OP_DIVU: case OP_DIVS: + if (!value) + break; + if (value == 1) + return replace_with_pseudo(insn, insn->src1); + /* Power-of-two? */ + if (!(value & (value-1))) { + int log2 = -1; + do { + log2++; + value >>= 1; + } while (value); + + /* Turn unsigned divides into shifts */ + if (insn->opcode == OP_DIVU) { + insn->src2->value = log2; + insn->opcode = OP_LSR; + return 1; + } + + /* + * This is incorrect, but we care more about + * the warning than the code generation + */ + warning(insn->pos, "expensive signed divide"); + insn->src2->value = log2; + insn->opcode = OP_ASR; + return 1; + } } return 0; } ^ permalink raw reply related [flat|nested] 39+ messages in thread
* Re: Signed divides vs shifts (Re: [Security] /dev/urandom uses uninit bytes, leaks user data) 2007-12-17 17:28 ` Signed divides vs shifts (Re: [Security] /dev/urandom uses uninit bytes, leaks user data) Linus Torvalds @ 2007-12-17 17:48 ` Al Viro 2007-12-17 17:55 ` Eric Dumazet 1 sibling, 0 replies; 39+ messages in thread From: Al Viro @ 2007-12-17 17:48 UTC (permalink / raw) To: Linus Torvalds Cc: Herbert Xu, John Reiser, Andrew Morton, security, tytso, Linux Kernel Mailing List, mpm, linux-sparse On Mon, Dec 17, 2007 at 09:28:57AM -0800, Linus Torvalds wrote: > > > On Sat, 15 Dec 2007, Herbert Xu wrote: > > > > There ought to be a warning about this sort of thing. > > We could add it to sparse. The appended (untested) patch seems to say > there's a lot of those signed divides-by-power-of-twos. I'm not sure that you are warning about the right things. If you want a real nightmare scenario in that area, consider this: int x[20]; int *p = x + n; int *q = x + m; p - q ((char *)p - (char *)q)/4 ((char *)p - (char *)q)/sizeof(int) The first two are equivalent on all targets we care about. However, an attempt to make the second one "more portable" silently creates the code that'll do something entirely different as soon as we get m > n... ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: Signed divides vs shifts (Re: [Security] /dev/urandom uses uninit bytes, leaks user data) 2007-12-17 17:28 ` Signed divides vs shifts (Re: [Security] /dev/urandom uses uninit bytes, leaks user data) Linus Torvalds 2007-12-17 17:48 ` Al Viro @ 2007-12-17 17:55 ` Eric Dumazet 2007-12-17 18:05 ` Ray Lee ` (2 more replies) 1 sibling, 3 replies; 39+ messages in thread From: Eric Dumazet @ 2007-12-17 17:55 UTC (permalink / raw) To: Linus Torvalds Cc: Herbert Xu, John Reiser, Andrew Morton, security, tytso, Linux Kernel Mailing List, mpm, linux-sparse On Mon, 17 Dec 2007 09:28:57 -0800 (PST) Linus Torvalds <torvalds@linux-foundation.org> wrote: > > > On Sat, 15 Dec 2007, Herbert Xu wrote: > > > > There ought to be a warning about this sort of thing. > > We could add it to sparse. The appended (untested) patch seems to say > there's a lot of those signed divides-by-power-of-twos. > > However, the problem with such warnings is that it encourages people to do > the simple fix that may be *wrong*. For example, you fixed it with patches > like > > > - int rsvd = r->limit ? 0 : random_read_wakeup_thresh/4; > > + int rsvd = r->limit ? 0 : random_read_wakeup_thresh / 4u; > > which is really quite dangerous for several reasons: > > - it depends intimately on the type of the thing being divided (try it: > it will do nothing at all if the thing you divide is larger than > "unsigned int", since then the "4u" will be turned into a _signed_ > larger type by the C type expansion). > I was looking at lib/extable.c which does emit a signed divide on i386 but not on x86_64: mid = (last - first) / 2 + first; So I tried to compiled this on x86_64 : long *mid(long *a, long *b) { return ((a - b) / 2 + a); } It gave : mid: movq %rdi, %rdx subq %rsi, %rdx sarq $3, %rdx movq %rdx, %rax shrq $63, %rax addq %rdx, %rax sarq %rax leaq (%rdi,%rax,8), %rax ret while long *mid(long *a, long *b) { return ((a - b) / 2u + a); } gave : mid: movq %rdi, %rdx subq %rsi, %rdx sarq $3, %rdx movq %rdx, %rax shrq $63, %rax addq %rdx, %rax sarq %rax leaq (%rdi,%rax,8), %rax ret and while : long *mid(long *a, long *b) { return (((unsigned long)(a - b)) / 2 + a); } gave : mid: movq %rdi, %rax subq %rsi, %rax sarq %rax andq $-8, %rax addq %rdi, %rax ret But I found this cast ugly so I cooked this patch. [PATCH] Avoid signed arithmetics in search_extable() On i386 and gcc-4.2.{1|2}, search_extable() currently does integer divides (by 2 !!!), while we can certainly use a right shift. This looks more a typical bsearch() implementation. Signed-off-by: Eric Dumazet <dada1@cosmosbay.com> diff --git a/lib/extable.c b/lib/extable.c index 463f456..03a81bd 100644 --- a/lib/extable.c +++ b/lib/extable.c @@ -54,20 +54,20 @@ search_extable(const struct exception_table_entry *first, const struct exception_table_entry *last, unsigned long value) { - while (first <= last) { - const struct exception_table_entry *mid; + unsigned long mid, low = 0, high = (last - first); - mid = (last - first) / 2 + first; + while (low <= high) { + mid = (low + high) / 2; /* * careful, the distance between entries can be - * larger than 2GB: + * larger than MAX_LONG: */ - if (mid->insn < value) - first = mid + 1; - else if (mid->insn > value) - last = mid - 1; + if (first[mid].insn < value) + low = mid + 1; + else if (first[mid].insn > value) + high = mid - 1; else - return mid; + return first + mid; } return NULL; } ^ permalink raw reply related [flat|nested] 39+ messages in thread
* Re: Signed divides vs shifts (Re: [Security] /dev/urandom uses uninit bytes, leaks user data) 2007-12-17 17:55 ` Eric Dumazet @ 2007-12-17 18:05 ` Ray Lee 2007-12-17 18:10 ` Eric Dumazet 2007-12-17 18:23 ` Al Viro 2007-12-17 18:28 ` [Security] Signed divides vs shifts (Re: " Linus Torvalds 2 siblings, 1 reply; 39+ messages in thread From: Ray Lee @ 2007-12-17 18:05 UTC (permalink / raw) To: Eric Dumazet Cc: Linus Torvalds, Herbert Xu, John Reiser, Andrew Morton, security, tytso, Linux Kernel Mailing List, mpm, linux-sparse On Dec 17, 2007 9:55 AM, Eric Dumazet <dada1@cosmosbay.com> wrote: > - mid = (last - first) / 2 + first; > + while (low <= high) { > + mid = (low + high) / 2; I think you just introduced a bug. Think about what happens if low=high=MAX_LONG/2 + 1. ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: Signed divides vs shifts (Re: [Security] /dev/urandom uses uninit bytes, leaks user data) 2007-12-17 18:05 ` Ray Lee @ 2007-12-17 18:10 ` Eric Dumazet 2007-12-17 18:12 ` Ray Lee 0 siblings, 1 reply; 39+ messages in thread From: Eric Dumazet @ 2007-12-17 18:10 UTC (permalink / raw) To: Ray Lee Cc: Linus Torvalds, Herbert Xu, John Reiser, Andrew Morton, security, tytso, Linux Kernel Mailing List, mpm, linux-sparse On Mon, 17 Dec 2007 10:05:35 -0800 "Ray Lee" <ray-lk@madrabbit.org> wrote: > On Dec 17, 2007 9:55 AM, Eric Dumazet <dada1@cosmosbay.com> wrote: > > - mid = (last - first) / 2 + first; > > + while (low <= high) { > > + mid = (low + high) / 2; > > I think you just introduced a bug. Think about what happens if > low=high=MAX_LONG/2 + 1. > Fortunatly this is not possible :) Hint : sizeof(struct exception_table_entry) is >= 8 so high is garanteed to be <= MAX_LONG/8 ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: Signed divides vs shifts (Re: [Security] /dev/urandom uses uninit bytes, leaks user data) 2007-12-17 18:10 ` Eric Dumazet @ 2007-12-17 18:12 ` Ray Lee 0 siblings, 0 replies; 39+ messages in thread From: Ray Lee @ 2007-12-17 18:12 UTC (permalink / raw) To: Eric Dumazet Cc: Linus Torvalds, Herbert Xu, John Reiser, Andrew Morton, security, tytso, Linux Kernel Mailing List, mpm, linux-sparse On Dec 17, 2007 10:10 AM, Eric Dumazet <dada1@cosmosbay.com> wrote: > On Mon, 17 Dec 2007 10:05:35 -0800 > "Ray Lee" <ray-lk@madrabbit.org> wrote: > > > On Dec 17, 2007 9:55 AM, Eric Dumazet <dada1@cosmosbay.com> wrote: > > > - mid = (last - first) / 2 + first; > > > + while (low <= high) { > > > + mid = (low + high) / 2; > > > > I think you just introduced a bug. Think about what happens if > > low=high=MAX_LONG/2 + 1. > > > > Fortunatly this is not possible :) > > Hint : sizeof(struct exception_table_entry) is >= 8 > > so high is garanteed to be <= MAX_LONG/8 Ah, my bad. One of these days I'll learn to not post before coffee. ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: Signed divides vs shifts (Re: [Security] /dev/urandom uses uninit bytes, leaks user data) 2007-12-17 17:55 ` Eric Dumazet 2007-12-17 18:05 ` Ray Lee @ 2007-12-17 18:23 ` Al Viro 2007-12-17 18:28 ` [Security] Signed divides vs shifts (Re: " Linus Torvalds 2 siblings, 0 replies; 39+ messages in thread From: Al Viro @ 2007-12-17 18:23 UTC (permalink / raw) To: Eric Dumazet Cc: Linus Torvalds, Herbert Xu, John Reiser, Andrew Morton, security, tytso, Linux Kernel Mailing List, mpm, linux-sparse On Mon, Dec 17, 2007 at 06:55:57PM +0100, Eric Dumazet wrote: > long *mid(long *a, long *b) > { > return ((a - b) / 2 + a); > } ... is not actually a middle (you'd want b-a, not a-b there), but anyway > It gave : > mid: > movq %rdi, %rdx > subq %rsi, %rdx > sarq $3, %rdx > movq %rdx, %rax > shrq $63, %rax > addq %rdx, %rax > sarq %rax > leaq (%rdi,%rax,8), %rax > ret > > while > > long *mid(long *a, long *b) > { > return ((a - b) / 2u + a); > } ... undefined behaviour if a < b > and while : > > long *mid(long *a, long *b) > { > return (((unsigned long)(a - b)) / 2 + a); > } undefined behaviour, again. ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [Security] Signed divides vs shifts (Re: /dev/urandom uses uninit bytes, leaks user data) 2007-12-17 17:55 ` Eric Dumazet 2007-12-17 18:05 ` Ray Lee 2007-12-17 18:23 ` Al Viro @ 2007-12-17 18:28 ` Linus Torvalds 2007-12-17 19:08 ` Al Viro 2 siblings, 1 reply; 39+ messages in thread From: Linus Torvalds @ 2007-12-17 18:28 UTC (permalink / raw) To: Eric Dumazet Cc: security, tytso, Herbert Xu, John Reiser, Linux Kernel Mailing List, linux-sparse, mpm, Andrew Morton On Mon, 17 Dec 2007, Eric Dumazet wrote: > > while > > long *mid(long *a, long *b) > { > return ((a - b) / 2u + a); > } This is exactly what I'm talking about. That "2u" is TOTALLY POINTLESS. It's an "unsigned int", but since (a-b) will be of type ptrdiff_t, and is *wider* on a 64-bit architecture (it's the same as "long" on x86-64), then the 2u will just be converted to "long", and be signed again! So you thought that you did an unsigned divide, but you did no such thing. If you change the "2u" to a "2ul", it works again, and you get mid: movq %rdi, %rax subq %rsi, %rax sarq %rax andq $-8, %rax addq %rdi, %rax ret which is the code you wanted. But quite frankly, you could just have written it with a shift to start with, and avoided the subtle type issue, although gcc then generates movq %rdi, %rax subq %rsi, %rax sarq $4, %rax leaq (%rdi,%rax,8), %rax ret instead. Of course, this all *does* still have subtle sign issues, because the "a-b" part implies a signed divide in itself, which is why you see that "sarq" in he first place (rather than a "shrq"). Signed divides are hard. The "a-b" pointer subtraction is actually cheaper than a general signed divide by sizeof, since the compiler can then assume that the two pointers are mutually aligned, which is why gcc can generate just a single "sarq" instead of having to do an extra "add negative bit" thing to get the rounding right. [ So Al, when you said that (a-b) is equivalent to ((char *)a-(char *)b)/4 for a "int *" a and b, you're right in the sense that the *result* is the same, but the code generation likely isn't. The "a-b" thing can (and does) allow the compiler to avoid the whole "align up for signed numbers" thing, and the difference in code generation is clear: subq %rsi, %rdi sarq $2, %rdi vs subq %rsi, %rdi leaq 3(%rdi), %rax testq %rdi, %rdi cmovs %rax, %rdi sarq $2, %rdi exactly because the first case *knows* that the low two bits have to be zero, and thus there is no rounding issue. ] Linus ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [Security] Signed divides vs shifts (Re: /dev/urandom uses uninit bytes, leaks user data) 2007-12-17 18:28 ` [Security] Signed divides vs shifts (Re: " Linus Torvalds @ 2007-12-17 19:08 ` Al Viro 0 siblings, 0 replies; 39+ messages in thread From: Al Viro @ 2007-12-17 19:08 UTC (permalink / raw) To: Linus Torvalds Cc: Eric Dumazet, security, tytso, Herbert Xu, John Reiser, Linux Kernel Mailing List, linux-sparse, mpm, Andrew Morton On Mon, Dec 17, 2007 at 10:28:38AM -0800, Linus Torvalds wrote: > [ So Al, when you said that > > (a-b) > > is equivalent to > > ((char *)a-(char *)b)/4 > > for a "int *" a and b, you're right in the sense that the *result* is > the same, but the code generation likely isn't. The "a-b" thing can (and Sure. And yes, I very much do prefer code that uses C as it ought to be used and doesn't play games with casts from hell, etc. For a lot of reasons, both correctness- and efficiency-related. We _do_ have such turds. In spades. And such places are potential timebombs, since well-intentioned idiotic patch ("I've read in lecture notes that sizeof is better than explicit constant, so replacement surely can only improve the things and the best part is, I don't need to understand what I'm doing") turns an ugly FPOS into equally ugly FPOS that silently doesn't work ;-/ [sorry about the rant, I'm about 3/4 through the drivers/net colonoscopy, with >300Kb of patches and a pile of assorted bugs so far - and then there's drivers/scsi to deal with. Endianness stuff, mostly...] ^ permalink raw reply [flat|nested] 39+ messages in thread
* /dev/urandom uses uninit bytes, leaks user data @ 2007-12-15 7:20 Matti Linnanvuori 2007-12-15 7:54 ` Valdis.Kletnieks 0 siblings, 1 reply; 39+ messages in thread From: Matti Linnanvuori @ 2007-12-15 7:20 UTC (permalink / raw) To: linux-kernel From: Matti Linnanvuori <mattilinnnvuori@yahoo.com> /dev/urandom use no uninit bytes, leak no user data Signed-off-by: Matti Linnanvuori <mattilinnnvuori@yahoo.com> --- --- a/drivers/char/random.c 2007-12-15 09:09:37.895414000 +0200 +++ b/drivers/char/random.c 2007-12-15 09:12:02.607831500 +0200 @@ -689,7 +689,7 @@ static ssize_t extract_entropy(struct en */ static void xfer_secondary_pool(struct entropy_store *r, size_t nbytes) { - __u32 tmp[OUTPUT_POOL_WORDS]; + static __u32 tmp[OUTPUT_POOL_WORDS]; if (r->pull && r->entropy_count < nbytes * 8 && r->entropy_count < r->poolinfo->POOLBITS) { Machen Sie Yahoo! zu Ihrer Startseite. Los geht's: http://de.yahoo.com/set ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: /dev/urandom uses uninit bytes, leaks user data 2007-12-15 7:20 /dev/urandom uses uninit bytes, leaks user data Matti Linnanvuori @ 2007-12-15 7:54 ` Valdis.Kletnieks 0 siblings, 0 replies; 39+ messages in thread From: Valdis.Kletnieks @ 2007-12-15 7:54 UTC (permalink / raw) To: Matti Linnanvuori; +Cc: linux-kernel [-- Attachment #1: Type: text/plain, Size: 802 bytes --] On Fri, 14 Dec 2007 23:20:30 PST, Matti Linnanvuori said: > From: Matti Linnanvuori <mattilinnnvuori@yahoo.com> > > /dev/urandom use no uninit bytes, leak no user data > > Signed-off-by: Matti Linnanvuori <mattilinnnvuori@yahoo.com> > > --- > > --- a/drivers/char/random.c 2007-12-15 09:09:37.895414000 +0200 > +++ b/drivers/char/random.c 2007-12-15 09:12:02.607831500 +0200 > @@ -689,7 +689,7 @@ static ssize_t extract_entropy(struct en > */ > static void xfer_secondary_pool(struct entropy_store *r, size_t nbytes) > { > - __u32 tmp[OUTPUT_POOL_WORDS]; > + static __u32 tmp[OUTPUT_POOL_WORDS]; This looks like a race waiting to happen - what lock is held so we don't have 'tmp' smashed by 2 instances on different CPUs (not a problem when each instance lives on a hopefully separate stack)? [-- Attachment #2: Type: application/pgp-signature, Size: 226 bytes --] ^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: /dev/urandom uses uninit bytes, leaks user data @ 2007-12-15 22:44 linux 0 siblings, 0 replies; 39+ messages in thread From: linux @ 2007-12-15 22:44 UTC (permalink / raw) To: jreiser, linux-kernel; +Cc: linux, tytso >> There is a path that goes from user data into the pool. This path >> is subject to manipulation by an attacker, for both reading and >> writing. Are you going to guarantee that in five years nobody >> will discover a way to take advantage of it? Five years ago >> there were no public attacks against MD5 except brute force; >> now MD5 is on the "weak" list. > Yep, I'm confident about making such a guarantee. Very confident. For the writing side, there's a far easier way to inject potentially hostile data into the /dev/random pool: "echo evil inentions > /dev/random". This is allowed because it's a very specific design goal that an attacker cannot improve their knowledge of the state of the pool by feeding in chosen text. Which in turn allows /dev/random to get potential entropy from lots of sources without worrying about how good they are. It tries to account for entropy it's sure of, but it actually imports far more - it just don't know how much more. One of those "allowed, but uncredited" sources is whatever you want to write to /dev/random. So you can, if you like, get seed material using wget -t1 -q --no-cache -O /dev/random 'http://www.fourmilab.ch/cgi-bin/Hotbits?fmt=bin&nbytes=32' 'http://www.random.org/cgi-bin/randbyte?nbytes=32&format=f' 'http://www.randomnumbers.info/cgibin/wqrng.cgi?limit=255&amount=32' 'http://www.lavarnd.org/cgi-bin/randdist.cgi?pick_num=16&max_num=65536' I don't trust them, but IF the data is actually random, and IF it's not observed in transit, then that's four nice 256-bit random seeds. (Note: if you actually use the above, be very careful not to abuse these free services by doing it too often. Also, the latter two actually return whole HTML pages with the numbers included in ASCII. If anyone knows how to just download raw binary, please share.) ^ permalink raw reply [flat|nested] 39+ messages in thread
end of thread, other threads:[~2007-12-27 10:44 UTC | newest] Thread overview: 39+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2007-12-14 19:34 /dev/urandom uses uninit bytes, leaks user data John Reiser 2007-12-14 20:13 ` Matt Mackall 2007-12-14 20:45 ` John Reiser 2007-12-14 23:23 ` Theodore Tso 2007-12-15 0:30 ` John Reiser 2007-12-15 4:32 ` Theodore Tso 2007-12-17 16:30 ` John Reiser 2007-12-17 17:36 ` Theodore Tso 2007-12-18 0:52 ` Andy Lutomirski 2007-12-18 3:05 ` Theodore Tso 2007-12-18 3:13 ` David Newall 2007-12-18 3:46 ` Theodore Tso 2007-12-18 4:09 ` David Newall 2007-12-18 4:23 ` Theodore Tso 2007-12-19 22:43 ` Bill Davidsen 2007-12-19 22:40 ` Bill Davidsen 2007-12-20 4:18 ` Andrew Lutomirski 2007-12-20 20:17 ` Phillip Susi 2007-12-21 16:10 ` Andrew Lutomirski 2007-12-22 1:14 ` Theodore Tso 2007-12-26 18:30 ` Phillip Susi 2007-12-20 20:36 ` Theodore Tso 2007-12-27 10:44 ` Pavel Machek 2007-12-18 5:12 ` David Schwartz 2007-12-17 20:59 ` David Schwartz 2007-12-15 7:13 ` Herbert Xu 2007-12-15 16:30 ` Matt Mackall 2007-12-17 17:28 ` Signed divides vs shifts (Re: [Security] /dev/urandom uses uninit bytes, leaks user data) Linus Torvalds 2007-12-17 17:48 ` Al Viro 2007-12-17 17:55 ` Eric Dumazet 2007-12-17 18:05 ` Ray Lee 2007-12-17 18:10 ` Eric Dumazet 2007-12-17 18:12 ` Ray Lee 2007-12-17 18:23 ` Al Viro 2007-12-17 18:28 ` [Security] Signed divides vs shifts (Re: " Linus Torvalds 2007-12-17 19:08 ` Al Viro 2007-12-15 7:20 /dev/urandom uses uninit bytes, leaks user data Matti Linnanvuori 2007-12-15 7:54 ` Valdis.Kletnieks 2007-12-15 22:44 linux
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).