Uninvertible passwd encryption (was: Re: Kmem security)

[Jim Reid]

In article <1991Mar19.231715.28594 at comp.vuw.ac.nz> duncan at comp.vuw.ac.nz (Duncan McEwan) writes:

   Exactly why is the Unix password encryption algorithm uninvertible?
   Is it to do with the fact that Unix encrypts a constant string using the
   password as a key -- so it *is* possible to work back to that
   constant string, but you still know nothing about the password?

Not exactly. UNIX password encryption is quite complicated. It uses
DES which is supposedly strong enough to survive most cryptanalytical
attacks. (Unless of course you work for the NSA or GCHQ....) It is
theoretically possible to break DES (like any encryption algorithm),
but computationally infeasible. For example, public-key encryption
tends to be based on the fact that factorising huge integers - say a
few hundred digits - takes a long time; possibly longer than the
lifetime of the universe even if using a supercompter. In other words
it can be done, but the amount of effort required means it's not worth
the bother of trying.

DES uses a 56-bit key which fits neatly into 8 ASCII characters, the
usual maximum length of a UNIX password. This gives a key space of
7.2E16 (2**56). Assuming you could perform 1 billion DES encryptions
per second, an exhaustive search of the key space would take over two
years. In reality, a rate of even 1 million encryptions per second is
somewhat optmistic. [Even if the original assumption were true, the
password would have to remain unchanged while it was being cracked.]

Of course, this approach is crude. However, DES is designed to
withstand cryptanalytical attacks on the key space even when the
plaintext and cyphertext is known. There is a lot of speculation that
DES may have a trap-door which makes it easily cracked by the likes of
the NSA. However, it hasn't been found yet, despite serious attempts
by experts.

"What about DES hardware?", I hear you ask. Well for UNIX purposes,
DES chips are not much help. The UNIX crypt() function which
implements DES permutes an internal DES table (the E-table) using an
effectively random number - the salt - based on the PID and time. This
salt is stored in the encrypted password field and is used to
initialise the DES algorithm before encrypting the plaintext with the
password as a key. The salt means there are 4096 permutations of the
DES E-table, making DES chips useless since they only have one
hard-wired E-table. It's possible someone could go out and build
custom DES hardware, but that won't exactly be cheap or quick.

All this is explained in the classic paper "Password Security: A Case
History" by Robert Morris and Ken Thompson. It's been shipped with
UNIX systems since the time of V7, but not many vendors include it
with their documentation these days.

		Jim