A Theory of Dictionary Attacks and its Complexity

Stéphanie Delaune 1 Florent Jacquemard 2
2 DAHU - Verification in databases
LSV - Laboratoire Spécification et Vérification [Cachan], ENS Cachan - École normale supérieure - Cachan, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8643
Abstract : We consider the problem of automating proofs of cryptographic protocols when some data, like poorly chosen passwords, can be guessed by dictionary attacks. First, we define a theory of these attacks: we introduce an inference system modeling the guessing capabilities of an intruder. This system extends the classical Dolev-Yao rules. Using proof rewriting techniques, we show a locality lemma for our inference system which yields the PTIME-completeness of the deduction problem. This result is lifted to the simultaneous solving of intruder deduction constraints with variables. Constraint solving is the basis of a NP algorithm for the protocol insecurity problem in the presence of dictionary attacks, assuming a bounded number of sessions. This extends the classical NP-completeness result for the Dolev-Yao model. We illustrate the procedure with examples of published protocols. The model and decision algorithm have been validated on some examples in a prototype implementation.
Type de document :
Communication dans un congrès
17th IEEE Computer Security Foundations Workshop (CSFW), Jun 2004, Asilomar, Pacific Grove, United States. IEEE Computer Society Press, pp.2-15, 2004, Proceedings of the 17th IEEE Computer Security Foundations Workshop (CSFW)
Liste complète des métadonnées

Littérature citée [24 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00579014
Contributeur : Florent Jacquemard <>
Soumis le : mardi 22 mars 2011 - 23:17:07
Dernière modification le : jeudi 11 janvier 2018 - 06:22:14
Document(s) archivé(s) le : jeudi 23 juin 2011 - 03:00:00

Fichiers

DJ-csfw2004.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00579014, version 1

Collections

Citation

Stéphanie Delaune, Florent Jacquemard. A Theory of Dictionary Attacks and its Complexity. 17th IEEE Computer Security Foundations Workshop (CSFW), Jun 2004, Asilomar, Pacific Grove, United States. IEEE Computer Society Press, pp.2-15, 2004, Proceedings of the 17th IEEE Computer Security Foundations Workshop (CSFW). 〈inria-00579014〉

Partager

Métriques

Consultations de la notice

205

Téléchargements de fichiers

187