On 2/19/06, Brett Lymn <blymn@baesystems.com.au> wrote:
> Regardless, it would be a Good Idea (tm) to perform some of the FIPS
> tests to ensure the RNG hardware at least looks functional rather than
> accepting a continuous stream of 0's (or 1's) as being "random".  I
> don't mean do this continuously but from memory there are some startup
> tests defined by FIPS that are designed to detect malfunctioning
> RNG's.

I'd like to see the ability to export the data _as close to the source
as possible_
for testing.  For example, they should not pass through a von Neumann corre=
ctor,
as this would throw off DC bias estimates while introducing
sequential dependence of bits.

One of the things Terry Ritter mentioned when evaluating the Atom Age HWRNG
(my page on it http://www.lightconsulting.com/~travis/atom_age/) is
that we should take the *analog noise* and digitize it and do
autocorrelation.  By passing it through a single-bit A/D, you're
throwing away data that might be useful to recognize a pattern which
is present though obscured in the digital data.  I'm sure you can
imagine such a thing.

Thor sez:
> Is it really the case that output from a hardware
> source should only be fed into the software mixing function if the raw
> HW output passes the tests?

Well, you shouldn't update the entropy count by as much if it fails.=20
I think that it is okay to hash together possibly-predictable data and
the pool contents, since if it isn't predicted then you may recover
from a state compromise, and each bit of the hash output is dependent
on about half the input bits, so unless an attacker knows the previous
state *and* the fresh input, he still has virtually nothing to say
about the new state.  In fact, I am in favor of a userland daemon
which periodically polls some of these web sites that deliver "random"
bits, under the assumption that even if observed, you're not any worse
off mixing them in, as long as you don't update the entropy counts.

> It is certainly appropriate to run the statistical test on the _output_
> of the software RNG, however.

Even the first-order rand(3) would pass most statistical tests, yet it
is clearly a very poor PRNG, much less a HWRNG.  Any sort of hashing
or encryption will fool most tests which do not explicitly invert the
hash or encryption.  That's how they are designed -- hashes and
encryption destroy structure.  Any which did not would not be suitable
for cryptographic purposes.

You definitely want to test as close to the source as possible.=20
Anything else is like putting on a blindfold before taking an eye
exam.  *You* may not be able to predict the next letter, but that
doesn't mean the doctor is equally impaired.

Schneier had some neat ideas in fortuna, the successor to Yarrow.  One
involved a 5-bit binary counter and 5 pools of entropy; you hashed
together the pools whose number indicates a set bit in the counter.=20
That means pool 5 is hashed for reseeds number 2^4 through (2^5)-1.=20
Basically the idea is like the slow and fast pools, only with 5 levels
instead of 2; hopefully the 5th pool will have enough entropy that the
reseed recovers from state compromise.  On the down side, there's no
net-accessible paper (only in the book Practical Cryptography) and his
implementation of the pools uses hashes; however, since entropy will
be added very frequently and often at interrupt time, updating SHA-1
hashes with new input may be a bad idea.  Perhaps there is some
lighter-weight function, like the current pool taps, that could be
combined with heavier processing when random bits are needed.

Basically I think the /dev/random interface is in need of a
crypto-engineering solution.  The current system just isn't nearly as
mature as some other parts of the kernel, like process scheduling,
where careful tradeoffs have been made between optimal behavior and
efficiency, backed by careful measurements and benchmarks.

See also this:
http://www.aculei.net/~shardy/bcard/talks/bhe04-paper.pdf

It describes extractors, which can take really-random and
weakly-random bits and make almost-random (e-close to uniform) bits.

A lot of these statistical tests would be challenging to do in the
kernel due to lack of floating point.  I wonder how much of the
mechanism actually needs to be in the kernel, and how much could be
pulled out into a userland daemon, where development could proceed
much more quickly and in overflow-safe languages, at least until a
good compromise had been made, at which point we could pull the
relevant functionality back into the kernel, where it could not be as
easily read, swapped out to disk, or subject to the same amount of
latency due to scheduler delays.

SHA-1 over a large pool is a fairly expensive way to generate 160
random bits.  I get about 1MB/s on my slow P3 system.  I think
something like yarrow might be better for high-volume (e.g.
randomizing disk surfaces).

I am also worred about the difference in semantics between OSes.  For
example, in FreeBSD, /dev/random gives pseudorandom bits, whereas on
Net/OpenBSD, it gives really random bits.  How is userland software
supposed to tell if they are really random or not?  Basically it's
back to version-tracking the /dev/random driver with respect to
testable features like the OS release, which I think is a lot of work
and prone to error (reminds me of OS fingerprinting).  There should be
some fool-resistant way of requesting bits to the desired strength.=20
Exactly what that would look like is a bit of a mystery to me at this
time.
--
Security Guru for Hire http://www.lightconsulting.com/~travis/ -><-
GPG fingerprint: 50A1 15C5 A9DE 23B9 ED98 C93E 38E9 204A 94C2 641B