[505] in Kerberos
Re: random_key()
daemon@TELECOM.MIT.EDU (Steve Miller)
Tue Sep 13 16:30:35 1988
From: miller%erlang.DEC@DECWRL.DEC.COM (Steve Miller)
To: kerberos@ATHENA.MIT.EDU, MILLER%erlang.DEC@DECWRL.DEC.COM
The problem of generating truly random and secret keys without a hardware
random number generator is difficult. Using a pseudo-random number
generator, the problem is reduced to providing a truly random seed that is
secret, i.e. can't be guessed. Most systems, such as the Unix or Ultrix
systems used for Kerberos, do not have much system "noise" to create a
good random seed. "Noise" can take the form of low order bits of the time
of day, system resource utilization, etc.
In the experiment reported by Ted Anderson, I believe that the system
noise used by the existing random_key routine was further minimized by
the nature of the experiment-- iterating random_key in a tight loop.
In the environment for which it was targeted, that is the Kerberos server,
there would be more variability than in such an experiment. This does not
suggest that the existing technique is good however. We did run some tests
of at least 10000 keys to verify that it was at least minimally adequate.
The reason we kept changing the seed was to prevent attacks where you would
get a key, then try to search the random number generator output until you
found the matching key, which could be done without exorbitant computation.
My documentation on random claims a period of 16*((2**31)-1).
Then, if a match was found, the attacker has a free lunch of subsequent
"random" keys.
A better solution, as Ted suggested, is to take the random number, or
even just a sequence number, and encrypt it under a secret key. While the
random_key code notes this in a comment, for reasons I don't recall it was
never implemented. Maybe we didn't want to require the presence of a
secret key to produce a random key.
Steve.
