6.16 Using a Block Cipher to Build a Full-Strength Hash Function

6.16.1 Problem

Given a block cipher, you want to produce a one-way hash function, where finding collisions should always be as hard as inverting the block cipher.

6.16.2 Solution

Use MDC-2, which is a construction that turns a block cipher into a hash function using two Matyas-Meyer-Oseas hashes and a bit of postprocessing.

6.16.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 MDC-2 message digest construction turns an arbitrary block cipher into a one-way hash function. It's different from Davies-Meyer and Matyas-Meyer-Oseas in that the output of the hash function is twice the block length of the cipher. It is also protected by patent until August 28, 2004.

However, MDC-2 does use two instances of Matyas-Meyer-Oseas as components in its construction. Matyas-Meyer-Oseas hashes block by block and uses the internal state as a key used to encrypt each block of input. The resulting ciphertext is XOR'd with the block of input, and the output of that operation becomes the new internal state. The output of the hash function is the final internal state (though if the block size is not equal to the key size, it may need to be expanded, usually by repeating the value). The initial value of the internal state can be any arbitrary constant. See Figure 6-2 for a depiction of how one block of the message is treated.

Figure 6-2. The Mayas-Meyer-Oseas construct

An issue with Matyas-Meyer-Oseas is that the cipher block size can be smaller than the key size, so you might need to expand the internal state somehow before using it to encrypt. Simply duplicating part of the key is sufficient. In the code we provide with this recipe, though, we'll assume that you want to use AES with 128-bit keys. Because the block size of AES is also 128 bits, there doesn't need to be an expansion operation.

MDC-2 is based on Matyas-Meyer-Oseas. There are two internal states instead of one, and each is initialized with a different value. Each block of input is copied, and the two copies go through one round of Matyas-Meyer-Oseas separately. Then, before the next block of input is processed, the two internal states are shuffled a bit; the lower halves of the two states are swapped. This is all illustrated for one block of the message in Figure 6-3.

Figure 6-3. The MDC-2 construct

Clearly, input needs to be padded to the block size of the cipher. We do this internally to our implementation by adding a 1 bit to the end of the input, then as many zeros as are necessary to make the resulting string block-aligned.

One important thing to note about MDC-2 (as well as Matyas-Meyer-Oseas) is that there are ways to extend a message to get the same hash as a result, unless you do something to improve the function. The typical solution is to use MD-strengthening, which involves adding to the end of the input a block that encodes the length of the input. We do that in the code presented later in this section.

Our API allows for incremental processing of messages, which means that there is a context object. The type for our context object is named SPC_MDC2_CTX. As with other hash functions presented in this chapter, the incremental API has three operations: initialization, updating (where data is processed), and finalization (where the resulting hash is output).

The initialization function has the following signature:

void spc_mdc2_init(SPC_MDC2_CTX *c);

All this function does is set internal state to the correct starting values.

Processing data is actually done by the following updating function:

void spc_mdc2_update(SPC_MDC2_CTX *c, unsigned char *t, size_t l);

This function hashes l bytes located at memory address t into the context c.

The result is obtained with the following finalization function:

void spc_mdc2_final(SPC_MDC2_CTX *c, unsigned char *output);

The output argument is always a pointer to a buffer that is twice the block size of the cipher being used. In the case of AES, the output buffer should be 32 bytes.

Following is our implementation of MDC-2, which is intended for use with AES-128. Remember: if you want to use this for other AES key sizes or for ciphers where the key size is different from the block size, you will need to perform some sort of key expansion before calling SPC_ENCRYPT_INIT( ). Of course, you'll also have to change that call to SPC_ENCRYPT_INIT( ) to pass in the desired key length.

#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     /* This implementation only works when the block size is equal to the key size */     typedef struct {   unsigned char h1[SPC_BLOCK_SZ];   unsigned char h2[SPC_BLOCK_SZ];   unsigned char bf[SPC_BLOCK_SZ];   size_t        ix;   size_t        tl; } SPC_MDC2_CTX;     void spc_mdc2_init(SPC_MDC2_CTX *c) {   memset(c->h1, 0x52, SPC_BLOCK_SZ);   memset(c->h2, 0x25, SPC_BLOCK_SZ);   c->ix = 0;   c->tl = 0; }     static void spc_mdc2_oneblock(SPC_MDC2_CTX *c, unsigned char bl[SPC_BLOCK_SZ]) {   int           i, j;   SPC_KEY_SCHED ks1, ks2;       SPC_ENCRYPT_INIT(&ks1, c->h1, SPC_BLOCK_SZ);   SPC_ENCRYPT_INIT(&ks2, c->h2, SPC_BLOCK_SZ);   SPC_DO_ENCRYPT(&ks1, bl, c->h1);   SPC_DO_ENCRYPT(&ks2, bl, c->h2);   j = SPC_BLOCK_SZ / (sizeof(int) * 2);   for (i = 0;  i < SPC_BLOCK_SZ / (sizeof(int) * 2);  i++) {     ((int *)c->h1)[i]     ^= ((int *)bl)[i];     ((int *)c->h2)[i]     ^= ((int *)bl)[i];     ((int *)c->h1)[i + j] ^= ((int *)bl)[i + j];     ((int *)c->h2)[i + j] ^= ((int *)bl)[i + j];     /* Now swap the lower halves using XOR. */     ((int *)c->h1)[i + j] ^= ((int *)c->h2)[i + j];     ((int *)c->h2)[i + j] ^= ((int *)c->h1)[i + j];     ((int *)c->h1)[i + j] ^= ((int *)c->h2)[i + j];   } }     void spc_mdc2_update(SPC_MDC2_CTX *c, unsigned char *t, size_t l) {   c->tl += l;  /* if c->tl < l: abort */   while (c->ix && l) {     c->bf[c->ix++] = *t++;     l--;     if (!(c->ix %= SPC_BLOCK_SZ))       spc_mdc2_oneblock(c, c->bf);   }   while (l > SPC_BLOCK_SZ) {     spc_mdc2_oneblock(c, t);     t += SPC_BLOCK_SZ;     l -= SPC_BLOCK_SZ;   }   c->ix = l;   for (l = 0;  l < c->ix;  l++)     c->bf[l] = *t++; }     void spc_mdc2_final(SPC_MDC2_CTX *c, unsigned char output[SPC_BLOCK_SZ * 2]) {   int i;       c->bf[c->ix++] = 0x80;   while (c->ix < SPC_BLOCK_SZ)     c->bf[c->ix++] = 0;   spc_mdc2_oneblock(c, c->bf);   memset(c->bf, 0, SPC_BLOCK_SZ - sizeof(size_t));   c->tl = htonl(c->tl);   for (i = 0;  i < sizeof(size_t);  i++)      c->bf[SPC_BLOCK_SZ - sizeof(size_t) + i] = ((unsigned char *)(&c->tl))[i];   spc_mdc2_oneblock(c, c->bf);   memcpy(output, c->h1, SPC_BLOCK_SZ);   memcpy(output+SPC_BLOCK_SZ, c->h2, SPC_BLOCK_SZ); }