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

Dan Brown <danibrown@blackberry.com> Mon, 22 June 2020 19:11 UTC

Return-Path: <danibrown@blackberry.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 1C63D3A10D2 for <cfrg@ietfa.amsl.com>; Mon, 22 Jun 2020 12:11:12 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.999
X-Spam-Level:
X-Spam-Status: No, score=-1.999 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIMWL_WL_HIGH=-0.001, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, HTML_MESSAGE=0.001, HTTPS_HTTP_MISMATCH=0.1, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=blackberry.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 LzKUzlrWPmuA for <cfrg@ietfa.amsl.com>; Mon, 22 Jun 2020 12:11:09 -0700 (PDT)
Received: from smtp-pg11.blackberry.com (smtp-pg11.blackberry.com [68.171.242.227]) (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 7B3263A10B5 for <cfrg@ietf.org>; Mon, 22 Jun 2020 12:11:07 -0700 (PDT)
Received: from pps.filterd (mhs401ykf.rim.net [127.0.0.1]) by mhs401ykf.rim.net (8.16.0.42/8.16.0.42) with SMTP id 05MIvDve134391; Mon, 22 Jun 2020 15:11:00 -0400
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=blackberry.com; h=from : to : subject : date : message-id : references : in-reply-to : content-type : mime-version; s=corp19; bh=da22f8W7Cz5S+rjVPp0VqbEPIPuyfLbpzXGexEa/NrQ=; b=w1eXWnhJm7CIxwtCecfbOVPs6gU8eSHGcyJIGCuaMkCxjtRTdrcU/gzEDwEIu9XW8QHL hiv0kg2LEMYUfFaRRPhZVYbYolhSJWxHw+GKhgIjmph4cS51Nr7tLu6sJnq7iiBbuhsw YJmxED1e/2mGK++LgagOUS1N4Baz4AEE1EBtQIZbt+xywQIm+HhYfxCbYDJeypPQuknr jP0g4G90B//1ixtp1NiH0XcumEX3ASTrskzv/6F95xlikY1N7ZtHDVuNTkaY/Uid8P/N kll9c7mcuCdoJp4jMmKiHm+i0jw4XbZIe+Lcl+A+HQplt/1lUt4HnRsAz9d2Calvr2sg mA==
Received: from xch211ykf.rim.net (xch211ykf.rim.net [10.2.27.111]) by mhs401ykf.rim.net with ESMTP id 31sdq6mbbq-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128 verify=NOT); Mon, 22 Jun 2020 15:11:00 -0400
Received: from XCH210YKF.rim.net (10.2.27.110) by XCH211YKF.rim.net (10.2.27.111) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.1913.5; Mon, 22 Jun 2020 15:10:59 -0400
Received: from XCH210YKF.rim.net ([fe80::ac8d:3541:704c:478a]) by XCH210YKF.rim.net ([fe80::ac8d:3541:704c:478a%5]) with mapi id 15.01.1913.007; Mon, 22 Jun 2020 15:10:59 -0400
From: Dan Brown <danibrown@blackberry.com>
To: "Scott Fluhrer (sfluhrer)" <sfluhrer@cisco.com>, Hugo Krawczyk <hugo@ee.technion.ac.il>, Loup Vaillant-David <loup@loup-vaillant.fr>, "<cfrg@ietf.org>" <cfrg@ietf.org>
Thread-Topic: [Cfrg] Using ephemeral DH in lieu of fresh nonces
Thread-Index: AQHWSKYmikeQFbsqOkmXt4xvq8L1H6jku+DAgABkVID//9jHkA==
Date: Mon, 22 Jun 2020 19:10:59 +0000
Message-ID: <f79952a40fbe460e98b548f183bff1b9@blackberry.com>
References: <326ebefc65c17f7fc11879b9b966a1e4585b1f16.camel@loup-vaillant.fr> <CADi0yUM6MQd0TPczK+YKSdbu1nzFaV+peC_0yf9Soat8d3+eLg@mail.gmail.com> <72d8587f17c94dfd8b67570f6a59037f@blackberry.com> <BN7PR11MB2641AC625A04DBFCFC2F4C11C1970@BN7PR11MB2641.namprd11.prod.outlook.com>
In-Reply-To: <BN7PR11MB2641AC625A04DBFCFC2F4C11C1970@BN7PR11MB2641.namprd11.prod.outlook.com>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach: yes
X-MS-TNEF-Correlator:
x-originating-ip: [100.64.97.250]
Content-Type: multipart/signed; protocol="application/x-pkcs7-signature"; micalg=2.16.840.1.101.3.4.2.1; boundary="----=_NextPart_000_0064_01D648A7.54E413A0"
MIME-Version: 1.0
X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:6.0.216, 18.0.687 definitions=2020-06-22_11:2020-06-22, 2020-06-22 signatures=0
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/xKyWD-ey29OW9OIWyNzTM9U0HQM>
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 19:11:12 -0000

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

 

