lunes, 27 de abril de 2015

Evasión del esquema criptográfico de protección en una aplicación real

Intro

Estudiar un keygen es una buena forma de aprender sobre protecciones de software reales.  Tienen la ventaja de que uno puede estudiarlos sin siquiera instalar el software para el que fueron desarrollados.

Lo hago de vez en cuando y a veces aprendo algunas cosas interesantes.  Ademas casi siempre encuentro detalles que me hacen reir.  Esta vez no será la excepción.

Pero además, esta vez veremos como un pequeño error de diseño en la implementación podría anular todo el esquema criptografico de la protección…

El keygen

Ya no recuerdo bien de donde saqué este keygen.  A veces los encuentro en las maquinas de la universidad, o veces los descargo yo mismo (ya sea para estudiarlos o solo para oir la musiquita que les ponen).

Estoy seguro de que no lo descargué porque estuviera interesado en el software para el que se hizo el keygen.  Lo se porque tengo instalada una herramienta libre que hace lo mismo que ese software.  Lo que si recuerdo es que lo guarde por algo que leí en el [About]… y tambien por la musiquita…

Pero me estoy adelantando. Este es el keygen…
Este es el formulario principal.  La imagen fue editada para eliminar el nombre del programa.
Hay cosas graciosas en este keygen (como en todos!) por ejemplo el autor usa la constante mágica 0x7FFF0000 para inicializar algunas cosas.  ese 7FFF hace referencia al autor (SeVeN) y a su grupo (Fighting For Fun).  Esto a veces lo hacen solo por vanidad, pero a veces es para llevar cuenta de quienes usan su Keygen para liberar algún numero de serie (o en este caso un Keyfile)…  Creo que este es el caso, pues el keygen incluye una lista negra y no permite generar el keyfile para algunos usuarios específicos (por ejemplo, 'cRaZy-cOoL' o 'Floodeur-666')…

Pero no es de eso de lo que quiero hablar.  Recuerden que les dije que había algo en el [About] que me hizo guardar este keygen para estudiarlo:

El [About] nos promete que la protección será ECC.  Nuevamente, esta editado para eliminar el nombre del programa
Asumimos que con ECC se refieren a Criptografía de Curva Elíptica… Me interesa!

Como exploración inicial, decido generar un keyfile con los valores por defecto para observar la estructura.  Aunque no he dicho (ni dire!) para que programa es este keygen, lo he editado por si acaso:

XXX registration data
SeVeN
Unlimited Company License
UID=????????????????????
??????????????????????????????????????????????????????
??????????????????????????????????????????????????????
??????????????????????????????????????????????????????
??????????????????????????????????????????????????????
??????????????????????????????????????????????????????
??????????????????????????????????????????????????????
??????????????????????????????????????????????????????
Esta es la estructura del keyfile.  Cada '?' representa un dígito en base 16.  El "XXX" lo agregue para ocultar el nombre del programa.

Tenemos un header, el usuario y el tipo de licencia (que son los parametros de este keygen) un UID de 20 bytes que no sabemos de donde salio.  Y siete lineas de números que asumo serán algún tipo de firma criptográfica de la información anterior… Entonces: [header]+[name]+[license]+[uid]+[signature]

Tantos números despertaron mi curiosidad. Vamos a ver bien de que se trata...

Desempacado del keygen

RDG Packer Detector v0.7.4 detecta que el keygen fue empaquetado con el compresor de ejecutables PECompat:


Este es un compresor bastante sencillo.  Si alguien no esta familiarizado, hay un tutorial de desempacado hecho por la gente de ARTeam.  Lo principal a tener en cuenta es que el punto de entrada original se mantiene luego del desempacado.

Aquí esta mi versión del proceso usando SnD v2.3 y Scylla v0.9.7c:

Al cargar el keygen en SnD 2.3 entramos en 0x004094CE

Si pulsamos F8 (Step Over) seis veces saltaremos al modulo GDI32:

Estamos en GDI32

Aquí podemos pulsar Alt+F9 (Execute till user code) lo que ejecutara la rutina de desempacado y nos regresara al modulo principal muy cerca del punto de entrada original.

De regreso en el modulo principal

Aquí podemos pulsar F8 otras trece veces para tomar ese JMP EAX que se ve en la ultima linea (está en la dirección 0x004579A6).  Esto nos llevará de vuelta al OEP:

Y ya estamos de regreso en 0x004094CE
Si en este momento cargamos Scylla y hacemos el attach al proceso, descubriremos que al pulsar [IAT Autosearch] y [Get Imports] aparece un Thunk invalido.

