Parallelizing MACs by subdividing the message and then aggregating results

Question

Most MACs other than GMAC (and Poly1305?) are not parallelizable. Examples include CMAC and HMAC.

Could these be securely parallelized by computing multiple MACs in parallel and then combining the result? This is sort of academic, just curious though.

Let's say you have a message being that you split into four parts such that M==M1|M2|M3|M4. You then compute CMAC on each of these and then a final CMAC on the results.

T=CMAC(CMAC(M1)|CMAC(M2)|CMAC(M3)|CMAC(M4))

The advantage is that this could be implemented in a way that exploits instruction-level parallelism. Instead of splitting the message into four chunks you could implement this by computing four CMACs in parallel with a stride of 4*B where B is the block size of the cipher (e.g. 128-bit for AES). The final CMAC could also be done sort of in parallel with the last block of each component CMAC.

You could also potentially use those crazy 4X parallel AES instructions on CPUs that support AVX-512 to do four CMACs in true parallel.

Obviously, the result would be different from CMAC(M), but would the security be equivalent? This is basically a hash list so I'm thinking yes, but the MAC use case is different from ordinary hash use cases.

Edit: an even bolder thing would be to just compute four CMACs and XOR them, but since XOR is commutative that makes me think it would be vulnerable to chosen-plaintext attacks.

Edit #2: it appears the XOR case may be secure if each MAC is independently keyed, but I'd want to look into it more.

Edit #3: alternatively it seems like CMAC(M1|CMAC(M2)|CMAC(M3)|CMAC(M4)) should be secure if the above is secure. This can be done in parallel by computing CMAC on all four parts (or stripes) of the message and then doing three more blocks of the first CMAC to incorporate the siblings.

Edit #4: thinking about this more, I think the fastest algorithm would be to do N parallel HMACs/CMACs with different keys and then XOR them together. This is secure as long as the MACs are secure. You can't swap anything because the keys are different and so e.g. CMAC[k1](M1) XOR CMAC[k2](M2) != CMAC[k1](M2) XOR CMAC[k2](M1). On an AVX2 enabled machine you could use _mm512_aesenc_epi128 to do four CMACs at once with different keys in true parallel. Even without that instruction level parallelism would kick in if the CPU does it.

So you would have something like (pseudocode, using CMAC-AES with 16-byte blocks):

K1 = KDF(K,1)
K2 = KDF(K,2)
K3 = KDF(K,3)
K4 = KDF(K,4)

while (remaining >= 64) {
  CMAC_BLOCK(K1,input)
  CMAC_BLOCK(K2,input + 16)
  CMAC_BLOCK(K3,input + 32)
  CMAC_BLOCK(K4,input + 48)
  remaining -= 64
  input += 64
}

// ... do final blocks with padding ...

MAC = CMAC_FINAL(K1) XOR CMAC_FINAL(K2) XOR ...

A highly optimized implementation would interpolate the instructions for each AES round to allow ILP to work or use SIMD AES like _mm512_aesenc_epi128 if available.

Answer 1

There are two general approaches to parallelizing MACs:

1. Use a universal hash like GHASH or Poly1305 whose algebraic structure admits essentially arbitrary levels of parallelism.

   For GHASH and Poly1305, the hash is polynomial evaluation:

   \begin{equation} H_r(m_1 \mathbin\| m_2 \mathbin\| \dotsb \mathbin\| m_n) := m_1 r^n + m_2 r^{n-1} + \dotsb + m_n r. \end{equation}

   The naive way to compute this is with Horner's rule:

   \begin{align} h_0 &:= m_1, \\ h_1 &:= h_0 r + m_2, \\ h_2 &:= h_1 r + m_3, \\ &\vdots \\ h_n &:= h_{n-1} r. \end{align}

   If you can compute two multiplications simultaneously, then by precomputing $r^2$ you can process the message two chunks at a time (handling an odd number of message blocks left as exercise for reader):

   \begin{align} h_0 &:= m_1, \\ h_2 &:= h_0 r^2 + m_2 r + m_3, \\ h_4 &:= h_2 r^2 + m_4 r + m_5, \\ &\vdots \\ h_{n-2} &:= h_{n-4} r^2 + m_{n-2} r + m_{n-1}, \\ h_n &:= h_{n-2} r^2 + m_n r. \end{align}

   The same idea extends to an arbitrary degree of parallelism in an implementation without changing the semantics of the MAC you compute. Other universal hashing MACs often have similarly parallelizable algebraic structure, e.g. UMAC which uses a combination of inner products and polynomial evaluation.

