6.11 Using OMAC (a Simple Block Cipher-Based MAC)

6.11.1 Problem

You want to use a simple MAC based on a block cipher, such as AES.

6.11.2 Solution

Use the OMAC implementation provided in Section 6.11.3.

6.11.3 Discussion

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

OMAC is a straightforward message authentication algorithm based on the CBC-encryption mode. It fixes some security problems with the naïve implementation of a MAC from CBC mode (CBC-MAC). In particular, that MAC is susceptible to length-extension attacks, similar to the ones we consider for cryptographic hash functions in Recipe 6.7.

OMAC has been explicitly specified for AES, and it is easy to adapt to any 128-bit block cipher. It is possible, but a bit more work, to get it working with ciphers with 64-bit blocks. In this section, we only cover using OMAC with AES.

The basic idea behind using CBC mode as a MAC is to encrypt a message in CBC mode and throw away everything except the very last block of output. That's not generally secure, though. It only works when all messages you might possibly process are a particular size.

Besides OMAC, there are several MACs that try to fix the CBC-MAC problem, including XCBC-MAC, TMAC, and RMAC:

RMAC: RMAC (the R stands for randomized) has security issues in the general case, and is not favored by the cryptographic community.^[6]

^[6] Most importantly, RMAC requires the underlying block cipher to protect against related-key attacks, where other constructs do not. Related-key attacks are not well studied, so it's best to prefer constructs that can avoid them when possible.
XCBC-MAC: XCBC-MAC (eXtended CBC-MAC) is the foundation for TMAC and OMAC, but it uses three different keys.
TMAC: TMAC uses two keys (thus the T in the name).

OMAC is the first good CBC-MAC derivative that uses a single key. OMAC works the same way CBC-MAC does until the last block, where it XORs the state with an additional value before encrypting. That additional value is derived from the result of encrypting all zeros, and it can be performed at key setup time. That is, the additional value is key-dependent, not message-dependent.

OMAC is actually the name of a family of MAC algorithms. There are two concrete versions, OMAC1 and OMAC2, which are slightly different but equally secure. OMAC1 is slightly preferable because its key setup can be done a few cycles more quickly than OMAC2's key setup. NIST is expected to standardize on OMAC1.

