NetNews Usenet Archive 1992 #16/NN_1992_16.iso/spool/sci/crypt/2741

Text File | 1992-07-25 | 4.5 KB | 89 lines

Newsgroups: sci.crypt
Path: sparky!uunet!cs.utexas.edu!hermes.chpc.utexas.edu!jonathan
From: [e-mail] (Jonathan Thornburg)
Subject: "random generator" passwords (was: Re: Keeping track of a lot of passwords)
Message-ID: <[e-mail]>
Summary: random number generators produce *highly* *insecure* passwords
Keywords: password choose random number generator pattern insecure break
Sender: [e-mail] (Jonathan Thornburg)
Organization: U of Texas at Austin / Physics Dept / Center for Relativity
References: <[e-mail]> <[e-mail]> <[e-mail]>
Date: Sun, 26 Jul 92 07:26:31 GMT
Lines: 75

In article <[e-mail]> [e-mail]
(Hari Seldon) writes [I *think* have the multi-level attribution
right here, if not and I'm misattributing anything, please forgive me]:
>... i wrote a small rng to
>get new ones [passwords] with.
>and the code for it all is in a wierd jumping off
>point in the hh. [handheld computer] so you need to know where to
>jump to to start the thing.
>it's not perfect but it helps.
>i'd considered putting it in my sons pc jr but some day .....

Using a random number generator (RNG) to generate passwords is
almost always a very bad idea -- it yields *highly* *insecure*
passwords.  There are two reasons for this:

(1) The set of passwords your "small rng" can produce is at most
    the number of possible internal states in the RNG.  For a
    typical RNG this at most 2**32 (= 4 billion), and sometimes
    only 64K.  Either is far too small, and could easily be
    exhaustively searched.  The classic (1978) Bell System Technical
    Journal on Unix Password Security describes a successful
    attack of this sort (on a pre-Unix system).

(2) Even if you use an RNG with a large internal state space,
    it will still probably produce passwords which can be easily
    broken.  The problem is that to produce good crypto keys
    (which is essentially what you're trying to do), you need
    a stream of "random numbers" which is *cryptographically*
    strong, not just "random" in statistical sense.  The difference
    here is that cryptographically strong random streams are
    (ideally) *unpredictable* even given complete knowledge of
    the output so far, i.e. the next password is unpredictable
    even given knowledge of all your past passwords.

    In contrast, normal "statistically good" RNGs (i.e. all those
    in common use, all those in Knuth v.2, all those which those
    of us lacking in extensive crypto training are likely to come
    up with) may have good randomness properties (but does your
    "small rng" pass the spectral test described by Knuth?),
    but their relatively simple internal structure (*) makes
    their future output relatively easy to predict from a knowledge
    of even a few past outputs.

    For example, for the commonly-used linear congruential
    random number generators, Knuth has an excercise showing
    how knowing any K consecutive "random number" outputs
    suffices to determine the internal state, and hence all
    future outputs.  K here is some small integer, I think 3.
    In other words, anyone knowing 3 (say) consecutive passwords
    produced by such an RNG could break the RNG and thereafter
    be able to know all future RNG outputs.

    Your implementation may contain special safeguards against
    these and other similar problems, but there are murky waters
    here -- key generation is *hard*, and computers don't like
    to produce "truly random" (high-entropy) outputs.

(*) Note that complicating the RNG internal structure without an
    underlying theory to guide you will almost certainly make
    matters *worse*.  Knuth explains why relatively simple RNGs
    are probably the best for most (non-crypto) uses -- we can
    theoretically analyze their behavior and *prove* they're
    "statistically random".  In contrast, Knuth also explains
    why and how "random number generators chosen at random" are
    almost always very bad, and gives a truly horrifying/astonishing
    example.

Remembering multiple cryptographically-independent-and-high-entropy
passwords is a hard problem, but using a "small rng" to generate them
is not the solution.

- Jonathan Thornburg
  <[e-mail]> or <[e-mail]>
  University of Texas at Austin / Physics Dept / Center for Relativity
  and (for a few more months) U of British Columbia / {Astronomy,Physics}