[373] in Kerberos
a possible attack on Kerberos.
daemon@TELECOM.MIT.EDU (Bill Sommerfeld)
Tue Apr 26 19:40:58 1988
From: Bill Sommerfeld <wesommer@ATHENA.MIT.EDU>
To: kerberos@ATHENA.MIT.EDU
Cc: John Leo <leo@ATHENA.MIT.EDU>
One possible attack on Kerberos could involve being able to predict
the random number generator used by the KDC to create session keys.
In particular, the `rand()' random number generator is not very good;
the low order bit is not really random. `random()' is better, but not
available on non-BSD systems. System V includes a `rand48()' which is
supposedly better than `random()'; however, it isn't available on
Berkeley Unix..
It might make a lot of sense to do a portable implementation of the
algorithm described in the paper referred to in this posting and
include it in the distribution.
Of course, if you _really_ wanted to produce good random numbers for
session keys, you'd hook up a radioisitope and geiger counter to the
KDC...
- Bill
(this is truncated from the posting, so I don't overfill everyone's
mailbox..)
From bloom-beacon!athena.mit.edu!leo Tue Apr 26 19:26:34 EDT 1988
Article 1154 of sci.crypt:
Path: bloom-beacon!athena.mit.edu!leo
>From: leo@athena.mit.edu (Oblivious Transfer)
Newsgroups: sci.math,sci.crypt
Subject: pseudo-random number generation
Message-ID: <4898@bloom-beacon.MIT.EDU>
Date: 26 Apr 88 22:49:28 GMT
Sender: daemon@bloom-beacon.MIT.EDU
Reply-To: leo@athena.mit.edu (Oblivious Transfer)
Organization: Massachusetts Institute of Technology
Lines: 278
Xref: bloom-beacon sci.math:3624 sci.crypt:1154
For those interested, the following is the introduction to the
Blum-Micali paper on pseudorandom number generation. Although the paper
is rather difficult reading, the introduction is fairly easy to follow
and quite enjoyable. I have included the numbered references, but not
mentioned what they are; also notation has been made TeX-like for
precision. Hopefully there are not too many typos.
John Leo
leo@xx.lcs.mit.edu
leo@athena.mit.edu
******
Siam Journal of Computing, Volume 13, Number 4, November 1984
(pages 850-864)
How to Generate Cryptographically Strong Sequences of Pseudo-random Bits
Manuel Blum and Silvio Micali
ABSTRACT: We give a set of conditions that allow one to generate 50-50
unpredictable bits.
Based on those conditions, we present a general algorithmic scheme for
constructing polynomial-time deterministic algorithms that stretch a
short secret random input into a long sequence of unpredictable
pseudo-random bits.
We give an implementation of our scheme and exhibit a pseudo-random
bit generator for which any efficient strategy for predicting the next
output bit with better thant 50-50 chance is easily transformable into
an "equally efficient" algorithm for solving the discrete logarithm
problem. In particular, if the discrete logarithm problem cannot be
solved in probabilistic polynomial time, no probabilistic
polynomial-time algorithm can guess the next output bit better than by
flipping a coin: if "head" guess "0", if "tail" guess "1".
KEY WORDS. randomness, pseudo-random number generation,
unpredictability, random self-reducibility