Thunk invalido

Se trata de un falso positivo. Podemos seleccionarlo con el botón derecho y elegir "Delete tree node" (Siempre prueben esto primero!).  Luego de esto ya podemos pulsar [Dump] para hacer el volcado y luego [Fix Dump] para corregir el IAT en el archivo que hemos volcado.

Análisis de la protección

Luego de probar que el volcado recién reparado era funcional (siempre recuerden verificar esto!) lo cargue en IDA Free v5.0.  Como la IAT fue reparada, al momento de cargar el keygen le digo a IDA que no genere el segmento de imports:

Desmarcamos ese "Make imports segment"

Y como el keygen genera un keyfile, iniciare mi análisis buscando referencias al api CreateFileA:

Iniciamos desde el CreateFileA


La primera referencia nos lleva al lugar correcto:

En la zona!

Veamos este bloque de código:

.text:00401B52 loc_401B52:                             ; CODE XREF: sub_40185C+2FB j
.text:00401B52                 mov     dl, [eax]
.text:00401B54                 inc     eax
.text:00401B55                 test    dl, dl
.text:00401B57                 jnz     short loc_401B52
.text:00401B59                 sub     eax, ecx
.text:00401B5B                 mov     esi, eax
.text:00401B5D                 push    esi
.text:00401B5E                 lea     eax, [ebp+var_AA4]
.text:00401B64                 push    eax
.text:00401B65                 push    edi
.text:00401B66                 lea     eax, [ebp+var_10A4]
.text:00401B6C                 push    eax
.text:00401B6D                 push    ebx
.text:00401B6E                 lea     eax, [ebp+var_18A4]
.text:00401B74                 push    eax
.text:00401B75                 push    [ebp+var_8]
.text:00401B78                 lea     eax, [ebp+var_6A4]
.text:00401B7E                 push    eax
.text:00401B7F                 push    [ebp+var_10]
.text:00401B82                 or      eax, 0FFFFFFFFh
.text:00401B85                 push    [ebp+arg_0]
.text:00401B88                 push    [ebp+var_14]
.text:00401B8B                 push    [ebp+arg_4]
.text:00401B8E                 call    sub_4014EC
.text:00401B93                 pop     ecx
.text:00401B94                 pop     ecx
.text:00401B95                 call    sub_4014EC
.text:00401B9A                 pop     ecx
.text:00401B9B                 pop     ecx
.text:00401B9C                 call    sub_4014EC
.text:00401BA1                 pop     ecx
.text:00401BA2                 pop     ecx
.text:00401BA3                 call    sub_4014EC
.text:00401BA8                 pop     ecx
.text:00401BA9                 pop     ecx
.text:00401BAA                 call    sub_4014EC
.text:00401BAF                 pop     ecx
.text:00401BB0                 pop     ecx
.text:00401BB1                 call    sub_4014EC
.text:00401BB6                 push    eax
.text:00401BB7                 lea     eax, [ebp+var_AA4]
.text:00401BBD                 push    eax
.text:00401BBE                 lea     eax, [ebp+var_10A4]
.text:00401BC4                 push    eax
.text:00401BC5                 lea     eax, [ebp+var_18A4]
.text:00401BCB                 push    eax
.text:00401BCC                 lea     eax, [ebp+var_6A4]
.text:00401BD2                 push    eax
.text:00401BD3                 push    esi
.text:00401BD4                 push    edi
.text:00401BD5                 push    ebx
.text:00401BD6                 push    [ebp+var_8]
.text:00401BD9                 lea     eax, [ebp+var_2A4]
.text:00401BDF                 push    offset a02_2d03_3d03_3 ; "%02.2d%03.3d%03.3d%02.2d%s%s%s%s%010u"
.text:00401BE4                 push    eax
.text:00401BE5                 call    sub_408CEA
.text:00401BEA                 add     esp, 34h
.text:00401BED                 xor     eax, eax
.text:00401BEF                 push    eax             ; hTemplateFile
.text:00401BF0                 push    80h             ; dwFlagsAndAttributes
.text:00401BF5                 push    2               ; dwCreationDisposition
.text:00401BF7                 push    eax             ; lpSecurityAttributes
.text:00401BF8                 push    eax             ; dwShareMode
.text:00401BF9                 push    0C0000000h      ; dwDesiredAccess
.text:00401BFE                 push    [ebp+lpFileName] ; lpFileName
.text:00401C01                 call    CreateFileA
.text:00401C07                 mov     edi, eax
.text:00401C09                 cmp     edi, 0FFFFFFFFh
.text:00401C0C                 jnz     short loc_401C15
.text:00401C0E

