Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!thunder.mcrcim.mcgill.edu!mouse
From: mouse@thunder.mcrcim.mcgill.edu (der Mouse)
Newsgroups: comp.unix.wizards
Subject: Re: WARNING!
Message-ID: <1991Apr14.093305.12559@thunder.mcrcim.mcgill.edu>
Date: 14 Apr 91 09:33:05 GMT
References: <26512@adm.brl.mil>
Organization: McGill Research Centre for Intelligent Machines
Lines: 55

In article <26512@adm.brl.mil>, attcan!vpk1!john@uunet.uu.net writes:
> John Lupien <lupienj@hpwadac.hp.com> types:
> In article <1991Mar27.094325.24599@en.ecn.purdue.edu> kidder@en.ecn.purdue.edu (Mark Stephen Kidder) writes:
[Are those attribution lines really right?  They look odd. -Mouse]
>>> PS I learned earlier from another that UNIX does not use a DES
>>>    encryption method for the password; however, a one-way method is
>>>    used making decoding a password impossible.
>>                                     ^^^^^^^^^^^
>> To borrow a phrase from [some movie], "You use that word a lot. I
>> don't think it means what you think it means."
> It doesn't matter how fast or powerful the hardware is.  [...]  While
> there is no known method of reversing the encrytpion, you can use
> comparison or other BFI methods ([...]) to get at passwords.

What's the difference?  Any method that takes the hashed password as
input and produces the original form as output (or, arguably, any
string which would be accepted for (eg) logins) counts as "decoding the
password" or "reversing the encry[pt]ion".  Whether this is done by
some clever method only the no-such-agencies currently know, by table
lookup in a monster table, by exhaustive search through the space of
possibilities, or some other method, is completely irrelevant.

The common password encryption scheme is not DES, not quite; it is DES
with the E-box diddled slightly by the salt value (supposedly to defeat
attempts to use DES hardware for exhaustive search).  It is a
reasonably good approximation to a one-way function.  Nevertheless, to
mangle the language sightly, it is not impossible and is steadily
becoming less so.  There are only 2^56 input values.  I have code that
does approximately a thousand trials a second on general-purpose
hardware.  Let's suppose with a little hardware work we could push this
to a million per second (a bit in advance of current hardware, but
probably not that much).

This still sounds fairly secure, as it works out to about two thousand
years to cover the entire space.  But now we spend a little money and
buy/build a thousand of those hardware assist units.  Now we're down to
two years.

And the vast majority of the space of possibilities corresponds to
passwords like V 3 ^A 9 W ' ; x that no sane person would pick because
they're so impossible to remember.

No, it's time to start thinking about it.  Now.  Not in five years,
when anyone with access to one of the latest FrobozzCo 64K-processor
2684TRX PLA machines can exhaust the space in a month, and find your
password and mine much sooner than that.  Or when storage densities
have improved to the point where one person can carry that monster
lookup table I mentioned in a pocket.  (64 bits times 2^56 passwords
times 2^12 salts is 2^71 bytes.  That looks ridiculous.  Today.)

					der Mouse

			old: mcgill-vision!mouse
			new: mouse@larry.mcrcim.mcgill.edu