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

Neil Madden <> Wed, 19 December 2018 10:25 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id D612D1277D2 for <>; Wed, 19 Dec 2018 02:25:25 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -2
X-Spam-Status: No, score=-2 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (2048-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id jpN5HsSwSPTB for <>; Wed, 19 Dec 2018 02:25:23 -0800 (PST)
Received: from ( [IPv6:2a00:1450:4864:20::335]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 5DF8F127598 for <>; Wed, 19 Dec 2018 02:25:23 -0800 (PST)
Received: by with SMTP id g67so5791008wmd.2 for <>; Wed, 19 Dec 2018 02:25:23 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=ipaour/YJfyUSfQD3huEt5wzAcUZXHHP+6jKQlruk7I=; b=SQZy6eudFhvScOUwsSR5DzDfrkYcn7wST3JA6+C5cjvIcs1z7N1RfsnOUiG9R4oB4f CuL4pwcJxdYINaptIMGZ5CuyqR5++fhjKnXIShwXSyXkW8jlkvbuCtgDd2qTBNeZquBI Sqk6EVByIisL1MprDeANjAMIk/nwALU3K7ZYJvirPpzRXlq3OaOuRfCBARZ2y8ZEhSWi uttXI6xkJOYKKw4XdvbhcCDZkr67J+STn0D4ybWwn7rh2YwFHHg1asNbgRLqcFo1XBoC riERT6jc4MHtChbWZJuMJsAUW7iN/l0Tb/qP5cefPKLneUMnp7jKm8eA8prDxo6iFrkw bfFg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=x-gm-message-state:mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=ipaour/YJfyUSfQD3huEt5wzAcUZXHHP+6jKQlruk7I=; b=LWiq3GQvCXuu7EtGnWVAHmB4DHN9Egc0ocBJ9hkFHqYQJGYjhrP2NuIKjCuY1TrLZU 1lrja2vkqQkddLRSl6EwYMTNvep0yt273oYLI4z8PAHIe25M8z+Bv1NR5hTnUZgwKD6y O+unCsbPnBqqWXAC+KlmvsTllXLpxEWUMdz8p66o4gJwtNh5cD3HkQU4XlgiKfNm+CCa +JWqpwkO60DDWEQ7B/Cg2vAOxIBYm+Uzu5UWGaXzoCcm65aIqHI0Ieh5dhicbEFvt759 COMm2XwaOGqkhRFmNF2kjnNzlCparroCnzdREWoP1Xpvk5D4Ci3HkLkIRj/wOW+cK34V f+BA==
X-Gm-Message-State: AA+aEWZMaQ+ko9SipNdEU511XunMJTGRsuVqJMGgkjyhm4Gn/pxdQ3i+ 4HOXymnwqhflxPuHjarJ1Jw=
X-Google-Smtp-Source: AFSGD/UOHwoZI2iRuIwZMg7qjlzzHa+XKJpv2SQ8yjGJKs+D7qNz5HaBUfgFH2fyev0Kw4g5MMcNgQ==
X-Received: by 2002:a1c:650b:: with SMTP id z11mr6606641wmb.23.1545215121609; Wed, 19 Dec 2018 02:25:21 -0800 (PST)
Received: from guest2s-mbp.lan ( []) by with ESMTPSA id y185sm3217963wmg.34.2018. (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 19 Dec 2018 02:25:20 -0800 (PST)
Content-Type: text/plain; charset="utf-8"
Mime-Version: 1.0 (Mac OS X Mail 12.2 \(3445.102.3\))
From: Neil Madden <>
In-Reply-To: <>
Date: Wed, 19 Dec 2018 10:25:18 +0000
Cc: Mihir Bellare <>,
Content-Transfer-Encoding: quoted-printable
Message-Id: <>
References: <> <> <> <>
To: Tony Arcieri <>
X-Mailer: Apple Mail (2.3445.102.3)
Archived-At: <>
Subject: Re: [Cfrg] Building a vector-input MAC by chained construction
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Wed, 19 Dec 2018 10:25:26 -0000

|On 18 Dec 2018, at 20:34, Tony Arcieri <> wrote:
> On Tue, Dec 18, 2018 at 10:52 AM Neil Madden <> 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,