[Cfrg] Building a vector-input MAC by chained construction

[Neil Madden <[e-mail]>]

While mulling over some ways to improve JOSE [1], I was looking at the Macaroons paper [2] and realised that the chained-MAC construction they use to allow new caveats to be appended to a Macaroon also serves as a way to convert a normal string-input MAC into one that takes a vector of strings as input instead. This is exactly what the S2V construction in AES-SIV does, and most of the detail in the SIV RFC (and my internet draft extending it to non-AES ciphers) is around S2V.

The chained-MAC construction used in Macaroons is basically the following. If you want to authenticate a vector of strings s[0]…s[n] with a key k, you do the following:

key = k
tag = null
for i = 0 to n:
    tag = MAC(key, s[i])
    key = tag
end

That is, on each iteration you simply use the tag from the last iteration as the MAC key.

Compared to S2V, this is very easy to implement and naturally generalises to different MACs (so long as the tag size is the same as the key size), however it would be costly if MAC has an expensive key setup.

Based on this observation I mocked up a variant of SIV that uses this instead of S2V. The code is almost comically simple - you just perform the above MAC calculation and then encrypt (in-place) the final element s[n] using a stream cipher (e.g. AES-CTR or XChaCha20) using the tag as the SIV. 

The paper [3] has security proofs for this construction based on the assumption that the MAC is a secure PRF (Construction 1 in section 3.1.1). Based on this, my plan is to include this construction as an alternative to S2V in the generalised SIV draft, unless there are strong objections. 

[1] https://neilmadden.blog/2018/12/16/simplifying-jose/
[2] https://ai.google/research/pubs/pub41892
[3] https://cs.nyu.edu/media/publications/TR2013-962.pdf

Kind regards,

Neil