EDP (entropy distribution protocol), userland PRNG design

[Jack Lloyd]

On Wed, Oct 12, 2005 at 04:49:43AM -0500, Travis H. wrote:
> I am thinking of making a userland entropy distribution system, so
> that expensive HWRNGs may be shared securely amongst several machines.
[...]
> Comments?
> --
> http://www.lightconsulting.com/~travis/  -><-
> "We already have enough fast, insecure systems." -- Schneier & Ferguson

I can't say I a fan of the idea of having multiple ways of mixing entropy into
the system. In particular, the idea of producing output by XORing your PRNGs
output with the output of a semi-public RNG seems like a bad idea to me,
because an attacker can easily control those values by taking over the web
server or modifying packets in the network, and if they can somehow predict
your PRNG outputs then they will be able to actually control the final output.
The difference between knowing and controlling the PRNG output is a big deal
when you're using it for something like DSA.

I prefer a multi-stage design, as described by various people smarter than I
am:

  source(s) --> mixer --> pool --> extractor --> X9.31

Take the sources, mix it into an entropy pool and then use an extraction
function to derive values from the pool. Then use the values of that to seed a
X9.31 PRNG and produce the final output with that (with the DT values also
being generated by the extractor function). That helps make sure that even if
you make a mistake with the extractor and/or mixer function you still have some
level of protection. For example, even if an attacker can correctly guess every
16th bit of your extractor function, it will still be very difficult for them
to guess the final PRNG outputs. I've found that it is much easier to think
about the two functions as distinct, so you can reason about what specific
properties you want or need the mixer and extractor to have, and it also makes
it simpler to replace one or the other to make different security/speed
tradeoffs.

I believe most common hardware RNGs produce data at fairly high rates, often
over 100 kbytes per second. If you have one of those you'll be able to get much
more entropy from that than you will out of regular system sources, especially
as the entropy of those samples usually decreases pretty strongly after the
first sample or two, while the HWRNG keeps producing entropy at the same rate.
Instead of treating the two entropy sources as somehow different in your mixing
strategy, just use the HWRNG for most of the inputs, but every tenth sample (or
whatever), instead use the hash of all the random-looking system data you can
get ahold of. Only doing it occasionally means there is a reasonable chance
that sufficient changes have happend to the system since the sample worthwhile
in terms of entropy gained, and doing a large block of it all at once prevents
iterative guessing attacks if an attacker can control your HWRNG outputs but
not your system statistics.

Encrypting the output using keys generated by the PRNG is a good idea, but you
presented it in a somewhat confusing way, in that it sounded almost like you
were doing message transfer. Then I realized you're not actually doing that at
all, just a postprocessing (or preprocessing, in the case of the recipient)
operation using a randomly keyed block cipher (which the X9.31 RNG would also
provide nicely). At not point do the two sides actually exchange messages, so
in this situation, your mention of key distribution is somewhat misleading. If
you want to try to keep the entropy values sent from the box with the HWRNG to
the client a secret from people on the network, just open up a TLS session. TLS
is cheap if you use session resumption, and with self-signed certificates or
anonymous DH there is no key distribution. It makes bootstrapping a little more
difficult, but presumably the client can get at least some entropy via the
traditional means currently available on common platforms.

You could also just solve the problem you mention directly, and try to find a
cheaper HWRNG design. I know people who have built them for a few dollars worth
of stuff at Radio Shack, and apparently VIA, Intel, and AMD have all found them
cheap enough at various times to ship them included in components they've built
at little or no extra cost. You can buy a PCI board with a low-end Hifn crypto
chip on it for less than $80 online.

-Jack

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com