Criptografía aplicada. Cómo restauramos bitcoins por 300 mil dólares

Compartiré contigo una historia. Hace unos veinte años, recibí un título en física, pero me dediqué a ingeniería inversa y criptoanálisis. Nuestra empresa AccessData trabajó a fines de los 90 y principios de los 2000. Luego, el gobierno de los Estados Unidos levantó gradualmente las restricciones a la exportación de criptografía, sin embargo, la protección con contraseña en la mayoría de los programas aún era bastante inútil. Tomamos programas de oficina, realicé ingeniería inversa y descubrí el algoritmo de cifrado, y luego rompí la protección criptográfica.

Fue un flujo interminable de acertijos matemáticos interesantes, pero no particularmente difíciles. Durante todo el tiempo escribí alrededor de cuarenta crackers de contraseñas. Los vendimos a usuarios domésticos, administradores de sistemas y agencias policiales locales y federales. Tuve que ir varias veces al centro federal de capacitación de las fuerzas del orden público en Glinko para explicar a los muchachos del Servicio Secreto, el FBI y la ATF los conceptos básicos de la criptografía y cómo usar nuestros productos.

Recuerdo especialmente dos proyectos. El primero fue Microsoft Word 97. Antes de que apareciera, los archivos se encriptaron usando bytes XOR de texto claro y una cadena de 16 bytes que salió de la contraseña. Los bytes más comunes en un archivo de Word generalmente eran 0x00, 0xFF o 0x20 (espacio), por lo que simplemente elegimos el carácter más común en cada columna y verificamos de 3 a ¹⁶ opciones. La recuperación de la clave usualmente ocurría instantáneamente, pero para que la gente no pensara que habían malgastado dinero, insertamos una pequeña animación similar a la escena del hacker de Hollywood con muchos caracteres aleatorios, de los cuales emerge gradualmente la contraseña correcta.

Microsoft Word 97 ha cambiado todo. Quizás MSDN también reveló el formato de cifrado, pero nuestra pequeña empresa no podía pagar una suscripción. Y no el hecho de que se nos permita escribir un programa para hackear después de recibir información. Para comprender, en SoftICE establecí un punto de interrupción inmediatamente después de ingresar la contraseña, y luego lentamente subí la pila hasta que encontré un algoritmo. Esto fue antes del lanzamiento de IDA Pro, por lo que tenía docenas de páginas impresas con un código de ensamblador rayado con un marcador rojo en mi pared. Estaba muy contento cuando finalmente lo descubrí. En ese momento, a Microsoft se le permitía exportar solo criptografía de 40 bits, por lo que la compañía implementó debidamente la criptografía estrictamente permitida: repetidamente cifraron la contraseña en MD5 usando "salt" (bytes seleccionados al azar del archivo),para obtener una clave de 40 bits, luego se le añadió sal y se volvió a aplicar hash. La verificación de contraseñas en las computadoras de esa época tomó aproximadamente medio segundo. Tuvimos que usar un ataque de diccionario porque era casi imposible descifrar una contraseña con fuerza bruta. Como resultado, escribimos un descifrador de contraseñas para grandes empresas y agencias. El programa ejecutó la fuerza bruta de un espacio clave de 40 bits usando estas elegantes instrucciones MMX Pentium. Escuché que una vez que trabajó durante nueve meses antes de que recogiera la contraseña.El programa ejecutó la fuerza bruta de un espacio clave de 40 bits usando estas elegantes instrucciones MMX Pentium. Escuché que una vez que trabajó durante nueve meses antes de que recogiera la contraseña.El programa ejecutó la fuerza bruta de un espacio clave de 40 bits usando estas elegantes instrucciones MMX Pentium. Escuché que una vez que trabajó durante nueve meses antes de que recogiera la contraseña.

Otro proyecto realmente divertido son los archivos zip. Phil Katz, creador de PKZIP, tomó una decisión inusual en ese momento de documentar su formato de archivo e incluir esta documentación en el paquete de software, que convirtió a ZIP en un formato favorito para los desarrolladores. Roger Schlafly desarrolló un cifrado de flujo para encriptar archivos. El estándar zip se convirtió rápidamente en el más popular en Windows, y muchos otros formatos, como archivos .jar java y documentos OpenOffice, en realidad eran archivos zip con una estructura de directorio específica en su interior. La versión de código abierto del programa se llamaba InfoZIP, era la base de casi todos los archivadores zip patentados, como WinZip. Cuando comencé a hackear WinZip, ocupaba el 95% del mercado.

Eli Biham y Paul Kocher publicaron una descripción del ataque con texto sin formato conocido (texto antes del cifrado), pero en nuestro caso, el texto sin formato conocido fue archivado . Para obtener los códigos de Huffman al comienzo de un archivo comprimido, esencialmente necesita todo el archivo. El ataque fue prácticamente inútil para la policía.

