cvs commit: src/sys/modules/random Makefile src/sys/dev/random randomdev.h randomdev_soft.c randomdev_soft.h yar

[Nate Lawson]

On Sat, 10 Apr 2004, Mark Murray wrote:
> Bruce M Simpson writes:
> > > > http://www.cryptography.com/resources/whitepapers/index.html
> > >
> > > Actually, I have. I read it again, now, to be sure. Nothing it says
> > > suggests that what I did here is a "huge mistake". Nearest I get is
> > > the suggestion that the output from the on-chip RNG is used as a
> > > source for a hash function (like Yarrow). I feel that is overkill,
> > > and that the output of the on-chip RNG is sufficient.
> >
> > I'm inclined to trust your judgement here on this, Mark, but Nate does
> > have a valid point; we need to be sure that the entropy sources are of
> > sufficiently high quality or we risk compromising the system.
> >
> > If you could cite some independent tests for the VIA C3 on-chip RNG
> > that would be very helpful to all.
>
> How about Nate's paper? It gives the VIA C3 a very high assessment WRT
> the quality of the entropy delivered.
>
> If it is felt that further whitening of the VIA C3 RNG is needed,
> then I believe that Yarrow would be overkill, and that a much smaller
> hash function will be sufficient.

I have thought very carefully before responding and realized that there
are two issues that need to be addressed:  the attitude behind your
approach and the actual technical problems with it.  Unfortunately,
contractual issues limit what I can say about security, but I've been
involved with both the design and analysis of a number of hardware RNGs
and PRNG constructions since 1996.  FYI, I'm not a main author of the VIA
whitepaper.  Also, I appreciate you implementing the RNG driver and think
it would be a good source for seeding our PRNG.

One point a lot of talks given by Cryptography Research have made is the
question of strength vs. assurance.  We define strength as a system's
security against known attacks.  One intuitive example of this is key
length.  Everyone can understand how a 128 bit key is stronger than a 56
bit key.  We define assurance as a system's resistance to attacks that
were unknown or unexpected when it was designed.  Assurance is much harder
to get than strength and harder to reason about.  In real world attacks,
the issue is nearly always one of a failure in assurance, not strength.
As an example, WEP can be used with a 128 bit (actually 104 bit) key but
it wasn't successfully broken by a brute force attack on the key.  It was
a use of the cipher in a way that voids its warranty and compromised it,
no matter what key length was used.

This relates directly to your decision to disable the PRNG when this
hardware entropy source is available and use it directly.  It is
perplexing that you have chosen to go against years of research and
established practice by avoiding the PRNG in this case with no research of
your own.  Your response is statements that the hardware source is
"sufficient" and that a PRNG is "overkill".  Also, you indicate that
nothing in the paper above says your approach is a huge mistake even
though it does explicitly recommend use of a PRNG.

This approach is inherently and unnecessarily low assurance.  Assurance
isn't gained by going it on your own and hoping things are good enough.
History has rewarded a realistic approach to security, with careful study
to back up claims.  A sobering point is that about 50% of the
peer-reviewed ciphers proposed at CRYPTO each year are broken within a
year, some at the informal rump session during the same conference.  What
should that say about a non-peer-reviewed change that goes against
established research in PRNGs?  How much assurance does that have?

The actual technical problems with this are numerous and instead of
repeating them all here, read section 5.2 of our paper where we recommend
the hardware source be used to seed a PRNG and other papers like
"Cryptanalytic Attacks on Pseudorandom Number Generators" by Kelsey et al.
For one, temporal correlation in the source is more visible without a
PRNG.  Also, since /dev/random output is used for both public (i.e.
sequence numbers) and private (i.e. keys) purposes, it is especially
important to use entropy from as many sources as possible with a proper
PRNG construction.  Good PRNGs provide features like fast recovery from a
complete pool compromise that a hardware source alone is not intended to
provide.

For those not familiar with the particulars, I think the VIA hardware
entropy source when properly configured and used is a good way to
contribute entropy to a PRNG.  I also think the CRI whitepaper gives good
examples how to properly use it.

-Nate