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

[Scott Arciszewski <[e-mail]>]

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