EDP (entropy distribution protocol), userland PRNG design

[Jack Lloyd]

On Tue, Oct 18, 2005 at 12:18:57AM -0500, Travis H. wrote:
> >
> >  source(s) --> mixer --> pool --> extractor --> X9.31
> 
> Where can I find out more about the design choices for these stages?

Peter Gutmann has several good papers on RNG design, as have some folks
currently or formerly associated with Counterpane (ie Wagner, Kelsey, Hall,
...). It is worth reading their analysis papers as well as their design papers,
especially the ones that cover fielded PRNG designs.

> > I believe most common hardware RNGs produce data at fairly high rates, often
> > over 100 kbytes per second.
> 
> Some do, some don't.  Depends on the random source they are tapping.

Of course. I was just pointing out that there are many that do produce at that
rate. Since you weren't specific, I assumed it was a COTS hardware RNG.

> However, that's a sealed opaque package, so I don't fully trust it. 
> I've been wondering if there's a way I could use it such that I didn't
> have to fully trust it.  For example, if I could combine several, so
> that an effective attack would require collusion of several parties.

That does not seem very difficult: just sample all of them. As long as your
PRNG is good, an attacker won't be able to do anything by only controlling a
subset of them.

> 
> > 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.
> 
> That seems like a very ad-hoc system that treats the HWRNG and
> random-looking system data as somehow different (one is used for 90%
> of the samples, one for 10%).

Sorry, I should have been a little more clear. That 1/10 split was only
supposed to be an example. You would presumably determine the appropriate
sample rate based on an analysis of the system statistics. It is just as you
mentioned, "oversampling won't help you generate random bits any faster; you
will get more bits but no more randomness." You should sample each possible
source so as to reach some maximum; presumably you either want to maximize
total entropy over time, or total entropy over bits sampled, or maybe total
entropy over # of samples. In any case, it's highly likely that alternating
between reading 160 bits from a good HWRNG and the SHA1 hash of the output of
`ps` is not going to produce any such maxiumum.

The point of my suggestion was not that you implement those specific steps, but
that you desing your PRNG so that it can make the best use of an arbitrary
number of entropy sources with various (known or estimated) distributions. This
ties in well with the previous point about using multiple HWRNGs.

> 
> > 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. [...]
> > At not point do the two sides actually exchange messages,
> 
> I don't follow.  I'm transmitting entropy from the source to where it
> is needed; surely this is a message of some kind?

But that is all you are moving - entropy. As best as I could tell from your
original proposal, the two sides never actually shared a key. So while one side
was encrypting stuff and the other side was decrypting, at no point were they
actually exchanging information.

[...]

> 
> > 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 SSL, right?

Yes.

> 
> Transmitting over SSL would limit the strength to the minimum of the
> strength of the asymmetric and symmetric ciphers.  Using my method
> alone would not involve PK, so would be faster, need less entropy to
> start with, and also the upper bound on strength is the same or
> higher.  What I'm saying is that a chain is only as strong as its
> weakest link, and my protocol has one less link.

However, I don't see how you are protecting the confidentiality of the data at
all in your current design. I was not suggesting TLS as an alternative, but as
a method of achieving what you (apparently?) meant to do. However, if you could
perhaps clarify what you meant with regards to encrypting the data that is
transferred, that might help - I may well have simply misread you. In
particular, how do the two sides agree on an initial key?  I'm afraid I don't
see how it is possible for two parties to use the same key starting out with no
shared knowledge and without any public key operations.

> > 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.
> 
> For anyone who is interested, here is a link:
> http://www.hifn.com/info/candp/Boardpartners.html

Thanks for the link - I only knew about the Soekris boards.

-J

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