Arrêtez d'utiliser RSA

Salut% username%!

RSA est le premier algorithme de cryptographie asymétrique largement utilisé qui est toujours populaire dans l'industrie. C'est relativement simple à première vue. Le chiffrement et la signature RSA peuvent être comptés sur une feuille de papier, ce que les étudiants font souvent en laboratoire.
Mais il existe tout simplement un grand nombre de nuances sans lesquelles même un enfant peut casser votre implémentation RSA.

Pour une raison quelconque, les gens pensent toujours que RSA est un bon algorithme. Mais en fait, la possibilité d'un tir dans la jambe lors de la mise en œuvre de RSA est extrêmement énorme. Les paramètres faibles sont difficiles à vérifier, voire impossibles. Et les mauvaises performances de l'algorithme encouragent les développeurs à utiliser des moyens risqués pour l'améliorer.

Pire encore, le rembourrage des attaques oracle inventées il y a plus de 20 ans est toujours d'actualité.
Même si en théorie il est possible d'implémenter RSA correctement, en pratique un tel «exploit» est presque impossible à réaliser. Et les vulnérabilités qui ne cessent d'émerger depuis des décennies ne font que le confirmer.

Quelques mots sur l'algorithme RSA

Si vous savez comment fonctionne RSA, vous pouvez ignorer cette partie.

RSA est un cryptosystème à clé publique qui a deux utilisations.

Le premier est le chiffrement, quand Alice publie sa clé publique et que Bob, le sachant, peut chiffrer un message que seule Alice peut lire, le déchiffrant avec sa clé privée.

La seconde est une signature numérique, qui permet à Alice de signer le message avec sa clé privée afin que chacun puisse vérifier cette signature avec sa clé publique.

Les deux algorithmes diffèrent par des détails insignifiants, nous les appellerons donc simplement RSA.

Pour commencer à travailler avec RSA, Alice doit choisir deux nombres premiers p et q , qui forment ensemble un groupe de nombres modulo N = pq . Ensuite, Alice doit choisir un exposant ouvert e et un exposant secret d tels que $$$ed = 1 \ mod (p-1) (q-1)$. En substance, e et d devraient être mutuellement simples.

Une fois ces options sélectionnées, Bob peut envoyer à Alice un message M, informatique $$$C = M ^ e (mod \ N)$. Alice peut ensuite déchiffrer le message en calculant $$$M = C ^ d (mod \ N)$.
La signature numérique est exactement le contraire. Si Alice veut signer le message, elle calcule la signature $$$S = M ^ d (mod \ N)$Bob peut vérifier en s'assurant que le message $$$M = S ^ e (mod \ N)$

C'est tout, c'est l'idée principale. Nous reviendrons sur Padding oracles plus tard, mais pour l'instant voyons ce qui peut être fait si les paramètres RSA sont mal sélectionnés.

Début de fin

Pour que RSA fonctionne, vous devez sélectionner plusieurs paramètres. Malheureusement, des méthodes apparemment innocentes de leur choix peuvent nuire à la sécurité. Passons en revue chacun d'eux et voyons quelles mauvaises surprises vous attendent.

Prime Generation

La sécurité RSA est basée sur le fait qu'il est difficile d'avoir un grand nombre N , qui est le produit de deux nombres premiers p et q , décomposer N en facteurs premiers sans connaître p et q . Les développeurs sont responsables du choix des nombres premiers qui composent le module RSA. Ce processus est extrêmement lent par rapport à la génération de clés pour d'autres protocoles cryptographiques, où il suffit de sélectionner simplement quelques octets aléatoires. Par conséquent, au lieu de générer un nombre premier vraiment aléatoire, les développeurs essaient souvent de créer des nombres d'une certaine forme. Cela se termine presque toujours mal. Il existe de nombreuses façons de choisir des nombres premiers pour que l'affacturage N soit simple. Par exemple, p et q doivent être globalement uniques. Si p ou q sont réutilisés dans d'autres modules RSA, les deux facteurs peuvent être facilement calculés à l'aide de l'algorithme GCD. De mauvais générateurs de nombres aléatoires rendent ce scénario très probable, et des études ont montré qu'environ 1% du trafic TLS en 2012 était exposé à une telle attaque.

