Subject: [Cfrg] CPACE: what the "session id" is for?

From: Loup Vaillant-David <[email-masked]>
Date: Fri, 19 Jun 2020 18:33:19 +0200

>From the latest draft:

  https://tools.ietf.org/html/draft-haase-cpace-01

""" 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.

---

From: Björn Haase <[email-masked]>
Date: Fri, 19 Jun 2020 17:13:50 +0000

Dear Loup,

This is a good question. 

The sid originally came into the design of CPace as sort of an "artifact" and as a consequence of the security analysis in the UC framework, which requires that each independent session.is given a unique session id prior to the protocol start. An analysis in the game-based models such as FTG or ROR would not have required the nonce value.

In my analysis and after discussions with Ralf Küster's group prepending a nonce to hash inputs is important in order to get UC composability guarantees if a global single hash function is to be used, since we really need to avoid any form of "shared state" between different concurrent sessions.

Still IMO, the nonce should not be considered solely as an technicality and artifact of the proof strategy but also as an advantage and security feature.

If one composes a larger protocol which uses CPace as a substep, it needs to provide its sid value to CPace in the course of the composition and make sure that any output that is generated here will be tied to this session id. Any output of a possibly concurrently running other CPace session could not provide any valuable input to the attacker. For such a composed security protocol, the sid could be considered as to form some sort of "glue" linking the individual subblocks of the composed protocol (as e.g. used in AuCPace). 

In my opinion this could be of real-world use when designing APIs for security functionality that is internally composed together by using different subparts, such as suggested by Ran Canetti in https://mailarchive.ietf.org/arch/msg/cfrg/PBMlEarxjp5l1EPfTYamE3Y_0g4/ . 

The sid also serves for making each generator ephemeral for each session and this could be useful for mitigating side-channel analysis since the adversary has essentially only one single trace available. This "ephemeral generator G" feature that comes with the inclusion of the sid is IMO also relevant for the "quantum annoying" property.

There has also be a related post on this list https://mailarchive.ietf.org/arch/msg/cfrg/fgwMYLfaa1ZbF_UgKcurse211KE/ by Ran Canetti.

I have also tried to discuss this topic roughly in slides #53 to #58 in

https://ches.iacr.org/2019/src/slides/Day3/Session13_IOTSec/Paper2_Session13_Presentation_AuCPace_CHES2019.pdf

Your question moreover has been an important topic that Michel Abdalla and Manuel have been discussing last week regarding the security proofs. In the process of the finalization of the proceedings version of their paper https://eprint.iacr.org/2020/320 , they had the plan to discuss this topic more in depth in the text and with their co-authors.

>From this discussion with Michel and Manuel I took with me that we three agreed on the assessment that for UC composability in the Joint-State setting (and a global hash function as RO is some sort of joint state) a nonce value needs to be involved in each hash operation and, thus, also in the calculation of the generator for CPace (and TBPEKE). If I understood correctly, this was also some aspect that they planned to consider in the re-work of their Annex B regarding the TBPEKE proof (which is except for the mapping almost exactly like CPace).

For this reason, I think that it is a good idea to keep the "sid" and not purely some artifact from the proof approach.

Yours,

Björn.

Mit freundlichen Grüßen I Best Regards 

Dr. Björn Haase 

Senior Expert Electronics | TGREH Electronics Hardware

Endress+Hauser Liquid Analysis

Endress+Hauser Conducta GmbH+Co.KG | Dieselstrasse 24 | 70839 Gerlingen | Germany
Phone: +49 7156 209 377 | Fax: +49 7156 209 221
[email-masked] |  www.conducta.endress.com 

Endress+Hauser Conducta GmbH+Co.KG
Amtsgericht Stuttgart HRA 201908
Sitz der Gesellschaft: Gerlingen
Persönlich haftende Gesellschafterin:
Endress+Hauser Conducta Verwaltungsgesellschaft mbH
Sitz der Gesellschaft: Gerlingen
Amtsgericht Stuttgart HRA 201929
Geschäftsführer: Dr. Manfred Jagiella

Gemäss Datenschutzgrundverordnung sind wir verpflichtet, Sie zu informieren, wenn wir personenbezogene Daten von Ihnen erheben.
Dieser Informationspflicht kommen wir mit folgendem Datenschutzhinweis (https://www.endress.com/de/cookies-endress+hauser-website) nach.

Disclaimer: 

The information transmitted is intended only for the person or entity to which it is addressed and may contain confidential, proprietary, and/or privileged material. Any review, retransmission, dissemination or other use of, or taking of any action in reliance upon, this information by persons or entities other than the intended recipient is prohibited. If you receive this in error, please contact the sender and delete the material from any computer. This e-mail does not constitute a contract offer, a contract amendment, or an acceptance of a contract offer unless explicitly and conspicuously designated or stated as such.

-----Ursprüngliche Nachricht-----
Von: Cfrg <[email-masked]> Im Auftrag von Loup Vaillant-David
Gesendet: Freitag, 19. Juni 2020 18:33
An: [email-masked]
Betreff: [Cfrg] CPACE: what the "session id" is for?

>From the latest draft:

  https://eur03.safelinks.protection.outlook.com/?url=https%3A%2F%2Ftools.ietf.org%2Fhtml%2Fdraft-haase-cpace-01&amp;data=02%7C01%7Cbjoern.haase%40endress.com%7C919f03384285480aff6e08d8146e8b15%7C52daf2a93b734da4ac6a3f81adc92b7e%7C1%7C0%7C637281812313363894&amp;sdata=WU6zi7uD9S6%2F9RjhsQBhfKMl6ylHH%2FS58G6rDLMQkyQ%3D&amp;reserved=0

Loup.

_______________________________________________
Cfrg mailing list
[email-masked]
https://eur03.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.irtf.org%2Fmailman%2Flistinfo%2Fcfrg&amp;data=02%7C01%7Cbjoern.haase%40endress.com%7C919f03384285480aff6e08d8146e8b15%7C52daf2a93b734da4ac6a3f81adc92b7e%7C1%7C0%7C637281812313363894&amp;sdata=CNbRgqbWTz%2BbifiT%2FvhFv76Z6Yejo0CfTl2gpxV0oQc%3D&amp;reserved=0

---

From: Loup Vaillant-David <[email-masked]>
Date: Fri, 19 Jun 2020 23:46:56 +0200

Dear Björn,

Thank you for the lightning quick response. Overall, I reckon I must
agree with your conclusions.

> Any output of a possibly concurrently running other CPace session
> could not provide any valuable input to the attacker.

Yes, it wouldn't do to be able to mess with the protocol by picking a
messages from several runs together. I confess I was too lazy to
seriously consider the possibility.

> The sid also serves for making each generator ephemeral for each
> session and this could be useful for mitigating side-channel analysis
> since the adversary has essentially only one single trace available.

Didn't think of the side channel.  A quick mention of that in the draft
could help.

> This "ephemeral generator G" feature that comes with the inclusion of
> the sid is IMO also relevant for the "quantum annoying" property.

Let's see… Perform discrete logarithm, guess G once, we can now compute
a working yb/Yb pair forever. Instead of "1 DLP per password guess", we
get "1 DLP per user". Not great indeed, good point.

> I have also tried to discuss this topic roughly in slides #53 to #58
> in [AuCPace presentation PDF]

The current draft does not match those slides.  The slides says *both*
parties should transmit a random string, and the sid is then a hash of
the two (or, if sid is always the input of a hash, they may be just
concatenated together?). The draft instead says:

""" If no such ssid is available from a higher-level protocol, a
""" suitable approach is including ssid in the first message from B to
""" A as shown in the figure below.

