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

I may be missing something but this does not seem secure. Given the tag
tag1 = MAC(key,x1) of a length-1 vector x1, we can compute the tag of the
length-2 vector (x1,x2) as tag = MAC(tag1,x2).

Mihir

On Tue, Dec 18, 2018 at 8:55 AM Neil Madden <neil.e.madden@gmail.com> wrote:

> 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
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg
>