Newsgroups: sci.crypt
Path: cactus.org!milano!cs.utexas.edu!convex!news.utdallas.edu!hermes.chpc.
+ utexas.edu!jonathan
From: jonathan@chpc.utexas.edu (Jonathan Thornburg)
Subject: distilling random numbers (was: Re: IBM-PC random generator, source
+ included)
Message-ID: <1992Jun27.014023.13094@chpc.utexas.edu>
Followup-To: jonathan@einstein.ph.utexas.edu
Summary: DES is *good* so long as you're not trying to stop governments
Keywords: random bits generate improve cryptographic hash MD5 DES distill
Sender: jonathan@einstein.ph.utexas.edu
Organization: U of Texas at Austin / Physics Dept / Center for Relativity
References: <2808@accucx.cc.ruu.nl> <1992Jun26.080402.27283@ncar.ucar.edu>
+ <1992Jun26.231556.4588@cactus.org>
Date: Sat, 27 Jun 92 01:40:23 GMT
Lines: 77
The context here is that we have a source of "semirandom" bits,
and we'd like to some how get some "really random" bits from them.
I and a couple of others have suggested using the "semirandom" bits
as inputs to a good modern cryptosystem like MD5 or DES, and taking
the output as our hopefully "really random" bits.
In article <1992Jun26.231556.4588@cactus.org> ritter@cactus.org
(Terry Ritter) writes:
> 2. Simply because some complex process somehow converts 384
> bits to 128 bits is no reason to believe that it has somehow
> captured the "essential" randomness in any special way.
>
> If we want every bit of the output to depend on every
> bit of the input we could use CRC's.
>
> 3. If "holographic smear" is, by itself, a virtue, it's
> easy enough to transform to some other domain with FFT,
> Walsh-Hadamard, or related transformations. Then we can
> "distill it down" by using a subset of the output.
> However, I see no reason to believe that data which are
> mostly structured are going to be less structured in a
> transformed domain.
>
> The problem with MD5 is that we know very little about
> the technology used to create it, and, thus, the limits
> and dangers of using that technology to produce a hash.
>
> We have a similar problem with DES, and that is almost
> two decades old. Yes, these transformations look complex,
> but that is part of the problem. Their complexity may just
> make it difficult for us to *see* their weaknesses.
I disagree with 2. Assuming that the original semirandom bits
have a structure that could be crytographically analyzed, then
we want to scramble that structure enough so that analyzing
the output of our "improver" will be too hard for our cryptographic
opponent. CRC does a lot less scrambling than a good hashing
or cipher algorithm like MD5 or DES respectively.
I also disagree with part of 3. I'm not sure about MD5, but
I'd certainly agree that we don't know how DES was designed,
and that the NSA (*) presumably do know. Therefore I would consider
DES to be inadequate for the present purpose if I were trying to get
random bits which the NSA couldn't cryptographically "unrandomize".
(I.e., given the past 10**12 bits from my "random" stream, and
any other "anciliary" information about my computer they might
happen to have handy, can they say anything useful about the next
N bits, for any useful value of N).
But, if you're worrying about the NSA unrandomizing your bits,
they you can probably afford a *real* radioactive or thermal-noise
or whatever random number generator. (Even the NSA can't fudge
the 2nd law of thermodynamics!) Therefore, I think it's reasonable
to say that this whole thread is aimed at a lower degree of security.
And I would argue that for any degree of security where your
cryptographic opponents are smaller than (say) a rather large corporation,
that DES is a *superb* cipher, and that MD5 is probably a *superb*
cryptographic hashing function. I'm quite willing to grant weaknesses
in either which the NSA could climb through, but that's not what
we're talking about here. These systems have both been around
long enough to have been attacked by a lot of pretty good people.
The fact that (so far as I know) they're as yet unbroken (modulo
differential cryptoanalysis for DES, which isn't yet "practical")
suggests that they're strong systems.
For DES we also have additional evidence that it's strong -- banks
are using it for *large* wire transfers, in the $100Ms and up. If
DES weren't secure against any but the NSA, I'm sure the NSA would
have quietly lobbied the American Banker's Association not to adopt
it as a standard for this type of use.
- Jonathan Thornburg
***** temporary alternate addr *****
University of Texas at Austin / Physics Dept / Center for Relativity
and (for a few more months) University of British Columbia / Astronomy