That may not be what you intended: with that method, the client is free
to repeat the sid, and the generator would now be only as ephemeral as
the x/X key pair.

If I may, the server *can* contribute to the sid without increasing the
number of messages:

    Client sends Csid, name, U
    Server sends Ssid, salt/UQ, X, sigma, Ya

    sid = H(Csid || Ssid)  -- safe
    sid =   Csid || Ssid   -- maybe that would work too?

Maybe for the next draft?

Loup.

---

From: Björn Haase <[email-masked]>
Date: Sat, 20 Jun 2020 01:17:52 +0200

Dear Loup,

 >The current draft does not match those slides. The slides says *both*

Yes. This is a change that came in in the final round of the selection
process after the feedback of Ran Canetti on this list regarding the sid
and the reviewers, together with the added full communication transcript.

> The parties should transmit a random string, and the sid is then a hash of

Yes, I am aware of this and this approach works for the AuCPace case and
what you describe is also what I had in mind when writing the slides of
the TCHES talk. I did focus on the full AuCPace there.

Unfortunately, this does not work as nicely for CPace, where the sid is
already required for the initiator's message.

It is true that if the CPace sid is chosen by the initiator alone, the
same generator could be re-used in several sessions. This aspect causes
a situation where we need to consider possible simulation problems in
the proof. Simulation would fail if the simulator needs to program the
RO to some specified value for an input that has previously been queried
in a different session. Fortunately, this problem does not show up in
the hash query H_1 of CPace where no such re-programming conflict
occurs. We could safely re-use the previously programmed value in later
sessions in the simulator. So this is not an issue for the security
proof, at least for a single-session setting.  Still after discussion
with others with more knowledge on UC than me, I think that this
"sid"-re-use aspect might generate some problems for a rigid proof for
*composability* in the joint-state setting. I believe that for CPace
with a single-side-generated sid, the UC security guarantees might not
rigidly cover composability (at least not without adaptions to the
model), so that the security guarantees fall back to a level comparable
to what one gets from the game-based models.

