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

On further consideration, there are enough details* even with an encrypted last block that I’d like to have a proof of correctness for it before I recommend anyone use that approach. As an RFC is not the place for security proofs, I’ll withdraw my suggestion to add this to the draft and concentrate on S2V. 

* eg if somebody appends a block that is a duplicate of the SIV that would not prevent decryption, but then the ciphertext would also not be the last block so would not be decrypted anyway, which means the tag would be computed over the ciphertext and not the plaintext. I need to think about it some more. 

— Neil

> On 18 Dec 2018, at 18:51, Neil Madden <neil.e.madden@gmail.com> wrote:
> 
> In the context of SIV, encrypting the last input prevents any further extension, as any extension will destroy the SIV rendering the plaintext undecryptable and the tag then unverifiable. You’re right that as a general purpose MAC it would either need to have a fixed number of inputs or else encode the length into the first input. 
> 
> — Neil
> 
>> On 18 Dec 2018, at 18:29, Mihir Bellare <mihir@eng.ucsd.edu> wrote:
>> 
>> 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