Générateur de Porte Dérobée RSA

Ce dépôt contient le code pour reproduire l'attaque de piège secrètement intégré avec protection universelle (SETUP) sur la génération de clés RSA proposée par Young & Yung, 1996. Compte tenu du potentiel de cette attaque, ne faites jamais confiance aux systèmes de génération de clés en boîte noire.

Références : - Présentation de l'algorithme - Article original complet

Utilisation

Commencez par générer vos clés d'attaquant, puis générez les clés piégées.

# construction
go build generator.go
go build decryptor.go

# (option) générez vos clés RSA (légitimes)
openssl genrsa -out attacker_priv.pem 2048
openssl rsa -in attacker_priv.pem -pubout -out attacker_pub.pem

# génération des clés piégées
./generator -pk attacker_pub.pem

# sortie
------
[*] Génération d'un SETUP de 4096 bits...
    > Cela peut prendre un moment...
------

------
[*] Paramètres trouvés :
    > Longueur en bits de p : 256
    > Longueur en bits de q : 3840
    > Longueur en bits de n : 4096 // longueur de la clé finale
    > Tentatives nécessaires : 542692
------

------
[*] Clés piégées enregistrées dans :
    > Clé privée : out/victim_priv.pem
    > Clé publique : out/victim_pub.pem
------

------
[*] Test avec :
    > echo -n "hello world" | openssl pkeyutl -encrypt -inkey out/victim_pub.pem -pubin -out out/cipher.bin // chiffrer avec la clé publique SETUP
    > ./decryptor -pk out/victim_pub.pem -sk <attacker_priv.pem> -c out/cipher.bin // déchiffrer avec la clé secrète
------

Si la victime fait confiance aux clés reçues (qui ont l'air parfaitement normales et fonctionnent comme prévu), elle les utilisera pour chiffrer certaines données, par exemple :

# chiffrer
echo -n "SuperSecretSh1tttttt" | openssl pkeyutl -encrypt -inkey out/victim_pub.pem -pubin -out out/cipher.bin

# vérifier
echo out/cipher.bin | base64

La subtilité est que l'attaquant peut déchiffrer le message en utilisant la clé publique de la victime et sa propre clé privée. Par exemple :

# déchiffrer
./decryptor -pk out/victim_pub.pem -sk attacker_priv.pem -c out/cipher.bin

# sortie
------
[*] Chargement des clés et du texte chiffré...
    > Clé publique de la victime chargée
    > Clé privée de l'attaquant chargée
    > Texte chiffré chargé
------

------
[*] Dérivation de la clé privée à partir du SETUP...
    > Taille de la clé publique : 2048
    > Factorisation valide trouvée en utilisant s1
    > p récupéré (longueur en bits : 256)
    > q récupéré (longueur en bits : 3840)
    > d récupéré (longueur en bits : 4092)
------

--- MESSAGE DÉCHIFFRÉ ---
 ��ϓ�f�~~P�k(���t%Tp��i/3qHvr��s        �x��f����){���\c�f�
�.���n�=y���
�R}��r_2���q�H>u�K��%EB�,�yNZ���5�1��:�>��%O�Y/�,��J$a���`��
                                      �ì�|��k&r��1�5H˚�+����U�/4p� ���֒9���#Gmծ����=�gfq��Pg,w�g)�E^���ͻ����-2�t�2-v
        �y�.�Ȟ�<0S�i8�w�+�\���D/��/���e���sf?18��l�����Э�Y�
�uk��D҃C�P�leS�<���Cy�oI�I�˴�O�B'
g;L9{b�o.���y.���+J���
2А�$�޶��WƇ�B���υk�D�SuperSecretSh1tttttt
-------------------------

Comment ça fonctionne ?

Si vous voulez tous les détails de cette attaque, consultez les deux liens dans le préambule. Voici un aperçu de haut niveau de cette attaque :

Génération normales de clés RSA (Référence)

Générer deux grands nombres premiers aléatoires p et q (≈1024 bits chacun pour une clé de 2048 bits).
Calculer n = p · q.
Choisir l'exposant public e (généralement 2¹⁶+1).
Calculer d tel que e · d ≡ 1 mod φ(n) avec φ(n) = (p–1)(q–1).
Clé publique : (n, e) ; Clé privée : d.
Chiffrement : c = mᵉ mod n ; Déchiffrement : m = cᵈ mod n.

Génération de clés RSA kleptographique (SETUP)

Choisir un nombre premier s de 1024 bits et calculer p = H(s) (répéter jusqu'à ce que p soit premier).
Chiffrer s avec la clé de l'attaquant : c = sᴱ mod N.
Choisir un z aléatoire.
Construire q de sorte que c || z = p · q + r pour un certain reste r arbitraire ; réessayer si q n'est pas premier.
Calculer n = p · q, définir e normalement, et calculer d comme dans le RSA standard.
Sortir une clé publique (n, e) et une clé privée d d'apparence normale — mais avec une porte dérobée cachée.

Récupération de la clé privée de la victime par l'attaquant

Prendre les n/2 bits les plus significatifs de n comme u (≈1024 bits).
Définir c₁ = u et c₂ = u + 1 (pour gérer une éventuelle perte de bits dans l'encapsulation c||z).
Déchiffrer avec la clé privée de l'attaquant D :
- s₁ = c₁ᴰ mod N, s₂ = c₂ᴰ mod N.
Calculer les candidats premiers :
- p₁ = H(s₁), p₂ = H(s₂).
Calculer q₁ = n / p₁ et q₂ = n / p₂ ; la division qui donne un entier révèle le vrai p et q.
Recalculer d à partir de (p, q, e).
L'attaquant récupère désormais complètement la clé privée RSA de la victime.

Améliorations

Actuellement, le programme utilise ProbablyPrime() pour vérifier si un n donné est premier. ProbablyPrime effectue n tests de Miller-Rabin pour vérifier si x est premier. S'il retourne true, x est premier avec une probabilité de 1 - 1/4^n. S'il retourne false, x n'est pas premier. Par conséquent, il existe une probabilité non nulle que la génération de la porte dérobée échoue (Q ne peut pas être résolu). Relancez simplement l'outil si c'est le cas.

Travaux futurs

Prendre en charge les formats suivants : ssh-rsa, ssh-dsa, ssh-ecdsa. SETUP est théoriquement possible pour ceux-ci, ssh-ed25519 est résistant à SETUP. La clé privée SSH pourrait alors être dérivée des clés publiques récupérées avec ssh-keyscan. Je prévois également de fournir une petite utilitaire pour hooker ssh-keygen sur une machine compromise afin de piéger automatiquement les clés suivantes... À suivre.

RSA-Backdoor

Populaires