Password validation

[John B. Nagle]

     Some months ago I posted a program to detect obvious password choices
given the clear text; I will send a copy or repost to net.sources if
requested.  The algorithm is about a page of C code plus a large bitmap
(about 10 pages of C initialization) constructed by running the entire
Unix spelling dictionary through the algorithm.  The routine will reject
every word in the Unix dictionary and most other English words, but a
randomly chosen letter sequence has an 80% chance of being acceptable.
Processing time is a few milliseconds on any reasonable machine, and
the code will run on almost anything with a C compiler, including a 
DECsystem 2060.
     I sent a copy off to the NSA Computer Security Center, and received
a few informal comments in return.  They like randomly generated passwords, 
and they mean random, not psuedo-random.  But a reasonable way to encode the
random number is as a sequence of alternating vowels and consonants; such
strings are easier to remember than totally random strings.  The trouble with
an obvious password detector of the type I developed is that users tend to
learn some way to get around it by performing some obvious transform on
their favorite password (such as sticking a digit in the middle of
their name).  Thus, the only sound approach from an administrative viewpoint
where you want to prevent the laziest user from providing a hole in security
is to generate passwords entirely randomly.  Such is their thinking.
     The random password approach tends to work best in a security-concious
environment; most sites find it too annoying.  My approach is admittedly a
compromise.
     Generating random numbers on a computer is hard.  The right way is with
special hardware that exploits a phenomenon known to be random from fundamental
physical considerations (a noise diode or radiation source connected to 
appropriate digital hardware) and even this is not trivial.  Using the clock 
is no good; if you know roughly when the password was changed, the search space
becomes very small, especially if the clock has low resolution (such as 1/60 
sec.).  A more promising approach is to take, say, the low order bit of the 
angular address of some rotating medium at intervals of (say) 100 ms and 
accumulate a value of the desired length in that way.  This may still be 
vulnerable to a sophisticated attack, and may take system modifications, but 
somehow random numbers must be derived from the real, non-deterministic world
to be really random, and this is a way to do so with common hardware.
     Always bear in mind that while break-ins by outsiders get most of the
attention, real losses usually come from inside jobs.