Generatore di Backdoor RSA

Questo repository contiene il codice per riprodurre l'attacco Secretly Embedded Trapdoor with Universal Protection (SETUP) sulla generazione di chiavi RSA proposto da Young & Yung, 1996. Considerando il potenziale di questo attacco, non fidarti mai di sistemi di generazione di chiavi a scatola nera.

Riferimenti: - Presentation of the algorithm - Original full paper

Utilizzo

Inizia generando le tue chiavi dell'attaccante e poi genera le chiavi con backdoor.

# 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
------

Se la vittima si fida delle chiavi ricevute (che sembrano perfettamente normali e funzionano come previsto) le userà per crittografare alcuni dati, ad esempio:

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

# verify
echo out/cipher.bin | base64

Il colpo di scena è che l'attaccante può decifrare il messaggio usando la chiave pubblica della vittima e la propria chiave privata. Ad esempio:

# 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
-------------------------

Come funziona ?

Se vuoi i dettagli completi di questo attacco, controlla i due link nel preambolo. Una panoramica ad alto livello di questo attacco è la seguente:

Generazione normale di chiavi RSA (Baseline)

Genera due grandi numeri primi casuali p e q (≈1024 bit ciascuno per una chiave a 2048 bit).
Calcola n = p · q.
Scegli l'esponente pubblico e (tipicamente 2¹⁶+1).
Calcola d tale che e · d ≡ 1 mod φ(n) con φ(n) = (p–1)(q–1).
Chiave pubblica: (n, e); Chiave privata: d.
Crittografia: c = mᵉ mod n; Decifratura: m = cᵈ mod n.

Generazione di chiavi RSA cleptografica (SETUP)

Scegli un numero primo s a 1024 bit e calcola p = H(s) (ripeti finché p non è primo).
Crittografa s con la chiave dell'attaccante: c = sᴱ mod N.
Scegli un z casuale.
Costruisci q in modo che c || z = p · q + r per un resto r arbitrario; riprova se q non è primo.
Calcola n = p · q, imposta e normalmente e calcola d come nell'RSA standard.
Output della chiave pubblica (n, e) e della chiave privata d dall'aspetto normale — ma con una botola nascosta.

Recupero della chiave privata della vittima da parte dell'attaccante

Prendi i primi n/2 bit di n come u (≈1024 bit).
Definisci c₁ = u e c₂ = u + 1 (per gestire la possibile perdita di bit nell'incorporamento di c||z).
Decifra con la chiave privata dell'attaccante D:
- s₁ = c₁ᴰ mod N, s₂ = c₂ᴰ mod N.
Calcola i primi candidati:
- p₁ = H(s₁), p₂ = H(s₂).
Calcola q₁ = n / p₁ e q₂ = n / p₂; la divisione che produce un intero rivela il vero p e q.
Ricalcola d da (p, q, e).
L'attaccante ora recupera completamente la chiave privata RSA della vittima.

Miglioramenti

Attualmente il programma utilizza ProbablyPrime() per verificare se un dato n è primo. ProbablyPrime esegue n test di Miller-Rabin per verificare se x è primo. Se restituisce true, x è primo con probabilità 1 - 1/4^n. Se restituisce false, x non è primo. Di conseguenza, esiste una probabilità non nulla che la generazione della backdoor fallisca (Q non può essere risolto). Basta rieseguire lo strumento in tal caso.

Lavori futuri

Supporto per i seguenti formati: ssh-rsa, ssh-dsa, ssh-ecdsa. SETUP è teoricamente possibile per questi, ssh-ed25519 è resistente a SETUP. La chiave privata ssh potrebbe quindi essere derivata dalle chiavi pubbliche ottenute con ssh-keyscan. Ho anche intenzione di fornire una piccola utility per agganciare ssh-keygen su un host compromesso per backdoorare automaticamente altre chiavi... Da definire.

RSA-Backdoor

Più Popolari