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

어떻게 동작하나요?

이 공격의 전체 세부 사항을 원한다면 서문의 두 링크를 확인하세요. 이 공격의 높은 수준의 개요는 다음과 같습니다:

일반 RSA 키 생성 (기준)

2048비트 키를 위해 각각 약 1024비트 크기의 두 개의 큰 난수 소수 p와 q를 생성합니다.
n = p · q를 계산합니다.
공개 지수 e를 선택합니다 (일반적으로 2¹⁶+1).
**φ(n) = (p–1)(q–1)**일 때 **e · d ≡ 1 mod φ(n)**이 되도록 d를 계산합니다.
공개 키: (n, e); 개인 키: d.
암호화: c = mᵉ mod n; 복호화: m = cᵈ mod n.

클렙토그래픽 (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 개인 키를 완전히 복구합니다.

개선 사항

현재 프로그램은 주어진 n이 소수인지 확인하기 위해 ProbablyPrime()을 사용합니다. ProbablyPrime은 x가 소수인지 확인하기 위해 n회의 Miller-Rabin 테스트를 수행합니다. true를 반환하면 x는 1 - 1/4^n의 확률로 소수입니다. false를 반환하면 x는 소수가 아닙니다. 따라서 백도어 생성이 실패할 확률 (Q를 풀 수 없는 경우)은 0이 아닙니다. 그런 경우에는 도구를 다시 실행하세요.

향후 작업

다음 형식을 지원합니다: ssh-rsa, ssh-dsa, ssh-ecdsa. 이들에 대해 SETUP는 이론적으로 가능하며, ssh-ed25519는 SETUP에 저항력이 있습니다. 이후 ssh-keyscan으로 수집한 공개 키에서 개인 ssh 키를 유도할 수 있습니다. 또한 손상된 호스트에서 ssh-keygen을 후킹하여 추가 키에 자동으로 백도어를 삽입하는 작은 유틸리티를 제공할 계획입니다... TBC.

RSA-Backdoor

인기