Hello all...
David Rysdam enscribed thusly:
> This is a very general answer, not specific to Unix, shadow passwords or
> MD5 (which is what I believe shadow uses).
MD5 (which shadow can use - and should use) is a hash algorithm...
The older system uses DES. DES is a symetrical encryption decryption
algorithm but is not used this way for passwords, it's used in a way
that creates a one-way hash.
> Modern encryption is based on problems that are only solvable in one
> direction. Prime factorization is a good example. It's very easy to
> take two (large) primes and multiply them together. But it is very
> difficult to take a (very large) composite number and factor it back to
> the two primes.
What you are describing is public key cryptography and that is
not what is used here. In fact, the passwords are not reversibly
encrypted at all.
> This basic fact (there's a lot more in real cryptography about modulus,
> etc) makes encryption easy but decryption hard.
> Maurice Hendrix wrote:
> > Hi,
> > I have a question about password encryption used by Linux (PAM I think).
> > Could somebody explain to me why it would be impossible to write a program
> > that will decrypt a password taken from the /etc/passwd file (or it's
> > shadow) using the inverse of the encryption algorithm? What *is* the
> > encryption algorithm used anyway?
First misconception. Even though the hashes stored in /etc/passwd
or /etc/shadow are referred to as "encrypted passwords", they are not.
What is stored in those files are password hashes. They are not encrypted
passwords.
The conventional way the standard password file uses with DES is to
take the users password, plus a "seed" to encrypt a known value. The result,
plus the seed, is stored in the password field (setting) or compared to the
value in the password file (testing). Note that what is encrypted is NOT
the password, but is some fixed value that is encrypted USING the password.
This gives you an irreversable hash. The seed is a value from 0-4095 and
is represented in the hash by the first two characters of the hash field.
In the case of the MD5 algorithm, an encryption is not even
involved. It's merely the MD5 hash of the password and MD5 is an
irreversable algorithm. I'm not totally sure if a seed is involved with
MD5 hashes or not. If not, it should be. A given password should have
the possiblity of resulting in more that one hash (determined by the seed).
You can not "decrypt a password" ... "using the inverse of the
encryption algorithm" basically because the "inverse of the encryption
algorithm" does not exist in this case. The passwords are never
"decrypted" and comparisons are made between the hashes, never the
unencrypted passwords.
You test to see if a password is correct by rehashing the password
to be tested in the same maner as the stored hash. If the two hashes match,
the two passwords most likely matched. I say most likely, because it is
in the nature of the hashing algorithms to have more that one input which
can result in the same output. This is described as a "collision" and is
extremely rare (won't happen in my lifetime). It does mean that the
algorithms are not reversable (since uniqueness is thereby violated).
The probability of a collision is a measure of how "robust" a hashing
algorithm is. The lower the probability, the harder it is to find another
"input" which will match the "output" and the more robust the hash is.
The best you can do is "brute force". Use a lot of horsepower
and test out candidate passwords by hashing them and comparing the hash
to the target to be broken. When you get a match, you've broken the
password. Good passwords are incredibly difficult to break this way.
Bad passwords fall to brute forcers like "crack", "John the Ripper", or
"L0phtCrack" (Windows) in minutes. I ran crack on a password file for
a site I was assisting with an intruder breakin. Out of 200 accounts,
crack had brute forced over 70 of the passwords in less than two hours,
and some of them were pretty good (just from looking at them).
It's a general cryptographic principle that a one-way hashing
algorithm can generally be used to create a symetrical encryption/decryption
algorithm (whether it's a GOOD one or not is another question) and
an encryption algorithm can be used to create a hashing algorithm.
That creates a lot of confusion between the two. They are not the same.
> > If that isn't a challenge already, try to answer slowly in plain English (I
> > do have fair understanding of math).
> > TIA,
> > --
> > Maurice Hendrix
> > snailmail: Fuji Photo Film BV Standard disclaimers apply
> > Dept. P1LPI
> > attn. M. Hendrix
> > PO Box 90156
> > 5000 LJ Tilburg
> > phone: +31 13-579 1370 or fax: +31 13-579 1385
> > - Still 19 months to go until the next millenium...
> --
> My public encryption key is available from
> www.az.com/~drysdam/crypt/rysdam.gpg.html
> and of course www.keyserver.net
Mike
--
Michael H. Warfield | (770) 985-6132 | [EMAIL PROTECTED]
(The Mad Wizard) | (770) 925-8248 | http://www.wittsend.com/mhw/
NIC whois: MHW9 | An optimist believes we live in the best of all
PGP Key: 0xDF1DD471 | possible worlds. A pessimist is sure of it!