Si empezamos desde abajo hacia arriba vemos que antes de hacer la llamada a CreateFileA se esta llamando a una función sub_408CEA() que recibe un string de formato así que seguramente es algo cómo un sprintf()
int sprintf ( char * str, const char * format, ... );
Entonces, el primer push (resaltado en verde) es del buffer de destino *str = ebp+var_2A4, y usando el string de formatos podemos identificar el tipado de los otros parámetros del sprintf(): ebp+var_8, ebx, edi, esi (los push en cyan) son los cuatro %d del string de formato, los cuatro push en naranja corresponden a los cuatro %s y el push eax (en verde) corresponde al %u.

(Por cierto, si seguimos subiendo veremos que otro sprintf escribe el encabezado, el nombre, el tipo de licencia, y el UID, pero no mostrare esa sección de codigo, porque no la necesitaremos)

Ese ultimo push eax (el del %u) parece ser la salida de la función sub_4014EC() que se ha llamado varias veces.  Veamos esa función:

.text:004014EC ; ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦ S U B R O U T I N E ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦
.text:004014EC
.text:004014EC ; Attributes: bp-based frame
.text:004014EC
.text:004014EC sub_4014EC      proc near               ; CODE XREF: sub_40185C+24A p
.text:004014EC                                         ; sub_40185C+26F p ...
.text:004014EC
.text:004014EC arg_0           = dword ptr  8
.text:004014EC arg_4           = dword ptr  0Ch
.text:004014EC
.text:004014EC                 push    ebp
.text:004014ED                 mov     ebp, esp
.text:004014EF                 xor     ecx, ecx
.text:004014F1                 cmp     [ebp+arg_4], ecx
.text:004014F4                 jbe     short loc_401514
.text:004014F6                 push    esi
.text:004014F7
.text:004014F7 loc_4014F7:                             ; CODE XREF: sub_4014EC+25 j
.text:004014F7                 mov     edx, [ebp+arg_0]
.text:004014FA                 movzx   edx, byte ptr [ecx+edx]
.text:004014FE                 movzx   esi, al
.text:00401501                 xor     edx, esi
.text:00401503                 shr     eax, 8
.text:00401506                 xor     eax, dword_428880[edx*4]
.text:0040150D                 inc     ecx
.text:0040150E                 cmp     ecx, [ebp+arg_4]
.text:00401511                 jb      short loc_4014F7
.text:00401513                 pop     esi
.text:00401514
.text:00401514 loc_401514:                             ; CODE XREF: sub_4014EC+8 j
.text:00401514                 pop     ebp
.text:00401515                 retn
.text:00401515 sub_4014EC      endp
.text:00401515


Esa secuencia de instrucciones parece corresponder a alguna de las formas de CRC (vease por ejemplo esta implementación).  Para verificar revisamos si dword_428880 es una tabla de CRC.

Estas son las referencias cruzadas a este dword:

.text:00428880 dword_428880    dd 0                    ; DATA XREF: sub_4014EC+1A r

.text:00428880                                         ; sub_40185C+222 w


La primera es la que ya conocemos, asi que veremos la segunda:

.text:00401A6C loc_401A6C:                             ; CODE XREF: sub_40185C+220 j
.text:00401A6C                 test    al, 1
.text:00401A6E                 jz      short loc_401A79
.text:00401A70                 shr     eax, 1
.text:00401A72                 xor     eax, 0EDB88320h
.text:00401A77                 jmp     short loc_401A7B
.text:00401A79 ; ---------------------------------------------------------------------------
.text:00401A79
.text:00401A79 loc_401A79:                             ; CODE XREF: sub_40185C+212 j
.text:00401A79                 shr     eax, 1
.text:00401A7B
.text:00401A7B loc_401A7B:                             ; CODE XREF: sub_40185C+21B j
.text:00401A7B                 dec     edx
.text:00401A7C                 jnz     short loc_401A6C
.text:00401A7E                 mov     dword_428880[ecx*4], eax


Vemos que en esta zona se esta llenando la tabla y un poco mas arriba vemos la constante 0xEDB88320 que nos confirma que estamos haciendo un CRC (Siempre hagan búsquedas de las constantes sospechosas en internet!).