2. Use a PRF like BLAKE2 on a tree-structured encoding of a message—Merkle trees.

   If $H$ is a uniform random (secret) function, then so is $$(x, y) \mapsto H(2 \mathbin\| H(0 \mathbin\| x) \mathbin\| H(1 \mathbin\| y))$$ on the appropriate domain, or at least nearly so—this construction is indifferentiable from a random oracle. Then if you instantiate $H = F_k$ for uniform random $k$ where $F$ is a pseudorandom function family, the PRF-security of the construction $$(x, y) \mapsto F_k(2 \mathbin\| F_k(0 \mathbin\| x) \mathbin\| F_k(1 \mathbin\| y))$$ isn't much different from the PRF-security of the primitive $F_k$. And of course a uniform random function makes a good MAC, so the PRF $(x, y) \mapsto F_k(2, F_k(0, x), F_k(1, y))$ makes a good MAC—for fixed-length messages. Here $F_k$ might be, e.g., AES-CMAC or HMAC-SHA256.

   You must take care to encode the message uniquely. If you exposed oracles for $H$ (on short messages only) and $(x, y) \mapsto H(H(x) \mathbin\| H(y))$ (on long messages only), then an adversary could forge the authenticator for $(x, y)$ by querying the $H$ oracle for $x$, for $y$, and for $H(x) \mathbin\| H(y)$. This mistake is not immediately obvious, and appears in real-world protocols like BitTorrent and certificate transparency logs, which is why proposed standards like BLAKE2 tree-hashing and Sakura exist.

   Usually this technique is applied when we want to incrementally verify or modify part of the tree, but you could expand the radix to whatever fanout you want to maximize parallelism. The BLAKE2bp and BLAKE2sp parallel-hashing modes do essentially this with the BLAKE2 compression function as a PRF, but if for some reason you had to use AES-CMAC or HMAC-SHA256, you could use those as PRFs instead in this structure (at considerable cost to performance), provided you uniquely encode all the parameters that figure natively into BLAKE2.

   Merkle trees can attain an essentially arbitrary degree of parallelism, but you must agree in advance to change what MAC you use. Maybe right now you like the idea of four parallel AES-CMACs; maybe tomorrow you would rather have chosen eight; maybe on Tuesday a customer with a small ARM system that can only do one sequential AES-CMAC is sad.

---

What about the constructions you suggested?

T=CMAC(CMAC(M1)|CMAC(M2)|CMAC(M3)|CMAC(M4))

If this is a fixed-depth Merkle tree, then it may make a secure MAC, but the devil is in the details of what oracles you expose for CMAC under your key and how you encode the message into a tree structure. Of course, CMAC doesn't have built-in space for encoding parameters like tree position the way the BLAKE2 compression function does, so you'll have to find another way to do that.

CMAC(M1|CMAC(M2)|CMAC(M3)|CMAC(M4))

Similar to above, but now you are even more likely to accidentally expose an oracle for plain CMAC under your key.

Edit #2: it appears the XOR case may be secure if each MAC is independently keyed, but I'd want to look into it more.

That post discusses $H_1(m) \oplus H_2(m) \oplus \dotsb \oplus H_n(m)$, where the $H_i$ are independently chosen MACs applied to the whole message $m$, but you have taken this to mean $H_1(m_1) \oplus H_2(m_2) \oplus \dotsb \oplus H_n(m_n)$ applied separately to the separate blocks $m_1 \mathbin\| m_2 \mathbin\| \dotsb \mathbin\| m_n$ of $m$. The conclusion you inferred does not follow. (You also have to spend additional time deriving subkeys, of course!)

Answer 2

It looks very much as if you could do a Merkle Tree in which each parallel chunk or stripe of the message is a leaf node. The advantage of a Merkle tree over some novel arrangement is that Merkle trees are extremely well studied with a ton of published research to consult.

If the tree is more than one level deep the evaluation of the intermediate nodes can also be parallelized. Intermediate nodes process only two blocks, so they're fast anyway.

For this application you'd have a fixed size and structure of tree. For example if you wanted 8-way CMAC parallelization you'd have a 4-layer deep tree.

Edit: looks like this and this are great places to start.