Keccak : le nouveau standard pour les signatures digitales

Un nouveau standard international vient d’être attribué à l’algorithme Keccak. Il sera une brique de base pour les signatures digitales.

Par Frédéric Prost.

Au début du mois d’octobre Keccak a été désigné vainqueur de la compétition ouverte en 2007 pour SHA-3 par le NIST. J’imagine que pour la plus grande partie des lecteurs la phrase précédente ne signifie pas grand chose. Le NIST est l’institut national des standard technologiques américains qui est de facto l’institut qui produit les standards mondiaux dans les domaines des TIC (Technologies de l’Information et des Communications). On lui doit par exemple l’algorithme de cryptage ‘standard’ recommandé pour l’administration américaine : AES. En l’occurrence SHA-3 est un nouveau standard qui porte également sur la sécurité informatique mais dont le but n’est pas de crypter des informations mais de fournir une brique de base pour authentifier l’information.

En effet rien ne ressemble plus à un fichier informatique qu’un autre fichier informatique comportant les mêmes informations : ce n’est pas une analyse de l’écriture qui pourra vous apporter une quelconque information. Un ‘0’ dans un fichier n’a pas d’identité, c’est une information pure. On ne peut pas ‘signer’ un fichier comme on le fait d’un contrat (ce qui est une modification physique du support de l’information que vous êtes réputez être seul à savoir faire). D’ailleurs, à l’inverse de ce qui se passe dans le monde matériel, il n’est pas non possible de savoir si quelqu’un a changé ce qui était un ‘1’ en ‘0’ que vous êtes en train de lire sur un fichier : là encore ce n’est pas comme ce qui se passe sur une feuille de papier où l’on peut toujours trouver des traces de gommage ou autres manipulations physiques ayant permis de modifier l’information. Les questions de l’intégrité (suis-je certain que l’information que je consulte n’a pas été modifiée ?) et de la signature (suis-je bien certain que l’information que je consulte a bien été produite par la personne qui est supposée l’avoir produite ?) ne sont pas évidentes et paraissent même impossibles à résoudre quand on y songe sérieusement.

Ces questions ont de multiple implications dans la vie de tous les jours. Sans que vous le sachiez, en permanence votre ordinateur quand il met à jour des programmes, par exemple, vérifie que ces derniers sont bien les bons (pour éviter qu’ils n’aient été modifiés par l’intégration de virus par exemple) : cela se fait au moyen d’un protocole de vérification de signature dont le constituant fondamental est une fonction mathématique ayant certaines spécificités et propriétés. SHA-3 est une de ces fonctions.

Intégrité et identité

Pour s’assurer qu’un document digital n’a pas été modifié il faut intégrer deux technologies : la cryptographie à clef publique et les fonctions de hachages. La cryptographie à clef publique permet à n’importe qui de crypter des informations de telle manière à ce que seuls ceux qui possèdent la clef privée (clef qu’il est quasi impossible à calculer en ne connaissant que la clef publique) sont en mesure de la décoder. Une description informelle mais plus détaillée peut se trouver dans cet article.

Pour utiliser un système à clef publique il faut commencer par produire une paire de clefs, d’une part la clef publique Kpub et la clef secrète qui lui correspond Kpriv. Nous noterons E(Kpub,m) l’encodage d’un message clair m, et E(Kpriv,mc) le décodage d’un message codé mc (les fonctions de codage et décodage sont les mêmes). Le système nous assure que décoder un message codé avec les bonnes clefs redonne bien le message original, et cela marche aussi dans l’autre sens. Mathématiquement cela correspond à l’équation suivante :

E(Kpriv,E(Kpub,m))=m=E(Kpub,E(Kpriv,m)).

On peut donc commencer par encrypter en utilisant la clef privée et ensuite ré-appliquer la fonction d’encryptage avec la clef publique, ce qui nous redonnera le message original.

Supposons qu’Alice désire envoyer un mail à Bob. Ce que Bob veut quand il va recevoir le mail c’est de s’assurer que personne ne l’a intercepté et modifié au passage. Pour cela Alice va agir de la façon suivante, si le message qu’elle veut transmettre est m elle va calculer h(m) où h est une fonction de hachage.

Une fonction de hachage calcule un « résumé ». En d’autres termes si vous imaginez que le message m est un grand chiffre de plusieurs milliers ou millions de bits. En effet chaque lettre d’un mail est codée comme une suite de 0 et 1 et n’est donc en fin de compte qu’un gros chiffre (même si le mail contient des pièces jointes elles seront elles aussi en dernier ressort codées comme un chiffre). L’image par la fonction de hachage du message, h(m), qu’on appelle l’empreinte ou le résumé de m, est un chiffre beaucoup plus petit, typiquement quelques centaine de bits au plus. L’idée d’une fonction de hachage est que si deux message sont différents alors leurs deux empreintes le seront également.