First, we provide an incremental API for using OMAC. This code requires linking against an AES implementation, and also that the macros developed in Recipe 5.5 be defined (they bridge the API of your AES implementation with this book's API). The secure memory function spc_memset( ) from Recipe 13.2 is also required.

To use this API, you must instantiate an SPC_OMAC_CTX object and pass it to the various API functions. To initialize the context, call either spc_omac1_init( ) or spc_omac2_init( ), depending on whether you want to use OMAC1 or OMAC2. The initialization functions always return success unless the key length is invalid, in which case they return 0. Successful initialization is indicated by a return value of 1.

int spc_omac1_init(SPC_OMAC_CTX *ctx, unsigned char *key, int keylen);
int spc_omac2_init(SPC_OMAC_CTX *ctx, unsigned char *key, int keylen);

These functions have the following arguments:

ctx: Context object to be initialized.
key: Block cipher key.
keylen: Length of the key in bytes. The length of the key must be 16, 24, or 32 bytes; any other key length is invalid.

Once initialized, spc_omac_update( ) can be used to process data. Note that the only differences between OMAC1 and OMAC2 in this implementation are handled at key setup time, so they both use the same functions for updating and finalization. Multiple calls to spc_omac_update( ) act just like making a single call where all of the data was concatenated together. Here is its signature:

void spc_omac_update(SPC_OMAC_CTX *ctx, unsigned char *in, size_t il);

This function has the following arguments:

ctx: Context object to use for the current message.
in: Buffer that contains the data to be processed.
il: Length of the data buffer to be processed in bytes.

To obtain the output of the MAC operation, call spc_omac_final( ), which has the following signature:

int spc_omac_final(SPC_OMAC_CTX *ctx, unsigned char *out);

This function has the following arguments:

ctx: Context object to be finalized.
out: Buffer into which the output will be placed. This buffer must be at least 16 bytes in size. No more than 16 bytes will ever be written to it.

Here is the code implementing OMAC:

#include <stdlib.h>

typedef struct {
  SPC_KEY_SCHED ks;
  int           ix;
  unsigned char iv[SPC_BLOCK_SZ];
  unsigned char c1[SPC_BLOCK_SZ]; /* L * u */
  unsigned char c2[SPC_BLOCK_SZ]; /* L / u */
} SPC_OMAC_CTX;
   
int spc_omac1_init(SPC_OMAC_CTX *ctx, unsigned char *key, int keylen) {
  int           condition, i;
  unsigned char L[SPC_BLOCK_SZ] = {0,};
   
  if (keylen != 16 && keylen != 24 && keylen != 32) return 0;
   
  SPC_ENCRYPT_INIT(&(ctx->ks), key, keylen);
  SPC_DO_ENCRYPT(&(ctx->ks), L, L);
  spc_memset(ctx->iv, 0, SPC_BLOCK_SZ);
  ctx->ix = 0;
   
  /* Compute L * u */
  condition = L[0] & 0x80;
  ctx->c1[0] = L[0] << 1;
  for (i = 1;  i < SPC_BLOCK_SZ; i++) {
    ctx->c1[i - 1] |= L[i] >> 7;
    ctx->c1[i]      = L[i] << 1;
  }
  if (condition) ctx->c1[SPC_BLOCK_SZ - 1] ^= 0x87;
   
  /* Compute L * u * u */
  condition  = ctx->c1[0] & 0x80;
  ctx->c2[0] = ctx->c1[0] << 1;
  for (i = 1;  i < SPC_BLOCK_SZ;  i++) {
    ctx->c2[i - 1] |= ctx->c1[i] >> 7;
    ctx->c2[i]      = ctx->c1[i] << 1;
  }
  if (condition) ctx->c2[SPC_BLOCK_SZ - 1] ^= 0x87;
  spc_memset(L, 0, SPC_BLOCK_SZ);
  return 1;
}
   
int spc_omac2_init(SPC_OMAC_CTX *ctx, unsigned char *key, int keylen) {
  int           condition, i;
  unsigned char L[SPC_BLOCK_SZ] = {0,};
   
  if (keylen != 16 && keylen != 24 && keylen != 32) return 0;
   
  SPC_ENCRYPT_INIT(&(ctx->ks), key, keylen);
  SPC_DO_ENCRYPT(&(ctx->ks), L, L);
  spc_memset(ctx->iv, 0, SPC_BLOCK_SZ);
  ctx->ix = 0;
   
  /* Compute L * u, storing it in c1 */
  condition  = L[0] >> 7;
  ctx->c1[0] = L[0] << 1;
  for (i = 1;  i < SPC_BLOCK_SZ;  i++) {
    ctx->c1[i - 1] |= L[i] >> 7;
    ctx->c1[i]      = L[i] << 1;
  }
  if (condition) ctx->c1[SPC_BLOCK_SZ - 1] ^= 0x87;
   
  /* Compute L * u ^ -1, storing it in c2 */
  condition = L[SPC_BLOCK_SZ - 1] & 0x01;
  i = SPC_BLOCK_SZ;
  while (--i) ctx->c2[i] = (L[i] >> 1) | (L[i - 1] << 7);
  ctx->c2[0] = L[0] >> 1;
  L[0] >>= 1;
  if (condition) {
    ctx->c2[0]                ^= 0x80;
    ctx->c2[SPC_BLOCK_SZ - 1] ^= 0x43;
  }
  spc_memset(L, 0, SPC_BLOCK_SZ);
  return 1;
}
   
void spc_omac_update(SPC_OMAC_CTX *ctx, unsigned char *in, size_t il) {
  int i;
   
  if (il < SPC_BLOCK_SZ - ctx->ix) {
    while (il--) ctx->iv[ctx->ix++] ^= *in++;
    return;
  }
  if (ctx->ix) {
    while (ctx->ix < SPC_BLOCK_SZ) --il, ctx->iv[ctx->ix++] ^= *in;
    SPC_DO_ENCRYPT(&(ctx->ks), ctx->iv, ctx->iv);
  }
  while (il > SPC_BLOCK_SZ) {
    for (i = 0;  i < SPC_BLOCK_SZ / sizeof(int);  i++)
      ((unsigned int *)(ctx->iv))[i] ^= ((unsigned int *)in)[i];
    SPC_DO_ENCRYPT(&(ctx->ks), ctx->iv, ctx->iv);
    in += SPC_BLOCK_SZ;
    il -= SPC_BLOCK_SZ;
  }
  for (i = 0;  i < il;  i++) ctx->iv[i] ^= in[i];
  ctx->ix = il;
}
   
int spc_omac_final(SPC_OMAC_CTX *ctx, unsigned char *out) {
  int i;
   
  if (ctx->ix != SPC_BLOCK_SZ) {
    ctx->iv[ctx->ix] ^= 0x80;
    for (i = 0;  i < SPC_BLOCK_SZ / sizeof(int);  i++)
      ((int *)ctx->iv)[i] ^= ((int *)ctx->c2)[i];
  } else {
    for (i = 0;  i < SPC_BLOCK_SZ / sizeof(int);  i++)
      ((int *)ctx->iv)[i] ^= ((int *)ctx->c1)[i];
  }
  SPC_DO_ENCRYPT(&(ctx->ks), ctx->iv, out);
  return 1;
}

For those interested in the algorithm itself, note that we precompute two special values at key setup time, both of which are derived from the value we get from encrypting the all-zero data block. Each precomputed value is computed by using a 128-bit shift and a conditional XOR. The last block of data is padded, if necessary, and XOR'd with one of these two values, depending on its length.

Here is an all-in-one wrapper to OMAC, exporting both OMAC1 and OMAC2:

int SPC_OMAC1(unsigned char key[  ], int keylen, unsigned char in[  ], size_t l,
              unsigned char out[16]) {
  SPC_OMAC_CTX c;
  
  if (!spc_omac1_init(&c, key, keylen)) return 0;
  spc_omac_update(&c, in, l);
  spc_omac_final(&c, out);
  return 1;
}
   
int SPC_OMAC2(unsigned char key[  ], int keylen, unsigned char in[  ], size_t l,
              unsigned char out[16]) {
  SPC_OMAC_CTX c;
   
  if (!spc_omac2_init(&c, key, keylen)) return 0;
  spc_omac_update(&c, in, l);
  spc_omac_final(&c, out);
  return 1;
}

[ Team LiB ]

6.11 Using OMAC (a Simple Block Cipher-Based MAC)

6.11.1 Problem

6.11.2 Solution

6.11.3 Discussion

6.11.4 See Also