Random password generation

Random password generation

Post by Johnny Kw » Sun, 23 Jan 1994 02:32:13



Recently I read a newspaper article which mentioned that a
random pronouncable password generation algorithm has been developed
from NIST (National Institute of Standards and Technology) and
the government is going to adopt such algorithm for generation
of passwords. Does anyone know if the source for such password
generation program available for public use?
If yes, where can I get it?

Johnny Kwan
Office of Telecommunication Services
University of Texas System
Austin, Texas

 
 
 

Random password generation

Post by Andrew Bu » Mon, 24 Jan 1994 00:45:12



Quote:>Recently I read a newspaper article which mentioned that a
>random pronouncable password generation algorithm has been developed
>from NIST (National Institute of Standards and Technology) and
>the government is going to adopt such algorithm for generation
>of passwords. Does anyone know if the source for such password
>generation program available for public use?

Just a note of caution on randomly generated passwords...

The quality of your random password generation will depend almost entirely
on the quality of your random number generator.  For example, if you seed
your generator, as many of us have probably done for simplicity,
srandom(getpid()), you are actually limiting yourself to a list of
roughly 30,000 possible passwords (since Unix pids roll over at 30,000).
srandom(time(NULL)&0xffff) gives 64K unique passwords, etc.

Further, assuming one can generate a better seed, if one uses a 32bit
random value for a seed, you still only have 2^32 (~2 billion) possible
seeds/passwords (many of which may come out duplicates because of the
algorithm trying to make it pronounceable).  This is only 1% of the potential
2^11 (26^8) 8-char single-case alpha passwords.

Indeed, limiting oneself to 8-char single-alpha *pronounceable* passwords
may cut this down quite a bit in itself, no matter how good the rng is.

I haven't seen this NIST doc, but I hope it addresses this issue.