From: Scott Fluhrer (sfluhrer) <sfluhrer@cisco.com> 
Sent: Monday, June 22, 2020 1:05 PM
To: Dan Brown <danibrown@blackberry.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

 

As for subliminal channels to exfiltrate keys, ephemeral DH can do that just fine (it just takes longer).

 

To exfiltrate a key (one bit at a time), one simple way you can do that is, when you need to send the next ephemeral DH key share, you generate one honestly, and check its lsbit; if it is not the bit you want to leak, then you multiple the key share by the generator (and increment the private value by 1), and repeat your check.  This means that the lsbits of the successive key shares you send spell out the key.  There are more sophisticated ways to do this; this is just a simple example.

 

What a nonce gives you is an easy-to-use way to exfiltrate multiple bits at once; however I don’t know if the difference in exploitability difficulty is really that significant.

 

From: Cfrg <cfrg-bounces@irtf.org <mailto:cfrg-bounces@irtf.org> > On Behalf Of Dan Brown
Sent: Monday, June 22, 2020 11:20 AM
To: Hugo Krawczyk <hugo@ee.technion.ac.il <mailto:hugo@ee.technion.ac.il> >; Loup Vaillant-David <loup@loup-vaillant.fr <mailto:loup@loup-vaillant.fr> >; <cfrg@ietf.org <mailto:cfrg@ietf.org> > <cfrg@ietf.org <mailto:cfrg@ietf.org> >
Subject: Re: [Cfrg] Using ephemeral DH in lieu of fresh nonces

 

Hi Hugo,

Good points about the advantages of nonces with ephemeral DH (for PAKE or TLS, etc.).

What about the disadvantages, such as misuse of nonces as a subliminal channel to exfiltrate keys?  

 

Perhaps some protocols are already mitigate this disadvantage (e.g. strict patterned nonces, counters).  Perhaps nonce-misuse is non-issue due to the obscure threat model and due to the abundance of other subliminal channels (timing, non-crypto nonces, etc.)

 

Best regards,

​​​​​

Dan

 

From: Cfrg <cfrg-bounces@irtf.org <mailto:cfrg-bounces@irtf.org> > On Behalf Of Hugo Krawczyk
Sent: Monday, June 22, 2020 11:02 AM
To: Loup Vaillant-David <loup@loup-vaillant.fr <mailto:loup@loup-vaillant.fr> >; <cfrg@ietf.org <mailto:cfrg@ietf.org> > <cfrg@ietf.org <mailto:cfrg@ietf.org> >
Subject: [Cfrg] Using ephemeral DH in lieu of fresh nonces

 

In the email below, Loup raises a natural question: Why not reuse ephemeral DH values in a protocol instead of fresh nonces?

 

Formalisms apart, fresh non-repeating session identifiers are essential for many reasons: against replay attacks, for binding session flows together, avoiding  "composition attacks" (e.g., where flows from different sessions are mixed-and-matched), ensuring domain separation, etc. A natural implementation of session id's uses session-specific fresh random nonces. An equally natural question (and I think your email was referring to this issue) is why not use the ephemeral DH in lieu of random nonces, after all these values are selected as fresh random values for each session. 

 

A generic reason (which I strongly advocate) for not doing so is that one should avoid having the same element in the protocol to serve  two separate functionalities/roles (in this case it would be using a DH value as key share and also as nonce/sessionid). This results in fragile protocols that can easily go wrong with variants of the protocol or when the protocol evolves over time, and is prone to bad implementations. For example, if one of the roles of this element is not  required anymore (due to changes in the protocol or changes in the setting where the protocol operates), the element may be changed "without remembering" that it had this other role. 

 

