Generador de Puerta Trasera RSA

Este repositorio contiene código para reproducir el ataque de Trampilla Secretamente Incrustada con Protección Universal (SETUP) en la generación de claves RSA propuesto por Young & Yung, 1996. Dado el potencial de este ataque, nunca confíe en sistemas de generación de claves en caja negra.

Referencias: - Presentación del algoritmo - Artículo original completo

Uso

Comience generando sus claves de atacante y luego genere las claves con puerta trasera.

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

# (option) generate your (legit) RSA keys
openssl genrsa -out attacker_priv.pem 2048
openssl rsa -in attacker_priv.pem -pubout -out attacker_pub.pem

# generate backdoored keys
./generator -pk attacker_pub.pem

# output
------
[*] Generating 4096-bits SETUP...
    > This may take a while...
------

------
[*] Found parameters:
    > p bit length: 256
    > q bit length: 3840
    > n bit length: 4096 // final key length
    > Attempts needed: 542692
------

------
[*] Backdoored keys saved to:
    > Private key: out/victim_priv.pem
    > Public key:  out/victim_pub.pem
------

------
[*] Test with:
    > echo -n "hello world" | openssl pkeyutl -encrypt -inkey out/victim_pub.pem -pubin -out out/cipher.bin // encrypt with SETUP PK
    > ./decryptor -pk out/victim_pub.pem -sk <attacker_priv.pem> -c out/cipher.bin // decrypt with SK
------

Si la víctima confía en las claves recibidas (que se ven perfectamente normales y funcionan como se espera), las usará para cifrar algunos datos, por ejemplo:

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

# verify
echo out/cipher.bin | base64

El truco es que el atacante puede descifrar el mensaje usando la clave pública de la víctima y su propia clave privada. Por ejemplo,

# decrypt
./decryptor -pk out/victim_pub.pem -sk attacker_priv.pem -c out/cipher.bin

# output
------
[*] Loading keys and ciphertext...
    > Loaded victim public key
    > Loaded attacker private key
    > Loaded ciphertext
------

------
[*] Deriving private key from SETUP...
    > PK bitsize: 2048
    > Found valid factorization using s1
    > Recovered p (bit length: 256)
    > Recovered q (bit length: 3840)
    > Recovered d (bit length: 4092)
------

--- DECRYPTED MESSAGE ---
 ��ϓ�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
-------------------------

¿Cómo funciona?

Si desea los detalles completos de este ataque, revise los dos enlaces del preámbulo. Una visión general de alto nivel de este ataque es la siguiente:

Generación de Claves RSA Normal (Línea Base)

Generar dos primos grandes aleatorios p y q (≈1024 bits cada uno para una clave de 2048 bits).
Calcular n = p · q.
Elegir exponente público e (típicamente 2¹⁶+1).
Calcular d tal que e · d ≡ 1 mod φ(n) con φ(n) = (p–1)(q–1).
Clave pública: (n, e); Clave privada: d.
Cifrado: c = mᵉ mod n; Descifrado: m = cᵈ mod n.

Generación de Claves RSA Cleptográfica (SETUP)

Elegir un primo s de 1024 bits y calcular p = H(s) (repetir hasta que p sea primo).
Cifrar s con la clave del atacante: c = sᴱ mod N.
Elegir z aleatorio.
Construir q de modo que c || z = p · q + r para algún resto r arbitrario; reintentar si q no es primo.
Calcular n = p · q, establecer e normalmente y calcular d como en RSA estándar.
Salida de clave pública de apariencia normal (n, e) y clave privada d — pero con una trampilla oculta.

Recuperación de la Clave Privada de la Víctima por parte del Atacante

Tomar los n/2 bits superiores de n como u (≈1024 bits).
Definir c₁ = u y c₂ = u + 1 (para manejar la posible pérdida de bits en la incrustación de c||z).
Descifrar con la clave privada del atacante D:
- s₁ = c₁ᴰ mod N, s₂ = c₂ᴰ mod N.
Calcular primos candidatos:
- p₁ = H(s₁), p₂ = H(s₂).
Calcular q₁ = n / p₁ y q₂ = n / p₂; la división que dé un entero revela el verdadero p y q.
Recalcular d a partir de (p, q, e).
El atacante recupera totalmente la clave privada RSA de la víctima.

Mejoras

Actualmente, el programa usa ProbablyPrime() para verificar si un n dado es primo. ProbablyPrime realiza n pruebas de Miller-Rabin para comprobar si x es primo. Si devuelve verdadero, x es primo con probabilidad 1 - 1/4^n. Si devuelve falso, x no es primo. Como tal, existe una probabilidad no nula de que la generación de la puerta trasera falle (Q no se puede resolver). Simplemente ejecute de nuevo la herramienta si es el caso.

Trabajos futuros

Compatibilidad con los siguientes formatos: ssh-rsa, ssh-dsa, ssh-ecdsa. SETUP es teóricamente posible para estos, ssh-ed25519 es resistente a SETUP. La clave privada SSH podría entonces derivarse de claves públicas obtenidas con ssh-keyscan. También planeo proporcionar una pequeña utilidad para enganchar ssh-keygen en un host comprometido para añadir automáticamente puertas traseras a más claves... Por determinar.

RSA-Backdoor

Más Populares