BIKE implementation : vulnerabilities and countermeasures
Mise en œuvre de BIKE, vulnérabilités et contre-mesures
Résumé
BIKE is a post-quantum key encapsulation scheme (KEM) selected for the fourth round of the NIST standardization campaign. Its security is based on the robustness of the syndrome decoding problem for quasi-cyclic codes, and provides competitive performance with the other candidates in the 4th round, making it relevant for use in real-life cases. The scientific community has strongly encouraged analysis of its resistance to auxiliary channel attacks, and several works have already highlighted various weaknesses. To correct them, the latter have proposed ad hoc countermeasures. However, in contrast to the well-documented line of research on masking latice-based algorithms, the possibility of generically protecting code-based algorithms through masking has only been marginally investigated in a 2016 paper by Cong Chen et al. At this stage of the standardization campaign, it is important to evaluate the possibility of fully masking the BIKE scheme and the resulting cost in terms of performance. The aim of this thesis is therefore to propose a BIKE algorithm whose security has been proven, by carrying out the entire process in a masked way, without ever directly manipulating sensitive data. To achieve this, we use "gadgets", which are masked functions identified by levels of non-interference: NI (non-interference) and SNI (strong non-interference). In simple terms, SNI allows gadgets to be composable: they can be called one after the other, with the same variables. NI, on the other hand, requires greater care in terms of the variables manipulated. Gadgets are the subject of proofs, based on the ISW model, giving a real argument of safety and robustness to the algorithmic. If the scheme is proven to be end-to-end safe, it is a priori robust.It should be noted that masking was initially developed for symmetrical schemes and was based on Boolean masking. It's only recently that we've begun to take an interest in asymmetrical schemes, and in particular lattice-based schemes. For this purpose, arithmetic masking has been the main one used, although Boolean conversions could be performed to achieve certain things (value comparison among others).Today, we're able to offer a masked implementation of BIKE, based on a proven safe algorithm. As BIKE manipulates binary data, we focused on Boolean masking. We therefore had to :- reuse existing gadgets,- adapt and optimize existing arithmetic masking gadgets,- create new gadgets. Each time, we had to carry out proofs, and also prove their composition within each BIKE function, to arrive at the full scheme proof.As a reminder, BIKE is based on QC-MDPCs, and its arithmetic is based on dense, sparse polynomials, so choices had to be made regarding representation and the way calculations are performed. We therefore decided to explore two paths (fully dense and hybrid sparse-dense) and see what was most relevant between the two. In addition to the full C implementation, benchmarks were carried out, enabling us to see where performance was limited and where the bottlenecks were.In the end, we propose a fully masked and proven-safe BIKE algorithm, with its C implementation and various benchmarks to judge its performance.
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.
Domaines
Cryptographie et sécurité [cs.CR]
Origine : Version validée par le jury (STAR)