Index O'Stuff
Home Compression Arithmetic CodingBurrows-Wheeler Transform Huffman Coding LZSS Coding LZW Coding Run Length Encoding Misc. Programming School ProjectsThesis Project crypt(3) Source Hamming Codes Bit Manipulation Libraries Square Root Approximation Library Sort Library Trailing Space Trimmer and Tab Remover Command Line Option Parser Humor Dictionary O'Modern TermsThe Ten Commandments of C Style Other Stuff TOPS Success StoryFree Win32 Software External Links SPAN (Spay/Neuter Animal Network)Los Angeles Pet Memorial Park Mirrors
Pages at geocitiesPages at dipperstein.com Obligatory Links
Visits since I started counting: |
Michael Dipperstein's Crypt(3) PageAs 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 mdipper@alumni.engr.ucsb.edu Brief HistoryIn 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 ProblemAs 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 half 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 ProblemThe 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 into left and the next 32 into the array right. The second place this same bug occurs is at the end of the function encrypt. 64 characters are copied out of the 32 character array left into the 64 character array block. The code should actually copy the first 32 characters from left and the next 32 from the array right. Make these two changes and your code should function properly with any ANSI C Compiler. Corrected and Cleaned-up SourceIf 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: mdipper@alumni.engr.ucsb.edu |
Home
Last updated on January 4, 2006