Casser RSA… ou presque!

Introduction

Envie de cracker RSA? Ben c’est pas tout de suite que vous pourrez jouer à la NSA en espionnant les GAFAM mais si vous voulez tester la solidité d’une clé publique, c’est par ici! Il se peut même que vous arriverez à casser le chiffrement s’il n’est pas trop hard. Au passage, RSA est utilisé dans le protocole https, c’est à dire pour toutes vos transactions, envoie de messages, consultations etc… dans votre navigateur web lorsque le site est “sécurisé”.

Une fois encore, n’espérez pas cracker Google (taille de la clé: 2048 bits) mais une clé de 256 bits par contre, ne tiendra pas plus de quelques minutes pour peu que vous ayez une machine qui tient bien la route. En ce qui me concerne, ce sera un i7-4720HQ, une carte Nvidia GTX 965M, 8Gb DDR3 et SSD. Vous me direz que l’info sur la carte graphique n’est pas très importante, mais en fait c’est presque ce qui déterminera la totalité du temps de calcul! Les GPU sont programmés pour réaliser un certain type d’opérations de manière efficace, bien plus qu’un proc, même un i7. Nous allons donc utiliser cet avantage. La difficulté réside dans le problème de décomposition d’un nombre en un produit de facteurs premiers, ce que nous allons expliquer par la suite.

/!\ Attention /!\ Cet article est à but pédagogique, et doit être utilisé pour mieux comprendre le chiffrement que l’on utilise tous les jours (oui tous, tous les jours, même si l’on ne s’en rend pas compte). Vous pouvez casser toutes les clés que vous voulez, mais sachez qu’il est interdit d’espionner une communication. Comme d’hab ce qui est interdit en bas ne l’est pas en haut au passage… Bref je ne saurai être tenu pour responsable d’une mauvaise utilisation de l’information donnée ici!

Cela dit, accrochez-vous car la suite ne va pas être totalement triviale!

Installation des outils

 

Dans les langages de programmation classiques (notamment le C++), le plus grand entier qu’on puisse stocker est un ‘unisgned long long int’, codé sur 16 octects, soit un nombre égal à: 2^(16*8) – 1 maximum soit un nombre à 39 chiffres, si je ne dis pas de bétises. Seulement ce n’est pas assez pour faire du chiffrement, c’est pour cela qu’il va falloir installer la librairie GMP, qui va shunter cette limite. L’installation est assez classique:
– Téléchargement depuis le site officiel: https://gmplib.org/#DOWNLOAD
– Installation:

$ ./configure ; make ; make check ; make install

De même il va falloir installer la version Python:

$ sudo aptitude install python-gmpy

On va maintenant installer msieve, qui va réaliser cette décomposition en facteurs premiers via l’algorithme “general number fild sieve”, considéré comme ayant la complexité la plus faible à ce jour (donc le plus efficace). J’ai bien essayé de comprendre quelque chose à l’algorithme, mais en vain… L’installation est quand à elle, relativement simple:
– Télécharger msieve depuis github: https://github.com/radii/msieve
– Switcher les commentaires sur la ligne “OPT” du Makefile pour avoir, ligne 19 et 20:

OPT_FLAGS = -O3 -fomit-frame-pointer -march=athlon-xp -DNDEBUG
#OPT_FLAGS = -O3 -fomit-frame-pointer -march=k8 -DNDEBUG

Installer msieve (l’ajout du flag CUDA=1 est optionnel, pour ceux qui voudraient utiliser la capacité de calcul du GPU d’une carte graphique Nvidia GTX):

$ make x86_64 all CUDA=1

Enfin, si vous n’avez pas de clé mais que vous souhaitez tout de même essayer l’attaque, vous pouvez générer une paire privée / publique de 256bits:

$ openssl genrsa 256 > key.pem

Pour récupérer la clé publique:

$ openssl rsa -pubout -in key.pem -out pubkey.pem

Et pour chiffrer un message avec la clé publique:

$ echo "Fichier protégé" > plain.txt
$ openssl rsautl -encrypt -in plain.txt -pubin -inkey pubkey.pem -out cipher.txt

Vous pouvez mettre le fichier chiffré (cypher.txt) de côté, et essayer de le cracker avec la méthode qui suit. Mais avant tout, il va falloir installer un dernier outil: PyCrypto. C’est codé en Python et cela permet de reconstruire une clé privée à partir des différents paramètres. Le téléchargement s’effectue là aussi sur le site officiel. Pour l’installation:

$ sudo aptitude install python-dev python3.4-dev
$ python setup.py build
$ python setup.py install

Utilisation des outils

 

