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.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. |
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 |
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. |
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 |
 |
| 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. |
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:
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:
Y esta es la salida:
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:
- Aunque se analizó una protección real no se reveló el nombre de la aplicación y no se analizó directamente su código.
- 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).
- 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?
- 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
- 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/ o 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:
- Usa exactamente la misma curva de pegwit que se usa en la aplicación que nos interesa (y² + xy = x³ + 161)
- 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)
- Seleccione un número k de forma aleatoria.
- Calcule kP = (x1,y1).
- Calcule r = x1 mod n. Si r = 0 regresa al primer paso. (En este paso x1 es tratado como un entero).
- Calcule (k-1) mod n.
- 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).
- 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)(r1 – r2)–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…
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:
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í.
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:
- 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)
- 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í.
Comentarios
Publicar un comentario