RSA バックドアジェネレータ

このリポジトリには、Young & Yung（1996）によって提案されたRSA鍵生成に対するSETUP（Secretly Embedded Trapdoor with Universal Protection）攻撃を再現するコードが含まれています。この攻撃の可能性を考慮すると、ブラックボックス鍵生成システムを決して信頼しないでください。

参考文献： - アルゴリズムのプレゼンテーション - オリジナルの完全な論文

使用方法

まず攻撃者の鍵を生成し、次にバックドア付きの鍵を生成します。

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

もし被害者が受け取った鍵（完全に正常に見え、期待通りに機能する）を信頼した場合、それを使ってデータを暗号化します。例：

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

# verify
echo out/cipher.bin | base64

ここで重要なのは、攻撃者が被害者の公開鍵と自身の秘密鍵を使ってメッセージを復号できることです。例：

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

どのように動作するか？

この攻撃の詳細については、前文の2つのリンクを参照してください。この攻撃の高レベルの概要は次のとおりです：

通常のRSA鍵生成（ベースライン）

2つの大きなランダム素数 p と q を生成します（2048ビット鍵の場合、それぞれ約1024ビット）。
n = p · q を計算します。
公開指数 e を選択します（通常は2¹⁶+1）。
e · d ≡ 1 mod φ(n) となる d を計算します。ただし φ(n) = (p–1)(q–1) です。
公開鍵: (n, e); 秘密鍵: d。
暗号化: c = mᵉ mod n; 復号: m = cᵈ mod n。

Kleptographic（SETUP）RSA鍵生成

1024ビットの素数 s を選択し、p = H(s) を計算します（pが素数になるまで繰り返す）。
s を攻撃者の鍵で暗号化: c = sᴱ mod N。
ランダムな z を選択します。
任意の余り r に対して c || z = p · q + r となるように q を構築します。qが素数でない場合は再試行します。
n = p · q を計算し、通常通りにeを設定し、標準RSAと同様に d を計算します。
通常に見える公開鍵 (n, e) と秘密鍵 d を出力しますが、隠されたトラップドアが埋め込まれています。

攻撃者による被害者の秘密鍵の復元

n の上位 n/2 ビット を u として取得します（約1024ビット）。
c₁ = u および c₂ = u + 1 と定義します（c||zの埋め込みでビット損失の可能性に対処）。
攻撃者の秘密鍵 D で復号:
- s₁ = c₁ᴰ mod N, s₂ = c₂ᴰ mod N。
候補素数を計算:
- p₁ = H(s₁), p₂ = H(s₂)。
q₁ = n / p₁ および q₂ = n / p₂ を計算し、整数になる除算が真の p と q を明らかにします。
(p, q, e)から d を再計算します。
攻撃者は被害者のRSA秘密鍵を完全に復元します。

改善点

現在、プログラムはProbablyPrime()を使用して与えられたnが素数かどうかをチェックしています。ProbablyPrimeはn回のミラーラビンテストを実行し、xが素数かどうかをチェックします。真を返した場合、xは確率1 - 1/4^nで素数です。偽を返した場合、xは素数ではありません。そのため、バックドア生成が失敗する確率はゼロではありません（Qが解けない）。その場合はツールを再実行してください。

今後の作業

以下のフォーマットをサポート予定：ssh-rsa, ssh-dsa, ssh-ecdsa。これらのフォーマットでは理論的にSETUPが可能ですが、ssh-ed25519はSETUPに対して耐性があります。ssh-keyscanで取得した公開鍵から秘密SSH鍵を導出できるようになります。また、侵害されたホスト上でssh-keygenをフックし、後続の鍵に自動的にバックドアを仕込む小さなユーティリティも提供する予定です...続く。

RSA-Backdoor

人気