Subject: [CFRG] On the properties of sid in CPace

From: "Filippo Valsorda" <[email-masked]>
Date: Mon, 12 Apr 2021 01:43:00 +0200

Hi all,

I am trying to figure out the required properties of sid in CPace, and what
happens in various attack and misuse scenarios.

This is what draft-irtf-cfrg-cpace-01 says about sid, if I didn't miss anything:

   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.

   Prior to entering the protocol, A and B agree on a sid string. sid is
   typically pre-established by a higher-level protocol invocing CPace.
   If no such sid is available from a higher-level protocol, a suitable
   approach is to let A choose a fresh random sid string and send it to
   B together with Ya.

   Upon completion of this protocol, the session key ISK returned by A
   and B will be identical by both parties if and only if the supplied
   input parameters sid, PRS and CI match on both sides and the
   information on the public elements in J were not modified by an
   adversary.

Overall, it's not described as particularly different from CI (it's public, and
the output is tied to it), but sid is hashed into both the generator and into
the key material, while CI is not:

   G = map_to_group_mod_neg(DSI1 || PRS || ZPAD || sid || CI)

   ISK = H(DSI2 || sid || Ks || Yas || Ybs)

Last year there was a brief but very useful discussion about the sid ([Cfrg]
CPACE: what the "session id" is for?) with arguments for its importance, but I
still have a few questions. (Some excerpts from that thread below.)

First, how does the security of CPace degrade upon sid reuse? If it were to
happen due to birthday bounds, how catastrophic would it be?

What happens if the sid can be attacker-controlled between two otherwise honest
peers which both know the password?

Is uniqueness its only requirement, or does it also have to be unpredictable?

> the sid could be considered as to form some sort of "glue" linking the
> individual subblocks of the composed protocol

Isn't that what the additional data in CI is for? Is placing binding values in
CI less effective than placing them in the sid?

If I were to use CPace in a network protocol such as TLS, my instinct would be
to use a transcript hash as CI. Assuming the protocol negotiated random values
and identities, would that be enough or would I also need to hoist sid and
identities out and into the explicit CPace parameters?

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

Does this work with an A-generated sid? It looks like an attacker could force B
to keep operating on the same generator in that case.

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

Is "quantum annoyingness" lost if only one side contributes to the sid? Is it
lost upon a single sid reuse?

I'm not arguing for removing the sid at all, but I think CPace as a low-level
primitive should provide a tool that is easy to reason about with clear rules
and properties, so documenting the expectations for the sid would help.

Thank you,
Filippo

P.S. This is the first time I see UTF-8 used as a general purpose variable
length integer encoding. I think I love it. However, it's likely UTF-8 libraries
will behave weirdly and most importantly differently around 0xFFFD, invalid
encodings, and surrogate pairs, which I can see causing trouble.

---

From: Julia Hesse <[email-masked]>
Date: Mon, 12 Apr 2021 21:51:05 +0200

Dear Filippo,

thank you for opening this topic, which certainly needs discussion. I 
planned to write about sid establishment in general for a while, so I'm 
happy you are finally forcing me :) First, let me try to 
complement/structure some prior information given on this list about 
session identifiers in UC.

 From the side of UC, there are 2 requirements on the sid of a protocol 
(for the purpose of this email, it's okay to think of a 2-party key 
exchange protocol):
  (1) uniqueness
  (2) known in advance
