Re: [Cfrg] Adopting "AES-GCM-SIV: Nonce Misuse-Resistant Authenticated Encryption" as a CFRG document

Andy Lutomirski <luto@amacapital.net> Sun, 03 April 2016 00:49 UTC

Return-Path: <luto@amacapital.net>
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 0DC9912D0DB for <cfrg@ietfa.amsl.com>; Sat, 2 Apr 2016 17:49:19 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.6
X-Spam-Level:
X-Spam-Status: No, score=-2.6 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=amacapital-net.20150623.gappssmtp.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 mEZFGT39lfdS for <cfrg@ietfa.amsl.com>; Sat, 2 Apr 2016 17:49:17 -0700 (PDT)
Received: from mail-oi0-x22e.google.com (mail-oi0-x22e.google.com [IPv6:2607:f8b0:4003:c06::22e]) (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 3AD3B12D0A7 for <cfrg@irtf.org>; Sat, 2 Apr 2016 17:49:17 -0700 (PDT)
Received: by mail-oi0-x22e.google.com with SMTP id y204so6503725oie.3 for <cfrg@irtf.org>; Sat, 02 Apr 2016 17:49:17 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=amacapital-net.20150623.gappssmtp.com; s=20150623; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc; bh=BbAbcmq7vRUpotUb7xixfLKSPmIoeR/4sHpcy0KIjyY=; b=aRfvy1WizC16iwyrl4ArDbcnkQ8WT3GMJweL1KcBJadbH7AbUzpdObrHKModW9zAsD cW70O6cB2U080HKRNd4Tl2dFyeq+Ygx1dU1LQ9sovyBqB/iLG3Yv0EZObcK7RhuwaWHD SEXahplkLSRT5LZmX7G8aK8psrkqpMs2m0/KzPue3F7lojDHdVdSsz7N/KLIAXKKkSuT CGOeIN6CpQoQA85LCKB9mCRDFa5z7M5y9iKqYqd/RH5GbFDaRB+jlfmUYc+zL1HxDAC7 5B/ATtPbFqOeBjsHuGJFFejDlvaCCMePpMJk9W28mxylCgr5DZ36/YkPjRmm7eiQUssG /i+Q==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:date :message-id:subject:from:to:cc; bh=BbAbcmq7vRUpotUb7xixfLKSPmIoeR/4sHpcy0KIjyY=; b=lE6ohdQVaPAC3Iu7ISqt9O/kQjsoOji0oZ9SFG5tG7dd8aMS8xIKhTqjCDWqxyBh+x yz+rvWw47nz+A8I1EdbfXuJbwJatCKWsBXQ7njfI1GoiRNtx41Jtk/TSagasjlvaZeP4 Rdp7XBF/RMUnNv8WHM6q3KAd6GigFjf8zZv1K26NmA4gUwkurbtSHjdCndtF/P1z1fmL L7lzLNg/gaDiAlGZaRzcgVhEEv5S8wvijdc625Vp2EcVxldBMXziccmrfy7FoufD8+lq 7FOxIzNkvUixnIL4QW1pxz1FyKUlfvMvGpz0iPMw9HyiKIqqlPHt3olF3do6ciEw0cR6 2uBw==
X-Gm-Message-State: AD7BkJI5uIn4hgBNsYZUz6R2MgOY3xVnEh+Qx4UyK99C2xQxcdEWJtCySLxo+EWsSqjBgaeBH7dvWB0lixJctP6M
MIME-Version: 1.0
X-Received: by 10.202.60.5 with SMTP id j5mr1056231oia.43.1459644556517; Sat, 02 Apr 2016 17:49:16 -0700 (PDT)
Received: by 10.202.202.209 with HTTP; Sat, 2 Apr 2016 17:49:15 -0700 (PDT)
Received: by 10.202.202.209 with HTTP; Sat, 2 Apr 2016 17:49:15 -0700 (PDT)
In-Reply-To: <CAMfhd9V9s=mwz4nDGWWAx4Li_aXykfuXhNsHb5s1g_HEpBu_xA@mail.gmail.com>
References: <1893951588-3704@skroderider.denisbider.com> <CALCETrW7ew_inZdFDxSgcDER-4wcgAoN_8Tr9-ZgBy+cwLb8HA@mail.gmail.com> <CALCETrXV2E8rUDwWNqc+t1kJM4mdXpDhUN8fqqpW5uCf05g-pw@mail.gmail.com> <CAMfhd9V9s=mwz4nDGWWAx4Li_aXykfuXhNsHb5s1g_HEpBu_xA@mail.gmail.com>
Date: Sat, 02 Apr 2016 17:49:15 -0700
Message-ID: <CALCETrVP_Op+-jpoP0JBFWZZQkvo0JYuLNtAS=itSPTb4Ptkuw@mail.gmail.com>
From: Andy Lutomirski <luto@amacapital.net>
To: Adam Langley <agl@imperialviolet.org>
Content-Type: multipart/alternative; boundary="001a113cc26c4a4387052f89fbb8"
Archived-At: <http://mailarchive.ietf.org/arch/msg/cfrg/9ftfiHs80CxzcuhLpwVAPrkeJGo>
Cc: Yehuda Lindell <yehuda.lindell@biu.ac.il>, cfrg@irtf.org, Adam Langley <agl@google.com>
Subject: Re: [Cfrg] Adopting "AES-GCM-SIV: Nonce Misuse-Resistant Authenticated Encryption" as a CFRG document
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: Sun, 03 Apr 2016 00:49:19 -0000

On Apr 2, 2016 7:57 PM, "Adam Langley" <agl@imperialviolet.org> wrote:
>
> On Thu, Mar 31, 2016 at 3:22 PM, Andy Lutomirski <luto@amacapital.net>
wrote:
> > 4. Since this claims nonce-MR, setting nonce=0 is valid.  If someone
does
> > this, then I think they are vulnerable to the extra-easy parallel
attack.
>
> Ah, do you mean when the AES-GCM-SIV is used with a fixed nonce?
>
> In that case, it breaks down in the same way as AES-GCM with random
> nonces. We note that in the Security Considerations
> (https://tools.ietf.org/html/draft-gueron-gcmsiv-02#section-9)

I mean something different, but I read it a bit wrong.  If I understand
correctly, if AES256-GCM-SIV is used 128-bit keys, then you can only
encrypt with ~2^64 (key, nonce) pairs, even with different keys, before a
work factor ~2^64 attacker can decrypt one of them (which one is not under
their control).  This may not work if something prevents DJB's efficient
parallel attack from working.

With fixed nonce, the key derivation has no practical effect (as I said, I
read it wrong at first).  With *variable* nonce, the protocol no longer
works like the paper, so I don't believe the security proof works as is.