Re: [CFRG] Review of draft-irtf-cfrg-aead-limits-01

John Mattsson <john.mattsson@ericsson.com> Mon, 23 November 2020 14:00 UTC

Return-Path: <john.mattsson@ericsson.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 B28953A0B80 for <cfrg@ietfa.amsl.com>; Mon, 23 Nov 2020 06:00:59 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.202
X-Spam-Level:
X-Spam-Status: No, score=-0.202 tagged_above=-999 required=5 tests=[DKIMWL_WL_HIGH=-0.001, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, RCVD_IN_MSPIKE_H2=-0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=ericsson.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 T3KDq7inKc7B for <cfrg@ietfa.amsl.com>; Mon, 23 Nov 2020 06:00:57 -0800 (PST)
Received: from EUR05-DB8-obe.outbound.protection.outlook.com (mail-db8eur05on2067.outbound.protection.outlook.com [40.107.20.67]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 71B983A0B6B for <cfrg@irtf.org>; Mon, 23 Nov 2020 06:00:57 -0800 (PST)
ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=g4gSbmPsTYzsno0jf5ZMfDACepG5TakmOEJUB3MJ2n4rMeD9xCLUlKAXUiTLqw9tOj+l80OWLbW1l9lGBIPI0bwXekn2HOMcmWyAsxiOgk7k2Nu2le+JRao0JwXAlsALJWQq3ZMHhTo8yjI5YMxzXS9YYleXFYOOpRrsd5m9lnB/r5fvNBckDFSSXvc/FQpP6kdjeC39+Oeh342kL4vnwyyK8imw/bAyqA9v07GDBk2n0Y10MPle/RVJufhc7LxDvrvIhPJtu+MDFl+rApg3F+wfv2RrUOoWE3FkhrGffPwSvZ/oBPqcV0h527no7xKkI0QDLfZNyfO7uZNFuUvmZw==
ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=Y9RHewibAqH8mK37W8ARqgY+2X0LpJBD6PHdrAJbM/E=; b=hvmBEG9l1sAQTs+eJZ6GxMGCsBE2sgHZMueTVCGDH+gx/7t2E7hvslJoppr0gJsfKwaGMO4/jF6IhRNeSOMV84nK571WT7P7XZ4CuS3kZLHOKq6KCxelxFRUFofG8C+YeirGZQdXQEFzweAFiZxCx3xgAqWG7/G8RWUi/m0wjr0WlXi1dP4YCqlu3xKrJjsE2ZVmugOzS1ohDdr+n6bAKuQ095IfJZgrbnhJJcvElfhks/dNRBLllpkKYKqU6aS2S0bpUKKh6xsWh6gJElj42hd2TcaQV5+FsMffBSfAY0aNdRr1oMhhnjc0KwHdMDjfOmu8mUJdyWmsFYgfmLltEA==
ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=ericsson.com; dmarc=pass action=none header.from=ericsson.com; dkim=pass header.d=ericsson.com; arc=none
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ericsson.com; s=selector1; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=Y9RHewibAqH8mK37W8ARqgY+2X0LpJBD6PHdrAJbM/E=; b=XYMZjQZfmEkTqYfTq+jJX9sF9s8DGaFZgMBO2EAeh++NLS8pMvlWOnrqBWkc6tVXkBg61XWQm4GfcQ5FZf3MZDd/uDbgSHXy1KPCMfLjWZvz05NKRAM+sk40VFgk4yg0y9o+T4x09k+Kt4ZvKdkJUu4xlShcxck6ZPqXvwWdBzg=
Received: from AM6PR07MB4584.eurprd07.prod.outlook.com (2603:10a6:20b:17::24) by AS8PR07MB7079.eurprd07.prod.outlook.com (2603:10a6:20b:25c::14) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.3611.9; Mon, 23 Nov 2020 14:00:53 +0000
Received: from AM6PR07MB4584.eurprd07.prod.outlook.com ([fe80::6cb1:adbe:25f:1b4e]) by AM6PR07MB4584.eurprd07.prod.outlook.com ([fe80::6cb1:adbe:25f:1b4e%4]) with mapi id 15.20.3611.020; Mon, 23 Nov 2020 14:00:53 +0000
From: John Mattsson <john.mattsson@ericsson.com>
To: CFRG <cfrg@irtf.org>
Thread-Topic: Review of draft-irtf-cfrg-aead-limits-01
Thread-Index: AQHWvTnzG5eDcgGL2kuaVeRiz5GG26nV2GsA
Date: Mon, 23 Nov 2020 14:00:52 +0000
Message-ID: <6319FA87-87AA-46AA-86DF-DD2140478214@ericsson.com>
References: <24F660E5-C158-4FE6-A151-74BF78BE8CD9@ericsson.com>
In-Reply-To: <24F660E5-C158-4FE6-A151-74BF78BE8CD9@ericsson.com>
Accept-Language: en-US
Content-Language: en-GB
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
user-agent: Microsoft-MacOutlook/16.42.20101102
authentication-results: irtf.org; dkim=none (message not signed) header.d=none;irtf.org; dmarc=none action=none header.from=ericsson.com;
x-originating-ip: [81.225.97.222]
x-ms-publictraffictype: Email
x-ms-office365-filtering-correlation-id: f86081cd-a2d0-4614-6a05-08d88fb83126
x-ms-traffictypediagnostic: AS8PR07MB7079:
x-microsoft-antispam-prvs: <AS8PR07MB7079E951A9D4C226218D188D89FC0@AS8PR07MB7079.eurprd07.prod.outlook.com>
x-ms-oob-tlc-oobclassifiers: OLM:10000;
x-ms-exchange-senderadcheck: 1
x-microsoft-antispam: BCL:0;
x-microsoft-antispam-message-info: xIXTrYCK012tLnOlDvdBcq5UuJjzQYy3siKbgLj1k/ukdLbgtl+VZdMbOLZdV1IDNcLxeu1QF11x4s/g7MmKrrbAZG/pk6vNCi1CBZkO3TREWcmjGwdtzHB3EH4bJJCvPYx3D1rlIWfaVYXepoqufLW2Gn97dNsgA3vuvuA30KtA7f/FDzsJmDKFiv29e1z4eDY0+AXf0DXuGk0ogdIfO0fLER4727VuSni8YoOg078+EBQWd0QJJGtaas8LZG0Ez7HZh7sJI2vKPcCYZSXp1rHM6wBIHDomHSYVRlSdJfAQkegnvh2SfI1YJSHuqG2eVzpMKUDgEc9E7KW6jCBjooN6rA8mMs1TZPY6J+GtniHB4xCjvYaZllnuvOBfRP2/7z7GfXbaOHtmbqH+b6FmCz30Pz7XXQbTXNKPEA3dJ7zoz4xaxZuLzn4Y352DwWT/35ufbPnN+tKNXsSmzO+RWw==
x-forefront-antispam-report: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:AM6PR07MB4584.eurprd07.prod.outlook.com; PTR:; CAT:NONE; SFS:(4636009)(136003)(346002)(376002)(366004)(39860400002)(396003)(478600001)(8676002)(26005)(186003)(6916009)(53546011)(966005)(6506007)(83080400002)(2906002)(33656002)(8936002)(6512007)(76116006)(66946007)(36756003)(91956017)(66574015)(83380400001)(71200400001)(5660300002)(316002)(6486002)(86362001)(44832011)(66476007)(66556008)(64756008)(66446008)(2616005); DIR:OUT; SFP:1101;
x-ms-exchange-antispam-messagedata: aEFTmNIr1Of1LkqAxZDRswcHIqqjaJR2pJ7jqRNy5gTtVe3bnq+pLcnRwxEml2PuFIS429LHS0MBb0ER9oHYs+FNl90fN2hA1Sk/iO4Xf9mRgiCB15TE/vWatV2OZJQtKsfO8OTe1LmUSc0BEREwrdtKvPop3EB0SZ0C6rXI4Vw304rIMoLwrJlpc5zehuqp8f5c99WVjn9hyDk+9OSiCHsCjvygSnXRdPzeJ6csyw5JyK+6iXtPxQzFHYiRLLzyMgOg5XwKIsuSgXOg7lPO8d+tVF5WS5VM5zSZsOdCUw0qwQXyzDCy33yfqolbm7aNSJ9SuQ5eVV8hnRIYEUy4pmQ6AAjTld3e3VmFITvrqDqP8lvkPedMlNqm+80jXysZy/C/nvdle4cmoadE8zkV0jnnhfIjKuSeLeJENs85H8V71EuTm1iiAGUoz7Tq1WD9mkABhuWHBNDZQX/ql1FGYS1IcxCwYGG5WNDObRl1AZLt7dLUb02HuPsnI6RD0EoOmDKM0JVHW1R5FSVrbZN6XnDs/hA+4rzfVYdB1LUHi+lkMewGF+sgDVkl4hKG5TAZZCLrlrFy5QxD16f3eKllua9At75g2X4yzmlz/6gbciUNqfxJS9Vdn1drtldoD/uVhmWgl0yRLkmg+Z0Cb76zGA==
x-ms-exchange-transport-forked: True
Content-Type: text/plain; charset="utf-8"
Content-ID: <2E068C6D313ED744B7C0DBC68A09A7C8@eurprd07.prod.outlook.com>
Content-Transfer-Encoding: base64
MIME-Version: 1.0
X-OriginatorOrg: ericsson.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-AuthSource: AM6PR07MB4584.eurprd07.prod.outlook.com
X-MS-Exchange-CrossTenant-Network-Message-Id: f86081cd-a2d0-4614-6a05-08d88fb83126
X-MS-Exchange-CrossTenant-originalarrivaltime: 23 Nov 2020 14:00:53.3491 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 92e84ceb-fbfd-47ab-be52-080c6b87953f
X-MS-Exchange-CrossTenant-mailboxtype: HOSTED
X-MS-Exchange-CrossTenant-userprincipalname: YO07yW5ntUHFJFxwr2zYmKGJgtCSsP8lSwsfSP/PZ2O9Vsp1DFhQF/sgCRCQhaFhb+W0tMIolu9IfbVzWvD5k1pSPiWqZ1xVPM3G6o5jLJs=
X-MS-Exchange-Transport-CrossTenantHeadersStamped: AS8PR07MB7079
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/Mf1MeM_NyRZVNlrRS9SvA8aioS0>
Subject: Re: [CFRG] Review of draft-irtf-cfrg-aead-limits-01
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: Mon, 23 Nov 2020 14:01:00 -0000

Hi,

Some more comments on the document:


- "However, in practice, there are often many users with
independent keys.  The "multi-user" security setting hence considers
an attacker's advantage in breaking security of any of these many
keys, further assuming the attacker may have done some offline work
to help break security."

I think the term "multi-user" is a quite misleading term. It was coined by Belallare, Boldyreva, Micali trying to provide a theoretical framework against Håstad's attack on public key RSA and even then they used quotes ("") as a user might have several public keys. When applied to symmetric keys in security protocols with frequent rekeying it becomes a bit misleading as the attack scenario is really for multi-key and each user definitly has several keys. In strongly think the term "multi-user" should be replaced with "multi-key", but I know that "multi-user" is what is used i several academic papers... At a minimum I think you should define "multi-user" in terms of multiple keys and write that the keys can belong to one, two, or many users.


- "single-user". I think this terminology should definitly go away. Luykx et al. use "single-key". When applied to e.g. TLS there is already 2 users.


- "Number of attacker forgery attempts (failed AEAD decryption invocations)"

Note that Iwata et al. defines q' as the number of decryption queries, while your document defines it as number of failed decryption queries. In theory that could mean that the inequality 

IA <= 2 * (v * (l + 1)) / 2^128

does not hold anymore. In practice it holds anyway. I think you should keep the definition of v, but you should alert the reader that you have modified this, and maybe give some justification.


- "LS aims to keep CA below 2^-60 and IA below 2^-57"

This indicates that you might want two different variables p_ca a p_ia for the two different bounds.


- "AES-GCM without nonce randomization is also discussed in [GCM-MU2], though this section does not include those results as they do not apply to protocols such as TLS 1.3 [RFC8446]." 

The negation of "AES-GCM without nonce randomization" is not well defined. It would be good to now if the results apply only for the constructions where the salt is secret (TLS 1.3, DTLS 1.3, QUIC, OSCORE), or only to constructions where the salt has the same length as the nonce, or if it apply to all constructions with a random component. It would be good if the document is also useful for protocols like ESP, SRTP, CMS, JOSE, COSE, etc...

Cheers,
John

-----Original Message-----
From: John Mattsson <john.mattsson@ericsson.com>
Date: Wednesday, 18 November 2020 at 00:32
To: CFRG <cfrg@irtf.org>
Subject: Review of draft-irtf-cfrg-aead-limits-01

Hi,

Great that you are taking the time to summarize all this information. Very useful.


Comments:

-- "plaintext, and optional associated data"

P and A are both optional in RFC 5116.


-- It would be good if the document states that it only focuses on "single forgery attacks"

I think some readers might believe that a second forgery is as hard as the first, which it is not. It it typically much easier. It might also vary drastically between algorithms as calculated in [1].


-- I think the document should briefly explain the assumptions about the adversary. For both CA and IA, one assumption worth explaining is that the adversary has access to an encryption oracle and can freely encrypt chosen-plaintexts.


-- The table defines l as "length of each message" while a paragraph further down writes "maximum message size (l)".


-- ”passive attacker”

For a reader that does now the IND-CPA game by heart it might be good to point out that the “passive” attacker does not just eavesdrop but also choses all the encrypted plaintexts.


-- “Integrity limit (IL): The number ciphertexts an application can decrypt, either successfully or not”

That IL also count successful decryptions seems to contradict other parts of the document that links IL to v which by definition only counts failed attempts.


-- “This implies the following usage limit: q + s <= p^(1/2) * 2^(129/2) – 1”
   “This implies the following limit: v <= (p * 2^127) / (l + 1)”

This does not follow with the current definition of p (p = CA or p = IA). To make the inequalities hold I think you need to define p as:

"Upper bound on adversary attack success probability"

just like the parameter epsilon in [AEBounds].


-- I think the document should briefly explain the assumptions about the algorithms. In [GCMProofs] it is e.g. assumed that AES is a PRP. Future cryptanalysis that does not make these ideal assumptions could make the limits worse.


-- The document should make it clear that formulas for CA and IA (at least for GCM) are upper bounds. Future analysis could make the limits better. That they are just bounds also make any direct comparision between algorithms tricky as some bounds might be tigher than others.


- The draft briefly mention that small limits lead to denial-of-service attacks. The DTLS 1.3 draft does that.


-- The draft seems to make the assumption that l is fixed like n, k, r. I don't think this needs to be the case. My understanding is that for the GCM limits, l_max_allowed can be replaced by l_max_seen being the largest length processed. The encryption or decryption function would then terminate when CA or IA can not be verified to be under the chosen bound. This would make a big difference for applications typically processing much smaller messages than for example 2^14. For the CCM integrity bounds, the formula would probably have to involve (2 * l_max_allowed * q + 2 * l_max_seen_* v). The DoS problem would still be tied to l_max_allowed.


Cheers,
John

[1]  https://csrc.nist.gov/CSRC/media/Projects/Block-Cipher-Techniques/documents/BCM/Comments/CWC-GCM/multi-forge-01.pdf