Re: [Cfrg] Using ephemeral DH in lieu of fresh nonces

"Hao, Feng" <Feng.Hao@warwick.ac.uk> Mon, 22 June 2020 22:46 UTC

Return-Path: <Feng.Hao@warwick.ac.uk>
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 6C90F3A1245 for <cfrg@ietfa.amsl.com>; Mon, 22 Jun 2020 15:46:09 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.9
X-Spam-Level:
X-Spam-Status: No, score=-1.9 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, HTML_MESSAGE=0.001, RCVD_IN_MSPIKE_H2=-0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
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 pjG9Nam9yWyj for <cfrg@ietfa.amsl.com>; Mon, 22 Jun 2020 15:45:56 -0700 (PDT)
Received: from EUR04-HE1-obe.outbound.protection.outlook.com (mail-eopbgr70073.outbound.protection.outlook.com [40.107.7.73]) (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 BF8913A1226 for <cfrg@ietf.org>; Mon, 22 Jun 2020 15:45:55 -0700 (PDT)
ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=Qu0nJezNEr/GHW0+bOpHIy0wAgi+QBXeq6c1GK2EsE2F0Av1OMh7lLX/rqJvrCmQPvLz1oOAZcFPH20cnEEjNMfuA5fLCxL7zQtUX+wyXXLxhOxzP88mreuFlXtqf8i3Mp11cD0yhjaYbMrlUTE5qtrE/zHheY/j3wuO7hCXiw7bb3tIMb8OqKMSIHMzZ4vqZhv/lt+w07lrvv3B9NwYjyAM53RUk3d9F7SC7TEG+ATfECE18KmyBoDyhBcbzL1AcMxcL5CE2/6rMV/aD4qavzl6Uz2KERDjXxQ+PEhrxzZeDW1UFYxiB10e6XEl+N+gdonGJgbFj8VTycGsHV+kbw==
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=jWP5nn7zU3Q118T0XU7abNov+C8zw1rW1SOYjJQumjY=; b=MlsZ1G8mAaP18iQEHp4mZSEUZ3Tkx+23jjBVbb4Xjr8lriEmIK2AtQR7yaEMGRwp9T2PaANv4wHpJD/Nx/5AFKnQ3UP82RrikY+8YMY1F0aUqPWI71vl5KolYDexGWejTW7dR89/ELWdC/aRCHqf0mFHJAhMNs/zwmRzTVc5gk/iLxtc+DsA4X7nz6Jd+C9PEIx0oaRggRpXDk1hulq10gB+7YhzpZg2lQ13arwoiVAuw+uK7/rQ1vV1RuIdk0gpCyBIjge1vlxYm84cLjY7MBgLus1R629L3h/qd7QkfpE4hYuVwOCRxHU2w2J+pDUIyrsn2QokCBCydmoUsiAyHQ==
ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=warwick.ac.uk; dmarc=pass action=none header.from=warwick.ac.uk; dkim=pass header.d=warwick.ac.uk; arc=none
Received: from VI1PR01MB4285.eurprd01.prod.exchangelabs.com (2603:10a6:803:65::27) by VI1PR01MB4352.eurprd01.prod.exchangelabs.com (2603:10a6:803:67::10) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.3109.22; Mon, 22 Jun 2020 22:45:48 +0000
Received: from VI1PR01MB4285.eurprd01.prod.exchangelabs.com ([fe80::dd1c:bb47:e1be:cc52]) by VI1PR01MB4285.eurprd01.prod.exchangelabs.com ([fe80::dd1c:bb47:e1be:cc52%6]) with mapi id 15.20.3109.027; Mon, 22 Jun 2020 22:45:48 +0000
From: "Hao, Feng" <Feng.Hao@warwick.ac.uk>
To: Dan Brown <danibrown@blackberry.com>
CC: "<cfrg@ietf.org>" <cfrg@ietf.org>
Thread-Topic: [Cfrg] Using ephemeral DH in lieu of fresh nonces
Thread-Index: AQHWSKY9Eg6uxJ8U8EOiX/JtUel+Wajkv8IAgAAdY4CAACNIgIAANp2AgAAWKoA=
Date: Mon, 22 Jun 2020 22:45:48 +0000
Message-ID: <D2423217-E551-419E-87FA-7C3D16A64D90@warwick.ac.uk>
References: <326ebefc65c17f7fc11879b9b966a1e4585b1f16.camel@loup-vaillant.fr> <CADi0yUM6MQd0TPczK+YKSdbu1nzFaV+peC_0yf9Soat8d3+eLg@mail.gmail.com> <72d8587f17c94dfd8b67570f6a59037f@blackberry.com> <BN7PR11MB2641AC625A04DBFCFC2F4C11C1970@BN7PR11MB2641.namprd11.prod.outlook.com> <f79952a40fbe460e98b548f183bff1b9@blackberry.com> <D048D4D1-42EE-4424-A521-397121302970@live.warwick.ac.uk>
In-Reply-To: <D048D4D1-42EE-4424-A521-397121302970@live.warwick.ac.uk>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
user-agent: Microsoft-MacOutlook/10.10.16.200509
authentication-results: blackberry.com; dkim=none (message not signed) header.d=none;blackberry.com; dmarc=none action=none header.from=warwick.ac.uk;
x-originating-ip: [86.1.47.16]
x-ms-publictraffictype: Email
x-ms-office365-filtering-correlation-id: 635d1a3e-5cd8-45a5-5190-08d816fe021c
x-ms-traffictypediagnostic: VI1PR01MB4352:
x-microsoft-antispam-prvs: <VI1PR01MB4352B072ED7138A1E7573728D6970@VI1PR01MB4352.eurprd01.prod.exchangelabs.com>
x-ms-oob-tlc-oobclassifiers: OLM:8882;
x-forefront-prvs: 0442E569BC
x-ms-exchange-senderadcheck: 1
x-microsoft-antispam: BCL:0;
x-microsoft-antispam-message-info: N1M7XdlXwxg+sPaQd6rrPrgpE3XB65aRl6k4yHJJNW3naRGfYiKHxZbfOtAYTnvEJBNCOT52ed/LxC1pXp9FoWDX+tvBPjeV625to1wOnXduy3FTo+RyKdaaW2eRm0dBAOOFL/xhIu/Nplp2tUNqQs+1SihwLWNumsPbqwn8Kceok1y+TE6qtExxUwaDWmSN68fhg2wNght4FL1+/I+JGNf+Z4Q9ca8rsZSDSGf1KQyAT0sk66Lzd31upfl9dD3FulqM+4zPFD/1/Z3hHPx69wnlU+6eqTmPGHwG7m0XsCBiwawp079sWegt+OIbU2VpitLBQaeSCkDvFp4j4kK5TJ4mNcJAeJeHWiN3zkkVTMFhHr+yOBoJ2HGA75ZRBdej7UoqQ1SD76y4OiIeY6h/EQ==
x-forefront-antispam-report: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:VI1PR01MB4285.eurprd01.prod.exchangelabs.com; PTR:; CAT:NONE; SFTY:; SFS:(4636009)(39860400002)(376002)(396003)(346002)(136003)(366004)(83380400001)(478600001)(66946007)(71200400001)(8936002)(316002)(6512007)(66476007)(66556008)(64756008)(66446008)(91956017)(76116006)(166002)(8676002)(66574015)(186003)(2906002)(33656002)(86362001)(2616005)(786003)(53546011)(6506007)(36756003)(9326002)(26005)(5660300002)(4326008)(6916009)(6486002); DIR:OUT; SFP:1101;
x-ms-exchange-antispam-messagedata: Vi5ctE2FbUiKuLsIDNbRtD1+/w8rZ3pAwCnWvYn3B9GYCcVJFchf2ZP6rd9yDIO2Qgwd9tVkX+XdzcBmAfM4Bf6ZuOnr8SO6TnS17ltTHUrNDvCgMThtdU1aEU1XKmegk8+mDeWA+dOMqiCqe+0Bm5y0CDyNUZ4kZGeqrC3q/JAOBmkeF0AvTFkC/8CuBJbYlrF5eCCJRaFfT6Wt+SilcUK7xy2XixipMocqYKqI6EbcJwLd2SPlz9j8gy9Q3fTlAcY2gP3zxo4rvGR7p3npfNGVAgBUV9CIWArvXjaDSSk8hg7r3iaDAmUCMxRCn07dXFolCHeOEh5brXlm3ewdI5XleJqOrWXxPYijwbiNLn89UnipAEX8frvvuJml0uWD1TvSUHKTe8oC/UKPIA8vD1vAwKR81++LCvrftqnF+bi4fYuc84sClOT43YDUeysXc6OlhjnWgxV/JiRGKi3heKNPzLkL+nn+o3ESApLYOc8=
x-ms-exchange-transport-forked: True
Content-Type: multipart/alternative; boundary="_000_D2423217E551419E87FA7C3D16A64D90warwickacuk_"
MIME-Version: 1.0
X-OriginatorOrg: warwick.ac.uk
X-MS-Exchange-CrossTenant-Network-Message-Id: 635d1a3e-5cd8-45a5-5190-08d816fe021c
X-MS-Exchange-CrossTenant-originalarrivaltime: 22 Jun 2020 22:45:48.5410 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 09bacfbd-47ef-4465-9265-3546f2eaf6bc
X-MS-Exchange-CrossTenant-mailboxtype: HOSTED
X-MS-Exchange-CrossTenant-userprincipalname: /t7owFdndZrUqEO25K7/EIxVkJapotvq38+NaBJ15jChhukzwD6LEvEuEsDLkFVI8jmRLEEFteYRnFuV+TY3qtk26Rqm6T5HfGZ08fBzE/Q=
X-MS-Exchange-Transport-CrossTenantHeadersStamped: VI1PR01MB4352
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/jgNRM5WfgoseFIn8Fa55hYSWaTA>
Subject: Re: [Cfrg] Using ephemeral DH in lieu of fresh nonces
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, 22 Jun 2020 22:46:13 -0000

Hi Dan,

To me, the malicious implementation threat (also known as algorithm substitution attack in the literature) is a realistic threat, especially in trusted computing systems, where crypto software is encapsulated within a tamper resistant module and the source code is inaccessible for checking by design.

The goal with ASA is to allow a state-funded attacker to conduct mass surveillance. However, the threat mode requires that the attack MUST remain undetectable by the public. It doesn’t really make sense to protect any specific entity from this attack (if NSA wants to have a targeted attack against your system, your system will be hacked no matter what). Hence, the security goal here is to protect the public users at a mass scale, assuming that an agency-controlled trusted computing system has been selling in the commercial market at a large scale (note that even TC vendors do not always have complete control in the software loaded to a hardware system in the factory given the very complex global supply chain issue, so the attack doesn’t necessarily require cooperation of the TC vendors or even their awareness).

Think about the three-letter agency who passively sits at ISPs to watch all the key exchange sessions. All key exchange items must be uniformly distributed to avoid detection by statistical analysis. Hence, even if the attacker might have knowledge of the seed, it is not a straightforward task to extract the private key to break the session key at a mass scale; some effort in computing the discrete logarithm is unavoidable. Of course, such an attacker will always opt for simpler and more effective attacks. In an earlier paper (https://eprint.iacr.org/2014/364.pdf), we presented a compression-based ASA attack (Figure 5, p. 12), which allows the attacker to passively break a DHIES session without being detected. Unfortunately, the same attack also defeats countermeasures proposed in many crypto papers based on merely using deterministic encryption. Nonetheless, in the paper, we also provided a solution based on using zero-knowledge proof to ensure the ciphertext is well-formed so this specific attack is addressable.

The 1-bit key exfiltration attack that is discussed below, although technically valid, has the risk of being detected by the public users. Hence, I don’t think it’s considered a very realistic attack in the threat model above. As said, the attacker must ensure the attack is covert and they always opt for simpler and more effective exploit path.

In the case of DH and PAKE, the good news is that even if we consider such a powerful state-funded adversary who has the capability to substitute a crypto implementation, it’s still not that easy for the attacker to break session keys at a mass scale without being detected. However, the addition of a nonce will change things dramatically, as this will provide an easy anchor for the attacker, e.g., the nonce may be an encrypted form of an ephemeral secret encrypted by a master key controlled by the adversary. Unlike other items, it is difficult to check whether a nonce is well-formed, i.e., a random string being random indeed. The attacker can now trivially and passively break every session, while keeping the attack totally undetectable. The use of a patterned nonce (say based on timestamp etc) might mitigate the attack, but that will also increase the chance of collision, and will significantly add to the complexity of the implementation.

Cheers,
Feng


From: Cfrg <cfrg-bounces@irtf.org> on behalf of Dan Brown <danibrown@blackberry.com>
Date: Monday, 22 June 2020 at 20:12
To: "Scott Fluhrer (sfluhrer)" <sfluhrer@cisco.com>om>, Hugo Krawczyk <hugo@ee.technion.ac.il>il>, Loup Vaillant-David <loup@loup-vaillant.fr>fr>, "<cfrg@ietf.org>" <cfrg@ietf.org>
Subject: Re: [Cfrg] Using ephemeral DH in lieu of fresh nonces

Hi Scott,
Good point too, about DH itself allowing 1 bit exfiltration (by a malicious implementation).

A bunch of naïve questions below …

The malicious implementation threat model is still very confusing to me. What are reasonable capabilities? What are the goals?

(Why not just fill the DH keys with PRNG output from a seed known to be bad guys?  Is it that there are some other keys, e.g. signature keys, that we want to exfiltrate instead, ultimately to forge signatures, over and above defeating the privacy provided by DH.)

I suppose that I was thinking about the Dual_EC_DRBG in TLS, which seemed to work well against nonces, but not against DH values.  If this is a realistic threat, i.e. a good DH implementation being attacked by a bad RNG implementation, then your DH-filtering attack still applies if the bad RNG can pre-compute the DH values.  The best fix is to use a good RNG, but if Dual_EC is technically worse than DH-filtering, it seems be a difference in the nonces (it socially worse due to its standardization, etc.)

In a PAKE system, what about a bad RNG that does not see the password? Would the bad RNG be able exfiltrate things by filtering DH-type values it should not be able to compute (say, if the base point is derived from the password)?  The bad-seed RNG could defeat security (without using nonces), or at least expose passwords to offline attacks.  Would a bad-seed RNG be more detectable, or less likely, than DH-filtering RNG?

Dan