Estamos en la zona de generación de la tabla CRC.  Algo como este trozo que encontré en por acá:

   if (table[1] == 0) {
      for (byte = 0; byte <= 255; byte++) {
         crc = byte;
         for (j = 7; j >= 0; j--) {    // Do eight times.
            mask = -(crc & 1);
            crc = (crc >> 1) ^ (0xEDB88320 & mask);
         }
         table[byte] = crc;
      }
   }

Ahora que identificamos esas dos funciones y algunas variables, veamos de nuevo el mismo bloque de código inicial luego de renombrar algunas cosas:


.text:00401B52 loc_401B52:                             ; CODE XREF: sub_40185C+2FB j
.text:00401B52                 mov     dl, [eax]
.text:00401B54                 inc     eax
.text:00401B55                 test    dl, dl
.text:00401B57                 jnz     short loc_401B52
.text:00401B59                 sub     eax, ecx
.text:00401B5B                 mov     esi, eax
.text:00401B5D                 push    esi
.text:00401B5E                 lea     eax, [ebp+str4]
.text:00401B64                 push    eax
.text:00401B65                 push    edi
.text:00401B66                 lea     eax, [ebp+str3]
.text:00401B6C                 push    eax
.text:00401B6D                 push    ebx
.text:00401B6E                 lea     eax, [ebp+str2]
.text:00401B74                 push    eax
.text:00401B75                 push    [ebp+var_8]
.text:00401B78                 lea     eax, [ebp+str1]
.text:00401B7E                 push    eax
.text:00401B7F                 push    [ebp+var_10]
.text:00401B82                 or      eax, 0FFFFFFFFh
.text:00401B85                 push    [ebp+arg_0]
.text:00401B88                 push    [ebp+var_14]
.text:00401B8B                 push    [ebp+arg_4]
.text:00401B8E                 call    crc32
.text:00401B93                 pop     ecx
.text:00401B94                 pop     ecx
.text:00401B95                 call    crc32
.text:00401B9A                 pop     ecx
.text:00401B9B                 pop     ecx
.text:00401B9C                 call    crc32
.text:00401BA1                 pop     ecx
.text:00401BA2                 pop     ecx
.text:00401BA3                 call    crc32
.text:00401BA8                 pop     ecx
.text:00401BA9                 pop     ecx
.text:00401BAA                 call    crc32
.text:00401BAF                 pop     ecx
.text:00401BB0                 pop     ecx
.text:00401BB1                 call    crc32
.text:00401BB6                 push    eax
.text:00401BB7                 lea     eax, [ebp+str4]
.text:00401BBD                 push    eax
.text:00401BBE                 lea     eax, [ebp+str3]
.text:00401BC4                 push    eax
.text:00401BC5                 lea     eax, [ebp+str2]
.text:00401BCB                 push    eax
.text:00401BCC                 lea     eax, [ebp+str1]
.text:00401BD2                 push    eax
.text:00401BD3                 push    esi
.text:00401BD4                 push    edi
.text:00401BD5                 push    ebx
.text:00401BD6                 push    [ebp+var_8]
.text:00401BD9                 lea     eax, [ebp+dst]
.text:00401BDF                 push    offset format   ; "%02.2d%03.3d%03.3d%02.2d%s%s%s%s%010u"
.text:00401BE4                 push    eax
.text:00401BE5                 call    sprintf

Renombre el string destino como dst, y los cuatro del %s como str1-str4.  El resaltado en verde parece ser la inicialización del CRC a 0xfffffff y desde allí se va calculando para varias cosas.

Como ya sabíamos que crc32() retornaba en eax (recuerden que se hizo un push para el %u del sprintf), parece ser que en eax siempre va quedando el valor actualizado del crc después de cada llamada a la funcion.

También parece que recibe dos parámetros por la pila.  Uno tendrá que ser el mensaje al que se le esta calculando el crc, el otro aun no sabemos (algunos ya se lo imaginaran...).  He marcado los pares de parámetros en amarillo (mensajes) y cyan (parametro desconocido).  Entonces, como ya hemos identificado los mensajes, y como estamos llevando la cuenta del crc acumulado en cada llamada, vemos que lo que se hace es algo como:
crc32(arg4 + arg0 + str1 + str2 + str3 + str 4)
donde el '+' denota la concatenación de strings.

Finalmente, notemos que los parámetros desconocidos (en cyan) son los mismos cuatro que se formatean con %d para el sprintf (los resalte en naranja)

Esto se ve bien!

Veamos de nuevo la función crc32() para confirmar que es lo que hace con ese parámetro desconocido;

