Re: [Cfrg] Do we need a selection contest for AEAD?

"David McGrew (mcgrew)" <mcgrew@cisco.com> Tue, 30 June 2020 23:41 UTC

Return-Path: <mcgrew@cisco.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 410843A0769 for <cfrg@ietfa.amsl.com>; Tue, 30 Jun 2020 16:41:10 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -9.597
X-Spam-Level:
X-Spam-Status: No, score=-9.597 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, HTML_MESSAGE=0.001, RCVD_IN_MSPIKE_H3=0.001, RCVD_IN_MSPIKE_WL=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001, USER_IN_DEF_DKIM_WL=-7.5] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=cisco.com header.b=dTA8t98v; dkim=pass (1024-bit key) header.d=cisco.onmicrosoft.com header.b=f1HmRu9s
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 PdAn1fc7Qmb5 for <cfrg@ietfa.amsl.com>; Tue, 30 Jun 2020 16:41:07 -0700 (PDT)
Received: from alln-iport-7.cisco.com (alln-iport-7.cisco.com [173.37.142.94]) (using TLSv1.2 with cipher DHE-RSA-SEED-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 06A293A0743 for <cfrg@irtf.org>; Tue, 30 Jun 2020 16:41:06 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=cisco.com; i=@cisco.com; l=10502; q=dns/txt; s=iport; t=1593560467; x=1594770067; h=from:to:cc:subject:date:message-id:references: in-reply-to:mime-version; bh=IpIFs2zNah0ajMDm646NeK0Glke2Gh1eetz94ScTqVM=; b=dTA8t98vlM9YMvKnAbvL+bSxn5MRwm498L3ve8rr9UqXLFOVM+yFi5gw 4+cxf2kc0qbUuPoHwIQB3b1SiqdA3S8PxoYUpOvjUhzpcgMNbEY8zsstI dEFcWv+li4EUZTpvdR/4ezUEXAxRH67X2mw5JO8LpbFx3kTSBGjW4m5F+ w=;
IronPort-PHdr: =?us-ascii?q?9a23=3AJVNhTBIQaQNo8n83G9mcpTVXNCE6p7X5OBIU4Z?= =?us-ascii?q?M7irVIN76u5InmIFeGv60/gVnGG5jQ8P4ChubL4OjsWm0FtJCGtn1KMJlBTA?= =?us-ascii?q?QMhshemQs8SNWEBkv2IL+PDWQ6Ec1OWUUj8yS9Nk5YS8v4aBvPqWa+qzMeB0?= =?us-ascii?q?a3OQ98PO+gHInUgoy+3Pyz/JuGZQJOiXK9bLp+IQ/wox/Ws5wdgJBpLeA6zR?= =?us-ascii?q?6arw=3D=3D?=
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: =?us-ascii?q?A0AUBgAozfte/5pdJa1gDg4BAQEBAQE?= =?us-ascii?q?HAQESAQEEBAEBQIFKgVIpKAdvWC8sCodtA40miiaJboRrglIDVQsBAQEMAQE?= =?us-ascii?q?YAQoKAgQBAYRHAoIQAiQ4EwIDAQELAQEFAQEBAgEGBG2FWwyFbwICAgEBEC4?= =?us-ascii?q?BASwLAQ8CAQg/ByEGCxQRAgQOBSKDBAGBfk0DLgEOo3ACgTmIYXSBNIMBAQE?= =?us-ascii?q?FgTIBgRaCdA0Lgg4DBoE4gmmJfxqCAIERJwwQgh8uPoIaQgEBAQKCCYMcgi2?= =?us-ascii?q?PFIlmmz1NCoJciEmMC4RuAx2Cc4ktknabbYJZkWQCBAIEBQIOAQEFgWoigVZ?= =?us-ascii?q?wFTsqAYI+UBcCDY4egSUBBoJFhRSFBD50AjUCBggBAQMJfI4yAYEQAQE?=
X-IronPort-AV: E=Sophos;i="5.75,298,1589241600"; d="scan'208,217";a="505601244"
Received: from rcdn-core-3.cisco.com ([173.37.93.154]) by alln-iport-7.cisco.com with ESMTP/TLS/DHE-RSA-SEED-SHA; 30 Jun 2020 23:41:03 +0000
Received: from XCH-ALN-003.cisco.com (xch-aln-003.cisco.com [173.36.7.13]) by rcdn-core-3.cisco.com (8.15.2/8.15.2) with ESMTPS id 05UNf3FK002135 (version=TLSv1.2 cipher=AES256-SHA bits=256 verify=FAIL); Tue, 30 Jun 2020 23:41:03 GMT
Received: from xhs-rtp-001.cisco.com (64.101.210.228) by XCH-ALN-003.cisco.com (173.36.7.13) with Microsoft SMTP Server (TLS) id 15.0.1497.2; Tue, 30 Jun 2020 18:41:03 -0500
Received: from xhs-aln-001.cisco.com (173.37.135.118) by xhs-rtp-001.cisco.com (64.101.210.228) with Microsoft SMTP Server (TLS) id 15.0.1497.2; Tue, 30 Jun 2020 19:41:02 -0400
Received: from NAM10-BN7-obe.outbound.protection.outlook.com (173.37.151.57) by xhs-aln-001.cisco.com (173.37.135.118) with Microsoft SMTP Server (TLS) id 15.0.1497.2 via Frontend Transport; Tue, 30 Jun 2020 18:41:02 -0500
ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=FHgA9BnNiYxMvwE+zTlgp5xMw09J7h9IbD83p/AlpFuMqjOTqz+/F3GFlgLpBIa9J6Kc026pZ6N7nFbX/CIrRitWPDoZ9TreYZWA5GdhUN5IuDd6MBB5+aIY6WXPkt/gES9LspjdOaiYtpixc87M5EA/SgBpRdml2xQW6rTm2lIu6YWrMjy3OaudquJBtQNWD1die4lqvGk23DvbN03vciVsV93g2sy91OrI3hRm/NoUzpu5/qjSMPBGSR4YL7zmYtliSxy6hiYpVVzPKmrmbRrvLVhcZTmVgHUWMb4qTA6pekR0zosDcFIdSBKZMqPnJBpC2tRXO+ARCkgITh+M+A==
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=IWKQ3+t66sZDowqjap+PfPVS29HfO4S7MYaPn/1EojI=; b=nc5wcdZJfx3Z3efliIzaje+P8F/g51YY+CBzqSMkslImSCfpc8kzV0zSjexoz9orvehYWU+F6dfIH1OAKdzB0v42ae0opfomc5uQamOyJhAREoAghDx/OsjNjFk5+utc/HR7z/ALd0lTGWhyDcNtnXdt+O6DCIt9JqmqA3Uk3F2xmKA01pEkSBmE5nbCd9ZgSQ51tdqcBb/M+o474uv9wCswIvZm2of72Fc2ZXmMNMnH+rrHNl1Ac68iLZZpkRKWV6VYSq2BUG340QSSgZKw0/TYaAyR8051NvwzTfyIGeeIK64HCjddtcb2aJT28SWpoXaCKG3pg8kmsIcf8YdwuA==
ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=cisco.com; dmarc=pass action=none header.from=cisco.com; dkim=pass header.d=cisco.com; arc=none
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=cisco.onmicrosoft.com; s=selector2-cisco-onmicrosoft-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=IWKQ3+t66sZDowqjap+PfPVS29HfO4S7MYaPn/1EojI=; b=f1HmRu9s9RPaVQguEN9fDGKNyMWONa8oOxO/gEsNVy4L3O50IxdiQmxCTiVxQwUpbB3Q0TcQRKQpq9zwsdGokp2CLJ5SXooufUBavTSezX8xU59Y8DYoDpWr5lUk8z5Ivgu+cFR3znpbgAbN72rbPjH7YzDmHdzLc8QN3mGYLOU=
Received: from BL0PR11MB2947.namprd11.prod.outlook.com (2603:10b6:208:33::28) by MN2PR11MB4712.namprd11.prod.outlook.com (2603:10b6:208:264::15) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.3131.20; Tue, 30 Jun 2020 23:41:01 +0000
Received: from BL0PR11MB2947.namprd11.prod.outlook.com ([fe80::3cea:d71b:ea4e:c02a]) by BL0PR11MB2947.namprd11.prod.outlook.com ([fe80::3cea:d71b:ea4e:c02a%2]) with mapi id 15.20.3131.027; Tue, 30 Jun 2020 23:41:01 +0000
From: "David McGrew (mcgrew)" <mcgrew@cisco.com>
To: Mihir Bellare <mihir@eng.ucsd.edu>
CC: Paul Grubbs <pag225@cornell.edu>, CFRG <cfrg@irtf.org>
Thread-Topic: [Cfrg] Do we need a selection contest for AEAD?
Thread-Index: AQHWRl+sLJeUiGUMVkyR6yf00MJrvKjn/esAgAAkJQCACcECAA==
Date: Tue, 30 Jun 2020 23:41:01 +0000
Message-ID: <55DF8455-D030-4961-A8CD-96C73F793CB6@cisco.com>
References: <CAMr0u6=QJuG9mshppB6qeryk6qekVKgi9D=WqGoa_L4sNgtYLg@mail.gmail.com> <CAKDPBw8oRZoBzCQv4yfM_QwGyHtqU42VXuV97MytjzsqyQJvcw@mail.gmail.com> <CACEhwkRqNTpW1--4Rc=2yjAHTLQBN1A38qrxbUBpyrmnpbP1VA@mail.gmail.com>
In-Reply-To: <CACEhwkRqNTpW1--4Rc=2yjAHTLQBN1A38qrxbUBpyrmnpbP1VA@mail.gmail.com>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
authentication-results: eng.ucsd.edu; dkim=none (message not signed) header.d=none;eng.ucsd.edu; dmarc=none action=none header.from=cisco.com;
x-originating-ip: [173.38.117.65]
x-ms-publictraffictype: Email
x-ms-office365-filtering-correlation-id: 6455c93b-544f-4e3e-4a2e-08d81d4f0c19
x-ms-traffictypediagnostic: MN2PR11MB4712:
x-microsoft-antispam-prvs: <MN2PR11MB4712A9A645B71C87620BD223C96F0@MN2PR11MB4712.namprd11.prod.outlook.com>
x-ms-oob-tlc-oobclassifiers: OLM:10000;
x-forefront-prvs: 0450A714CB
x-ms-exchange-senderadcheck: 1
x-microsoft-antispam: BCL:0;
x-microsoft-antispam-message-info: YT9Svxvecx2S1HyziyeJHapCA5QzDHwHSNIQrvRiX6KwbVS6ZbY8H3pBFdFUWvNiTxKSdfGXB/zZqNU+PzFJIP8E+O3JqiDDd0/tVA0OwE5IC6Pl7joZ9gz2izidaUKdILh5FjvETuqP101Bjd95wkN4ruayHD4AozzW7/z9iypoKBnfnJrhvtOPli24uTelrDvZ3V9rwVn3kgjuIOUAPbjzv1X+wkpdzFlFvHVh12QX++v2Um7Z48gwFQPBom5roLWlVx4vcIiJPn0uJ++yf4LvSnIoZLikuK7neI5dYJ1zXJ9MvRAa66Kx10mQ6Zl+LqbXosBzi8K8fbnG5hLgXhCb6dXcQEKk3keguu+/dEYDYPY3qn5FpqV6ox51dj5KI4WA+dqPTpGFeQ08lWMkPpWPvy1tuOgknrJ0TEVitBt0dd28Y9Wv6yKVa7+2aB/b+8P731hEZ3UFU06DpYWcXA==
x-forefront-antispam-report: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:BL0PR11MB2947.namprd11.prod.outlook.com; PTR:; CAT:NONE; SFTY:; SFS:(4636009)(396003)(136003)(39860400002)(366004)(346002)(376002)(2906002)(36756003)(86362001)(4326008)(8936002)(76116006)(66946007)(53546011)(8676002)(66476007)(66556008)(33656002)(166002)(5660300002)(83380400001)(6506007)(66446008)(64756008)(26005)(966005)(6916009)(478600001)(2616005)(71200400001)(296002)(186003)(6512007)(316002)(6486002)(54906003)(23603002); DIR:OUT; SFP:1101;
x-ms-exchange-antispam-messagedata: g3nPVRG4mUTvOy2Plsc7QcOftE2lvGCL6c+dmbXMrWtUMwtZ5QbHzXkC4HlRCAgU0S+/rdKGQWPAoUWwkh696r2FCJ/Q7bmc+3uIUVthyR3AYI/1vlTkKyoaTwD7Bio8ZhP1zVO5ddcJ98wg/zw+SAjsH8iQteQrnf8qoqwE5NfB9/JJTaGQVu3KZ1KoC9PE48TDDjjzGjtlJWMLoF+9MleoWqAYo6J5YD56TGrlYFCmu0bt/gkODMsH0wAaD5fVcyNjyeWdprwlEFLAPOZFNLCm8c6k9L68Z72fEv3OM5wl2mAHZy9BfByqjDLhgPx+VwlPcJwygWuYFiT8WE9+2FeA62yioUIqd8bf8LZWORr69Oi6TQKoeepXyrnNa/PhGnG0AVgu3c/3DVIH5YNyrcGmWgYSTIP1p3x5TLUfrmc4ehze+SytOXFwnUjdVfbvmeMLhd6tELv56uOBoJO70Y7Z088qVvV8sELpuVKsun0=
x-ms-exchange-transport-forked: True
Content-Type: multipart/alternative; boundary="_000_55DF8455D0304961A8CD96C73F793CB6ciscocom_"
MIME-Version: 1.0
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-AuthSource: BL0PR11MB2947.namprd11.prod.outlook.com
X-MS-Exchange-CrossTenant-Network-Message-Id: 6455c93b-544f-4e3e-4a2e-08d81d4f0c19
X-MS-Exchange-CrossTenant-originalarrivaltime: 30 Jun 2020 23:41:01.3782 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 5ae1af62-9505-4097-a69a-c1553ef7840e
X-MS-Exchange-CrossTenant-mailboxtype: HOSTED
X-MS-Exchange-CrossTenant-userprincipalname: 2wXwp2IV9Fzah4tCGi8vPSbLHDRwPJkVRCE2WC4kslD7jwIWPmFvT/HC9bz11cM835ORj3rzYE87sEIT2LxOlw==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: MN2PR11MB4712
X-OriginatorOrg: cisco.com
X-Outbound-SMTP-Client: 173.36.7.13, xch-aln-003.cisco.com
X-Outbound-Node: rcdn-core-3.cisco.com
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/CEJwn4kecyX1xLo1Y-BDLg7kes8>
Subject: Re: [Cfrg] Do we need a selection contest for AEAD?
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: Tue, 30 Jun 2020 23:41:10 -0000

Hi Mihir,

Please see inline:

On Jun 24, 2020, at 2:43 PM, Mihir Bellare <mihir@eng.ucsd.edu<mailto:mihir@eng.ucsd.edu>> wrote:


it might be good to have the first round be more of a "meta-competition" for discussing and prioritizing requirements and use cases.

Responding here both to the above and to Thomas's post about Deoxys. I think we need to step back to consider that what we call AEAD is not providing the message privacy that we think it is, and how that affects standardization.

RFC 5116<https://tools.ietf.org/html/rfc5116> says:  "there is no need to coordinate the details of the nonce format between the encrypter and the decrypter, as long the entire nonce is sent or stored with the ciphertext and is thus available to the decrypter ... the nonce MAY be stored or transported with the ciphertext ... "

What [BNT19]<https://eprint.iacr.org/2019/624.pdf> points out is that if you send the nonce with the ciphertext, for certain choices of nonces, you can compromise privacy of the message. This is kind of obvious in retrospect; the nonce can be message dependent. The difficulty is that in AEAD (which we call AE1), the nonce is assumed magically provided to the decryptor; the AEAD model does not say it is safe to transmit it.  [BNT19]<https://eprint.iacr.org/2019/624.pdf> defines a stronger AE2 goal which does what AEAD seems to have been understood to do, namely provide message privacy for any (non-repeating) choice of nonces, even if they are transmitted. This is done via nonce hiding, so the latter is not just about hiding the nonce itself (which is an added benefit) but, even before that, about hiding the message when nonces are visible.

Message-dependent nonces are not a likely choice, but they are allowed under RFC 5116. If one continues to use AEAD, I think in future standards, language as used in RFC 5116 should be changed to say that it is only with nonces that do not depend on the message (like random numbers or sequence numbers) or nonces that are not transmitted. But it is a burden for implementers to have to figure out if their nonces are conforming. With AE2, they don't need to; any (non-repeating) nonce choices, even message dependent, are fine.


I agree that RFC 5116 would benefit from the addition of the caveat that you suggest, but I do not see how it is a burden for implementers to determine if their nonces are conforming.  For the sake of completeness, I suppose that the RFC should also tell implementers that nonces should not be key-dependent.

regards,

David

On Tue, Jun 23, 2020 at 10:31 PM Thomas Peyrin <thomas.peyrin@gmail.com<mailto:thomas.peyrin@gmail.com>> wrote:
For nonce-hiding, I wonder if/how the constructions in https://eprint.iacr.org/2019/624.pdf could be applied on top of these modes optionally.

As above, it isn't just for nonce hiding that one would want to apply the above; it is to have message privacy even for transmitted nonces, meaning what AEAD was thought to provide. I think the goal for Deoxys and future AE schemes should be AE2 for this reason.

 As to the methods, yes, one could use them to get AE2. But the bounds mostly admit a birthday term. You seem to have worked to get good bounds for Deoxys, so perhaps one could find a direct way to get AE2 for Deoxys without sacrificing something in the bounds?

Mihir







<https://tools.ietf.org/html/rfc5116>

<https://tools.ietf.org/html/rfc5116>

<https://tools.ietf.org/html/rfc5116>

_______________________________________________
Cfrg mailing list
Cfrg@irtf.org<mailto:Cfrg@irtf.org>
https://www.irtf.org/mailman/listinfo/cfrg