El cifrado zip contiene 96 bits de estado interno, dividido en tres bloques llamados de 32 bits key0, key1ykey2. El primero y el tercero son el estado interno de dos copias de CRC32, un registro de desplazamiento lineal con retroalimentación (un modelo matemático simple que le permite crear secuencias pseudoaleatorias). En resumen, para actualizar el estado con un nuevo byte de datos, cambia todo hacia abajo en un byte (descartando el byte inferior) y luego hace XOR con una constante de la tabla de conversión indexada por el byte de datos después de XOR con el byte inferior. key1Es el estado interno de un generador congruente lineal truncado (TLCG). Para actualizar su estado interno, agregamos un byte de datos, multiplicamos por una constante, que llamaremoscy agrega uno. El cifrado funciona de la siguiente manera: ingrese el byte de datos en el primer CRC32, luego tome el byte inferior e ingréselo en TLCG, luego tome el byte superior desde allí e ingréselo en el segundo CRC32, luego tome el estado y el cuadrado (aproximadamente), y luego emita el segundo byte resultar en una secuencia de bytes. Para inicializar 96 bits del estado interno, comience con un estado conocido y cifre la contraseña, y luego cifre diez bytes de sal.

PKZIP obtiene sus bytes de sal, asignando memoria sin inicializarla, por lo que contiene fragmentos de materiales de otros programas o imágenes en ejecución, o documentos, lo que sea. Esto funcionó bien en Windows, pero en muchos sistemas Unix, la memoria se inicializa automáticamente cuando se asigna. InfoZIP selecciona bytes de sal utilizando la funciónrandLenguaje C. Inicializó el estado del generador de números aleatorios haciendo una marca de tiempo XOR en la ID del proceso, y luego generó diez bytes por archivo. En este caso, conociendo la marca de tiempo y el identificador del proceso, fue posible, teóricamente, recuperar los bytes del encabezado, lo que, a su vez, permitió llevar a cabo un ataque de Biham y Kocher. Parece que los autores de InfoZIP sabían sobre este ataque porque fueron un paso más allá y cifraron el encabezado con una contraseña. Por lo tanto, el atacante tenía solo el doble del texto plano cifrado, y el ataque no habría funcionado.

Me di cuenta de esto, porque la contraseña es la misma en ambos pasos, el primer byte de la transmisión es el mismo en cada uno de ellos. De la misma manera que cuando el interruptor de la luz se cambia dos veces, permanece donde estaba al principio, cuando el byte se repite XOR con el mismo byte de flujo, permanece intacto. Esto me permitió desarrollar un ataque muy poderoso solo en texto cifrado : después de recibir cinco archivos cifrados en el archivo, pude generar el estado interno de la funciónrandsin tener que mirar la marca de tiempo o conocer la ID del proceso. Entonces podría generar los encabezados originales sin cifrar. Dado que solo unos pocos bits en cada parte del cifrado afectan la siguiente parte, también podría adivinar algunos bits de estado y verificar si decodificar los siguientes bytes dos veces da la respuesta que esperaba. A medida que avanzaba, tenía que adivinar cada vez menos piezas de la llave. Cada archivo adicional también permitía excluir más materiales clave potenciales; en ese momento, tomó varias horas en un escritorio. Publiqué un artículo sobre esto y tuve la oportunidad de presentarlo en Japón en la conferencia Fast Software Encryption 2001.

Pronto dejé AccessData, trabajé para una startup en redes neuronales durante un año, pasé tres años estudiando para una maestría en ciencias de la computación en la Universidad de Auckland con Chris Kaloud, comencé mis estudios de doctorado con el físico matemático John Baez en la Universidad de California Riverside, trabajé durante seis años Como parte del equipo de Seguridad Aplicada de Google, completó su doctorado y unos años más tarde se convirtió en el CTO de la nueva startup.

Hace aproximadamente medio año, inesperadamente recibí un mensaje en LinkedIn de un chico ruso. Leyó el artículo que escribí hace 19 años y quería saber si el ataque funcionaría en un archivo que contiene solo dos archivos. Un análisis rápido mostró que requiere una gran cantidad de potencia informática y dinero. Como solo hay dos archivos, en cada etapa de la selección hay muchos más falsos positivos. El resultado son ^2.773 claves posibles para la prueba, casi 10 sextillones. Calculé que un clúster grande en la GPU funcionará durante un año, y su costo será de aproximadamente 100 mil dólares. Me golpeó, diciendo que accedió a gastar tanto dinero para restaurar la llave.

El hecho es que en enero de 2016, compró bitcoins por alrededor de $ 10-15 mil y colocó las llaves en un archivo zip cifrado. Ahora cuestan más de $ 300 mil, y no podía recordar la contraseña. Afortunadamente, todavía tenía la computadora portátil original y sabía exactamente el tiempo de cifrado. Dado que InfoZip genera entropía en función de una marca de tiempo, esto prometió reducir significativamente el número de posibles opciones clave "a solo" 10 quintillones, e hizo que el ataque fuera bastante factible en un par de meses en una granja de GPU promedio. Firmamos un contrato y me puse a trabajar.

Pasé algún tiempo recuperando el ataque descrito en el artículo. Para mi disgusto, hubo algunos detalles difíciles que me perdí en el artículo, pero los resolví nuevamente. ¡Y luego descubrí que había cometido un terrible error al evaluar la cantidad de cómputo!

