[HackTheBox] Desafio TwoForOne
O desafio indica que: “Alice enviou duas vezes a mesma mensagem para Bob.” e o material para realizar o desafio compactados em um zip, contendo duas chaves e duas mensagens (criptografadas).
Como todo o desafio, depois que você compreende o que precisa ser feito, fica fácil, mas para chegar até a decifragem é preciso gastar um pouco de neurônios, e posso dizer que aqui não precisamos de nehuma calculadora da Nasa ou qualquer coisa parecida. Precisamos da velha e pura matemática, e claro, conhecimento sobre o método RSA, um dos primeiros sistemas de criptografia de chave pública.
O Método RSA e a geração das chaves
RSA como dito é um dos primeiros algorítimos de criptografia de dados, cujo o nome se deve a três dos professores do MIT, Ronald Rivest, Adi Shamir e Leonard Adleman e fundadores da RSA Data Security, Inc.
Foi também o primeiro algorítimo a permitir criptografia e assinatura digital e uma das grandes inovações em criptografia de chave pública.
Neste método as chaves são geradas da seguinte maneira:
1. Pegamos de forma aleatória dois números primos grandes p e q, da ordem de 10¹⁰⁰ no mínimo (Apenas para efeito de curiosidade podemos também dizer da ordem de um googol, não confunda com o nome do buscador)
2. Calcule n=pq
3. Calcule a função totiente de Euler em n: ϕ(n) = (p-1)(q-1)
4. Escolhemos um inteiro e em que 1 < e < ϕ(n), de forma que e e ϕ(n) tenham o único divisor comum sendo 1
5. Calcule d de forma que de ≡ 1 (mod ϕ(n)), ou seja, d precisa ser inverso multiplicativo de e em (mod ϕ(n)).
Por fim, temos nossa chave pública: o par (n, e,) e a chave privada: a tripla (p, q, d)
Decifragem e solução do desafio.
Não irei entrar no como faz a cifragem, mas em resumo para decifrar ou recuperar a mensagem m da mensagem cifrada c usando a respectiva chave privada do receptor n e d, basta fazer outra potenciação modular: cᵈ ≡ m (mod n).
Apesar de ser matemática pura, não acho que temos que sair criando nossas próprias funções para resolver o desafio, não precisamos reinventar a roda.
Existe uma ferramenta no Github chamada RsaCtfTool que consiste em diversos ataques e exploração RSA e principalmente para CTF.
Estou presumindo que você saiba minimamente clonar e usar o pip do python para instalar as dependências do pacote.
Se usarmos o comando cat ou um edito de sua preferência em ambas as chaves públicas, notaremos que se parecem muito, para tirar prova disso, vamos usar a ferramenta RsaCtfTool com a opção dumpkey para que ele possa nos mostrar quem é o (n, e) da nossa chave pública, conforme explicado acima. Execute o comando para ambas as chaves e veja o conteúdo de n.
Agora que sabemos que as duas chaves usam o mesmo n, podemos usar um ataque conhecido como Ataque de Módulos Comum em RSA (RSA Common Modulus Attack).
O ataque consiste em pegar dois textos cifrados, criptografados com o mesmo módulo n, mas com um expoente e diferente. Então é possível recuperar o texto simples da mensagem m.
Para que esse ataque funcione, devemos lembrar do passo 4 da geração das chaves, onde o maior denominador comum dos dois expoentes deve ser 1: mdc (e1, e2) = 1.
Iremos usar um script chamado RSA-Common-Modulus-Attack que você encontra no Github também, seu uso é bem simples, após clonar e instalar os requerimentos usando o pip install do Python , então execute o comando conforme abaixo.
