Hierarchical and compositional verification of cryptographic protocols

(1)

Andrea Turrini

Hierarchical and Compositional

Verification of Cryptographic

Protocols

Ph.D. Thesis

May 15, 2009

Universit`

a degli Studi di Verona

(2)

Advisor:

prof. Roberto Segala

Series N◦_{: TD-06-09}

Universit`a di Verona

Dipartimento di Informatica Strada le Grazie 15, 37134 Verona Italy

(3)

Summary

Two important approaches to the verification of security protocols are known under the general names of symbolic and computational, respec-tively. In the symbolic approach messages are terms of an algebra and the cryptographic primitives are ideally secure; in the computational approach messages are bitstrings and the cryptographic primitives are secure with overwhelming probability. This means, for example, that in the symbolic approach only who knows the decryption key can decrypt a ciphertext, while in the computational approach the probability to decrypt a cipher-text without knowing the decryption key is negligible.

Usually, the cryptographic protocols are the outcome of the interaction of several components: some of them are based on cryptographic primitives, other components on other principles. In general, the result is a complex system that we would like to analyse in a modular way instead of studying it as a single system.

A similar situation can be found in the context of distributed systems, where there are several probabilistic components that interact with each other implementing a distributed algorithm. In this context, the analysis of the correctness of a complex system is very rigorous and it is based on tools from information theory such as the simulation method that allows us to decompose large problems into smaller problems and to verify sys-tems hierarchically and compositionally. The simulation method consists of establishing relations between the states of two automata, called simu-lation resimu-lations, and to verify that such resimu-lations satisfy appropriate step conditions: each transition of the simulated system can be matched by the simulating system up to the given relation. Using a compositional approach we can study the properties of each small problem independently from the

(4)

ii

each other, deriving the properties of the overall system. Furthermore, the hierarchical verification allows us to build several intermediate refinements between specification and implementation. Often hierarchical and compo-sitional verification is simpler and cleaner than direct one-step verification, since each refinement may focus on specific homogeneous aspects of the implementation.

In this thesis we introduce a new simulation relation, that we call poly-nomially accurate simulation, or approximated simulation, that is composi-tional and that allows us to adopt the hierarchical approach in our analyses. The polynomially accurate simulations extend the simulation relations of the distributed systems context in both strong and weak cases taking into account the lengths of the computations and of the computational proper-ties of the cryptographic primitives.

Besides the polynomially accurate simulations, we provide other tools that can simplify the analysis of cryptographic protocols: the first one is the concept of conditional automaton, that permits to safely remove events that occur with negligible probability. Starting from a machine that is attackable with negligible probability, if we build an automaton that is conditional to the absence of these attacks, then there exists a simulation. And this allows us to work with the simulation relations all the time and in particular we can also prove in a compositional way that the elimination of negligible events from an automaton is safe. This property is justified by the condi-tional automaton theorem that states that events are negligible if and only if the identity relation is an approximated simulation from the automaton and its conditional counterpart. Another tool is the execution correspon-dence theorem, that extends the one of the distributed systems context, that allows us to use the hierarchical approach. In fact, the theorem states that if we have several automata and a chain of simulations between them, then with overwhelming probability each execution of the first automaton is related to an execution of the last automaton. In other words, we have that the probability that the last automaton is not able to simulate an execution of the first one is negligible.

Finally, we use the polynomially accurate simulation framework to pro-vide families of automata that implement commonly used cryptographic primitives and to prove that the symbolic approach is sound with respect to the computational approach.

(5)

Acknowledgements

The first person that I would like to thank is my advisor Roberto Segala for his precious guide and encouragement over these years.

A great thanks goes to Catuscia Palamidessi for her very kind hospitality and constant support while I was visiting the LIX at ´Ecole Polytechnique, Paris, and all members of the Com´ete and Parsifal teams.

I would also like to thank my PhD thesis referees Riccardo Focardi and Bogdan Warinschi, as well as Isabella Mastroeni and Massimo Merro for their hints and comments on my studies.

(6)

(7)

1 Introduction

1.1 Cryptography and Security

Cryptography and Security are two closely related fields of Computer Sci-ence that have a big impact on the real world. Security usually is based on cryptography, because secrecy, authenticity, anonymity and other simi-lar properties are insured by cryptographic protocols, if they respect some well-defined requirements. For example, we can say that a protocol ensures anonymity of messages if nobody, except who has generated it, is able to say who is the sender of such message. Theoretic cryptographic protocols are the base of real protocols like AES, SSL, WEP, etc. that are used for passwords storage, secure web communications, secure wireless connections and other cases where it is required some kind of secrecy or authenticity. If a theoretical protocol contains errors that make it breakable, then all real implementations can be broken exploiting such errors.

To reduce the possibility of an attack, for example that an intruder can obtain secret informations, we must be sure that at least the theoretical protocol is correct. If we are sure that this happens, then we can concentrate all our attention on protocol implementation.

We can say that a cryptographical protocol is safe only when we are able to check that any adversary is not able to attack it successfully. This requirement is really strong, since it imposes that no adversary can attack the protocol, and not only adversaries we can conceive during the analysis of the protocol.

We can classify adversaries into two big classes, based on their capabili-ties: the first one is the class of passive adversaries that can only eavesdrop messages that are transmitted between participants of the protocol. The main aim of these adversaries is to worm out some information that can be

(12)

2 1 Introduction

used for other purposes. For example, in [48] Fluhrer, Mantin and Shamir analyze the RC4 algorithm and as a side effect they show that in a wireless network protected by the WEP protocol an eavesdropper who can sniff a sufficient number of packets can then derive the WEP key. Once the ad-versary knows the key, it can collect sensible data as passwords or credit card numbers. The eavesdropper needs from one to four millions packets to obtain a 40-bit key while for a 128-bit key it spends some hours to break the WEP protocol (time depends on computational power and network load; see [108] for details).

The second class is composed by active adversaries that can interact with the protocol participants. This implies that an active attacker can intercept a message, modify it and then deliver the alterated message. The man in the middle attack is based on this capability, and protocols that are prone to this problem are, for example, SSL (during the exchange of public keys) and the Needham-Schroeder public key protocol [70,71,87].

When we start to analyze the security of a cryptographic protocol, the first thing we must consider is which kind of adversary can try to attack the protocol. We may consider only passive adversaries, for example; in this case the analysis is simpler but the guarantees are weaker. On the contrary, if we consider all adversaries, passive and active ones, then the analysis is more difficult but the guarantees are stronger. Since adversaries in the real life are usually active, then it is reasonable to prove the correctness of a protocol considering active adversaries.

The second thing we must consider when we design a new protocol is if we want to use randomization. In fact, we can define protocols that are deterministic or that involve random choices. If we decide to design our protocol using only deterministic primitives, then the proposed protocol could be prone to the replay attack, where a legal message m from the participant A can be sent to B more than once and each time B receives m, B supposes that m comes from A even when A is offline. In addition, an eavesdropper is able to understand when a message is repeated, even when it is sent encrypted. In fact, if we do not use randomization, then each time a message is encrypted, the resulting ciphertext is the same. Another problem of non-randomized protocols is the following: consider a public-key encryption scheme [49] and suppose that the set of plaintexts is prefixed and small. An adversary A can attack the protocol in the following way: it encrypts all plaintexts using the public key of a participant P producing a table with the associations cyphertext - plaintext. When another

(13)

partici-1.1 Cryptography and Security 3

