The upshot of this is that /dev/random becomes non-exportable.

Date: Sat, 07 Aug 1999 22:44:35 -0500
To: tytso@mit.edu, cryptography@c2.net
From: John Kelsey <kelsey.j@ix.netcom.com>
Subject: linux-ipsec: Re: Summary re: /dev/random
Cc: cryptography@c2.net, daw@cs.berkeley.edu, linux-ipsec@clinet.fi
In-Reply-To: <199908022214.SAA00759@rsts-11.mit.edu>
References: <37A47E0E.5EB7939A@sympatico.ca>
 <Pine.LNX.4.04.9907261011150.30088-100000@ultra.gawth.com>
 <199907261413.HAA22696@proxy3.ba.best.com>
 <4.1.19990728194141.009213b0@popd.ix.netcom.com>
 <37A47E0E.5EB7939A@sympatico.ca>
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Sender: owner-linux-ipsec@clinet.fi

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

>Date: Mon, 2 Aug 1999 18:14:30 -0400
>To: cryptography@c2.net
>Subject: Re: Summary re: /dev/random
>From: tytso@mit.edu

[ Much deleted ]

>Yarrow is different.   It uses a 160 bit pool, and as such
>is much more dependent on the strength of the cryptographic
>function. Hence, the two stage design is much more
>important.  It also doesn't use a block cipher, BTW.  It
>just uses a an interated hash function such as SHA, at least
>the last time I looked at the Counterpane paper.

The next version (called Yarrow-160) will use a block cipher
for output generation, and a hash function for entropy
collection. We have a draft paper up on the website, and I'm
giving a talk on it at SAC in a couple days.  Before, we
were relying upon an ad-hoc design based on SHA1 for output
generation, for exportability reasons; we moved to 3DES
because we basically wanted to settle any arguments about
the security of the generating function.

>As such, I don't really believe the second stage design part
>of Yarrow is really necessary for /dev/random.  Does it add
>something to the security?  Yes, but at the cost of relying
>more on the crypto hash, and less on the entropy collection
>aspects of /dev/random, which is as far as I'm concerned
>much more important anyway.

I guess I'd evaluate this a little differently.  I think
generating good random-looking outputs, once we have 100 or
so bits of entropy, is easy.  On the other hand, I think
correctly estimating the entropy you're collecting in your
pool is quite hard.  It looks to me like /dev/random's
design makes the opposite set of assumptions:  I can get
plenty of entropy, and correctly estimate how much I have
got.  But I don't know how to do cryptographic pseudorandom
number generation.

Now, here's the problem:  I look at cryptographic primitives
for generating pseudorandom bit sequences from short keys or
seeds, and I see lots of solid-looking proposals.  I see
algorithms that people are already building systems around,
and that years of cryptanalysis have failed to dent.  I feel
like the problem is pretty well understood, and that, in
engineering terms, it's more-or-less solved.  We can argue
about whether we want to use 3DES-OFB, 3DES-counter, RC4,
SHA1-counter, that weird SHA1-OFB-ish mode we used for the
current version of Yarrow, or whatever else, but I don't
have any doubts that we can do this.  I am comfortable
relying on these primitives.

Then I look at estimating the entropy from each of the
possible sources on a PC running Windows or Linux.  I can
find some tools to do this, but I don't have a lot of
confidence I'm not missing something.  I have to worry about
all kinds of weird special cases--diskless workstations, PCs
with no user at them, fresh out of the box system
configurations, etc.  I don't see this as a solved
engineering problem, I see it as an interesting research
problem. *That* is the set of beliefs that led to the Yarrow
design.

Let's talk about iterative guessing attacks.  Everyone seems
to assume they can only happen if an attacker can either get
physical access to the box, or can get root.

The best way to implement the iterative guessing attack is
at the very beginning, when the pool has only (say) 50 bits
of entropy, but the software *thinks* it has a few hundred
bits of entropy.  If the PRNG starts outputting bytes at
this point, and an attacker is able to record the outputs from
this box, the attacker can spend some time to break the
initial state of the PRNG at the time of the first output.
He can then carry on the iterative guessing attack forward,
for as long as he has outputs being spun out faster than
entropy is coming in.  Now, something like /dev/random makes
an entropy estimate of how fast entropy is coming in, and at
least tries to limit its outputs.  But it's easy for an
estimate of this kind to be too high--entropy estimation is
hard to do well in all cases.  My claim is that if a
generator like /dev/random falls behind early enough for the
initial state to be guessed, and outputs keep being used
quickly, then the generator never recovers.

Now, I haven't looked closely at the design of /dev/random,
so I may be missing something.  Is there something that
would protect it from this class of attack, if it were
overestimating the entropy collected by a, say, a factor of
two or three?

>If Free S/WAN really wants the second stage design, I will
>observe that the second stage can be done entirely in user
>space.  Just use /dev/random or /dev/urandom as the first
>stage, and then simply use an iterated SHA (or AES candidate
>in MAC mode --- it really doesn't matter) as your second
>stage, periodically doing the catastrophic reseed by
>grabbing more data from /dev/random.  This gives you all of
>the benefits (speed of key generation, no worry about DOS
>attacks by depleting entropy --- by mostly ignoring the
>problem) and drawbacks (over-dependence on the crypto
>function) of Yarrow.

True.  This isn't hard at all.  Wait 'till /dev/random
reports a full pool (if you can do that), and then use it to
generate a two-key 3DES key, and use that to initialize the
ANSI X9.17 key generator.  Rekey ANSI X9.17 whenever the
pool thinks it's full.  Modulo some assumptions about
/dev/random's entropy estimation, that handles the iterative
guessing attack.

>						- Ted

>P.S. PGP's random number generator is similar to Linux's,
>and is similarly quite different from Yarrow.   Probably the
>best thing to say is that philosophically quite different. I
>don't really believe we have enough analysis tools to say
>which one is "better".

It looks to me like /dev/random, and the PGP and Cryptlib
PRNGs are all kind-of built on the assumption that there
will probably be enough entropy to generate all the output
bits we need (and we'll be able to tell if there is that
much or not), and if not, these PRNGs are designed to
hopefully give good pseudorandom outputs.  On the other
hand, Yarrow, and ANSI X9.17's key generator, and RSAREF's
PRNG, and the DSA PRNG, are all build on the assumption that
entropy is hard to get, and so we want to essentially take a
hundred or so bits of seed, maybe with occasional additional
entropy along the way, and use it to generate lots of
pseudorandom outputs.

Now, if you need truly random bits, the /dev/random approach
might look better.  After all, you're just distilling
entropy there, right?  But the security of the whole
scheme, and especially the question of whether its
outputs are random or merely pseudorandom, is based on the
quality of entropy estimation being done.  I claim this is
shakier ground than the strength of a cryptographic
mechanism.

   --John Kelsey, Counterpane Systems
     E-mail: kelsey@plnet.net // kelsey@counterpane.com
     PGP 2.6 fingerprint: 5D91 6F57 2646 83F9 6D7F 9C87 886D 88AF

-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 5.5.3i for non-commercial use <http://www.pgpi.com>

iQCVAwUBN6z8XiZv+/Ry/LrBAQEVYwQAgjcmeDCiaqKRGrpbIiACkytHF/A6vY+f
hyK9fmMiAiHTehI2prs8Wew6qNsMh4edcz19Ny42hMdAtGHj+o7GCigFAwabc0Mb
xRoYnpAIzmkSDEuZwz6RJoBbnaLILpisn56urzE0wrqQRx/Qc5VuuJcDffQaEE8O
rbLL/+wv8KE=
=3cyc
-----END PGP SIGNATURE-----