Soit la clé publique nommé “pubkey.pem”, codé sur 256 bits. On va en extraire l’exposant:

$ openssl rsa -in pubkey.pem -pubin -text -noout | grep Exponent
Exponent: 65537 (0x10001)

L’exposant de chiffrement ‘e’ est 65537, utilisé pour obtenir un message C à partir d’un texte en clair M:

Il nous faudra aussi, et surtout, le modulo  ‘n’, à récupérer de cette manière:

$ openssl rsa -pubin -in pubkey.pem -modulus
$ KEY_HEXA=$(openssl rsa -pubin -in pubkey.pem -modulus | grep Modulus | cut -d'=' -f2)
$ echo "ibase=16;$KEY_HEXA" | bc
93359642202747747467013736832386750311141115678500109750244749945734663859651

On a récupéré toutes les informations nécessaires, notre but maintenant est de calculer l’exposant de déchiffrement via msieve, pour réaliser l’opération inverse: le déchiffrement.

Quel est le lien entre ‘d’ et ‘n’? Eh bien sans vous (ré)expliquer la génération d’une paire de clé RSA, qui au passage n’est pas non plus hyper complexe mathématiquement parlant (voir même très simple pour certains), on a la relation suivante:

e x d ≡ 1 mod phi(n)

Pas besoin de s’étaler sur le sujet, si vous ne me croyez pas, vérifiez sur wikipedia. Cependant, même si vous ne comprenez pas la relation, on voit que l’on a ‘d’ et ‘n’ sur la même ligne. On peut certainement retrouver ‘d’ (exposant de DEchiffrement pour rappel) vu que nous avons déjà le modulo ‘n’ ainsi que ‘e’, donc en gros inverser ‘e’ mod phi(n). Mais bon, calculer phi(n), la fonction indicatrice d’Euler (nombre de nombres premiers avec ‘n’ et inférieur à ce dernier), avec ‘n’ très grand serait bien trop long. L’idée consiste alors à retrouver ‘p’ et ‘q’ deux nombres premiers quelconques tel que:
n = p x q
Il vont nous permettre de reconstruire phi(n) = (p – 1) x (q – 1), formule qui ne peut s’appliquer que si ‘p’ et ‘q’ sont premiers. Allez-y! Eh bien tout le problème se trouve ici, car il fait appel à cette fameuse décomposition en produit de facteurs premiers, assez difficile à résoudre! Heureusement pour nous, msieve vient nous sauver à la dernière minute pour faire tout le boulot:

Pour lancer le calcul:

$ ./msieve -v 93359642202747747467013736832386750311141115678500109750244749945734663859651

Attention: votre ordinateur risque de s’envoler! Selon la complexité de la clé, vous pouvez aller boire un café ou revenir après vos vacances… Pour un chiffrement faible, soit une clé de 256 bits, le calcul se fait en quelques minutes seulement! Si l’attaque a réussie, vous aurez certainement une sortie qui ressemble à cela:

Msieve v. 1.46
Sun Mar  6 22:03:51 2016
random seeds: 68e979b6 1d448533
factoring 93359642202747747467013736832386750311141115678500109750244749945734663859651 (77 digits)
no P-1/P+1/ECM available, skipping
commencing quadratic sieve (77-digit input)
using multiplier of 1
using 32kb Intel Core sieve core
sieve interval: 12 blocks of size 32768
processing polynomials in batches of 17
using a sieve bound of 918899 (36471 primes)
using large prime bound of 91889900 (26 bits)
using trial factoring cutoff of 26 bits
polynomial 'A' values have 10 factors

sieving in progress (press Ctrl-C to pause)
36961 relations (18791 full + 18170 combined from 197100 partial), need 36567
36961 relations (18791 full + 18170 combined from 197100 partial), need 36567
sieving complete, commencing postprocessing
... blablabla on comprend rien ...
commencing Lanczos iteration
memory use: 3.9 MB
lanczos halted after 413 iterations (dim = 26053)
recovered 15 nontrivial dependencies
prp39 factor: 292431263854591596428266434301252986203
prp39 factor: 319253286984971135858192285581289471417
elapsed time 00:02:28

Les deux gagnants, pour 2 min 28 sec, sont donc:
– “292431263854591596428266434301252986203”
et
– “319253286984971135858192285581289471417”

” Monsieur monsieur?
– Le petit emmerdeur du fond a une question?
– Comment on fait avec une clé de 512 voir 768 bits?”

