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

Julia Hesse <> Tue, 13 April 2021 09:38 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 5E6EE3A0DF9 for <>; Tue, 13 Apr 2021 02:38:42 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.847
X-Spam-Status: No, score=-1.847 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_ENVFROM_END_DIGIT=0.25, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, NICE_REPLY_A=-0.001, RCVD_IN_DNSWL_BLOCKED=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (2048-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id vSrQi7CdeMcM for <>; Tue, 13 Apr 2021 02:38:37 -0700 (PDT)
Received: from ( [IPv6:2a00:1450:4864:20::632]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 8FAF93A0DF3 for <>; Tue, 13 Apr 2021 02:38:36 -0700 (PDT)
Received: by with SMTP id v6so23573689ejo.6 for <>; Tue, 13 Apr 2021 02:38:36 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=subject:references:from:to:message-id:date:user-agent:mime-version :in-reply-to; bh=ybgZtft74qCB1rO8l41bjWQ8aBFc9BEs5j8r48TWwN4=; b=BR3RitJ7Idbxxq2VfS6+0PNppg/C3knYu7VCqDQavBsTO8Oc+QNoQsedn2Gb4f8bGW vkBoSshWxHsEdyaDHXk0Ro+ELFiTCHvjYLpdNchtRrvVOuyxb1ATE7ezhHInT9ibgv8t PqOAAV3+FHIjeov0a+O/cI1LUhpU2Hv32jG2qYl3gL9IVYFlZVt0PvErWYAQ5AA2uOi/ v1vw7SBX/KU40ppG8c2iNZlXGuuVIqYweX7kQwN+ZUdUxSpn2bLY1cBc7/3tIczQtlGa 5asL38Rim5s1OiAQxSla4s4kJjA4lvA6XjLBIOCMjza2H2d7Bl6SePpbmYO5IKFTbQWk 72FA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=x-gm-message-state:subject:references:from:to:message-id:date :user-agent:mime-version:in-reply-to; bh=ybgZtft74qCB1rO8l41bjWQ8aBFc9BEs5j8r48TWwN4=; b=i9vcWalBc6hrfMp5SRBMhX19SuO1ojQN8igwht9DIruRsegT8JQ12Tu4YwyRcmeyYy eDemhpXJnS/SadXkg9H1ygKp6hVHSnFNGdlnZWroKOqdMOrinAXxiNP2a0FO+QP6fmse cK033pRkg7Kbrip2dk2Ngl3MB7mn+C0SIeVDTXG/REkK8PwK8XwSugbfm8TX1js44EHv yc2oxf95B9zNszppBALdLUcKCCyQ82TLTlyURjzyH+pi/qGwcC40fUc6TBDYHclXpric ch1Wow79xYxbsQzDHG/Nn0DocxrIqKuGHbQv38/ByV4jlyLu7J5rgcaqf7WSdYIcbwO2 Vo5A==
X-Gm-Message-State: AOAM533ytMYPI2H1IPE0fHycneUUPtQzOezjillvqKCBzf5t69S3obqZ Q5dRgCG0xzInRXLCAMFYLeE=
X-Google-Smtp-Source: ABdhPJxVnjriKusfyoJ60VZsgKq/Y5YKYsCrlFx5qDs0LXDoD3gPewFDZ4aqdcU07O7jMF4IhHnnIw==
X-Received: by 2002:a17:906:6703:: with SMTP id a3mr30797437ejp.240.1618306714369; Tue, 13 Apr 2021 02:38:34 -0700 (PDT)
Received: from ?IPv6:2a02:aa12:a780:5480:299b:9cf5:8dba:b821? ([2a02:aa12:a780:5480:299b:9cf5:8dba:b821]) by with ESMTPSA id y21sm8769761edv.31.2021. (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 13 Apr 2021 02:38:33 -0700 (PDT)
References: <> <> <>
From: Julia Hesse <>
Message-ID: <>
Date: Tue, 13 Apr 2021 11:38:32 +0200
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101 Thunderbird/78.9.1
MIME-Version: 1.0
In-Reply-To: <>
Content-Type: multipart/alternative; boundary="------------63F611645239F6E493A78071"
Archived-At: <>
Subject: Re: [CFRG] On the properties of sid in CPace
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Tue, 13 Apr 2021 09:38:42 -0000

Hi Filippo,

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

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

I agree. Although I really hope that I am wrong in all this and somebody 
chimes in to tell me :)
> 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.

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

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

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 


> What do you think?
> Cheers,
> Filippo
> 2021-04-12 21:51 GMT+02:00 Julia Hesse < 
> <>>:
>> 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
>> [ 
>> <>], 
>> 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
>> <>
>> <>
> _______________________________________________
> CFRG mailing list