pant sends a message m encrypted with the public key of P , A obtains m looking for c in the table, where c is the ciphertexts corresponding to m.

To avoid such problems, one usually uses probabilistic elements like nonces (values that are used at most once) or randomized encryptions. Probabilistic elements enforce the quality of protocols but they do not ensures that resulting protocols are actually secure. In fact, we can define protocols that are malleable [50]: given one or more valid messages, the adversary can generate a new message that is valid and that it is not one of the messages produced by the participants. RSA [100], for example, is malleable.

As we have seen, we can use random values and randomized primitives to avoid some attacks. But this implies that when analyze the correctness of a protocol we must consider also all probabilistic aspects that occur in the protocol. If we omit some subtlety about probability, then later we can discover that the protocol is flawed. Consider, for example, the problem of dining cryptographers [39]. The situation is the following: there are three cryptographers that work for NSA and there is the bill to pay. NSA can decide to pay the bill or can tell to one of cryptographers to pay. In the former, everyone knows that the bill is payed by the NSA but in the latter no one (except the cryprographer that settles the bill) knows who is the payer. To achieve this result cryptographers perform this protocol: they are around the table and each one shares a coin with each neighbor. They flip coins, so each cryptographer can see two coins but not the value of the third one and he says agree or disagree if coins he see show the same side or not. The payer lies, hence he says disagree if coins are same and agree if they are different. If the number of disagrees is odd, then a cryptographer pays the dinner, else the bill is settled by NSA. If we analyze the protocol without probability (or under the hypothesis that coins are fair), then we can affirm that it is correct because each adversary can not guess the payer with a probability that is bigger that one third. If coins are not fair, then the adversary can iterate protocol a sufficient number of times with the same payer and if it knows the probability of head of each coin (but without knowing the actual values of coin tosses), then the adversary is able to identify with high probability the cryptographer that has settled the bill.

The dining cryptographers protocol is very easy to analyze manually, without using a formal model. But there exist other protocols that are more complex and a correct manual verification is infeasible, since there are too many details to consider. This situation can lead to proofs that are not very

(14)

4 1 Introduction

rigorous and that contain informal reasoning that can be correct but that may hide problematic cases. So, if we want to be sure about cryptographic protocols correctness, it is better if we perform our analysis using a formal, rigorous model that ensures the correctness of our reasoning.

1.2 The Main Approaches of Protocol Verification

Several authors have studied the problem of cryptographic protocol ver-ification, producing a large literature. We can identify basically two ap-proaches: the first one is based on a symbolic model [3,28,45–47,57,64,65, 70,71,77,83,85,90,91,109] where messages are symbols and all underlying cryptographic components satisfy the requirements, axiomatically. Further-more, the adversary can try to attack the protocol using a restricted set of actions that usually does not include the possibility to guess secrets (such as private keys). The second approach is based on a computational model [20–22, 26, 49–55, 112] where the exchanged messages are bitstrings and the adversary is limited only to work with bounded resources. This means that it can do what it wants to messages: it can try to guess secrets and to generate new messages, as well as modify or drop received ones. 1.2.1 The Symbolic Model Approach

The start point of symbolic model approach is the paper of Dolev and Yao [46]. In this model, cryptographic primitives used by protocol are mod-eled as symbolic operations or ideal boxes, which represent the security properties of the primitives in an idealized way. This means that if we have a protocol that is based on symmetric encryption, no one is able to obtain m from the encrypted message Enc(m, k) without the knowledge of the key k. Basically, in the Dolev-Yao model, the cryptographic opera-tions are replaced by term algebras with cancellation rules. For example, the encryption operation Enc(m, k) becomes the term Ek(m) and a typical

cancellation rule is Dk(Ek( · )) =id ( · ) where Dk is the decryption term

associated with the key k and id is the identity function on messages. Dolev-Yao model was extended in many papers, e.g. [43,45,47,79], and it is used in the automatic formal protocol verification, using tools like model checkers, theorem proovers, etc. [23, 27, 56, 64, 78, 82, 83, 85, 90]. Moreover, other formalisms are developed on Dolev-Yao model, like logics [29, 57,

(15)

1.2 The Main Approaches of Protocol Verification 5

80, 81], process algebras [68], π-calculus extensions [1–3], term rewriting systems [76], strand spaces [110,111] and others [65,77].

When we prove that there exists an attack against a protocol in the Dolev-Yao model, the same attack can be used also against all real imple-mentations of the protocol, impleimple-mentations based on real cryptographic primitives. This is possible since all attacks on this model use only poly-nomial time operations that can be replayed by a feasible real attacker. Using a Dolev-Yao representation of the public key authentication protocol of Needham and Schroeder [87], Lowe [70] has discovered that the protocol is prone to the man in the middle attack and later he proposed a repaired version [71] that is secure in the Dolev-Yao model. However, a correctness proof in the symbolic model is not enough to be sure that the protocol is correct when it is implemented using actual cryptographic primitives. In fact, consider an actual encryption algorithm: it is not ideal when imple-mented, since the adversary might guess the plaintext, so it can “decrypt” a ciphertext without knowing the corresponding decryption key, and this event is not captured by the symbolic model approach. This means that an analysis in a pure symbolic model is not enough to capture all possible attacks and thus we should consider also actual cryptographic aspects. 1.2.2 The Computational Model Approach

In the computational model, also known as the cryptographic model, a pro-tocol is analyzed as it is. The correctness proofs for propro-tocols are developed mainly following one of these two directions: in the first, it is proved that the probability of an attack to the protocol is negligible (e.g., exponentially low with respect to a security parameter); in the second, it is proved that if the attacker can break the protocol with non-negligible probability, then such attack can be used against an underlying cryptographic primitive that is supposed to satisfy required properties (for example, indistinguishability of encryptions and unforgeability of signatures).

This approach is widely used in cryptographic literature [20–22, 26, 49– 55, 112] but we must be careful during the security analysis of a protocol. In fact, we must consider all possible scenarios and all adversaries to be sure that the correctness proof is complete. Moreover, we must consider all probabilistic details in the analysis, because if we omit some of them, then it is possible that we do not discover an attack when the adversary uses exactly such details to exploit an attack. The main problem in the

(16)

6 1 Introduction

correctness proofs of computational model is that this kind of proofs is hand-made, it is long and very tedious since the prover must consider a lot of different cases and particulars. So he tends to take shortcuts counting on their validity but these can lead to incorrect proofs as showed, for example, in [44,93].

Another problem is that it is quite difficult to reuse the correctness proof of one protocol inside the verification of another one. Hence, when a new protocol is developed, we must provide a complete verification, starting again from the beginning. Moreover, generally it is not possible to split proof into several steps using a hierarchical approach to analyze and verify a single cryptographic aspect at each level of the hierarchy.

1.3 A Similar Situation: The Context of Distributed System

As we have seen previously, the correctness proofs in the computational model are quite difficult and error prone. This is due to several causes, like the lack of rigour that comes from the need to take shortcuts and the im-possibility of being thorough. Another cause is that it is not so easy to take into account the interaction of several entities that are based on (proba-bilistic) cryptographic primitives or on other principles. In fact, probability is involved into the generation of nonces and cryptographic keys, the en-cryption algorithm, and possibly the signing algorithm. Other sources of probability are, for example, the adversary and the network but in this case is not so easy to know which are the actual measures that describe such sources of probability.

