Re: /dev/urandom uses uninit bytes, leaks user data

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
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

Relevant Pages

  • Re: Fortuna
    ... Execution time for entropy output is not a major ... seed to start an efficient seed-using extractor. ... So the second pool is dumped in every 2 rounds, ... > attacker, and kept secret until you receive data from the source. ...
    (Linux-Kernel)
  • Re: [PROPOSAL/PATCH] Fortuna PRNG in /dev/random
    ... The Fortuna patch I've submitted tried to achieve this "more than 256 bits per ... pool" by carrying forward the digest output to the next pool. ... for the current /dev/random and Yarrow with entropy estimators as well. ... entropy into Fortuna compared to the output gathered by an attacker would ...
    (Linux-Kernel)
  • Re: Fortuna
    ... * the pool, the output data is totally unpredictable. ... "We're never going to give an attacker the unicity ... (thereby reducing output entropy), or to use the SHA1 feedback to induce ... you wrote the thing in the first place; is my summary of the goals ...
    (Linux-Kernel)
  • Re: Fortuna
    ... > Waiting for 256bits of entropy before outputting data is a good goal. ... > pool to aggravate the predictability of where entropy goes. ... Yes, the attacker *does* know! ... use that information to infer the seeds added to the not-selected ...
    (Linux-Kernel)
  • [PROPOSAL/PATCH] Fortuna PRNG in /dev/random
    ... Fortuna is an attempt to avoid the need for entropy estimation. ... Entropy estimation is very difficult, but not doing it leads to problems. ... adding one bit of seed material doesn't hurt an attacker who can look ... of the pool, an attacker can never get enough output to compute a unique ...
    (Linux-Kernel)