A crypt(3) Discussion and Implementation
by Michael Dipperstein
As part of homework assignment for a computer security class, I was required to obtain the password for three Unix accounts. I obtained a copy of the passwords encrypted with crypt(3) (if you don't know how to do that the world is that much safer) and attempted to guess the password that gives the same encrypted value. To do the guessing, I used my PC and a copy of crypt3.c that is widely available over the internet. As it turned out I was reminded that you can't trust everything you download.
This page discusses the bugs in that version of crypt3.c and links to a cleaner copy of code with the bugs fixed.
If you have nothing better to do, email me at email@example.com
In the fall of 1998, I needed to use the crypt(3) algorithm for a computer security homework assignment. Being a lazy student, I decide to check if there's already some C source floating around to do the job for me. As it turned out there are many sites containing a file called crypt3.c. The header of the file proclaims that it's a the genuine crypt(3) source from BSD Unix.
Perfect, I had my source now I could compile it use the function for my assignment.
Since I would have to make several calls to the function, I decided to benchmark it on with using the three C compilers that I had access to. I tried the CygWin32 version of gcc, lcc, and Borland's bcc. As things turned out, not only did the executable generated by each compiler have different execution times. The executables also produced different results.
I came up with a test to determine which, if any, results were correct. Only the gcc compiler produced correct results. This bothered me, because the source was not supposed to be compiler specific.
Cause of Problem
As it turned out, all three compilers produced correct results. There is a bug in the version of crypt3, and depending upon the compiler implementation the results will vary.
The bug is a pretty simple one. Crypt(3) is based on DES, which breaks up a 64 bit pattern into left and right halves, and performs permutations and transpositions on the bits in the halves. The crypt3.c source that I had assumed that the left and right halves were a single contiguous block of data, but it used a separate declaration for each half. gcc generated code with contiguous halves, while lcc and bcc allocated the halves differently.
Solution to Problem
The solution to the problem is simple, change all the code that assumes
the left and right halves are in contiguous memory, so that it doesn't
depend on that assumption. The assumption used made in two locations. Both
of which are in the function
encrypt. The first occurrence is
when the parameter
block is copied into the two halves. The
original file copies all 64 characters into the 32 character array
left. The code should actually copy the first 32 characters
left and the next 32 into the array
The second place this same bug occurs is at the end of the function
encrypt. 64 characters are copied out of the 32 character
left into the 64 character array
code should actually copy the first 32 characters from
and the next 32 from the array
Make these two changes and your code should function properly with any ANSI C Compiler.
Corrected and Cleaned-up Source
If you as lazy as I was and want to use a pre-existing copy of crypt(3) source, here's the source that I ended up with. The source is heavily borrowed from the crypt3.c file mentioned above. The code has been cleaned-up and compiles correctly under, gcc, lcc, and Borland's bcc C compilers. All implicit register declarations have been removed, because they generated suboptimal code. All constant data has been explicitly declared as const and all declarations have been given a minimal scope, because I'm paranoid. I hope this makes your life a bit easier.
The original source claimed to be BSD, but was not distributed with any BSD license or copyright claims. I am releasing the source that I have provided into public domain without any restrictions or warranties.
If you have any further questions or comments, you may contact me by e-mail. My e-mail address is: firstname.lastname@example.org