De plus, p et q doivent être sélectionnés indépendamment l'un de l'autre. Si p et q partagent environ la moitié de leurs bits les plus significatifs, alors N peut être calculé en utilisant la méthode de Fermat. En fait, même le choix d'un algorithme de test de simplicité peut avoir des implications sur la sécurité. L'attaque la plus médiatisée est peut-être la vulnérabilité ROCA dans RSALib, qui a affecté de nombreuses cartes à puce, modules de plateforme de confiance et même des clés Yubikey. Ici, lors de la génération de clés, seuls les nombres premiers d'une certaine forme sont utilisés pour accélérer les calculs. Les nombres premiers générés de cette manière sont triviaux à découvrir en utilisant des techniques délicates en théorie des nombres. Une fois qu'un système faible a été reconnu, les propriétés algébriques spéciales des nombres premiers permettent à un attaquant d'utiliser la méthode Coppersmith pour décomposer N.

Il convient de garder à l'esprit que dans aucun de ces cas, la génération de nombres premiers de cette manière est un fait évident conduisant à une défaillance complète du système. En effet, les propriétés théoriques des nombres insignifiantes des nombres premiers ont un impact significatif sur la sécurité RSA. L'espoir qu'un développeur ordinaire naviguera dans ce champ de mines mathématique compromet sérieusement la sécurité.

Exposant secret d

Étant donné que l'utilisation d'une grande clé privée affecte négativement le temps de déchiffrement et de signature, les développeurs sont incités à choisir un petit d , en particulier dans le cas d'appareils à faible consommation d'énergie, tels que les cartes à puce. Cependant, un attaquant peut récupérer la clé privée lorsque d est inférieur à la racine du 4ème degré de N. Au lieu de cela, les développeurs devraient choisir une grande valeur de d , afin que le théorème du reste chinois puisse être utilisé pour accélérer le déchiffrement. Cependant, la complexité de cette approche augmente la probabilité d'erreurs d'implémentation mineures qui peuvent conduire à une récupération de clé.

Vous dites qu'en général, lors de l'initialisation de RSA, vous générez d'abord un module, utilisez un exposant ouvert fixe, puis choisissez un secret?
Oui, cela empêche les attaques avec un petit exposant secret si vous utilisez toujours l'un des exposants ouverts recommandés e .
Malheureusement, cela suppose également que les développeurs le feront vraiment. Dans le monde réel, les développeurs font souvent des choses étranges, par exemple, choisissez d'abord d puis considérez e .

Exposant ouvert e

Comme pour l'exposant secret, les développeurs souhaitent utiliser de petits exposants ouverts pour économiser sur le cryptage et la vérification de signature. Typiquement, les nombres premiers de Fermat sont utilisés dans ce contexte, en particulier e = 3, 17 et 65537.

Malgré le fait que les cryptographes recommandent d'utiliser 65537, les développeurs choisissent souvent e = 3, ce qui entraîne de nombreuses vulnérabilités dans le cryptosystème RSA.


(Ici, les développeurs ont utilisé e = 1, qui ne crypte pas du tout le texte en clair.)

Lorsque e = 3 ou une taille similaire, beaucoup de choses peuvent mal tourner. Les petits exposants ouverts sont souvent associés à d'autres erreurs courantes qui permettent à un attaquant de décrypter certains textes chiffrés ou le facteur N.

Par exemple, une attaque Franklin-Reuters permet à un attaquant de déchiffrer deux messages connectés par une distance fixe connue. En d'autres termes, supposons qu'Alice envoie à Bob uniquement «acheter» ou «vendre». Ces messages seront associés à une valeur connue et permettront à un attaquant de déterminer lesquels signifient «acheter» et lesquels «vendre» sans déchiffrer le message. Certaines attaques avec un petit e peuvent même conduire à une récupération de clé.

Si l'exposant ouvert est petit (pas seulement 3), un attaquant qui connaît plusieurs bits de la clé secrète peut récupérer les bits restants et casser le cryptosystème. Bien que bon nombre de ces attaques RSA e = 3 puissent être corrigées par remplissage, les développeurs qui implémentent le RSA eux-mêmes oublient souvent de l'utiliser.

