From: "Theodore Ts'o" <tytso@MIT.EDU>
Date: Tue, 31 Oct 1995 07:47:22 +0800
To: Mark Murray <mark@grondar.za>
Subject: Re: /dev/random for FreeBSD [was: Re: /dev/random for Linux]
In-Reply-To: <199510302148.XAA00832@grumble.grondar.za>
Message-ID: <9510302225.AA25562@dcl.MIT.EDU>
MIME-Version: 1.0
Content-Type: text/plain


   Date: Mon, 30 Oct 1995 23:48:24 +0200
   From: Mark Murray <mark@grondar.za>

   > Secondly, making /dev/random only readable by "privileged programs"
   > means that people won't be able to compile their own version of PGP that
   > can take advantage of the random number generator.  Instead, they would
   > have to use a setuid version of PGP, and I'm quite sure PGP wasn't
   > written such that it would be safe to turn on its setuid bit.  

   How about SetGID? We were going for 660 root.kmem.

Bad idea; anyone who can run PGP could then get instant access to kmem

	cd /tmp
	ln -s /dev/kmem foo
	pgp -e tytso foo
	rm foo
	pgp foo.pgp

   > Again, /dev/random can be set to whatever permissions the system
   > administrator wants.  Secondly, writing to /dev/random merely adds
   > randomness to the pool, via the mixing algorithm.  It won't actually
   > permit people to *set* the state of the pool, and assuming that the
   > state of the pool is not known before the write operation, writing to it
   > won't allow the user to know what the state is after the write
   > operation.

   What happens if some attacker does:

   for (;;) {
	   write_to_devrandom(NULL);
	   check_to_see_if_state_is_crackable();
   }

   ? "Gut feel" suggests to me that large ammounts of "predicted" input might
   be worse than the normal sort of system noise you have been using.

But keep in mind that what we're doing is XOR'ing the input data into
the pool.  (Actually, it's a bit more complicated than that.  The input
is XOR'ed in with a CRC-like function, generated by taking an
irreducible polynomial in GF(2**128).  But for the purposes of this
argument, you can think of it as XOR.)  So since you don't know what the
input state of the pool is, you won't know what the output state of the
pool.

Also, you never get to see the actual state of the pool, even when you
read out numbers from /dev/random.  What you're getting is a *hash* of
the pool.  So if you can actually implement
check_to_see_if_state_is_crackable(), then you've found a weakness in
MD5 (or SHA, to which I'll probably be switching in the near future).

   > And, for race condition reasons, something which I need to implement
   > soon is an ioctl(), usuable only by root, that simultaneously updates
   > the entropy estimate *and* submits data to be mixed into the pool.  (Why
   > this is necessary should be obvious after a few minutes thought.)

   Clue me in - I'm not quite with you? :-)

Consider this scenario:

1)  Process one writes randomness to /dev/random.

2)  Process two immediately consumes a large amount of randomness using
/dev/urandom, so that the effective randomness is now zero.

3)  Process two uses the ioctl() to bump the entropy count by the amount
of randomness added in step 1.  Unfortunately, that entropy was already
consumed in step 2.

   > I didn't say that it would be trivial for an attacker to do this, but
   > it's certainly *doable*.  Some of the network traffic analyzers that
   > have been made available (I think Sandia National Labs has one that does
   > this), records down to millisecond accuracy when a packet was sniffed on
   > the network.  

   Is this millisecond accuracy quantifiable in terms of bits of entropy?
   if so, the ethernet is surely safe?

Well, no.  If you're only using as your timing the 100Hz clock, the
adversary will have a better timebase than you do.  So you may be adding
zero or even no bits of entropy which can't be deduced by the adversary.

This is even worse in the PGP keyboard timing case, since the adversary
almost certainly can find a better time resolution to measure your
incoming packets when compared to the timing resolution that most
programs have.  Far too many Unix systems only make a 100Hz clock
available to the user mode, even if you have a better quality high
resolution timing device in the kernel (for example, the Pentium cycle
counting register).

   Again, if you can quantify the number of possibilities into bits of entropy,
   your code is good. Depending on current technology, this may have to change.

The problem is that in order to do this requires making assumptions
about what the capabilities of your adversary are.  Not only does this
change over time, but certain adversaries (like the NSA) make it their
business to conceal their capabilities, for precisely this reason.

So I like to be conservative and use limits which are imposed by the
laws of physics, as opposed to the current level of technology.  Hence,
if the packet arrival time can be observed by an outsider, you are at
real risk in using the network interrupts as a source of entropy.
Perhaps it requires buidling a very complicated model of how your Unix
scheduler works, and how much time it takes to process network packets,
etc.  ---- but I have to assume that an adversary can very precisely
model that, if they were to work hard enough at it.

People may disagree as to whether or not this is possible, but it's not
prevented by the laws of physics; merely by how much effort someone
might need to put in to be able to model a particular operating system's
networking code.  In any case, that's why I don't like depending on
network interrupts.  Your paranoia level may vary.

						- Ted