8.10 Performing Password-Based Authentication with MD5-MCF

8.10.1 Problem

You want to use MD5 as a method for encrypting passwords.

8.10.2 Solution

Many modern systems support the use of MD5 for encrypting passwords. An encoding known as Modular Crypt Format (MCF) is used to allow the use of the traditional crypt( ) function to handle the old DES encryption as well as MD5 and any number of other possible algorithms.

On systems that support MCF through crypt( ),[2] you can simply use crypt( ) as discussed in Recipe 8.9 with some modification to the required salt. Otherwise, you can use the implementation in this recipe.

[2] FreeBSD, Linux, and OpenBSD support MCF via crypt( ). Darwin, NetBSD, and Solaris do not. Windows also does not because it does not support crypt( ) at all.

8.10.3 Discussion

What we are doing here isn't really encrypting a password. Actually, we are creating a password validator. We use the term encryption because it is in common use and is a more concise way to explain the process.

MCF is a 7-bit encoding that allows for encoding multiple fields into a single string. A dollar sign delimits each field, with the first field indicating the algorithm to use by way of a predefined number. At present, only two well-known algorithms are defined: 1 indicates MD5 and 2 indicates Blowfish. The contents of the first field also dictate how many fields should follow and the type of data each one contains. The first character in an MCF string is always a dollar sign, which technically leaves the 0th field empty.

For encoding MD5 in MCF, the first field must contain a 1, and two additional fields must follow: the first is the salt, and the second is the MD5 checksum that is calculated from a sequence of MD5 operations based on a nonintuitive process that depends on the value of the salt and the password. The intent behind this process was to slow down brute-force attacks; however, we feel that the algorithm is needlessly complex, and there are other, better ways to achieve the same goals.

As with the traditional DES-based crypt( ), we do not recommend that you use MD5-MCF in new authentication systems. You should use it only when you must maintain compatibility with existing systems. We recommend that you consider using something like PBKDF2 instead. (See Recipe 8.11.)

The function spc_md5_encrypt( ) implements a crypt( )-like function that uses the MD5-MCF method that we've described. If it is successful (the only error that should ever occur is an out-of-memory error), it will return a dynamically allocated buffer that contains the encrypted password in MCF.

In this recipe, we present two versions of spc_md5_encrypt( ) in their entirety. The first uses OpenSSL and standard C runtime functions; the second uses the native Win32 API and CryptoAPI.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <openssl/md5.h>
   
static char *crypt64_encode(const unsigned char *buf) {
  int           i;
  char          *out, *ptr;
  unsigned long l;
   
  static char   *crypt64_set = "./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
                               "abcdefghijklmnopqrstuvwxyz";
   
  if (!(out = ptr = (char *)malloc(23))) return 0;
   
#define CRYPT64_ENCODE(x, y, z)                                            \
  for (i = 0, l = (buf[(x)] << 16) | (buf[(y)] << 8) | buf[(z)];  i++ < 4; \
    l >>= 6) *ptr++ = crypt64_set[l & 0x3F]
   
  CRYPT64_ENCODE(0,  6, 12);  CRYPT64_ENCODE(1,  7, 13);
  CRYPT64_ENCODE(2,  8, 14);  CRYPT64_ENCODE(3,  9, 15);
  CRYPT64_ENCODE(4, 10,  5);
   
  for (i = 0, l = buf[11];  i++ < 2;  l >>= 6) *ptr++ = crypt64_set[l & 0x3F];
  *ptr = 0;
   
#undef CRYPT64_ENCODE
   
  return out;
}
   
static void compute_hash(unsigned char *hash, const char *key,
                         const char *salt, size_t salt_length) {
  int     i, length;
  size_t  key_length;
  MD5_CTX ctx, ctx1;
   
  key_length = strlen(key);
  MD5_Init(&ctx);
  MD5_Update(&ctx, key, key_length);
  MD5_Update(&ctx, salt, salt_length);
   
  MD5_Init(&ctx1);
  MD5_Update(&ctx1, key, key_length);
  MD5_Update(&ctx1, salt, salt_length);
  MD5_Update(&ctx1, key, key_length);
  MD5_Final(hash, &ctx1);
   
  for (length = key_length;  length > 0;  length -= 16)
    MD5_Update(&ctx, hash, (length > 16 ? 16 : length));
  memset(hash, 0, 16);
  for (i = key_length;  i;  i >>= 1)
    if (i & 1) MD5_Update(&ctx, hash, 1);
    else MD5_Update(&ctx, key, 1);
  MD5_Final(hash, &ctx);
   
  for (i = 0;  i < 1000;  i++) {
    MD5_Init(&ctx);
    if (i & 1) MD5_Update(&ctx, key, key_length);
    else MD5_Update(&ctx, hash, 16);
    if (i % 3) MD5_Update(&ctx, salt, salt_length);
    if (i % 7) MD5_Update(&ctx, key, key_length);
    if (i & 1) MD5_Update(&ctx, hash, 16);
    else MD5_Update(&ctx, key, key_length);
    MD5_Final(hash, &ctx);
  }
}
   