Concretely, in the case of using ephemeral DH values for freshness, there are good practical examples where security breaks with the dual use of these values. For example, an application may decide (e.g., for performance reasons) that they do not need "perfect" forward secrecy, but that a one-minute forward-secrecy window of repeated ephemeral DH values is enough for the application. With repeated DH values used as session ids, the uniqueness of the session id is gone.  This is also the case of applications that need to avoid forward secrecy at all (see requests for a static version of TLS 1.3 in the TLS mailing list). Yet another example is the SIGMA-I protocol (used in TLS 1.3 and IKEv1). If the initiator sends g^x in the first message, this value can be used against replay attacks in the responder's signature. Then, someone decides (and there may be good reasons for that) to send g^x only in the third message and you lose your anti-replay mechanism.

 

Mea culpa: I have used ephemeral DH values in the dual functionality of key shares and session identifiers in several of my papers for the sake of analysis/notation simplicity. But you should not do it when building real-world implementations. In the SIGMA instantiation in draft-krawczyk-cfrg-opaque, for example, nonces are used in addition to DH values. (See also appendix B of https://webee.technion.ac.il/~hugo/sigma-pdf.pdf <https://urldefense.proofpoint.com/v2/url?u=https-3A__webee.technion.ac.il_-7Ehugo_sigma-2Dpdf.pdf&d=DwMFaQ&c=yzoHOc_ZK-sxl-kfGNSEvlJYanssXN3q-lhj0sp26wE&r=qkpbVDRj7zlSRVql-UonsW647lYqnsrbXizKI6MgkEw&m=r1zeEz6DEF0-bdDU7a7UYsRe6vNvnWpEk4pzla6k_Ow&s=XaZPR3wmEdhE0biqIgP9ZcuesZGSBCE_0gDBnILUtek&e=>  )

 

Hugo

 

On Fri, Jun 19, 2020 at 12:34 PM Loup Vaillant-David <loup@loup-vaillant.fr <mailto:loup@loup-vaillant.fr> > wrote:

>>From the latest draft:

  https://tools.ietf.org/html/draft-haase-cpace-01 <https://urldefense.proofpoint.com/v2/url?u=https-3A__tools.ietf.org_html_draft-2Dhaase-2Dcpace-2D01&d=DwMFaQ&c=yzoHOc_ZK-sxl-kfGNSEvlJYanssXN3q-lhj0sp26wE&r=qkpbVDRj7zlSRVql-UonsW647lYqnsrbXizKI6MgkEw&m=r1zeEz6DEF0-bdDU7a7UYsRe6vNvnWpEk4pzla6k_Ow&s=AuO92opvT_bYl9sYBgQ79RpgQzjqQZfXef0Dl192XxY&e=> 

""" Let sid be a session id byte string chosen for each protocol
""" session before protocol execution; The length len(sid) SHOULD be
""" larger or equal to 16 bytes.

""" It is RECOMMENDED sid, is generated by sampling ephemeral random
""" strings.

Unlike ZPAD, The draft doesn't explain this recommendation.
What problem may occur if we omit sid altogether?

Even if G ends up being reused across several sessions, I don't believe
there's any way to tell, because Ya and Yb are uniformly distributed if
ya and yb are indeed random. I feel like I'm missing something.

Loup.


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

  _____  

This transmission (including any attachments) may contain confidential information, privileged material (including material protected by the solicitor-client or other applicable privileges), or constitute non-public information. Any use of this information by anyone other than the intended recipient is prohibited. If you have received this transmission in error, please immediately reply to the sender and delete this information from your system. Use, dissemination, distribution, or reproduction of this transmission by unintended recipients is not authorized and may be unlawful.

----------------------------------------------------------------------
This transmission (including any attachments) may contain confidential information, privileged material (including material protected by the solicitor-client or other applicable privileges), or constitute non-public information. Any use of this information by anyone other than the intended recipient is prohibited. If you have received this transmission in error, please immediately reply to the sender and delete this information from your system. Use, dissemination, distribution, or reproduction of this transmission by unintended recipients is not authorized and may be unlawful.