.text:004014EC ; ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦ S U B R O U T I N E ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦
.text:004014EC
.text:004014EC ; Attributes: bp-based frame
.text:004014EC
.text:004014EC crc32           proc near               ; CODE XREF: sub_40185C+24A p
.text:004014EC                                         ; sub_40185C+26F p ...
.text:004014EC
.text:004014EC msg             = dword ptr  8
.text:004014EC arg_4           = dword ptr  0Ch
.text:004014EC
.text:004014EC                 push    ebp
.text:004014ED                 mov     ebp, esp
.text:004014EF                 xor     ecx, ecx
.text:004014F1                 cmp     [ebp+arg_4], ecx
.text:004014F4                 jbe     short loc_401514
.text:004014F6                 push    esi
.text:004014F7
.text:004014F7 loc_4014F7:                             ; CODE XREF: crc32+25 j
.text:004014F7                 mov     edx, [ebp+msg]
.text:004014FA                 movzx   edx, byte ptr [ecx+edx]
.text:004014FE                 movzx   esi, al
.text:00401501                 xor     edx, esi
.text:00401503                 shr     eax, 8
.text:00401506                 xor     eax, crc32_table[edx*4]
.text:0040150D                 inc     ecx
.text:0040150E                 cmp     ecx, [ebp+arg_4]
.text:00401511                 jb      short loc_4014F7
.text:00401513                 pop     esi
.text:00401514
.text:00401514 loc_401514:                             ; CODE XREF: crc32+8 j
.text:00401514                 pop     ebp
.text:00401515                 retn
.text:00401515 crc32           endp
.text:00401515

Al principio ecx se inicializa a 0, y se compara con el parámetro que nos interesa si el parámetro es mayor o igual a 0 vamos a la zona magenta para terminar.  Si no es asi vamos a la zona verde, y vamos calculando el crc byte por byte.  En cada iteracion, ecx aumenta en 1 y lo comparamos nuevamente para ver si volvemos a la zona verde (para procesar otro carácter) o vamos a la zona magenta (para terminar).  Es bastante obvio que este parámetro es el tamaño del mensaje.

Si resumimos lo que ya sabemos, tendríamos algo como esto en Python:

crc = crc32(arg4 + arg0 + str1 + str2 + str3 + str4)
sig = "%02d%03d%03d%02d%s%s%s%s%010u" % (len(str1), len(str2), len(str3), len(str4), str1, str2, str3, str4, crc)

Por cierto, ya que es trivial probarlo en un debugger puedo confirmarles que arg0 es el nombre para el que se generara el keyfile y arg4 es el tipo de licencia.  Los valores por defecto en el keygen son 'SeVeN' y 'Unlimited Company License' respectivamente.

Para aclarar las cosas un poco, así va quedando la estructura del keyfile
XXX registration data
[name]
[license]
UID=????????????????????
[len(str1)][len(str2)][len(str3)][len(str4)][str1][str2][str3][str4][crc32(license+name+str1+str2+str3+str4)]
Aun no tenemos idea de que es el UID ni de como se calculan str1, str2, str3 o str4.

Y para no alargar mucho la cosa les puedo confirmar que los 20 bytes del UID son irrelevantes.  La linea empezando con "UID=" tiene que existir pero el valor puede ser cualquier cosa o estar vacío (siempre prueben un poco de fuzzing!)

Para evitar usos indebidos no les mostrare en el depurador los strings que se generan para los valores por defecto.  Pero si les puedo decir las longitudes de cada uno: 64, 122, 122 y 50.

Además, usando el truco de las constantes se puede confirmar que la generación de los strings involucra el uso de algunos valores aleatorios y el cálculo de algunos SHA-1.  Si le creemos al autor del keygen, algo de ECC tendremos también.  Todo apunta a una forma de ECDSA.

Pero en este punto tuve la idea que me motivo a escribir este post.  Si llega a funcionar se evade completamente el ECC y todo se reduce al CRC...

Se lo imaginan?

La idea es esta: como el keyfile incluye las longitudes de los strings, que pasará si declaro esas longitudes como 0?

El keyfile pasaria a ser algo como:
XXX registration data
[name]
[license]
UID=[random()]
[00][000][000][00][crc32(license+name)]
Recuerden que cada una de las longitudes lleva un padding para ajustar dos o tres caracteres según el string de formato.

Será posible?

Para implementarlo hay algo mas a tener en cuenta: el CRC32 que se calcula aqui no es el tipíco CRC32 que aparece por ejemplo en los archivos ZIP.  Es parecido pero no lo mismo.  Nuevamente la constante 0xEDB88320 nos indica que estamos usando una representación del polinomio con reflexión.  Pueden leerse este documento que es una maravilla.  Este subtitulo lo dice todo: "Everything you wanted to know about CRC algorithms, but were afraid to ask for fear that errors in your understanding might be detected". LOL!

