Preuve de sécurité

Une manière d’effectuer une réduction de sécurité consiste à effectuer une réduction polynomiale des hypothèses de difficulté vers les notions de sécurité à prouver. C’est le cas par exemple de la preuve du cryptosystème d'ElGamal, ou du cryptosystème de Goldwasser-Micali.

En sécurité prouvable, on mesure la qualité d’un attaquant par son avantage, c'est-à-dire la probabilité qu’il réussisse à casser une propriété de sécurité (par exemple produire un faux pour les signatures numériques). Lors d’une réduction de sécurité on part d’un attaquant contre la propriété de sécurité, ayant donc un avantage supposé, et l’on arrive à un attaquant contre une hypothèse de sécurité, avec un avantage polynomialement plus faible. C'est l'étude de ce polynôme qui est importante, puisque dans un système pluri-utilisateur, il se peut que la réduction dépende du nombre d’utilisateurs, une méthode générique classique étant par exemple de deviner quel utilisateur va être attaqué par l’adversaire pluri-utilisateur avant d’appliquer la sécurité du système à utilisateur unique sur cet utilisateur cible. Cela donne pour un avantage supposé ε pour le système à utilisateur unique un avantage de ${\displaystyle \varepsilon /|{\text{utilisateurs}}|}$[6], ce qui signifie que pour le réseau internet, il y a en 2016 une perte de sécurité de l’ordre de 2⁴¹[7], ce qui fait que pour une sécurité multi-utilisateur de 80 bits, il faut une sécurité simple utilisateur de 121 bits, ce qui fait grandir la taille des clefs en conséquence (par exemple la taille des nombres premiers choisis pour la Signature RSA, et par conséquent la taille de la signature).

Travailler à avoir une meilleure estimation de la perte de sécurité permet ainsi d’améliorer notre connaissance de la sécurité des systèmes cryptographiques, et dans le meilleur cas (une perte de sécurité constante), les cryptologues disent que la preuve est fine[8].

Une preuve par jeu est parfois utilisée lorsque la définition de sécurité est donnée par un jeu cryptographique que doit gagner l’adversaire. C’est le cas par exemple de la sécurité sémantique des schémas de chiffrements. Le but étant de passer étapes par étapes du jeu originel que doit gagner l’attaquant, de le transformer étape par étape en un jeu que l’adversaire ne peut pas gagner, par exemple parce qu’il revient à résoudre un problème difficile ou parce qu’il n’y a plus d’informations sur le message initial. Le passage d’une étape à la suivante ne peut changer l’avantage et le point de vue de l’adversaire que de manière négligeable par rapport au jeu précédent. De telle manière qu’en appliquant les différentes transformations, on se retrouve avec un jeu que l’adversaire est incapable de gagner, à une distance négligeable de la notion de sécurité que l’on souhaite démontrer.

L’avantage de telles preuves est qu’elles sont faciles à vérifier, étant donné que les passages d’une étape à la suivante sont explicitées, et l’argument peut donc être vérifié pas à pas.On peut de plus étapes par étapes borner l’avantage de l’adversaire pour évaluer avec précision le facteur d’approximation de la réduction[9].

On peut ainsi reformuler la preuve du cryptosystème d’ElGamal par des jeux cryptographiques.

Dans ce qui suit, la relation « ${\displaystyle \approx }$ » signifie que deux distributions sont statistiquement ou calculatoirement proches ; et Adv_i désigne l’avantage de l’adversaire. Pour la sécurité sémantique il s’agit de la quantité ${\displaystyle Adv=\left|{\frac {1}{2}}-\Pr[{\mathcal {A}}{\mbox{ gagne}}]\right|}$.

• Jeu 0: La sécurité sémantique du schéma. Le challenger commence par générer la paire de clefs et envoie pk = (G, q, g, h=g^a) à l’attaquant. L’attaquant renvoie alors deux message m₀ et m₁. Le challenger tire alors un bit σ à pile ou face et renvoie à l'attaquant un chiffré de m_σ : ${\displaystyle C=(m_{\sigma }\cdot h^{b},g^{b})}$. L’adversaire renvoie alors un bit σ’ et gagne si et seulement si σ = σ’.
• Jeu 1: Comme le choix de σ est indépendant de la vue de l’attaquant, on change ici le challenger pour qu’il tire le bit σ avant d’avoir vu les message. Rien n’a changé, Adv₀ = Adv₁.
• Jeu 2: En utilisant l'hypothèse de décision de Diffie-Hellman qui dit que ${\displaystyle (g,g^{a},g^{b},g^{ab})\approx (g,g^{a},g^{b},g^{c})}$ pour a, b, c tirés uniformément dans ℤ_q, on peut remplacer le chiffré C par ${\displaystyle (m_{\sigma }\cdot g^{c},g^{b})}$. On a utilisé l’hypothèse de sécurité du problème de décision de Diffie-Hellman, ici ${\displaystyle \scriptstyle |Adv_{2}-Adv_{1}|\ \leq \ Adv^{DDH}}$.
• Jeu 3 Désormais g^c est indépendant de la clef publique, et cache donc complètement le message. Sans aucune autre hypothèse, on peut donc remarquer que ${\displaystyle m_{\sigma }\cdot g^{c}\approx g_{r}}$ pour ${\displaystyle g_{r}}$ suivant une distribution uniforme dans G. On peut donc remplacer C par ${\displaystyle (g_{r},g^{b})}$, qui constitue un chiffré complètement aléatoire et indépendant du bit σ. Dans ce jeu encore, la distribution des chiffrés par rapport au jeu précédent reste inchangée : Adv₃ = Adv₂.