char *spc_md5_encrypt(const char *key, const char *salt) {
  char          *base64_out, *base64_salt, *result, *salt_end, *tmp_string;
  size_t        result_length, salt_length;
  unsigned char out[16], raw_salt[16];
   
  base64_out = base64_salt = result = 0;
   
  if (!salt) {
    salt_length = 8;
    spc_rand(raw_salt, sizeof(raw_salt));
    if (!(base64_salt = crypt64_encode(raw_salt))) goto done;
    if (!(tmp_string = (char *)realloc(base64_salt, salt_length + 1)))
      goto done;
    base64_salt = tmp_string;
  } else {
    if (strncmp(salt, "$1$", 3) != 0) goto done;
    if (!(salt_end = strchr(salt + 3, '$'))) goto done;
    salt_length = salt_end - (salt + 3);
    if (salt_length > 8) salt_length = 8; /* maximum salt is 8 bytes */
    if (!(base64_salt = (char *)malloc(salt_length + 1))) goto done;
    memcpy(base64_salt, salt + 3, salt_length);
  }
  base64_salt[salt_length] = 0;
   
  compute_hash(out, key, base64_salt, salt_length);
   
  if (!(base64_out = crypt64_encode(out))) goto done;
  result_length = strlen(base64_out) + strlen(base64_salt) + 5;
  if (!(result = (char *)malloc(result_length + 1))) goto done;
  sprintf(result, "$1$%s$%s", base64_salt, base64_out);
   
done:
  /* cleanup */
  if (base64_salt) free(base64_salt);
  if (base64_out) free(base64_out);
  return result;
}

We have named the Windows version of spc_md5_encrypt( ) as SpcMD5Encrypt( ) to adhere to conventional Windows naming conventions. In addition, the implementation uses only Win32 API and CryptoAPI functions, rather than relying on the standard C runtime for string and memory handling.

#include <windows.h>
#include <wincrypt.h>
   
static LPSTR Crypt64Encode(BYTE *pBuffer) {
  int   i;
  DWORD dwTemp;
  LPSTR lpszOut, lpszPtr;
   
  static LPSTR lpszCrypt64Set = "./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
                                "abcdefghijklmnopqrstuvwyxz";
   
  if (!(lpszOut = lpszPtr = (char *)LocalAlloc(LMEM_FIXED, 23))) return 0;
   
#define CRYPT64_ENCODE(x, y, z)                                     \
  for (i = 0, dwTemp = (pBuffer[(x)] << 16) | (pBuffer[(y)] << 8) | \
       pBuffer[(z)];  i++ < 4;  dwTemp >>= 6)                       \
    *lpszPtr++ = lpszCrypt64Set[dwTemp & 0x3F]
   
  CRYPT64_ENCODE(0,  6, 12);  CRYPT64_ENCODE(1,  7, 13);
  CRYPT64_ENCODE(2,  8, 14);  CRYPT64_ENCODE(3,  9, 15);
  CRYPT64_ENCODE(4, 10,  5);
   
  for (i = 0,  dwTemp = pBuffer[11];  i++ < 2;  dwTemp >>= 6)
    *lpszPtr++ = lpszCrypt64Set[dwTemp & 0x3F];
  *lpszPtr = 0;
   
#undef CRYPT64_ENCODE
   
  return lpszOut;
}
   