Resumiendo, podemos usar la implementación de crc32 en zlib, pero debemos usar el complemento de este valor y ademas truncarlo a 8 bytes:

Este es el código en Python:

import zlib
name = 'SeVeN'
license = 'Unlimited Company License'
crc = ~zlib.crc32(license + name) & 0xffffffff
print "XXX registration data\n%s\n%s\nUID=\n%s%u" % (name, license, '0' * 10, crc)

Y esta es la salida:

XXX registration data
SeVeN
Unlimited Company License
UID=
00000000001090226602

Se redujo la complejidad al eliminar 20 bytes del uid y 358 bytes de la firma.  Ademas, de los 20 bytes que quedan en la firma 10 serán siempre '0', asi que pasamos de 398 bytes desconocidos a solo 10 de un CRC mas 10 de relleno estático…

Y aunque no lo crean, esto es suficiente para pasar parte de las validaciones en el programa.  Posiblemente fue una decisión de diseño: verificar el crc es una tarea de bajo costo, pero verificar las firmas completas tiene un costo alto.

Consideraciones finales

Esto me hace pensar… será que el resto de la criptografía implementada en el programa es vulnerable a cosas como esta?

Uhmm… Por curiosidad busco en Internet cifras de descargas del programa... solo en CNET reportan mas de 22 millones.  Nada mal…

Para terminar:

  1. Aunque se analizó una protección real no se reveló el nombre de la aplicación y no se analizó directamente su código.
  2. El análisis presentado no hace mas vulnerable el esquema de protección de la aplicación pues al momento de hacer el análisis ya existía por lo menos un generador de claves público (que fue justamente lo que se analizó, y que además no se está compartiendo en esta página).
  3. Mi copia (legal!) de MalwareBytes Anti-Malware Home (Premium) v2.1.6.1022 detecta este keygen como una amenaza! Por lo tanto, es apenas lógico que haya realizado el análisis de un Programa Potencialmente Peligroso… no?
  4. Mi propio generador NO funcionará para evadir la protección de la aplicación (quien pretenda usarlo deberá cambiar ese 'XXX' por el valor correcto). Lo repito: NO estoy compartiendo un generador de claves para la aplicación
  5. Esta parece ser una aplicación bastante popular. Pero existe un buen numero de alternativas libres y gratuitas.  Usen software libre y eviten problemas!
Es cierto. LOL!
Ahh… y desde luego:

XXX registration data
Ruben Molina
Why bother to reverse ECC, when CRC is enough?
UID=
00000000001137829505

Actualización (8 horas después)

Algunos me escribieron para decirme que identificaron la aplicación.  Algunos para decirme que comparten mi interés por la musica de los keygens :) Para estos últimos, puedo recomendar http://keygenjukebox.com/http://www.keygenmusic.net/

Además, me han escrito para avisarme que esto no siempre funciona.  En particular, los keyfiles generados no rehabilitan el programa una vez que ha expirado el trial (El keygen de FFF si lo hace).  Es fácil confirmar que tienen razón.  Esta aplicación tiene dos interfaces: GUI y CLI.  En el GUI observe que la aplicación muestra un "only XX days to buy a license" en el titulo de la ventana y un "40 days trial copy" en el cuadro de dialogo "About".  En el CLI aparece un "Trial version".  No se si hay algunos otros puntos para verificar.

Al usar estos keyfiles el CLI cambia a "Registered to [name]" y el "only XX days to buy a license" desaparece del título del GUI.  Sin embargo, el "40 days trial copy" sigue apareciendo en el dialogo "About".  Es válido concluir que el keyfile es procesado con diferentes niveles de profundidad por la aplicación y que el problema aqui descrito no aplica a todos los niveles.

Más noticias cuando termine de analizar el keygen de FFF.

Actualización (8 días después)

He completado el análisis del keygen de FFF.  Una descripción detallada requeriría un post completo (que no estoy seguro de que aporte algo), pero la descripción general es la siguiente: 
  • str4 es simplemente un relleno y puede dejarse vacío o llenarse de forma aleatoria
  • str1 es una transformación del hash sha1(str4)
  • str2 es una firma criptografica de la concatenación: name + str1
  • str3 es una firma criptografica de license
  • Para las firmas se usa el esquema Nyberg-Rueppel y la curva elíptica por defecto (GF_M == 255) del software de dominio público pegwit. Es posible identificar el uso de pegwit por la presencia del string: "ERROR: not enough room for multiplication\n"
  • Una vez identificado pegwit, es trivial identificar sus funciones, y los parámetros de la curva usada. También es fácil confirmar que la clave privada usada es: 0x59FE…D65E (nuevamente, la recorto por si acaso)
