random passwords (was Re: Worm...)

[Steven M. Bellovin]

In article <278 at aber-cs.UUCP>, pcg at aber-cs.UUCP (Piercarlo Grandi) writes:
> somebody posted that an exhaustive generation
> of all possible keys encrypted by login is already a feasible thing to
> do.

Let's look at this quantitatively.  There are, more or less, 95
printable characters.  We'll subtract 2 for @ and #, which many UNIX
systems still use for line kill and erase.  If we consider just
8-character passwords, that means there are 93^8 possibilities, or
5,595,818,096,650,401.  Each one can be encrypt 4096 different ways,
given the salt; this leaves us with 22,920,470,923,880,042,496, but if
you're trying to attack one particular password, as opposed to password
fishing that number isn't relevant.  So we'll look at the smaller
number, which I trust you'll let me abbreviate as 5.6e15.  Let's assume
you can do an encryption in 1 microsecond (which is ~4 orders of
magnitude better than any claims I've seen for a VAX 8600).  Let's
further assume that you're doing this on some small cheap machine, so
that you can put 1000 of them to the task.  That means that you can try
10^9 passwords/second, so it should take you 5.6e6 seconds to crack my
password that way, or ~65 days.  More realistically, you're not going
to manage that speed any time soon, especially not on that many machines.
If your encryptions take even 10 microseconds -- still 1000 times the best
speed reported for an 8600 -- my password is safe for 2 years.  I change
it more frequently than that...

Using a more restricted character set helps the cracker a lot.
Under the same wildly-optimistic speed assumptions as before, a password
of only upper- and lower-case letters would take just .6 days to crack,
which is indeed worrisome.  A cracker on a lone 8600, using today's
technology, would need 6 million days.  Clearly, we can't be that optimistic.
Assume, for example, a worm that devoted all the power of the penetrated
machines to attacking one password.  The Internet is estimated to contain
60,000 machines; let's assume that each one could be infected, and each
one could check a password in 100 microseconds.  That means 6e8 trials a
second, for just over a day to check all possibilities.  This number isn't
that insane; we postulate a 5-fold improvement in the algorithm, and
a 20-fold improvement in CPU power, in a widely available form, is almost
here now.  And if the Internet keeps growing, our next wormer may have
something useful to do with all that CPU power!

Note that precalculating all these passwords doesn't work.  First, you'd
need to multiply the number of possibilities by 4K, because of the salt;
second, CPUs can calculate data much too rapidly for even optical disks
to keep up.  Again, 52^8 choices, times 4096 encryptions, times 8 bytes
for the output data maximally packed, yields 1,751,768,384,518,750,208 bytes.
We'll assume that the salt used and the cleartext password are calculable
from the position of the result, which probably isn't true if you organize
the file for rapid searching...

What can we conclude?  First, for 8-character passwords, today's algorithms
are good enough for now.  Second, that they won't be forever; in 10 years,
some of these numbers will start to look worrisome.  Third, using a larger
input character set expands the search space beyond the forseeable trouble
range.

		--Steve Bellovin