The analysis of systems that can be modelled as several (probabilis-tic) machine that interact with each other is a problem already studied in the context of randomized distributed algorithms [72,98,99]. In particular, there are several common aspect between cryptography and distributed al-gorithms; for example, in both cases we have to consider probabilistic and nondeterministic behaviors and the analysis is usually performed comparing the executions of two systems that behave in a similar way or transforming the execution of one system to the execution of another one that represents an attacker. One example of the last case is the analysis of indistinguishabil-ity property: given an attacker, we build another machine whose behavior is very close to the one of the original attacker and that it is able to break the indistinguishability property. One formal model that is used into the con-currency theory to model and to study randomized distributed algorithms

(17)

1.3 A Similar Situation: The Context of Distributed System 7

is the Probabilistic Automata model [73,102–106]. This model provides the mathematical rigor that is necessary to study rigorously randomized sys-tems and also provides the tools to relate executions of different syssys-tems: simulations and bisimulations allow us to compare the computations of two systems and to say if they behave in the same way or if their behaviors are not similar.

Moreover, concurrency theory allows us to prove properties of random-ized distributed algorithm in an hierarchical and compositional way: the possibility to work hierarchically permits to model the problem at several level of abstraction, and each level represents the algorithm in a more or less detailed way. This means, for example, that we can define an abstract level where for example almost all probabilistic aspects are missing and where we can focus our attention on the specification of the problem, studying its properties to see if the specification satisfies our requirements. If it is the case, then we can define other levels where we detail the single components that form the overall algorithm. The compositionality allows us to study each single component independently from the others and to extends its properties to the overall system. This means that if we prove that a com-ponent at level i is an implementation of the same comcom-ponent in the level i + 1, then we can say that the overall system at level i is an implementa-tion of the system at level i + 1. So this implies that whenever we generate a chain of implementations from the fully detailed system to the abstract system, by transitivity we can conclude that the fully detailed system is an implementation of the abstract system and thus it satisfies the same properties of the specification.

Compositionality is useful since it permits to consider small indepen-dent components instead of a big system with several interacting modules. Moreover we can reuse already known results in several proofs. So, if we already know that a functionality is implemented by a specific component, then we simply replace the functionality with it and by compositionality we derive that the new system is an implementation of the old one without proving it a second time.

In the context of distributed systems, the implementation is typically a form of behavioral inclusion: it can be based on traces, computations or traces that keep other informations like failures or tests. Failures usually are traces that are followed by actions that the system refuses to perform like the generation of forged signatures; tests are traces where a specific event occurs in an appropriate context like the generation of a repeated

(18)

8 1 Introduction

nonce. It is proved that the implementation relation has nice properties: it is transitive and compositional and moreover it has logical characterization and this permits to know which kind of properties the implementation relation preserves.

One problem of the implementation relation is that it is difficult to check. In fact, consider the case of trace inclusion: a trace of the real system can be a huge object, possibly infinite, and it could be very hard to verify if it is also a trace of the abstract system; for example, language inclusion is a PSPACE-complete problem. Fortunately, the simulation and bisimulation relations allow us to derive global properties of traces checking the proper-ties preserved by each computational step of the system independently from other steps like in the Hoare-style logical reasoning [60]. In fact, usually we reason about the properties that are satisfied in a state and the ones that are satisfied after performing an execution step. Then, just composing all reasoning we derive the properties that are valid in the global trace.

1.4 Our Proposal

As we have seen, concurrency theory and cryptography study systems that involve probabilistic behaviors and interaction between several entities and that present similar problems. Since probabilistic automata are an useful framework that help the analysis of randomized distributed system, we want to check if the probabilistic automata can help the verification of crypto-graphic protocols. To do this, we propose to use the probabilistic automata directly in the computational model and to utilize the mathematical rigor and the simulation relations of the framework to study the correctness of cryptographic protocols. We decide to model the protocol in a Dolev-Yao style [46]: participants (or agents) of the protocol are fair and they com-municate using an adversarially controlled network. The adversary tries to break the protocol generating, intercepting or modifying the messages that are sent from a participant to another one.

To verify security properties of a protocol, we would like to work hierar-chically, defining several adversaries that model different levels of security abstraction and then establishing some relation between adversaries. In particular, we would like to define an adversary that can be seen as an attacker inside the symbolic model and another adversary that stands for an attacker inside the cryptographic model. So, for example, we can have the adversary that ensures the correctness by construction (in particular,

(19)

1.4 Our Proposal 9

it represents a network that simply forwards messages between agents or it never sends messages that can break the protocol) and the adversary that represents a possible real attacker that generates messages using some (probabilistic) function on previous messages.

In the computational model, a real adversary can always generate a mes-sage that breaks the protocol: it simply chooses a random sequence of bits of the right length and if it is lucky, then such bitstring is a message that violates the protocol. Security requirements usually impose that a message generated by the adversary breaks the protocol with a negligible proba-bility with respect to some security parameter. In the symbolic model the adversary can not generate a message randomly, but it can only derive new messages from old ones, so we can not model the generation of a new ran-dom message in the symbolic model. This implies that standard simulation relations of probabilistic automata model can not be used to relate real and ideal adversaries, because a real attacker can generate messages and hence it can perform actions that an ideal adversary can not simulate. This means that we need to define a new extension of simulation relations, extension that permits to match the step condition up to some error. Moreover, we must take into account the fact that in the computational model both the security of the protocol and the computational power of the adversary de-pend on a security parameter: given a cryptographic protocol, usually its security is defined as “for each probabilistic polynomial time adversary, the probability of an attack is negligible” that means that for each constant c and polynomial p, there exists a security parameter ¯k such that for each k > ¯k if the adversary A runs for at most p(k) steps, then the probability that A performs a successful attack is less than k−_c_{. The security parameter}

usually is used to establish the length of nonces and of cryptographic keys and thus the protocol depends on such parameter. For example, consider the Needham-Schroeder-Lowe protocol [70,71,87]:

A → B : {Na.A}Eb

B → A : {Na.Nb.B}Ea

A → B : {Nb}Eb

Given the security parameter k, a concrete implementation of such proto-col can require that nonces Na, Nb belong to {0, 1}k as well as the agent

identities A and B and the encryption keys Ea and Eb.

As we have seen, in the computational model both agents and adver-saries are parameterized by a security parameter. This means that for each

(20)

10 1 Introduction

value of security parameter, we have different adversaries and agents that work always in the same way but using different values (for example, the length of nonces) and usually the security parameter is used to fix the computational power of adversaries. Hence we should extend the simula-tion relasimula-tion to consider also families of automata (and not only single automata), families that are parameterized by the security parameter. To consider the computational power of adversary, we can extend ordinary simulations adding some information about how many steps we have spent to reach a particular state of the automaton. To do this, we can base our simulation on automaton executions instead of automaton states, because an execution describes the sequence of states and actions that has led to its final state. In this way we are able to provide an upperbound to the computational power of an adversary bounding the execution lengths, that can be related to the security parameter via a polynomial, for example.

As we said previously, a real adversary can generate messages that an ideal adversary can not simulate but such messages must have negligible probability (otherwise the protocol is not secure). To consider these mes-sages, we can extend simulations permitting that the matching transition matches up to an error. If we relate such error to the security parame-ter, then we can provide an upperbound to the global error made by a real adversary with respect to an ideal adversary after a given number of steps. In this way, if we force the number of steps to be polynomial with respect to the security parameter and the step error to be negligible, then the global error is negligible and hence the protocol is secure with respect to the computational model meaning.

