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

[Björn Haase <[e-mail]>]

Hello Filippo,

 

thank you for asking.

 

Yes. We made progresses.

 

Today we have submitted the proceedings version of the security analysis paper to asiacrypt. We are now finishing the full paper of version for the eprints. The full paper will include a game based security proof. The comparison of the simulation based and game based analysis will highlight the specific requirements on the sid.

 

Our plan is to have it online on the eprints next friday and then incorporate the results into the RFC draft.
 

Yours,

 

Björn

 

 

Gesendet: Sonntag, 19. September 2021 um 22:29 Uhr
Von: "Filippo Valsorda" <[e-mail]>
An: [e-mail]
Betreff: Re: [CFRG] On the properties of sid in CPace

Hi all,

 

Has there been any progress on this?

 

If I read the diff correctly, draft-irtf-cfrg-cpace-02 has not changed

the recommendation for sid selection. Has a proof emerged for the

protocol with initiator-selected sid?

 

Thank you,

Filippo

 

2021-04-15 13:59 GMT+02:00 Filippo Valsorda <[e-mail]>:

2021-04-15 07:46 GMT+02:00 Julia Hesse <mailto:juliahesse2%40gmail.com" target="_blank" rel="nofollow">[e-mail]>:

Hi Filippo,

 

 

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

once per password?

 

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.

 

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.

 

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.

 

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!

 

 

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.

 

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

 

 

 

 

 

 

 

 

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

 

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

 

2021-04-12 21:51 GMT+02:00 Julia Hesse <mailto:juliahesse2%40gmail.com" target="_blank" rel="nofollow">[e-mail]>:

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/" target="_blank" rel="nofollow">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 

single-session key exchange? Let me try to answer some of your questions:

 

>

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

>

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 

> unpredictable?

>

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

 

_______________________________________________

CFRG mailing list

mailto:CFRG%40irtf.org" target="_blank" rel="nofollow">[e-mail]

https://www.irtf.org/mailman/listinfo/cfrg" target="_blank" rel="nofollow">https://www.irtf.org/mailman/listinfo/cfrg

 

 

 

_______________________________________________
CFRG mailing list
[e-mail]
https://www.irtf.org/mailman/listinfo/cfrg" target="_blank" rel="nofollow">https://www.irtf.org/mailman/listinfo/cfrg

 

_______________________________________________

CFRG mailing list

mailto:CFRG%40irtf.org" target="_blank" rel="nofollow">[e-mail]

https://www.irtf.org/mailman/listinfo/cfrg" target="_blank" rel="nofollow">https://www.irtf.org/mailman/listinfo/cfrg

 

 

 

_______________________________________________
CFRG mailing list
[e-mail]
https://www.irtf.org/mailman/listinfo/cfrg" target="_blank" rel="nofollow">https://www.irtf.org/mailman/listinfo/cfrg

 

_______________________________________________

CFRG mailing list

mailto:CFRG%40irtf.org" target="_blank" rel="nofollow">[e-mail]

https://www.irtf.org/mailman/listinfo/cfrg" target="_blank" rel="nofollow">https://www.irtf.org/mailman/listinfo/cfrg

 

 

_______________________________________________

CFRG mailing list

[e-mail]

https://www.irtf.org/mailman/listinfo/cfrg" target="_blank" rel="nofollow">https://www.irtf.org/mailman/listinfo/cfrg

 

 

_______________________________________________ CFRG mailing list [e-mail] https://www.irtf.org/mailman/listinfo/cfrg" target="_blank" rel="nofollow">https://www.irtf.org/mailman/listinfo/cfrg