Finalement on remarque que le jeu 3 ne peut pas être gagné par aucun adversaire avec une probabilité différente de 1/2. De plus la seule transformation faisant varier cette probabilité est le Jeu 2, où on utilise l’argument calculatoire de décision de Diffie-Hellman. Ce qui signifie qu’au total l’avantage d’un adversaire contre ce schéma est borné par l’avantage d’un adversaire face à DDH ; en effet

${\displaystyle {\begin{aligned}Adv_{0}&=|Adv_{3}-Adv_{0}|\\&=|Adv_{3}-Adv_{2}+Adv_{2}-Adv_{1}+Adv_{1}-Adv_{0}|\\&\leq |Adv_{3}-Adv_{2}|+|Adv_{2}-Adv_{1}|+|Adv_{1}-Adv_{0}|\\&=0+Adv^{DDH}+0=Adv^{DDH}\end{aligned}}}$

Les problèmes utilisés par la cryptographie sont tous dans NP : il est « facile » de coder un message, ou de décoder un message quand on en possède la clé. En revanche, en l'état actuel des connaissances, toutes les méthodes existantes pour casser ces codes sont exponentielles en la taille de la clé. C'est la disproportion pratique entre le temps de codage ou décodage avec clé d'une part, et de cassage d'autre part, qui rend les méthodes utiles.

Il n'y a pour l'instant pas d'objection théorique à l'existence d'algorithmes polynomiaux de cassage des codes utilisés actuellement, mais juste le constat pratique que ces problèmes résistent aux efforts soutenus de la communauté depuis suffisamment longtemps. Notons par ailleurs que les ordinateurs quantiques, si on arrive à en construire de « taille » (nombre de qbits) suffisante, permettraient de casser des systèmes comme RSA via l’algorithme de Shor.

Enfin, il est important de noter que les preuves de sécurité sont à prendre avec précaution[11]. Par exemple, un système que l'on doit à Ajtai et Dwork, accompagné d'une preuve de sécurité théorique supposant un certain problème difficile, s'est retrouvé cassé en pratique par Phong Nguyen et Jacques Stern[12].

• [Bellare, Micciancio et Warinschi 2003] (en) Mihir Bellare, Daniele Micciancio et Bogdan Warinschi, « Foundations of Group Signatures: Formal Definitions, Simplified Requirements, and a Construction Based on General Assumptions », Eurocrypt,‎ 2003, p. 614–629 (DOI 10.1007/3-540-39200-9_38)
• [Chatterjee, Menezes et Sarkar 2012] Sanjit Chatterjee, Alfred Menezes et Palash Sarkar, « Another Look at Tightness », Selected Area in Cryptography (SAC),‎ 2012 (DOI 10.1007/978-3-642-28496-0_18, lire en ligne)
• [Chaum et van Heyst 1991] (en) David Chaum et Eugène van Heyst, « Group Signatures », Eurocrypt,‎ 1991, p. 257–265 (DOI 10.1007/3-540-46416-6_22)
• [Degwekar, Vaikuntanathan et Vasudevan 2016] Akshay Degwekar, Vinod Vaikuntanathan et Prashant Nalini Vasudevan, « Fine-grained Cryptography », Crypto,‎ 2016 (DOI 10.1007/978-3-662-53015-3_19, lire en ligne)
• [Galbraith, Malone-Lee et Smart 2002] Steven Galbraith, James Malone-Lee et Nigel P. Smart, « Public key signatures in the multi-user setting », Information Processing Letters,‎ 2002 (DOI 10.1016/S0020-0190(01)00338-6)
• [Koblitz et Menezes 2004] (en) Neal Koblitz et Alfred Menezes, « Another Look at “Provable Security” », iacr ePrint reports,‎ 2004 (lire en ligne)
• [Lamport 1979] (en) Leslie Lamport, « Constructing digital signatures from a one-way function », Technical Report CSL-98,‎ 1979 (lire en ligne)
• [Nguyen et Stern 1998] (en) Phong Nguyen et Jacques Stern, « Cryptanalysis of the Ajtai-Dwork cryptosystem », Crypto,‎ 1998 (DOI 10.1007/BFb0055731)
• [Shannon 1949] (en) Claude Shannon, « Communication theory of secrecy systems », Bell System Technical Journal,‎ 1949 (lire en ligne)
• [Shoup 2006] (en) Victor Shoup, « Sequences of games: a tool for taming complexity in security proofs », iacr ePrint report,‎ 2006 (lire en ligne)

• Cryptanalyse
• Argument hybride