6.14 Using a MAC That s Optimized for Software Speed

6.14 Using a MAC That's Optimized for Software Speed

6.14.1 Problem

You want to use the MAC that is fastest in software.

6.14.2 Solution

Use a MAC based on Dan Bernstein's hash127, as discussed in the next section. The hash127 library is available from http://cr.yp.to.

6.14.3 Discussion

Be sure to look at our generic recommendations for using a MAC (see Recipe 6.9).

The hash127 algorithm is a universal hash function that can be turned into a secure MAC using AES. It is available from Dan Bernstein's web page: http://cr.yp.to/hash127.html. Follow the directions on how to install the hash127 library. Once the library is compiled, just include the directory containing hash127.h in your include path and link against hash127.a.

Unfortunately, at the time of this writing, the hash127 implementation has not been ported to Windows. Aside from differences in inline assembler syntax between GCC and Microsoft Visual C++, some constants used in the implementation overflow Microsoft Visual C++'s internal token buffer. When a port becomes available, we will update the book's web site with the relevant information.

The way to use hash127 as a MAC is to hash the message you want to authenticate (the hash function takes a key and a nonce as inputs, as well as the message), then encrypt the result of the hash function using AES.

In this recipe, we present an all-in-one MAC API based on hash127, which we call MAC127. This construction first hashes a message using hash127, then uses two constant-time postprocessing operations based on AES. The postprocessing operations give this MAC excellent provable security under strong assumptions.

When initializing the MAC, a 16-byte key is turned into three 16-byte keys by AES-encrypting three constant values. The first two derived keys are AES keys, used for postprocessing. The third derived key is the hash key (though the hash127 algorithm will actually ignore one bit of this key).

Note that Bernstein's hash127 interface has some practical limitations:

• The entire message must be present at the time hash127( ) is called. That is, there's no incremental interface. If you need a fast incremental MAC, use CMAC (discussed in Recipe 6.13) instead.

• The API takes an array of 32-bit values as input, meaning that it cannot accept an arbitrary character string.

However, we can encode the leftover bytes of input in the last parameter passed to hash127( ). Bernstein expects the last parameter to be used for additional per-message keying material. We're not required to use that parameter for keying material (i.e., our construction is still a secure MAC). Instead, we encode any leftover bytes, then unambiguously encode the length of the message.

To postprocess, we encrypt the hash output with one AES key, encrypt the nonce with the other AES key, then XOR the two ciphertexts together. This gives us provable security with good assumptions, plus the additional benefits of a nonce (see Recipe 6.12).

The core MAC127 data type is SPC_MAC127_CTX. There are only two functions: one to initialize a context, and one to MAC a message. The initialization function has the following signature:

void spc_mac127_init(SPC_MAC127_CTX *ctx, unsigned char *key);

This function has the following arguments:

ctx

Context object that holds key material so that several messages may be MAC'd with a single key.

key

Buffer that contains a 16-byte key.

To MAC a message, we use the function spc_mac127( ):

void spc_mac127(SPC_MAC127_CTX *ctx, unsigned char *m, size_t l,                 unsigned char *nonce, unsigned char *out);

This function has the following arguments:

ctx

Context object to be used to perform the MAC.

m

Buffer that contains the message to be authenticated.

l

Length of the message buffer in octets.

nonce

Buffer that contains a 16-byte value that must not be repeated.

out

Buffer into which the output will be placed. It must be at least 16 bytes in size. No more than 16 bytes will ever be written to it.

Here is our implementation of MAC127:

#include <stdlib.h> #ifndef WIN32 #include <sys/types.h> #include <netinet/in.h> #include <arpa/inet.h> #else #include <windows.h> #include <winsock.h> #endif #include <hash127.h>     typedef struct {   struct hash127 hctx;   SPC_KEY_SCHED  ekey;   SPC_KEY_SCHED  nkey; } SPC_MAC127_CTX;     void spc_mac127_init(SPC_MAC127_CTX *ctx, unsigned char key[16]) {   int                    i;   unsigned char          pt[16] = {0, };   volatile int32         hk[4];   volatile unsigned char ek[16], nk[16];      SPC_ENCRYPT_INIT(&(ctx->ekey), key, 16);   SPC_DO_ENCRYPT(&(ctx->ekey), pt, (unsigned char *)ek);   pt[15] = 1;   SPC_DO_ENCRYPT(&(ctx->ekey), pt, (unsigned char *)nk);   pt[15] = 2;   SPC_DO_ENCRYPT(&(ctx->ekey), pt, (unsigned char *)hk);   SPC_ENCRYPT_INIT(&(ctx->ekey), (unsigned char *)ek, 16);   SPC_ENCRYPT_INIT(&(ctx->nkey), (unsigned char *)nk, 16);   hk[0] = htonl(hk[0]);   hk[1] = htonl(hk[1]);   hk[2] = htonl(hk[2]);   hk[3] = htonl(hk[3]);   hash127_expand(&(ctx->hctx), (int32 *)hk);   hk[0] = hk[1] = hk[2] = hk[3] = 0;   for (i = 0;  i < 16;  i++) ek[i] = nk[i] = 0; }     void spc_mac127(SPC_MAC127_CTX *c, unsigned char *msg, size_t mlen,                  unsigned char nonce[16], unsigned char out[16]) {   int   i, r = mlen % 4; /* leftover bytes to stick into final block */   int32 x[4] = {0,};       for (i = 0;  i <r;  i++) ((unsigned char *)x)[i] = msg[mlen - r + i];   x[3] = (int32)mlen;   hash127_little((int32 *)out, (int32 *)msg, mlen / 4, &(c->hctx), x);   x[0] = htonl(*(int *)out);   x[1] = htonl(*(int *)(out + 4));   x[2] = htonl(*(int *)(out + 8));   x[3] = htonl(*(int *)(out + 12));   SPC_DO_ENCRYPT(&(c->ekey), out, out);   SPC_DO_ENCRYPT(&(c->nkey), nonce, (unsigned char *)x);   ((int32 *)out)[0] ^= x[0];   ((int32 *)out)[1] ^= x[1];   ((int32 *)out)[2] ^= x[2];   ((int32 *)out)[3] ^= x[3]; }

6.14.4 See Also

• hash127 home page: http://cr.yp.to/hash127.html

• Recipe 6.9, Recipe 6.12, Recipe 6.13