big integer calculator – Página 3 – Blog de Cracking y Hacking ético

Introducción
Funcionamiento de RSA
OllyDbg
Calculando un serial válido
Ejemplo operacional
Keygen
Links

Introducción

Empezamos con lo que espero que sea una serie de crackmes RSA. En este caso en particular y como el propio autor nos adelanta, se trata de RSA-200.

En criptografía, RSA (Rivest, Shamir y Adleman) es un sistema criptográfico de clave pública desarrollado en 1977. Es el primer y más utilizado algoritmo de este tipo y es válido tanto para cifrar como para firmar digitalmente.

Funcionamiento de RSA

Inicialmente es necesario generar aleatoriamente dos números primos grandes, a los que llamaremos p y q.
A continuación calcularemos n como producto de p y q:
```
n = p * q
```
Se calcula fi:
```
fi(n)=(p-1)(q-1)
```
Se calcula un número natural e de manera que MCD(e, fi(n))=1 , es decir e debe ser primo relativo de fi(n). Es lo mismo que buscar un numero impar por el que dividir fi(n) que de cero como resto.
Mediante el algoritmo extendido de Euclides se calcula d que es el inverso modular de e.
```
Puede calcularse d=((Y*fi(n))+1)/e para Y=1,2,3,... hasta encontrar un d entero.
```
El par de números (e,n) son la clave pública.
El par de números (d,n) son la clave privada.
Cifrado: La función de cifrado es.
```
c = m^e mod n
```
Descifrado: La función de descifrado es.
```
m = c^d mod n
```

OllyDbg

Con OllyDbg analizamos la parte del código que nos interesa.

00401065  |>push    19                          ; /Count = 19 (25.)
00401067  |>push    00404330                    ; |Buffer = dihux_ke.00404330
0040106C  |>push    2711                        ; |ControlID = 2711 (10001.)
00401071  |>push    dword ptr [ebp+8]           ; |hWnd
00401074  |>call    <GetDlgItemTextA>           ; \GetDlgItemTextA
00401079  |>cmp     eax, 5                      ;  Tamaño nombre >= 5
0040107C  |>jb      00401214
00401082  |>cmp     eax, 14                     ;  Tamaño nombre <= 0x14
00401085  |>ja      00401214
0040108B  |>mov     [404429], eax
00401090  |>push    96                          ; /Count = 96 (150.)
00401095  |>push    00404349                    ; |Buffer = dihux_ke.00404349
0040109A  |>push    2712                        ; |ControlID = 2712 (10002.)
0040109F  |>push    dword ptr [ebp+8]           ; |hWnd
004010A2  |>call    <GetDlgItemTextA>           ; \GetDlgItemTextA
004010A7  |>test    al, al
........
004010D8  |>xor     ecx, ecx                    ;  Case 0 of switch 004010B6
004010DA  |>/push    0
004010DC  |>|call    <__BigCreate@4>
004010E1  |>|mov     [ecx*4+404411], eax
004010E8  |>|inc     ecx
004010E9  |>|cmp     ecx, 6
004010EC  |>\jnz     short 004010DA
004010EE  |>push    dword ptr [404411]          ; /Arg3 = 00B60000
004010F4  |>push    10                          ; |16??
004010F6  |>push    0040401F                    ; |Arg1 = 0040401F ASCII "8ACFB4D27CBC8C2024A30C9417BBCA41AF3FC3BD9BDFF97F89"
004010FB  |>call    <__BigIn@12>                ; \dihux_ke.004013F3
00401100  |>push    dword ptr [404415]          ; /Arg3 = 00C70000
00401106  |>push    10                          ; |Arg2 = 00000010
00401108  |>push    00404019                    ; |Arg1 = 00404019 ASCII "10001"
0040110D  |>call    <__BigIn@12>                ; \dihux_ke.004013F3
00401112  |>push    dword ptr [404425]          ; /Arg3 = 00CB0000
00401118  |>push    10                          ; |Arg2 = 00000010
0040111A  |>push    00404349                    ; |Arg1 = 00404349 ASCII "123456789123456789"
0040111F  |>call    <__BigIn@12>                ; \dihux_ke.004013F3
00401124  |>push    00404330                    ; /String = "deurus"
00401129  |>call    <lstrlenA>                  ; \lstrlenA
0040112E  |>push    dword ptr [404419]
00401134  |>push    eax
00401135  |>push    00404330                    ;  ASCII "deurus"
0040113A  |>call    <__BigInB256@12>
0040113F  |>push    dword ptr [404421]          ;  c
00401145  |>push    dword ptr [404411]          ;  n = 8ACFB4D27CBC8C2024A30C9417BBCA41AF3FC3BD9BDFF97F89
0040114B  |>push    dword ptr [404415]          ;  e = 10001
00401151  |>push    dword ptr [404425]          ;  serial
00401157  |>call    <__BigPowMod@16>            ;  c = serial^e (mod n)
0040115C  |>mov     eax, 1337
00401161  |>push    0                           ; /Arg4 = 00000000
00401163  |>push    dword ptr [40441D]          ; |x
00401169  |>push    eax                         ; |0x1337
0040116A  |>push    dword ptr [404421]          ; |c
00401170  |>call    <__BigDiv32@16>             ; \x = c/0x1337
00401175  |>push    dword ptr [40441D]          ;  x
0040117B  |>push    dword ptr [404419]          ;  nombre
00401181  |>call    <__BigCompare@8>            ; ¿x = nombre?
00401186  |>jnz     short 0040119C
00401188  |>push    0                           ; /Style = MB_OK|MB_APPLMODAL
0040118A  |>push    00404014                    ; |Title = "iNFO"
0040118F  |>push    00404004                    ; |Text = "Serial is valid"
00401194  |>push    dword ptr [ebp+8]           ; |hOwner
00401197  |>call    <MessageBoxA>               ; \MessageBoxA
0040119C  |>xor     ecx, ecx
0040119E  |>/push    dword ptr [ecx*4+404411]
004011A5  |>|call    <__BigDestroy@4>
004011AA  |>|inc     ecx
004011AB  |>|cmp     ecx, 6
004011AE  |>\jnz     short 0040119E

