Creating and sharing knowledge for telecommunications

Project: ComFormCrypt - Computational Semantics of Formal Methods in Cryptography

Acronym: ComFormCrypt
Main Objective:
This project addresses the problem of correct symbolic abstractions of cryptographic primitives for the purpose of symbolic, automated proving of security properties of protocols.

Computer security has been of major interest in the past two decades. This field provides both interesting research problems and important applications to everyone's life such as e-commerce and e-government, hence the need for designing better and safer security protocols. Proving security of protocols however is a difficult task that sometimes cannot be performed by hand, therefore several tools have been designed to deal with such a complex problem [B01,BMV05,P98]. But the need for such (automated) tools is not only due to the complexity of the protocols. If we consider the simple protocol proposed by Needham and Schroeder in 1978 [NS78], it was not until 1996 that Lowe discovered his famous attack on the protocol using the CSP-model checker FDR [L96] and suggested a fix. The attack used a flaw in the protocol design, the encryption itself was assumed to be perfectly secure. With this ''perfect'' cryptography assumption the protocol is simple enough to be easily analyzed by standard model-checkers and theorem provers. The fix was shown to be safe as long as encryption was perfect.

But what happens when the cryptographic primitives are not perfect, which is the case in real life where we can always guess a key with small probability? After some positive results regarding cryptographic soundness of such abstractions, Warinschi [W03] showed that the same attack discovered by Lowe against the NS protocol, could be performed against the corrected version if a somewhat weak but standard encryption scheme is used, the El-Gamal encryption scheme. This result turned the attention of the research community for the need of soundness results for formal cryptography, ie, the importance to characterize when protocols proved correct using perfect cryptography are correct when implemented with computational cryptography.

Computational soundness of formal cryptography is an active research area and members of this team have been involved in several of its fronts [ABS05,ABHS05,ABHS09,AF06,AFGZN08,BHO07,BHO09,BMS06]

Symbolic models provide abstractions for the study of cryptography that are amenable for automatic verification of complex protocols but assume ''perfect cryptography'' [DY93]. Messages, keys, encryptions, attacks, all appear as formal objects described with symbolic operations, axioms, derivation rules; cryptographic operations are modeled as functions on a space of symbolic expressions and security properties are also treated symbolically. This method ignores the probabilistic nature of encryptions. It provides a powerful way to describe how an adversary may interfere, corrupt, deceive participants of a protocol, and grab this way information not addressed to him. This method is much easier to handle mathematically than the computational, the proofs can be automated but, as the probabilistic nature is ignored, security within this framework does not necessarily mean security in the real world. Real probabilistic attacks that are outside the framework of this model may still happen [W03]

On the other hand in the computational model cryptographic operations act on strings of bit and their security properties are defined in terms of probability and computational complexity [GM84]. Computational security proofs make use of techniques of these theories; proofs have to be done by hand (ie cannot be automated) and are different for each protocol. Good protocols are those in which attackers cannot do something bad too often and efficiently enough. This is a very detailed description, closer to reality as it involves the notion of efficient computation, hence complexity and probabilities. However, even for mildly complex protocols this approach simply becomes too difficult and impossible to handle.

The unification of these two models is absolutely necessary for symbolic security proofs to be trustable. So far in the literature there are fragmented attempts done by different research groups, but as their treatment lack sound mathematical basis, the results themselves and how they are related are questionable [AR02,ABHS09,AF06,BPW03,C01,CC08,DDMST05,MW04]

We expect this research project to deliver new insights to the relationship between the symbolic and computational models, clarify the applicability and limitations of existing approaches to this problem, and provide sound mathematical foundations that can be used in the future as a common framework and technique for sound symbolic abstraction of new cryptographic primitives.

