Cryptographic Choreographies Sebastian Mödersheim, Simon Lund, Alessandro Bruni, Marco Carbone, Rosario Giustolisi Abstract We present CryptoChoreo, a choreography language for the specification of cryptographic protocols. Choreographies can be regarded as an extension of Alice-and-Bob notation, providing an intuitive high-level view of the protocol as a whole (rather than specifying each protocol role in isolation). The extensions over standard Alice-and-Bob notation that we consider are non-deterministic choice, conditional branching, and mutable long-term memory. We define the semantics of CryptoChoreo by translation to a process calculus. This semantics entails an understanding of the protocol: it determines how agents parse and check incoming messages and how they construct outgoing messages, in the presence of an arbitrary algebraic theory and non-deterministic choices made by other agents. While this semantics entails algebraic problems that are in general undecidable, we give an implementation for a representative theory. We connect this translation to ProVerif and show on a number of case studies that the approach is practically feasible. Acknowledgments: Partly funded by EU Horizon Europe under Grant Agreement no. 101093006 (TaRDIS). I Introduction Specification languages for security protocols can be roughly divided into three classes. The most low-level one are based on multi-set rewriting rules, such as the Tamarin input language [ 19 ] and the AVISPA Intermediate Format [ 2 ] , where each rule describes state transitions corresponding usually to a pair of protocol steps from the view of one honest agent: receiving a message, processing and checking it, and sending the next message. More high-level are languages based on process calculus such as ProVerif [ 6 ] , where typically each role of the protocol is described like a program, often as a sequence of sending and receiving steps. The most high-level are languages based on Alice-and-Bob notation [ 20 , 18 , 15 , 21 , 12 , 1 , 3 ] , which describe the entire protocol by an ideal run of the protocol as a sequence of A\rightarrow B:M steps where role A sends message M to role B , thus describing the interplay of all roles. Alice-and-Bob notation is very intuitive and succinct because it gives the synopsis of the protocol and leaves implicit how agents construct the messages they send, and how they parse and check the messages they receive. The latter is a non-trivial problem one has to solve when defining a formal language based on Alice-and-Bob notation, namely when giving a formal semantics by translation to a lower-level language. This was described by [ 15 , 7 ] for models in the free term algebra, but a key question is how to deal with algebraic properties as needed, for instance, for Diffie-Hellman. If Alice needs to construct \exp(\exp(g,X),Y) , given her own secret X and the public value \exp(g,Y) from Bob, the semantics needs to infer that this is possible by composing \exp(\exp(g,Y),X) since this is equivalent to the goal term by the algebraic properties of exponentiation. It turns out that one can define such semantics in a general, uniform, and concise way for an arbitrary algebraic theory as an intruder deduction problem [ 21 , 12 , 1 , 3 ] As a side-effect of “abusing” the intruder deduction to define the behavior of honest agents, one prevents many specification errors that can easily happen in the lower-level formalisms, e.g., when the message sent by one agent are different from the messages that another agent expects, rendering the protocol unexecutable. This may lead in the worst case to a false negative (an attack of the real system is not detected because of a specification error). Many such errors are prevented by formal Alice and Bob approaches because the protocol would be refused as unexecutable by the compiler. Thus, Alice-and-Bob notation is a beneficial and accessible specification language that can be used even without a deep background in formal verification. It is also striking how often scientific works that formalize a protocol using a lower-level language first summarize the protocol informally in Alice-and-Bob notation. However, existing formal Alice-and-Bob languages do not support branches in the protocol execution (by conditions or non-determinism), unbounded repetition, or mutable long-term memory: everything is restricted to a linear session of fixed length. While informal uses of Alice-and-Bob notation can easily be extended ad hoc, the first main contribution of this paper is a new choreography language, called CryptoChoreo , which extends Alice-and-Bob notation with non-deterministic choice, branching, and mutable long-term memory. 1 1 1 Since a choreography can be executed an unbounded number of times, non-determinism and long-term memory are sufficient to formulate repetitions and sequential composition of protocols without an explicit repetition construct. Such features are needed for instance if we want to formulate a protocol with a server that maintains a long-term database and that may react to a request in different ways depending the current state of its database. Non-deterministic choice can be helpful for modelling several options in a protocol that are at a participant’s discretion, where we do not want to formalize how they make a decision. Especially this allows us to formulate an API where a user can non-deterministically choose to send any of a number of commands to a server (who may in turn ask other servers in order to answer the request). CryptoChoreo is, in a sense, a conservative extension of formal Alice-and-Bob languages: we give a semantics—parameterized over an arbitrary algebraic theory—that agrees with standard Alice-and-Bob languages on the subset that does not use the new constructs. A particular challenge for this semantics is to integrate the algebraic understanding of the protocol with branching: if one party has made a non-deterministic choice, other parties do not necessarily know which choice was taken. For instance, our semantics allows for the following protocol: Alice non-deterministically chooses one of two types of message that she sends encrypted for Bob over an intermediary server as an authentication service; the server is unaware in which branch the execution is, but in each case it can execute its step uniformly by checking a MAC from Alice and signing the resulting message. The semantics is formulated as a translation to local behaviors, i.e., a process for each role of the protocol. In general, this involves algebraic problems that are not recursively computable (since, e.g., whether two terms are equal under a set of algebraic equations is in general undecidable). The second main contribution is to give a computable translation for an algebraic theory that includes standard constructors and destructors as well as exponentiation (for Diffie-Hellman). As a third contribution, we connect our translator with ProVerif and demonstrate the effectiveness of our approach with several case studies. A particular challenge is that ProVerif’s abstraction often is not precise enough when the long-term memory induces non-monotonic behavior (e.g., when a certain action is possible only until a change of the memory state) and thus fails to verify a protocol. We have developed several heuristics to make sound encodings in ProVerif that often overcome these problems. The rest of this paper is organized as follows: in Section II we define the syntax of CryptoChoreo and give example; in Section III we define the semantics for an arbitrary algebraic theory; in Section IV , we describe the practical implementation for a representative algebraic theory; in Section V we describe the connection to ProVerif and our case studies; and we conclude in Section VI . II Choreography Language \begin{array}[]{l@{\;\!}l}\!\mathsf{A}:&(\nu M.\\ &\mathsf{A}\rightarrow\mathsf{s}:\mathit{scrypt}((\mathsf{B},{\color[rgb]{0,0,1}\mathit{crypt}((\mathit{msg},M),\mathit{ek}(\mathsf{B}))}),\mathit{shk}(\mathsf{A},\mathsf{s})).\\ &\mathsf{s}\rightarrow\mathsf{B}:\mathit{sign}((\mathsf{A},{\color[rgb]{0,0,1}\mathit{crypt}((\mathit{msg},M),\mathit{ek}(\mathsf{B}))}),\mathit{inv}(\mathit{sk}(\mathsf{s}))).\\ &\mathsf{B}~\mathsf{ni\text{-}authenticates}~\mathsf{A}~\mathsf{on}~M)\\ +&(\nu K.\\ &\mathsf{A}\rightarrow\mathsf{s}:\mathit{scrypt}((\mathsf{B},{\color[rgb]{0,0,1}\mathit{crypt}((\mathit{upd},K),\mathit{ek}(\mathsf{B}))}),\mathit{shk}(\mathsf{A},\mathsf{s})).\\ &\mathsf{s}\rightarrow\mathsf{B}:\mathit{sign}((\mathsf{A},{\color[rgb]{0,0,1}\mathit{crypt}((\mathit{upd},K),\mathit{ek}(\mathsf{B}))}),\mathit{inv}(\mathit{sk}(\mathsf{s}))).\\ &K~\mathsf{secret~between}~\mathsf{A},\mathsf{B})\end{array} Fig. 1: Example Choreography. Let us start with the example choreography in Fig. 1 . We discuss later the front-matter declarations (e.g., types and initial knowledge) that is needed for a full specification. Role \mathcal{A} is starting the choreography and first makes a non-deterministic choice ( + ) about which of the two sub-choreographies to run. In the first case, \mathsf{A} generates a new random M (representing a message to send to \mathsf{B} ) together with a constant tag \mathit{msg} (indicating that this is a message transmission), then asymmetrically encrypts it with the encryption key \mathit{ek}(\mathsf{B}) , highlighted in blue. \mathsf{A} then symmetrically encrypts the blue message and the name of \mathsf{B} with a shared key \mathit{shk}(\mathsf{A},\mathsf{s}) with the (trusted) server \mathsf{s} . Suppose only \mathsf{B} knows the decryption key \mathit{inv}(\mathit{ek}(\mathsf{B})) , then \mathsf{s} can only decrypt the outer symmetric encryption, but not the blue message. The next step is that \mathsf{s} signs the blue message and the sender name \mathsf{A} using the private signature key \mathit{inv}(\mathit{sk}(\mathsf{s})) ; the idea is that \mathsf{s} is vouching that the blue message really came from \mathsf{A} (as the symmetric encryption guarantees to \mathsf{s} ) and \mathsf{B} can verify the signature knowing the corresponding public signing key \mathit{sk}(\mathsf{s}) . Finally, we have an authentication goal when \mathsf{B} receives this message: namely, that \mathsf{A} has indeed intended to send the message M to \mathsf{B} . Non-injective ( \mathsf{ni} in \mathsf{ni\text{-}authenticates} ) here means that \mathsf{B} has no freshness guarantee (the message may be a replay). The other sub-choreography is very similar, except that here \mathsf{A} sends a different kind of message, a key update with a fresh key K with a different goal: K is secret between \mathsf{A} and \mathsf{B} (of course both sub-choreographies could have a secrecy and an authentication goal). Each of the two sub-choreographies could be specified in existing formal Alice-and-Bob languages, but not the non-deterministic choice. Note that \mathsf{s} here does not realistically know which sub-choreography was chosen by \mathsf{A} . The semantics we give below sorts this out correctly: the server shall do the same operations in both choreographies and simply handle the blue message as a black box. Note that an intruder playing role \mathsf{A} is also allowed; and this intruder may form a blue message that complies with neither sub-choreography; \mathsf{s} will anyway accept this message if everything it can check complies with the protocol. Terms We build terms using an alphabet \Sigma of function symbols and a set of variables \mathcal{V} . We denote all function symbols with lower-case letters and all variables with upper-case letters. In the above example, e.g., \mathit{scrypt} , \mathit{shk} , \mathit{inv} , \mathit{msg} , and \mathsf{s} are function symbols (constants are function symbols with 0 arguments), while \mathsf{A} and M are variables. Variables mean that they can take a different value in every run of the choreography. We use sans-serif font to denote roles of the protocol; they can be variables like \mathsf{A} and \mathsf{B} or constants like \mathsf{s} . The latter means that there is one fixed player who cannot be the intruder—an easy way to specify a trusted third party. We will discuss below the specification of function symbols and their algebraic properties. We also use the notation (t_{1},\ldots,t_{n}) for a concatenation using a pair operator. \small\begin{array}[]{rcl@{\;\;}l}\mathcal{C}&::=&\mathbf{0}&\text{(end)}\\ &\mid&\mathsf{A}\rightarrow\mathsf{B}:t.\,{\mathcal{C}}&\text{(interaction)}\\ &\mid&t~\mathsf{secret~between}~\mathsf{A}_{1},\ldots,\mathsf{A}_{n}.\mathcal{C}&\text{(secrecy goal)}\\ &\mid&\mathsf{B}~\mathsf{authenticates}~\mathsf{A}~\mathsf{on}~t.\mathcal{C}&\text{(inj. auth. goal)}\\ &\mid&\mathsf{B}~\mathsf{ni\text{-}authenticates}~\mathsf{A}~\mathsf{on}~t.\mathcal{C}&\text{(non-inj. auth. goal)}\\ &\mid&\mathsf{A}:\mathcal{A}&\text{(atomic)}\\ \\ \mathcal{A}&::=&\nu N.\;\mathcal{A}&\text{(new)}\\ &\mid&\mathcal{A}_{1}+\mathcal{A}_{2}&\text{(choice) }\\ &\mid&\mathsf{if}~s\doteq t~\mathsf{then}~\mathcal{A}_{1}~\mathsf{else}~\mathcal{A}_{2}&\text{(condition)}\\ &\mid&s:=c[t].\mathcal{A}&\text{(memory read)}\\ &\mid&c[t]:=s.\mathcal{A}&\text{(memory write)}\\ &\mid&\mathcal{C}&\text{(choreography)}\end{array} Fig. 2: Syntax of CryptoChoreo. Syntax The formal syntax of a choreography is shown in Fig. 2 . A choreography \mathbf{0} represents a terminated protocol, in which each participant has terminated. We omit trailing \mathbf{0} s when this is clear from the context. An interaction \mathsf{A}\rightarrow\mathsf{B}:t.\,{\mathcal{C}} denotes a protocol where \mathsf{A} sends a term t to \mathsf{B} and then continues with choreography \mathcal{C} . The next items represent the specification of goals (injective and non-injective authentication, and secrecy) that we discuss later in detail. All these constructs are present in existing formal Alice-and-Bob languages. What CryptoChoreo is adding are constructs that are all local to one role. Denote this by giving a role name \mathsf{A} followed by a colon and an atomic section \mathcal{A} of steps that \mathsf{A} locally executes. Here, we have the fresh generation of a random value \nu N (as is standard). Next, we have the non-deterministic choice \mathcal{A}_{1}+\mathcal{A}_{2} (this is actually an internal choice for the role who runs this atomic section and an external choice for all others). Then, we have a conditional where the condition is a comparison of terms. Last, we have reading from, and writing to, long-term memory. We denote with c[t] a memory cell in a family of memory cells c , where c is an identifier and t is an index term. On memory read and write, there will be no race conditions with other parallel sessions, because our semantics will treat each section \mathcal{A} as atomic like the name suggests. Memory Cell Example To illustrate memory, consider the following augmentation shown in 3 of the example in Fig. 1 , where \mathsf{A} may not know the encryption key of every \mathsf{B} (but just the public signature verification key \mathit{sk}(\mathsf{s}) of \mathsf{s} ). When \mathsf{A} wants to talk to \mathsf{B} , she checks her memory cell \mathit{keys}[\mathsf{B}] ; if this returns the initial value \mathit{blank} , then she does not know the key of \mathsf{B} and asks \mathsf{s} , which we assume knows all public encryption keys via the \mathit{ek} function and can vouch for it with its signature. \mathsf{A} checks the signature and stores the key (note that for \mathsf{A} the term \mathit{ek}(\mathsf{B}) is just a blob that she cannot verify itself; this will be shown in the semantics below). \begin{array}[]{ll}\mathsf{A}:&\mathit{EKB}:=\mathit{keys}[\mathsf{B}].\\ &\mathsf{if}~\mathit{EKB}\doteq\mathit{blank}~\mathsf{then}\\ &\quad\nu N.\,\mathsf{A}\rightarrow\mathsf{s}:(\mathit{key},\mathsf{B},N)\\ &\quad\mathsf{s}\rightarrow\mathsf{A}:\mathit{sign}((\mathit{key},\mathsf{B},\mathit{ek}(\mathsf{B}),N),\mathit{inv}(sk(\mathsf{s})))\\ &\quad A:\mathit{keys}[\mathsf{B}]:=\mathit{ek}(\mathsf{B})\\ &\mathsf{else}\ldots\text{(previous example with $\mathit{ek}(\mathsf{B})\mapsto{\mathit{EKB}}$)}\end{array} Fig. 3: Extension of the example from Fig. 1 . Note that we do not have a repetition operator, and this example shows why this is without loss of generality: in the case that \mathsf{A} does not know the key of \mathsf{B} , the run of the choreography ends with writing the key (that she received from \mathsf{s} ) into her memory. Thus, in any later run between the same \mathsf{A} and \mathsf{B} , \mathsf{A} will retrieve the key from her memory and run the standard protocol with it. In other words, unbounded repetition is implicit, because a choreography can be executed any number of times (also in parallel) with arbitrary instances of the (non-constant) roles and information between different runs can be transfered using memory. Front Matter The definition of our choreography language is parameterized over sets \Sigma and \mathcal{V} (respectively, function symbols and variables) and a set of equations E (over \Sigma,\mathcal{V} -terms). The set E induces a congruence relation =_{E} on terms. In the implementation of our translation, in Section IV , we instantiate E with a concrete choice of properties. Some variables and functions symbols are declared as roles (set in sans-serif in this paper) and only these can be used in places where the syntax indicates sans-serif font. For each role, one must declare the initial knowledge : a list of terms where all occurring variables are of type role. For our example (in the augmented version where \mathsf{A} does not initially know \mathsf{B} ’s public key), this declaration could be: \begin{array}[]{ll}\mathsf{A}:&\mathsf{A,B,s,\mathit{sk}(s),\mathit{shk}(A,s)}\\ \mathsf{s}:&\mathsf{A,B,s,\mathit{sk}(s),\mathit{inv}(\mathit{sk}(s)),\mathit{shk}(A,s),\mathit{ek}(B)}\\ \mathsf{B}:&\mathsf{A,B,s,\mathit{sk}(s),\mathit{ek}(B),\mathit{inv}(\mathit{ek}(B))}\end{array} Note that with less knowledge the protocol would not be executable (neither for the initial version of the example where \mathsf{A} cannot ask the server for \mathsf{B} ’s public key). We require that for every variables that is not of type role, the first occurrence is either in a new statement (like \nu X ) or in a memory read (like X:=c[s] ). Also, in a new statement \nu X , we assume that X did not occur before in the choreography (this can be achieved by renaming). In contrast, variables in a memory read may have occurred before, e.g., \nu X.\ldots X:=c[s_{1}].\ldots X:=c[s_{2}] is legal, and it would mean that the value retrieved here is the same value as before—in an ideal unattacked execution of the choreography. Our semantics can tell if the respective role has the necessary knowledge to check that and insert such a check in the code, if so. III Translation Semantics The semantics of CryptoChoreo is now defined by a translation to a process calculus, where we define for each role of the choreography a process, representing the local behavior of this role in one execution of the choreography. We then allow arbitrary instances of all roles to run in parallel, together with an intruder who can also play any of the roles (except trusted third parties) as a normal participant (but who does not necessarily follow the protocol). III-A Local Behaviors \small\begin{array}[]{rcl@{\qquad}l}\mathcal{L}&::=&\mathbf{0}\hfil\hskip 18.49988pt&\text{(end)}\\ &\mid&\mathsf{send}(r).\mathcal{L}_{i}\hfil\hskip 18.49988pt&\text{(send)}\\ &\mid&\mathsf{receive}(\mathcal{X}).\mathcal{L}\hfil\hskip 18.49988pt&\text{(receive)}\\ &\mid&\mathsf{lock}.\mathcal{A}\hfil\hskip 18.49988pt&\text{(atomic local)}\\ \\ \mathcal{A}&::=&\nu\mathcal{X}.\,\mathcal{L}\hfil\hskip 18.49988pt&\text{(new)}\\ &\mid&\mathcal{A}_{1}+\mathcal{A}_{2}\hfil\hskip 18.49988pt&\text{choice}\\ &\mid&\mathsf{if}~r_{1}\doteq r_{2}~\mathsf{then}~\mathcal{A}_{1}~\mathsf{else}~\mathcal{A}_{2}\hfil\hskip 18.49988pt&\text{(cond)}\\ &\mid&\mathcal{X}:=c[r_{1}].\mathcal{A}\hfil\hskip 18.49988pt&\text{(mem read)}\\ &\mid&c[r_{1}]:=r_{2}.\mathcal{A}\hfil\hskip 18.49988pt&\text{(mem write)}\\ &\mid&\mathsf{event}(r).\mathcal{A}\hfil\hskip 18.49988pt&\text{(event)}\\ &\mid&\mathsf{unlock}.\mathcal{L}\hfil\hskip 18.49988pt&\text{(end)}\end{array} Fig. 4: Syntax of Local Behaviors. It is convenient for the translation and the later connection to ProVerif to define a restricted syntax and semantics for local behaviors as the target language of the translation semantics. Syntax The syntax of local behaviors mirrors that of CryptoChoreo from the point of view of a single role: instead of a communication step between two roles, we have now sending and receiving. We use here however a different set of symbols \Sigma_{p} which represent public functions, i.e., functions that every agent, including the intruder, can apply. This will include most of the functions from \Sigma like \mathit{crypt} that represent cryptographic algorithms and as well as public constants like \mathit{msg} in the example above. It will not include however some functions from \Sigma that just describe relations in the model, but do not represent actual cryptographic algorithms like \mathit{inv} (which maps public keys to the corresponding private key) or \mathit{ek} (which maps an agent to a corresponding public key). \Sigma_{p} will also include some functions that are not in \Sigma : observe that we have not used any functions for decryption or signature verification, because they are destructors or verifiers , i.e., functions that extract a subterm or verify the structure of a term; while the choreography is only concerned with constructed messages. Also, we will use a distinct set of variables called labels . Labels are denoted \mathcal{X}_{1},\mathcal{X}_{2},\ldots and are disjoint from \Sigma , \Sigma_{p} , and \mathcal{V} . The terms built from these variables and \Sigma_{p} are called recipes and we denote them with r , r_{1} , r_{2} , etc. Fig. 4 shows the syntax of local behaviors. Note that, in order to enter the atomic section, it is necessary to make a \mathsf{lock} step and it has to end with an \mathsf{unlock} step; the semantics of local behaviors use that as a mutual exclusion mechanism on the memory to prevent race conditions (even if one ensures by design that each memory cell belongs to a particular agent, there may be more than one run of the choreography in parallel). The other constructs are similar to choreographies. However, instead of variables like M we have now labels like \mathcal{X} , and instead of terms (over \Sigma and \mathcal{V} ) we have recipes. Note that memory read and receiving can only “read into” a label \mathcal{X} (while on the choreography level, these can be composed terms). We require that at each receive and memory read, we use a new label (that did not occur before in the local behavior; this can be easily achieved by renaming). Frames To capture the knowledge of an honest agent at a state of protocol execution, we define a frame to be a finite mapping F=[\mathcal{X}_{1}\mapsto t_{1},\ldots,\mathcal{X}_{n}\mapsto t_{n}] where the X_{i} are labels and the t_{i} are terms. We call \{\mathcal{X}_{1},\ldots,\mathcal{X}_{n}\} the domain of F and we say F is concrete if the t_{i} contain no variables. The semantics of local behaviors will only use concrete frames. Given a recipe r , we use a frame F like a substitution and write F(r) for the term that results from replacing the labels \mathcal{X}_{i} with the respective term t_{i} ; F(r) is undefined if r contains labels outside the domain of F . To each role \mathsf{A} , we attach an initial knowledge frame F_{\mathsf{A}} that is not necessarily concrete but contains only variables of type role. In the translation from CryptoChoreo to local behaviors, we take the initial knowledge of each role \mathsf{A}:t_{1},\ldots,t_{n} at the CryptoChoreo level and turn into an initial knowledge frame F_{\mathsf{A}}=[\mathcal{X}_{1}\mapsto t_{1},\ldots,\mathcal{X}_{n}\mapsto t_{n}] for the local behavior. We require that all labels in a local behavior first occur in the initial knowledge frame, in a new, in a receive, or in a memory read. Example Local Behavior The role \mathsf{A} of the example of Fig. 3 will be translated by the semantics into the following local behavior: {\hskip-8.53581pt\begin{array}[]{l}F_{\mathsf{A}}=[\mathcal{X}_{1}\mapsto\mathsf{A},\mathcal{X}_{2}\mapsto\mathsf{B},\mathcal{X}_{3}\mapsto\mathsf{s},\mathcal{X}_{4}\mapsto\mathit{sk}(\mathsf{s}),\mathcal{X}_{5}\mapsto\mathit{shk}(\mathsf{A},\mathsf{s})]\\ \mathsf{lock}.\mathcal{X}_{K}:=\mathit{keys}[\mathcal{X}_{2}].\\ \mathsf{if}~\mathcal{X}_{K}\doteq\mathit{blank}~\mathsf{then}\\ \quad\nu\mathcal{X}_{N}.\mathsf{unlock}.\mathsf{send}((\mathit{key},\mathcal{X}_{2},\mathcal{X}_{N})).\\ \quad\mathsf{receive}(\mathcal{X}_{kc}).\mathsf{lock}.\\ \quad\mathsf{if}~(\mathit{vsign}(\mathcal{X}_{kc},\mathcal{X}_{4})=\top)~\mathsf{then}\\ \qquad\mathsf{let}~(\mathcal{X}_{t},\mathcal{X}_{B},\mathcal{X}_{K^{\prime}},\mathcal{X}_{N^{\prime}})=\mathit{open}(\mathcal{X}_{kc})~\mathsf{in}\\ \qquad\mathsf{if}~(\mathcal{X}_{t}\doteq\mathit{key}\wedge\mathcal{X}_{B}=\mathcal{X}_{2}\wedge\mathcal{X}_{N^{\prime}}=\mathcal{X}_{N})~\mathsf{then}\\ \qquad\quad\mathit{keys}[\mathcal{X}_{2}]:=\mathcal{X}_{K^{\prime}}.\mathsf{unlock}.0\\ \qquad\mathsf{else}~\mathsf{unlock}.0\\ \quad\mathsf{else}~\mathsf{unlock}.0\\ \mathsf{else}~...~\text{translation of the other part, using $\mathcal{X}_{K}$ as $\mathit{ek}(\mathsf{B})$}\end{array}} Here, we use some syntactic sugar: several checks can be done by one condition; and that we write let for parsing the content of a message, in this case expecting that it can be parsed into a quadruple. The function \mathit{vsign} is supposed to be signature verification with the property \mathit{vsign}(\mathit{sign}(m,\mathit{inv}(k)),k)=_{E}\top and open a destructor that yields the signed message, i.e., \mathit{open}(\mathit{sign}(m,\mathit{inv}(k)))=m . This models a signature scheme where the signed text is transmitted in plain along with a signed hash, i.e., one needs the public key only for signature verification. One can also observe that between each \mathsf{lock} and \mathsf{unlock} there is at most one memory read or write, so locking is in this case actually redundant as it does not prevent any race conditions. \begin{array}[]{l}(0\uplus L,F,\mu)\to(L,F,\mu)\\ (\mathsf{send}(r).\mathcal{L}\uplus L,F,\mu)\to(\mathcal{L}\uplus L,F[\mathcal{X}\mapsto r],\mu)\\ \quad\text{ where $\mathcal{X}$ is a fresh label}\\ (\mathsf{receive}(\mathcal{X}).\mathcal{L}\uplus L,F,\mu)\to(\mathcal{L}[\mathcal{X}\mapsto F(r)]\cup L,F,\mu)\\ \quad\text{ where $r$ is a recipe over the domain of }F\\ (\mathsf{lock}.\mathcal{A}\uplus L,F,\mu)\stackrel{{\scriptstyle\mathit{tr}}}{{\to}}(\mathcal{L}\uplus L,F,\mu^{\prime})\\ \quad\text{ if }(\mathcal{A},\mu)\stackrel{{\scriptstyle\mathit{tr}}}{{\Rightarrow^{*}}}(\mathsf{unlock}.\mathcal{L},\mu^{\prime})\\ (L,F,\mu)\to(\sigma(F_{\mathsf{A}})(\mathcal{L}_{\mathsf{A}})\uplus L,F,\mu)\\ \quad\text{if $\sigma$ is a an honest instantiation of a role $F_{\mathsf{A}}:\mathcal{L}_{\mathsf{A}}$,}\\ (L,F,\mu)\to(L,F\uplus\sigma(F_{\mathsf{A}}),\mu)\\ \quad\text{if $\sigma$ is a dishonest instantiation of a role $F_{\mathsf{A}}:\mathcal{L}_{\mathsf{A}}$}\\ \quad\text{and where the labels of $F_{\mathsf{A}}$ have been freshly renamed}\\ \\ (\nu\mathcal{X}.\,\mathcal{A},\mu)\Rightarrow(\mathcal{A}[\mathcal{X}\mapsto n],\mu)\text{ where $n$ is a fresh constant}\\ (\mathcal{A}_{1}+\mathcal{A}_{2},\mu)\Rightarrow(\mathcal{A}_{i},\mu)\text{ if }i\in\{1,2\}\\ (\mathsf{if}~r_{1}\doteq r_{2}~\mathsf{then}~\mathcal{A}_{1}~\mathsf{else}~\mathcal{A}_{2},\mu)\Rightarrow(A_{1},\mu)\text{ if }r_{1}=_{E}r_{2}\\ (\mathsf{if}~r_{1}\doteq r_{2}~\mathsf{then}~\mathcal{A}_{1}~\mathsf{else}~\mathcal{A}_{2},\mu)\Rightarrow(A_{2},\mu)\text{ if }r_{1}\neq_{E}r_{2}\\ (\mathcal{X}:=c[r_{1}].\mathcal{A},\mu)\Rightarrow(\mathcal{A}[\mathcal{X}\mapsto\mu(c,r_{1})],\mu)\\ (c[r_{1}]:=r_{2}.\mathcal{A},\mu)\Rightarrow(\mathcal{A},\mu[(c,r_{1})\mapsto r_{2}])\\ (\mathsf{event}(r).\mathcal{A},\mu)\stackrel{{\scriptstyle r}}{{\Rightarrow}}(\mathcal{A},\mu)\end{array} Fig. 5: Semantics of Local Behaviors. Semantics of Local Behaviors We give a simple operational semantics for a set of local behaviors F_{\mathsf{A}_{1}}:\mathcal{L}_{\mathsf{A}_{1}},\ldots,F_{\mathsf{A}_{n}}:\mathcal{L}_{\mathsf{A}_{n}} (where each F_{\mathsf{A}_{i}} is the initial knowledge frame of \mathsf{A}_{i} ). We assume a set \mathit{Ag}\subseteq\Sigma\cap\Sigma_{p} of public constant of type role and that \mathsf{i}\in\mathit{Ag} represents a dishonest agent (‘‘intruder’’) while all other agents are honest. 2 2 2 One may well consider more than one dishonest agent, but for simplicity we work with just one. For a behaviour F_{\mathsf{A}}:\mathcal{L}_{\mathsf{A}} we call the substitution \sigma an instantiation if it maps all variables in F_{\mathsf{A}} (that are by definition of type role) to elements of \mathit{Ag} . We say it is a dishonest instantiation if \sigma(\mathsf{A})=\mathsf{i} and an honest instantiation otherwise. We write \sigma(F_{\mathsf{A}}) for the instantiation of the initial knowledge frame and \sigma(F_{\mathsf{A}}(\mathcal{L}_{\mathsf{A}})) for the instantiation of the behavior itself, replacing all labels from F_{\mathsf{A}} in \mathcal{L}_{\mathsf{A}} by ground terms; thus all remaining labels first occur at a new, at a receive, or at a memory read. The last ingredient for the semantics is a memory map \mu that maps every memory cell c[(t)_{E}] gives a value, initially \mathit{blank} , where (t)_{E} is the =_{E} -equivalence class of a ground term t over \Sigma . As easy notation we just write \mu(c,t) for this value, and we write \mu[(c,t)\mapsto t^{\prime}] for changing the memory cell c[(t)_{E}] to value t^{\prime} . The semantics of local behaviour is defined in Fig. 5 and consists of two transition relations \to and \Rightarrow that call each other: \to is on triples (L,F,\mu) where L is a multi-set of local behaviors, F is a frame representing the intruder knowledge and \mu is the memory map; the initial state is (\emptyset,[],\mu_{0}) where \mu_{0} maps everything to \mathit{blank} ; \Rightarrow is on tuples (\mathcal{A},\mu) where \mathcal{A} is an atomic section of a local behavior. We decorate the transition relations with a list of events that occurred upon the transitions. In this semantics, the intruder is the network: every message an honest agent sends gets added into the intruder knowledge, and every message an honest agent receives comes from the intruder knowledge: the intruder can choose any recipe over their knowledge, which includes encrypting and decrypting with known keys. An atomic section is handled literally atomically using the \Rightarrow relation locally at an agent until it hits the \mathsf{unlock} ; we label the transition with the trace \mathit{tr} of all events that the agent emitted. The next rule allows to spawn new instances any role \mathsf{A} : we choose any instantiation \sigma of the variables in F_{\mathsf{A}} with agent names; if \sigma is honest, i.e., \sigma(\mathsf{A})\neq i , we apply the instantiated knowledge \sigma(F_{\mathsf{A}}) as a substitution to the local behavior \mathcal{L}_{\mathsf{A}} , leaving only labels that are introduced by new, receive, and memory read. This semantics allows running an arbitrary number of sessions in parallel and sequentially. If \sigma is dishonest, i.e., \sigma(\mathsf{A})=i then this represents that the intruder plays role \mathsf{A} under the actual name i . This models a dishonest/compromised agent. We give the intruder the initial knowledge needed to play the role, i.e., \sigma(\mathcal{F}_{\mathsf{A}}) where we have to rename the labels in the frame to avoid a clash with labels in the present intruder knowledge. III-B Projection: The Semantics of CryptoChoreo We can now give the semantics of CryptoChoreo by translation to local behaviors. We again use frames to represent the knowledge of a role at a given point in the translation, but this differs from their use in the local behavior semantics. As said, the messages in a choreography represent how messages look like in an “ideal” or unattacked run—which may differ from the shape of messages in a real run due to interference from the attacker. For instance if \mathsf{A} is supposed to receive \exp(g,Y) from \mathsf{B} for a secret Y that \mathsf{A} does not know, there is nothing that \mathsf{A} can check about this message. To keep track of this during translation we make an entry [\mathcal{X}_{i}\mapsto\exp(g,Y)] in the frame F of \mathsf{A} that expresses: \mathsf{A} has received some message \mathcal{X}_{i} and according to the choreography it is supposed to be \exp(g,Y) . Given that another entry [\mathcal{X}_{j}\mapsto X] represents the fresh value \mathsf{A} has created for her own secret X , then the Diffie-Hellman key \exp(\exp(g,X),Y) can be formed with the recipe r=\exp(\mathcal{X}_{i},\mathcal{X}_{j}) : F(r)=\exp(\exp(g,Y),X)=_{E}\exp(\exp(g,X),Y) . In this way, frames make the connection between the messages the agents have and use in their local behavior and what the messages supposedly are on the choreography level. We will use this to figure out how agents generate outgoing messages and how they analyze incoming messages. We thus define two core algorithmic problems on frames: • The deduction problem: Given frame F and term t , compute a recipe r such that F(r)=_{E}t if one exists or return fail otherwise. • The complete check problem: Given a frame F , compute a finite set of checks , i.e., equations of recipes \phi=\{r_{1}\doteq r_{1}^{\prime},\ldots,r_{n}\doteq r_{n}^{\prime}\} such that F(r_{i})=_{E}F(r_{i}^{\prime}) for each 1\leq i\leq n , that is complete in the sense that if for any other r_{0},r_{0}^{\prime} we have F(r_{0})=_{E}F(r_{0}^{\prime}) , then \phi\models_{E}r_{0}\doteq r_{0}^{\prime} , or return fail if no finite set of checks satisfies that. 3 3 3 We use standard logical notation: an interpretation \mathcal{I} maps all the variables to terms; define \mathcal{I}\models_{E}s\doteq t if \mathcal{I}(s)=_{E}\mathcal{I}(t) ; we extend this definition to sets of equations; \phi\models_{E}\psi if for all \mathcal{I}\models_{E}\phi also \mathcal{I}\models_{E}\psi . Both these problems are in general not recursively computable (because in general even =_{E} is undecidable), but in Section IV we give algorithms for both problems for a standard set E of equations. We first note a complete set of checks for F is not unique, however if \phi and \psi are two complete set of checks for F , then \phi\models_{E}\psi and \psi\models_{E}\phi , so they are equivalent and in the semantics we can leave this choice undetermined 4 4 4 Thus a concrete implementation is free to choose one. without making the semantics ambiguous. By abuse of notation we thus write \phi(F) for a complete set of checks for F , even though it is strictly speaking not a function. Second, also the deduction problem has in general many solutions, i.e., different r_{1} and r_{2} such that F(r_{1})=_{E}F(r_{2})=_{E}t . (This does generally not imply that r_{1}=_{E}r_{2} : we may have different ways in knowledge F to produce a particular term t .) However, in this case \phi(F)\models_{E}r_{1}\doteq r_{2} , i.e., if we have performed all the checks in \phi(F) , then also the choice between the two recipes r_{1} and r_{2} does not matter. Third, in the semantics, we need a slight generalization of the deduction problems, namely given several frames F_{1},\ldots,F_{n} and goal terms t_{1},\ldots,t_{n} and we want a single recipe r that solves all deduction problems, i.e., F_{i}(r)=t_{i} for every 1\leq i\leq n . Suppose we already have a set \phi of checks that is a complete set of checks for each of the F_{i} , and suppose there is a solution r for all frames. Then any solution r^{\prime} for one of the frames, say F_{1} , must be equivalent to r , i.e., \phi\models_{E}r\doteq r^{\prime} . Thus for checked frames it suffices to compute a solution for one frame and check if it works on the other frames—if not, then there is no common solution for all frames. Nondeterminism and conditions mean that, in general, a role does not know which branch of the choreography we currently are in, and this also holds during the translation. Therefore, during in the translation, the translation state contains a finite set of pairs (F_{i}:\mathcal{C}_{i}) where each F_{i} is a frame (all F_{i} have the same domain) and \mathcal{C}_{i} is the remainder of the choreography that still needs to be translated. Definition 1 . A translation state is of the form (\mathsf{A},\phi\triangleright\psi,b,\{(F_{1}:\mathcal{C}_{1}),\ldots,(F_{n}:\mathcal{C}_{n})\}) where \mathsf{A} is the role we are currently translating; \phi and \psi are a set of equations r_{1}\doteq r_{2} between recipes, where \phi represents checks that have already been done, and \psi are checks that are pending; b\in\{\mathsf{c},\mathsf{a}\} is a flag indicating whether we are on the choreography level or in an atomic section; the F_{i} are frames with the same domain that map to terms; and the \mathcal{C}_{i} are either choreographies if b=\mathsf{c} or atomic sections if b=\mathsf{a} . During translation we preserve the invariant that \phi\cup\psi is a complete set of checks for the F_{1},\ldots,F_{n} where \psi may contain checks that do not hold on all F_{i} . If \psi\neq 0 , i.e., if there are pending checks, they will be performed first before all other translation steps. Given a choreography \mathcal{C} and a role \mathsf{A} of that choreography and a frame F_{A} that contains the initial knowledge of \mathsf{A} in the choreography specification where each item has received a unique label \mathcal{X}_{i} , the initial translation state for translating \mathsf{A} in \mathcal{C} is: (\mathsf{A},\emptyset\triangleright\emptyset,\mathsf{c},\{(F_{A}:\mathcal{C})\}) i.e., there is just one possibility \mathcal{C} where we are and the current knowledge is F_{A} . III-B 1 Cases of the Semantics Function The semantics function [\![T]\!] takes a translation state T and projects the choreography to the actions of the role, yielding a local behavior for that role. We define it recursively by a case distinction on T . Since we will often require all possibilities (F_{i},\mathcal{C}_{i}) to start with the same kind of command, we use the following notation: \{F_{i},\nu N_{i}.\mathcal{C}_{i}\}_{i=1}^{n} for \{F_{1},\nu N_{1}.\mathcal{C}_{1},\ldots,F_{n},\nu N_{n},\mathcal{C}_{n}\} , and similar for other constructs in place of \nu N . For simplicity, we first present this semantics without goals. [\![\mathsf{A},\phi\triangleright\emptyset,\mathsf{c},\{(F_{i}:\mathbf{0})\}_{i=0}^{n}]\!] where n>0 All possibilities have finished, and the translation is simply: \mathbf{0} . [\![\mathsf{A},\phi\triangleright\emptyset,\mathsf{c},\{(F:\mathsf{B}\rightarrow\mathsf{C}.\mathcal{C})\}\cup\{F_{i}:\mathcal{C}_{i}\}_{i=1}^{n}]\!] for \mathsf{A}\neq\mathsf{B} and \mathsf{A}\neq\mathsf{C} One of the possibilities is a communication step that \mathsf{A} is not involved in and is therefore ignored. The translation is thus: [\![\mathsf{A},\phi\triangleright\emptyset,\mathsf{c},\{(F:\mathcal{C})\}\cup\{F_{i}:\mathcal{C}_{i}\}_{i=1}^{n}]\!] [\![\mathsf{A},\phi\triangleright\emptyset,\mathsf{c},\{F_{i}:\mathsf{A}\rightarrow\mathsf{B}_{i}:t_{i}.\mathcal{C}_{i}\}_{i=1}^{n}]\!] where n>0 All possibilities are send steps for \mathsf{A} . As explained before, we check whether there is a recipe r such that F_{i}(r)=t_{i} for each 1\leq i\leq n . If there is no such r , then we reject the protocol as unexecutable: either there is no way for \mathsf{A} to produce the outgoing term t_{i} , or the different possibilities would require different recipes, and \mathsf{A} cannot know in which possibility they are. However, if there is such an r , 5 5 5 If there are several such recipes, the choice between them leads to equivalent translation outcomes as explained before. then the translation is: \mathsf{send}(r).[\![\mathsf{A},\phi\triangleright\emptyset,\mathsf{c},\{F_{i}:\mathcal{C}_{i}\}_{i=1}^{n}]\!] [\![\mathsf{A},\phi\triangleright\emptyset,\mathsf{c},\{F_{i}:{\mathsf{B}_{i}}\rightarrow\mathsf{A}:t_{i}.\mathcal{C}_{i}\}_{i=1}^{n}]\!] where n>0 All possibilities are receive steps for \mathsf{A} . Let \mathcal{X} be a new recipe variable and F_{i}^{\prime}=F_{i}[\mathcal{X}\mapsto t_{i}] for every i\in\{1,\ldots,n\} . Let \phi_{i} be a complete finite set of checks for F_{i}^{\prime} and let \Phi=\cup_{i=1}^{n}\,\phi_{i} . This represents all checks that we can do in any of the frames F_{i} . First we can remove from \Phi all those checks that are already implied by the checks \phi from the translation state (i.e., that have already been done before in the translation process). We can also remove from \Phi any equation that is implied by the other equations. Let thus \Phi^{\prime} be a resulting minimal set of equations. 6 6 6 Again, there may be several minimal sets, e.g., if two equations imply each other; however all resulting sets from the minimization are logically equivalent. The translation of the receive step is then obtained by adding received message to the frames and inserting the \Phi^{\prime} as pending checks that have to be done next: \mathsf{receive}(\mathcal{X}).[\![\mathsf{A},\phi\triangleright\Phi^{\prime},\mathsf{c},\{F_{i}^{\prime}:\mathcal{C}_{i}\}_{i=1}^{n}]\!] [\![\mathsf{A},\phi\triangleright\{r_{1}\doteq r_{2}\}\cup\psi,b,\{F_{i}:\mathcal{C}_{i}\}_{i=1}^{n}]\!] where n>0 There is at least one pending check r_{1}\doteq r_{2} . We partition the possibilities into those where F_{i} satisfies the check and those that do not: Let \mathsf{FCs_{+}}=\{(F_{i}:C_{i})\mid F_{i}(r_{1})=_{E}F_{i}(r_{2})\} and \mathsf{FCs_{-}}=\{(F_{i}:C_{i})\mid F_{i}(r_{1})\neq_{E}F_{i}(r_{2})\} . The translation is now: \mathsf{if}\,r_{1}\doteq r_{2}\;\mathsf{then}\,[\![\mathsf{A},\phi\cup\{r_{1}\doteq r_{2}\}\triangleright\psi,b,\mathsf{FCs_{+}}]\!] \phantom{\mathsf{if}\,r_{1}\doteq r_{2}\;}\mathsf{else}\,[\![\mathsf{A},\phi\triangleright\psi,b,\mathsf{FCs_{-}}]\!] [\![\_,\_\triangleright\_,\_,\emptyset]\!] There are no possible continuations. This can happen when doing a check that splits the possibilities into FCs_{+} and FCs_{-} , and one of them is empty. It means that if we reach this branch, the agent has detected that an incoming message is not compliant with the choreography, and aborts the execution. The translation is thus simply: \mathbf{0} [\![\mathsf{A},\phi\triangleright\emptyset,\mathsf{c},\{F_{i}:\mathsf{A}:\mathcal{A}_{i}\}_{i=1}^{n}]\!] where n>0 All possibilities start with an atomic section of the agent \mathsf{A} . Then the translation is simply to issue the lock and switch the atomic section flag: \mathsf{lock}.[\![\mathsf{A},\phi\triangleright\emptyset,\mathsf{a},\{F_{i}:\mathcal{A}_{i}\}_{i=1}^{n}]\!] [\![\mathsf{A},\phi\triangleright\emptyset,\mathsf{c},\{(F:\mathsf{B}:\mathcal{A})\}\cup\{F_{i}:\mathcal{C}_{i}\}_{i=1}^{n}]\!] where \mathsf{B}\neq\mathsf{A} One possibility is that another role goes into its atomic section. Role \mathsf{A} should ignore these steps and just extract all continuations after the atomic section, which is defined as follows: \begin{array}[]{rcl}\mathit{cont}(\mathcal{A}_{1}+\mathcal{A}_{2})&=&\mathit{cont}(\mathcal{A}_{1})\cup\mathit{cont}(\mathcal{A}_{2})\\ \mathit{cont}(\mathsf{if}~s\doteq t~\mathsf{then}~\mathcal{A}_{1}~\mathsf{else}~\mathcal{A}_{2})&=&\mathit{cont}(\mathcal{A}_{1})\cup\mathit{cont}(\mathcal{A}_{2})\\ \mathit{cont}(\_.\mathcal{A})&=&\mathit{cont}(\mathcal{A})\\ \mathit{cont}(\mathcal{C})&=&\{\mathcal{C}\}\end{array} Let \mathcal{C}_{1},\ldots,\mathcal{C}_{m}=\mathit{cont}(\mathcal{A}) in the translation: [\![\mathsf{A},\phi\triangleright\emptyset,\mathsf{c},\{F:\mathcal{C}_{i}\}_{i=1}^{m}\cup\{F_{i}:\mathcal{C}_{i}\}_{i=1}^{n}]\!] We now come to the cases for an atomic section of the agent we translate for: [\![\mathsf{A},\phi\triangleright\emptyset,\mathsf{a},\{F_{i}:\nu N_{i}.\mathcal{A}_{i}\}_{i=1}^{n}]\!] for n>0 All possibilities create a fresh number N_{i} . We pick a fresh label \mathcal{X} and translate: \nu\mathcal{X}.\,[\![\mathsf{A},\phi\triangleright\emptyset,\mathsf{a},\{F_{i}[\mathcal{X}\mapsto N_{i}]:\mathcal{A}_{i}\}_{i=1}^{n}]\!] [\![\mathsf{A},\phi\triangleright\emptyset,\mathsf{a},\{F_{i}:s_{i}:=c[t_{i}].\mathcal{A}_{i}\}_{i=1}^{n}]\!] where n>0 All cases start with a memory read. Similar to the send case, we require that there is one recipe r such that F_{i}(r)=_{E}t_{i} for each 1\leq i\leq n . If not, the semantics rejects the protocol as unexecutable at this point (because the agent either cannot create the proper index for the memory lookup, or there are contradicting possibilities for this index). The retrieved message s_{i} is treated like in the receive case: we add it to the knowledge with a new label \mathcal{X} , giving frames F_{i}^{\prime}=F_{i}[\mathcal{X}\mapsto s_{i}] , and then we compute a complete set of checks \phi_{i} for each F_{i}^{\prime} , compute the union \Phi=\cup_{i=1}^{n}\phi_{i} , and remove redundant equations leading to a reduced \Phi^{\prime} . The translation is then: \mathcal{X}:=c[r].[\![\mathsf{A},\phi\triangleright\Phi^{\prime},\mathsf{a},\{F_{i}^{\prime}:\mathcal{A}_{i}\}_{i=1}^{n}]\!] [\![\mathsf{A},\phi\triangleright\emptyset,\mathsf{a},\{F_{i}:c[t_{i}]:=s_{i}.\mathcal{A}_{i}\}_{i=1}^{n}]\!] where n>0 All possibilities start with a write step. We require that there are recipes r_{1} and r_{2} such that F_{i}(r_{1})=t_{i} and F_{i}(r_{2})=s_{i} for each i\in\{1,\ldots,n\} . (If not, this is a specification error, because it is unclear what A ’s next step is.) Then the translation is: c[r_{1}]:=r_{2}.[\![\mathsf{A},\phi\triangleright\emptyset,\mathsf{a},\{F_{i}:\mathcal{A}_{i}\}_{i=1}^{n}]\!] [\![\mathsf{A},\phi\triangleright\emptyset,\mathsf{a},\{F_{i}:\mathsf{if}~s_{i}\doteq t_{i}~\mathsf{then}~\mathcal{A}_{i}^{+}~\mathsf{else}~\mathcal{A}_{i}^{-}\}_{i=1}^{n}]\!] where n>0 All the \mathcal{A}_{i} start with a condition. We require that there are recipes r_{1} and r_{2} such that F_{i}(r_{1})=t_{i} and F_{i}(r_{2})=s_{i} for each i\in\{1,\ldots,n\} . (If not, this is a specification error, because it is unclear what A ’s next step is.) We define \mathcal{T}^{+}=[\![\mathsf{A},\phi\triangleright\emptyset,\mathsf{a},\{F_{i}:\mathcal{A}_{i}^{+}\}_{i=1}^{n}]\!] and \mathcal{T}^{-}=[\![\mathsf{A},\phi\triangleright\emptyset,\mathsf{a},\{F_{i}:\mathcal{A}_{i}^{-}\}_{i=1}^{n}]\!] . The translation is: \mathsf{if}~r_{1}\doteq r_{2}~\mathsf{then}~\mathcal{T}^{+}~\mathsf{else}~\mathcal{T}^{-} [\![\mathsf{A},\phi\triangleright\emptyset,\mathsf{a},\{F_{i}:\mathcal{C}_{i}\}_{i=1}^{n}]\!] where n>0 Finally, if all the \mathcal{A}_{i} conclude the atomic section, then the translation is: \mathsf{unlock}.[\![\mathsf{A},\phi\triangleright\emptyset,\mathsf{c},\{F_{i}:\mathcal{C}_{i}\}_{i=1}^{n}]\!] [\![\_]\!] for any other translation state this is an error, because it is unclear what \mathsf{A} should do next. III-B 2 Example Let us continue the example choreography from Fig. 3 and let us look at the translation for the role \mathsf{s} . The knowledge of \mathsf{s} gives us the frame: F_{0}=[\mathsf{\mathcal{X}_{1}\mapsto A,\mathcal{X}_{2}\mapsto B,\mathcal{X}_{3}\mapsto s,\mathcal{X}_{4}\mapsto\mathit{sk}(s),} \phantom{F_{0}=[}\mathsf{\mathcal{X}_{5}\mapsto\mathit{inv}(\mathit{sk}(s)),\mathcal{X}_{6}\mapsto\mathit{shk}(A,s),\mathcal{X}_{7}\mapsto\mathit{ek}(B)}] and we compute [\![\mathsf{s},\emptyset\triangleright\emptyset,\mathsf{c},\{F_{0}:\mathcal{C}\}]\!] where \mathcal{C} is the entire choreography. The choreography begins with atomic actions of \mathsf{A} , checking if the key of B is known, asking \mathsf{s} if not and starting the main protocol otherwise. Thus using rule III-B1 we get a split into two possibilities \{(F_{0}:\mathsf{A}\rightarrow\mathsf{s}:(\mathit{key},\mathsf{B},N).\ldots),(F_{0}:\mathcal{C}_{0})\} where \mathcal{C}_{0} is the initial choreography example of Fig. 1 (with \mathit{ek}(\mathsf{B}) replaced by the variable \mathit{EKB} that represents the key that \mathsf{A} has looked up from memory). Now \mathcal{C}_{0} starts with another atomic section of \mathsf{A} (the choice to either send a message or a key update). So we apply again rule III-B1 to split that possibility into two: \begin{array}[]{l}(F_{0}:\mathsf{A}\rightarrow\mathsf{s}:(\mathit{key},\mathsf{B},N).\ldots),\\ (F_{0}:\mathsf{A}\rightarrow\mathsf{s}:\mathit{scrypt}((\mathsf{B},{\color[rgb]{0,0,1}\mathit{crypt}(\ldots,\mathit{EKB})}),\mathit{shk}(\mathsf{A},\mathsf{s})).\ldots)\\ (F_{0}:\mathsf{A}\rightarrow\mathsf{s}:\mathit{scrypt}((\mathsf{B},{\color[rgb]{0,0,1}\mathit{crypt}(\ldots,\mathit{EKB})}),\mathit{shk}(\mathsf{A},\mathsf{s})).\ldots)\end{array} Now finally all messages are something the server can receive, so with rule III-B1 we get updated frames F_{1},F_{2},F_{3} augmenting F_{0} with a new label \mathcal{X}_{8} , which is bound to the respective incoming message. The checks that we can do for F_{1} are that \mathcal{X}_{8} is a triple, that the first item is constant \mathit{key} and the second item is \mathcal{X}_{2} . 7 7 7 More realistically, \mathsf{s} should not expect a particular name \mathsf{B} but rather have it determined through \mathsf{A} ’s request. This is why we like to model \mathit{ek}(\cdot) as a public function (one can look up the public key of any role), but here we deliberately made this function private, so that \mathsf{A} has to ask the server for the role. Anyway the semantics ensures that for any instantiation of the role variables with agent names, we have any number of server instances, so this comes without loss of attacks. For ease of notation, assume we have functions \mathit{vtuple}_{n} and \pi_{n} (for all n\in\mathbb{N} ) with the property \mathit{vtuple}_{n}(t_{1},\ldots,t_{n})=_{E}\top and \pi_{i}(t_{1},\ldots,t_{n})=_{E}t_{i} . Thus the checks for F_{1} are \phi_{1}=\{\mathit{vtuple}_{3}(\mathcal{X}_{8})\doteq\top,\pi_{1}(\mathcal{X}_{8})\doteq\mathit{key},\pi_{2}(\mathcal{X}_{8})\doteq X_{2}\} . In F_{2} and F_{3} we can check that symmetric decryption of \mathcal{X}_{8} with key \mathcal{X}_{6} succeeds and yields a pair. The blue parts in F_{2} and F_{3} cannot be decrypted, so \mathsf{s} cannot further check anything about this. In our example theory E below we have operators \mathit{scrypt} , \mathit{vscrypt} and \mathit{dscrypt} with the properties \mathit{dscrypt}(\mathit{scrypt}(m,k),k)=_{E}m and \mathit{vscrypt}(\mathit{scrypt}(m,k),k)=_{E}\top . Together they model AEAD symmetric schemes, i.e., the attacker cannot modify the encrypted message m by modifying the ciphertext \mathit{scrypt}(m,k) , as this would lead to errors when decrypting; thus the decryption is an operation that fails when applied to an incorrect message or the wrong key, and we model that in the algebra by two functions, one telling us whether decryption works with the given key and one that in the positive case gives the result. We thus have in F_{2} and F_{3} the complete set of the checks: \phi_{2}=\phi_{3}= \{\mathit{vcrypt}(\mathcal{X}_{8},\mathcal{X}_{6})\doteq\top, \mathit{vtuple}_{2}(\mathit{dscrypt}(\mathcal{X}_{8},\mathcal{X}_{6}))\doteq\top,{\pi_{1}(\mathit{dscrypt}(\mathcal{X}_{8},\mathcal{X}_{6}))\doteq\mathcal{X}_{2}}\} . We thus have the translation \mathsf{receive}(\mathcal{X}_{8}).[\![\mathsf{s},\emptyset\triangleright\phi_{1}\cup\phi_{2},\mathsf{c},\{(F_{1}\text{:\ldots}),(F_{2}\text{:\ldots}),(F_{3}\text{:\ldots})\}]\!] Applying rule III-B1 several times to process all checks, we get the possibilities partitioned (because \phi_{1} only holds in F_{1} and \phi_{2} only holds in F_{2} and F_{3} ) as follows: \begin{array}[]{l}\mathsf{if}~\phi_{1}~\mathsf{then}~[\![\mathsf{s},\phi_{1}\triangleright\emptyset,\mathsf{c},\{(F_{1}\text{:\ldots})\}]\!]~\mathsf{else}\\ \mathsf{if}~\phi_{2}~\mathsf{then}~[\![\mathsf{s},\phi_{1}\triangleright\emptyset,\mathsf{c},\{(F_{2}\text{:\ldots}),(F_{3}\text{:\ldots})\}]\!]~\mathsf{else}~\mathbf{0}\end{array} Let us just look at the most interesting branch, namely the positive case under \phi_{2} . Here the next step in F_{2} is \mathsf{s}\rightarrow\mathsf{B}:\mathit{sign}((\mathsf{A},{\color[rgb]{0,0,1}\mathit{crypt}((\mathit{msg},M),\mathit{EKB})}),\mathit{inv}(\mathit{sk}(\mathsf{s}))) and in F_{3} the corresponding step but with content (\mathit{upd},K) . So we need to apply rule III-B1 which requires a recipe r that works in both cases. Let r_{\color[rgb]{0,0,1}b}=\pi_{2}(\mathit{dscrypt}(\mathcal{X}_{8},\mathcal{X}_{6})) which gives the “blue message part” that \mathsf{s} cannot decrypt in either F_{2} or F_{3} . Now r=\mathit{sign}((\mathcal{X}_{1},r_{\color[rgb]{0,0,1}b}),\mathcal{X}_{5}) is the recipe that works in both cases. Thus the complete translation for the server role is: \begin{array}[]{l}\mathsf{receive}(\mathcal{X}_{8}).\mathsf{if}~\phi_{1}~\mathsf{then}~\mathsf{send}(\mathit{sign}((\mathit{key},\mathcal{X}_{2},\mathcal{X}_{7})),\mathcal{X}_{5})~\mathsf{else}\\ \mathsf{if}~\phi_{2}~\mathsf{then}~\mathsf{send}(\mathit{sign}((\mathcal{X}_{1},\pi_{2}(\mathit{dscrypt}(\mathcal{X}_{8},\mathcal{X}_{6}))),\mathcal{X}_{5}))\end{array} III-C Attack Semantics In this section, we formalize our notion of security. In a sentence, we consider there to be an attack if the system can possibly develop in a way that falsifies a given query over traces. A security query is built from the following grammar: \small\begin{array}[]{r c l}p&::=&\mathsf{event}(t)\mid\mathsf{event}(s)\sqsubseteq\mathsf{event}(t)\mid\mathsf{intruder}(t)\mid s\doteq t\\ &\mid&\bot\mid p_{1}\Longrightarrow p_{2}\mid\forall X.\ p^{\prime}\end{array} The other logical operators can be added as syntactic sugar (in particular we will use \land ). We only consider a query well-formed if it contains no free variables. We characterize a trace, (L_{0},F_{0},\mu)\stackrel{{\scriptstyle t_{1},\ldots,t_{n}}}{{\to^{*}}}(L_{m},F_{m},\mu) , by the list of emitted events and the final knowledge of the intruder: ([t_{1},\ldots,t_{n}],F_{m}) . Following is the semantics for evaluating a query: \displaystyle([t_{1},\ldots,t_{n}],F) \displaystyle\models\mathsf{event}(s)\text{ iff }s=_{E}t_{i} \displaystyle([t_{1},\ldots,t_{n}],F) \displaystyle\models\mathsf{intruder}(s)\text{ iff }F(r)=_{E}s \displaystyle([t_{1},\ldots,t_{n}],F) \displaystyle\models s\doteq t\text{ iff }s=_{E}t \displaystyle([t_{1},\ldots,t_{n}],F) \displaystyle\models\bot\text{ never} \displaystyle([t_{1},\ldots,t_{n}],F) \displaystyle\models p_{1}\Longrightarrow p_{2} \displaystyle\text{iff} \displaystyle([t_{1},\ldots,t_{n}],F)\not\models p_{1} \displaystyle\text{or} \displaystyle([t_{1},\ldots,t_{n}],F)\models p_{2} \displaystyle([t_{1},\ldots,t_{n}],F) \displaystyle\models\forall X.\ p \displaystyle\text{iff} \displaystyle\text{ for all }s\text{ we have }([t_{1},\ldots,t_{n}],F)\models p[s/X] \displaystyle([t_{1},\ldots,t_{n}],F) \displaystyle\models\mathsf{event}(s)\sqsubseteq\mathsf{event}(t) \displaystyle\text{iff} \displaystyle\text{ for every }t_{i}=_{E}s\text{ there is a unique }t_{j}=_{E}t We consider a configuration as secure with regard to a given query if the query is valid on all traces from the configuration. For the rest of this section, we will show how to encode the security goals in a choreography as queries. First, we modify the grammar of choreographies to allow the emission of events: \small\begin{array}[]{rcl@{\qquad}l}\mathcal{C}&::=&\ldots\hfil\hskip 18.49988pt\\ \mathcal{A}&::=&\ldots\hfil\hskip 18.49988pt\\ &\mid&\mathsf{event}(t).\mathcal{A}\hfil\hskip 18.49988pt\\ \end{array} These events will be handled by the projection in the same way as sends: We check if we can find a recipe that produces t in all frames, and return a translation error if not. To each secrecy goal g=``t~\mathsf{secret~between}~\mathsf{A}_{1},\ldots,\mathsf{A}_{n}" , we assign a unique event name e_{g}\in\Sigma\setminus\Sigma_{p} . We then replace each g with \mathsf{A}_{1}:\mathsf{event}(e_{g}(t,\mathsf{A}_{1},\ldots,\mathsf{A}_{n})). \ \ \ \ \ \ \ \ \vdots \mathsf{A}_{n}:\mathsf{event}(e_{g}(t,\mathsf{A}_{1},\ldots,\mathsf{A}_{n})) The goal holds iff the following query holds: \forall X,\mathsf{A}_{1},\ldots,\mathsf{A}_{n}.\ \neg\left(\begin{array}[]{l}\mathsf{A}_{1}\not\doteq\mathsf{i}\land\ldots\land\mathsf{A}_{n}\not\doteq\mathsf{i}\land\\ \mathsf{event}(e_{g}(X,\mathsf{A}_{1},\ldots,\mathsf{A}_{n}))\land\mathsf{intruder}(X)\end{array}\right) To a goal g=``\mathsf{B}~\mathsf{ni\text{-}authenticates}~\mathsf{A}~\mathsf{on}~t" , we associate unique start- and end-event names e_{gs},e_{ge}\in\Sigma\setminus\Sigma_{p} . We then replace the goal with the end event \mathsf{B}:\mathsf{event}(e_{ge}(t,\mathsf{A},\mathsf{B})) . We want to check that the occurrence of this event implies the occurrence of a corresponding start event from \mathsf{A} . However, it is not always possible to insert that start event right at the beginning of the choreography; t might contain values that have been generated during the protocol run. To solve this, we make the following modification to the projection semantics for \mathsf{A} : If we are computing [\![\mathsf{A},\phi\triangleright\emptyset,\mathsf{c},\{F_{i}:\mathcal{C}_{i}\}_{i=1}^{n}]\!] , \mathsf{B}:\mathsf{event}(e_{ge}(t,\mathsf{A},\mathsf{B})) is in one of the \mathcal{C}_{i} , and the corresponding start event has not yet been generated, try the following: If there is a recipe r such that F_{1}(r)=t\land\ldots\land F_{n}(r)=t , return \mathsf{event}(e_{gs}(r,\mathsf{A},\mathsf{B})).[\![\mathsf{A},\phi\triangleright\emptyset,\mathsf{c},\{F_{i}:\mathcal{C}_{i}\}_{i=1}^{n}]\!] while remembering that the event was generated. Otherwise, continue computing [\![\mathsf{A},\phi\triangleright\emptyset,\mathsf{c},\{F_{i}:\mathcal{C}_{i}\}_{i=1}^{n}]\!] as normal. The goal is enforced by the following query: \forall X,\mathsf{A},\mathsf{B}.\ \begin{array}[]{l}\mathsf{A}\not\doteq\mathsf{i}\land\mathsf{B}\not\doteq\mathsf{i}\land\mathsf{event}(e_{ge}(X,\mathsf{A},\mathsf{B}))\\ \ \ \ \ \Longrightarrow\mathsf{event}(e_{gs}(X,\mathsf{A},\mathsf{B}))\end{array} For each g=``\mathsf{B}~\mathsf{authenticates}~\mathsf{A}~\mathsf{on}~t" , we do the same procedure, except that we use the query: \forall X,\mathsf{A},\mathsf{B}.\ \begin{array}[]{l}\mathsf{A}\not\doteq\mathsf{i}\land\mathsf{B}\not\doteq\mathsf{i}\Longrightarrow\\ \mathsf{event}(e_{ge}(X,\mathsf{A},\mathsf{B}))\sqsubseteq\mathsf{event}(e_{gs}(X,\mathsf{A},\mathsf{B}))\end{array} IV Mechanization of the Projection We give now an overview of the mechanization for a representative algebraic theory; most details are found in Appendix -B . To implement the projection of Section III , one must be able to do the following: • ( word problem ) Given two terms s and t , check if s=_{E}t . • ( recipe composition ) Given a set of frame-term pairs \{(F_{1},t_{1}),\ldots,(F_{n},t_{n})\} , decide if there is a recipe r so F_{1}(r)=_{E}t_{1}\land\ldots\land F_{n}(r)=_{E}t_{n} , and return it if so. • ( complete set of checks ) Given a frame F calculate a complete set of checks, i.e., a finite set of checks that implies all checks that can be made at all. In this section we will demonstrate how to do this for a particular cryptographic model with Diffie-Hellman keys, symmetric encryption, and asymmetric encryption. We assume that for all destructors we have a corresponding verifier that can be used to check whether decryption would succeed. Recall that we are distinguishing terms, denoted s,t , as used in the choreography. They built over the alphabet \Sigma and variables \mathcal{V} , where \Sigma does not contain any destructors or verifiers, but may contain private functions. In contrast, on the local behavior level, we have recipes that are built over \Sigma_{p} and labels \mathcal{X}_{i} , where \Sigma_{p} contains only public function symbols, but includes destructors and verifiers. As part of our algebraic theory we consider the following built-in symbols: \begin{array}[]{l|lll}&\text{Constructors}&\text{Destructors}&\text{Verifiers}\\ \hline\cr\text{Tuples}&\mathit{pair}&\mathit{fst},\mathit{snd}&\mathit{vpair}\\ \text{Asymmetric Enc.}&\mathit{crypt}&\mathit{dcrypt}&\mathit{vcrypt}\\ \text{Private Keys}&\mathit{inv}&\mathit{pub_{k}}&\mathit{vinv}\\ \text{Symmetric Enc.}&\mathit{scrypt}&\mathit{dscrypt}&\mathit{vscrypt}\\ \text{Signatures}&\mathit{sign}&\mathit{open}&\mathit{vsign}\\ \text{Diffie-Hellman}&\mathit{exp}&\mathit{exp}^{-1}&\mathit{vexp}\\ \end{array} All the constructors are part of \Sigma and can occur in terms, and all except \mathit{inv} are public and thus in \Sigma_{p} and can occur in recipes. Note that we had earlier used n -tuples for simplicity, and here have only binary tuples, but this can be seen as syntactic sugar. Besides these symbols, the modeler can declare other further function symbols that can be either public (and thus both part of \Sigma and \Sigma_{p} ), e.g., to model hash functions or public constants, or that can be private (and thus only part of \Sigma ), e.g., to model key infrastructures or fixes secrets between agents. However, these user-defined functions cannot have any algebraic properties. We also have a public constant \top both in \Sigma and \Sigma_{p} . We call a recipe constructive if it does not contain destructors or verifiers. Definition 2 . We define our algebra E=R\cup B where R= \{\mathit{vpair}(\mathit{pair}(x,y),\top)\doteq\top , \mathit{fst}(\mathit{pair}(x,y),\top)\doteq x , \mathit{snd}(\mathit{pair}(x,y),\top)\doteq y , \mathit{vscrypt}(\mathit{scrypt}(x,y),y)\doteq\top , \mathit{dscrypt}(\mathit{scrypt}(x,y),y)\doteq x , \mathit{vcrypt}(\mathit{crypt}(x,y),\mathit{inv}(y))\doteq\top , \mathit{dcrypt}(\mathit{crypt}(x,y),\mathit{inv}(y))\doteq x , \mathit{vsign}(\mathit{sign}(x,\mathit{inv}(y)),y)\doteq\top , \mathit{open}(\mathit{sign}(x,\mathit{inv}(y)),y)\doteq x , \mathit{vinv}(\mathit{inv}(x),\top)\doteq\top , \mathit{pub_{k}}(\mathit{inv}(x),\top)\doteq x , \mathit{vexp}(\mathit{exp}(x,y),y)\doteq\top , \mathit{exp}^{-1}(\mathit{exp}(x,y),y)\doteq x\} , and B=\{\mathit{exp}(\mathit{exp}(x,y),z)\doteq\mathit{exp}(\mathit{exp}(x,z),y)\} . Let =_{E} denote the congruence induced by these equations and =_{B} the congruence induced just by the equation in B . The functions \mathit{vpair} , \mathit{fst} , \mathit{snd} , \mathit{vinv} , and \mathit{pub_{k}} should actually be unary functions, because they do not require a key. For uniformity we have made them binary functions like all the other destructors and verifiers, and we use \top as a dummy value for the key-position. The reader may be surprised to see a verifier for Diffie-Hellman exponentiation. This is because our method below requires that every destructor has a corresponding verifier. However, the verifier \mathit{vexp} exists only pro-forma: if we our procedure runs into a situation where it actually employs \mathit{vexp} , it stops with an error. The only situation where it would be employed is, if we have an agent knows both x and a term (equivalent to) \mathit{exp}(t,x) , but not t , and this does not occur in standard uses of Diffie-Hellman. A similar question may arise from the destructor and verifier for private keys. Many approaches model a public constructor that from a given private key generates a public key; we use here instead a private constructor \mathit{inv} to map a public key to a corresponding private key; this allows us easily model public-key infrastructures like \mathit{ek}(\mathsf{A}) being the public encryption of \mathsf{A} where \mathit{ek} is a public function (so every agent can lookup keys). The small price to pay is that the inverse mapping from private to public key is called a destructor and that we have a verifier to check if a private key really fits with the public key. The considered theory E=R\cup B allows us to decide the word problem, i.e., for terms or recipes s,t , whether s=_{E}t . This is because R used as rewrite rules modulo B (i.e., \rightarrow_{R/B} ) is convergent. Thus we only need to compare the normal forms of s and t modulo B . The equivalence class modulo B of any term is finite and easily computable. See Theorem 1 in the appendix. IV- 1 Compose We define a function \mathit{compose}(F,t) that, given a frame F and a term t , obtains all constructive recipes r such that F(r)=_{B}t . Roughly, for every term t_{0} in [t]_{B} (the equivalence class of t modulo B ) we can check if t_{0} is a term in the frame, and additionally, if t_{0}=f(t_{1},\ldots,t_{n}) for a public f (which cannot be a destructor or verifier by construction), we recursively compute \mathit{compose}(F,t_{i}) and from the results construct the solutions for \mathit{compose}(F,t) as expected. We further introduce the notion of an analyzed frame , i.e., where the frame contains every term that can be obtained using a destructor on any message in the frame, using a constructive recipe for the key term. In an analyzed frame F , \mathit{compose} finds a recipe for every term t that can be obtained with any recipe (Lemmas 4 and 5 ). IV- 2 Analysis We define an analysis procedure that successively applies decryption steps as long as possible: for every message that potentially can be decrypted, we check if we can compose the decryption key. If so, the resulting message is added to the frame. Whenever we add an analyzed message to the frame, we also need to check again all those messages for which we previously did not have the decryption key. We show that this terminates (Theorem 2 ) and produces correct analyzed frames (Theorem 3 ). IV- 3 Checks Finally, given an analyzed frame, we show how to compute a complete set of checks. In particular, it is sufficient to restrict oneself to constructive recipes for checks in an analyzed frame (Lemma 6 and Theorem 4 ). Finally, the compose procedure can be extended to the recipe composition problem, i.e., given analyzed and checked F_{1},\ldots,F_{n} and goal terms t_{1},\ldots,t_{n} , find a single recipe r with F_{i}(r)=t_{i} for all i , because we try to get a solution for F_{1}(r)=t_{1} and if it exists, then it works in all frames, because they are checked (Theorem 5 ). V Case studies V-A Exporting to ProVerif In this section, we summarize how the output from the projection semantics of Section III can be further translated to ProVerif code for automatic verification. More details can be found in Appendix Section -A . We start by unfolding the labels from the initial knowledge in each local behavior, similarly to what we do in the semantics of Figure 5 . Each local behavior is almost a valid ProVerif process already, except for the use of nondeterministic choice and memory cells. Nondeterministic choice is simple to encode: we take a message from the network (the intruder) indicating which branch to take, and then branch on the content of that message. Thus, we leave it to the intruder to pick the branch that will lead to an attack (if one exists). Encoding memory cells is more involved. We encode each memory cell as a private channel, and ensure by construction that the channel always contains exactly one message (except when the message has been consumed in an atomic section that has not yet been left). Then, in the semantics of ProVerif, a read from the memory cell corresponds exactly to reading the term that was most recently placed in the channel. However, when the ProVerif process is translated to Horn-clauses, certain overapproximations will mean that it is no longer guaranteed that a message on a private channel is consumed in the right order or only once. We decrease the chance of a false positive by adding a counter to each memory cell, which is incremented on every write. Adding the admissible axiom that if two values written to a memory cell are associated with the same counter value they must be equal, excludes many impossible models during the proof search. V-B Examples We implemented a tool in Haskell that automates the projection from choreographies to local behaviors, based on the definitions in Sections III and IV . It also supports the generation of a ProVerif file from these local behaviors, following the steps described in Section V-A . We will in the following describe one particular example, but have made more available. All our examples combined verify in a minute when exported to ProVerif. We wish to highlight the following notable examples: • ttp-blind-forward.choreo is similar to the example from Section II . Here a trusted third party either helps \mathsf{A} authenticate a new encryption key with or authenticate a request to \mathsf{B} , without knowing which branch it is in. • SSO.choreo describes a protocol where an agent \mathsf{A} authenticates to another agent \mathsf{B} using a trusted third party \mathsf{ttp} . We can also verify this when the behaviour of \mathsf{ttp} is taken from SSO-API.choreo , where \mathsf{ttp} is implemented like an API responding to queries and saving their state using memory cells. Our tool includes an option for selecting the behavior of participants from different choreographies like this. • We demonstrate in tpm-simple.choreo and tpm-simple-API.choreo the security of a TPM that can either declassify a given value or delete it. In particular, this protocol is non-monotonic, as it should be transparent to the owner of the value which choice was taken, and that if one choice is made then the other cannot be made later. • SSO-DH.choreo and SSO-DH-API.choreo demonstrates a Diffie-Hellman exchange mediated by a trusted third party. • ASW.choreo contains the example described in the following. The Asokan-Shoup-Waidner (ASW) protocol serves as a motivating example that demonstrates the expressiveness of our choreography language, particularly its support for explicit branching, non-deterministic choice, conditional behavior, and long-term memory access. ASW is a fair contract signing protocol involving three participants: an originator \mathsf{O} , a responder \mathsf{R} , and a trusted third party (\mathsf{TTP}) . The protocol mainly ensures that either both parties obtain a binding contract, or neither does. The key challenges addressed by this protocol are: • Timeouts and abort scenarios : Participants may timeout, leading to different protocol continuations. • Stateful TTP : The TTP must maintain memory of previous contract states to prevent inconsistent responses. • Conditional logic : Protocol actions depend on checking stored memory values. Algorithm 1 ASW Choreography 1: \mathsf{O}:\nu\mathit{Text}.\,\nu\mathit{NO}.\; 2: \mathsf{O}\rightarrow\mathsf{R}:\underbrace{\mathit{sign}(f_{1}(\mathsf{O},\mathsf{R},\mathsf{ttp},\mathit{Text},h(\mathit{NO})),\mathit{inv}(\mathit{pk}(\mathsf{O})))}_{=:M_{1}}. 3: \mathsf{R}:{\color[rgb]{1,0,0}\mathsf{R}\rightarrow\mathsf{O}:\mathit{timeout}.\textsc{Abort}(\mathsf{O},M_{1})} 4: {\color[rgb]{1,0,0}+}\;\;\nu\mathit{NR}.\; 5: \quad\;\mathsf{R}\rightarrow\mathsf{O}:\underbrace{\mathit{sign}(f_{2}(M_{1},h(\mathit{NR})),\mathit{inv}(\mathit{pk}(\mathsf{R})))}_{=:M_{2}}. 6: \quad\;\mathsf{O}:\color[rgb]{1,0,0}\mathsf{O}\rightarrow\mathsf{R}:\mathit{timeout}.\textsc{Resolve}(\mathsf{R},M_{1},M_{2}) 7: \quad\;{\color[rgb]{1,0,0}+}\;\;\;\mathsf{O}\rightarrow\mathsf{R}:\mathit{NO}. 8: \qquad\quad\mathsf{R}:\color[rgb]{1,0,0}\mathsf{R}\rightarrow\mathsf{O}:\mathit{timeout}.\textsc{Resolve}(\mathsf{O},M_{1},M_{2}) 9: \qquad\quad{\color[rgb]{1,0,0}+}\;\;\;\mathsf{R}\rightarrow\mathsf{O}:\mathit{NR} 10: 11: \textsc{Abort}(\mathsf{A},M_{1})= 12: \mathsf{A}\rightarrow\mathsf{\mathsf{ttp}}:sign(f_{\mathit{abort}}(M_{1}),\mathit{inv}(\mathit{pk}(\mathsf{A}))) 13: \mathsf{\mathsf{ttp}}:\mathit{blank}:=\mathit{ttp\_mem}[M_{1}]. 14: \qquad\mathit{ttp\_mem}[M_{1}]:=\mathit{aborted}. 15: \qquad\mathsf{\mathsf{ttp}}\rightarrow\mathsf{A}:\mathit{sign}(f_{\mathit{abort}}(M_{1}),\mathit{inv}(\mathit{pk}(\mathsf{ttp}))) 16: +\quad\,\mathit{aborted}:=\mathit{ttp\_mem}[M_{1}]. 17: \qquad\mathsf{\mathsf{ttp}}\rightarrow\mathsf{A}:\mathit{sign}(f_{\mathit{abort}}(M_{1}),\mathit{inv}(\mathit{pk}(\mathsf{ttp}))) 18: +\quad\,(\mathit{resolved},M_{2}):=\mathit{ttp\_mem}[M_{1}]. 19: \qquad\mathsf{\mathsf{ttp}}\rightarrow\mathsf{A}:\mathit{sign}(f_{\mathit{resolve}}(M_{1},M_{2}),\mathit{inv}(\mathit{pk}(\mathsf{ttp}))) 20: 21: \textsc{Resolve}(\mathsf{A},M_{1},M_{2})= 22: \mathsf{A}\rightarrow\mathsf{\mathsf{ttp}}:sign(f_{\mathit{resolve}}(M_{1},M_{2}),\mathit{inv}(\mathit{pk}(\mathsf{A}))) 23: \mathsf{\mathsf{ttp}}:\mathit{blank}:=\mathit{ttp\_mem}[M_{1}]. 24: \qquad\mathit{ttp\_mem}[M_{1}]:=(\mathit{resolved},M_{2}). 25: \qquad\mathsf{\mathsf{ttp}}\rightarrow\mathsf{A}:\mathit{sign}(f_{\mathit{resolve}}(M_{1},M_{2}),\mathit{inv}(\mathit{pk}(\mathsf{ttp}))) 26: +\quad\,\mathit{aborted}:=\mathit{ttp\_mem}[M_{1}]. 27: \qquad\mathsf{\mathsf{ttp}}\rightarrow\mathsf{A}:\mathit{sign}(f_{\mathit{abort}}(M_{1}),\mathit{inv}(\mathit{pk}(\mathsf{ttp}))) 28: +\quad\,(\mathit{resolved},M_{2}):=\mathit{ttp\_mem}[M_{1}]. 29: \qquad\mathsf{\mathsf{ttp}}\rightarrow\mathsf{A}:\mathit{sign}(f_{\mathit{resolve}}(M_{1},M_{2}),\mathit{inv}(\mathit{pk}(\mathsf{ttp}))) V-C Non-deterministic Choice and Branching Algorithm 1 presents the ASW choreography using explicit branching in the message flow. After \mathsf{O} sends M_{1} to \mathsf{R} , the responder can either timeout and trigger an abort request (shown in red), or continue by generating \mathit{NR} and replying with M_{2} . In the continuation, timeouts may occur again: after receiving M_{2} , \mathsf{O} can either timeout and ask the \mathsf{\mathsf{ttp}} to resolve, or proceed by sending \mathit{NO} ; symmetrically, after receiving \mathit{NO} , \mathsf{R} can either timeout and resolve, or complete by sending \mathit{NR} . The explicit + -marked alternatives capture this non-determinism directly at the level of the choreography. V-D Conditional Behavior and Memory Access The distinctive feature of ASW is the behavior of the trusted third party, which consults and updates long-term memory cells indexed by the contract identifier M_{1} . In both Abort and Resolve , the \mathsf{\mathsf{ttp}} first reads \mathit{ttp\_mem}[M_{1}] (with \mathit{blank} denoting an uninitialized cell) and then branches on the stored value. This illustrates several language features: 1. Memory read : \mathit{blank}:=\mathit{ttp\_mem}[M_{1}] reads the current state associated with M_{1} . 2. Case distinction on memory : depending on whether \mathit{ttp\_mem}[M_{1}] is still \mathit{blank} , has been set to \mathit{aborted} , or contains (\mathit{resolved},M_{2}) , the \mathsf{\mathsf{ttp}} returns a consistently matching signed response. 3. Memory write : \mathit{ttp\_mem}[M_{1}]:=\mathit{aborted} (in Abort ) and \mathit{ttp\_mem}[M_{1}]:=(\mathit{resolved},M_{2}) (in Resolve ) record the outcome so that repeated requests cannot lead to contradictory replies. 4. Non-monotonic memory : the same cell can be read multiple times and updated across different interactions in the run. V-E Semantic Challenge: Participant Knowledge A subtle aspect of ASW mechanization arises during projection. When \mathsf{O} or \mathsf{R} make decisions (e.g., “abort”), they must send signals that the \mathsf{ttp} later interprets. However, the originating participant does not see the entire memory state of the TTP. During projection, the analyzer must determine: • When to accept incoming values without immediate verification (e.g., when \mathsf{O} receives an untagged nonce response). • When to insert runtime checks that compare received values against later constraints (e.g., when verifying h(NO)=X after learning NO ). VI Related Work and Conclusions Alice-and-Bob notation. Several lines of work have given Alice-and-Bob notation a precise semantics by compiling them to lower-level role-based specifications, and by rejecting notations that are not executable because e.g. senders cannot construct a message or receivers cannot check it. Early semantics were developed for the free term algebra and later extended to equational theories, often by reducing executability questions to intruder deduction and unification problems [ 15 , 7 , 21 ] . Our semantics follows this tradition, but lifts it from linear notations to choreographies with non-deterministic choice, branching, and mutable long-term memory. This combination is essential for modeling modern protocol interactions with stateful services and APIs, while maintaining the compact global view that motivates Alice-Bob notations. Protocol models and tool support. At the other end of the spectrum, multi-set rewriting languages (e.g., as used by Tamarin and the AVISPA family) provide an explicit account of state and message flows and are well-suited for reasoning with rich adversary models [ 19 , 2 , 4 ] . Process-calculus based tools such as ProVerif offer a more program-like view of each role and highly automated verification, typically by a sound over-approximation [ 5 , 6 ] . Our contribution is complementary: CryptoChoreo aims to be a high-level specification language that can be translated into such backends. In this respect, our approach is aligned with lines of work that provide source-to-source translations or front-ends for existing verification tools, such as SAPIC/SAPIC+ [ 16 , 10 ] , but with a focus on preserving the readability and single global story of a choreography. Choreographies and global types. Choreographic programming and the theory of multiparty session types/global types study how a global description of multiparty interaction can be projected to local behaviors, with correctness guarantees such as deadlock freedom [ 8 , 9 , 14 ] . Our work is inspired by the same global-to-local methodology, but targets the Dolev–Yao setting with an active adversary, cryptographic constructors/destructors, equational theories, and explicit attacker knowledge. State and APIs in protocol models. Stateful extensions and encodings have been studied both at the specification level and in tool-oriented front-ends [ 16 ] . CryptoChoreo makes state explicit at the choreography level via memory cells. Equational reasoning and mechanization. Reasoning about message construction, parsing, and checks in the presence of equational theories is a classic challenge in symbolic protocol analysis [ 13 ] . Our mechanization focuses on a representative theory combining standard constructors/destructors with Diffie–Hellman exponentiation, and yields an effective projection procedure [ 23 ] . This is intentionally backend-agnostic at the level of the core semantics, while our ProVerif export demonstrates one concrete and practical target. Conclusions. We introduced CryptoChoreo, a choreography language for cryptographic protocols that extends Alice-and-Bob notation with non-deterministic choice, conditional branching, and mutable long-term memory, together with a projection-based semantics and an effective mechanization for a representative equational theory. Our ProVerif export shows that these high-level specifications can be connected to automated verification backends in practice. Future work includes widening the class of supported equational theories, improving automation for non-monotonic state encodings, and adding additional backend targets. -A Exporting to ProVerif (extended) ProVerif encoding In this section, we will describe how to use the projection semantics from Section III to automatically convert a choreography into a ProVerif process. For the rest of this section, we assume the following: • We have a choreography \mathcal{C} • In \mathcal{C} there are roles \mathsf{A}_{1},\ldots,\mathsf{A}_{n_{\mathsf{A}}} • The initial knowledges are given in F_{\mathsf{A}_{1}},\ldots,F_{\mathsf{A}_{n_{\mathsf{A}}}} • We have projected the choreography for each role: \mathcal{L}_{\mathsf{A}_{1}}=F_{\mathsf{A}_{1}}([\![F_{\mathsf{A}_{1}}:\mathcal{C}]\!]_{\mathsf{A}_{1}}),\ldots,\mathcal{L}_{n_{\mathsf{A}}}=F_{n_{\mathsf{A}}}([\![F_{n_{\mathsf{A}}}:\mathcal{C}]\!]_{n_{\mathsf{A}}}) • Of all the roles, \mathsf{U}_{1},\ldots,\mathsf{U}_{n_{\mathsf{U}}} are untrusted. • For each role \mathsf{A}_{i} , \mathsf{U}_{\mathsf{A}_{i}1},\ldots,\mathsf{U}_{\mathsf{A}_{i}n_{\mathsf{U}_{\mathsf{A}_{i}}}} are the untrusted roles occurring in \mathcal{L}_{\mathsf{A}_{i}} and F_{\mathsf{A}_{i}} (i.e. the parameters to the role) • In \mathcal{C} we have the cell families c_{1},\ldots,c_{n_{c}} We start by encoding the algebra. For the most part, we encode the algebra E as is, though a simplification must be made with regard to \exp . Directly inserting the equation in B in ProVerif will lead to nontermination. However, as shown in [ 17 ] and [ 22 ] , it is sound to use the following encoding for standard Diffie-Hellman: \mathbf{fun}\ \mathsf{exp}(\mathsf{bitstring},\mathsf{bitstring}){:}\ \mathsf{bitstring}. \mathbf{const}\ \mathsf{g}{:}\ \mathsf{bitstring}. \mathbf{equation}\ \mathbf{forall}\ \mathit{x}{:}\ \mathsf{bitstring},\mathit{y}{:}\ \mathsf{bitstring}; \ \ \ \ \mathsf{exp}(\mathsf{exp}(\mathsf{g},\mathit{y}),\mathit{x})=\mathsf{exp}(\mathsf{exp}(\mathsf{g},\mathit{x}),\mathit{y}). We will omit most of the definition of the algebra here, but include the encoding of symmetric encryption: \mathbf{type}\ \mathsf{skey}. \mathbf{fun}\ \mathsf{scrypt}(\mathsf{bitstring},\mathsf{skey}){:}\ \mathsf{bitstring}. \mathbf{reduc}\ \mathbf{forall}\ \mathit{x}{:}\ \mathsf{bitstring},\mathit{k}{:}\ \mathsf{skey}; \ \ \ \ \mathsf{dscrypt}(\mathsf{scrypt}(\mathit{x},\mathit{k}),\mathit{k})=\mathit{x}. \mathbf{fun}\ \mathsf{vscrypt}(\mathsf{bitstring},\mathsf{skey}){:}\ \mathsf{bool} \mathbf{reduc}\ \mathbf{forall}\ \mathit{x}{:}\ \mathsf{bitstring},\mathit{k}{:}\ \mathsf{skey};\ \ \ \ \ \mathsf{vscrypt}(\mathsf{scrypt}(\mathit{x},\mathit{k}),\mathit{k})=\mathsf{true} \mathbf{otherwise}\ \mathbf{forall}\ \mathit{x}{:}\ \mathsf{bitstring},\mathit{k}{:}\ \mathsf{skey};\ \ \ \ \ \mathsf{vscrypt}(\mathit{x},\mathit{k})=\mathsf{false}. As another preliminary step, we include the type of agents and the name of the intruder: \mathbf{type}\ \mathsf{agent}. \mathbf{free}\ \mathsf{i}{:}\ \mathsf{agent}. ProVerif processes are written in the \pi -calculus , and look much like our local behaviors, except for network communication, nondeterministic choice, and memory cells. We write [\![\mathcal{L}]\!]_{\mathsf{pv}} for the ProVerif process obtained from the local behavior \mathcal{L} , and in the following only describe the cases where the local behaviors differ from the resulting ProVerif processes. In our local behaviors, we simply use \mathsf{send}(X) and \mathsf{receive}(X) to send the content of variable X to the public network or receive a value from the network and assign it to X . In ProVerif, the corresponding statements are \mathbf{out}(\mathsf{c},\mathit{X}) and \mathbf{in}(\mathsf{c},X{:}\mathsf{bitstring}) , where \mathsf{c} is a public channel. To make a clear conceptual divide, we declare two public channels: \mathsf{c} is the public channel the communication declared in the choreography happens over, while we use \mathsf{ic} when information must be given to or taken from the intruder for the purpose of modeling. \mathbf{free}\ \mathsf{ic}{:}\ \mathsf{channel}. \mathbf{free}\ \mathsf{c}{:}\ \mathsf{channel}. We then define [\![\mathsf{send}(t).\mathcal{L}]\!]_{\mathsf{pv}}=\mathbf{out}(\mathsf{c},t);[\![\mathcal{L}]\!]_{\mathsf{pv}} and [\![\mathsf{receive}(X).\mathcal{L}]\!]_{\mathsf{pv}}=\mathbf{in}(\mathsf{c},X{:}\mathsf{bitstring});[\![\mathcal{L}]\!]_{\mathsf{pv}} . When a process makes a nondeterministic choice, our encoding simply has the intruder decide: [\![\mathcal{L}_{1}+\mathcal{L}_{2}+\ldots+\mathcal{L}_{n}]\!]_{\mathsf{pv}}= \ \ \mathbf{in}(\mathsf{ic},\mathit{Branch}{:}\mathit{nat}); \ \ \mathbf{if}\ \mathit{Branch}=0\ \mathbf{then}\ \ \ \ \ \ \ [\![\mathcal{L}_{1}]\!]_{\mathsf{pv}} \ \ \mathbf{else}\ \mathbf{if}\ \mathit{Branch}=1\ \mathbf{then}\ \ \ \ \ \ \ [\![\mathcal{L}_{2}]\!]_{\mathsf{pv}}\ \ \ \ \ \ \ \ \ \vdots \ \ \mathbf{else}\ \mathbf{if}\ \mathit{Branch}=\mathit{n}\ \mathbf{then}\ \ \ \ \ \ \ [\![\mathcal{L}_{n}]\!]_{\mathsf{pv}} With regard to memory cells, we restrict ourselves to choreographies with the following properties: • In every atomic section there is at most one read and one write to each cell family on every branch, and if a branch contains both they must use the same address. • All writes happen at the end of the atomic section. • All addresses are public. 8 8 8 This is not technically required for the translation to be sound. However, our translation will reveal addresses to the intruder, so you will get false attacks if this is not the case. For each cell family, c_{i} , we declare a function: \mathbf{fun}\ \mathsf{cell{\_}}c_{i}(\mathsf{bitstring}){:}\ \mathsf{channel}\ [\mathit{private}]. We can use this function to create a private channel for each cell in the family. Each such channel will contain at most one message at any given time, representing the current value stored in the cell. Information sent on a private channel is of course not revealed to the intruder. Furthermore, communication over private channels is synchronous, and we can use this to enforce atomicity when there is a read and write to the same cell in one atomic section. The same trick can be used to create atomic sections in general. We define \mathbf{free}\ \mathsf{atomic{\_}lock}{:}\ \mathsf{channel}\ [\mathit{private}]. \mathbf{const}\ \mathsf{atomic{\_}baton}{:}\ \mathsf{bitstring}.\ To enter an atomic section, a process must obtain the baton, and they should send it back when they leave. We have not found it beneficial to enforce atomicity of all atomic sections from local behaviors, but use it strategically for some parts (for example the memory-initializer processes below). We ensure that when an agent wants to read from a cell there is always a message available by including initializer processes for each cell family. ProVerif supports tables , which are set-like structure we can use to keep track of which cells have been initialized, thus making sure that we only initialize a cell once and enforce the property that each cell channel contains at most one message. For each c_{i} , we define: \mathbf{table}\ c_{i}\mathsf{{\_}initializer{\_}table}(\mathsf{bitstring}). \mathbf{let}\ c_{i}\mathit{{\_}initializer}()= \ \ \ \ \mathbf{in}(\mathsf{atomic{\_}lock},=\mathsf{atomic{\_}baton}); \ \ \ \ \mathbf{in}(\mathsf{ic},\mathit{Addr}{:}\ \mathsf{bitstring}); \ \ \ \ \mathbf{get}\ c_{i}\mathsf{{\_}initializer{\_}table}(=\mathit{Addr})\ \mathbf{in}\ 0 \ \ \ \ \mathbf{else} \ \ \ \ \ \ \ \ \mathbf{insert}\ c_{i}\mathsf{{\_}initializer{\_}table}(\mathit{Addr}); \ \ \ \ \ \ \ \ (\mathbf{out}(\mathsf{cell{\_}}c_{i}(\mathit{Addr}),\mathsf{blank})\mid \ \ \ \ \ \ \ \ \ \mathbf{out}(\mathsf{atomic{\_}lock},\mathsf{atomic{\_}baton})). The outputs at the end must be put in parallel, so that one does not block the other. We can now have the intruder initialize our memory cells: [\![X:=c[t].\mathcal{L}]\!]_{\mathsf{pv}}=\mathbf{out}(\mathsf{ic},t);\mathbf{in}(\mathsf{cell{\_}}c(t),X{:}\ \mathsf{bitstring});[\![\mathcal{L}]\!]_{\mathsf{pv}} Also, writing should not block the rest of the process: [\![c[t]:=s.\mathcal{L}]\!]_{\mathsf{pv}}=(\mathbf{out}(\mathsf{cell{\_}}c(t),s)\mid[\![\mathcal{L}]\!]_{\mathsf{pv}}) . There are two remaining problems: If on a branch in an atomic section there is a read from a cell but no write, the value in the cell will be consumed and no other process will be able to read from it. Similarly, if there is a write but no read, the cell will contain two values, and either is a possible value when the next process reads from the cell (we also lose the atomicity mentioned above). We solve this by a simple transformation: If we are done translating a branch of an atomic section where we have processed X:=c[t] but no corresponding write and need to return the rest of the translation [\![\mathcal{L}]\!]_{\mathsf{pv}} , return instead (\mathbf{out}(\mathsf{cell{\_}}c(t),s)\mid[\![\mathcal{L}]\!]_{\mathsf{pv}}) . Similarly, if we want to translate [\![c_{1}[t_{1}]:=s_{1}.\ldots.c_{n}[t_{n}]:=s_{n}.\mathcal{L}]\!]_{\mathsf{pv}} (recall that writes must be at the end of an atomic section) and have not read from c_{i} , we return \mathbf{out}(\mathsf{ic},t_{i});\mathbf{in}(\mathsf{cell{\_}}c_{i}(t_{i}),\_{:}\ \mathsf{bitstring});[\![c_{1}[t_{1}]:=s_{1}.\ldots.c_{n}[t_{n}]:=s_{n}.\mathcal{L}]\!]_{\mathsf{pv}} . We now how a way to translate local behaviors to ProVerif processes. However, we still need to compose all these into a single process that can be verified by ProVerif. Furthermore, this process must handle the multiple sessions and instantiations supported by the semantics in Figure 5 . For each role \mathsf{A}_{i} with parameters \mathsf{U}_{\mathsf{A}_{i}1},\ldots,\mathsf{U}_{\mathsf{A}_{i}n_{\mathsf{U}_{\mathsf{A}_{i}}}} we define the process spawner for that agent: \mathbf{let}\ \mathit{process}{\mathsf{A}_{i}}({\mathsf{U}_{\mathsf{A}_{i}1}}{:}\ \mathsf{agent},\ldots,{\mathsf{U}_{\mathsf{A}_{i}n_{\mathsf{U}_{\mathsf{A}_{i}}}}}{:}\ \mathsf{agent})=[\![\mathcal{L}_{\mathsf{A}_{i}}]\!]_{\mathsf{pv}}. \mathbf{let}\ \mathit{spawn}{\mathsf{A}_{i}}()= \ \ \ \ \mathbf{in}(\mathsf{ic},({\mathsf{U}_{\mathsf{A}_{i}1}}{:}\ \mathsf{agent},\ldots,{\mathsf{U}_{\mathsf{A}_{i}n_{\mathsf{U}_{\mathsf{A}_{i}}}}}{:}\ \mathsf{agent})); \ \ \ \ \mathit{process}{\mathsf{A}_{i}}({\mathsf{U}_{\mathsf{A}_{i}1}},\ldots,{\mathsf{U}_{\mathsf{A}_{i}n_{\mathsf{U}_{\mathsf{A}_{i}}}}}). For each untrusted \mathsf{U}_{i} we must also give the intruder the associated initial knowledge. Let \mathsf{U}_{\mathsf{U}_{i}1},\ldots,\mathsf{U}_{\mathsf{U}_{i}n} be all the parameters of the role \mathsf{U}_{i} except the role \mathsf{U}_{i} itself and t_{1},\ldots,t_{m} be the terms in the knowledge of \mathsf{U}_{i} (i.e. \mathcal{F}_{\mathsf{U}_{i}}=\{\mathcal{X}_{1}\mapsto t_{1},\ldots,\mathcal{X}_{m}\mapsto t_{m}\} ). We define: \mathbf{let}\ \mathit{knowledge}{\mathsf{U}_{i}}()= \ \ \ \ \mathbf{in}(\mathsf{ic},({\mathsf{U}_{\mathsf{U}_{i}1}}{:}\ \mathsf{agent},\ldots,{\mathsf{U}_{\mathsf{U}_{i}n}}{:}\ \mathsf{agent})); \ \ \ \ \mathbf{out}(\mathsf{ic},(t_{1}[\mathsf{i}/\mathsf{U}_{i}],\ldots,t_{m}[\mathsf{i}/\mathsf{U}_{i}])). Finally, we can define the main ProVerif process: \mathbf{process} \ \ \ \ (\mathbf{out}(\mathsf{atomic{\_}lock},\mathsf{atomic{\_}baton}))\mid \ \ \ \ !(\mathbf{new}\ \mathit{a}{:}\ \mathsf{agent};\ \mathbf{out}(\mathsf{ic},\mathit{a}))\mid \ \ \ \ !(\mathit{spawn}{\mathsf{A}_{1}}())\mid \ \ \ \ \ \ \vdots \ \ \ \ !(\mathit{spawn}{\mathsf{A}_{n_{\mathsf{A}}}}())\mid \ \ \ \ !(\mathit{knowledge{\mathsf{U}_{1}}}())\mid \ \ \ \ \ \ \vdots \ \ \ \ !(\mathit{knowledge{\mathsf{U}_{n_{\mathsf{U}}}}}())\mid \ \ \ \ !c_{1}\mathit{{\_}initializer}() \ \ \ \ \ \ \vdots \ \ \ \ !c_{n_{c}}\mathit{{\_}initializer}() Improved Encoding of Memory Cells When verifying ProVerif code produced by the encoding above, we run into the issue that the overapproximations associated with the abstractions of ProVerif make many secure protocols unverifiable. By default, ProVerif will consider the values in a cell as a set, and when you read you will not necessarily get the last value that was written. This means that for example the TPM example included with our submission does not verify, since ProVerif considers runs where \mathit{deleted} is written to the cell and then \mathit{classified} is later read from it. We can improve the accuracy of our encoding by a trick inspired by the “precise” option in ProVerif, originally presented in [ 11 ] . When writing t to a cell c , we instead write (i_{c},t) where i_{c} is a natural number indicating that this was the i_{c} th value written to c . Furthermore, we trigger an event registering what was written, every time a value is written to a call. The new encoding of cell c_{i} becomes: \mathbf{fun}\ \mathsf{cell{\_}}c_{i}(\mathsf{bitstring}){:}\ \mathsf{channel}\ [\mathit{private}]. \mathbf{event}\ \mathsf{write{\_}}c_{i}(\mathsf{bitstring},\mathsf{nat},\mathsf{bitstring}). \mathbf{table}\ c_{i}\mathsf{{\_}initializer{\_}table}(\mathsf{bitstring}). \mathbf{let}\ c_{i}\mathit{{\_}initializer}()= \ \ \ \ \mathbf{in}(\mathsf{atomic{\_}lock},=\mathsf{atomic{\_}baton}); \ \ \ \ \mathbf{in}(\mathsf{ic},\mathit{Addr}{:}\ \mathsf{bitstring}); \ \ \ \ \mathbf{get}\ c_{i}\mathsf{{\_}initializer{\_}table}(=\mathit{Addr})\ \mathbf{in}\ 0 \ \ \ \ \mathbf{else} \ \ \ \ \ \ \ \ \mathbf{event}\ \mathsf{write{\_}}c_{i}(\mathit{Addr},0,\mathsf{blank}); \ \ \ \ \ \ \ \ \mathbf{insert}\ c_{i}\mathsf{{\_}initializer{\_}table}(\mathit{Addr}); \ \ \ \ \ \ \ \ (\mathbf{out}(\mathsf{cell{\_}}c_{i}(\mathit{Addr}),(0,\mathsf{blank}))\mid \ \ \ \ \ \ \ \ \ \mathbf{out}(\mathsf{atomic{\_}lock},\mathsf{atomic{\_}baton})). Furthermore, we redefine the process translation with the following: [\![X:=c[t].\mathcal{L}]\!]_{\mathsf{pv}}=\begin{array}[]{l}\mathbf{out}(\mathsf{ic},t);\\ \mathbf{in}(\mathsf{cell{\_}}c(t),(\mathit{Counter}_{c}{:}\ \mathsf{nat},X{:}\ \mathsf{bitstring}));\\ [\![\mathcal{L}]\!]_{\mathsf{pv}}\end{array} [\![c[t]:=s.\mathcal{L}]\!]_{\mathsf{pv}}=\begin{array}[]{l}\mathbf{event}\ \mathsf{write{\_}}c(t,\mathit{Counter}_{c},s);\\ (\mathbf{out}(\mathsf{cell{\_}}c(t),(\mathit{Counter}_{c}+1,s))\mid[\![\mathcal{L}]\!]_{\mathsf{pv}})\end{array} When inserting writes on branches that only have reads, we can omit incrementing the counter, as we will necessarily just write back the value that was already there. In our experiments, this omission increases the efficiency of ProVerif in many cases. Our encoding ensures that every time a new value is put in the cell, it is associated with a new counter value. Thus, it is sound to add the following axiom: \mathbf{axiom}\ t{:}\ \mathsf{bitstring},\mathit{C}{:}\ \mathit{nat},s_{1}{:}\ \mathsf{bitstring},s_{2}{:}\ \mathsf{bitstring}; \ \ \ \ \mathbf{event}(\mathsf{write{\_}}c_{i}(t,\mathit{C},s_{1}))\wedge\mathbf{event}(\mathsf{write{\_}}c_{i}(t,\mathit{C},s_{2})) \ \ \ \ \ \ \ \ \Longrightarrow s_{1}=s_{2}. -B Mechanization of the Projection in Detail We will here show in more detail how to solve the word problem , recipe-composition problem , and complete-set-of-checks problem described in Section IV . In addition to the \Sigma and \Sigma_{p} from Section IV , we use \Sigma_{d} to denote the set of destructors (+ pair projections, Diffie-Hellman inverse, etc.) and \Sigma_{v} for the set of verifiers. Unlike in the main matter of the paper, we will here permit terms s,t,\ldots to contain all function symbols, as we here make precise how these terms are then reduced to ones built only from \Sigma . For the benefit of the following proofs, we define the syntactic size of terms and checks: |\mathcal{X}|=1 , |f(t_{1},\ldots,t_{n})|=1+|t_{1}|+\ldots+|t_{n}| , and |t\doteq s|=|t|+|s| . Additionally, we need the following concepts: Definition 3 . We define [t]_{=B}=\{t^{\prime}\mid t=_{B}t^{\prime}\} . We write \rightarrow_{R} for the rewriting system obtain by applying the equations in R from left to right. We can then define the rewriting system modulo B -equivalence classes: s\rightarrow_{R/B}t iff \exists s^{\prime}\ t^{\prime}.\ s=_{B}s^{\prime}\land s^{\prime}\rightarrow_{R}t^{\prime}\land t^{\prime}=_{B}t . We use t\downarrow_{R/B} to denote the normal form of t . Lemma 1 . If s=_{B}t then |s|=|t| and if s\rightarrow_{R/B}t then |s|>|t| . Proof. The first part can be shown by induction on the derivation of s=_{B}t , and the second part follows by case analysis on s^{\prime}\rightarrow_{R}t^{\prime} after unfolding the definition of \rightarrow_{R/B} . ∎ Lemma 2 . s=_{E}t if and only if either: • s=_{B}t , • or there is s^{\prime} so s\rightarrow_{R/B}s^{\prime} and s^{\prime}=_{E}t , • or there is t^{\prime} so t\rightarrow_{R/B}t^{\prime} and s=_{E}t^{\prime} Proof. We do induction on the derivation of s=_{E}t in the equational logic induced by E . ∎ We can now show that our rewriting system is well-behaved: Lemma 3 . (A) [t]_{=B} is finite for all t . (B) If s\rightarrow_{R/B}t then s=_{E}t . (C) \rightarrow_{R/B} is convergent, modulo B . (D) t\downarrow_{R/B} is defined and unique for all t , modulo B . Proof. (A) is easy to see (the equation in B is a kind of commutativity). (B) follows from transitivity of =_{E} and the definitions of \rightarrow_{R} and \rightarrow_{R/B} . (D) follows (C) by definition. To show (C), we combine (B) with the following: (1) \rightarrow_{R/B} has no infinite chains. (2) If s=_{E}t and \rightarrow_{R/B} applies to neither s nor t , then s=_{B}t . (1) follows from the fact that if t_{1}\rightarrow_{R/B}t_{2}\rightarrow_{R/B}\ldots then |t_{1}|>|t_{2}|>\ldots . (2) follows from Lemma 2 . ∎ With this, we can solve the word problem from the start of the section: Theorem 1 . s=_{E}t if and only if s\downarrow_{R/B}=_{B}t\downarrow_{R/B} . Proof. That s\downarrow_{R/B}=_{B}t\downarrow_{R/B} implies s=_{E}t follows from Lemma 3 (B). If s=_{E}t then s\downarrow_{R/B}=_{E}t\downarrow_{R/B} by Lemma 3 (B), and since \rightarrow_{R/B} applies to neither s\downarrow_{R/B} nor t\downarrow_{R/B} we have s\downarrow_{R/B}=_{B}t\downarrow_{R/B} by Lemma 2 . ∎ In the following, we will analyze a set of frames by alternating between applying verifiers and destructors to obtain new terms. We extend frames with additional information, including which checks have been performed, and how the content in a label was derived. Definition 4 (Enhanced Frames) . Frames are built over the following grammar: \displaystyle F \displaystyle::= \displaystyle 0 \displaystyle\mid \displaystyle F_{0}.\mathcal{X}\mapsto t \displaystyle\mid \displaystyle F_{0}.\mathcal{X}\leftarrow r\mapsto t \displaystyle\mid \displaystyle F_{0}.r_{1}\doteq r_{2} We let e range over the entries of the form \mathcal{X}\mapsto t , \mathcal{X}\leftarrow r\mapsto t , and r_{1}\doteq r_{2} . • The domain of a frame is defined as follows. \dom(0)=\emptyset , \dom(F_{0}.\mathcal{X}\mapsto t)=\dom(F_{0})\cup\{\mathcal{X}\} , \dom(F_{0}.\mathcal{X}\leftarrow r\mapsto t)=\dom(F_{0})\cup\{\mathcal{X}\} , and \dom(F_{0}.r_{1}\doteq r_{2})=\dom(F_{0}) . • Given a recipe r for frame F , we define F(r) as expected, ignoring r_{1}\doteq r_{2} and \leftarrow r . In the following, we only consider well-formed frames , which satisfy these properties: • In a frame F_{0}.\mathcal{X}\mapsto t , \mathcal{X}\notin\dom(F_{0}) and t is constructive. • In a frame F_{0}.\mathcal{X}\leftarrow r\mapsto t , \mathcal{X}\notin\dom(F_{0}) , \mathsf{fv}(r)\subseteq\dom(F_{0}) , F_{0}(r)=t , and there exists constructive t^{\prime} such that t=_{E}t^{\prime} . • In a frame F_{0}.r_{1}\doteq r_{2} , \mathsf{fv}(r_{1})\cup\mathsf{fv}(r_{2})\subseteq\dom(F_{0}) , and F_{0}(r_{1})=_{E}F_{0}(r_{2}) . • In a frame F_{0}.e , F_{0} is well-formed. It is easy to see that the projection semantics above and the following procedures preserve well-formedness. The checks contained in a frame F , written \mathit{checks}(F) , is the set of all the equations r_{1}\doteq r_{2} contained in the frame together with the equations l\doteq r for each entry l\leftarrow r\mapsto t in the frame. In the projection semantics, we consider sets of frames. There is a notion that these frames are identical with regard to all operations we have performed so far, which we formalize in the following: Definition 5 (Compatible Frames) . We define two frames being compatible , written F\simeq F^{\prime} , as the least relation satisfying the following rules: \begin{array}[]{cccccc}0\simeq 0\\ F_{0}.\mathcal{X}\mapsto t\simeq F_{0}^{\prime}.\mathcal{X}\mapsto t^{\prime}F_{0}\simeq F_{0}^{\prime}\\ F_{0}.\mathcal{X}\leftarrow r\mapsto t\simeq F_{0}^{\prime}.\mathcal{X}\leftarrow r\mapsto t^{\prime}F_{0}\simeq F_{0}^{\prime}\\ F_{0}.r_{1}\doteq r_{2}\simeq F_{0}^{\prime}.r_{1}\doteq r_{2}F_{0}\simeq F_{0}^{\prime}\end{array} Thus, frames are compatible if they have passed the same checks and performed the same operations to construct new terms, in the same order. Our analysis should extend a frame to contain all derivable subterms. This goal is captured in the following: Definition 6 . A label \mathcal{X}\in\dom(F) is analyzed (in F ) if for any constructive key-recipe r_{k} and destructor d\in\Sigma_{d} , if d applies to (F(\mathcal{X}),F(r_{k})) , there exists an entry \mathcal{X}^{\prime}\leftarrow d(\mathcal{X},r_{k}^{\prime})\mapsto t where F(r_{k})=_{E}F(r_{k}^{\prime}) . Furthermore, for the associated verifier v there must be an entry v(\mathcal{X},r_{k}^{\prime})\doteq\top . A frame F is fully analyzed if all labels in \dom(F) are analyzed. Note that since F is well-formed, we must have t=_{E}d(F(\mathcal{X}),F(r_{k})) . When all the subterms have been added to a frame, we can obtain any obtainable term by composition , i.e. a constructive recipe. The following recursive function returns all constructive recipes for a given term: Definition 7 . We define \mathit{compose}(F,t)=\bigcup\{\mathit{compose}_{lc}(F,s)\mid s\in[t]_{=B}\} where \mathit{compose}_{lc}(F,s)=\mathit{compose}_{l}(F,s)\cup\mathit{compose}_{c}(F,s) , \mathit{compose}_{l}(F,s)=\{\mathcal{X}|\mathcal{X}\in\dom(F)\land F(\mathcal{X})=s\} , and \mathit{compose}_{c}(F,s)=\{f(s_{1}^{\prime},\ldots,s_{n}^{\prime})\mid s_{1}^{\prime}\in\mathit{compose}(F,s_{1})\land\ldots\land s_{n}^{\prime}\in\mathit{compose}(F,s_{n})\} if s=f(s_{1},\ldots,s_{n}) for f\in\Sigma_{c} and \mathit{compose}_{c}(F,s)=\{\} otherwise. That \mathit{compose}(F,t) is finite can be seen by induction on |t| and that [t]_{=B} is finite. The following shows that for fully analyzed frames, \mathit{compose} can create any obtainable term: Lemma 4 . Assume that F is a fully analyzed frame. If there is a recipe r and a constructive term t such that F(r)=_{E}t , then we have that (1) \mathit{compose}(F,t) is non-empty, and (2) for every r_{c}\in\mathit{compose}(F,t) we have F(r_{c})=_{E}t . Proof. (1) We show that if F(r)\rightarrow_{R/B}^{*}t then there is r_{c}\in\mathit{compose}(F,t) such that F(r_{c})\rightarrow_{R/B}^{*}t . We do induction on |r| . If r=\mathcal{X} , we are done. If r=f(r_{1},\ldots,r_{n}) for f\in\Sigma_{c} , we apply the induction hypothesis and are done. If r=d(r_{1},\ldots,r_{n}) for f\in\Sigma_{d} , then either the recipe reduces and we are done by the induction hypothesis, or r=d(\mathcal{X},r_{\mathit{key}}) and there is another label \mathcal{X}^{\prime} and (by the induction hypothesis) a constructive recipe r_{\mathit{key}}^{\prime} such that F(\mathcal{X}^{\prime})=F(d(\mathcal{X},r_{\mathit{key}}^{\prime})) . (2) It is easy to prove that for every r_{c}\in\mathit{compose}_{\mathit{lc}}(F,t) we have F(r_{c})=_{E}t by induction on |t| . Furthermore, it is by definition the case that for every s\in[t]_{=B} we have s=_{E}t . ∎ The following shows completeness of \mathit{compose} : Lemma 5 . For any frame F (even if not fully analyzed), if r is a constructive recipe such that F(r)=_{E}t and t is constructive, then r\in\mathit{compose}(F,t) . Proof. Follows by induction on |r| . ∎ In the following, we define an analysis procedure that can be triggered during the projection semantics of Section III any time a new term is added the frame. For the analysis of frame F , we require a marking of the type M:\dom(F)\longrightarrow\{\star,+,\checkmark\} . All labels are initially marked \star , and whenever a label is added to the frame it is also marked \star . Definition 8 . A marking M of frame F is accurate if any label \mathcal{X}\in\dom(F) where M(X)=\checkmark is analyzed in F . Definition 9 (Analysis Procedure) . We want to calculate the analyzed extensions of a set of frames, \{F_{1},\ldots,F_{n}\} , and marking, M , where the marking is accurate for each frame and the frames are pairwise compatible. The analysis-extension function, \Ana(M,\{F_{1},\ldots,F_{n}\}) , is defined by three cases: If the given set is empty ( n=0 ), return \{\} . If there is a label \mathcal{X} marked \star , try the following in order: • F_{1}(\mathcal{X}),\ldots,F_{n}(\mathcal{X}) are all terms for which no verifier exists, then return \Ana(M[\mathcal{X}\mapsto\checkmark],\{F_{1},\ldots,F_{n}\}) . • (decomposition) We have a frame F_{i} , a verifier v\in\Sigma_{v} , and a constructive term t such that v applies to (F_{i}(\mathcal{X}),t) (for any d and F_{i}(\mathcal{X}) at most one such t exists and it is easy to find). Furthermore, \mathit{compose}(F_{i},t) is non-empty, containing at least r_{\mathit{key}} . Then, let d_{1},\ldots,d_{k} be all destructors associated with v and \mathcal{X}_{1},\ldots,\mathcal{X}_{k} fresh labels, and set r_{1}=d_{1}(\mathcal{X},r_{\mathit{key}}),\ldots,r_{k}=d_{k}(\mathcal{X},r_{\mathit{key}}) . Let M^{\prime} be the marking that for any \mathcal{X}^{\prime} returns \checkmark if \mathcal{X}=\mathcal{X}^{\prime} , \star if \mathcal{X}^{\prime}\in\{\mathcal{X}_{1},\ldots,\mathcal{X}_{k}\} or M(\mathcal{X}^{\prime})=+ , and M(\mathcal{X}^{\prime}) otherwise. Finally, let \mathit{FS}^{+}=\{F.v(\mathcal{X},r_{\mathit{key}})\doteq\top.X_{1}\leftarrow r_{1}\mapsto F(r_{1}).\,\cdots\,.X_{k}\leftarrow r_{k}\mapsto F(r_{k})\mid F\in\{F_{1},\ldots,F_{n}\}\land F(v(\mathcal{X},r_{\mathit{key}}))=_{E}\top\} and \mathit{FS}^{-}=\{F\mid F\in\{F_{1},\ldots,F_{n}\}\land F(v(\mathcal{X},r_{\mathit{key}}))\not=_{E}\top\} . We then return \Ana(M^{\prime},\mathit{FS}^{+})\cup\Ana(M,\mathit{FS}^{-}) . • Return \Ana(M[\mathcal{X}\mapsto+],\{F_{1},\ldots,F_{n}\}) . If no labels are marked \star , return \{(M,\{F_{1},\ldots,F_{n}\})\} . Note that the choice of r_{\mathit{key}} does not matter, since if multiple recipes are supposed to produce the same term but actually do not, we are not in a run of the protocol that agrees with the given frame. This will then be discovered when we later do the checks. Theorem 2 . The analysis procedure terminates. Proof. Let \mathit{raw}(F) be all the entries of the form \mathcal{X}\mapsto t (i.e. the label assignments that are not the product of analysis). Let |F|=\sum\{|t|\mid\mathcal{X}\mapsto t\in\mathit{raw}(F)\} and |\{F_{1},\ldots,F_{n}\}|=\sum_{i=1}^{n}|F_{i}| . Let |M|^{\checkmark} be the number of labels marked \checkmark in M and |M|^{+} be the number of labels marked + . Lexicographically measure (|\{F_{1},\ldots,F_{n}\}|-|M|^{\checkmark},|\{F_{1},\ldots,F_{n}\}|-|M|^{+}) . The number of labels in a marking will never exceed the number of subterms of the raw terms of the frames the marking is based on, so |\{F_{1},\ldots,F_{n}\}|-|M|^{\checkmark} and |\{F_{1},\ldots,F_{n}\}|-|M|^{+} will always be at least 0. It is easy to see that no step in the analysis makes |\{F_{1},\ldots,F_{n}\}|-|M|^{\checkmark} increase, and that each step will either decrease |\{F_{1},\ldots,F_{n}\}|-|M|^{\checkmark} or |\{F_{1},\ldots,F_{n}\}|-|M|^{+} . ∎ Theorem 3 . If F_{1},\ldots,F_{n} are compatible frames, M is an accurate marking, and \Ana(M,\{F_{1},\ldots,F_{n}\})=\{(M_{1},\mathit{FS}_{1}),\ldots,(M_{m},\mathit{FS}_{m})\} , then all frames in each \mathit{FS}_{i} are fully analyzed, pairwise compatible, and M_{1},\ldots,M_{m} are accurate. Proof. It is easy to see that the procedure preserves compatibility and accuracy of markings. When the procedure is done, no label will be marked * . If one of F_{ij} is then not fully analyzed, there must be a label \mathcal{X} , a constructive term t , and (by Lemma 5 ) a recipe r_{k}\in\mathit{compose}(F,t) , such that the (decomposition) case is applicable for \mathcal{X} (which must mean, by accuracy, that \mathcal{X} is marked + ). However, this cannot be the case, as if this r_{k} existed when the marking of \mathcal{X} was changed from \star to + then the wrong case was applied, and if it did not exist then the frame must have changed since this, which would remark \mathcal{X} as \star . ∎ After distinguishing and extending a set of frames with this procedure, defining procedures for solving the two remaining problems stated at the beginning of this section becomes easier. We start by showing that in an analyzed frame, all checks can be done in a constructive way: Lemma 6 . If F is a fully analyzed frame, then for any check r_{a}\doteq r_{b} where F(r_{a})=_{E}F(r_{b}) there exists a set of constructive checks \phi_{c} such that \bigwedge\mathit{checks}(F)\land\bigwedge\phi_{c}\models_{E}r_{a}\doteq r_{b} . If r_{a} is of the form f(r_{a}^{\prime},r_{k}) where f\in\Sigma_{v}\cup\Sigma_{d} and r_{a}^{\prime} , r_{k} and r_{b} are constructive, then there is such a \phi_{c} where for each check r_{1}\doteq r_{2}\in\phi_{c} we have that |r_{1}\doteq r_{2}|\leq\mathit{max}(2*|r_{k}|,|r_{a}^{\prime}|+|r_{b}|) . Proof. We prove the first part by induction on |r_{a}\doteq r_{b}| . The second part of the lemma can be proven by considering the cases of r_{a}^{\prime} . First, we note that the proof is immediate if it is not the case that f is a destructor or verifier that applies to (F(r_{a}^{\prime}),F(r_{k})) , and we therefore only consider this case. If r_{a}^{\prime}=\mathcal{X} where \mathcal{X} is a label, then we know that for the applicable verifier v and destructors d_{1},\ldots,d_{n} we have a constructive recipe r_{k}^{\prime} and labels \mathcal{X}_{1},\ldots,\mathcal{X}_{n} such that \{v(\mathcal{X},r_{k}^{\prime})\doteq\top,d_{1}(\mathcal{X},r_{k}^{\prime})\doteq\mathcal{X}_{1}\ldots d_{n}(\mathcal{X},r_{k}^{\prime})\doteq\mathcal{X}_{n}\}\subseteq\mathit{checks}(F) . If f=v we set \phi_{c}=\{r_{k}\doteq r_{k}^{\prime},r_{b}\doteq\top\} and are done. If f=d_{i} we set \phi_{c}=\{r_{k}\doteq r_{k}^{\prime},r_{b}\doteq\mathcal{X}_{i}\} and are done. If r_{a}^{\prime} is a composed recipe (i.e. of the form g(r_{a1}^{\prime},\ldots,r_{an}^{\prime}) ) then it must be the case that f(r_{a}^{\prime},r_{k})\rightarrow_{R}r_{a}^{\prime\prime} for some constructive recipe r_{a}^{\prime\prime} . We then set \phi_{c}=\{r_{a}^{\prime\prime}\doteq r_{b}\} and are done. ∎ Definition 10 . For a term F we define the set of all checks that hold in the frame: \phi(F)=\{r_{1}\doteq r_{2}\mid r_{1}\in\mathcal{T}(\Sigma_{p},\dom(F))\land r_{2}\in\mathcal{T}(\Sigma_{p},\dom(F))\land F(r_{1})=_{E}F(r_{2})\} We also define the set of all checks between labels and recipes we can compose: \phi_{\mathit{lc}}(F)=\{\mathcal{X}\doteq r\mid\mathcal{X}\in\dom(F)\land r\in\mathit{compose}(F,F(\mathcal{X}))\} Since a frame is finite, and for any t we have that \mathit{compose}(F,t) is finite, it must be that \phi_{\mathit{lc}}(F) is finite. We can now solve the complete set of checks problem: Theorem 4 . If F is fully analyzed, then for any r_{1}\doteq r_{2}\in\phi(F) we have \bigwedge\mathit{checks}(F)\land\bigwedge\phi_{\mathit{lc}}(F)\models_{E}r_{1}\doteq r_{2} Proof. Because of Lemma 6 we can assume that r_{1} and r_{2} are constructive. We do induction on |r_{1}\doteq r_{2}| . If either r_{1} or r_{2} is a label, we are done. If r_{1}=f(r_{11},\ldots,r_{1n}) and r_{2}=g(r_{21},\ldots,r_{2n}) , we must have f=g . Furthermore, if r_{11}\doteq r_{21},\ldots,r_{1n}\doteq r_{2n} are valid checks in F , and we apply the induction hypothesis to get checks \phi_{1},\ldots,\phi_{n} . We have \bigwedge\mathit{checks}(F)\land\bigwedge\phi_{1}\land\ldots\land\bigwedge\phi_{n}\models_{E}r_{1}\doteq r_{2} and are done. The only hard part is if r_{1}=\exp(r_{1a},r_{1b}) and r_{2}=\exp(r_{2a},r_{2b}) when F(r_{1a})\not=_{E}F(r_{2a}) or F(r_{1b})\not=_{E}F(r_{2b}) . We then have either that F(r_{1a})=_{E}\exp(s,t) and t=_{E}F(r_{2b}) or F(r_{2a})=_{E}\exp(s,t) and t=_{E}F(r_{1b}) , for some constructive s and t . We consider the former and the proof for the latter is symmetric. We get \mathit{exp}^{-1}(F(r_{1a}),F(r_{2b}))=s and \mathit{vexp}(F(r_{1a}),F(r_{2b}))=\top . From \mathit{exp}^{-1}(F(r_{1a}),F(r_{2b}))=s and Lemma 4 , we get a constructive recipe r^{\prime} such that F(r^{\prime})=s . Observe that |r^{\prime}|<|r_{1a}| . By Lemma 6 we get that there must be constructive checks \phi^{r^{\prime}} such that \bigwedge\mathit{checks}(F)\land\bigwedge\phi^{r^{\prime}}\models_{E}\mathit{exp}^{-1}(r_{1a},r_{2b})\doteq r^{\prime}\land\mathit{vexp}(r_{1a},r_{2b})=\top and for all r_{\phi}\doteq r_{\phi}^{\prime}\in\phi^{r^{\prime}} we have |r_{\phi}\doteq r_{\phi}^{\prime}|\leq\mathit{max}(2*|r_{2b}|,|r_{1a}|+|r^{\prime}|) . Since |r_{2b}|<|r_{1a}| we further have that for all r_{\phi}\doteq r_{\phi}^{\prime}\in\phi^{r^{\prime}} we have |r_{\phi}\doteq r_{\phi}^{\prime}|<|r_{1}\doteq r_{2}| . The induction hypothesis then gives a set of checks \phi^{r^{\prime}}_{lc}\subseteq\phi_{\mathit{lc}}(F) such that \bigwedge\mathit{checks}(F)\land\bigwedge\phi^{r^{\prime}}_{lc}\models_{E}\bigwedge\phi^{r^{\prime}} . Furthermore, we have that F(\exp(r^{\prime},r_{1b}))=_{E}F(r_{2a}) , which together with the induction hypothesis gives a set of checks \phi^{r_{2a}}_{lc}\subseteq\phi_{\mathit{lc}}(F) such that \bigwedge\mathit{checks}(F)\land\bigwedge\phi^{r_{2a}}_{lc}\models_{E}\exp(r^{\prime},r_{1b})\doteq r_{2a} . Combining the above with \mathit{exp}^{-1}(r_{1a},r_{2b})\doteq r^{\prime}\land\mathit{vexp}(r_{1a},r_{2b})=\top\models_{E}r_{1a}\doteq\exp(r^{\prime},r_{2b}) and r_{1a}\doteq\exp(r^{\prime},r_{2b})\land\exp(r^{\prime},r_{1b})\doteq r_{2a}\models_{E}\exp(r_{1a},r_{1b})\doteq\exp(r_{2a},r_{2b}) yields \bigwedge\mathit{checks}(F)\land\bigwedge\phi^{r^{\prime}}_{lc}\land\bigwedge\phi^{r_{2a}}_{lc}\models_{E}r_{1}\doteq r_{2} and we are done. ∎ It still remains to solve recipe composition . We have already shown that \mathit{compose} will compose a recipe for a term in a single fully analyzed frame if it exists, but it remains to be shown that we can use it to compose a recipe that will work for all given frames. To prove this, we will leverage the complete set of checks. Definition 11 . A frame F is fully checked if for any r_{1}\doteq r_{2}\in\phi(F) we have \mathit{checks}(F)\models_{E}r_{1}\doteq r_{2} . The following checking procedure simply mimics the one from Section III : Definition 12 (Checking Procedure) . We want to calculate the checked extensions of a set of frames, \{F_{1},\ldots,F_{n}\} where the frames are pairwise compatible. This is given by \Chck(\phi_{\mathit{lc}}(F_{1})\cup\ldots\cup\phi_{\mathit{lc}}(F_{n}),\{F_{1},\ldots,F_{n}\}) where \Chck is the check-extension function . \Chck(\phi,\{F_{1},\ldots,F_{n}\}) is defined by three cases: If \phi=\{\} , return \{\{F_{1},\ldots,F_{n}\}\} . If n=0 , return \{\} . If r_{1}\doteq r_{2}\in\phi , let \phi^{\prime}=\phi\setminus r_{1}\doteq r_{2} , \mathit{FS}^{+}=\{F.r_{1}\doteq r_{2}\mid F\in\{F_{1},\ldots,F_{n}\}\land F(r_{1})=_{E}F(r_{2})\} and \mathit{FS}^{-}=\{F\mid F\in\{F_{1},\ldots,F_{n}\}\land F(r_{1})\not=_{E}F(r_{2})\} , and then return \Chck(\phi^{\prime},\mathit{FS}^{+})\cup\Chck(\phi^{\prime},\mathit{FS}^{-}) This procedure is sound: Lemma 7 . If \{F_{1},\ldots,F_{n}\} is a set of compatible and analyzed frames, then every \mathit{FS}\in\Chck(\phi_{\mathit{lc}}(F_{1})\cup\ldots\cup\phi_{\mathit{lc}}(F_{n}),\{F_{1},\ldots,F_{n}\}) will contain compatible, analyzed and checked frames. Proof. It is easy to see that compatibility is preserved by the procedure, and that they are still analyzed (no terms are added to the frames). If F\in\mathit{FS} then \phi_{\mathit{lc}}(F)\subseteq\mathit{checks}(F) , and we are done by Theorem 4 . ∎ As an immediate result, we get that there is no way to distinguish the frames that are grouped together by \Chck : Lemma 8 . If F_{1},\ldots,F_{n} are compatible and fully checked frames, for any F_{i} and any check r_{1}\doteq r_{2} we have that F_{i}(r_{1})=_{E}F_{i}(r_{2}) if and only if F_{1}(r_{1})=_{E}F_{1}(r_{2})\land\ldots\land F_{n}(r_{1})=_{E}F_{n}(r_{2}) . Proof. We have F_{i}(r_{1})=_{E}F_{i}(r_{2}) if and only if \mathit{checks}(F_{i})\models_{E}r_{1}\doteq r_{2} . Furthermore, by compatibility, we have \mathit{checks}(F_{1})=\ldots=\mathit{checks}(F_{n}) . ∎ For a set of compatible, fully analyzed, and fully checked frames, the recipe composition problem is simply solved by \mathit{compose} : Theorem 5 . If F_{1},\ldots,F_{n} are compatible, fully checked, and fully analyzed frames, t_{1},\ldots,t_{n} are constructive terms, and there exists an r such that F_{1}(r)=_{E}t_{1}\land\ldots\land F_{n}(r)=_{E}t_{n} , then \mathit{compose}(F_{1},t_{1}) is non-empty and for any r^{\prime}\in\mathit{compose}(F_{1},t_{1}) we have F_{1}(r^{\prime})=_{E}t_{1}\land\ldots\land F_{n}(r^{\prime})=_{E}t_{n} . Proof. We get the non-emptiness of \mathit{compose}(F_{1},t_{1}) and that for each r^{\prime} we have F_{1}(r^{\prime})=_{E}t_{1} by Lemma 4 . Since F_{1}(r)=_{E}F_{1}(r^{\prime}) , we have by Lemma 8 that F_{2}(r)=_{E}F_{2}(r^{\prime})\land\ldots\land F_{n}(r)=_{E}F_{n}(r^{\prime}) , and are done. ∎