Verificando Seguranca de Modulo RSA em Relacao ao Expoente Publico e

O algoritmo de "criptografia"(cifragem) do RSA eh descrito da seguinte forma:

C = M ^ e (mod N)

Onde temos:

C = Texto Cifrado
M = Texto Limpo
e = expoente publico
N = Modulo N (Numero inteiro gigante gerado a partir de dois primos(p e q)).

Nesse tipo de ataque(que podemos chamar de recuperacao de mensagens), nao nos interessa
o algoritmo de decriptografia.

Pela aritmetica modular, nos sabemos que se o valor de "e" for pequeno e o valor
de N for gigante, a segurança da mensagem vai passar a depender do tamanho da mesma,
exemplo:

M = ABCD

A = 41
B = 42
C = 43
D = 44

podemos ter M = 41424344. Elevando esse valor por um numero "e" pequeno, exemplo 3, teremos:

C = 41424344 ^ 3 (mod N)

Abaixo temos um programa para calcular isso:

----------- RSA_m_elevado_e.c ---------------
/*
 * Intruders Tiger Team Security
 * http://www.intruders.com.br/
 *
 * Brute Force Colision using RSA.
 *
 * Glaudson Ocampos - <glaudson@securitylabs.com.br>
 *
 * Compile com:
 * $ gcc -o RSA_m_elevado_e RSA_m_elevado_e.c -lssl -Wall
 */

#include <stdio.h>
#include <unistd.h>
#include <sys/types.h>

#include <openssl/bn.h>
#include <openssl/rsa.h>
#include <openssl/engine.h>

#define  ERRO                           -1

void
uso(char *progname){
  fprintf(stdout,"BigNUM - M elevado a e.\n");
  fprintf(stdout,"Uso: %s <M> <expoente>\n", progname);
  fflush(stdout);
}

int
main(int argc, char *argv[]){
 BIGNUM *e = NULL; 
 BIGNUM *m = NULL;
 BIGNUM *r = NULL;
 BN_CTX *ctx = NULL;

 if(argc < 2){
  uso(argv[0]);
  _exit(0);
 }

 ctx = BN_CTX_new();
 if(ctx == NULL){
  fprintf(stderr,"Erro na criacao de BN_CTX\n");
  fflush(stderr);
  _exit(ERRO);
 }


 m = BN_CTX_get(ctx);  
 BN_hex2bn(&m,argv[1]);

 e = BN_CTX_get(ctx);    
 BN_hex2bn(&e,argv[2]);

 r = BN_CTX_get(ctx);
 if(BN_exp(r,m,e,ctx) == 0){
   fprintf(stderr,"Erro na elevacao a potencia!\n");
   BN_free(m);
   BN_free(r);
   BN_free(e);
   _exit(ERRO);
 }

 fprintf(stdout,"Valor: %s\n",BN_bn2hex(r));

 BN_free(m);
 BN_free(e); 
 BN_free(r); 

 return 0;
} 

---------------------------------------------

Vamos compilar e executar para ver o output:

bash-4.2# gcc -o RSA_m_elevado_e RSA_m_elevado_e.c -lssl -Wall
bash-4.2# ./RSA_m_elevado_e 
BigNUM - M elevado a e.
Uso: ./RSA_m_elevado_e <M> <expoente>
bash-4.2# ./RSA_m_elevado_e 3 2
Valor: 09
bash-4.2# ./RSA_m_elevado_e 41424344 3
Valor: 043D9EDD651B18EA9ABF5C40

Apenas olhando, ja sabemos que esse valor eh pequeno se comparado
com modulos N gigantes como de 1024 bits, 2048 e por ai vai:

bash-4.2# itts_rsa_analyzer 
Intruders Tiger Team Security
http://www.intruders.com.br
ITTS - RSA Analyzer - Versao v1.0
Desenvolvido por Glaudson Ocampos <glaudson@intruders.com.br>

itts_rsa_analyzer [opcoes]

-n <bignum>                     Checa tamanho de BIGNUM (em hexadecimal)
-p <bignum>                     Checa se BIGNUM (em hexadecimal) eh primo
-x <certificado>                Extrai Informacoes de um Certificado
-a <tamanho_modulo_N>           Exibe valor aceitavel para expoente publico (e) em relacao ao modulo N (mod N)
-h                              Exibe essa tela de ajuda.


bash-4.2# itts_rsa_analyzer -n 043D9EDD651B18EA9ABF5C40
Intruders Tiger Team Security
http://www.intruders.com.br
ITTS - RSA Analyzer - Versao v1.0

*** Numero de Bits: 91 ***
------------------------------------


Ou seja, apenas 91 bits. Vamos fazer entao uma simples
verificacao da aritmetica modular, usando um valor alto para N,
para isso podemos usar o seguinte programa:

------------- RSA_checa_m_em_relacao_N.c ---------------
/*
 * Intruders Tiger Team Security
 * http://www.intruders.com.br/
 *
 * RSA - Verificar Mensagem cifrada com expoente pequeno em relacao
 * ao Modulo N.
 * Glaudson Ocampos - <glaudson@securitylabs.com.br>
 *
 *
 */