Lo primero que observamos es que el código nos proporciona el exponente público (e) y el módulo (n).

e = 10001
n = 8ACFB4D27CBC8C2024A30C9417BBCA41AF3FC3BD9BDFF97F89

A continuación halla c = serial^d mod n. Finalmente Divide c entre 0x1337 y lo compara con el nombre.

Como hemos visto en la teoría de RSA, necesitamos hallar el exponente privado (d) para poder desencriptar, según la fórmula vista anteriormente.

Fórmula original: m=c^d mod n
Nuestra fórmula: Serial = x^d mod n. Siendo x = c * 0x1337

Calculando un serial válido

Existen varios ataques a RSA, nosotros vamos a usar el de factorización. Para ello vamos a usar la herramienta RSA Tool. Copiamos el módulo (n), el exponente público (e) y factorizamos (Factor N).

Hallados los primos p y q, hallamos d (Calc. D).

Una vez obtenido d solo nos queda obtener x, que recordemos es nombre * 0x1337.

Cuando decimos nombre nos referimos a los bytes del nombre en hexadecimal, para deurus serían 646575727573.

Ejemplo operacional

Nombre: deurus

x = 646575727573 * 0x1337 = 7891983BA4EC4B5
Serial = x^d mod n
Serial = 7891983BA4EC4B5^32593252229255151794D86C1A09C7AFCC2CCE42D440F55A2D mod 8ACFB4D27CBC8C2024A30C9417BBCA41AF3FC3BD9BDFF97F89
Serial = FD505CADDCC836FE32E34F5F202E34D11F385DEAD43D87FCD

Como la calculadora de Windows se queda un poco corta para trabajar con números tan grandes, vamos a usar la herramienta Big Integer Calculator. A continuación os dejo unas imágenes del proceso.

Keygen

En esta ocasión hemos elegido Java ya que permite trabajar con números grandes de forma sencilla, os dejo el código más importante.

JButton btnNewButton = new JButton("Generar");
btnNewButton.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent arg0) {
BigInteger serial = new BigInteger("0");
BigInteger n = new BigInteger("871332984042175151665553882265818310920539633758381377421193");//módulo
BigInteger d = new BigInteger("316042180198461106401603389463895139535543421270452849695277");//exponente privado
BigInteger x = new BigInteger("4919");//0x1337
String nombre = t1.getText();
BigInteger nombre2 = new BigInteger(nombre.getBytes());
nombre2 = nombre2.multiply(x);
serial = nombre2.modPow(d, n);
t2.setText(serial.toString(16).toUpperCase());
}
});

Blog de Cracking y Hacking ético

enjoy!

Etiqueta: big integer calculator

Solución al KeygenMe1 (RSA200) de Dihux