random passwords (was Re: Worm...)

[J Greely]

In article <278 at aber-cs.UUCP> pcg at cs.aber.ac.uk writes:
>In article <28399 at tut.cis.ohio-state.edu> jgreely at cis.ohio-state.edu (J Greely) writes:

> [quick test showed at least a half-million possible strings from
>  Brandon's "pronouncable" password generator]

>I used the word unconscionably, and for good reason :-(.  Assume that a
>nice system administrator uses your 500,000 figure.

The half-million was quoted simply because it took only a few minutes
to generate.  The "sort | uniq" was getting a bit unwieldy at that point.
I haven't had time to really study the method used, beyond noting that
it does attempt to generate random strings with lots of vowels (although
"oo" is *far* too popular).  As is, I would not attempt to force every
user here to use it (fat chance they'd listen to me, anyway), but as
soon as I am sufficiently convinced of its efficiency, I have no problem
pointing it out as an option.

  I'd rather have people using a random string from a known algorithm
than something from /usr/dict/words.  It may not be completely safe,
but it has the advantage of not being *online*.  Quick example: the
infamous worm never got here, but I tested our passwd files against
the 432 strings it used.  32 out of 2000 accounts were broken,
including 2 staff accounts.  So, when I'm convinced that this or
some other algorithm generates a reasonably large number of pronouncable,
non-English words (and I convince the rest of the staff :-)), I'll
be happy to add it as an *option*.

  If I could convince them to roll a set of Boggle(TM) dice, I'd
try that, too.

>						 Assume somebody
>decides to DES all of them, say one every millisecond. In less than 500
>seconds (say 15 minutes, including delays etc...) he has broken ALL the
>passwords on your system. Interesting... :-) :-)

Pretty fast crypt.  Remember, password encryption is 25 times slower
than normal DES (unless you know something about multiple encryption
with the same key that I don't).  And for a quick back-of-the-keyboard
calculation, 500000 * 11 * 4096 / 1024^3 is almost 21 *giga*bytes,
just for the ciphertext.  Now that you know you broke it, you still
have to have the original text somewhere to find out what the password
is.  Messy.

For those who don't know where the 4096 came from, Unix password
encryption changes DES in one of 4096 ways before encrypting (the
"salt"), raising the effective key size to 68 bits, at the possible
cost of some of the algorithm's strength.

>Consider also the fact that pwgen must eventually cycle.

  Can't avoid this with any password generation system.  If you use
any one system, you decrease your security drastically, no matter how
secure that one system is.  However, if, in my list of "ways to make a
good password", I include a random string generator (whether it be
pwgen, travesty, or dissociated press), some people will try it, find
something they like, and use it.  Better that than "password", or
their username.

>It has been argued forcefully that even the 2^56 keyspace of fully
>random DES is too small; somebody posted that an exhaustive generation
>of all possible keys encrypted by login is already a feasible thing to
>do.

Feasible?  'scuse me a moment.  2^56 * 4096 * 11 / 1024^3 > 3 * 10^12
gigabytes of storage for the whole thing.  Consider that when you're
generating these, they have to be compared to your target passwords.
If your target list is small enough, you can (encrypt,compare,throw
out), otherwise you'll have to store them somewhere (a few pieces at a
time).  No doubt it can be done, but the effort required is not
cost-effective for cracking most systems.

>Manual password generation may be weak, but at least it is less
>predictable.

Well, sort of.  Human nature is *very* predictable.  When I tested
here for people using either their username or part of their full name
("joes"), I was not surprised to find several.  When I tested the worm
list, I was not surprised to find more (in fact, some of the accounts
broken pointed out a much larger security problem, which shall remain
nameless :-)).

>My own opinion is that the worse security risk is a false sense of
>security and a "random" password generator is one of the best tools to
>achieve this.

  I'm not going to argue this one.

  "Well, Mr. Upperclass Management Person, we've increased our
security by requiring all employees to use randomly generated
passwords, to prevent them from choosing easy-to-remember words.  Now
they must use company-assigned passwords, and guard them with their
worthless lives."

  I'd be the first person to raise hell if something like this was
tried, particularly in a university environment.

>If a reasonable and articulate and competent person like Mr. Greely

(mind if I show this part to my boss?)
-- 
J Greely (jgreely at cis.ohio-state.edu; osu-cis!jgreely)
Unseen, in the background, Fate was quietly slipping the lead
into the boxing glove.