6.15 Constructing a Hash Function from a Block Cipher

6.15.1 Problem

You're in an environment in which you'd like to use a hash function, but you would prefer to use one based on a block cipher. This might be because you have only a block cipher available, or because you would like to minimize security assumptions in your system.

6.15.2 Solution

There are several good algorithms for doing this. We present one, Davies-Meyer, where the digest size is the same as the block length of the underlying cipher. With 64-bit block ciphers, Davies-Meyer does not offer sufficient security unless you add a nonce, in which case it is barely sufficient. Even with AES-128, without a nonce, Davies-Meyer is somewhat liberal when you consider birthday attacks.

Unfortunately, there is only one well-known scheme worth using for converting a block cipher into a hash function that outputs twice the block length (MDC-2), and it is patented at the time of this writing. However, those patent issues will go away by August 28, 2004. MDC-2 is covered in Recipe 6.16.

Note that such constructs assume that block ciphers resist related-key attacks. See Recipe 6.3 for a general comparison of such constructs compared to dedicated constructs like SHA1.

6.15.3 Discussion

Hash functions do not provide security in and of themselves! If you need to perform message integrity checking, use a MAC instead.

The Davies-Meyer hash function uses the message to hash as key material for the block cipher. The input is padded, strengthened, and broken into blocks based on the key length, each block used as a key to encrypt a single value. Essentially, the message is broken into a series of keys.

With Davies-Meyer, the first value encrypted is an initialization vector (IV) that is usually agreed upon in advance. You may treat it as a nonce instead, however, which we strongly recommend. (The nonce is then as big as the block size of the cipher.) The result of encryption is XOR'd with the IV, then used as a new IV. This is repeated until all keys are exhausted, resulting in the hash output. See Figure 6-1 for a visual description of one pass of Davies-Meyer.

Figure 6-1. The Davies-Meyer construct

Traditionally, hash functions pad by appending a bit with a value of 1, then however many zeros are necessary to align to the next block of input. Input is typically strengthened by adding a block of data to the end that encodes the message length. Nonetheless, such strengthening does not protect against length-extension attacks. (To prevent against those, see Recipe 6.7.)

Matyas-Meyer-Oseas is a similar construction that is preferable in that the plaintext itself is not used as the key to a block cipher (this could make related-key attacks on Davies-Meyer easier); we'll present that as a component when we show how to implement MDC-2 in Recipe 6.16.

Here is an example API for using Davies-Meyer wihtout a nonce:

void spc_dm_init(SPC_DM_CTX *c);
void spc_dm_update(SPC_DM_CTX *c, unsigned char *msg, size_t len);
void spc_dm_final(SPC_DM_CTX *c, unsigned char out[SPC_BLOCK_SZ]);

The following is an implementation using AES-128. This code requires linking against an AES implementation, and it also requires that the macros developed in Recipe 5.5 be defined (they bridge the API of your AES implementation with this book's API).

#include <stdlib.h>
#include <string.h>
#ifndef WIN32
#include <sys/types.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#else
#include <windows.h>
#include <winsock.h>
#endif
   
#define SPC_KEY_SZ 16
   
typedef struct {
  unsigned char h[SPC_BLOCK_SZ];
  unsigned char b[SPC_KEY_SZ];
  size_t        ix;
  size_t        tl;
} SPC_DM_CTX;
   
void spc_dm_init(SPC_DM_CTX *c) {
  memset(c->h, 0x52, SPC_BLOCK_SZ);
  c->ix = 0;
  c->tl = 0;
}
   
static void spc_dm_once(SPC_DM_CTX *c, unsigned char b[SPC_KEY_SZ]) {
  int           i;
  SPC_KEY_SCHED ks; 
  unsigned char tmp[SPC_BLOCK_SZ];
   
  SPC_ENCRYPT_INIT(&ks, b, SPC_KEY_SZ); 
  SPC_DO_ENCRYPT(&ks, c->h, tmp);
  for (i = 0;  i < SPC_BLOCK_SZ / sizeof(int);  i++)
    ((int *)c->h)[i] ^= ((int *)tmp)[i];
}
   
void spc_dm_update(SPC_DM_CTX *c, unsigned char *t, size_t l) {
  c->tl += l;  /* if c->tl < l: abort */
  while (c->ix && l) {
    c->b[c->ix++] = *t++;
    l--;
    if (!(c->ix %= SPC_KEY_SZ)) spc_dm_once(c, c->b);
  }
  while (l > SPC_KEY_SZ) {
    spc_dm_once(c, t);
    t += SPC_KEY_SZ;
    l -= SPC_KEY_SZ;
  }
  c->ix = l;
  for (l = 0;  l < c->ix;  l++) c->b[l] = *t++;
}
   
void spc_dm_final(SPC_DM_CTX *c, unsigned char output[SPC_BLOCK_SZ]) {
  int i;
   
  c->b[c->ix++] = 0x80;
  while (c->ix < SPC_KEY_SZ) c->b[c->ix++] = 0;
  spc_dm_once(c, c->b);
  memset(c->b, 0, SPC_KEY_SZ - sizeof(size_t));
  c->tl = htonl(c->tl);
  for (i = 0;  i < sizeof(size_t);  i++)
    c->b[SPC_KEY_SZ - sizeof(size_t) + i] = ((unsigned char *)(&c->tl))[i];
  spc_dm_once(c, c->b);
  memcpy(output, c->h, SPC_BLOCK_SZ);
}

6.15.4 See Also

Recipe 5.5, Recipe 6.3, Recipe 6.7, Recipe 6.16