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

["Scott Fluhrer (sfluhrer)" <[e-mail]>]

I do not feel that I am qualified to make general statements about systems that are secure against malicious implementations that attempt to exfiltrate secrets; to do this completely would sound to me to be quite difficult (especially since ASAs are not the only thing to worry about – could an implementation leak some information with the timing?)

However, I will address the two PAKEs that have recently been selected:


  *   CPace; if the adversary spikes the entropy source (so that they can guess the randomness used by either the client or the server), then they can perform an offline dictionary attack; CPace uses, as you suggested, a base point derived from the password, and so if they know the exponent, they can recover the base point that was actually used, and then compare it to the base points that are derived from the various passwords in his dictionary.  In addition, even if the password is strong (and not in the dictionary), the attacker can still derive the shared secret for that specific session (and thus listen in, and possibly MITM, if he wishes).
  *   Opaque is arguably worse; if the adversary spikes the client’s entropy source, then the attacker can recover the clients private signature keys (even if the password was strong); he can then able to log in as the client (without knowing the actual password).  It is less clear if Opaque would allow a MITM, as it doesn’t itself derive a shared secret, but uses another exchange to do that (possibly an authenticated DH or MQV); to MITM, we’d have to assume that the adversary spikes that entropy as well.


From: Dan Brown <[e-mail]>
Sent: Monday, June 22, 2020 3:11 PM
To: Scott Fluhrer (sfluhrer) <[e-mail]>; Hugo Krawczyk <[e-mail]>; Loup Vaillant-David <[e-mail]>; <[e-mail]> <[e-mail]>
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

From: Scott Fluhrer (sfluhrer) <[e-mail]<mailto:[e-mail]>>
Sent: Monday, June 22, 2020 1:05 PM
To: Dan Brown <[e-mail]<mailto:[e-mail]>>; Hugo Krawczyk <[e-mail]<mailto:[e-mail]>>; Loup Vaillant-David <[e-mail]<mailto:[e-mail]>>; <[e-mail]<mailto:[e-mail]>> <[e-mail]<mailto:[e-mail]>>
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 <[e-mail]<mailto:[e-mail]>> On Behalf Of Dan Brown
Sent: Monday, June 22, 2020 11:20 AM
To: Hugo Krawczyk <[e-mail]<mailto:[e-mail]>>; Loup Vaillant-David <[e-mail]<mailto:[e-mail]>>; <[e-mail]<mailto:[e-mail]>> <[e-mail]<mailto:[e-mail]>>
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 <[e-mail]<mailto:[e-mail]>> On Behalf Of Hugo Krawczyk
Sent: Monday, June 22, 2020 11:02 AM
To: Loup Vaillant-David <[e-mail]<mailto:[e-mail]>>; <[e-mail]<mailto:[e-mail]>> <[e-mail]<mailto:[e-mail]>>
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 <[e-mail]<mailto:[e-mail]>> 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
[e-mail]<mailto:[e-mail]>
https://www.irtf.org/mailman/listinfo/cfrg<https://urldefense.proofpoint.com/v2/url?u=https-3A__urldefense.proofpoint..com_v2_url-3Fu-3Dhttps-2D3A-5F-5Fwww.irtf.org-5Fmailman-5Flistinfo-5Fcfrg-26d-3DDwMFaQ-26c-3DyzoHOc-5FZK-2Dsxl-2DkfGNSEvlJYanssXN3q-2Dlhj0sp26wE-26r-3DqkpbVDRj7zlSRVql-2DUonsW647lYqnsrbXizKI6MgkEw-26m-3Dr1zeEz6DEF0-2DbdDU7a7UYsRe6vNvnWpEk4pzla6k-5FOw-26s-3DTnDdq0O8w7uMnPtXoYDGprqQPk-5F1YZfKPZTB-2Db4rv3o-26e-3D&d=DwMGaQ&c=yzoHOc_ZK-sxl-kfGNSEvlJYanssXN3q-lhj0sp26wE&r=mf6j6fOClApRsArWE9wqI1rEGUVkfxZ0aXWmn35nK_c&m=t08k5n9Fi0sWBQAvptHMHJPZVGzIwEhq41trz3Rn9Q0&s=9cklS7GBbaibRfGUdDu8ipkt-JFIpMblorqkCfp7-lQ&e=>
________________________________
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.