The main contribution of this thesis is the definition of the polynomi-ally accurate simulation relation: an extension of the simulation relation of probabilistic automata that takes into account the computational aspects of cryptographic primitives, the length of executions, and the errors we ac-cept. Main advantages of this simulation are that we can fix an upperbound to the adversary’s computational power bounding the length of executions; we can decide if the probability of unmatched executions is negligible and hence to decide if there exist attacks such that their probabilities of success are not negligible. Moreover, the verification of the protocol correctness is local, step-based and not global. In this way we can focalize our attention to a restricted set of adversarial actions and this permits to simplify the veri-fication. This holds because the check of the step condition reduces directly to the statement of correctness of the underlying cryptographic protocols

(21)

1.4 Our Proposal 11

and if we have considered enough level of abstractions, for each simulation we can analyze a single cryptographic aspect: a simulation considers only that nonces are not repeated, another considers only signs, and so on. On the contrary, when the analysis is global, we must consider all computa-tional aspects at the same time and this makes the correctness proof more difficult.

We also prove several properties of the polynomially accurate simula-tions: the first one is that it is compositional, that is given the automata A and B, if A is polynomially accurate simulated by B, then for each context C compatible with both A and B, it holds that A composed C is polynomi-ally accurate simulated by B composed C. Since the polynomipolynomi-ally accurate simulation is compositional, we can study complex cryptographic protocols as the composition of several automata that model the cryptographic prim-itives, the agents, the adversary, and so on. Moreover, the compositionality allows us to model real and ideal cryptographic primitives using automata relating them using our new simulation, defining a library of basic results that can be used in all other security analysis of cryptographic protocols without having to prove again the existence of the simulation.

Another result that is related to the hierarchical verification is the ex-ecution correspondence theorem, that extends the one of the distributed systems context. In fact, the theorem states that if we have several au-tomata and a chain of simulations between them, then with overwhelming probability each execution of the first automaton is related to an execution of the last automaton. In other words, we have that the probability that the last automaton is not able to simulate an execution of the first one is negli-gible. The execution correspondence theorem provides a formal justification of the use of the hierarchical verification of the security of cryptographic protocols: given the model of the concrete protocol, using compositionality we replace a different primitive at each level of refinement and we are sure that with overwhelming probability each execution of the concrete protocol is related to an execution of the idealized protocol.

The second main contribution of this thesis is the concept of conditional automaton that permits to safely remove events that occur with negligible probability. Starting from a machine that is attackable with negligible prob-ability, if we build an automaton that is conditional to the absence of these attacks, then there exists a simulation. And this allows us to work with the simulation relations all the time and in particular we can also prove in a compositional way that the elimination of negligible events from an

(22)

12 1 Introduction

automaton is safe. This property is justified by the conditional automaton theorem that states that events are negligible if and only if the identity rela-tion is an approximated simularela-tion from the automaton and its condirela-tional counterpart.

1.5 Related Work

As we have seen, when we adopt the symbolic model, we have rigorous proofs but we do not take into account the computational aspects; on the other hand, the cryptographic model permits to consider the computational aspects of the protocols, but proofs are quite complex and they may be not so rigorous. Hence it seems to be interesting to have a way to use rigour and simplicity of symbolic model and obtain results in the cryptographic model.

In literature there are find several papers that are focused on the proof of the soundness of symbolic analysis. This correctness is achieved using dif-ferent approaches: some author prefers to use a logic-like description of the protocol and the analysis is based on the adversary’s ability to manipulate the terms that model the exchanged messages to attack the protocol and to induce the participants to complete the protocol with the adversary without realizing that they are interacting with it and not with another participant. Once the protocol is proven to be correct within the provided model, the soundness results permit to extend the correctness to the computational model, provided that cryptographic primitives respect the hypotheses of the soundness theorems.

Other groups of authors base their papers directly in the computational model and each group provides a framework that can be used to describe the protocol. In these frameworks, the protocol, the cryptographic compo-nents and the adversary are modelled using interactive Turing machines. To prove the correctness of the protocol, two or more systems are considered: one of these systems is the composition of the protocol, the adversary, and the actual cryptographic primitives; another of these systems is the com-position of the protocol, another adversary that can be different from the first one, and the cryptographic primitives that ensure their correctness by construction. A protocol is said to be correct if it is not possible to dis-tinguish between an execution of the first system and an execution of the second system except for a negligible set of cases. All these frameworks provide a compositional theorem that permits to compose several

(23)

proto-1.5 Related Work 13

cols together or to split the analysis into several sub-problems in order to simplify the actual correctness proof reusing previous results or focusing on smaller components.

1.5.1 The Abadi and Rogaway Work

A first work on the correctness proofs is the one of Abadi and Rogaway [6,7] and subsequent works [4,62,80,81]. In these papers it is provided a formal model based on data expressions and an equivalence relation over them and the model is used to analyze the correctness of protocols that are based on symmetric encryption and the attacker is a passive adversary. Recall that a passive adversary can eavesdrop messages but it can not generate, modify or drop messages sent by participants of the protocol. Each expression represents a message that is exchanged between participants of the security protocol and such message is built up from bits and keys by pairing and encryption. The equivalence relation captures when two pieces of data “look the same” to an adversary that has no prior knowledge of the keys that are used to generate the data. The expressions are defined using a context free grammar and two expression are equivalent if their patterns are the same up to key renaming. A pattern of an expression is another expression that is the same of the original except for those encrypted components for which the key is unknown to the adversary. An example is the following: denote by K1, K2 two different keys, by ( · , · ) the pairing and by {v}k the

encryption of the value v under the key k. An adversary can recover the key K1 from the expression M = ({{(0, 1)}K2}K1, K1) and then the value

{(0, 1)}K2 but it can not obtain K2 nor (0, 1). The pattern of M is the

expression ({¤}K1, K1) where ¤ denotes an arbitrary undecryptable value.

The computational model they provide is based on indistinguishabil-ity [53, 112] over sets of strings. In particular, two distributions S1 and S2

are (computationally) indistinguishable if for each probabilistic polynomial time adversary A, |p1− p2| is negligible, where for i = 1, 2, pi is the

prob-ability that A returns 1 when it receives strings chosen accordingly to Si.

In other words, the probability that A declares that the strings are chosen accordingly to S1 when they are actually chosen from the support of S1

is essentially the same of the probability that A declares that strings are chosen accordingly to S1 instead of S2.

Given an encryption scheme and a security parameter η, Abadi and Ro-gaway show how to map an expression to a string (the map is probabilistic,

(24)

14 1 Introduction

because the used encryption scheme is probabilistic) and then they prove a soundness theorem for their formal model. Soundness theorem states that, given two acyclic expressions and a type-0 secure encryption scheme, if expressions are equivalent, then their maps into computational model are indistinguishable. An encryption scheme is type-0 secure if it does not re-veal message repetitions, which key is used in encryption and the message length; an expression E is acyclic if it is not cyclic: an expression E is cyclic if there exists a pair of keys K1, K2 that occur in E, such that there exist

two sub-expression E1, E2 of E such that E1 is encrypted with K1 and it

contains K2 as plain text and, similarly, E2 is encrypted with K2 and it

contains K1 as plain text. Cycles, such as encrypting a key under itself,

are a source of errors in practice; they also lead to weakness in common computational models.

In [6, 7], authors provide a counter example to show that formal model is not complete. Such example is based on the fact that it is possible to generate two different messages that are mapped outside the set of input messages of encryption scheme and hence they are both consider as invalid messages and they are associated to the same string set.