#include <stdio.h>
#include <unistd.h>
#include <sys/types.h>

#include <openssl/bn.h>
#include <openssl/rsa.h>
#include <openssl/engine.h>

#define  ERRO   -1

void
uso(char *progname){
  fprintf(stdout,"RSA - Checa se mensagem cifrada eh menor que mod N.\n");
  fprintf(stdout,"Uso: %s <M_elevado_e> <modulo_N>\n", progname);
  fflush(stdout);
}

int
main(int argc, char *argv[]){
 BIGNUM *N = NULL;
 BIGNUM *m = NULL;
 BIGNUM *C = NULL;
 BN_CTX *ctx = NULL;

 if(argc < 2){
  uso(argv[0]);
  _exit(0);
 }

 ctx = BN_CTX_new();
 if(ctx == NULL){
  fprintf(stderr,"Erro na criacao de BN_CTX\n");
  fflush(stderr);
  _exit(ERRO);
 }

 m = BN_CTX_get(ctx);
 BN_hex2bn(&m,argv[1]);

 N = BN_CTX_get(ctx);  
 BN_hex2bn(&N,argv[2]);

 /* Executamos C = M (mod N) */

 C = BN_CTX_get(ctx);
 BN_nnmod(C,m,N,ctx);   
 
 fprintf(stdout,"Valor: %s\n",BN_bn2hex(C));

 BN_free(N);
 BN_free(m); 
 BN_free(C); 

 return 0;
} 

----------------------------

Compilando e executando o mesmo, temos:

bash-4.2# gcc -o RSA_checa_m_em_relacao_N RSA_checa_m_em_relacao_N.c -lssl -Wall
bash-4.2# ./RSA_checa_m_em_relacao_N 
RSA - Checa se mensagem cifrada eh menor que mod N.
Uso: ./RSA_checa_m_em_relacao_N <M_elevado_e> <modulo_N>
bash-4.2# ./RSA_checa_m_em_relacao_N 2 11
Valor: 02
bash-4.2# ./RSA_checa_m_em_relacao_N 043D9EDD651B18EA9ABF5C40 
B87BD0B4783DF3CB4611F36F5B1FB7DDDCF1860E9FF745DED447AE50FA372C4682D969EAFD93DB4F10E779666591D4C4F3C1512667DE1F86859FDB5F4AD8DC7FBFB7D0696621E54D031135286E40DF478CC101EFA832E143206AE112450476559439CA6F49CAEDCD18D12F28A44DCE2DC23465A41E51767186168A700914CD33
Valor: 043D9EDD651B18EA9ABF5C40

Podemos verificar que o valor de saida eh o mesmo valor gerado em M elevado a "e".

Entao, se de algum modo, capturamos o dado (seja via sniffing, man-in-the-middle e etc)
e a chave RSA tiver um expoente publico "e" pequeno e um "modulo N" grande, entao podemos
resolver uma simples equacao para "extrair" o texto em modo limpo.

A equeacao eh a enesima raiz de C.

     e_____
M =  V C


Abaixo podemos ver um programa pra isso:

-------------- RSA-extrai.c ---------------
/*
 * Intruders Tiger Team Security
 * http://www.intruders.com.br/
 * 
 * RSA - Extrai a raiz enezima.
 * Glaudson Ocampos - <glaudson@securitylabs.com.br>
 * 
 * 
 * Compile com:
 * $ gcc -o RSA_extrai RSA_extrai.c -lmpir -Wall
 */


#include <stdio.h> 
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#include <mpir.h>

void
uso(char *progname){   
        fprintf(stdout,"%s <texto_cifrado> <valor_de_e>\n",progname);
        fflush(stdout);
        _exit(0);
}       
        

int
main(int argc, char *argv[]){
        mpz_t rop;
        mpz_t op;
        unsigned long int n =0;
        
 
        if(argc < 3){
                uso(argv[0]);  
        }
   
        mpz_init(rop);
        mpz_init(op);
 
        mpz_init_set_str(op,argv[1],16 ); //hexadecimal to int;
        n = atoi(argv[2]);

        mpz_root(rop,op, n);

        gmp_printf("Valor: %Zx\n",rop, rop);

        mpz_clear(rop);
        mpz_clear(op);

        return 0;
}
        
---------------------------------

bash-4.2# ./RSA_extrai                           
./RSA_extrai <texto_cifrado> <valor_de_e>
bash-4.2# ./RSA_extrai 043D9EDD651B18EA9ABF5C40 3
Valor: 41424344
bash-4.2#


Entao, eh possivel extrairmos o texto limpo quando o valor de "e"
eh pequeno em relacao ao valor de N.


Referencias:

"Cryptanalysis of RSA and Its Variantes" - M. Jason Hinek;

"Cryptanalytic Attacks on RSA" - Song Y. Yan.