Es válido preguntarse como logró SeVeN conseguir la clave privada.  
  • Fue un increíble golpe de suerte lo que le permitió adivinarla? No. Claro que no.
  • Acaso fue un leak/hack (como en el caso de las claves de Armadillo)? Nop.
  • Fue entonces un esfuerzo de computación distribuida (como en el caso de los retos RSA)? No, tampoco.
  • Ahh… fue entonces un error de implementación (como el de la clave del PlayStation 3)? Desde luego.  Algo asi tuvo que ser :)
Volveré a citar la frase de +ORC que ya use en un post anterior:
"the only way to hack and crack correctly is to be more a software historian than a programmer"
Si estudiamos un poco la historia de SeVeN y su grupo FFF podremos confirmar que poco después del keygen que estamos estudiando escribió otro en el que también se usa ECC (esta vez para The Bat!) y que por esa misma época  jB! (otro miembro de FFF) escribió uno más (nuevamente recuperando la clave privada) para CloneCD.

El caso de CloneCD es especialmente relevante por dos razones:
  1. Usa exactamente la misma curva de pegwit que se usa en la aplicación que nos interesa (y² + xy = x³ + 161)
  2. Esta completamente documentado (aunque sólo en francés) :)
Para los que no leen francés, dejaré un micro-resumen de lo que interesa:

Empecemos por pegar aquí el proceso de firmado de mensajes en ECDSA (tomado de la wikipedia)

  1. Seleccione un número k de forma aleatoria.
  2. Calcule kP = (x1,y1).
  3. Calcule r = x1 mod n. Si r = 0 regresa al primer paso. (En este paso x1 es tratado como un entero).
  4. Calcule (k-1) mod n.
  5. Calcule s = k-1(H(m) + dr) mod n. Si s = 0 regrese al primer paso. (H(m) es el hash del mensaje a firmar, calculado con el algoritmo SHA-1).
  6. La firma del mensaje m son los números r y s.

El problema siempre está en no seguir correctamente los pasos. Específicamente, en este caso se falla desde el paso 1: Cuando k no es aleatorio sino que es constante, o se reusa, o incluso si se aleja ligeramente de la aleatoriedad (por ejemplo, si múltiples k comparten los primeros 4 bits!) entonces es posible recuperar la clave privada.

El documento de jB! tenemos la solución para el caso de dos mensajes que se firman con la misma k y que se reduce a calcular: d = (s2 – s1)(r1r2)–1 mod n

En definitiva, exactamente lo que paso con la PlayStation 3 :P

Así pues. FFF tenía experiencia demostrable en la explotación de fallos de implementación.  Aún así, no es exactamente el caso del software que nos interesa. A decir verdad el texto menciona este software y aclara que usa pegwit de forma correcta por lo que "no ha sido posible escribir un keygen después de varios años" (y tomaria varios años mas).

La documentación de pegwit menciona: "For generating a multiplier for a digital signature, the seed is the SHA1 hash of the secret key, concatenated with the double-barreled SHA1 hash of the file being signed.".Generar k en función del mensaje y la clave privada se considera una buena práctica pues elimina la dependencia de un número aleatorio criptograficamente seguro (como curiosidad histórica, esta fue una idea original de pegwit).

Esto podría ser un problema si dos licencias diferentes se firmaran con el mismo nombre (piensen en una empresa que pasa de 10 a 100 licencias, por ejemplo).  Esto generaría el mismo estado inicial para la semilla del PRNG y desde allí eventualmente podríamos firmar una licencia con un k previamente usado.  Sin embargo esto no es posible ya que el nombre se concatena con el str1 que a su vez depende de valores aleatorios.  Esto ya no pasa con la firma del texto de licencia pero al llegar a este punto el contexto ya ha sido aleatorizado.

Parece que se necesitan muchas condiciones especiales el ataque sea viable? Así es.  Debemos considerar que tomo casi 10 años para que fuese posible este generador de claves.  Cualquiera que haya sido la situación que fue explotada tuvo que depender de circunstancias especiales.

En cualquier caso, el proceso de obtención de la clave privada nunca ha sido descrito ni reproducido públicamente (aunque el grupo CORE tuvo también un keygen para esta aplicación, reconocieron que usaba la clave privada calculada por SeVeN).

