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

From: Neil Madden <[email-masked]>
Date: Tue, 18 Dec 2018 16:55:38 +0000

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

---

From: Mihir Bellare <[email-masked]>
Date: Tue, 18 Dec 2018 10:29:03 -0800

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

---

From: Tony Arcieri <[email-masked]>
Date: Tue, 18 Dec 2018 10:40:47 -0800

> length-2 vector (x1,x2) as tag = MAC(tag1,x2).

This sort of "self-inflicted length extension attack" is leveraged by the
Macaroons construction by design to support an offline attenuation feature
for a credential format, with the caveat that the vector is itself a vector
of caveats. That is to say, in the context of Macaroons, extending the
vector only reduces authority, and can therefore be used by the holder of a
credential to delegate authority to a third party by passing the
credential, removing the original MAC, and adding further restrictions.
That said, ensuring Macaroon caveats only reduce authority, rather than
amplify it, is pretty much left as an exercise to the reader.

This does not seem like a desirable property in the context of a
construction like S2V.

-- 
Tony Arcieri

---

From: Neil Madden <[email-masked]>
Date: Tue, 18 Dec 2018 18:51:47 +0000

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 <[email-masked]> 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
>

---

From: Scott Arciszewski <[email-masked]>
Date: Tue, 18 Dec 2018 13:57:17 -0500

When designing PASETO, I specifically did something like this for feeding
data into the MAC:

function LE64(n) {
    var str = '';
    for (var i = 0; i < 8; ++i) {
        if (i === 7) {
            // Clear the MSB for interoperability
            n &= 127;
        }
        str += String.fromCharCode(n & 255);
        n = n >>> 8;
    }
    return str;
}function PAE(pieces) {
    if (!Array.isArray(pieces)) {
        throw TypeError('Expected an array.');
    }
    var count = pieces.length;
    var output = LE64(count);
    for (var i = 0; i < count; i++) {
        output += LE64(pieces[i].length);
        output += pieces[i];
    }
    return output;
}

Or, in human terms:

First, you feed in the number of pieces (little-endian, unsigned
64-bit integer).

Then, for each piece, you prefix the piece with the length of the
piece (little-endian, 64-bit integer) followed by the data.

Adopting a similar strategy may be advantageous here. (I don't think
we'll have to worry about 64-bit integer overflows in the real world
today, due to bandwidth limitations.)

Scott Arciszewski
Chief Development Officer
Paragon Initiative Enterprises <https://paragonie.com>

On Tue, Dec 18, 2018 at 1:52 PM Neil Madden <[email-masked]> 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
>
>> 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
>>

---

From: Neil Madden <[email-masked]>
Date: Tue, 18 Dec 2018 20:19:54 +0000

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 <[email-masked]> wrote:
>

---

From: Tony Arcieri <[email-masked]>
Date: Tue, 18 Dec 2018 12:34:45 -0800

On Tue, Dec 18, 2018 at 10:52 AM Neil Madden <[email-masked]>
wrote:

> undecryptable and the tag then unverifiable.
>

This is true, although the presence of a length extension attack in what
feels to me like something which could easily be a secure "vMAC" seems like
something of a sharp edge, even if it isn't (at least as you claim to have
proven) strictly necessary for this case..

> 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.
>

These things seem easy enough to add to this construction for
"belt-and-suspenders" value, even in the context of a SIV mode.

--

A more general note (and I hope I'm not hijacking your thread here, let me
know if you think I should make a new thread or feel free to respond in a
separate one): I've implemented AES-SIV as specified in RFC 5297, and also
played around with swapping CMAC for PMAC resulting in a construction I've
been calling "AES-PMAC-SIV".

I've now implemented POLYVAL and am looking at implementing the rest of
AES-GCM-SIV soon. In doing so, I see a lot of parts of the AES-GCM-SIV
construction which are desirable over the RFC 5297 construction:

- Deriving unique keys per message provides better-than-birthday-bound
(BBB) security, and generally eliminates worries about long-term key usage.
For SIV modes this is important because they're useful for keywrapping and
in contexts like KMS services which hold a Key Encrypting Key and
encrypting large numbers of Data Encrypting Keys. There was a talk at
RealWorldCrypto this year by AWS about the challenges of doing this with
AES-GCM, and the RFC 5297-specified AES-SIV suffers the same problem.
- Moving the SIV tag from the front to the end of the message, while
precluding "streaming decryption", makes the overall construction less
weird. When I talk about "weird": there are many in-place AEAD APIs in
which you provide a buffer containing the plaintext and extra space to add
the MAC tag. For the RFC 5297 construction, this involves putting this
extra space at the beginning of a buffer and shifting the plaintext over.
Doing this avoids the need for special case handling of "SIV modes as
opposed to AEAD modes" in APIs and protocols: SIV modes can present an
otherwise standard AEAD API which is potentially just a wrapper around a
more powerful "SIV API".

