BIKE implementation : vulnerabilities and countermeasures

Mise en œuvre de BIKE, vulnérabilités et contre-mesures BIKE est un schéma d'encapsulation de clés (KEM) post-quantique sélectionné pour le quatrième tour de la campagne de standardisation du NIST. Sa sécurité repose sur la robustesse du problème de décodage du syndrome pour les codes quasi-cycliques et fournit des performances compétitives par rapport aux autres candidats du 4e tour, ce qui le rend pertinent pour une utilisation dans des cas concrets. La communauté scientifique a fortement encouragé l'analyse de sa résistance aux attaques par canaux auxiliaires et plusieurs travaux ont déjà souligné diverses faiblesses. Pour les corriger, ces derniers ont proposé des contre-mesures ad hoc. Toutefois, contrairement à la ligne de recherche bien documentée sur le masquage des algorithmes basés sur les réseaux, la possibilité de protéger génériquement les algorithmes basés sur des codes par du masquage n'a été étudiée que de manière marginale dans un article de 2016 de Cong Chen et al. À ce stade de la campagne de standardisation, il est important d'évaluer la possibilité de masquer entièrement le schéma BIKE et le coût qui en résulte en termes de performances. L'objectif de cette thèse est donc de proposer un algorithme de BIKE dont la sécurité a été prouvée, en réalisant l'ensemble du processus de manière masquée, et ce sans jamais manipuler directement les données sensibles. Pour ce faire, nous utilisons des "gadgets'", qui sont des sortes de fonctions masquées, identifiées par des niveaux de non-interférence : NI (non-interference) et SNI (strong non-interference). En termes simples, SNI permet aux gadgets d'être composables : ils peuvent être appelés l'un après l'autre, avec les mêmes variables. NI, en revanche, exige plus de précautions en termes de variables manipulées. Les gadgets font l'objet de preuves, basées sur le modèle ISW, permettant de donner un véritable argument de sécurité et de robustesse à l'algorithmique. Si le schéma est prouvé sûr de bout en bout, il est a priori robuste. Il convient de noter que le masquage a été initialement développé pour les schémas symétriques et qu'il était basé sur le masquage booléen. Ce n'est que récemment que l'on a commencé à s'intéresser aux schémas asymétriques, et en particulier aux schémas basés sur les réseaux. Dans ce but, le masquage arithmétique a été le principal utilisé, bien que des conversions booléennes aient pu être effectuées pour réaliser certaines choses (comparaison de valeurs entre autres). Aujourd'hui, nous sommes en mesure de proposer une implémentation masquée de BIKE, basée sur un algorithme prouvé sûr. Comme BIKE manipule des données binaires, nous nous sommes concentrés sur le masquage booléen. Nous avons donc dû :- réutiliser les gadgets existants,- adapter et optimiser les gadgets de masquage arithmétique existants,- créer de nouveaux gadgets. A chaque fois, nous avons dû effectuer des preuves, et également prouver leur composition au sein de chaque fonction de BIKE, pour arriver à la preuve du schéma intégral. Pour rappel, BIKE repose sur des QC-MDPC, et son arithmétique est basée sur des polynômes denses et creux, il a donc fallu faire des choix concernant la représentation et la manière dont les calculs sont effectués. Nous avons donc décidé d'explorer deux voies (entièrement dense et hybride creux-dense) et de voir ce qui était le plus pertinent entre les deux. En plus de l'implémentation complète en C, des benchmarks ont été réalisés, ce qui nous a permis de voir où les performances étaient limitées et où se trouvaient les goulots d'étranglement. Au final, nous proposons un algorithme BIKE masqué intégralement et prouvé sûr, avec son implémentation en C et divers benchmarks permettant de juger de ses performances.