random passwords (was Re: Worm...)

[Piercarlo Grandi]

In article <28399 at tut.cis.ohio-state.edu> jgreely at cis.ohio-state.edu (J Greely) writes:

    >[1] It restricts unconscionably the key space (usually to a few thousand
    >or at best dozen thousand entries).
    
    Well, after fixing the minor bugs in pwgen, I'm not terribly worried about
    the key space:
    
    	% pwgen 9 500000 | sort | uniq | wc -l
    	482718
    
      The percentage of unique passwords seems to drop at a fairly
    constant rate as you raise the number generated, but at 500000 it's
    still over 96%.

I used the word unconscionably, and for good reason :-(.  Assume that a
nice system administrator uses your 500,000 figure. 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... :-) :-)

Consider also the fact that pwgen must eventually cycle. For all you
know, the cycle is exactly 482718 elements long, and after that
passwords start repeating. Maybe yes, maybe not. Also, there being a
cycle, there must be a point at which the number of duplicates raises
linearly. When you have got 50% duplicates, this just means that you
have just run thru the second cycle.

Note also that duplicates are not the whole story; there may be no
duplicates, but the key space is still highly structured, and in a
known way.

    It would require more testing to see just how many
    unique strings it's capable of generating, but that's for another day.

The point is that security is not a something where you test; you PROVE,
or you make a convincing mathematical analysis using the best tools of
statistics etc...

    >[2] If the algorithm used to generate the passwords get known, it can be
    >used to obtain a complete list of all possibly passwords.
    
    Naaah.  The patch I sent to him suggested adding a switch to randomly
    upcase letters, as well as replace letters with numbers ('l' -> '1',
    'o' -> '0', etc).  If 8-character passwords are chosen, modified by
    these transformations, the key space is more than sufficient.

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.

All algorithms that do generate "random" passwords lop off a LOT of the
56 bits of the key space. So much the worse if the "random" selection
is based on fairly restrictive rules. The resulting key space may be
larger than a few dozen thousand entities, but will most likely be
small enough to be easily attackable, especially as it is known that it
is highly structured, i.e. not random at all. A good codebreaker uses
the regularity of natural language as a powerful tool; an algorithm as
the source of the signal to decode is just too good to be true,
especially if it is highly predictable.

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


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.

If a reasonable and articulate and competent person like Mr. Greely
still feels like giving an example with a number like 500,000 for a
reasonably large key space, and may be prepared to trust a site's
security to it, I shudder thinking of what less prepared people might
come up with.
-- 
Piercarlo "Peter" Grandi			INET: pcg at cs.aber.ac.uk
Sw.Eng. Group, Dept. of Computer Science	UUCP: ...!mcvax!ukc!aber-cs!pcg
UCW, Penglais, Aberystwyth, WALES SY23 3BZ (UK)