(One could also increase the potency by inserting a special char or
whatnot, but I'd hate to see a federal guideline that makes cracking easier.)
--


"But if he was dying he wouldn't bother to carve "Aaaaargh", he'd just say it."

 
 
 

Random password generation

Post by Earl Killi » Wed, 26 Jan 1994 09:09:03


I use a program that uses the time between keystrokes to provide its
randomness.  It runs a generator (with 1643 bits of state) continuously
and generates the next character every time I type a key.
--
Earl A. Killian

USPS: Quantum Effect Design, 2670 Seeley Road, San Jose, CA 95134
--
Earl A. Killian

USPS: Quantum Effect Design, 2670 Seeley Road, San Jose, CA 95134
 
 
 

Random password generation

Post by Bob Bos » Sun, 30 Jan 1994 09:34:55




>>Recently I read a newspaper article which mentioned that a
>>random pronouncable password generation algorithm has been developed
>>from NIST (National Institute of Standards and Technology) and
>>the government is going to adopt such algorithm for generation
>>of passwords. Does anyone know if the source for such password
>>generation program available for public use?
>Just a note of caution on randomly generated passwords...
>The quality of your random password generation will depend almost entirely
>on the quality of your random number generator.  For example, if you seed
>your generator, as many of us have probably done for simplicity,
>srandom(getpid()), you are actually limiting yourself to a list of
>roughly 30,000 possible passwords (since Unix pids roll over at 30,000).
>srandom(time(NULL)&0xffff) gives 64K unique passwords, etc.
>Further, assuming one can generate a better seed, if one uses a 32bit
>random value for a seed, you still only have 2^32 (~2 billion) possible
>seeds/passwords (many of which may come out duplicates because of the
>algorithm trying to make it pronounceable).  This is only 1% of the potential
>2^11 (26^8) 8-char single-case alpha passwords.
>Indeed, limiting oneself to 8-char single-alpha *pronounceable* passwords
>may cut this down quite a bit in itself, no matter how good the rng is.
>I haven't seen this NIST doc, but I hope it addresses this issue.
>(One could also increase the potency by inserting a special char or
>whatnot, but I'd hate to see a federal guideline that makes cracking easier.)
>--

A further note of caution: none of these schemes provides any protection
from replay attacks of the type that permeate the Internet. If your
network includes broadcast segments, or allows access from any net
that does, you should consider some form on non-replayable authentication
system instead.

Regards,

--

Bob Bosen
Enigma Logic Inc.
2151 Salvio St. #301
Concord, CA   94520
USA

Tel: +1 510 827-5707

**************************************************************************
* "It wasn't me!!! Somebody must have captured my username/password!!!"  *
**************************************************************************

 
 
 

Random password generation

Post by Tom Perri » Thu, 10 Feb 1994 05:18:16




   Newsgroups: comp.security.unix
   Date: 6 Feb 94 04:40:02 GMT
   Organization: HomeVax

   : >>Recently I read a newspaper article which mentioned that a
   : >>random pronouncable password generation algorithm has been developed

Actually, the first such generator was the PhD thesis of Roger Schell,
U.S. Air Force, in 1967 or so.  It was implemented in Multics.

   Sorry for getting in on this late, and also for munging the attributions.
   Y'all might want to go look at the discussion that Marcus just started
   about cracking passwords using a dictionary of common digraphs.

Almost any pronouncable passwd generation alog will be succeptible to a
digraph/trigraph attack.  As soon as the alogorithm and the n-graph
list is published, you have exactly what you need to generate the
ditcionary and/or patterns.

   I used a pronouncable password generator on a VAX, and it seemed to me
   that the method of making them pronouncable was by pulling random di-
   or tri- graphs from a list, and concatenating them.  This would make
   them very suceptable to the cracker that Marcus contemplates.

   --

--

San Diego Supercomputer Center |   FAX: +1 619 534-5152
P. O. Box 85608                | I'm not cynical, I just have a
San Diego CA 92186-9784        | fine appreciation of reality.

 
 
 

Random password generation

Post by Paul A. Karg » Fri, 11 Feb 1994 02:23:00


Some corrections on the history of password generators:

(I have cross-posted to alt.os.multics as well.)


|>

|>    Newsgroups: comp.security.unix
|>    Date: 6 Feb 94 04:40:02 GMT
|>    Organization: HomeVax
|>
|>    : >>Recently I read a newspaper article which mentioned that a
|>    : >>random pronouncable password generation algorithm has been developed
|>
|> Actually, the first such generator was the PhD thesis of Roger Schell,
|> U.S. Air Force, in 1967 or so.  It was implemented in Multics.
|>
|>    Sorry for getting in on this late, and also for munging the attributions.
|>    Y'all might want to go look at the discussion that Marcus just started
|>    about cracking passwords using a dictionary of common digraphs.
|>
|> Almost any pronouncable passwd generation alog will be succeptible to a
|> digraph/trigraph attack.  As soon as the alogorithm and the n-graph
|> list is published, you have exactly what you need to generate the
|> ditcionary and/or patterns.
|>
|>    I used a pronouncable password generator on a VAX, and it seemed to me
|>    that the method of making them pronouncable was by pulling random di-
|>    or tri- graphs from a list, and concatenating them.  This would make
|>    them very suceptable to the cracker that Marcus contemplates.
|>
|>    --

|>
|>
|> --

|> San Diego Supercomputer Center |   FAX: +1 619 534-5152
|> P. O. Box 85608                | I'm not cynical, I just have a
|> San Diego CA 92186-9784        | fine appreciation of reality.
|>

A few corrections on your history of password generators.  The first
widely used password generator was indeed done for Multics, and Roger Schell
was the head of the computer security branch at the Air Force's Electronic
Systems Division that sponsored and guided the work, but the generator
was actually done by Morrie Gasser at MITRE ("A Random Word Generator
for Pronouncable Passwords", ESD-TR-75-97, November 1975, available
from NTIS.)  The report includes a statistical analysis of the generated
password (from digraphs and trigraphs) and indicates the probabilities
of guessing (with or without dictionaries) as a function of the number
of digraphs and trigraphs used.   The use of digraphs and trigraphs to
make the password pronouncable and easier to remember certainly does
reduce the search space, so you have to increase the length of the passwords
to get your statistics improved.  Note also that you use the password
generator in combination with auditing of password guessing attempts, and you
DO NOT make the encrypted version of the password file available as a
world-readable file.  Only UNIX ever made the encrypted passwords generally
available.  Neither Multics nor VMS ever did.  

The Gasser password generator was NOT the first random password generator.
There had been an earlier one written for Multics by (I think) Tom Van Vleck,
but his was never actually installed in the system or widely used.  Gasser's
was the first to be installed as standard system software and the first to
have extensive statistical studies done on its resistence to guessing.  The VMS
password generator was a port of the Gasser generator with some changes in
the random number generator, but not in the actual password generation code
itself.  Both password generators used their own crytographic-based random
number generators to avoid the well-known problems with system-provided
random number generators that actually provide small search spaces.

On a separate note - Roger Schell's PhD was in 1971 on dynamic reconfiguration
of CPUs and memories in the Multics symmetric multiprocessor - a much more
impressive technical achievement than a simple password generator!

 
 
 

Random password generation

Post by Tom Van Vle » Fri, 18 Feb 1994 15:29:11



Quote:> The Gasser password generator was NOT the first random password generator.
> There had been an earlier one written for Multics by (I think) Tom Van Vleck,
> but his was never actually installed in the system or widely used.

I don't remember writing such a pronounceable password generator.
I think I did write a password generator as a tool for the MIT
user registration people but that it was not based on digraphs.
I have a fading memory that Daniel J. Edwards wrote a better
password generator.. you out there Dan?  

Morrie's password generator had a very nice interface that said, e.g.
    Your new password is "wuffleduf" pronounced "wuf-fle-duf"
Perhaps he will read this message and shed more light on the history.

(I did write a trigraph-based password generator in the 80s in TAL while
at Tandem, seem to have mislaid the source though.  Using a 16-bit word
for the frequencies would make the table 35K bytes, big for the T16.
So I encoded each frequency as its log and truncated to 4 bits.
It worked just as well.  I passed it around and offered it to the
LOGON command owners but it was never installed in the system either.)

 
 
 

Random password generation

Post by Morrie Gass » Sat, 19 Feb 1994 18:08:14


Since I recently started reading this newsgroup (where was I all these years?)
and my name was mentioned I might as well chime in.

The only thing on which I can shed light, with regard to who wrote the first
password generator (if that's the point of this discussion) is that I completed
my password generator sometime in early or mid 1975.  I recall when I started
the effort that the notion of a pronounceable password generator was proposed,
but it seems to me that if there was one available that someone knew about then
I wouldn't have been asked to invent one.  I was pretty new to Multics at the
time so I don't have much history of what went before me.  At the time I was
unable to find any references on the topic so I developed the scheme from
scratch.

In 1976 or 77 I did get a letter from someone at Draper, whose name I don't
remember, about a different approach involving scanning actual text and
extracting pronounceable letter combinations.  I got the impression that his
generator was in use about the same time as mine.  Mine was forced to generate
rather ugly words because of the military requirement that it had to have a
uniform space of at least 26**6 different words.  While the program generated
very nice 6-letter words, people were forced to run it in 8 or 9 character mode
to increase the space and in that mode it tends to generate just a bunch of
disconnected syllables that are pronounceable but just as hard for me to
remember as six random letters.

To this day, I complain about the requirement to use ridiculously long
generated passwords on systems (like VMS or Multics) where the password file is
protected and number of failed attempts before detection is limited to small
integers.  I only use the password generator when I'm forced to.