[Cfrg] SIDs in UC-secure PAKE and KE

["Canetti, Ran" <[e-mail]>]

Dear CFRG:


Apologies for the long message.


There seems to be some confusion in some CFRG postings regarding the role
of the session identifiers in the UC framework. In particular I believe it
was stated that in order for a PAKE (or more generally a KE) protocol to be
eligible to be considered UC secure, the protocol must involve an initial
round where the involved parties agree on a session identifier (SID) to be
used in the actual PAKE/ KE protocol, and I've been asked to clarify.

So, in short: This is not the case!

To give a more meaningful clarification, let me start with some background.
The basic computing unit in the UC model (which I'll refer to here as a
"machine") represents some computational process within some
computer/cluster/principal/party. Each machine has an identity string. The
identity is fixed throughout the lifetime of the machine. Each machine can
create, during its execution, multiple other machines; when a new machine
is created, the creating machine sets the identity of the created machine
to some value, according to the program of the creating machine.  It is up
to the creator machine to set the identities appropriately. Machine
identities can be just nonces, sequence numbers, or be more sophisticated
(eg public keys). Machines have access to their own identity, but the
identities are in essence a tool for the creator machine to tell the
created ones apart.

To facilitate delineating individual “protocol instances” within a larger
system, the UC framework further sub-partitions the identity of a machine
to a session identifier (SID) and "the rest" (called party identifier, or
PID). Session s of protocol \pi at a certain moment in an execution of a
system is then defined to be the set of machines whose program is \pi and
whose SID is s. This allows for a relatively simple-yet-expressive
definition of protocol instances in dynamically changing systems.

[To avoid modeling ambiguity, the framework prohibits having two machines
with the same identity and program. but there are simple mechanisms to
"hide" this fact from the protocol being analyzed. That is, it is possible
to represent and analyze protocols that assume that identities and codes
are repeatable, if one insists...]

Let me describe how hese conventions can play out in the modeling of KE (or
PAKE) protocol, in two different modeling styles. First let me describe the
simpler, single-session modeling of KE. Here a session of the KE protocol
corresponds to a single exchange of a key:

 1. First, the "application machine" within the initiator of the exchange
(say, an HTTPS machine, or perhaps a “secure channel machine” that was
created by the HTTPS machine), creates a new machine whose code is the code
of the single-instance KE protocol, where the SID and PID of the newly
created machine are set by the application machine, and where the KE
machine is given the identity of the responder as input. Let (sid,Init) be
the sid and pid of the initiator KE machine, and let Resp be the identity
of the responder.

2. The initiator KE machine (let’s call it (sid,Init,KE) ) sends a message
to the responder KE machine (sid,Resp,KE). As a result, a new  machine
(sid,Resp,KE) is created.

 [I'm a bit cheating here, since the initiator machine doesn’t send
messages directly to the responder. The communication goes via some channel
machine, and then via the adversary, but never mind that. Also, if for some
reason the machine (sid,Resp,KE) already exists in the system, then the
message will be routed to it. If the protocol is designed correctly than
this will only happen due to adversarial intervention and so the exchange
should fail in this case.]

 3. The initiator and responder KE machines now exchange messages (via the
adversary). They may also contact other machines, such as a PKI service, a
signing module, a hashed-password repository, etc. At some point, the
initiator KE machine sends output to its caller, namely the initiator
application machine. This output will contain the sid, the session key, and
potentially other parameters

4. At another point, the responder KE machine generates output to some
other machine, as its code instructs. That other machine can represent,
say, the application machine (eg, the secure channel or HTTPS process
within the responder).

So here, we have an instance of a KE protocol, that consists of two
machines (sid,init,KE) and (sid,Resp,KE), and where there is no other
communication in the system other than the actual protocol messages between
the two KE machines (possibly altered by the adversary). The only thing
that's required is that the initiator KE machine be able to communicate the
SID that was determined by its caller, via the protocol messages, to the
responder KE machine. whenever transmitting the sid fails, the exchange
should fail.

In essence, the SID mechanism provides a link that starts at the
application machine within the initiator, threads through the two KE
machines, and ends at the application machine within the responder. It
provides a way for the two endpoints to link the session with other
concurrent stuff that is going on at the two endpoints in a globally
consistent way.


A second way to model KE protocols is to have a single session of a KE
protocol handle multiple exchanges of a key among multiple parties. To
avoid confusion, let me call this primitive MKE. This formulation is a bit
more cumbersome, but it can be useful as a tool to analyze protocols that
“generate their own SIDs”. That is, protocols where there is no SID value
that was given by the initiator calling machine to the initiator KE
machine, and that also appears in the output of the responder KE machine,
but on the other hand each exchanged key is associated with a public
non-repeating identifier. Here execution will proceed as follows:

1. There is a single, global “sid” * for MKE that all use. (That is, all
participants will use the same long-lived instance of MKE.)

2. At setup of each “principal” (pid), the principal starts its own
long-lived MKE machine with identity (*,pid).

3. To initiate the exchange of a key, the application machine (say, HTTPS,
or a multi-session secure channels machine) within the initiator calls
(MKE,*,Init) with input (Resp, lid). (Here Init is the pid of the
initiator, Resp is the pid of the responder, and lid is a “local
identifier” between the application machine and MKE.)

4. The machine (MKE,*,Init) interacts (via the adversary) with the machine
(MKE,*,Resp) within the responder. At some point (MKE,*,Init) outputs to
the initiator application machine some value (lid, s, k), where lid is the
local identifier, s is a session id generated by MKE, and k is the session key.

5. At another point, (MKE,*,Resp) outputs to the recipient application
machine the value (lid’,s,k) where lid’ is a local value within the
responder, and s and k are the same as above.

It should be noted that the value s is not a “formal UC sid”, but it still
provides a link that threads from the application machine within the
initiator to the application machine within the responder.

So when is going the KE way better and when is going the MKE way better?
Clearly, KE is easier to handle from the point of view of specification and
 analysis. Otoh, in situations where one wants to analyze an existing
protocol whose structure does not allow for a convenient KE modeling (as
appears to be the case for TLS1.*), one’s hands are clearly tied. But are
there additional considerations? Or situations where one might be
preferable to the other? (It’s an honest question, perhaps people on the
list might have some insight.)

Happy to further clarify if needed.


Best,


Ran