Cryptanalyse algorithmique avec de véritables implémentations – GORILLA

GORILLA vise à améliorer notre compréhension de la sécurité offerte par les mécanismes cryptographiques qui sécurisent données et communications, qu'ils soient déjà largement utilisés ou bien encore à un stade de développement.

Pour cela, le projet a pour but principal d'améliorer l'efficacité de certaines "attaques" cryptographiques qui visent à briser les propriétés de sécurité offertes par ces mécanismes cryptographiques.

Des mécanismes cryptographiques à clef publique, dont la signature numérique et l'échange de clef, sont nécessaires au protocole TLS pour établir des
connections sécurisées sur internet. Leur sécurité repose sur la difficulté supposée de problèmes calculatoires bien identifiés : factorisation des grands
entiers, logarithme discret dans des groupes d'entiers modulo ou sur des courbes elliptiques, résolution de système d'équations quadratiques, etc.

Des progrès algorithmiques ainsi que l'augmentation de la capacité de calcul peuvent permettre la résolution d'instances de plus en plus grandes de ces problèmes et nécessiter une réévaluation des paramètres des schémas cryptographiques correspondants. Par exemple, les clefs RSA de 1024 bits (qui étaient la norme il y a 10 ans) ne sont plus recommandées.

Ainsi, il est nécessaire de réévaluer périodiquement la difficulté concrète, et pas seulement théorique, de résoudre ces problèmes.

Le projet GORILLA s'inscrit dans cette perspective, à travers trois objectifs : premièrement, améliorer certains algorithmes utilisés dans les attaques cryptographique (ou en découvrir de nouveaux plus efficaces). Deuxièmement, produire des réalisations logicielles de haute qualité de ces attaques et les mettre dans le domaine public. Troisièmement, exécuter ces programmes avec des moyens de calcul importants.

L'existence d'implantations de références, publiques, des attaques cryptographiques (ou de certains de leurs composants principaux) est indispensable pour permettre au public (ou à d'autres chercheurs) d'évaluer et de se faire une opinion sur la sécurité des mécanismes cryptographiques. Elles peuvent certes permettre d'en casser des versions faibles, mais ces dernières ne doivent justement pas être tolérées.

Le projet se propose de d'exécuter ces programmes sur des tailles record, avec des moyens de calculs important, pour montrer en pratique leur qualité mais surtout afin de produire des démonstrations publiques de l'échelle de la faisabilité des attaques correspondantes.

Plus précisément, le projet se concentre sur quelques problèmes algorithmiques précis qui jouent un rôle important dans la sécurité des mécanismes cryptographiques actuels ou futurs.

Le projet compte d'abord améliorer certains aspects du crible algébrique (NFS), qui est le meilleur algorithme connu pour factoriser des grands entiers ou calculer des logarithmes discrets modulo p. Les améliorations envisagées visent la phase de crible ainsi que la phase d'algèbre linéaire; ils seront incorporés dans CADO-NFS, le logiciel libre de référence développé par l'INRIA.

Le projet s'intéressera ensuite à l'algorithme de recherche de collision parallèle de Van Oorschot et Wiener qui a de nombreuses applications, notamment au calcul du logarithme discret sur des courbes elliptiques. Le projet se propose d'en produire une implantation de haute qualité puis de l'utiliser pour casser le challenge Certicom ECC2K-130, qui consiste à calculer un logarithme discret sur une courbe elliptique (de Koblitz) définie sur un corps de 130 bits. Le projet compte ensuite l'utiliser pour démontrer une attaque "par le milieu" sur le double-DES, qui n'a jamais été réalisée.

Enfin, le projet abordera le problème de la résolution de systèmes d'équations booléennes quadratiques, un problème utilisé en cryptographie "post-quantique". Il s'agit de mieux comprendre le comportement d'un algorithme récent de Joux-Vitse et de le comparer avec la recherche exhaustive, puis d'atteindre un record de calcul significatif.