[1779] in cryptography@c2.net mail archive
Re: Random numbers (fwd)
daemon@ATHENA.MIT.EDU (Raph Levien)
Thu Oct 30 14:40:05 1997
Date: Thu, 30 Oct 1997 09:14:15 -0800 (PST)
From: Raph Levien <raph@acm.org>
To: cryptography@c2.net
I posted this yesterday to coderpunks. Perry suggested forwarding it to
cryptography, so here it is:
On Wed, 29 Oct 1997, Bruce Schneier wrote (to coderpunks):
> At 2:39 PM -0600 10/29/97, Steve Schear wrote:
> >John Walker, of Autodesk fame has an interesting and eclectic site. Among
> >the items of cryptographic interest is HotBits
> >http://www.fourmilab.ch/hotbits
[blurb deleted]
> Is this serious, or is this a joke. If it's serious, it's really funny.
I'm going to vote for serious. Keep in mind that not all uses of random
numbers are cryptographic - true random numbers may be useful for
simulations and other scientific applications, as well.
There are warnings on the page against using the random numbers for
cryptography or security. This seems to make it less likely that it's a
joke.
As for the idea of using a Geiger-Muller tube to generate random numbers,
that's not a joke at all. Perry Metzger wrote a post a couple of years
ago, if I recall correctly, advocating this method if you _really_ care
about the numbers being random. To summarize his main points:
1. You can calculate the entropy rate from first principles using fairly
simple physics. It's very unlikely that the estimate would ever have to
be significantly revised.
2. It should be easy to detect silent failure, a serious problem with
other sources of randomness (oops, the bulb in the lavalamp burned out
again).
3. It would be hard for an attacker to degrade the amount of entropy - a
serious concern with techniques like using Ethernet packet timing.
4. It is very easy to verify that the system is working end to end. Take
the radioactive source away from the tube and watch the pulse rate
decrease, then increase again when you replace the source.
Of course, when using these numbers for cryptography, you need a private
and authentic channel from the random bits to your application. That's
something that HotBits does not provide. But they're not claiming to.
Raph
P.S. I do believe that the name of the service is a joke.
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Note added later:
I looked more carefully at the HotBits implementation, and notice that it
lacks property 3. If you imagine an attacker shooting individual rays of
his own timing at the Geiger tube, then it's pretty easy to decrease the
entropy. Walker's implementation compares the two intervals induced by
three pulses. If the first interval is shorter, you get a 0, otherwise a
1. One advantage is that you get a rock-solid entropy estimate assuming an
unbiased source: one half bit per pulse. The disadvantage is that if an
attacker sent pairs of pulses with alternately short and long intervals,
you'd seriously get to bias the bit stream.
For protection against such an attacker, I think the best solution is to
hash the raw output of the counter. However, this gets into issues of
whether we trust the hash function to preserve the entropy. I haven't
worked out the specifics, but I believe that the requirement for such a
hash function is considerably weaker than what's needed for (eg) digital
signatures. As I see it, the output of the hash function has to have a
uniform distribution if the input has a sufficient amount of entropy. I
haven't worked out the details, but my hunch is that either a bucket hash
or a XOR MAC can be proven to have this property (citations [Bucket95] and
[XORMac95] on http://wwwcsif.cs.ucdavis.edu/~rogaway/papers/list.html).
Use with care!
Raph
