[7294] in cryptography@c2.net mail archive
Re: random seed generation without user interaction?
daemon@ATHENA.MIT.EDU (Arnold G. Reinhold)
Sun Jun 11 16:03:47 2000
Mime-Version: 1.0
Message-Id: <v04210104b5694765eb34@[24.218.56.92]>
In-Reply-To: <l03110708b56545c63ca9@[208.192.102.55]>
Date: Sun, 11 Jun 2000 10:34:47 -0400
To: Don Davis <dtd@world.std.com>, cryptography@c2.net
From: "Arnold G. Reinhold" <reinhold@world.std.com>
Content-Type: text/plain; charset="iso-8859-1" ; format="flowed"
Content-Transfer-Encoding: quoted-printable
At 12:12 PM -0400 6/8/2000, Don Davis wrote:
>steve b., perry m., and arnold r. all point out,
>quite correctly, that hashing was used for noise-
>whitening, long before sgi's lavarand and before
>my disk-randomness paper. the difference that
>sgi's work and mine offered was a more rigorous
>notion of randomness. by explicitly drawing on
>the strict mathematical definition of "chaos," we
>could call our generators' outputs random per se.
>thus, chaos-based rngs go beyond prior work on
>noise-whitening, but the difference is perhaps
>more important theoretically than practically.
I don't want to disparage Don's contribution in any way, but it is my=20
non-lawyer understanding that patents are awarded to the person who=20
first comes up with an idea, not the person who first provides a=20
rigorous underpinning for that idea.
As for SGI, their patent defines chaos as follows: "A chaotic system=20
is one with a state that changes over time in a largely unpredictable=20
manner." That is hardly "the strict mathematical definition."
>
>both generators produced truly unpredictable bits,
>though SGI & i differed in our statistical criteria.
>my experiment produced asymptotically i.i.d. uniform
>bits, while lavarand produced _effectively_ uniform
>bits. in other words, both SGI and i offered truly
>random bits, and not merely securely unpredictable
>bits. note the contrast with prior work: while
>arnold's DoD citation from 1985 does offer a
>practical & effective way to seed a PRNG, the doc't
>explicitly calls the product bits "pseudo-random."
I think it is important not to let the meaning of term=20
"pseudo-random" degenerate into "less than perfectly random." It has=20
a very specific, widely accepted meaning. For example, RFC-2828=20
defines "pseudo-random" as:
" A sequence of values that appears to be random (i.e.,=20
unpredictable) but is actually generated by a deterministic=20
algorithm."
There are applications where a PRNG may be preferable to a source of=20
true random numbers, for example in Monte-Carlo analyses where it=20
desirable to be able to repeat any given calculation.
Both the DOD Password guidelines and the SGI patent envision using a=20
random quantity to seed a PRNG which is then used to provide multiple=20
instances of cryptographic constants, passwords in the DOD=20
guidelines, passwords and cryptographic keys in the SGI patent. (What=20
the SGI patent refers to as a "random number generator" is really a=20
PRNG.)
>
>our/my novel contribution was to justify dropping
>the prefix "pseudo-". afaik, before my paper,
>noone spoke of software "TRNGs". no-one believed
>it was possible to produce truly random bits
>without specialized hardware, though many of us
>knew that hashing or encrypting an irregular or
>secret input was necessary & sufficient for most
>cryptographic purposes.
>
> - don davis, boston
I think most researchers were reluctant to use the term "truly=20
random" because it is such a strong assertion and because there is a=20
fair amount of disagreement as to the proper definition of=20
"random."=A0 However, some people did speak of possibility of producing=20
true random bits. For example, here is a quote from: PGP(tm) User's=20
Guide Volume I: Essential Topics by Philip Zimmermann Revised 22=20
May 94: (PGP 2.6)
"The public/secret key pair is derived from large truly random numbers
derived mainly from measuring the intervals between your keystrokes
with a fast timer. "
PGP hashes a large number of timing values to produce those bit. I=20
suspect the same quote can be found in earlier editions.
Arnold Reinhold