Note, however that for the setting where the sid is generated by one
side only, it is also very helpful to have the full transcript included
in the final hash. Having the transcript included makes sure that
re-programming problems for the simulator regarding the hash used for
the final session key could be ruled out (because ephemeral data from
both sides is included in form of Ya and Yb).

Yours,

Björn

---

From: Hugo Krawczyk <[email-masked]>
Date: Mon, 22 Jun 2020 11:01:30 -0400

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 )

Hugo

On Fri, Jun 19, 2020 at 12:34 PM Loup Vaillant-David <[email-masked]>
wrote:

> https://www.irtf.org/mailman/listinfo/cfrg
>

---

From: Dan Brown <[email-masked]>
Date: Mon, 22 Jun 2020 15:19:32 +0000

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 <[email-masked]> On Behalf Of Hugo Krawczyk
Sent: Monday, June 22, 2020 11:02 AM
To: Loup Vaillant-David <[email-masked]>; <[email-masked]> <[email-masked]>
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

>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=> 

Loup.

_______________________________________________
Cfrg mailing list
[email-masked] <mailto:[email-masked]> 
https://www.irtf.org/mailman/listinfo/cfrg <https://urldefense.proofpoint.com/v2/url?u=https-3A__www.irtf.org_mailman_listinfo_cfrg&d=DwMFaQ&c=yzoHOc_ZK-sxl-kfGNSEvlJYanssXN3q-lhj0sp26wE&r=qkpbVDRj7zlSRVql-UonsW647lYqnsrbXizKI6MgkEw&m=r1zeEz6DEF0-bdDU7a7UYsRe6vNvnWpEk4pzla6k_Ow&s=TnDdq0O8w7uMnPtXoYDGprqQPk_1YZfKPZTB-b4rv3o&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.

---

From: Loup Vaillant-David <[email-masked]>
Date: Mon, 22 Jun 2020 17:21:52 +0200

Hi Hugo,

Thank you so much for your response, it forced me to change my mind on
a couple points.

How using a primitive for several purposes was new to me. Now I need to
re-consider the design of Monokex, my Noise-like protocol framework
(Noise is amazing, but I felt it could be further simplified): both
framework use ephemeral keys as nonces. The Noise specifications
insists that no party shall send encrypted stuff before they mix their
own ephemeral key in the key mix.

Composition attacks also make my head hurt, so squashing them simply
with a session id sounds like a good safety belt, in case I design a
brittle protocol that would otherwise be vulnerable.

Loup.

On Mon, 2020-06-22 at 11:01 -0400, Hugo Krawczyk wrote:
> 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.pdfdf )
> 
> Hugo

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Mon, 22 Jun 2020 17:04:43 +0000

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 <[email-masked]> On Behalf Of Dan Brown
Sent: Monday, June 22, 2020 11:20 AM
To: Hugo Krawczyk <[email-masked]>; Loup Vaillant-David <[email-masked]>; <[email-masked]> <[email-masked]>
Subject: Re: [Cfrg] Using ephemeral DH in lieu of fresh nonces

Hi Hugo,

Best regards,
 
Dan

From: Cfrg <[email-masked]<mailto:[email-masked]>> On Behalf Of Hugo Krawczyk
Sent: Monday, June 22, 2020 11:02 AM
To: Loup Vaillant-David <[email-masked]<mailto:[email-masked]>>; <[email-masked]<mailto:[email-masked]>> <[email-masked]<mailto:[email-masked]>>
Subject: [Cfrg] Using ephemeral DH in lieu of fresh nonces

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

