Attaques sur les codes QC-MDPC

Attaques sur les codes QC-MDPC

Nous avons vu précédemment que l’utilisation des codes quasi-cycliques MDPC dans le cryptosystème de McEliece permet de construire un schéma de chiffrement post-quantique dont les clés ont une taille raisonnable. Cependant, ces codes étant très bien structurés, ils sont vulnérables aux attaques de types structurelles. Ces attaques permettent aux cryptanalystes de retrouver la clé secrète en vue de déchiffrer le message envoyé. La principale faille de ces types d’attaques est l’algorithme de décodage bit-flipping. Nous allons, dans ce chapitre, faire une étude exhaustive de l’attaque de récupération de clé de Guo-Johansson-Stankovski ainsi que de l’attaque temporelle sur les codes quasi-cycliques MDPC.

Attaque de Guo-Johannson-Stankovski

L’attaque de récupération de clé dans [42] sur les codes QC-MDPC est une attaque de réaction reposant sur le fait que lors de l’étape du déchiffrement, le décodage itératif peut échouer avec une faible probabilité. Les auteurs ont ainsi identifié une dépendance entre la clé secrète et l’échec du décodage. Cette attaque suppose seulement qu’un adversaire est en mesure de dire quand une erreur s’est produite, par exemple parce qu’une demande de renvoi a été effectuée. Elle peut être utilisée pour construire ce que l’on appelle le spectre de distance pour la clé secrète. L’attaque se déroule en deux étapes. La première étape consiste à calculer le spectre de distance de la clé secrète (ou d’une partie de la clé secrète), basée sur l’observation d’un grand nombre de vecteurs d’erreur qui ont abouti à un échec du décodage. La deuxième étape consiste à reconstruire la clé secrète en fonction du spectre de distance.

Exemple : considérons le vecteur ℎ = 1001000001, avec 𝑟 = 10 et 𝑤 = 3. On peut remarquer que 𝑑(ℎ) = {1,3,4}. En effet, le premier et le dernier bit de ℎ sont voisins (la distance étant comptée de manière cyclique), ce qui donne 1 comme spectre. Le premier et le quatrième bit sont distants de 3. Le quatrième et le dernier bit quant à eux sont distants de 4. . L’idée principale de cette attaque est de vérifier le nombre d’échecs de décodage signalés en utilisant un certain ensemble de modèles d’erreurs différents. L’attaque génère ces schémas d’erreurs selon un certain critère. ensembles seront utilisés pour générer des informations statistiques sur le taux de réussite du décodage. Comme décrit précédemment, ce taux de réussite dépend de l’emplacement des bits d’erreur.

La motivation derrière cette attaque est qu’il existe une corrélation entre la probabilité d’erreur de décodage calculée et la fréquence d’occurrence d’une distance 𝑑 dans le premier circulant , plus la probabilité d’erreur de décodage calculée sera faible. Le nombre de fois que la distance se produit dans un vecteur donné est appelé multiplicité de cette distance dans ce vecteur, et est désignée par 𝜇(𝑑). Par conséquent, un profil de distance de ℎ, et leurs multiplicités correspondantes. Le profil de cette distance est indiqué par 𝐷(ℎCet exemple montre la façon dont le vecteur d’erreur est généré lors de l’attaque et pour une distance donnée, ainsi que la façon dont la multiplicité de cette distance apparaîtra en ℎ.

Reconstruction de la Clé secrète

Une fois que l’attaque est faite, et que 𝐷(ℎ, peut être faite facilement. Tout d’abord, on place un ‘‘1’’ dans la première position du vecteur de reconstruction, qu’on notera ℎ quelconque et la distance entre celui-ci et les deux précédemment calculées. Si ces distances calculées apparaissent dans le profil de distance, alors la troisième est maintenue dans sa position; sinon, une nouvelle position est testée. Cette opération est répétée jusqu’à ce que les distances calculées, avec cette position 𝑖 pourra alors être reconstruit en décalant cycliquement chaque entrée de ℎLe nombre d’opérations binaires nécessaires pour rompre le système cryptographique QC- MDPC avec pour la sécurité 80-bit est estimée à 228 opérations. La décision difficile de Gallager L’algorithme de décodage était l’un des premiers algorithmes de décodage itératif pour les codes LDPC. Des algorithmes de décodage plus avancés avec de meilleures performances de décodage rendent cette la cryptanalyse pour trouver la clé privée. Il faut envoyer davantage de cryptogrammes pour obtenir suffisamment des informations statistiques pour construire le spectre de distance 𝐷(𝐻La variante CCA-2, plus sûre, qui utilise essentiellement l’idée de brouiller les bits du message d’entrée 𝑚 autour, peut également être cryptée avec cette attaque. Bien que l’attaque nécessite quelques modifications mineures et que le facteur de travail de cette variante soit plus élevé .