Aaron Toponce

Recently, the Password Hashing Competition announced its winner, namely Argon2, as the future of password hashing. It's long since been agreed that using generic-purpose cryptographic hashing algorithms for passwords is not a best practice. This is due to their speed. Cryptographic hashing algorithms are designed to be lighting fast, while also maintaining large margins of security. However, Poul-Henning Kamp noticed in the early 1990s that the DES-based crypt() function was no longer providing the necessary margins of security for hashing passwords. He noticed how fast crypt() had become, and that greatly bothered him. Even worse, was the realization that FPGAs could make practical attacks against crypt() in practical time. As he was the FreeBSD release engineer, this meant putting something together that was intentionally slow, but also with safe security margins. He chose MD5 as the basis for his new "md5crypt password scrambler", as he called it.

Before delving into the algorithm, the first thing you'll notice is the strange number of steps and mixing that PHK does with his md5crypt() algorithm. When I was reading the algorithm, the first question that popped into my mind was: "Why not just do standard key-stretching with the password?" Something like this (pseudocode):

digest = md5(password + salt).digest()
rounds = 1000
while rounds > 0:
  digest = md5(password + salt + digest).digest()
  counter -= 1

This certainly seems to be the most straightforward approach, and the entirety of the security is based on the cryptographic security of MD5. If you were concerned about the output digest being recognizable, it might make sense to scramble it. You could scramble the remaining bytes in a deterministic fashion, which PHK actually ends up doing before saving to disk.

But then it hit me: PHK wanted his new algorithm to be intentionally slow, even if using MD5. This means adding additional steps to mixing the password, which requires more CPU, and thus, more time. If raw MD5 could process 1,000,000 hashes per second, then standard key-stretching of 1,000 iterations would bring it down to 1,000 hashes per second. However, if adding additional operations slows it down by 1/N-iterations, the the resulting throughput would be 1,000/N hashes per second. I can see it now- anything to slow down the process, without overburdening the server, is a gain. As such, the md5crypt() function was born.

Here is the algorithm, including what I think may be a bug:

1. Set some constants:

   "pw" = user-supplied password.
   "pwlen" = length of "pw".
   "salt" = system-generated random salt, 8-characters, from [./0-9A-Za-z].
   "magic" = the string "$1$".
   "itoa64" = is our custom base64 string "./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
   

2. Initialize digest "a", and add the password, magic, and salt strings to it:

   da = MD5.init()
   da.update(pw)
   da.update(magic)
   da.update(salt)
   

3. Initialize digest "b", and add the password, salt, and password strings to it:

   db = MD5.init()
   db.update(pw)
   db.update(salt)
   db.update(pw)
   final = db.digest()
   

4. Update digest "a" by repeating digest "b", providing "pwlen" bytes:

   for(pwlen; pwlen > 0; pwlen -= 16):
     if(pwlen > 16):
       da.update(final)
     else:
       da.update(final[0:pwlen])
   

5. Clear virtual memory

   memset(final, 0, length(final))
   

6. Update digest "a" by adding a character at a time from either digest "final" or from "pw" based on each bit from "pwlen":

   for(i = pwlen; i; i >>= 1):
     if i % 2 == 1:
       da.update(final[0])
     else:
       da.update(pw[0])
   dc = da.digest()
   

7. Iterate 1,000 times to prevent brute force password cracking from going too fast. Mix the MD5 digest while iterating:

   for(i=0; i<1000; i++)
     tmp = MD5.init()
     if i % 2 == 0:
       tmp.upate(dc)
     else:
       tmp.update(pw)
     if i % 3 == 0:
       tmp.update(salt)
     if i % 7 == 0:
       tmp.update(pw)
     if i % 2 == 0:
       tmp.update(pw)
     else:
       tmp.update(dc)
     dc = tmp.digest()
   

8. Convert 3 8-bit words of digest "c" into 4 6-bit words:

   final = ''
   for a, b, c in ((0, 6, 12), (1, 7, 13), (2, 8, 14), (3, 9, 15), (4, 10, 5)):
     v = ord(dc[a]) < < 16 | ord(dc[b]) << 8 | ord(dc[c])
     for i in range(4):
       final += itoa64[v & 0x3f]
       v >>= 6
   v = ord(dc[11])
   for i in range(2):
     final += itoa64[v & 0x3f]
     v >>= 6
   

9. Clear virtual memory:

   memset(dc, 0, length(dc))
   

Notice that between steps 5 and 6, the virtual memory is cleared, leaving the digest "final" as NULLs. Yet, in step 6, the for-loop attempts to address the first byte of digest "final". It seems clear that PHK introduced a bug in this algorithm, that was never fixed. As such, every implementation must add a C NULL in step 6, instead of final[0]. Otherwise, you will end up with a different output than the original source code by PHK.

Anyway, that's the algorithm behind md5crypt(). Here's a simple Python implementation that creates valid md5crypt() hashes:

Ulrich Drepper created a "sha256crypt()" as well as "sha512crypt()" function, which is very similar in design, and which I'll blog about later.

It's important to note, that while PHK may have announced md5crypt() as insecure, it's not for the reasons you think. Yes, MD5 is broken, horribly, horribly broken. However, these breaks only deal with the compression function and blind collision attacks. MD5 is not broken with preimage or second preimage collisions. In the case of a stored md5crypt() hash, it requires either a brute force search or a preimage attack to find the plaintext that produced the hash. MD5 is secure with preimage attacks. The reason md5crypt() has been deemed as "insecure", is because MD5 is fast, fast, fast. Instead, password hashing should be slow, slow, slow, and no amount of creativity with MD5 can adequately address its performance. As such, you should migrate to a password hashing solution designed specifically to slow attackers, such as bcrypt or scrypt, with appropriate parameters for security margins.