Both properties are assumptions made by the UC framework, which is why 
protocols formulated in UC terminology never check uniqueness of the sid 
given to them. It is simply an assumption, meaning that it is not 
possible to model protocol executions with session identifiers are not 
unique or not known in advance. As Ran explained here 
[https://mailarchive.ietf.org/arch/msg/cfrg/fgwMYLfaa1ZbF_UgKcurse211KE/], 
he chose these mechanisms for the proper modeling of interactive 
processes in dynamic systems.

Okay. But who choses sid's, and how?

Combining both properties, for a two-party protocol our options are 
essentially as follows:
(1) sid is given as input to initiator, the responder obtains the sid 
with the initiator's first message and outputs it to the application.
(2) sid is given as input to both parties.
In both cases, the application needs to ensure uniqueness of the sid for 
proven UC guarantees to hold even if the protocol is executed multiple 
times. For (2), one could let both parties contribute their own 
randomness in an interactive protocol that is run *as part of the 
application*. A non-interactive way is to let both parties' application 
processes derive a unique sid from the application's session's values, 
e.g. sid=(IP-A,IP-B,application-transcript). There might be ways to 
nicely integrate such sid establishment into application protocols 
(e.g., TLS or HTTPS) by piggybacking messages etc., but they all exploit 
properties of the specific application protocol. What I want to say is 
that, imo, there is no way of telling what the best sid establishment 
methods for CPace or OPAQUE are without considering the concrete 
application protocols.

If we want to provide and analyze an application-independent method for 
session identifier establishment, we need to switch to a multi-session 
version of, e.g., key exchange (as hinted by Ran in his post already). A 
practical example of such a multi-session protocol is the DH key 
exchanges within TLS1.3 (essentially, all of them, seen as one single 
protocol execution that runs since the deployment of TLS1.3). Since this 
protocol is started only once and runs during the lifetime of TLS1.3, we 
can simply set sid=DHKE_TLS1.3. In this protocol, it is up to the 
parties to keep track of and distinguish their different attempts to 
exchange keys. Thus, any multi-session key exchange protocol will have 
to incorporate a mechanism to establish unique joint identifiers 
(``sub-session identifiers'') whenever two parties want to exchange a key.

What does this mean for CPace, which is analyzed and drafted as a 

> peers which both know the password?
No need to invoke the birthday bound, as it happens already when the 
responder accepts any sid proposed by a malicious initiator (who can of 
course also play man-in-the-middle with same sid on both sides). Note 
that we are now kind of outside the UC model for single-session CPace, 
since in UC sid re-use "merges" CPace instances, while in reality we can 
have different CPace executions with same sids.

To answer your question formally, one would need to consider CPace as 
multi-session protocol. If this protocol has a built-in mechanism to 
keep parties from running different key exchanges with matching sids, I 
would bet that we can just use the same simulation strategy as in 
single-session CPace, to simulate each subsession. If such mechanism is 
missing, it seems the current proof strategy cannot be lifted to 
multiple sessions: it breaks down upon re-use of sid for a pair of 
parties P,P' exchanging two keys from same passwords. The individual 
simulation strategies for those exchanges would attempt to program the 
password hash function at the same point (sid,P,P',pw) to different 
values, and thus fail.

This of course does not imply that there is a meaningful attack on the 
multi-session protocol level (a protocol that has not even been 
specified yet), nor that the conducted single-session proof is flawed. 
It does however suggest that method (1), which is also used in the 
current version of the draft, is not the best choice for single-session 
CPace.

> Is uniqueness its only requirement, or does it also have to be 
The proof of CPace does not rely on unpredictability. Of course, 
unpredictability could help ensuring uniqueness in a setting where 
multiple single-session CPace executions are spread in a distributed 
system that does not have any other mean for ensuring uniqueness.

Best
Julia

---

From: "Filippo Valsorda" <[email-masked]>
Date: Tue, 13 Apr 2021 05:23:12 +0200

Hi Julia,

Thank you for the thorough explanation of how the UC framework
assumptions work!

Do I understand correctly that, in summary, an initiator-selected sid
does not meet the uniqueness requirement, so the CPace proof does not
cover the protocol currently specified in the draft?

There are real world uses for an initiator-selected sid, as it enables
0.5RTT data, so it would be really nice if the proof could be extended.

In the meantime, it sounds like CPace should only run after unique
values (such as random values with comfortable birthday bounds) have
been negotiated from both sides, as I can't think of any other way to
provide such a strong uniqueness guarantee.

>From a protocol engineering point of view, I find it more comfortable
to think in terms of transcripts, and not have to worry about how sid,
identities, and additional data might have different properties and
requirements, so I would suggest the following variant

    G = map_to_group_mod_neg(DSI1 || PRS || ZPAD || transcript1)

    ISK = H(DSI2 || Ks || transcript2) [should there be a ZPAD after Ks?]

where transcript1 MUST include unique values from both sides, and
transcript2 MUST include transcript1, Yas, and Ybs.

(This implies sending Yas and Ybs on the wire, which raises the question
of why the current draft sends Ya and Yb instead. Sending something
different from what's hashed in the transcript seems like asking for
trouble. Of course none of this would matter for a proper prime order
group such as ristretto255...)

Besides being IMHO clearer about how to integrate in a protocol, this
variant has two other advantages: it encourages the use of transcripts
even further, and it eliminates the difference between CI and sid, which
is still not clear to me.

What do you think?

Cheers,
Filippo

2021-04-12 21:51 GMT+02:00 Julia Hesse <[email-masked] <mailto:juliahesse2%40gmail.com>>:
> _______________________________________________
> CFRG mailing list
> [email-masked] <mailto:CFRG%40irtf.org>
> https://www.irtf.org/mailman/listinfo/cfrg
>

---

From: Julia Hesse <[email-masked]>
Date: Tue, 13 Apr 2021 11:38:32 +0200

Hi Filippo,

> cover the protocol currently specified in the draft?
If the protocol from the draft is used to exchange multiple keys, then 
non-uniqueness of sid's yields a setting that cannot be covered by the 
(any) single-session proof plus the composability guarantees of UC. As I 
said before, it's simply outside the model: while sid collisions in the 
model never happen because then colluding processes are merged to a 
single one, a real execution would could have *different* runs of CPace 
with the same sid.

It urgently needs to be clarified in the draft whether it proposes only 
a one-time protocol, and if not under which conditions (i.e., on sid) it 
can be executed multiple times.

> 0.5RTT data, so it would be really nice if the proof could be extended.
The only way I see to make the initiator-chosen sid work is to give the 
responder means to check uniqueness. That is of course annoying, as we 
don't want to burden parties with long-term state in an otherwise 
stateless protocol.
> provide such a strong uniqueness guarantee.

I agree. Although I really hope that I am wrong in all this and somebody 
chimes in to tell me :)
> transcript2 MUST include transcript1, Yas, and Ybs.

I have to side with Hugo here: we need to be careful not to obfuscate by 
assigning more than one reason to a design choice. Ya and Yb are key 
shares and we should not at the same time use them as nonces. If we need 
nonces for security reasons, we should introduce them to the protocol. 
(Obviously, I'm more on the theory side of crypto, so introducing nonces 
for more security makes me happy.)

> is still not clear to me.
Quick question: what is the difference between Ya and Yas here?

Thanks for the proposal! We are currently in the process of reviewing 
the contents of the draft, including revisiting the roles of 
DSI,CI,sid,party identifiers etc., and we will take your proposal into 
account.

Best,
Julia

>> [https://mailarchive.ietf.org/arch/msg/cfrg/fgwMYLfaa1ZbF_UgKcurse211KE/ 
>> <https://mailarchive.ietf.org/arch/msg/cfrg/fgwMYLfaa1ZbF_UgKcurse211KE/>], 
>>
>> <https://www.irtf.org/mailman/listinfo/cfrg>
>>
>
>
> [email-masked]

---

From: "Filippo Valsorda" <[email-masked]>
Date: Tue, 13 Apr 2021 13:56:16 +0200

2021-04-13 11:38 GMT+02:00 Julia Hesse <[email-masked] <mailto:juliahesse2%40gmail.com>>:
> If the protocol from the draft is used to exchange multiple keys, then non-uniqueness of sid's yields a setting that cannot be covered by the (any) single-session proof plus the composability guarantees of UC. As I said before, it's simply outside the model: while sid collisions in the model never happen because then colluding processes are merged to a single one, a real execution would could have *different* runs of CPace with the same sid.
> 
> It urgently needs to be clarified in the draft whether it proposes only a one-time protocol, and if not under which conditions (i.e., on sid) it can be executed multiple times. 

When you say a "one-time protocol", does that mean executing it only
once per password?

> The only way I see to make the initiator-chosen sid work is to give the responder means to check uniqueness. That is of course annoying, as we don't want to burden parties with long-term state in an otherwise stateless protocol. 
> 
> I agree. Although I really hope that I am wrong in all this and somebody chimes in to tell me :)
> 
>> 
> I have to side with Hugo here: we need to be careful not to obfuscate by assigning more than one reason to a design choice. Ya and Yb are key shares and we should not at the same time use them as nonces. If we need nonces for security reasons, we should introduce them to the protocol. (Obviously, I'm more on the theory side of crypto, so introducing nonces for more security makes me happy.)

Oh, I am not suggesting using Ya and Yb as nonces, like in the original
thread. I am firmly on the engineering side, so if you folks are not
comfortable with it I am not going to mess with it :) I think my
suggestion is the same from a theoretical point of view, and if it isn't
I am failing to understand or explain something.

What I'm saying is that currently any implementer or higher level
protocol designer needs to figure out the difference between sid,
identities, and additional data, and match them with parts of their
protocol. My suggestion doesn't remove or repurpose anything, it just
rewords everything in terms of a protocol transcript and what it must
include.

Instead of hashing sid and CI into G, and maybe the transcript into CI,
it says to hash the whole transcript, and that it must include unique
values from both sides, which means it includes the sid. Then instead
of hashing sid, Yas, and Ybs into ISK, it says to again hash the whole
transcript, which at this point will include the sid values from before
CPace was run, and Yas and Ybs. Yas and Ybs are in transcript2 because
they are already in the draft, not to replace sid.

> Quick question: what is the difference between Ya and Yas here?

Yas = strip_sign_information(Ya)

It's the x or u coordinate without the sign bit for the other coordinate.

> Thanks for the proposal! We are currently in the process of reviewing the contents of the draft, including revisiting the roles of DSI,CI,sid,party identifiers etc., and we will take your proposal into account. 
> 
> Best,
> Julia
> 
> 
>> What do you think?
>> 
>> Cheers,
>> Filippo
>> 
CFRG mailing list

---

From: Julia Hesse <[email-masked]>
Date: Thu, 15 Apr 2021 07:46:49 +0200

Hi Filippo,

> When you say a "one-time protocol", does that mean executing it only
it depends on whether the protocol uses the isolated sid or not. E.g., 
in case it always uses sid,P,P' (where P,P' are identifiers of the two 
participants), the current security analysis seems to hold for one 
execution per pair of identifiers. That means you and I could exchange 
at most one key. Of course, we do not want such restrictions for the 
draft. All I'm saying in this thread is that the current security 
analysis does not support more executions if sids are initiator-chosen.

