basics 5 - tutorial MD5 and DES encrypted password leaks

This tutorial compares DES and MD5 encryption methods. Ubuntu used to encrypt users passwords with them until a few weeks, but the new kernel version is embedded with SHA512 encryption.
French version available on the site.

crypt()

Have a look to the crypt() funcion in libc manual [16].

CAUTION, this doc is obsoloete. Now, Ubuntu Karmic 9.10 uses SHA512 by default!

— Function: char * crypt (const char *key, const char *salt)
The crypt function takes a password, key, as a string, and a salt character array which is described below, and returns a printable ASCII string which starts with another salt. It is believed that, given the output of the function, the best way to find a key that will produce that output is to guess values of key until the original value of key is found.
The salt parameter does two things. Firstly, it selects which algorithm is used, the MD5-based one or the DES-based one. Secondly, it makes life harder for someone trying to guess passwords against a file containing many passwords; without a salt, an intruder can make a guess, run crypt on it once, and compare the result with all the passwords. With a salt, the intruder must run crypt once for each different salt.
For the MD5-based algorithm, the salt should consist of the string $1$, followed by up to 8 characters, terminated by either another $ or the end of the string. The result of crypt will be the salt, followed by a $ if the salt didn't end with one, followed by 22 characters from the alphabet ./0-9A-Za-z, up to 34 characters total. Every character in the key is significant.
For the DES-based algorithm, the salt should consist of two characters from the alphabet ./0-9A-Za-z, and the result of crypt will be those two characters followed by 11 more from the same alphabet, 13 in total. Only the first 8 characters in the key are significant.
The MD5-based algorithm has no limit on the useful length of the password used, and is slightly more secure. It is therefore preferred over the DES-based algorithm.
When the user enters their password for the first time, the salt should be set to a new string which is reasonably random. To verify a password against the result of a previous call to crypt, pass the result of the previous call as the salt.

This description calls some remarks:
- DES salt is made with only 2 characters,
- DES key's size is less than 11 characters. Only the 8 first ones are significative. Indeed, keys 12345678 and 123456789, used with the same salt, provide the same hash.

DES vs MD5

have à look:

On intrus, copy this source in a file called  genere_password.c

#include < unistd.h>
#include < stdio.h>
#include < string.h>


int main(int argc, char *argv[]) {
char *clair;
char *salt;
if(argc<3) printf(“Usage : motDePasseClair salt \n”);
else {
clair=argv[1];
salt=argv[2];
printf("Le chiffré est : %s\n",(char*)crypt(clair, salt));
}
return(0);
}

compile:

intrus$ gcc -lcrypt -o genere_password ./genere_password.c

result with DES:

intrus$ ./genere_password 1234567 ss
Le chiffré est: ssa3oBf/DtBng
intrus$ ./genere_password 12345678 ss
Le chiffré est: ssoQRtDQFsXkU
intrus$ ./genere_password 123456789 ss
Le chiffré est: ssoQRtDQFsXkU

We obtain the same encrypted result with 8 and 9 characters long keys.

Now, use MD5:  Just define the salt as follow: $1$ 8characters$

intrus$ ./genere_password 12345678 '$1$123456789'
Le chiffré est: $1$12345678$f8QoJuo0DpBRfQSD0vglc1
intrus$ ./genere_password 123456789 '$1$123456789'
Le chiffré est: $1$12345678$yRP2PzM0ZPA3W0Q4o/Axk1

Result:
- To use MD5, the salt must begin with $1$
- the salt size has a 8 characters limit (which is still better than the 2 DES ones),
- the key size is not limited with 8 characters.

John the Ripper

Now, use a tool to test passwords strength:

prerequisites: install John-the-Ripper

intrus$ sudo apt-get install john

copy last results into 2 files:
DES:

DES_1234567_ss:ssa3oBf/DtBng
DES_12345678_ss:ssoQRtDQFsXkU
DES_123456789_ss:ssoQRtDQFsXkU

MD5:

MD5_12345678_$1$123456789:$1$12345678$f8QoJuo0DpBRfQSD0vglc1
MD5_123456789_$1$123456789:$1$12345678$yRP2PzM0ZPA3W0Q4o/Axk1

start John with these files:

intrus$ john --show DES
DES_1234567_ss:1234567
DES_12345678_ss:12345678
DES_123456789_ss:12345678
3 password hashes cracked, 0 left

intrus$ john --show MD5
MD5_12345678:12345678
MD5_123456789:123456789
2 password hashes cracked, 0 left

conclusion

DES is a dangerous algorithm to encrypt passwords: the maximum size of passwords is 8 bytes, and its salt is 2 bytes long.
A weak password (easy to find or too short) is quickly found by a tool as John the Ripper.

references

16) manuel libc – fonction crypt() - http://www.gnu.org/s/libc/manual/html_node/crypt.html