Re: [Cfrg] Critique of AES-GCM-SIV

Daniel Bleichenbacher <bleichen@google.com> Fri, 17 February 2017 10:01 UTC

Return-Path: <bleichen@google.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 09AC5129480 for <cfrg@ietfa.amsl.com>; Fri, 17 Feb 2017 02:01:00 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.7
X-Spam-Level:
X-Spam-Status: No, score=-2.7 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_LOW=-0.7, RP_MATCHES_RCVD=-0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=google.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 JSqcw_0dGA42 for <cfrg@ietfa.amsl.com>; Fri, 17 Feb 2017 02:00:58 -0800 (PST)
Received: from mail-yw0-x233.google.com (mail-yw0-x233.google.com [IPv6:2607:f8b0:4002:c05::233]) (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 C44181294E2 for <cfrg@irtf.org>; Fri, 17 Feb 2017 02:00:57 -0800 (PST)
Received: by mail-yw0-x233.google.com with SMTP id l19so20880991ywc.2 for <cfrg@irtf.org>; Fri, 17 Feb 2017 02:00:57 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=okqRaRwBwVNX5SAIcpeULV4CquW5m/XtV0qY0tI1RzE=; b=WV9xvBbJiw7WorVBx17tVGmggDbIpHw4hiqd/9sRtteBP1Q4rzRojh1fsB3KIkx1Wo 48NfjGd86cfqiLYiTWw1QE1KWJQERpraQB1zZX1DNKa2ySSai86vdptnMnMSVzck7SeZ J+Hgos56llCv6wIBDyEGREMrrv3fBDUco5LlGh1HwUqMhvjl61m+6LG3nLDxfFWwI83u 6kKyBYgP9UId30A7k3TIaXfMYq8ybuAyX68kSmKuW3iq5rWQ3I4rmQUU9YAwNU7mTxQ+ 32r7BbpRyiWx3A7E87eGba54lm25tuFpuplgtLxuFerLlQBkSUD4BEoj9Jla15VjYJY0 jHUg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=okqRaRwBwVNX5SAIcpeULV4CquW5m/XtV0qY0tI1RzE=; b=HWXKJdYuWQ6r7KRW3kGqsp/VXuIF4AP2WSdAKM18SBPMNWGR90ApmS6GWidol5KTtf v9ae3aCxpVBkCcD1nfIaAeKvVYJC53sN5XwbBblVtOtKPXZsNmNQxp9TzbDYBW8Oepc0 2xrljtANcICppNXAvRSVTZwFKohJi+sFxSKY80x7qfnDoU74dP7ZO4PNfzp01B+BO4Kd S/0PBSQBhcTvsKCVbbtTlGN1KqAIfTos1WRxWvBaaJ3HeLyNurPOjtjYyE9PwmlrWLHA 4zJNHkyVSM2BUittoJpOCQU1DdAD35qT7HHXitPeRdmCMHj9Ic0s+2KedRUQqKfyy/5C 0JXQ==
X-Gm-Message-State: AMke39l7WnRPmpg4CoTV27kDXWCH0zgYljXmqkeIPZ+DML2PFVJ1IEzrVLu4SdcFiUiVViuwFxci8Rs8CVzCmRt0
X-Received: by 10.129.129.3 with SMTP id r3mr5056463ywf.0.1487325656770; Fri, 17 Feb 2017 02:00:56 -0800 (PST)
MIME-Version: 1.0
Received: by 10.37.207.149 with HTTP; Fri, 17 Feb 2017 02:00:56 -0800 (PST)
In-Reply-To: <20170217000247.GB23785@gmail.com>
References: <20170217000247.GB23785@gmail.com>
From: Daniel Bleichenbacher <bleichen@google.com>
Date: Fri, 17 Feb 2017 11:00:56 +0100
Message-ID: <CAPqF7e2xFVqbw0cCi4468_Ag+Lp4QuXPMaR2cNsU4m_F7hFppQ@mail.gmail.com>
To: Marko Kreen <markokr@gmail.com>
Content-Type: multipart/alternative; boundary="94eb2c07dd3e701d9f0548b6fd04"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/SZQHDxJp8jeBTowIhqPdlz81UDQ>
Cc: CFRG <cfrg@irtf.org>
Subject: Re: [Cfrg] Critique of AES-GCM-SIV
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.17
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: Fri, 17 Feb 2017 10:01:00 -0000

On Fri, Feb 17, 2017 at 1:02 AM, Marko Kreen <markokr@gmail.com> wrote:

>
> Hello CFRG!
>
> I have reviewed the AES-GCM-SIV proposal (draft 3).  And while there
> are parts I like - overall direction to higher security and
> getting rid of GCM bitflipping - current design feels "ugly".
> (That's a cryptographic term.)
>
> Specifically, it is supposed to be Nonce-Misuse-Resistant mode.
> That means even if nonce+key repeat, you get enough unpredictability
> from message hash, so security does not fundamentally change.
> Except it is now possible to detect if same message repeats.
>
> But this does not apply to draft-03 version - if key+nonce repeat,
> mode fundamentally changes - it uses fresh key and counter in one
> case and only fresh counter other case.  That is ugly.
>
> Instead it would be clearer (less ugly) if MAC(message) is always
> used as extension of nonce.  They both affect counter.  Similarly,
> either both affect encryption key or neither affects encryption key:
>
> 1) No rekey, only counter is synthesized - that would be basically AES-SIV
>    with modern hash.  This would be strict improvement over AES-GCM,
>    better security (but not too good), but same performance.
>
> 2) MAC(Plaintext) always affects encryption key.  This would give
>    significantly better boundaries than just synthesized counter.
>    But at the cost of extra keygen per message, which is slow for AES,
>    so the mode will seem more costly than current AES-GCM.
>
> While I like the current direction of AES-GCM-SIV of trying to achieve
> higher security level by using rekey, I wonder if it would be
> good to standardise a simple AES-POLYVAL mode like 1) that is also
> clearly securitywise better than AES-GCM.  For use in new designs
> that do care about maximum performance.  Just a thought.
>
>
> To throw out some ideas on 2), here is my proposal how to synthesize
> both key and counter based on MAC.
>
>
> AES-GCM-SAFE
> ============
>
> Cipher mode that uses key, nonce and MAC(message)
> to synthesize both counter and encryption key.
>
> Input:
>   K = 128/256-bit key
>   N = 128-bit Nonce
>   P = plaintext
>   A = additional data
>
> Process:
>   AuthKey = AES(K, N)
>   SubKey1 = AES(K, N xor 1)
>   RawTag = POLYVAL(AuthKey, PAD(A) || PAD(P) || LEN(A) || LEN(P))
>   Tag = AES(K, N xor RawTag)
>   Counter = AES(K, Tag)
>   SubKey2 = AES(K, Tag xor 1)
>   EncKey/128 = SubKey1 xor SubKey2
>   EncKey/256 = SubKey1 || SubKey2
>   CipherText = AES-CTR(EncKey, Counter, P) || Tag
>
> Where:
>   || - concat
>   xor 1 - flip lowest bit of first byte
>   LEN(V) - number of bits in V in 64-bit little-endian format
>   PAD(V) - zero-pad to full block
>   AES(K, V) - Encrypt V with key K
>   AES-CTR(K, C, V) - Encrypt V with key K and counter C
>
> Improvements
>
> + When key and nonce repeat, then same AuthKey is used.  But both
>   counter and encryption key will be synthesized based on MAC.
>
> + EncKey is used only for encrypting plaintext, so no need to waste
>   bits on domain-separation.  Thus full 128-bit counter can be used.
>
> * There are no steps that need dropping bits so 128-bit nonce can
>   be used.  As this is supposed to be high-security mode.
>
> + More natural 128/256-bit keygen for EncKey.  It's faster too
>   due to less blocks encrypted.
>
> + Counter is not sent in clear.  While sending counter in clear does
>   not change probability of catastrophic failure, it does make
>   exploiting it less expensive.
>
> Notes
>
> * If AES256 has related-key problems when only half of the key changes,
>
>     EncKey/256 = (SubKey1 xor Counter) || SubKey2
>
>   should fix it.  This may be also useful if shorter nonce is used.
>
> * Its possible to use domain-separation for AES(K,N) vs. AES(K,Tag)
>   but it does not seem necessary.
>
> Comments?
>
> --
> marko
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg
>

I have problems to see how this proposal is safe.
I.e. Cooley used that POLYVAL returns 0 if A and P are empty in the
AES-GCM-SIV cryptanalysis.
In the proposal above using A="" and P = "" results in
Tag = AES(K,N)
Therefore an attacker can use the proposal above as an oracle to for
encrypting single blocks with K.
This is all that is needed to break the proposal.
Hence it seems to me that even a nonce respecting adversary can break this
proposal.

I actually don't know what "ugly" means as a cryptographic term.
My guess would something like difficult to formally analyze.
E.g. in the proposal above if N and N xor 1 are both used as nonces then
AuthKey and SubKey1 change their role and that seems to add a lot of
complexity
to a potential analysis.