Les signatures RSA sont également vulnérables aux petits exposants publics. En 2006, Bleichenbacher a découvert une attaque qui permet aux attaquants de truquer des signatures arbitraires dans de nombreuses implémentations RSA, y compris celles utilisées dans Firefox et Chrome. Cela signifie que tout certificat TLS d'une implémentation vulnérable peut être falsifié. Cette attaque exploite le fait que de nombreuses bibliothèques utilisent un petit exposant public et ne font pas une simple vérification d'alignement lors du traitement des signatures RSA. L'attaque de Bleichenbacher contre la signature est si simple qu'elle est incluse dans de nombreux exercices de cours de cryptographie.

Le choix des options est une tâche difficile

Le point commun à toutes ces attaques contre les paramètres est que le nombre total de variantes possibles de paramètres est beaucoup plus grand que le nombre de variantes sûres.

Il est supposé que les développeurs géreront eux-mêmes ce processus de sélection complexe, car tout sauf l'exposant ouvert doit être généré lors de l'initialisation.
Il n'existe aucun moyen simple de vérifier la fiabilité des paramètres . Au lieu de cela, les développeurs ont besoin d'une base mathématique sérieuse, dont la présence ne devrait pas être attendue des employés ordinaires. Bien que l'utilisation de RSA avec alignement puisse vous sauver si vous avez les mauvais paramètres, beaucoup préfèrent toujours ne pas le faire.

Remplissage des attaques Oracle

Comme nous l'avons expliqué ci-dessus, le simple fait d'utiliser RSA hors de la boîte ne fonctionne pas tout à fait. Par exemple, le schéma RSA décrit dans l'introduction créera des textes chiffrés identiques si le même texte en clair a déjà été chiffré plus d'une fois. C'est un problème car il permettra à un attaquant d'apprendre le contenu d'un message à partir du contexte, sans pouvoir le décrypter. C'est pourquoi nous devons aligner les messages avec quelques octets aléatoires. Malheureusement, le schéma d'alignement le plus utilisé, PKCS # 1 v1.5, est souvent vulnérable à la soi-disant attaque oracle de remplissage.

L'attaque initiale contre PKCS # 1 v1.5 a été découverte en 1998 par Daniel Bleikhanbacher. Malgré le fait qu'elle ait plus de 20 ans, elle continue aujourd'hui d'être pertinente pour de nombreux systèmes. Les versions modernes de cette attaque incluent souvent un oracle supplémentaire, un peu plus compliqué que celui décrit à l'origine par Bleikhanbacher, par exemple, le temps de réponse du serveur ou l'exécution de toute rétrogradation de protocole dans TLS. Un exemple particulièrement choquant était l'attaque ROBOT , qui était si terrible qu'une équipe de chercheurs a pu signer des messages avec Facebook et PayPal à clés secrètes. Certains pourraient affirmer que ce n'est pas vraiment la faute de RSA - les mathématiques de base sont très bien; les gens ont juste foiré une norme importante il y a des décennies. Le fait est que nous avions déjà , depuis 1998, un schéma d'alignement standard avec des preuves de sécurité strictes, OAEP. Mais presque personne ne l'utilise. Même lorsque cela se produit, il est de notoriété publique que OAEP est difficile à implémenter, et il est souvent vulnérable à une attaque Manger, qui est une autre attaque Oracle qui peut être utilisée pour récupérer du texte en clair.

Le problème fondamental ici est que l'alignement est nécessaire lors de l'utilisation de RSA, et cette complexité supplémentaire ouvre de grandes possibilités pour les attaques contre le cryptosystème. Le fait qu'un élément d' information, «si le message était correctement aligné», peut avoir un impact si important sur la sécurité que le développement de bibliothèques sécurisées est pratiquement impossible. TLS 1.3 ne prend plus en charge RSA, nous pouvons donc nous attendre à moins d'attaques de ce type à l'avenir.

Mais alors que les développeurs continuent d'utiliser RSA dans leurs propres applications, les attaques de remplissage d'Oracle continueront de se produire.

