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

Julia Hesse <> Mon, 12 April 2021 19:51 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 6F25D3A14BB for <>; Mon, 12 Apr 2021 12:51:19 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.849
X-Spam-Status: No, score=-1.849 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, NICE_REPLY_A=-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 NU51x0HDBNXe for <>; Mon, 12 Apr 2021 12:51:15 -0700 (PDT)
Received: from ( [IPv6:2a00:1450:4864:20::433]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id EC86C3A14B9 for <>; Mon, 12 Apr 2021 12:51:14 -0700 (PDT)
Received: by with SMTP id a6so14160341wrw.8 for <>; Mon, 12 Apr 2021 12:51:14 -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:content-transfer-encoding; bh=m3viZt8aLEPk2e7kZMM7cDXcydbSH87wZgYpz1rP2qU=; b=mz+KsQsXCFAnFlI889EzbN3c8OGf63Ry+V0HZxFAwkC/W4hHzeGRGksujdGcQ1v61L DmKdrgF+lRb9C+0Jy8/xbgvpynWAKz9QS0nwXWIvoOag9cL2HG9iB20MhOtyy49NsBhY DW90L1eJ6E7LakkgNIOW27ElJnZtTC0n0s4qoFYofk/hL8/0ATgcxcJrsKPZXEoirTCs eynqXdzlkx9B68DRrDg2YROw6LufOz7fD9gXqHRXCEyAD6AYnXyVjzfB/yLGBXwEOf6H AREgOLs5PXF2UsD/wapfaaS3KSq3t6b/UvkYINGxTDAUNvPEbnX8evi6ixYhdRBE4OT9 m+vQ==
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:content-transfer-encoding; bh=m3viZt8aLEPk2e7kZMM7cDXcydbSH87wZgYpz1rP2qU=; b=kabFm8E8KbSCWynQk9zRy/1P5Fw86Fu1vlc78/Lkm7flzgWmDjoRABPlw3Vwfhvw4s NKuFUZXK4s3fily8BekHFnneIqSMpOulRIgGjytS4kFbFRkmp5AYtmGQI04ChfXr+psB jOxMVu9TArw6Kqmleb27HV4NIo2L6HADumcXd9BhTLhyb3DmLWSfpvvilclyQ39xYed2 VKOJilbUpP9mmNVO1/2zfvltt2UvHN/JZatxKmgXKzK+tVp7qOyhO24S+sBG0XYT/cCg Wt8fSXKU7dNJ6NGzdpW05BOySH94vuKvGDSC3BgwLFuN5fPFiv7T3StqDj/IE/V5tcUN zs5g==
X-Gm-Message-State: AOAM531PzC6xnpFuq2ubB78OWQ6bvlQhAEo4UkEVlYxbt9TwSyMCGs1N KR2gtvemALy5RfuD9+B1KXc=
X-Google-Smtp-Source: ABdhPJxVitcBxhoManFJyM34gh/d4RvbWsBZQpN0IS4p0JYPdU0scynbuExbmYY3D4y5okJAAL3E9A==
X-Received: by 2002:a5d:51c6:: with SMTP id n6mr26896000wrv.230.1618257068234; Mon, 12 Apr 2021 12:51:08 -0700 (PDT)
Received: from ?IPv6:2a02:aa12:a780:5480:7982:80fc:8561:83da? ([2a02:aa12:a780:5480:7982:80fc:8561:83da]) by with ESMTPSA id f8sm347587wmc.8.2021. (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Mon, 12 Apr 2021 12:51:07 -0700 (PDT)
References: <>
From: Julia Hesse <>
Message-ID: <>
Date: Mon, 12 Apr 2021 21:51:05 +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: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
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: Mon, 12 Apr 2021 19:51:19 -0000

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 

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