Gerador de Backdoor RSA

Este repositório contém código para reproduzir o ataque de Alçapão Secretamente Embutido com Proteção Universal (SETUP) na geração de chaves RSA proposto por Young & Yung, 1996. Considerando o potencial deste ataque, nunca confie em sistemas de geração de chaves do tipo caixa-preta.

Referências: - Apresentação do algoritmo - Artigo original completo

Uso

Comece gerando suas chaves de atacante e depois gere as chaves com 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 a vítima confiar nas chaves recebidas (que parecem perfeitamente normais e funcionam como esperado), ela as usará para criptografar alguns dados, por exemplo:

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

# verify
echo out/cipher.bin | base64

A reviravolta é que o atacante pode descriptografar a mensagem usando a chave pública da vítima e a sua própria chave privada. Por exemplo:

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

Como funciona?

Se você quiser os detalhes completos deste ataque, consulte os dois links no preâmbulo. Uma visão geral de alto nível deste ataque é a seguinte:

Geração Normal de Chaves RSA (Linha de Base)

Gere dois números primos grandes aleatórios p e q (≈1024 bits cada para uma chave de 2048 bits).
Calcule n = p · q.
Escolha o expoente público e (tipicamente 2¹⁶+1).
Calcule d tal que e · d ≡ 1 mod φ(n) com φ(n) = (p–1)(q–1).
Chave pública: (n, e); Chave privada: d.
Criptografia: c = mᵉ mod n; Descriptografia: m = cᵈ mod n.

Geração de Chaves RSA Cleptográfica (SETUP)

Escolha um primo s de 1024 bits e calcule p = H(s) (repita até p ser primo).
Criptografe s com a chave do atacante: c = sᴱ mod N.
Escolha um z aleatório.
Construa q de modo que c || z = p · q + r para algum resto arbitrário r; tente novamente se q não for primo.
Calcule n = p · q, defina e normalmente e calcule d como no RSA padrão.
Gere uma chave pública (n, e) e uma chave privada d de aparência normal — mas com um alçapão oculto.

Recuperação da Chave Privada da Vítima pelo Atacante

Pegue os n/2 bits superiores de n como u (≈1024 bits).
Defina c₁ = u e c₂ = u + 1 (para lidar com possível perda de bits no embutimento de c||z).
Descriptografe com a chave privada D do atacante:
- s₁ = c₁ᴰ mod N, s₂ = c₂ᴰ mod N.
Calcule os primos candidatos:
- p₁ = H(s₁), p₂ = H(s₂).
Calcule q₁ = n / p₁ e q₂ = n / p₂; a divisão que resultar em um inteiro revela os verdadeiros p e q.
Recalcule d a partir de (p, q, e).
O atacante agora recupera completamente a chave privada RSA da vítima.

Melhorias

Atualmente, o programa usa ProbablyPrime() para verificar se um determinado n é primo. ProbablyPrime executa n testes de Miller-Rabin para verificar se x é primo. Se retornar true, x é primo com probabilidade 1 - 1/4^n. Se retornar false, x não é primo. Dessa forma, há uma probabilidade diferente de zero de que a geração do backdoor falhe (Q não pode ser resolvido). Basta executar a ferramenta novamente se for o caso.

Trabalhos futuros

Suporte aos seguintes formatos: ssh-rsa, ssh-dsa, ssh-ecdsa. SETUP é teoricamente possível para estes; ssh-ed25519 é resistente a SETUP. A chave ssh privada poderia então ser derivada de chaves públicas obtidas com ssh-keyscan. Também estou planejando fornecer um pequeno utilitário para interceptar o ssh-keygen em hosts comprometidos e colocar backdoor automaticamente em outras chaves... A continuar.

RSA-Backdoor

Mais Populares