Related note: the UC model, and therefore all security analyses of 
CPace, assume that these party identifiers are known on both sides. 
However, this might be impractical for some applications. Let's say we 
recommend in the draft to choose identifiers as strings IP:PORT. 
Consider a setting where my computer runs two processes, one called AUTH 
handling authentication requests, and one called MAIN handling 
everything else, for example network communication. While I would assume 
that implementors can adapt the AUTH process to work with CPace, they 
may not be able to touch the MAIN process. If MAIN internally rewrites 
IP:PORT pairs to another identifier PID1, then we are suddenly in a 
situation where both ends of CPace do not have any joint understanding 
of how they call themselves.
To summarize: you are very right in being worried about loading 
implementors with instantiating the various CPace parameters. As I said, 
we are working on simplifications. For example, we are currently looking 
into completely removing party identifiers from hashes in the security 
analysis, such that we can change some parameters in the draft to be 
optional.

> they are already in the draft, not to replace sid.

Ah, sorry for my misunderstanding. What you propose would clearly 
simplify, but I don't feel able to discuss this without knowing the 
exact requirements for all the parameters in the draft,e.g., how they 
map to the parameters used in the security analysis. Let me get back to 
you when we are at that point.

Best,
Julia

>> DSI,CI,sid,party identifiers etc., and we will take your proposal 
>> into account.
>>
>> Best,
>> Julia
>>
>>
>>> What do you think?
>>>
>>> Cheers,
>>> Filippo
>>>
>>> [email-masked]  <mailto:[email-masked]>
>>> https://www.irtf.org/mailman/listinfo/cfrg  <https://www.irtf.org/mailman/listinfo/cfrg>
>>>
>>

---

From: "Filippo Valsorda" <[email-masked]>
Date: Thu, 15 Apr 2021 13:59:39 +0200

Hi Julia,

Oh, so if I understand correctly one execution means one per identities
pair, which makes sense, thank you.

Looking forward to hearing if you can get past that restriction, and
thank you for walking me through it.

> analysis, such that we can change some parameters in the draft to be 

Indeed, this is why I opened this thread in the first place: I was
trying to get a better sense of how to map protocols (where we rarely
have access to stable, shared, and unique identities) to CPace
parameters. I am glad to hear you are working on it!

CFRG mailing list

CFRG mailing list