Other papers [59, 62, 80, 81] extend the result of Abadi and Rogaway in several ways: they consider active adversaries instead of passive ones; they provide a more meaningful counter example and a limited completeness theorem for the logic of Abadi and Rogaway. [80] presents and proves the completeness theorem under the hypothesis of acyclic expressions and type-0 confusion free encryption scheme: an encryption scheme is confusion free if for each pair of keys k1, k2, if c is the ciphertext obtained encrypting the

message m under k1 and m0 is the result of decrypting c using k2, then the

probability that m0 _{is not a failure message is negligible. Other papers [62,}

81] consider active adversaries and prove that the symbolic model is a safe abstraction of the computational one using hypothesis on the cryptographic primitives that are less restrictive than in [80]. [4] extends [6] defining a more complex language that considers a system of programs that communicate synchronously and hence proving a similar soundness theorem for the new language.

1.5.2 The Backes and Pfitzmann Work

A second work that considers the security analysis of cryptographic pro-tocols and the soundness of the symbolic approach with respect to the

(25)

1.5 Related Work 15

computational approach is the one of Backes and Pfitzmann. The authors have defined a general system model for cryptographic protocols, includ-ing a model of what adversaries and honest users can do [8, 9, 91, 92]. The model (founded on [94]) is based on reactive systems. A reactive system is a probabilistic extended finite machine which input can change during execution. Such machines are similar to the probabilistic I/O automata of Segala [102] but input actions can be ignored. To consider computational aspects, reactive systems are implemented with interactive probabilistic Turing Machines [49].

The standard way to prove the correctness of a protocol is the following: consider an adversary, a set of honest users and at least two reactive sys-tems. The adversary and the honest users can interact arbitrarily and both communicate with one of the reactive systems. In particular, one of the reactive systems is a real system that uses actual cryptographic primitives and another is an ideal system that ensures the correctness of cryptographic primitives by definition. The verification is performed checking if the com-position of adversary, honest users and the real system is as secure as the composition of another adversary, honest users and the ideal system.

The “as secure as” relation is also said reactive simulatability [95, 97] and it is defined as follows: take two systems S1, S2 with the same set H

of honest users, an adversary A1 for S1 and consider which attacks A1 can

perform against H in S1. S1 is as secure as S2 if there exists A2 for S2 such

that A2 can perform the same attacks of A1 against H essentially with the

same probability. This means that honest users are not able to distinguish when they are interacting with the first system or with the second system, except for a negligible set of cases.

The model is defined for both synchronous [95] and asynchronous [18,96, 97] cases and main results are the reactive simulatability and a composition theorem [18], that can be used to replace a sub-system A with another system B and, if A is as secure as B, the overall system does not modify its security properties.

Authors have used the model to verify security properties of protocols like integrity [11, 95], liveness [15, 16] and secrecy [13, 14] and they have also developed a cryptographic library [10,12,19] in a Dolev-Yao style that can be used to prove the correctness of protocols like the one of Needham, Schroeder and Lowe [71] and the Otway-Rees protocol [89] for efficient mutual authentication (via a mutually trusted third party).

(26)

16 1 Introduction

1.5.3 The Canetti Work

A third work that provides a tool to verify a cryptographic protocol is the one of Canetti. The main paper is [31] (together with the preliminary technical report [30]) that is extended by [36–38, 61, 88]. The Universally Composable (UC) security framework of Canetti is based on the same idea of the model of Backes and Pfitzmann: define two systems, one ideal and one real, and show that they are not distinguishable.

In particular, first it is formulated a model representing the process of protocol execution in the real-life. This is called the real-life model. Next, in order to capture the security requirements of a given task, it is formulated an ideal process for carrying out the task. It is then possible to say that a protocol securely realizes the task at hand if running the protocol in the real-life model amounts to “emulating” the ideal process for that task.

To capture the computational aspects of a protocol, the real-life model consists of a set of Interacting Turing Machines (ITMs), each one repre-senting a party involved in the protocol, plus an ITM that plays the role of the adversary. These machines are composed with another ITM that represents the environment that is whatever is external to the current pro-tocol execution, like other propro-tocols runs, other adversaries, etc. Security is proved by showing that the environment is not able not distinguish when it is composed with the adversary and the real system or when it is com-posed with another adversary and the ideal system. Multiple instances of the modelled protocol can run in parallel and the environment can inter-act with other parties not only at the beginning of the execution, but also during the protocol run.

The main result of this framework, that justifies the Universally Com-posable name, is the universal composition theorem. Standard composition theorems permit to decompose a complex task into two or more sub-tasks that are usually simpler to design and analyze. This means that once it is designed the protocols that securely realizes the sub-tasks, it is possible to provide a protocol that implements the given task assuming that the evalu-ation of the sub-task is possible. Finally, the composition theorem permits to argue that the protocol composed by the already-designed sub-protocols securely realizes the given task. The composition theorem provided in the UC security framework is used as a tool for gaining confidence about the level of security of a protocol with respect to arbitrary environments. In-deed, protocols that satisfy a UC definition are ensured to maintain their

(27)

1.5 Related Work 17

security within each protocol environment we can consider, known or un-known.

1.5.4 The Warinschi Work

Besides the previous works, in literature we find authors that provide soundness results that permit to relate the symbolic and the computa-tional model. These soundness results are very useful in the analysis of the correctness of a protocol since they permit to study the protocol in the symbolic model and then they permit to extend the results to the compu-tational case, provided that cryptographic primitives such as encryptions and signatures satisfy cryptographic assumptions like unforgeability of sig-natures or indistinguishability of encryption. We can find such results in the papers of Warinschi et al. [40–42]. In these works, authors define a lan-guage that is used to describe the protocol; then two models are provided: a formal execution one where messages are terms of an algebra, crypto-graphic primitives are correct by definition, and the attacker is a Dolev-Yao style adversary [46]; the second model is a concrete execution model where messages are bitstrings, cryptographic primitives satisfy standard require-ments, and the attacker is probabilistic polynomial time adversary that can generate, intercept, drop and modify messages. To prove the sound-ness theorem, they consider an execution of the protocol in the concrete model and then they show that with overwhelming probability it is pos-sible to map such execution into a symbolic one and that such symbolic execution is valid, that is, a symbolic adversary is able to generate it per-forming only allowed operations on the terms that represent the exchanged messages. The soundness results permit to relate several properties of the protocols, such as trace properties like entity and message authentication, and secrecy properties of nonces. Related work that obtain similar result are, for example, [6,7,17,67,81]. The main differences between these works are on the type of adversary (passive in [6, 7] and active in the other pa-pers), the number of protocol session (priorly fixed in [67]), and the kind of cryptographic primitives (symmetric encryption [6, 7, 17, 67], public key encryption [40–42,81], signatures [41,42], and hash functions [40]).

(28)

18 1 Introduction

1.5.5 Other Work

Other papers that provide tools to establish the correctness of crypto-graphic protocols are based on strand spaces, on a process calculus that is a variant of CCS or on probabilistic automata.

Strand spaces [58,110,111] are collections of strands, which are sequences of events that represent either an execution of a legitimate party of a pro-tocol or a sequence of actions of the adversary. Strands are used to model messages that each participant expects or wants to send during a protocol run; an adversary performs a successful attack when it is able to gener-ate a new, fresh message that leads a protocol participant to complete its strand. [58] presents a way to fix a security parameter to respect a given bound for the probability of successful attacks. Computational aspects are considered as they are, in an ordinary cryptographic point of view, not inside the strand spaces model.

