Aucun système n'étant infaillible, qu'est-ce qu'avoir confiance en la sécurité d'un protocole cryptographique ? C'est pouvoir prouver que le système atteint bien le niveau de sécurité promis pour une utilisation donnée, a expliqué David Pointcheval dans son allocution des rencontres INRIA-industrie. Pour cela, les chercheurs font une hypothèse, par exemple la difficulté de la factorisation, sur laquelle repose le système cryptographique. Il s'agit ensuite de démontrer que le seul moyen de casser le système cryptographique est de casser la factorisation (l'hypothèse). Si c'est le cas, le système est sûr : il est aussi difficile de casser le système cryptographique que le problème de factorisation.

La première étape de la démonstration consiste à définir et à modéliser les atouts d'un potentiel attaquant (les informations dont il dispose, ses probabilités de succès, etc.), la seconde à montrer, en simulant les interactions de l'attaquant avec l'environnement, que la seule solution à sa disposition est de casser la factorisation, ce qu'il ne peut faire en moins de 2puissance80 opérations, par exemple, avec des paramètres convenables. Un niveau qui sera ou non suffisant selon la contrainte de sécurité requise.
Traditionnellement, cette preuve est effectuée par la méthode dite par réduction mais, précise David Pointcheval, cette méthode est dure à écrire et à vérifier. Une approche récente s'appuyant sur la méthode des jeux successifs permet de simplifier cette opération. Elle consiste à modifier pas à pas l'environnement réel de départ avec les informations dont dispose l'attaquant et de montrer qu'à chaque fois l'environnement simulé n'est pas discernable du précédent. Au bout du compte, on arrive à un environnement qui met l'attaquant face à un système cryptographique idéal et donc incassable : l'attaquant ne pourrait donc pas gagner non plus dans le jeu réel.
L'avantage de cette nouvelle méthode est que l'on peut envisager de l'automatiser pour un certain nombre de preuves. Il serait également possible de compléter cette démonstration que le système est sûr (si la preuve n'aboutit pas, on ne sait pas s'il est sûr ou non) par la démonstration montrant que le système n'est pas sûr en exhibant une attaque fournie par les approches formelles. Mais là, on est déjà dans le futur !

Pour en savoir plus

Contact :
David Pointcheval
Chercheur CNRS et membre de l'équipe-projet Cascade
INRIA Paris - Rocquencourt
Mél. : David.Pointcheval@ens.fr


INédit n° 62 - janvier 2008