>>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=>

Loup.

_______________________________________________
Cfrg mailing list
[email-masked]<mailto:[email-masked]>
https://www.irtf.org/mailman/listinfo/cfrg<https://urldefense.proofpoint..com/v2/url?u=https-3A__www.irtf.org_mailman_listinfo_cfrg&d=DwMFaQ&c=yzoHOc_ZK-sxl-kfGNSEvlJYanssXN3q-lhj0sp26wE&r=qkpbVDRj7zlSRVql-UonsW647lYqnsrbXizKI6MgkEw&m=r1zeEz6DEF0-bdDU7a7UYsRe6vNvnWpEk4pzla6k_Ow&s=TnDdq0O8w7uMnPtXoYDGprqQPk_1YZfKPZTB-b4rv3o&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.

---

From: "Hao, Feng" <[email-masked]>
Date: Mon, 22 Jun 2020 17:20:49 +0000

Hi,

I want to second Dan that the use of nonce in a crypto protocol needs to be carefully justified, not just in a theoretical model, but considering the practical context as well. As a general principle, only items that are strictly necessary should be included in a protocol. Any small change, even though looking harmless at a glance, might be abused in some unintended way.

For example, in the Active Authentication protocol in the 1st generation of e-passport design, there is a subliminal attack that involves mis-using the nonce for tracing the movements of a passenger. This attack was not considered in the initial theoretical design as the nonce was assumed to be generated at random, but it can cause serious privacy concerns. This is one of the reasons that the AA protocol has been removed from the subsequent 2nd and 3rd generations of e-passport and is no longer recommended for implementation. The AA protocol has be replaced by BAC and later EAC (based on PACE) for chip authentication. The misuse of random data in BAC and EAC for the same privacy attack is still theoretically possible, but is much harder. More details about e-passport protocols can be found in [1].

In the post-Snowden era, if we wish to consider a state-funded attacker who may launch an algorithm substitution attack for mass surveillance (e.g., by substituting a legitimate crypto implementation in a tamper-resistant hardware module say HSM without anyone able to notice the change), many symmetric and public key algorithms that involve random factors have been shown to be potentially vulnerable, but the attacks are not always straightforward and often require heavy pre-computation. However, the use of a nonce together with an encrypted item or DH, will make the ASA attack really trivial. More details on ASA can be found in Bellare, Paterson and Rogaway, Crypto’14 [2].

With the examples above, I don’t mean to say a nonce shouldn’t be used, but we should be careful to justify the use of nonce is not only sufficient but also strictly necessary. Dan has actually already touched on these issues in his reply. I thought maybe it’s helpful to elaborate them a bit more as these issues are often overlooked.

[1] https://link.springer.com/chapter/10.1007/11908739_11
[2] https://eprint.iacr.org/2014/438

Cheers,
Feng

From: Cfrg <[email-masked]> on behalf of Dan Brown <[email-masked]>
Date: Monday, 22 June 2020 at 16:20
To: Hugo Krawczyk <[email-masked]>, Loup Vaillant-David <[email-masked]>, "<[email-masked]>" <[email-masked]>
Subject: Re: [Cfrg] Using ephemeral DH in lieu of fresh nonces

Hi Hugo,

Best regards,
 
Dan

Hugo

Loup.

---

From: Nico Williams <[email-masked]>
Date: Mon, 22 Jun 2020 14:00:53 -0500

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

Using ephemeral DH in lieu of nonces != re-using ephemeral DH in lieu...

> [...]

As others have said: to avoid the Dual_EC DRBG + extended nonce style of
in-band subliminal channel, nonces must be small or not be used at all.
Using ephemeral DH key agreement shared keys as nonces reduces the
freedom an implementation has to leak bits of PRNG state or keys
in-band.  Of course, there are lots of ways to leak bits in-band, and
even more out-of-band, so perhaps this should not be a concern.

> share and also as nonce/sessionid). This results in fragile protocols that

Key hygiene, sure.  Perhaps one can do an additional ephemeral DH key
agreement exchange for nonce agreement if this is an issue.  I hope the
nonce agreement need not be as strong / costly as the primary key
agreement.

> element may be changed "without remembering" that it had this other role.

