6.22 Parallelizing MACs

6.22.1 Problem

You want to use a MAC, but parallelize the computation.

6.22.2 Solution

Run multiple MACs at the same time, then MAC the resulting tags together (and in order) to yield one tag.

6.22.3 Discussion

If you want to perform message authentication in parallel, you can do so with a variation of interleaving (which we discussed for block ciphers in Recipe 5.12 through Recipe 5.14) Basically, you can run multiple MACs keyed separately at the same time and divide up the data stream between those MACs. For example, you might run two MACs in parallel and alternate sending 64 bytes to each MAC.

The problem with doing this is that your two MAC's authentication values need to be tied together; otherwise, someone could rearrange the two halves of your stream. For example, if you were to MAC this message:

ABCDEFGHIJKL

where MAC 1 processed the first six characters, yielding tag A, and MAC 2 processed the final six, yielding tag B, an attacker could rearrange the message to be:

GHIJKLABCDEF

and report the tags in the reverse order. Authentication would not detect the change. To solve this problem, once all the MACs are reported, MAC all the resulting tags to create a composite MAC. Alternatively, you could take the last MAC context and add in the MAC values for the other contexts before generating the tag, as illustrated in Figure 6-8.

Figure 6-8. Properly interleaving MACs

If your MAC accepts a nonce, you can use the same key for each context, as long as you never reuse a {key, nonce} pair.

Here's a simple sequential example that runs two OMAC1 contexts, alternating every 512 bytes, that produces a single resulting tag of 16 bytes. It uses the OMAC1 implementation from Recipe 6.11.

#include <stddef.h>
   
#define INTERLEAVE_SIZE 512
   
unsigned char *spc_double_mac(unsigned char *text, size_t len,
                                unsigned char key[16]) {
  SPC_OMAC_CTX      ctx1, ctx2;
  unsigned char *out = (unsigned char *)malloc(16);
  unsigned char tmp[16];
   
  if (!out) abort(); /* Consider throwing an exception instead. */
  spc_omac1_init(&ctx1, key, 16);
  spc_omac1_init(&ctx2, key, 16);
  while (len > 2 * INTERLEAVE_SIZE) {
    spc_omac_update(ctx1, text, INTERLEAVE_SIZE);
    spc_omac_update(ctx2, text + INTERLEAVE_SIZE, INTERLEAVE_SIZE);
    text += 2 * INTERLEAVE_SIZE;
    len  -= 2 * INTERLEAVE_SIZE;
  }
  if (len > INTERLEAVE_SIZE) {
    spc_omac_update(ctx1, text, INTERLEAVE_SIZE);
    spc_omac_update(ctx2, text + INTERLEAVE_SIZE, len - INTERLEAVE_SIZE);
  } else spc_omac_update(ctx1, text, len);
  spc_omac_final(ctx1, tmp);
  spc_omac_update(ctx2, tmp, sizeof(tmp));
  spc_omac_final(ctx2, out);
  return out;
}

6.22.4 See Also

Recipe 5.11, Recipe 6.12 through Recipe 6.14