There exist several automatic verification tools of cryptographic protocols, but only few of them are able to check protocols in presence of algebraic properties. Most of these tools are dealing either with Exclusive-Or (XOR) and exponentiation properties, so-called Diffie-Hellman (DH). In the last few years, the number of these tools increased and some existing tools have been updated. Our aim is to compare their performances by analysing a selection of cryptographic protocols using XOR and DH. We compare execution time and memory consumption for different versions of the following tools OFMC, CL-Atse, Scyther, Tamarin, TA4SP, and extensions of ProVerif (XOR-ProVerif and DH-ProVerif). Our evaluation shows that in most of the cases the new versions of the tools are faster but consume more memory. We also show how the new tools: Tamarin, Scyther and TA4SP, can be compared to previous ones. We also discover and understand for the protocol IKEv2-DS a difference of modelling by the authors of different tools, which leads to different security results. Finally, for Exclusive-Or and Diffie-Hellman properties, we construct two families of protocols P xori and P dhi that allow us to clearly see for the first time the impact of the number of operators and variables in the tools' performances. S 3 A [DSV03] and [CE02]. All these tools can verify one or several security properties and rely on different theoretical approaches, e.g., rewriting, solving constraints system, SAT-solvers, resolution of Horn clauses, or tree automata etc. All these tools work in the symbolic world, where all messages are represented by an algebra of terms. Moreover, they also consider the well-known Dolev-Yao intruder model [DY81], where a powerful intruder is considered [Cer01]. This intruder controls the network, listens, stops, forges, replays or modifies some messages according to its capabilities and can play several sessions of a protocol. The perfect encryption hypothesis is often assumed, meaning that without the secret key associated to an encrypted message it is not possible to decrypt the cipher-text. In such model most of the tools are able to verify two security properties: secrecy and authentication. The first property ensures that an intruder cannot learn a secret message. The authentication property means that one participant of the protocol is sure to communicate with another one. Historically, formal methods have been developed for analysing cryptographic protocols after the flaw discovered by G. Lowe [Low96] 17 years after the publication of Needham-Schoreder protocol [NS78] . The security of this protocol has been proven for one session using the BAN logic in [BAN90,BM94]. The flaw discovered by G. Lowe [Low96] works because the intruder plays one session with Alice and in the same time a second one with Bob. In this second session, Bob believes that he is talking to Alice. Then the intruder learns the shared secret key that Bob thinks that he shares with Alice. This example clearly shows that even for a protocol of three messages the number of possible combinations outpaces the humans' capabilities. In presence of algebraic properties, the number of possible combinations to construct traces blows up. The situation is even worse because some attacks can be missed. Let consider the following 3-pass Shamir protocol composed of three messages, where {m} KA denotes the encryption of m with the secret key KA: This protocol works only if the encryption has the following algebraic property: {{m} KA } KB = {{m} KB } KA . In order to implement this protocol one can use the One Time Pad (OTP) encryption, also known as Vernam encryption because it is generally credited to Gilbert S. Vernam and Joseph O. Mauborgne, but indeed it was invented 35 years early by Franck Miller [Bel11]. The encryption of the message m with the key k is m ⊕ k. This encryption is perfectly secure according to Shanon information theory, meaning that without knowing the key no information about the message is leaked [Vau05,BJL + 10]. Moreover the OTP encryption is key commutative since: {{m} KA } KB = (m ⊕ KA) ⊕ KB = (m ⊕ KB) ⊕ KA = {{m} KB } KA . Unfortunately combining the
More recently, Lafourcade and Puys REF focus on performance analysis of a number of tools including a ProVerif extension and analysis of 21 cryptographic protocols dealing with Exclusive-Or (xor) and exponentiation properties like Diffie-Hellman (DH).
Performance Evaluations of Cryptographic Protocols Verification Tools Dealing with Algebraic Properties
FPS
Computer Science