This sort of thing can always happen.  We just have to write good docs.
We can't remove all footguns in crypto.  At some point we need to choose
between footguns to remove or keep.

> [...]

In this case you need to separate nonce agreement from key agreement,
but then you start wondering why reuse key agreement keys.  If it's for
key escrow, find a better way (encrypt the keys to the escrow agent and
send them there).  If dual use can produce a good reason (and pressure)
to never reuse keys, then dual use might be a good thing anyways.

Assuming no DH keypair reuse, is there a reason not to use DH key shared
keys as a sourc eof "nonces"?

> reasons for that) to send g^x only in the third message and you lose your

Nico
--

---

From: Dan Brown <[email-masked]>
Date: Mon, 22 Jun 2020 19:10:59 +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) <[email-masked]> 
Sent: Monday, June 22, 2020 1:05 PM
To: Dan Brown <[email-masked]>; Hugo Krawczyk <[email-masked]>; Loup Vaillant-David <[email-masked]>; <[email-masked]> <[email-masked]>
Subject: RE: [Cfrg] Using ephemeral DH in lieu of fresh nonces

From: Cfrg <[email-masked] <mailto:[email-masked]> > On Behalf Of Dan Brown
Sent: Monday, June 22, 2020 11:20 AM
To: Hugo Krawczyk <[email-masked] <mailto:[email-masked]> >; Loup Vaillant-David <[email-masked] <mailto:[email-masked]> >; <[email-masked] <mailto:[email-masked]> > <[email-masked] <mailto:[email-masked]> >
Subject: Re: [Cfrg] Using ephemeral DH in lieu of fresh nonces

Hi Hugo,

Best regards,

Dan

From: Cfrg <[email-masked] <mailto:[email-masked]> > On Behalf Of Hugo Krawczyk
Sent: Monday, June 22, 2020 11:02 AM
To: Loup Vaillant-David <[email-masked] <mailto:[email-masked]> >; <[email-masked] <mailto:[email-masked]> > <[email-masked] <mailto:[email-masked]> >
Subject: [Cfrg] Using ephemeral DH in lieu of fresh nonces

Hugo

Loup.

  _____

---

From: "Hao, Feng" <[email-masked]>
Date: Mon, 22 Jun 2020 22:45:48 +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 <[email-masked]> on behalf of Dan Brown <[email-masked]>
Date: Monday, 22 June 2020 at 20:12
To: "Scott Fluhrer (sfluhrer)" <[email-masked]>, Hugo Krawczyk <[email-masked]>, Loup Vaillant-David <[email-masked]>, "<[email-masked]>" <[email-masked]>
Subject: Re: [Cfrg] Using ephemeral DH in lieu of fresh nonces

Hi Scott,

Dan

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Mon, 22 Jun 2020 21:28:46 +0000

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 <[email-masked]>
Sent: Monday, June 22, 2020 3:11 PM
To: Scott Fluhrer (sfluhrer) <[email-masked]>; Hugo Krawczyk <[email-masked]>; Loup Vaillant-David <[email-masked]>; <[email-masked]> <[email-masked]>
Subject: RE: [Cfrg] Using ephemeral DH in lieu of fresh nonces

Hi Scott,

Dan

From: Scott Fluhrer (sfluhrer) <[email-masked]<mailto:[email-masked]>>
Sent: Monday, June 22, 2020 1:05 PM
To: Dan Brown <[email-masked]<mailto:[email-masked]>>; Hugo Krawczyk <[email-masked]<mailto:[email-masked]>>; Loup Vaillant-David <[email-masked]<mailto:[email-masked]>>; <[email-masked]<mailto:[email-masked]>> <[email-masked]<mailto:[email-masked]>>
Subject: RE: [Cfrg] Using ephemeral DH in lieu of fresh nonces

From: Cfrg <[email-masked]<mailto:[email-masked]>> On Behalf Of Dan Brown
Sent: Monday, June 22, 2020 11:20 AM
To: Hugo Krawczyk <[email-masked]<mailto:[email-masked]>>; Loup Vaillant-David <[email-masked]<mailto:[email-masked]>>; <[email-masked]<mailto:[email-masked]>> <[email-masked]<mailto:[email-masked]>>
Subject: Re: [Cfrg] Using ephemeral DH in lieu of fresh nonces

Hi Hugo,

Best regards,
 
Dan

Hugo

Loup.

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=>