In the process calculus defined by Mitchell et al. [68, 69, 75, 84, 86] they consider only expressions that are probabilistic polynomial time in the sense that evaluation of each process expression halts in probabilistic polynomial time. They define a probabilistic bisimulation to relate expressions, bisim-ulation based on an observational equivalence that is a standard relation from programming language theory that involves quantifying over all pos-sible environments that might interact with the protocol. The probabilistic bisimulation is used to establish a soundness result for an equational proof system based on such observational equivalences. Protocol computational aspects are captured directly in the definition of the calculus.

The last approach we consider is the one based on Probabilistic Au-tomata. The main group that works with probabilistic automata is com-posed by Canetti et al. [32–35]. They model the protocol participants as probabilistic I/O automata [72,73,102,106] and the relations between them are obtained using simulation relations [74]. Within the framework they propose, they formalize the notion of “implementing a specification” along the lines of the notion of “realizing an ideal functionality” within the uni-versally composable security framework of Canetti [30]. In particular, their idea is to assert the security of a protocol directly in a concrete model with-out abstracting the cryptographic primitives (unlike the Dolev-Yao based models). The security of a protocol usually holds only when adversaries are computationally bounded machines and only under computational as-sumptions (as happens in cryptographic models). Then, correctness of a

(29)

1.6 Overview of the Thesis 19

protocol is proved establishing a simulation between a real adversary and an automaton that ensures the ideal functionality by construction.

1.6 Overview of the Thesis

This thesis is structured as follows. In Chapter 2 we introduce some prelim-inary notions about mathematical background, probabilistic automata and cryptography that we will use throughout the thesis. In particular, we recall the concepts that are used in probability theory like measurable spaces and functions and probability measures; for probabilistic automata, we recall the definition of the automata, the parallel composition and the simulation relation, that uses the concept of lifting of relations to probability mea-sure; finally, we recall some cryptographic primitives like oracle machines, nonces, (pseudo-)random functions, message authentication codes, public key encryption schemes and public key signature schemes.

In Chapter 3 we introduce a new simulation relation, the polynomially accurate simulation. We define such simulation starting from the ordinary simulation between probabilistic automata and modifying it to take into ac-count the lengths of executions, the fact that in the computational model the adversary, the participants and the cryptographic primitives are pa-rameterized on a security parameter, and the fact that it is possible to perform some successful attack but the probability of such attack should be negligible.

In Chapter 4 we consider the relation that exists between an automaton A and its variants. In particular, we focus our attention on the automata obtained from A adding some history variable and extending its set of external actions under the hypothesis that the effect of the new actions does not interfere with the original actions. Then we define the notion of G-conditional automaton A|G that is the automaton obtained from A in the following way: each transition of A|G is a transition of A which target measure is conditioned to reach states in G. This means that the probability to reach states of A|G that belong to B = S\G is zero. Finally, we prove our Conditional Automaton Theorem: A is polynomially accurate simulated by A|G if and only if the probability to reach states in B is negligible.

In Chapter 5 we analyze the polynomially accurate simulation pointing out some limitations it presents. The first limitation is that we are not sure that it is transitive: the naive way to define transitivity does not lead to a polynomially accurate simulation but anyway we are able to prove

(30)

20 1 Introduction

the Execution Correspondence Theorem that allows us to relate executions of a family of automata to executions of another one whenever we are able to find a sequence of intermediate families of automata starting with the first family and ending with the last one that are related by a chain of simulations. The second limitation is that the polynomially accurate simulation is not compositional. We overcome this problem defining a new polynomially accurate simulation, based on states instead of on execution, that implies the approximated simulation defined on executions and that is compositional. We are able to prove the two main theorems of polynomially accurate simulation also for this new notion of simulation, so we can use the first definition or the second one according to the result we want to achieve. Finally, we extend the simulation based on states to the weak case, simply replacing the matching combined transition with a weak bounded combined transition.

In Chapter 6 we apply the two notions of polynomially accurate sim-ulations to the analysis of the cryptographic primitives. In particular, we show how the real implementation of the primitive is polynomially accu-rate simulated by its ideal counterpart. We obtain such simulations starting from the real implementation, modifying it by adding history variables and actions and taking the G-conditional automaton. If we look at this chain of automata and simulations, then we can observe that the we use the ar-gumentation about the properties of the cryptographic primitive such as negligibility of repeated nonces and unforgeability of signatures only when we consider the G-conditional automaton, where we define the set B = S\G as the set of states where an attack occur, that is, a nonce is repeated or a signature is forged.

In Chapter 7 we use the results on cryptographic primitives to study the security of the MAP1 protocol of Bellare and Rogaway [22]. In this case study, we provide two proofs that involve the polynomially accurate simulation: the first one allows us to replace the real nonce generator with its ideal counterpart and that we perform using previous results; the second one involves the message authentication codes and we directly apply the definition of polynomially accurate simulation to point out that the nega-tion of the step condinega-tion (that is the non-existence of the simulanega-tion) leads to the negation of the security property of the cryptographic primitive.

In Chapter 8 we consider a more complex case study: we recast the soundness result of Cortier and Warinschi [41] and we show how

(31)

polyno-1.6 Overview of the Thesis 21

mially accurate simulations can be used as a sanity check tool for existing proofs.

Finally, in Chapter 9 we sum up the major contributions of the thesis and we briefly describe future works that we would like to explore.

(32)

(33)

2 Preliminaries

In this chapter we recall some basic concepts that are used inside this the-sis. In particular, we recall concepts from Probability Theory, Probabilistic Automata and Cryptography.

2.1 Probability Theory

2.1.1 Measurable Spaces

Consider a set Ω. A σ-field on Ω is a set F ⊆ 2Ω _{that includes Ω and}

is closed under complement and countable union. A measurable space is a pair (Ω, F) where Ω is a set, also called sample space, and F is a σ-field over Ω. A measurable space (Ω, F) is called discrete if F = 2Ω_.

2.1.2 Probability Measures and Spaces

A measure over a measurable space (Ω, F) is a function ρ: F → R>0 _such

that, for each countable collection {Ωi}_i∈I of pairwise disjoint elements of

F, ρ(∪IΩi) = PIρ(Ωi). A probability measure over a measurable space

(Ω, F) is a measure ρ over (Ω, F) such that ρ(Ω) = 1. A sub-probability measure over (Ω, F) is a measure over (Ω, F) such that ρ(Ω) 6 1. A mea-sure over a discrete measurable space (Ω, 2Ω_{) is called a discrete measure}

over Ω. The support of a measure ρ over (Ω, F), denoted by Supp(ρ), is the set {ω ∈ Ω | ρ(ω) > 0}.

A probability space is a triple (Ω, F, ρ), where (Ω, F) is a measurable space and ρ is a probability measure on (Ω, F).

Given a set X, denote by Disc(X) the set of discrete probability sures over X, and by SubDisc(X) the set of discrete sub-probability mea-sures over X. We call a discrete probability measure a Dirac measure if it

(34)

24 2 Preliminaries

assigns measure 1 to exactly one object x (denote this measure by δx). We

also call Dirac a sub-probability measure that assigns measure 0 to all ob-jects. In the sequel discrete sub-probability measures are used to describe progress. If the measure of a sample space is not 1, then it means that with some non-zero probability the system does not progress.

Given a set X, a set G ⊆ X, and a measure ρ ∈ Disc(X) such that ρ(G) > 0, we call the measure ρ0 _{∈ Disc(X) the G-conditional measure of}

ρ, denoted by ρ|G, if for each x ∈ X,

