Description
Date depot: 1 janvier 1900
Titre: Cryptographie post-quantique : Attaques par canaux cachés sur les cryptosystèmes à base de codes MDPC quasi-cycliques
Directeur de thèse:
Nicolas SENDRIER (Inria-Paris (ED-130))
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Non defini
Resumé:
{{{Le cryptosystème de McEliece : chiffrer avec des codes correcteurs d'erreurs}}}
Le chiffrement consiste à transformer le texte clair en un mot d'un code linéaire (de façon publique et réversible) puis à ajouter des erreurs aléatoires. L'utilisateur légitime connaît l'algorithme de décodage et peut retirer les erreurs. L'adversaire qui ignore le secret (l'algorithme de décodage) doit résoudre un problème algorithmique dont la résolution est hors de portée.
{{La variante QC-MDPC-McEliece.}} Récemment, une variante quasi-cyclique du système de McEliece a été proposée utilisant les codes MPDC (Moderate Density Parity Check) [5]. Cette variante propose de bonnes garanties de sécurité, y compris contre un adversaire quantique, tout en offrant des clés publiques de taille raisonnable (de l'ordre de 10 kilobits contre 2 mégabits pour un McEliece « classique », soit un facteur 200, à sécurité égale).
{{{Sujet : Attaques par canaux cachés sur les cryptosystème à base de codes MDPC quasi-cycliques}}}
{{Une attaque exploitant les échecs du décodage.}} Il existe une probabilité, faible mais strictement positive, pour que cet algorithme de décodage échoue. Dans un travail récent [1] une attaque a été décrite mettant en évidence un lien entre les motifs d’erreurs provoquant un échec et la clé secrète du système. Ceci permet de décrire un scénario dans lequel un adversaire ayant accès à un oracle de déchiffrement peut retrouver de façon effective la clé secrète. Un code MDPC de longueur n et quasi-cyclique d’index 2 a une dimension k = n/2, il est défini par la donnée d’une équation de parité creuse de poids de Hamming O(√n), par exemple la première ligne de sa matrice de parité creuse. Cette équation est secrète. Le déchiffrement consiste à appliquer l’algorithme de décodage des codes MDPC (l’algorithme « bit flipping ») à un mot de code auquel a été ajouté une erreur de poids de Hamming O(√n). Lorsque l’erreur présente une « similarité » avec l’équation de parité (un écart entre deux positions non nulles de l’erreur que l’on retrouve entre deux positions non nulles de l’équation de parité) on constate une légère variation du taux d’échec. Cela permet au bout d’un grand nombre d’essais de décodage pour lesquels l’erreur est connue, de déterminer quels écarts sont absents ou présents dans l’équation de parité, puis d’en déduire cette équation à l’aide d’un algorithme de reconstruction de type « backtrack search ». L’attaque est relativement peu coûteuse dans le scénario favorable où le taux d’échec est élevé et/ou l’adversaire peut choisir l’erreur. Dans un scénario plus réaliste (taux d’échec faible et système sémantiquement sûr, ce qui signifie que l’adversaire ne peut pas choisir l’erreur) l’attaque est plus chère mais semble fonctionner néanmoins. Le premier volet de l’étude consistera à mettre en œuvre l’attaque, à savoir la mesure des corrélations puis l’algorithme de reconstruction du secret. D'abord dans le scénario le plus facile, puis dans la mesure possible dans des scénarios plus réalistes.
{{Analyse et extensions de l’attaque.}} Il existe une contre-mesure à cette attaque consistant à réduire le taux d’échec de l’algorithme, ce qui peut être fait relativement facilement en augmentant la taille de certains paramètres. Néanmoins, cette contre-mesure ne fait pas disparaître le problème de fond, à savoir que le comportement global de l’algorithme de décodage varie en fonction du degré de « similarité » entre l’erreur et le secret. Il s’agira de comprendre quelles sont les grandeurs calculées par l’algorithme qui dépendent de cette similarité et de déterminer qualitativement et quantitativement le liens entre ces grandeurs et la similarité. Ceci permettra de déterminer précisément comment et à quel coût l’observation d’une quantité interne de l’algorithme (qui peut constituer un canal caché observable) permettra à l’adversaire de retrouver tout ou partie de la clé secrète.
{{Algorithme de reconstruction.}} Un autre volet de l’étude consiste à étudier isolément algorithme de reconstruction de l’équation de parité secrète à partir des écarts présents ou absents. Son coût est estimé dans [1] lorsque l’information recueillie est « dure », c’est-à-dire que l’on connaît sans erreur un ensemble d’écarts présents et un ensemble d’écarts absents. Dans un scénario d’attaque réaliste, par exemple lorsque le nombre d’appel à l’oracle de déchiffrement est limité, l’information sur les écarts peut être « souple », c’est-à-dire que pour chaque écart on connaît une mesure de vraisemblance de sa présence dans le secret. Dans un tel cas la reconstruction reste possible mais devient plus coûteuse, il pourrait être intéressant de comprendre quels liens existent entre entre la quantité d’information recueillie (typiquement l’entropie des mesures de vraisemblance) et la complexité de algorithme de reconstruction.
{{Contre-mesures.}} Parmi les objectifs de l’étude, l’un consistera à comprendre, de façon
Doctorant.e: Lequesne Matthieu