Au secours les bugs attaquent !

Nos ordinateurs sont infectés de bugs en tous genres, le plus souvent bien heureusement inoffensifs. Quelles sont les implications cryptographiques de telles imperfections ? Comment un attaquant peut-il réduire à néant la sécurité d'algorithmes cryptographiques aussi répandus que le cryptosystème RSA ?

Récemment, trois chercheurs israéliens, dont Adi Shamir, l’un des inventeurs de RSA (Rivest-Shamir-Adleman), ont montré dans un article publié à la conférence CRYPTO 2008, que ces bugs, bien qu’inoffensifs pour la plupart des applications courantes, peuvent se révéler désastreux pour la sécurité de certains cryptosystèmes [1]. Ils ont étudié en particulier les effets d’un bug de multiplication qui n’affecterait qu’une seule paire d’entrées a et b dont le produit serait calculé de façon incorrecte. Remarquons que sur un multiplieur à 64 bits et pour des entrées aléatoires, le produit ab n’a qu’une probabilité égale à 2^(-128) d’être effectivement calculé. Concrètement, il est extrêmement improbable que ces deux entrées soient un jour multipliées sur un ordinateur. Pourtant, un attaquant qui en aurait connaissance pourrait mettre à mal de nombreux algorithmes cryptographiques fonctionnant sur un tel processeur.

Un simple bug de multiplication fatal à RSA

Rappelons comment fonctionne le cryptosystème à clé publique RSA. Chaque utilisateur possède une clé publique connue des autres utilisateurs et une clé privée connue de lui seul. La clé publique est constituée d’un couple (n,e) où n est le produit de deux grands nombres premiers p et q (la taille de n est typiquement de 1.024 ou 2.048 bits), et e est un nombre premier avec (p-1)*(q-1). La clé privée est le couple (n,d) où d a la particularité que pour tout nombre M compris entre 0 et n-1 : (M^e)^d = M mod n.Ce cryptosystème permet deux fonctionnalités, le chiffrement et la signature. Ainsi, pour chiffrer un message M à destination d’un utilisateur dont la clé publique est (n,e), on calcule : C = M^e mod n, et on lui envoie C. Le destinataire peut alors retrouver M en calculant : M = C^d mod n.Pour signer un message M, le signataire utilise sa clé privée (n,d) et calcule tout d’abord l’image h(M) du message par une fonction de hachage cryptographique h telle que SHA1, puis calcule la signature : S = h(M)^d mod n.N’importe quel autre utilisateur peut alors s’assurer de la validité de la signature à partir de la clé publique (n,e) en vérifiant que : S^e = h(M) mod n.Dans tous les cas, le calcul secret consiste en une exponentiation modulaire à la puissance d, l’exposant secret, modulo n. La sécurité de RSA repose sur l’impossibilité de factoriser le module n, c’est-à-dire sur l’impossibilité de retrouver p et q à partir de la clé publique (n,e) et de résultats d’opérations de déchiffrement ou de signature. Toute méthode permettant de factoriser n réduit à néant la sécurité et permet de décrypter des messages ou de contrefaire des signatures.Lorsque le processeur comporte un bug de multiplication, il est possible que certains calculs RSA produisent un résultat faux. Par la suite nous noterons toutes les valeurs erronées avec un astérisque (M*,…). Toutes les attaques par bug consistent à utiliser le résultat erroné d’un calcul impliquant l’exposant secret d, qu’il s’agisse d’un déchiffrement M* = C^d mod n ou d’une signature S* = h(M)^d mod n. Les attaques par bug dépendent de la façon dont est implémentée l’exponentiation à la puissance d lors du calcul secret. La méthode naïve consiste simplement à effectuer une exponentiation rapide (type « Square and Multiply ») modulo n. Cependant il existe une méthode plus efficace utilisant le fameux « théorème des restes chinois ». Cette méthode consiste à calculer C^d modulo p et modulo q séparément, puis à en déduire le résultat modulo n, et permet d’accélérer le calcul d’un facteur 4 par rapport à une implémentation classique. Lorsque cette méthode est utilisée, il est possible de factoriser le module n si l’on obtient le résultat d’un calcul correct modulo p et incorrect modulo q (ou l’inverse). En effet, supposons qu’un attaquant ait accès au résultat faussé M* du déchiffrement d’un chiffré C correspondant à un message M. Comme le calcul était correct modulo p, on a M = M* mod p. Par contre le résultat est incorrect modulo q, si bien que M est différent de M* modulo q. Il résulte de ces deux égalités que le plus grand diviseur commun de ((M*)^e-C) et n est égal à p. Ainsi, on peut factoriser n par un simple calcul de PGCD.Reste à savoir comment l’attaquant peut provoquer une telle erreur lors du déchiffrement ou de la signature. Lorsque le calcul secret se déroule sur un processeur possédant un bug de multiplication affectant le produit ab, ceci est possible en demandant le déchiffrement d’un chiffré bien choisi ou la signature d’un message adéquat. Rappelons que les nombres en jeu ont une taille de 1.024 ou 2.048 bits, et sont donc constitués d’un très grand nombre de mots de 32 ou 64 bits. Lorsque l’on calcule la puissance d’un nombre X de cette taille, tous les mots de 32 ou 64 bits de X sont multipliés entre eux à une certaine étape du calcul. Par conséquent, lorsque X contient à la fois le mot a et le mot b, le produit ab intervient et fausse le résultat final. Supposons que les facteurs p et q de n sont tels que p < q. L'attaque (représentée sur la Figure 1) consiste à choisir pour chiffré C dont on va demander le déchiffrement un nombre compris entre p et q (tout nombre suffisamment proche de la partie entière de la racine carrée de n convient) et contenant les deux mots a et b dont le produit est calculé incorrectement. La première étape du calcul de C^d par le théorème des restes chinois consiste à réduire C modulo p et modulo q. Comme C < q, C n'est pas modifié lors de la réduction modulo q et contient donc toujours les deux mots a et b, et par conséquent le résultat du calcul de C^d modulo q est erroné. En revanche, comme C > p, la réduction modulo p modifie complètement et de façon aléatoire le nombre, si bien que Cp = C mod p n’a qu’une probabilité très faible de contenir a et b. Par conséquent le calcul de C^d mod p est juste. On peut alors factoriser n comme expliqué précédemment.