The ultimate goal of this research is to develop/adapt fully automated tools for symbolic models that, via our soundness results, entail strong cryptographic guarantees to the computational model, hence substituting the tedious complexity-theoretic proofs of computational cryptography by automated ones
Reference: PTDC/EIA-CCO/113033/2009
Funding: FCT/PTDC
Start Date: 01-02-2011
End Date: 01-07-2014
Team: Pedro Miguel dos Santos Alves Madeira Adão, Gergely István Bana, Carlos Manuel Costa Lourenco Caleiro, Paulo Alexandre Carreira Mateus, Pedro Alexandre Cardoso Baltazar, David Henriques, Andreia Filipa Torcato Mordido, Filipe Manuel Rodrigues Casal
Groups: Security and Quantum Information - Lx
Local Coordinator: Pedro Miguel dos Santos Alves Madeira Adão
Internal Page

Associated Publications
  • 6Papers in Journals
  • P. Adão, P. Mateus, L. Viganò, Protocol Insecurity with a Finite Number of Sessions and a Cost-Sensitive Guessing Intruder is NP-Complete., Theoretical Computer Science, Vol. 538, No. 1, pp. 2 - 15, June, 2014 | BibTex
  • A. M. Carvalho, P. Adão, P. Mateus, Hybrid learning of Bayesian multinets for binary classification, Pattern Recognition, Vol. 47, No. 10, pp. 3438 - 3450, April, 2014 | BibTex
  • A. M. Carvalho, P. Adão, P. Mateus, Efficient Approximation of the Conditional Relative Entropy with Applications to Discriminative Learning of Bayesian Network Classifiers, Entropy, Vol. 15, No. 7, pp. 2716 - 2735, July, 2013 | BibTex
  • D. Henriques, M. Biscaia, P. Baltazar, P. Mateus, Decidability and complexity for omega-regular properties of stochastic systems, Logic Journal of the IGPL, Vol. 20, No. 6, pp. 1175 - 1201, December, 2012 | BibTex
  • F. Assis, A. Stojanovic, P. Mateus, Y. Omar, Improving classical authentication over a quantum channel, Entropy, Vol. 14, No. 12, pp. 2531 - 2549, December, 2012 | BibTex
  • D. Basin, C. Caleiro, J. Ramos, L. Viganò, Distributed temporal logic for the analysis of security protocol models, Theoretical Computer Science, Vol. 412, No. 31, pp. 4007 - 4043, July, 2011 | BibTex
  • 6Papers in Conferences
  • P. Adão, CB Bozzato, GDR Dei Rossi, RF Focardi, FLL Luccio, Mignis: A Semantic Based Tool for Firewall Configuration, IEEE Computer Security Foundations Workshop - CSFW, Vienna, Austria, Vol., pp. 351 - 365, July, 2014 | Full text (PDF 395 KBs) | BibTex
  • P. Adão, RF Focardi, FLL Luccio, Type-Based Analysis of Generic Key Management APIs, IEEE Computer Security Foundations Workshop - CSFW, New Orleans, United States, Vol., pp. 97 - 111, June, 2013 | Full text (PDF 428 KBs) | BibTex
  • G. Bana, P. Adão, H. Sakurada, Computationally Complete Symbolic Attacker in Action, Foundations of Software Technology and Theoretical Computer Science - FSTTCS, Hyderabad, India, Vol. 18, pp. 546 - 560, December, 2012 | Full text (PDF 383 KBs) | BibTex
  • G. Bana, P. Adão, H. Sakurada, Computationally Complete Symbolic Attacker in Action, Foundations of Software Technology and Theoretical Computer Science - FSTTCS, Hyderabad, India, Vol. 18, pp. 546 - 560, December, 2012 | Full text (PDF 383 KBs) | BibTex
  • P. Adão, J. M. Mendes, Trusted Civitas: Client Trust in CIVITAS Electronic Voting Protocol, Inforum - Simpósio de Informática, Lisboa, Portugal, Vol. 0, pp. 0 - 0, September, 2012 | Full text (PDF 376 KBs) | BibTex
  • D. Basin, C. Caleiro, FAST - An efficient decision procedure for deduction and static equivalence, International Conf. on Rewriting Techniques and Applications - RTA, Novi Sad, Serbia & Montenegro, Vol. 10, pp. 11 - 20, July, 2011 | BibTex