Re: /dev/random for FreeBSD [was: Re: /dev/random for Linux]

>    Date: Mon, 30 Oct 1995 20:16:24 +0200
>    From: Mark Murray <mark@grondar.za>
> 
>    A colleague drew my attention to this, and I was so pleased with it that
>    I ported it to FreeBSD.
> 
> Which version did you grab?  More recent versions of the driver use a
> more efficient mixing algorithm suggested by Colin Plum.  There's also
> the beginnings of support for user-mode deamons to add randomness into
> the random pool by writing to /dev/random.  I also added support for
> reading the instruction timing register for x86 platforms that support
> it. 

Version 0.92 21st Sept 1995.

Something I didn't mention earlier; we felt that letting the unwashed
masses read /dev/*random was not a good idea, as they could deplete
the pool of entropy all to easily for attack purposes. For the same
(or similar) reason, giving the said unwashed masses _write_ privelige
might allow them to set /dev/*random to a known state. You've probably
already thought of this, but I just had to say it :-).

>    2) We felt that hooking all interrupts might be dangerous. IDE drives can
>    interrupt at a heck of a rate, and so can some serial ports, and we felt
>    that in these cases _not_ using the interrupt was a good idea. So I
>    added an ioctl to allow the superuser to select his own set, appropriate
>    to the hardware in use. It is nearly impossible to do this automatically.
> 
> Indeed; I can't emphasize this enough.  The clock interrupt, for
> example, is a very bad irq to try to use.  In the Linux driver, only
> device drivers who register their interrupt driver with the
> SA_SAMPLE_RANDOM flag actually have the interrupt timings sampled for
> the random number generator.

(Hmm.. Thinks of ways of doing something similar. I'm not functioning too
well right now.)

> People have suggested using making it possible to select at run-time
> which interrupts to sample, instead of at compiling it into the device
> drivers.  I've generally not been convinced this is a good idea, because
> most system administrator won't likely know which irq's are good and
> which are bad for random number generation.  For example, although it
> may not be obvious, the network interrupt may not be a good choice,
> since an adversary who is monitoring the ethernet cable can make a
> pretty good guess about the timing of your network interrupts, and hence
> what the likely inputs are to the random number pool might be.

Are you sure about this? The stochastisity if this would be pretty
hefty. Not only would our attacker have to get the _time_ that the
interrupt occurred (if it interrupted our machine), he would then have
to process in brute-force mode all possible times in his error range.
What is more, more interrupts are coming in...

>    Gimme a yell if you want copies :-)
> 
> Sure, why not.   I'd be interested to see what you did.

Hokay! Please also send me _your_ latest. (BTW - did Linus put it in
his latest kernel?)

M
--
Mark Murray
46 Harvey Rd, Claremont, Cape Town 7700, South Africa
+27 21 61-3768 GMT+0200
Finger mark@grumble.grondar.za for PGP key

Date: Mon, 30 Oct 1995 21:25:50 +0200
   From: Mark Murray <mark@grondar.za>

   Version 0.92 21st Sept 1995.

Yup, there's a more recent version in the Linux tree at this point.

   Something I didn't mention earlier; we felt that letting the unwashed
   masses read /dev/*random was not a good idea, as they could deplete
   the pool of entropy all to easily for attack purposes. 

That should be a system administration issue.  If someone wants to make
/dev/random readable only by root at their site, that's their business.
I don't see any point in trying to enforce that in the kernel code.

I don't agree that restricting read access is useful.  First of all, if
the pool of entropy is depleted, someone who tries to obtain entropy by
reading /dev/random will know that they didn't get enough entropy.  So
assuming a program that actually checks return values from system calls,
this is at worse a denial of service attack, and there are much easier
ways of performing those srots of attacks: "while (1) fork()", for
example.

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.  

Finally, even if you did have trustworthy applications which you could
setuid and only allow those programs to have access to /dev/random,
someone who repeatedly ran those applications could still end up
depleteing the pool of entropy.

So in the general case I would advise that /dev/random be left world
readable, since you *do* want general user programs to have access to
high quality random numbers.  

   For the same (or similar) reason, giving the said unwashed masses
   _write_ privelige might allow them to set /dev/*random to a known
   state. You've probably already thought of this, but I just had to say
   it :-).

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.

The ioctl() which sets the entropy estimate, however, *does* need to be
runnable only by the superuser, however, since that does represent an
attack path.

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

   > For example, although it
   > may not be obvious, the network interrupt may not be a good choice,
   > since an adversary who is monitoring the ethernet cable can make a
   > pretty good guess about the timing of your network interrupts, and hence
   > what the likely inputs are to the random number pool might be.

   Are you sure about this? The stochastisity if this would be pretty
   hefty. Not only would our attacker have to get the _time_ that the
   interrupt occurred (if it interrupted our machine), he would then have
   to process in brute-force mode all possible times in his error range.
   What is more, more interrupts are coming in...

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.  

For this reason, people shouldn't really trust initializing PGP's random
number generator over a network connection, since it is possible for an
adversary to obtain very high quality timings of when your telnet or
rlogin packets appeared on the network, and hence be able to guess
(within some error range) what the interkeyboard timings which PGP used
to initialize its random number generator.

The adversary might have to try a large number of possibilities, but if
the number of possibilities is less than a brute-force search, you
definitely have a weakness --- a fact which Netscape learned to its
embarassment a few weeks ago.

   Hokay! Please also send me _your_ latest. (BTW - did Linus put it in
   his latest kernel?)

Yup.  1.1.34 and higher has most of my changes.  (I'm still making
changes which are still in development, though.  Mostly incremental
improvements of one sort or another.)

							- Ted

-----BEGIN PGP SIGNED MESSAGE-----

In article <199510301925.VAA27116@grumble.grondar.za>,
Mark Murray <mark@grondar.za> wrote:
> Something I didn't mention earlier; we felt that letting the unwashed
> masses read /dev/*random was not a good idea, as they could deplete
> the pool of entropy all to easily for attack purposes.

That's really just a DOS attack, isn't it?  An application that needs
true randomness should be using /dev/random, which you can slow but not
disturb, and an application that is using /dev/urandom should be ok with
less than full entropy.

-----BEGIN PGP SIGNATURE-----
Version: 2.6.2

iQCVAwUBMJVTqeyjYMb1RsVfAQGqYwP/W6xUdsxwCMrWlvmuPrfV4yfaYpZWt3JW
/ld8HsqyQt5XRkbNwq/hcXDle13exEaqzXe2l6qHtR3qySEaU/4WF/BgSTwqpQa+
iA6p8KL51XPluNF9oagMrmOR2J4yxMPldrx5m/+WcZRJj4mdfzxQoMQ9J4agTVsC
l2spGY8iNkA=
=9cfz
-----END PGP SIGNATURE-----
-- 
Shields.