6.12 Using HMAC or OMAC with a Nonce

6.12.1 Problem

You want to use HMAC or OMAC, but improve its resistance to birthday attacks and capture replay attacks.

6.12.2 Solution

Use an ever-incrementing nonce that is concatenated to your message.

6.12.3 Discussion

Be sure to actually test the nonce when validating the nonce value, so as to thwart capture replay attacks. (See Recipe 6.21.)

If you're using an off-the-shelf HMAC implementation, such as OpenSSL's or CryptoAPI's, you can easily concatenate your nonce to the beginning of your message.

You should use a nonce that's at least half as large as your key size, if not larger. Ultimately, we would recommend that any nonce contain a message counter that is 64 bits (it can be smaller if you're 100% sure you'll never use every counter value) and a random portion that is at least 64 bits. The random portion can generally be chosen per session instead of per message.

Here's a simple wrapper that provides a nonced all-in-one version of OMAC1, using the implementation from Recipe 6.11 and a 16-byte nonce:

void spc_OMAC1_nonced(unsigned char key[  ], int keylen, unsigned char in[  ],
                      size_t l, unsigned char nonce[16], unsigned char out[16]) {
  if (!spc_omac1_init(&c, key, keylen)) abort(  );
  spc_omac_update(&c, nonce, 16);
  spc_omac_update(&c, in, l);
  spc_omac_final(&c, out);

6.12.4 See Also

Recipe 6.11, Recipe 6.21