I've tried various methods of abstracting over these differences, and I
think I've mostly been successful in building abstractions that generalize
over both constructions. However in doing so, and especially lately, I've
been thinking a lot about how AES-GCM-SIV is probably a better framework
for "new SIV modes", and am thinking about what a new AES-PMAC-SIV would
look like which shares more of its design in common with AES-GCM-SIV.

I think that's something you might consider with a ChaCha20 + Poly1305 SIV
mode as well, especially as AES-GCM-SIV is already designed to work with a
universal hash function. I'd be curious to hear your thoughts on this,
especially if you can thing of any drawbacks for your particular use cases.

---

From: Neil Madden <[email-masked]>
Date: Wed, 19 Dec 2018 10:25:18 +0000

|On 18 Dec 2018, at 20:34, Tony Arcieri <[email-masked]> wrote:
> 
> On Tue, Dec 18, 2018 at 10:52 AM Neil Madden <[email-masked]> 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.
> 
> This is true, although the presence of a length extension attack in what feels to me like something which could easily be a secure "vMAC" seems like something of a sharp edge, even if it isn't (at least as you claim to have proven) strictly necessary for this case..
>  
> 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.
> 
> These things seem easy enough to add to this construction for "belt-and-suspenders" value, even in the context of a SIV mode.

I agree. I’ll park it for now, and maybe revisit it later.

> 
> --
> 
> A more general note (and I hope I'm not hijacking your thread here, let me know if you think I should make a new thread or feel free to respond in a separate one): I've implemented AES-SIV as specified in RFC 5297, and also played around with swapping CMAC for PMAC resulting in a construction I've been calling "AES-PMAC-SIV".
> 
> I've now implemented POLYVAL and am looking at implementing the rest of AES-GCM-SIV soon. In doing so, I see a lot of parts of the AES-GCM-SIV construction which are desirable over the RFC 5297 construction:
> 
> - Deriving unique keys per message provides better-than-birthday-bound (BBB) security, and generally eliminates worries about long-term key usage. For SIV modes this is important because they're useful for keywrapping and in contexts like KMS services which hold a Key Encrypting Key and encrypting large numbers of Data Encrypting Keys. There was a talk at RealWorldCrypto this year by AWS about the challenges of doing this with AES-GCM, and the RFC 5297-specified AES-SIV suffers the same problem.

I agree that deriving a unique key for each message is useful. That is what XChaCha20 does too, after all.

Just to be clear though, even without beyond birthday bound security with AES-SIV you can encrypt 2^48 messages before you reach a 2^-32 chance of a collision - that’s over 281 trillion messages. Admittedly you don’t want to get close to that bound, but the birthday bound for a 128-bit block cipher is still quite a lot. It’s specifically GCM that has worse security bounds that limits to 2^32 messages.

(I’d need to dig into my notes to remember if these bounds are for messages or blocks, but for symmetric key-wrapping you are typically only encrypting one or two blocks anyway).

In my own sketches for JOSE improvements I specified that all usage of a key must go through one of HKDF (for symmetric) or ECDH (for public key). The main reason was not primarily a worry about overuse of a key (although I’d certainly sleep better at night), but rather so that I can feed in some context information so that if the same key is used for different purposes then separate keys will be derived with high probability.

> - Moving the SIV tag from the front to the end of the message, while precluding "streaming decryption", makes the overall construction less weird. When I talk about "weird": there are many in-place AEAD APIs in which you provide a buffer containing the plaintext and extra space to add the MAC tag. For the RFC 5297 construction, this involves putting this extra space at the beginning of a buffer and shifting the plaintext over. Doing this avoids the need for special case handling of "SIV modes as opposed to AEAD modes" in APIs and protocols: SIV modes can present an otherwise standard AEAD API which is potentially just a wrapper around a more powerful "SIV API”.

I full agree with this. “Streaming decryption” is something of an anti-pattern anyway, as it is dangerous to release plaintext before you have verified the tag.

> 
> I've tried various methods of abstracting over these differences, and I think I've mostly been successful in building abstractions that generalize over both constructions. However in doing so, and especially lately, I've been thinking a lot about how AES-GCM-SIV is probably a better framework for "new SIV modes", and am thinking about what a new AES-PMAC-SIV would look like which shares more of its design in common with AES-GCM-SIV.
> 
> I think that's something you might consider with a ChaCha20 + Poly1305 SIV mode as well, especially as AES-GCM-SIV is already designed to work with a universal hash function. I'd be curious to hear your thoughts on this, especially if you can thing of any drawbacks for your particular use cases.

I think you’re probably right about this. I will re-read the AES-GCM-SIV papers and have a think about what is best practice here.

Kind regards,

Neil