logo EDITE Sujets de doctorat

Constructions pour la cryptographie à bas coût

Sujet proposé par
Directeur de thèse:
Doctorant: Sebastien DUVAL
Unité de recherche INRIA 0 Institut National de Recherches en Informatique et en Automatique

Domaine: Sciences et technologies de l'information et de la communication

Projet

Présentation du domaine

La cryptographie permet à plusieurs parties de communiquer de façon sécurisée en présence d'un adversaire, en fournissant notamment des outils pour garantir la confidentialité, l'intégrité, et l'authenticité des messages, ou pour vérifier l'identité des interlocuteurs. Avec le développement massif des communications, la cryptographie est aujourd'hui un outil primordial pour sécuriser les données et les transmissions.

Les algorithmes de chiffrement, visant à protéger la confidentialité des données, se répartissent en deux grandes familles : les algorithmes à clef publique, pour lesquels la clef de chiffrement peut être publique et les algorithmes à clef secrète (ou symétriques), où un même secret partagé par les deux interlocuteurs sert à chiffrer et à déchiffrer. La cryptographie à clef publique permet naturellement de résoudre le problème de distribution de clefs, mais la cryptographie à clef secrète est la seule qui offre les performances requises par la plupart des applications. En pratique, on utilise souvent des système hybrides, et tous les systèmes reposent en partie sur la sécurité des algorithmes à clef secrète.

La cryptographie à bas coût. Les algorithmes de chiffrement sont de plus en plus déployés dans des systèmes peu puissants : systèmes embarqués, cartes à puce, capteurs sans fils, objets connectés... Dans de tels environnements ne disposant que de très peu de ressources, les chiffrements standardisés comme l'AES ne peuvent généralement pas être utilisés et des algorithmes dédiés doivent être développés. Ce domaine de recherche est actuellement très actif, et de nombreux algorithmes ont été introduits en réponse à une importante demande industrielle. On peut citer par exemple NOEKEON, PRESENT, PRINCE ou les LS-Designs. Suite à ces multiples propositions, l'organisme de standardisation américain NIST organise un colloque sur la cryptographie à bas coût cet été http://www.nist.gov/itl/csd/ct/lwc_workshop2015.cfm , avec pour objectif probable à terme de lancer un processus de standardisation pour ce type d'algorithmes.

