[Cfrg] Critique of AES-GCM-SIV
Marko Kreen <markokr@gmail.com> Fri, 17 February 2017 00:02 UTC
Return-Path: <markokr@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 308AD1294E9 for <cfrg@ietfa.amsl.com>; Thu, 16 Feb 2017 16:02:54 -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, FREEMAIL_FROM=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=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 vJy-Q2JEl69Y for <cfrg@ietfa.amsl.com>; Thu, 16 Feb 2017 16:02:52 -0800 (PST)
Received: from mail-lf0-x232.google.com (mail-lf0-x232.google.com [IPv6:2a00:1450:4010:c07::232]) (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 615EE1293EE for <cfrg@irtf.org>; Thu, 16 Feb 2017 16:02:52 -0800 (PST)
Received: by mail-lf0-x232.google.com with SMTP id o140so1577925lff.1 for <cfrg@irtf.org>; Thu, 16 Feb 2017 16:02:52 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=date:from:to:subject:message-id:mime-version:content-disposition; bh=Js/75KJWrIg8ps1K9cUklKR0ayF5VmSYDtIdkYkMGZk=; b=CxlvNs1wcm9bVPAB1JDmbOXNZn37V/9oLibCr0rlQUa9fqsjpA4AakfJnHfl9gKOWe +Jo4ygsbonRIXuMWUJ90jjJIn1srAKyLxl1292kn7J8q3afppaQBrrerg22KTFWAH4Li 9OzvqS2s1Gf2N7HaT5GdkA3C2AEiDNvEH2e0A130qELci0LPSG7KssgAXEfRh+PMmOXT Gcc4HIdIfocQY6BAF1K4H63g/3XS3Fi7DER9bDDl5Ot+6Q2gSeDMcatkqCkXnXgDD+wb qpB9sKwCFNFVm+6v0WjC5L52zubh4SZSNcO2BTG9xnFZ5qViTyj3JmVr5096ZqMnZyVs MAhg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:subject:message-id:mime-version :content-disposition; bh=Js/75KJWrIg8ps1K9cUklKR0ayF5VmSYDtIdkYkMGZk=; b=bjeEZgDng9J/eCWM5kqoNZ+sCRUgc/uh8DAFQQBV0zKqEDXgsq5DsmoS2UI3z0ENvp ag8CT9+vARe5AMxqDkpvqhtZP0BKn5UvbNz9R+AnEu4Duga1fkxI9swZTjipPv3WOOfK RsSQn0OnDGeEi4EpXFBcQM3eZiqsxMIKn5gXi5G/kawoIrzASNNvSVDM5fB1RfHjBY4m /jQiSKRA6IyJ6+T61NX8fDaml3W0kZAIIDJKf1xosA1KBHbtI2aNeQW5sSQzML4h0l21 Hp7HhdKGbFgpjZaaELd6vMdHDCJ8ZFbNUUX+TbdvnOY6YiUeHcUCqb6eD2gFsyXfMhc/ eHwQ==
X-Gm-Message-State: AMke39lL+ee5P17JCdezjF+NkCGXpa7QDisbyRQnhQgT6gs+7wnUoD+Nf1bn+3oHxioE8Q==
X-Received: by 10.46.0.68 with SMTP id 65mr1152793lja.64.1487289770074; Thu, 16 Feb 2017 16:02:50 -0800 (PST)
Received: from gmail.com (103-169-191-90.dyn.estpak.ee. [90.191.169.103]) by smtp.gmail.com with ESMTPSA id s7sm2087368lja.27.2017.02.16.16.02.48 for <cfrg@irtf.org> (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 16 Feb 2017 16:02:49 -0800 (PST)
Date: Fri, 17 Feb 2017 02:02:47 +0200
From: Marko Kreen <markokr@gmail.com>
To: CFRG <cfrg@irtf.org>
Message-ID: <20170217000247.GB23785@gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Content-Disposition: inline
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/E5UacJcZTSbgSQqUbqasnHbNMks>
Subject: [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 00:02:54 -0000
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] Critique of AES-GCM-SIV Marko Kreen
- Re: [Cfrg] Critique of AES-GCM-SIV Daniel Bleichenbacher
- Re: [Cfrg] Critique of AES-GCM-SIV Marko Kreen
- Re: [Cfrg] Critique of AES-GCM-SIV Aaron Zauner
- Re: [Cfrg] Critique of AES-GCM-SIV Marko Kreen