A survey of algebraic properties used in cryptographic protocols

Article type: Research Article

Authors: Cortier, Véronique^{a; *} | Delaune, Stéphanie^{b; c} | Lafourcade, Pascal^{c; d}

Affiliations: [a] LORIA, CNRS UMR 7503 and INRIA Lorraine project CASSIS, Campus Scientifique – BP 239, 54506 Vandoeuvre-les-Nancy cedex, France. E-mail: [email protected] | [b] France Télécom R&D, France | [c] Laboratoire Spécification et Vérification, ENS de Cachan and CNRS UMR 8643 and INRIA Futurs project SECSI, 61, avenue du Président Wilson, 94235 Cachan cedex, France. E-mail: [email protected], [email protected] | [d] LIF, Université Aix-Marseille 1 and CNRS UMR 6166, 39, r. Joliot-Curie, 13453 Marseille Cedex 13, France

Correspondence: [*] Corresponding author: Véronique Cortier, LORIA, CNRS and INRIA Lorraine project CASSIS, Campus Scientifique – BP 239, 54506 Vandoeuvre-les-Nancy cedex, France, Tel.: +33 3 83 59 30 55; Fax: +33 3 83 41 30 79; E-mail: [email protected].

Abstract: Cryptographic protocols are successfully analyzed using formal methods. However, formal approaches usually consider the encryption schemes as black boxes and assume that an adversary cannot learn anything from an encrypted message except if he has the key. Such an assumption is too strong in general since some attacks exploit in a clever way the interaction between protocol rules and properties of cryptographic operators. Moreover, the executability of some protocols relies explicitly on some algebraic properties of cryptographic primitives such as commutative encryption. We give a list of some relevant algebraic properties of cryptographic operators, and for each of them, we provide examples of protocols or attacks using these properties. We also give an overview of the existing methods in formal approaches for analyzing cryptographic protocols.

Keywords: Cryptographic protocols, algebraic properties, decidability results, exclusive or, Abelian group, modular exponentiation, elliptic curves

DOI: 10.3233/JCS-2006-14101

Journal: Journal of Computer Security, vol. 14, no. 1, pp. 1-43, 2006