ρ0_{(x) =}(ρ(x)/ρ(G) if x ∈ Supp(ρ) ∩ G

0 otherwise

2.1.3 Measurable Functions and Image Measures

Let (Ω1, F1) and (Ω2, F2) be two measurable spaces. A function f : Ω1 →

Ω2 is said to be a measurable function from (Ω1, F1) to (Ω2, F2) if the

inverse image under f of any element of F2 is an element of F1. In this

case, given a measure ρ on (Ω1, F1) it is possible to define a measure on

(Ω2, F2) via f, called the image measure of ρ under f and denoted by f(ρ),

as follows: for each X ∈ F2, f(ρ)(X) = ρ(f−1(X)). In other words, the

measure of X in F2 is the measure in F1 of those elements whose f-image

is in X. The measurability of f ensures that f(ρ) is indeed a well defined measure.

2.2 Relations and Lifting of a Relation to Measures

Let R1 be a relation from a set X to a set Y and R2 be a relation from

a set Y to a set Z. The composition of R1 and R2, denoted by R1 ◦ R2,

is a relation from X to Z defined as R1 ◦ R2= {(x, z) | ∃y ∈ Y.(x, y) ∈R1

∧(y, z) ∈R2}. The extension to n relation is straightforward: given n

re-lations R1, . . . , Rn such that for each 1 6 i 6 n, Ri is a relation from a

set Xi to Xi+1, the relation R1 ◦ . . . ◦ Rn is the relation from X1 to Xn+1

defined as (. . . ((R1 ◦ R2)◦ R3) ◦ . . . )◦ Rn.

Let R1 be a relation from W to X and R2 be a relation from Y to

Z. The cross-product of R1 and R2, denoted by R1 × R2, is the relation

R⊆ (W × Y ) × (X × Z) such that (w, y) R (x, z) if and only if w R1 x and

(35)

2.2 Relations and Lifting of a Relation to Measures 25

Let R be a relation from a set X to a set Y . The lifting of R, denoted by L(R) [105], is a relation from Disc(X) to Disc(Y ) such that ρx L(R) ρy

if and only if there exists a weighting function w : X × Y → [0, 1] such that 1. w(u, v) > 0 implies u R v,

2. P_u∈Xw(u, v) = ρy(v), and

3. P_v∈Y w(u, v) = ρx(u).

An alternative definition of lifting given in a more probabilistic style states that ρ1 L(R) ρ2 if and only if there exists a joint measure w with

marginal measures ρ1 and ρ2 such that the support of w is included in R.

Note that if R is an equivalence relation, then ρ1 L(R) ρ2 if and only

if, for each equivalence class C of R, ρ1(C) = ρ2(C).

The lifting of a relations has some interesting properties: Property 2.1.Let R and S be two relations.

1. x R y if and only if δx L(R) δy.

2. R= ∅ if and only if L(R)= ∅. 3. If R⊆S, then L(R)⊆L(S).

4. If R is reflexive, then L(R) is reflexive. 5. If R is symmetric, then L(R) is symmetric.

6. Let ρ1, ρ2, ρ3 be three probability measures. If ρ1 L(R) ρ2 and ρ2 L(S)

ρ3, then ρ1 L(R ◦ S) ρ3.

7. If R is transitive, then L(R) is transitive.

8. Let ρx, ρy, ρz be three probability measures. If ρx L(R) ρy, then ρx×

ρz L(R × id) ρy× ρz.

Proof. 1. Let R be a relation from X to Y .

(⇒) Define w : X × Y → [0, 1] as: for each u ∈ X, v ∈ Y , w(u, v) =(1 if u = x and v = y,

0 otherwise. w is a weighing function for δx and δy. In fact:

– w(u, v) > 0 implies that u = x and v = y and thus (u, v) = (x, y) ∈R; – for each u ∈ X, X v∈Y w(u, v) =(1 if u = x 0 otherwise

(36)

26 2 Preliminaries

By definition of Dirac measure, we have that δx(u) =(1 if u = x

0 otherwise and thus P_v∈Y w(u, v) = δx(u);

– for each v ∈ Y , X

u∈X

w(u, v) =(1 if v = y 0 otherwise By definition of Dirac measure, we have that

δy(v) =(1 if v = y

0 otherwise and thus P_u∈Xw(u, v) = δy(v).

(⇐) δxL(R) δy implies that there exists w : X × Y → [0, 1] such that

– for each u ∈ X, v ∈ Y , w(u, v) > 0 =⇒ u R v; – for each u ∈ X, δx(u) = P_v∈Y w(u, v); and

– for each v ∈ Y , δy(v) = Pu∈Xw(u, v).

For each u 6= x, we have that δx(u) = 0 and thus for each v ∈ Y ,

w(u, v) = 0. So, only for u = x we can have w(x, v) > 0. For each v 6= y, we have that δy(v) = 0 and thus for each u ∈ X, w(u, v) = 0.

This implies that only for u = x and v = y we have w(x, y) > 0 and thus x R y.

2. Let R be a relation from X to Y .

(⇒) Suppose, for the sake of contradiction, that R= ∅ while L(R)6= ∅. L(R)6= ∅ implies that there exist measures ρx ∈ Disc(X) and ρy ∈

Disc(Y ) such that ρx L(R) ρy and thus there exists a weighting

function w : X × Y → [0, 1]. Since ρx(X) = 1, then there exists

u ∈ X such that ρx(u) > 0. By condition 3 of lifting, we have that

ρx(u) = Pv∈Y w(u, v) > 0 and thus there exists v ∈ Y such that

w(u, v) > 0. By condition 1 of lifting, we have that w(u, v) > 0 implies (u, v) ∈R. This contradicts the hypothesis R= ∅ and thus R= ∅ =⇒ L(R)= ∅.

(⇐) We prove R6= ∅ =⇒ L(R)6= ∅ that is equivalent to L(R)= ∅ =⇒ R= ∅. So, suppose that R6= ∅. This implies that there exist x ∈ X, y ∈ Y such that (x, y) ∈R. By Property 1, it follows that δxL(R) δy

(37)

2.2 Relations and Lifting of a Relation to Measures 27

3. Let R, S be two relations from X to Y such that R⊆S. Let ρx ∈

Disc(X) and ρy ∈ Disc(Y ) be two measures such that ρx L(R) ρy.

This implies that there exists w : X × Y → [0, 1] such that – for each u ∈ X, v ∈ Y , w(u, v) > 0 =⇒ (u, v) ∈R; – for each u ∈ X, δx(u) = Pv∈Y w(u, v); and

– for each v ∈ Y , δy(v) = P_u∈Xw(u, v).

For each u ∈ X and v ∈ Y , if w(u, v) > 0 then (u, v) ∈R⊆S and thus (u, v) ∈S. This implies that w is also a weighting function with respect to S and thus ρx L(S) ρy. This means that for each ρx ∈ Disc(X)

and ρy ∈ Disc(Y ), if (ρx, ρy) ∈L(R) then (ρx, ρy) ∈L(S) and thus

L(R)⊆L(S).

4. Let R be a reflexive relation on X and ρ ∈ Disc(X) be a measure. Define w : X × X → [0, 1] as

w(u, v) =(ρ(u) if v = u, 0 otherwise. w is a weighting function:

– for each u, v ∈ X, w(u, v) > 0 implies that v = u and since R is reflexive, we have that (u, u) ∈R;

– for each u ∈ X, P_v∈Xw(u, v) = w(u, u) = ρ(u); – for each v ∈ X, P_u∈Xw(u, v) = w(v, v) = ρ(v).

5. Let R be a symmetric relation on X and ρ1, ρ2 ∈ Disc(X) be two

measures such that ρ1 L(R) ρ2. This means that there exists w : X ×

X → [0, 1] such that

– for each u ∈ X, v ∈ Y , w(u, v) > 0 =⇒ (u, v) ∈R; – for each u ∈ X, P_v∈Xw(u, v) = ρ1(u); and

– for each v ∈ X, P_u∈Xw(u, v) = ρ2(v).

Define w0_{: X × X → [0, 1] as w}0_{(u, v) = w(v, u) w}0 _{is a weighting}

func-tion:

– for each u, v ∈ X, w0_{(u, v) > 0 implies that w(v, u) > 0, thus v R u}

and since R is symmetric, we have that u R v; – for each u ∈ X, P_v∈Xw0_{(u, v) = P}

v∈Xw(v, u) = ρ2(u);

– for each v ∈ X, P_u∈Xw0_{(u, v) = P}

u∈Xw(v, u) = ρ1(v).

This implies that ρ2L(R) ρ1.

6. Let R, S be two relations from X to Y and from Y to Z, respectively. Let ρx ∈ Disc(X), ρy ∈ Disc(Y ), ρz ∈ Disc(Z) be three probability

measures such that ρxL(R) ρy and ρy L(S) ρz. This implies that there

(38)

28 2 Preliminaries

– for each u ∈ X, v ∈ Y , wr(u, v) > 0 =⇒ (u, v) ∈R;

– for each u ∈ X, P_v∈Y wr(u, v) = ρx(u); and

– for each v ∈ Y , P_u∈Xwr(u, v) = ρy(v).

and

– for each u ∈ Y , v ∈ Z, ws(u, v) > 0 =⇒ (u, v) ∈S;

– for each u ∈ Y , P_v∈Zws(u, v) = ρy(u); and

– for each v ∈ Z, P_u∈Y ws(u, v) = ρz(v).

Define wrs: X × Z → [0, 1] as wrs(u, v) = Pt∈Y,ρy(t)6=0

wr(u, t)ws(t, v)

ρy(t) .

wrs is a weighting function:

– for each u ∈ X and v ∈ Z, since wrs(u, v) > 0 we have that

P

t∈Y,ρy(t)6=0

wr(u, t)ws(t, v)

ρy(t) > 0 and thus there exists q ∈ Y such

that ρy(q) 6= 0 and wr(u, q)w_ρ s(q, v)

y(q) > 0. Since ρy is a probability

measure, it follows that ρy(q) ° 0 and thus wr(u, q)ws(q, v) > 0 that

implies wr(u, q) > 0 and ws(q, v) > 0. Hence we have that (u, q) ∈R

and (q, v) ∈S and thus (u, v) ∈R ◦ S; – for each u ∈ X, X v∈Z wrs(u, v) =X v∈Z X t∈Y,ρy(t)6=0 wr(u, t)ws(t, v) ρy(t) = X t∈Y,ρy(t)6=0 X v∈Z wr(u, t)ws(t, v) ρy(t) = X t∈Y,ρy(t)6=0 wr(u, t) ρy(t) X v∈Z ws(t, v) = X t∈Y,ρy(t)6=0 wr(u, t) ρy(t) ρy(t) = X t∈Y,ρy(t)6=0 wr(u, t) =X t∈Y wr(u, t) = ρx(u)

We can remove the condition on ρy(t) 6= 0 from the

summa-tion since by definisumma-tion of weighting funcsumma-tion, if ρy(t) = 0, then

P

(39)

2.2 Relations and Lifting of a Relation to Measures 29 – for each v ∈ Z, X u∈X wrs(u, v) = X u∈X X t∈Y,ρy(t)6=0 wr(u, t)ws(t, v) ρy(t) = X t∈Y,ρy(t)6=0 X u∈X wr(u, t)ws(t, v) ρy(t) = X t∈Y,ρy(t)6=0 ws(t, v) ρy(t) X u∈X wr(u, t) = X t∈Y,ρy(t)6=0 ws(t, v) ρy(t) ρy(t) = X t∈Y,ρy(t)6=0 ws(t, v) =X t∈Y ws(t, v) = ρz(v)

We can remove the condition on ρy(t) 6= 0 from the sum since by

definition of weighting function, if ρy(t) = 0, then Pv∈Zws(t, v) = 0

and thus for each v ∈ Z, ws(t, v) = 0.

This implies that wrs is a weighting function from ρx to ρz and thus

ρx L(R ◦ S) ρz.

7. Let R be a transitive relation on X and let ρ1, ρ2, ρ3 ∈ Disc(X) be

three probability measures such that ρ1 L(R) ρ2 and ρ2 L(R) ρ3. By

the Property 6, we have that ρ1 L(R ◦ R) ρ1. If R ◦ R⊆R, then by

Property 3 we have that ρ1 L(R) ρ3, as required. So, let x, z ∈ X be two

states such that (x, z) ∈R ◦ R. By definition of composition, it follows that there exists y ∈ X such that (x, y) ∈R and (y, z) ∈R. Since R is transitive, we have that (x, z) ∈R and thus R ◦ R⊆R.

8. Let R be a relation from X to Y and id be the identity relation on Z. Let ρx, ρy, ρz be three probability measures in Disc(X), Disc(Y ), and

Disc(Z), respectively. Suppose that ρx L(R) ρy. This implies that there

exists a weighting function w : X × Y → [0, 1] such that – for each u ∈ X, v ∈ Y , w(u, v) > 0 implies u R v, – for each u ∈ X, P_v∈Y w(u, v) = ρx(u), and

– for each v ∈ Y , P_u∈Xw(u, v) = ρy(v).

(40)

30 2 Preliminaries

w0_{((u, s), (v, t)) =}(w(u, v)ρz(s) if u R v and s id t

0 otherwise

w0 _{is a weighting function from ρ}

x× ρz to ρy× ρz. In fact,

– for each (u, s) ∈ X × Z, (v, t) ∈ Y × Z, w0_{((u, s), (v, t)) > 0 implies}

u R v and s id t and thus (u, s) R × id (v, t), – for each (u, s) ∈ X × Z,

X (v,t)∈Y ×Z w0_{((u, s), (v, t)) =} X (v,t)∈Y ×Z,uRv,sidt w(u, v)ρz(s) = ρz(s) X v∈Y,uRv w(u, v) = ρz(s)X v∈Y w(u, v) = ρz(s)ρx(u) = ρx× ρz(u, s) – for each (v, t) ∈ Y × Z, X (u,s)∈X×Z w0_{((u, s), (v, t)) =} X (u,s)∈X×Z,uRv,sidt w(u, v)ρz(s) = ρz(t) X u∈X,uRv w(u, v) = ρz(t)X u∈X w(u, v) = ρz(t)ρy(v) = ρy× ρz(v, t) u t 2.3 Compatible Mappings

Let σ : X → Y be a partial mapping function. We denote by Dom(σ) the set of all x ∈ X such that σ(x) is defined.

Two partial mapping functions σ : X → Y and σ0_{: X}0 _{→ Y}0 _are

com-patible if and only if for each x ∈ Dom(σ) ∩ Dom(σ0_{), σ(x) = σ}0_(x).

In other words, two mappings are compatible if they assign the same value to the common points.

Hierarchical and compositional verification of cryptographic protocols

Andrea Turrini