En mi ataque original, adiviné los bytes altos de las teclas key1 · c, key1 · c ² , key1 · c ³ y key1 · c ⁴ . Cuando adiviné este cuarto byte, sabía el estado completo del resto del cifrado; Solo necesitaba convertir estos cuatro bytes a la clave original1, y eso es todo. Revisaría el espacio de estado de 32 bits para key1 y verificaría cada uno para ver si da los bytes altos correctos. Sin embargo, aquí tendría que verificar quintillones de claves; Si necesita hacer 2 ³² pruebas en cada una, tomaría varios cientos de miles de años.

Recordaba vagamente que se había realizado algún trabajo en el criptoanálisis TLCG mediante la reducción de la base de celosía, así que desenterré el artículo original. ¡Y asi fue! Solo era necesario determinar la red con los vectores de base dados por 2 ³² y el grado de constante de TLCG, y luego hacer la reducción de la base de la red. De manera reducida, podría restaurar el estado original de bytes altos simplemente multiplicando las matrices.

Al menos esa es la idea. Se necesitaron cinco bytes para llegar al único resultado correcto, y en ese momento solo tenía cuatro ataques. El proceso descrito en el artículo rara vez dio la respuesta correcta. Sin embargo, sabía que la respuesta debería ser cercana a la correcta, por lo que podría repasar todos los valores posibles de la clave1 y verificar la diferencia entre la respuesta real y la verdadera. ¡La diferencia siempre ha sido uno de los 36 vectores! Con esta optimización, puedo reducir la búsqueda a solo 36 opciones en lugar de cuatro mil millones. Todavía estamos en el negocio.

Además, nos enfrentamos con el problema de transferir datos entre máquinas con una GPU. Mi socio comercial, Nash Foster, participó en la implementación de la GPU. Me aconsejó la rapidez con la que se realizan varias operaciones, y escribió la mayoría de las estructuras de soporte para la aplicación con mi código para el descifrado criptográfico. ¿Cómo obtener estos petabytes de claves candidatas para la prueba de GPU? Estarán inactivos casi todo el tiempo, arrojando sus núcleos en previsión del trabajo. Se me ocurrió que en cada etapa de mi ataque se verifican muchos bits, y luego solo se salva uno de los aproximadamente 65 mil candidatos. Si pudiera encontrar alguna forma de salidaestos bits se basan en la información disponible, y no solo por fuerza bruta, ahorraría mucho trabajo y, lo que es más importante, mucho tráfico de red. El problema aquí eran algoritmos demasiado complicados, que representaban una mezcla de campos finitos con anillos de enteros, pero no encajan muy bien entre sí.

Pensé en otros ataques criptoanalíticos que conozco. Uno de ellos fue el ataque de "encuentro en el medio". Parecía una candidata prometedora. El ataque se aplica a un cifrado de bloque cuando usa una parte del material clave para realizar la primera mitad del cifrado y la otra parte para la segunda. Esto se aplicaba al código postal, pero el material clave superaba con creces el número de bits en el medio. Entonces se me ocurrió, ¿qué pasa si usamos la linealidad de CRC32: si realizamos la operación XOR en las dos salidas del último CRC32, entonces el resultado será independiente de key2! En lugar de calcular el estado intermedio del cifrado y almacenarlo en una tabla, calcularía el XOR de los dos estados intermedios y lo almacenaría en su lugar.

Escribí una reunión diferencial "reunión en el medio" y la lancé en mi computadora portátil. La etapa, que solía tomar varias horas, ahora se completa en solo unos segundos. La siguiente etapa, que podría llevar una semana en la granja de GPU, terminó en unas pocas horas en una CPU potente. No pude optimizar la tercera etapa del ataque lo suficiente como para afectar la velocidad general, pero no había necesidad de mover los datos por completo: solo calculamos los candidatos para cada GPU en la computadora con estas tarjetas. Nash escribió un código de GPU que funcionó a una velocidad increíble.

El ataque duró diez días y terminó en fracaso.

Mi corazón estaba roto ¿Nos estamos perdiendo una de las claves posibles? Regresamos y observamos el identificador de proceso máximo en su computadora portátil y descubrimos que era varios bits más de lo que esperábamos y, por lo tanto, había un poco más de semillas de origen posibles rand. También revisé todo nuestro código. Tal vez nos perdimos algo? ¿Tal vez la versión en la CPU funcionó de alguna manera diferente que en la GPU? Finalmente, descubrí que la versión en la GPU no podía encontrar la clave correcta cuando era la segunda en la lista de candidatos, sino solo la primera. Al hurgar en el código, descubrimos que confundimos el índice de bloque con el índice de flujo al calcular el desplazamiento en la estructura de datos.

Solucionamos el error, volvimos a ejecutar el código y encontramos la clave correcta en un día. Nuestro cliente estaba muy satisfecho y nos dio un gran bono por encontrar la llave tan rápido y ahorrarle mucho dinero más allá de nuestra estimación inicial.

Ahora estoy buscando trabajo. Si tiene problemas interesantes con el análisis técnico o la optimización, avíseme.

---