C’était prévu! Aujourd’hui il est plus probable de tomber sur des clés codées sur plus de 256 bits, mais la méthode reste la même, ou presque. J’ai pu essayer avec une clé en 768 bits, mais après 24h sans résultat j’ai arrêté le programme. En fait, il faudrait ici parler en semaines, voir en mois pour que le calcul prenne fin… Mais il existe une petite variante: vous pouvez utiliser des sites comme factordb, qui est une immense base de données, pour retrouver cette fameuse décomposition. Cependant, comme vous l’aurez compris, il faut au préalable que l’info soit renseignée… Si vous n’arrivez à rien, essayez une simple recherche du modulo dans Qwant (sans rire ça a marché pour moi avec cette dite clé de 768 bits… haha!).

“On” (ou plutôt msieve) a donc décomposé notre modulo en un produit de facteurs premiers, chouette! Mais maintenant on fait quoi? Et bien on est pas encore arrivé, mais le plus dur est fait!

Recontruire la clé privée

 

On va maintenant utiliser Gmpy puis PyCrypto, pour reconstruire la clé à partir de ‘n’, ‘e’ et ‘d’, soit respectivement le modulo, l’exposant de chiffrement et l’exposant de déchiffrement. Seulement je vous rappelle que l’on a que ‘p’ et ‘q’, c’est à dire le résultat de notre décomposition de ‘n’. Il se trouve que l’on a dans l’algorithme de RSA:

n = p x q
e x d ≡ 1 mod phi(n)

On peut donc reconstruire ‘e’ comme:

e ≡ d ^ -1 mod phi(n)

Seulement comme dit précédemment, le calcul de phi(n) avec ‘n’ très grand serait bien trop long, c’est là que réside la robustesse de RSA. On va donc utiliser une implication de la fonction indicatrice d’Euler avec nos valeurs ‘p’ et ‘q’ trouvées précédemment. La manip se fait via console python:

$ python
import gmpy
p = 292431263854591596428266434301252986203
q = 319253286984971135858192285581289471417
n = long(93359642202747747467013736832386750311141115678500109750244749945734663859651)
e = long(65537)
d = long(gmpy.invert(e, (p-1) * (q-1)))
print(d)
69133309919526523384863000524406374374368485983427192746243825479803255141243

Bien, maintenant on reconstruit notre clé privée, toujours dans la console python:

from Crypto.PublicKey import RSA
key = RSA.construct((n, e, d))
print(key.exportKey())
-----BEGIN RSA PRIVATE KEY-----
MIGsAgEAAiEAzmevVtgWOI2Ndga7uV5MWKtQalS0EGh0jRU18AyFbcMCAwEAAQIh
AKLrsLkp45BMG0b4VaEhz7wacJ2xNMMSNWEnfykBqSBhAhEA8C3yT3Oz9kLe7kkh
/rg9uQIRANwANnhO4SM9Ns2ZHmDZ5VsCEGmga05R3jVRV2WIODEjqdECEQCrxNrC
ikvL+MJuOkv2sIobAhEA1222EzcQCo8TOrTSpddvkA==
-----END RSA PRIVATE KEY-----

Tadaa!!! Maintenant, on peut mettre la clé dans un fichier, ‘privkey.pem’ par exemple, et tester le tout en chiffrant puis déchiffrant:

$ echo "Fichier protégé" > plain.txt
$ openssl rsautl -encrypt -in plain.txt -pubin -inkey pubkey.pem -out cipher.txt
$ cat cipher.txt
�f0�V���Oe$rg�?��>Y���x��:�V�
$ openssl rsautl -decrypt -in cipher.txt -inkey privkey.pem
Fichier protégé

 

Conclusion

Et voilà, on retrouve bien “Fichier protégé” alors que nous n’avions pas au départ, la clé privée en notre possession. Il est donc extrêmement facile (même si cela a été dur, une fois la mécanique digérée, ça se fait tout seul) de casser RSA en 256 bits. Pour info, ma clé publique en 768 bits, pour la quelle j’avais retrouvé la décomposition en tapant le modulo sur Qwant, a été cassée aussi! J’ai donc pu déchiffrer, même décryter, des informations illisibles au départ \o/
Pour conclure, je ne pourrai que vous conseiller d’utiliser des chiffrements forts et de se méfier quoi qu’il arrive (si nous on arrive à faire ça, imaginez de quoi est capable notre gouvernement, ou la NSA…). Chiffré n’est pas toujours signe de confidentialité. De plus, si vous avez le choix, tournez-vous plutôt vers le chiffrement El Gamal, un peu plus récent, intégrant de l’aléa et étant plus robuste (ou moins ciblé peut être). En tout cas, c’est quasiment notre seul rempart contre l’espionnage de masse (à contrario de l’espionnage ciblé…), alors faites-y un peu attention 😉