Les versions plus sophistiquées sont également menacées

L’attaque par bug que nous venons de voir pour le cas particulier de l’implémentation par le théorème des restes chinois peut être généralisée à d’autres implémentations, notamment les algorithmes d’exponentiation classiques de type « Square and Multiply ». Dans ce cas l’attaque devient plus complexe et il faut plus qu’un seul chiffré choisi comme pour l’attaque précédente. Ainsi, pour attaquer RSA avec des clés de 1.024 bits où le déchiffrement est effectué avec l’algorithme d’exponentiation « Left-to-Right », il faut 2^10 chiffrés choisis ou 2^56 clairs connus. L’attaque consiste à déduire chacun des bits de l’exposant secret d un à un en soumettant un chiffré bien choisi pour déchiffrement et en analysant si le résultat est correct ou non.Par ailleurs, même lorsque RSA est utilisé avec la méthode OAEP (Optimal Asymmetric Encryption Padding), qui décrit comment formater un message, en incluant l’aléa qui est censée protéger des attaques à chiffrés choisis, il est encore possible d’effectuer une attaque par bug, mais de complexité nettement supérieure.Remarquons que les attaques décrites peuvent être difficiles à mettre en œuvre car ce sont des attaques à chiffrés choisis. Mais elles ne sont pas impossibles, car de l’information peut tout de même parvenir à l’attaquant (par exemple la plate-forme peut renvoyer un message d’erreur si le résultat du déchiffrement était mal formaté, etc.).Par ailleurs, les attaques par bug peuvent également s’appliquer à d’autres types d’algorithmes cryptographiques, tels que l’algorithme de Pohlig-Hellman (un système de chiffrement algébrique à clé secrète), aux systèmes basés sur les courbes elliptiques, ou encore à certains algorithmes de chiffrement par bloc utilisant la multiplication comme opération élémentaire tels que IDEA, MARS ou RC6.

Les contre-mesures sont possibles

Comment se protéger des attaques par bug ? La protection la plus efficace consiste naturellement à vérifier le résultat du calcul secret. Ainsi pour une signature S, on vérifie que l’on a bien S^e = h(M) mod n. Cependant cette méthode augmente sensiblement le temps de calcul et nécessite la connaissance de la clé publique par le dispositif qui calcule la signature ou qui déchiffre, ce qui n’est pas toujours le cas. Une technique alternative consiste à rendre le calcul secret « aléatoire ». Ainsi, pour déchiffrer un chiffré C correspondant à un message M, on peut par exemple choisir un entier r aléatoire, puis calculer C’ = C.r^e = (M.r)^e mod n. On applique alors la procédure de déchiffrement à C’ (et non C) pour obtenir (C’)^d = ((M.r)^e)^d = M.r. Il ne reste alors plus qu’à diviser le résultat par r pour retrouver le message M. Cette technique (appelée « blinding ») empêche l’attaquant de contrôler la valeur d’entrée de l’algorithme de déchiffrement ou de signature, et contrecarre efficacement les attaques précédemment décrites. Dans tous les cas, les implémenteurs devront avoir ces nouvelles attaques à l’esprit lors des futurs développements de cryptosystèmes.Par Yannick Seurin, Ingénieur de recherche en cryptographie

Notes

[1] E. Biham, Y. Carmeli, et A. Shamir, Bug Attacks, CRYPTO 2008, p. 221–240, 2008.[2] D. Boneh, R.A. DeMillo, et R.J. Lipton, On the Importance of Checking Cryptographic Protocols for Faults, EUROCRYPT 1997, p. 37 – 51, 1997. systèmes d’information,[[