Parece que aun pasará algún tiempo antes de que este misterio se aclare y pueda volver a dormir tranquilo…

Desenlace (otros 8 días después)

Finalmente he encontrado una explicación a este misterio:  Tal y como lo decía el paper de jB! la aplicación que nos interesa utiliza correctamente pegwit, y esto me llevo a pensar que tal vez el error estaba directamente en pegwit.

Al buscar ataques a pegwit encontré este mensaje, donde mencionan que la elección del campo compuesto GF(2^255) era considerada riesgosa debido al "ataque de Smart", y que la nueva versión de pegwit usaría GF(2^233), un campo resistente al ataque de Smart ya que 233 es primo.

Buscando mas información sobre el ataque encontré que podría referirse a un ataque de Gaudry, Hess y Smart (preprint) y que, en principio, permite trasladar el problema del logaritmo discreto desde una curva elíptica hacia el jacobiano de una curva hiperelíptica, donde puede (o no) ser mas fácil hallar la respuesta.  En particular, el trabajo debilita las curvas sobre campos binarios extendidos.

Mientras leía sobre el ataque encontré también el trabajo de Menezes y Qu (preprint) que demuestra que los campos binarios donde la potencia es un número primo no son vulnerables al ataque GHS.  Lo que soportaba la elección del campo GF(2^233) y confirmaba que el "ataque de Smart" se refería efectivamente al ataque GHS.

Finalmente, el trabajo de Maurer, Menezes y Teske (preprint) analiza un rango de campos buscando cuales son vulnerables al ataque GHS.  Este rango incluye el campo GF(2^255) usado en nuestra aplicación, y los valores en el Apéndice A, muestran que número de iteraciones esperadas en el algoritmo de Enge-Gaudry (2^49) es mucho menor que el número de operaciones de curva elíptica esperadas en el método de Pollard (2^127) por lo que el campo se considera debilitado.

Si el ataque se conocía desde el año 2000, me surgen dos preguntas:

  1. porque se utilizo un campo vulnerable en la aplicación? (esta aplicación fue una de las primeras en usar ECC en su esquema de protección, es lógico que hayan investigado antes de hacerlo)
  2. porque tomo tanto tiempo (hasta el 2006) en aparecer el keygen de FFF? (recuerden que ya hemos probado que tanto FFF como SeVeN tenían suficiente experiencia como para estar familiarizados con los ataques relevantes).

Resolver la primera pregunta fue fácil: vía correo electrónico, el desarrollador principal de la aplicación me confirmó que el esquema de protección se implementó en 1999, cuando aun no se había reportado el ataque GHS.

La segunda pregunta fue un poco mas compleja, pero creo que también la resolví: dentro de los valores en el Apéndice de Maurer, Menezes y Teske, el campo "F" marca el tamaño base de los factores y para el campo que nos interesa F = 32.  Pues bien, el trabajo también incluye un criterio de factibilidad técnica para el ataque: si 2^F < 10^7, el ataque se considera realizable.  Para nuestro caso falla este criterio.  Sin embargo, el límite 10^7 es tecnológico y se hace mas grande conforme pasa el tiempo.  Si aplicamos la ley de Moore, el momento en el que 2^32 sería alcanzable no se encontraba muy lejos: unos diez años si se hace un redondeo grueso…  Si aplicamos la ley de Moore considerando un período de duplicación de 18 meses en lugar de 24 meses (como le gusta hacer a la gente de Intel) entonces ese limite sería alcanzable mucho antes y las fechas se ajustarían lo suficiente con las de la aparición del keygen.

Y eso ya me deja dormir tranquilo :)

Por cierto, si alguien quiere hacer la prueba, existe una implementación del ataque para Magma, sin embargo, verificar completamente la recuperación de la clave privada requeriría reversar el código de la aplicación para extraer la clave pública y esto no lo recomendaremos aquí.

miércoles, 22 de abril de 2015

Prime Obsession

Podríamos decir que este es un snippet demostrando como parsear y aplicar filtros a una tabla HTML remota, pero la verdad es que solo quería probar como insertar código en Blogger desde GitHub

Por completitud, aquí esta la salida del script:
[['1165012003' 'Wolverine 3']
 ['0793965019' 'Wolverine 61']
 ['0702818009' 'Wolverine 65']
 ['0616089007' 'Wolverine Special 102.5']
 ['0147650011' 'Wolverine 136']
 ['0192004009' 'Wolverine 188']]