L'objectif de cette thèse est d'étudier des constructions spécialement adaptées à la cryptographie à bas coût. Elle abordera deux aspects de cette problématique :

  • la construction de fonctions internes, notamment de fonctions non-linéaires, ayant de bonnes propriétés cryptographiques et une faible complexité d'implémentation ;
  • l'analyse et la conception de modes opératoires adaptés aux chiffrements par blocs à bas coût, en particulier aux algorithmes opérant sur des blocs de petite taille.
  • Enjeux

    Construction de boîtes-S à bas coût

    La plupart des chiffrements par blocs sont construits en suivant les principes de confusion et de diffusion de Shannon. Ils alternent des opérations linéaires qui mélangent tout l'état, et des fonctions non-linéaires qui opèrent en parallèle sur des portions de cet état (typiquement sur des octets). Ces fonctions non-linéaires de petite taille sont usuellement appelées boîtes-S (par référence à l'algorithme DES). Par exemple, la seule opération non-linéaire dans le standard AES est une permutation opérant sur les octets, 16 copies de cette permutation étant utilisées à chaque itération pour transformer un état de 128 bits. La boîte-S est naturellement un composant essentiel dans le chiffrement et ses propriétés conditionnent la résistance ou la vulnérabilité du système à la plupart des attaques (cryptanalyse différentielle, cryptanalyse linéaire, cryptanalyse algébrique...).

    Dans le contexte de la cryptographie à bas coût, les boîtes-S doivent également posséder une faible complexité d'implémentation. En effet, la mise en oeuvre d'une boîte-S par le stockage en mémoire de ses valeurs devient problématique, en particulier pour des implémentations matérielles (les accès mémoire peuvent aussi poser des problèmes de sécurité face aux attaques par canaux cachés visant le cache mémoire).

    Deux types de solutions (complémentaires) peuvent alors être envisagés pour construire des boîtes-S :

    • des constructions itératives à partir de boîtes-S opérant sur moins de bits, ce qui permet de ne manipuler que des tables de
    • taille réduite. On peut par exemple construire de cette manière une boîte-S sur 8 bits en combinant des fonctions sur 4 bits et des opérations linéaires. Pour ce faire, on peut utiliser des structures qui ont déjà été étudiées pour la construction d'algorithmes de chiffrement, tel que les réseaux de Feistel, ou les structures SPN. Cette approche a été utilisée en particulier dans Misty, Whirlpool, KHAZAD, ou dans les LS-Designs. Cependant même si ces constructions ont fait l'objet de nombreuses études, l'analyse des propriétés cryptographiques (non-linéarité, uniformité différentielle...) de la boîte-S ainsi obtenue demande une étude spécifique, car dans notre contexte la construction ne fait plus intervenir de paramètre secret. Cette étude nécessite donc une analyse à clef fixée, qui peut donner des résultats très différents de l'analyse en moyenne sur les clefs effectuée classiquement. Ce type d'étude a été mené récemment pour les réseaux de Feistel, et nous avons obtenu des résultats similaires sur les réseaux Misty.
    • des constructions de boîtes-S par un circuit électronique comportant peu de portes logiques. Notons qu'un petit nombre de portes logiques est une propriété également intéressante pour la mise en oeuvre logicielle car elle permet les implémentations bitslice peu coûteuses (comme dans Serpent, NOEKEON ou les LS-designs). En particulier, les constructions avec peu de portes non-linéaires sont très avantageuses dans le cas d'implémentations protégées contre les attaques à canaux cachés en utilisant la technique du masquage. Une problématique similaire apparaît aussi lorsque le chiffrement est utilisé pour protéger les communications dans le contexte de calculs externalisés effectués au moyen de chiffrement homomorphe (cloud computing). Dans tous ces cas les opérations non-linéaires sont de très loin plus coûteuses que les opérations linéaires.
    • Une question importante est alors la détermination du nombre minimal de portes non-linéaires (ou de portes AND) nécessaire pour implémenter une boîte-S ayant des propriétés cryptographiques données. Cette question peut être abordée pour un petit nombre de variables par une exploration du type de celle effectuée pour les implémentations bitslice par De Cannière et al., mais également en tentant d'établir des liens entre certains résultats de théorie des circuits et les propriétés cryptographiques classiques.

      Les boîtes-S utilisées dans les LS-designs, ainsi que les alternatives plus intéressantes trouvées par Sébastien Duval, résultent de la combinaison de ces deux approches.

      Modes opératoires pour la cryptographie à bas coût

      Pour les implémentations matérielles, la quantité de mémoire utilisée par un algorithme est un facteur important dans le coût de l'implémentation. Pour cette raison, l'immense majorité des chiffrements par blocs à bas coût (e.g PRESENT, PRINCE) opère sur une taille de bloc de n=64 bits, alors que les algorithmes classiques comme l'AES utilisent n = 128 bits. Cela pose cependant un grave problème quand on construit un schéma de chiffrement complet avec un mode opératoire, afin de pouvoir chiffrer des messages de longueur quelconque. En effet, les modes opératoires classiques (modes compteur, CBC, CFB, OFB, GCM, OCB, ...) perdent leurs garanties de sécurité quand la quantité de données chiffrées atteint 2^n/2 blocs (i.e. 32 Go avec n=64), à cause de la présence de collisions.

      Ce problème est encore assez mal exploré: quelques constructions permettent de garantir la sécurité au delà de cette borne (beyond-birthday security), mais cela induit un coût supplémentaire important, et la sécurité obtenue atteint rarement plus de 2^2n/3. Toutefois, pour certains de ces modes, on ne sait pas si cette limite sur les données à chiffrer est due à l'existence d'une attaque ou s'il s'agit d'un artéfact résultant de la technique de preuve employée pour démontrer la sécurité de la construction. Cette question mérite par exemple d'être explorée pour la variante du mode compteur obtenue en tronquant certaines coordonnées du chiffrement par blocs. Une autre solution repose sur l'utilisation d'un chiffrement dit adaptable (tweakable) mais la construction de ce type de primitives est assez délicate. L'objectif ultime de ce travail est naturellement d'identifier ou de concevoir un mode de chiffrement ayant une sécurité proche de 2^n avec un schéma de chiffrement par bloc sur n bits, ce qui n'est pas possible avec les constructions actuelles. Nous souhaitons aussi étudier des modes récemment proposés, en particulier les soumissions à la compétition internationale Caesar, et évaluer leur sécurité. Plusieurs chiffrements candidats proposent en effet de nouveaux modes opératoires qui, pour certains, ont déjà été attaqués.

    Remarques additionnelles

    Cette thèse sera encadrée conjointement par Anne Canteaut et Gaëtan Leurent, et se déroulera au sein de l'équipe-projet SECRET.