Ainsi Alice envoie le message suivant à Bob (nous notons m1;m2 la concaténation des messages m1 et m2) :

m;E(KprivA,h(m))

Donc en clair Alice calcule l’empreinte de son message et encrypte cette empreinte (avec sa clef privée qu’elle est supposée être la seule à la connaître) qu’elle envoie ainsi que son message à Bob. Quand Bob reçoit le mail d’Alice, grâce à la clef publique d’Alice il peut décrypter la deuxième partie du message. Il va trouver comme résultat un certain chiffre, disons r. Ensuite pour vérifier que le message n’a pas été modifié il va recalculer l’empreinte du message m. S’il se trouve que h(m) est égal à r alors le message n’a pas été modifié !

En effet supposons que Charlie intercepte le message d’Alice et le transforme, par exemple il écrit m2 à la place de m. Le message qu’il va transmettre à Bob sera:

m2;E(KprivA,h(m))

 Comme il ne connait pas la clef privée d’Alice, il ne peut pas calculer une fausse signature donc soit il écrit un chiffre au hasard (à ce moment-là Bob verra en essayant de décrypter cette partie du message que quelque chose ne va pas), soit il réutilise la signature d’Alice. Seulement quand Bob va calculer l’empreinte du message qu’il a reçu ce sera celle de m2 qu’il calculera et elle ne correspondra pas à l’empreinte de m du fait de la propriété des fonctions de hachage.

Les fonctions de hachage sécurisées

SHA-3 est une fonction de hachage dite sécurisée (d’où l’acronyme signifiant Secure Hash Algorithm). Pour qu’une fonction de hachage soit qualifiée comme telle il faut qu’elle présente certaines garanties supplémentaires. Il y a trois caractéristiques traditionnelles à prendre en compte. La première est le problème de préimage : il faut qu’il soit difficile, étant donnée un chiffre y, de trouver un message particulier m tel que h(m)=y. C’est à dire qu’étant donnée une empreinte, construire un message qui conduit à cette empreinte doit être compliqué. Le second problème à considérer est celui de la seconde préimage. Cette fois-ci on suppose donné un message m et la question est de trouver un autre message m2 différent de m mais qui ait la même empreinte, c’est-à-dire h(m)=h(m2). Enfin il faut que la fonction de hachage ne présente pas beaucoup de collisions. Comme l’empreinte est plus petite que les messages il est clair qu’il va exister plusieurs messages qui auront la même empreinte. Une fonction de hachage est résistante vis-à-vis des collisions s’il est très difficile de trouver deux mots m1 et m2 ayant la même empreinte.

Le concours du NIST consistait à trouver une fonction de hachage qui ait de bonnes propriétés vis-à-vis des trois points évoqués ci-dessus. C’est donc une équipe de STMicroelectronics (une firme franco-italienne, une fois n’est pas coutume nous pouvons nous laisser aller à un peu de chauvinisme) qui remporte la compétition en utilisant une architecture différente des précédents standard qui devrait rendre inopérantes certaines attaques.

Retour de flame

Tous ces problèmes pourraient sembler bien loin de la vie de monsieur et madame tout le monde. Pourtant il y a peu un super-virus a été découvert : Flame. Ce super malware n’est pas le produit d’un adolescent en mal de sensations fortes qui piraterait en fin de journée pour pimenter un peu sa vie. En effet, au cÅ“ur de ce malware se trouve une attaque par collision de MD-5 qui permet de fabriquer de fausses signatures : en fait le malware arrive à se faire passer comme une mise à jour Windows authentique en utilisant cette faille. Pour monter une attaque de ce type, il faut la participation d’une équipe de scientifiques d’un niveau mondial (ce n’est pas en bidouillant tout seul sur son ordinateur qu’on peut y arriver à l’instar de l’image d’Épinal qu’on se fait souvent du « hacker » dans les médias traditionnels). D’ailleurs il se trouve que Flame est le « moteur » du vers Stuxnet : un programme qui a infecté les ordinateurs des usines de retraitement nucléaire iraniennes. Le résultat fut notamment (en dehors des résultats d’espionnage inconnus à ce jour) le sabotage de dizaines de centrifugeuses qui, comme par hasard, s’autodétruisaient toutes seules… Ce fait divers montre comment de plus en plus des questions mathématiques fondamentales trouvent aujourd’hui leur chemin jusqu’au cÅ“ur de nos sociétés digitales.