mwp@murtoa (Michael Paddon) (12/07/88)
From article <120@tnl.UUCP>, by norstar@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@munnari.oz.au) | | Department of Computer Science, Melbourne University | ========================================================
gwyn@smoke.BRL.MIL (Doug Gwyn ) (12/09/88)
In article <1106@murtoa.cs.mu.oz.au> mwp@murtoa writes: >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). But if you know X and B, then A = X ^ B is the unique solution for A. Also, the various equations that need to be solved to invert a DES are somewhat redundant. If you solve enough samples simultaneously, the plaintext can be uniquely reconstructed without knowing the key in advance. (I don't say that this is EASY.) And, in the case of cracking encrypted passwords, one doesn't normally care what the actual password was, so long as A working password is produced.