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

Neil Madden <neil.e.madden@gmail.com> Wed, 19 December 2018 10:25 UTC

Return-Path: <neil.e.madden@gmail.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id D612D1277D2 for <cfrg@ietfa.amsl.com>; Wed, 19 Dec 2018 02:25:25 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2
X-Spam-Level:
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: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id jpN5HsSwSPTB for <cfrg@ietfa.amsl.com>; Wed, 19 Dec 2018 02:25:23 -0800 (PST)
Received: from mail-wm1-x335.google.com (mail-wm1-x335.google.com [IPv6:2a00:1450:4864:20::335]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 5DF8F127598 for <cfrg@ietf.org>; Wed, 19 Dec 2018 02:25:23 -0800 (PST)
Received: by mail-wm1-x335.google.com with SMTP id g67so5791008wmd.2 for <cfrg@ietf.org>; Wed, 19 Dec 2018 02:25:23 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; 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; d=1e100.net; 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 (92.150.32.217.dyn.plus.net. [217.32.150.92]) by smtp.gmail.com with ESMTPSA id y185sm3217963wmg.34.2018.12.19.02.25.20 (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 <neil.e.madden@gmail.com>
In-Reply-To: <CAHOTMVK76Acag9orV1O47y9C+UQmbXmEFyt3qpGwHPixUTNgHQ@mail.gmail.com>
Date: Wed, 19 Dec 2018 10:25:18 +0000
Cc: Mihir Bellare <mihir@eng.ucsd.edu>, cfrg@ietf.org
Content-Transfer-Encoding: quoted-printable
Message-Id: <2831A1F7-C620-40E4-83BE-B5047BBE5864@gmail.com>
References: <A44A80BE-030B-4D1E-9889-F727EB0BF142@gmail.com> <CACEhwkQKHkHEyLbmZ6oeDtvuvmwgifyuTUsb6Xy1CDR+4RE9PA@mail.gmail.com> <F9E1D18B-2C9E-4ED1-8F23-C25A0A8AF2C6@gmail.com> <CAHOTMVK76Acag9orV1O47y9C+UQmbXmEFyt3qpGwHPixUTNgHQ@mail.gmail.com>
To: Tony Arcieri <bascule@gmail.com>
X-Mailer: Apple Mail (2.3445.102.3)
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/hGRLYDoDBxg7wVDgWtFy_wUmShg>
Subject: Re: [Cfrg] Building a vector-input MAC by chained construction
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Wed, 19 Dec 2018 10:25:26 -0000

|On 18 Dec 2018, at 20:34, Tony Arcieri <bascule@gmail.com> wrote:
> 
> On Tue, Dec 18, 2018 at 10:52 AM 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.
> 
> 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