static BOOL ComputeHash(BYTE *pbHash, LPCSTR lpszKey, LPCSTR lpszSalt,
                        DWORD dwSaltLength) {
  int        i, length;
  DWORD      cbHash, dwKeyLength;
  HCRYPTHASH hHash, hHash1;
  HCRYPTPROV hProvider;
   
  dwKeyLength = lstrlenA(lpszKey);
  if (!CryptAcquireContext(&hProvider, 0, MS_DEF_PROV, 0, CRYPT_VERIFYCONTEXT))
    return FALSE;
  if (!CryptCreateHash(hProvider, CALG_MD5, 0, 0, &hHash)) {
    CryptReleaseContext(hProvider, 0);
    return FALSE;
  }
  CryptHashData(hHash, (BYTE *)lpszKey, dwKeyLength, 0);
  CryptHashData(hHash, (BYTE *)lpszSalt, dwSaltLength, 0);
   
  if (!CryptCreateHash(hProvider, CALG_MD5, 0, 0, &hHash1)) {
    CryptDestroyHash(hHash);
    CryptReleaseContext(hProvider, 0);
    return FALSE;
  }
  CryptHashData(hHash1, lpszKey, dwKeyLength, 0);
  CryptHashData(hHash1, lpszSalt, dwSaltLength, 0);
  CryptHashData(hHash1, lpszKey, dwKeyLength, 0);
  cbHash = 16;  CryptGetHashParam(hHash1, HP_HASHVAL, pbHash, &cbHash, 0);
  CryptDestroyHash(hHash1);
   
  for (length = dwKeyLength;  length > 0;  length -= 16)
    CryptHashData(hHash, pbHash, (length > 16 ? 16 : length), 0);
  SecureZeroMemory(pbHash, 16);
  for (i = dwKeyLength;  i;  i >>= 1)
    if (i & 1) CryptHashData(hHash, pbHash, 1, 0);
    else CryptHashData(hHash, lpszKey, 1, 0);
  cbHash = 16;  CryptGetHashParam(hHash, HP_HASHVAL, pbHash, &cbHash, 0);
  CryptDestroyHash(hHash);
   
  for (i = 0;  i < 1000;  i++) {
    if (!CryptCreateHash(hProvider, CALG_MD5, 0, 0, &hHash)) {
      CryptReleaseContext(hProvider, 0);
      return FALSE;
    }
    if (i & 1) CryptHashData(hHash, lpszKey, dwKeyLength, 0);
    else CryptHashData(hHash, pbHash, 16, 0);
    if (i % 3) CryptHashData(hHash, lpszSalt, dwSaltLength, 0);
    if (i & 7) CryptHashData(hHash, lpszKey, dwKeyLength, 0);
    if (i & 1) CryptHashData(hHash, pbHash, 16, 0);
    else CryptHashData(hHash, lpszKey, dwKeyLength, 0);
    cbHash = 16;  CryptGetHashParam(hHash, HP_HASHVAL, pbHash, &cbHash, 0);
    CryptDestroyHash(hHash);
  }
   
  CryptReleaseContext(hProvider, 0);
  return TRUE;
}
   
LPSTR SpcMD5Encrypt(LPCSTR lpszKey, LPCSTR lpszSalt) {
  BYTE  pbHash[16], pbRawSalt[8];
  DWORD dwResultLength, dwSaltLength;
  LPSTR lpszBase64Out, lpszBase64Salt, lpszResult, lpszTemp;
  LPCSTR lpszSaltEnd;
   
  lpszBase64Out = lpszBase64Salt = lpszResult = 0;
   
  if (!lpszSalt) {
    spc_rand(pbRawSalt, (dwSaltLength = sizeof(pbRawSalt)));
    if (!(lpszBase64Salt = Crypt64Encode(pbRawSalt))) goto done;
    if (!(lpszTemp = (LPSTR)LocalReAlloc(lpszBase64Salt, dwSaltLength + 1, 0)))
      goto done;
    lpszBase64Salt = lpszTemp;
  } else {
    if (lpszSalt[0] != '$' || lpszSalt[1] != '1' || lpszSalt[2] != '$') goto done;
    for (lpszSaltEnd = lpszSalt + 3;  *lpszSaltEnd != '$';  lpszSaltEnd++)
      if (!*lpszSaltEnd) goto done;
    dwSaltLength = (lpszSaltEnd - (lpszSalt + 3));
    if (dwSaltLength > 8) dwSaltLength = 8; /* maximum salt is 8 bytes */
    if (!(lpszBase64Salt = (LPSTR)LocalAlloc(LMEM_FIXED,dwSaltLength + 1)))
                                             goto done;
    CopyMemory(lpszBase64Salt, lpszSalt + 3, dwSaltLength);
  }
  lpszBase64Salt[dwSaltLength] = 0;
   
  if (!ComputeHash(pbHash, lpszKey, lpszBase64Salt, dwSaltLength)) goto done;
   
  if (!(lpszBase64Out = Crypt64Encode(pbHash))) goto done;
  dwResultLength = lstrlenA(lpszBase64Out) + lstrlenA(lpszBase64Salt) + 5;
  if (!(lpszResult = (LPSTR)LocalAlloc(LMEM_FIXED, dwResultLength + 1)))
    goto done;
  wsprintfA(lpszResult, "$1$%s$%s", lpszBase64Salt, lpszBase64Out);
   
done:
  /* cleanup */
  if (lpszBase64Salt) LocalFree(lpszBase64Salt);
  if (lpszBase64Out) LocalFree(lpszBase64Out);
  return lpszResult;
}

Verifying a password encrypted using MD5-MCF works the same way as verifying a password encrypted with crypt( ): encrypt the plaintext password with the already encrypted password as the salt, and compare the result with the already encrypted password. If they match, the password is correct.

For the sake of both consistency and convenience, you can use the function spc_md5_verify( ) to verify a password encrypted using MD5-MCF.

int spc_md5_verify(const char *plain_password, const char *crypt_password) {
  int  match = 0;
  char *md5_result;
   
  if ((md5_result = spc_md5_encrypt(plain_password, crypt_password)) != 0) {
    match = !strcmp(md5_result, crypt_password);
    free(md5_result);
  }
  return match;
}

8.10.4 See Also

Recipe 8.9, Recipe 8.11