Introduite en 1984 dans cet article, la notion de sécurité sémantique peut s'expliquer comme suit : toute information obtenue à partir d'un message chiffré au sujet d'un message clair peut s'obtenir sans disposer du message chiffré.

Vers les preuves de sécurité

On est donc bien dans le domaine de la cryptanalyse, c'est à dire de la recherche de moyens de déchiffrer un message sans avoir connaissance de la clef de déchiffrement. Toute l'histoire de la cryptologie fonctionne ainsi:

  • un nouveau chiffrement est utilisé, et implémenté dans une solution logicielle ou physique
  • la solution ou le chiffrement sont attaqués, et de l'information est obtenue sur les messages échangés, ou sur l'algorithme, ou encore sur la clé utilisée.

Et comme personne n'est dupe, ce n'est pas parce qu'une direction marketing est compétente pour jurer qu'un nouvel algorithme est absolument incassable qu'il l'est vraiment. Donc, il fut question de prouver la qualité des solutions, pas seulement de chercher à la casser en investissant un effort. 

On peut tout craquer, c'est une question de temps

Réfléchissons déjà un peu. Si vous disposez de la clef publique d'un adversaire et de l'algorithme qui l'utilise, vous pouvez chiffrer les messages que vous voulez. En particulier, la méthode de la force brute qui consiste à prendre un message connu et à tester toutes les clefs privées possible va forcément fonctionner. La seule inconnue reste le temps. Et la taille des clés actuelles est conçue pour que ce temps se mesure en milliards d'années. Donc, il va falloir faire mieux, trouver une façon rapide de trouver de l'information. La formalisation de cette idée de faire mieux se base sur les algorithmes de la classe P, c'est à dire dont le temps d'exécution est un polynôme (pas trop grand si possible) sur la taille de l'entrée. Si ce polynôme est en "x carré", cela veut dire que doubler la taille de l'entrée (passer de 1024 bits à 2048 bits) va multiplier par 4  le temps de calcul. C'est pour ça qu'une preuve de difficulté ou une mesure de la complexité se base sur sa complexité, à savoir polynomiale ou pas.

Prouver un algorithme

Il existe plusieurs manières de le faire.

Technique 1 : par réduction à un problème très très compliqué. RSA par exemple part du principe qu'il est impossible de factoriser un nombre donné en ses facteurs. Sa sécurité repose donc sur un savoir mathématique et algorithmique à un moment donné. Imaginons que vous connaissiez un problème réputé insoluble en pratique, voire encore mieux, en théorie. Imaginons que vous montriez que résoudre votre problème donne un algorithme qui peut se réutiliser pour résoudre le problème très très compliqué. En quelque sorte, vous avez établi que votre problème est "plus compliqué" que le problème très très compliqué. Et vous avez une "preuve" basée sur la complexité d'un problème connu. 

Technique 2 : par les probabilités. L'idée est de dire que comme tout codage d'information se ramène à du binaire, vous avez une chance sur deux de trouver un bit à une position donnée d'un message sans aucune autre information. Si vous mettez en place un algorithme qui a la même probabilité de deviner un bit qu'un lancer de pile ou face, mais avec une heure de calcul par bit, et bien... Vous avez fait de la m...auvaise informatique. En revanche, si vous arriver à deviner un bit d'un message en clair à partir de son message chiffré avec une probabilité de 99% de bien tomber, là, là vous avez une sacrée bonne piste!

La sécurité sémantique

Cette notion de probabilité est exactement celle utilisée par la sécurité sémantique. Rappelez vous que tout algorithme par force brute va marcher, mais il met en pratique trop de temps pour être mis en oeuvre. On va donc prouver qu'aucun algorithme polynomial ne peut deviner un bit autrement que par pur hasard. En terme de probabilité, cela veut dire que la probabilité de trouver la valeur d'un bit avec cet algorithme vaut en moyenne 50% = 0.5. Toujours en terme de probabilité, si la probabilité de trouver ce bit sachant une information est la même que la probabilité de trouver ce bit sans cette information, vous comprenez bien que l'information ne vous a servi à rien. La sécurité sémantique veut traduire le fait qu'un message chiffré ne vous apporte jamais aucune information sur le message en clair à la base. Et donc, la définition informelle de la sécurité sémantique est la suivante:  toute information obtenue en temps polynomial à partir d'un message chiffré au sujet d'un message clair peut s'obtenir en temps polynomial sans disposer du message chiffré. 

Conclusion

Bon, on a lu l'article souvent, et beaucoup. On a cherché des sources externes pour cerner l'idée. Le principe de cette notion est en fait simple, sa formulation mathématique beaucoup plus complexe. En substance, un chiffrement est sémantiquement sûr (ou sécurisé sémantiquement) si, ne sachant rien d'un message en clair, vous n'apprenez rien de sa version chiffrée, et vous n'avez pas moyen de décider une partie du message autrement qu'au hasard. En pratique, vous pouvez tester si votre intuition est bonne en utilisant par exemple la clef publique de votre adversaire pour chiffrer votre essai. Donc, vous ne pouvez pas deviner le message en clair à partir d'un message chiffré, mais vous pouvez vérifier que votre essai de message donnera bien le même message chiffré. Dans le prochain article, on parlera de ces fonctions si particulières, les fonctions dite à trappe.

 

Comments are closed.

Set your Twitter account name in your settings to use the TwitterBar Section.