Reversing the password algorithm

[Michael Paddon]

>From article <120 at tnl.UUCP>, by norstar at tnl.UUCP (Daniel Ray):
>
> ... the crypt() routine IRREVERSIBLY encrypts a password. As a trivial
> example: lets say we encrypt the alphabet..A is mapped to B, B to C, C to D,
> etc, except that both Y and Z are  mapped to Z. The encrypted text of the
> word "ZOO" would be "ZPP". Easy to do. However, by knowing that the ciphered
> text is "ZPP", can one reverse it? No, because both "ZOO" and "YOO" encrypt
> to that. I thought crypt() was like this in a much more sophisticated way,
> and that there exists the remote but theoretical possibility of password
> collision (two different passwords encrypting to the same string using the
> same salt).

The encrypted string is produced by using the plain text password as
the key to encrypt a fixed sequence of bytes using a (modified) DES
algorithm. Usually this fixed sequence of bytes is just all zeroes,
although it may be specified as something different at compile time.
Normally nobody does this as:
	1) You can't then copy encrypted passwords to other machines
(unless they are also running the modified crypt);
	2) Security via secrecy is not effective over a long period,
as we are all well aware. Especially holes in sendmail and fingerd :-)

The problem of decrypting a password therefore becomes the problem
of calculating the key (48 bits) used from four known factors:
	1) the plain text (64 bits),
	2) the encrypted text (64 bits),
	3) the salt (12 bits) and
	4) the algorithm used (see above comment on secrecy).

This, however, is a far more difficult than it seems at first glance.
When I was an undergrad, I had a look at this problem (in fact I reverse
compiled the library object since I didn't have access to source;
naturally, it was all in the pusuit of pure intellectual curiosity :-)
and found that the algorithm is essentially irreversible,
in respect to the key, due to the use of two bitwise XOR's, ie.

	[right half of plain text] ^ [bit string derived from key]
and
	[left half of plain text] ^ [bit string derived from above calculation]

The plain text halves are then swapped and fed back into the algorithm
until a total of 16 encryptions have been performed. The entire encryption
process is repeated 25 times.

Now we all know that if X = A ^ B, and we know X that it is not possible to
deduce what A and B were in the first place because there are many A's and
B's which satisfy the equation (remember: 1 ^ 1 = 0, and 0 ^ 0 = 0).

It is, however, theoretically possible to sometimes reduce the brute
force search space by reversing the algorithm to the extent that we
know some of the bits in the key. I haven't ever actually tried this
and I don't have any idea how much of the key the worst/best/average 
cases are likely to yield.

========================================================
| Michael Paddon (mwp at munnari.oz.au)                   |
| Department of Computer Science, Melbourne University |
========================================================