{"id":32,"date":"2011-08-09T14:00:39","date_gmt":"2011-08-09T14:00:39","guid":{"rendered":"http:\/\/www.vidarholen.net\/contents\/blog\/?p=32"},"modified":"2011-07-28T10:39:26","modified_gmt":"2011-07-28T10:39:26","slug":"password-hashing-with-md5-crypt-in-relation-to-md5","status":"publish","type":"post","link":"https:\/\/www.vidarholen.net\/contents\/blog\/?p=32","title":{"rendered":"Password hashing with MD5-crypt in relation to MD5"},"content":{"rendered":"

If you haven’t reinstalled recently, chances are you’re using MD5-based passwords. However, the password hashes you find in \/etc\/shadow look nothing like what md5sum<\/code> returns. <\/p>\n

Here’s an example:<\/p>\n

\r\n\/etc\/shadow:\r\n$1$J7iYSKio$aEY4anysz.gtXxg7XlL6v1\r\n\r\nmd5sum:\r\n7c6483ddcd99eb112c060ecbe0543e86 \r\n<\/pre>\n
What’s the difference in generating these hashes? Why are they different at all?<\/p>\n
Just running md5sum on a password and storing that is just marginally more secure than storing the plaintext password. <\/p>\n
Thanks to GPGPUs, a modern gaming rig can easily try 5 billion such passwords per second, or go over the entire 8-character alphanumeric space in a day. With rainbow tables<\/a>, a beautiful time–space tradeoff, you can do pretty much the same in 15 minutes.<\/p>\n
MD5-crypt employs salting<\/a> to make precomputational attacks exponentially more difficult. Additionally, it uses stretching<\/a> to make brute force attacks harder (but just linearly so). <\/p>\n
As an aside, these techniques were used in the original crypt from 1979, so there’s really no excuse to do naive password hashing anymore. However, at that time the salt was 12 bits and the number of rounds 25 — quite adorable in comparison with today’s absolute minimum of 64 bits and 1000 rounds.<\/p>\n
The original crypt was DES<\/a> based, but used a modified algorithm to prevent people from using existing DES cracking hardware. MD5-crypt doesn’t do any such tricks, and can be implemented in terms of any MD5 library, or even the md5sum util. <\/p>\n
As regular reads might suspect, I’ve written a shell script to demonstrate this: md5crypt<\/a>. There are a lot of workarounds for Bash’s inability to handle NUL bytes in strings. It takes 10 seconds to generate a hash, and is generally awful..ly funny! <\/p>\n
Let’s first disect a crypt hash. man 3 crypt has some details. <\/p>\n
\r\nIf salt is a character string starting with the characters\r\n\"$id$\" followed by a string terminated by \"$\":\r\n\r\n       $id$salt$encrypted\r\n\r\nthen instead of using the DES machine, id  identifies  the\r\nencryption  method  used  and this then determines how the\r\nrest of the password string is interpreted.  The following\r\nvalues of id are supported:\r\n\r\n       ID  | Method\r\n       -------------------------------------------------\r\n       1   | MD5\r\n       2a  | Blowfish (on some Linux distributions)\r\n       5   | SHA-256 (since glibc 2.7)\r\n       6   | SHA-512 (since glibc 2.7)\r\n\r\n<\/pre>\n
Simple and easy. Split by $, and then your fields are Algorithm, Salt and Hash. <\/p>\n
md5-crypt is a function that takes a plaintext password and a salt, and generate such a hash.<\/p>\n
To set a password, you’d generate a random salt, input the user’s password, and write the hash to \/etc\/shadow. To check a password, you’d read the hash from \/etc\/shadow, extract the salt, run the algorithm on this salt and the candidate password, and then see if the resulting hash matches what you have.<\/p>\n
md5-crypt can be divided into three phases. Initialization, loop, and finalization. Here’s a very high level description of what we’ll go through in detail:<\/p>\n
    \n
  1. Generate a simple md5 hash based on the salt and password<\/li>\n
  2. Loop 1000 times, calculating a new md5 hash based on the previous hash concatenated with alternatingly the password and the salt.<\/li>\n
  3. Use a special base64 encoding on the final hash to create the password hash string<\/li>\n<\/ol>\n
     <\/p>\n
    Put like this, it relatively elegant. However, there are a lot of details that turn this from elegant to eyerolling. <\/p>\n
    Here’s the real initialization.<\/p>\n
      \n
    1. Let “password” be the user’s ascii password, “salt” the ascii salt (truncated to 8 chars), and “magic” the string “$1$”<\/li>\n
    2. Start by computing the Alternate sum, md5(password + salt + password)<\/code><\/li>\n
    3. Compute the Intermediate0<\/sub> sum by hashing the concatenation of the following strings:\n
        \n
      1. Password<\/li>\n
      2. Magic<\/li>\n
      3. Salt<\/li>\n
      4. length(password) bytes of the Alternate sum, repeated as necessary<\/li>\n
      5. For each bit in length(password), from low to high and stopping after the most significant set bit\n