Que faire

Les gens préfèrent souvent utiliser RSA parce qu'ils le trouvent conceptuellement plus simple que le protocole DSA alambiqué ou la cryptographie à courbe elliptique (ECC). Mais bien que RSA soit plus intuitif, il manque vraiment de protection contre le fou.

Tout d'abord, une idée fausse commune est que l'elliptique est très dangereux, car le choix d'une mauvaise courbe peut tout annuler. Il est vrai que la sélection des courbes a un grand impact sur la sécurité, mais l'un des avantages de l'utilisation de l'ECC est que la sélection des paramètres peut être effectuée publiquement. Les cryptographes font le choix des paramètres pour vous, les développeurs n'ont donc qu'à générer des octets aléatoires de données à utiliser comme clés. Les développeurs peuvent théoriquement construire une implémentation ECC avec des paramètres terribles et ne pourront pas vérifier des choses comme des points de courbe incorrects, mais ils ne le font généralement pas. L'explication probable est que les mathématiques derrière ECC sont si complexes que très peu de gens se sentent suffisamment confiants pour le mettre en œuvre. En d'autres termes, cette peur oblige les gens à utiliser des bibliothèques créées par des cryptographes qui connaissent leur métier. Le RSA, en revanche, est si simple qu'il peut être (mal) implémenté en une heure.

Deuxièmement, tout schéma de correspondance ou de signature basé sur Diffie-Hellman (y compris les options de courbe elliptique) ne nécessite pas d'alignement et, par conséquent, est entièrement résistant aux attaques Padding Oracle. Il s'agit d'une victoire majeure, étant donné que le RSA a un très long palmarès de tentatives pour éviter cette classe de vulnérabilités.

Nous vous recommandons d'utiliser Curve25519 pour l'échange de clés et ed25519 pour les signatures numériques. Le cryptage doit être effectué à l'aide du protocole ECIES, qui combine l'échange de clés ECC avec un algorithme de cryptage symétrique. Curve25519 a été conçu pour empêcher complètement les classes d'attaque qui pourraient arriver à d'autres courbes, et il est également très rapide. De plus, il est implémenté dans de nombreuses bibliothèques, par exemple libsodium, qui est équipé d'une documentation facile à lire et est disponible dans la plupart des langues.

Arrêtez d'utiliser RSA. Sérieusement.

(Twilio utilise toujours des clés RSA)


(Travis CI utilise toujours des clés de 1024 bits et ne permet pas de les remplacer)

RSA a été une étape importante dans le développement de communications sécurisées, mais les deux dernières décennies de recherche cryptographique l'ont rendu obsolète. Les algorithmes sur les courbes elliptiques pour l'échange de clés et les signatures numériques ont été normalisés en 2005 et ont depuis été intégrés dans des bibliothèques intuitives et résistantes aux abus, comme libsodium. Le fait que RSA soit encore largement utilisé aujourd'hui indique à la fois une erreur de la part des cryptographes en raison d'une description inadéquate des risques inhérents à RSA et des développeurs qui surestiment leur capacité à le déployer avec succès. La communauté de la sécurité devrait commencer à le considérer comme un problème de troupeau - bien que certains d'entre nous puissent naviguer dans le processus extrêmement dangereux de configuration ou de mise en œuvre de RSA, des exceptions indiquent clairement aux développeurs que RSA est toujours pertinent à certains égards. Malgré les nombreuses mises en garde et avertissements sur StackExchange et GitHub README, très peu de gens croient que ce sont eux qui vont gâcher le RSA, et donc ils continuent d'agir de façon imprudente. En fin de compte, vos utilisateurs paieront pour cela. C'est pourquoi nous devons tous convenir que l'utilisation de RSA en 2019 est totalement inacceptable. Aucune exception.

Article original en anglais.

VirgilSecurity, Inc. Développe un SDK convivial pour les développeurs et des services de protection des données. Nous permettons aux développeurs d'utiliser les algorithmes existants avec un risque de sécurité minimal.

PS Je vous recommande également de lire sur l' incorporation d'une porte dérobée dans la clé publique RSA.