Evolucionando decoders [1]: Brainfuck
Ya va casi un año desde el último post, como pasa el tiempo...
Esta época he estado liado con varios proyectos, he acabado mi Trabajo de Fin de Grado, del que intentaré hablar más adelante, y he participado en algún CTF. Algo que he notado es que en lo que se refiere a pruebas criptográficas suele haber dos tipos, en las que el algoritmo está claro desde el principio y hay que atacarlo. Y en las que se da un texto cifrado y se plantea el reto de obtener el flag que hay en el.
La idea detrás de este segundo tipo de pruebas (supongo) es determinar la capacidad de reconocer similitudes con cifrados ya existentes, de realizar un análisis de los datos (entropía, ...) y extraer conclusiones a partir de ahí. Hay gente que es muy buena haciendo esto...
Yo no.
Otra opción es hacer pruebas hasta que vaya apareciendo algo interesante, pero es un proceso largo y que no necesariamente da frutos, sería interesante poder automatizarlo, verdad?
Habría dos formas de atacar este problema, la primera es aplicar muchos filtros ya conocidos, todos los que se nos ocurran, y buscar en los resultados la respuesta, es muy realizable y probablemente encuentre las preguntas para retos simples, pero se atasque cuando encuentre algo nuevo (te esperarías algo en base 85?).
La segunda forma es evolucionar un decoder especifico para la cadena a "descifrar", las ventajas serían que con un poco de suerte se podría enfrentarse a problemas completamente nuevos. Como desventajas sería mucho más lento, más complejo y más dado a fallar que su contraparte no evolutiva.
En adelante intentaré desarrollar esta segunda opción, por ahora no da buenos resultados pero espero que las pruebas puedan resultar interesantes, la criatura está en este repositorio
El concepto
Bueno, deamos un paso atrás, está claro por que optamos por un acercamiento de IA (inteligencia artificial) para esto, hay una cantidad muy grande de formas en las que codificar algo, demasiado como para atacarlo con métodos más tradicionales. Así que, por cual optar? por que algoritmos evolutivos?
Por lo general las técnicas de IA parten de un conjunto de entrenamiento (machine learning), reglas predefinidas (sistemas expertos) o algún tipo de conocimiento previo del dominio. En el caso de pruebas de criptografía, no disponemos de datos de entrenamiento útiles o no serían útiles, ya que probablemente se haya usado un encoding diferente al de pruebas anteriores. Y también debemos descartar la idea de desarrollar alguna tabla de reglas, de nuevo por que no podríamos enfrentarnos a casos nuevos.
Lo que nos queda es utilizar el conocimiento específico del que dispongamos. Cuando se trata de codificación de información podemos saber como de posible es que una cierta cadena sea la respuesta, de la misma forma que lo haría una persona si la cadena es una frase coherente probablemente hayamos tenido éxito.
Esto lo podemos explotar de la siguiente forma: podemos construir un modelo de lenguaje que nos indique como de coherente es un texto.
Bien, decidido este punto queda decidir como llegar a este texto que calificaremos, podríamos
- Generar textos al azar.
- "Mutar" el texto que nos proporciona el reto hasta llegar a algo coherente.
Esto daría lugar a frases tan buenas como lo fuera modelo de lenguaje permita, pero es muy probable que no guarden ninguna relación con el texto cifrado. Una tercera aproximación más complicada sería buscar algún algoritmo que dado el texto cifrado como entrada produjese como salida el texto claro, la idea es el paso intermedio de evolucionar un programa en vez de la cadena en sí evite que se rompa el vínculo entre las dos cadenas, haciendo que el que el resultado sea coherente dependa de que el algoritmo sea el correcto para la entrada.
Así, el programa tendría 3 componentes principales, el modelo de lenguaje que sirve para puntuar, el intérprete del programa a evolucionar y los algoritmos de cruce.
El modelo de lenguaje
Es el componente encargado de decidir como de cercano a una frase normal es un texto. Los problemas que tendrá esto son bastante claros de entrada, y es que es algo extremadamente complejo, hay una disciplina de IA dedicada exclusivamente a la interpretación de lenguajes naturales (NLP) y si bien va avanzando, los resultados varían mucho según el lenguaje utilizado, y aún en los casos ideales, queda mucho por recorrer.
Para este caso en concreto además tendremos que dar una puntuación que indíque la cercanía, para dirigir la evolución de los programas. Como construir a mano un modelo para cada lenguaje que vayamos a utilizar y actualizarlo cada vez que queramos modificar cosas es bastante incómodo lo que haremos será calcularlo al vuelo a partir de un conjunto de textos que proporcione el usuario.
En este momento el modelo depende de 5 parametros, una lista de bigramas (la probabilidad de que después de que un caracter vaya otro dado), trigramas (lo mismo para grupos de 3), palabras completas, la cantidad de basura (caracteres no printables o que no se corresponden a una palabra), y una medida de la entropía del lenguaje.
El modelo esperado se calcula al arrancar el programa a partir de un texto de diccionario, los resultados son suficientes para realizar pruebas pero mejorables.
1 2 3 4 5 6 7 8 9 10 11 12 | |
La cadena "Hello world" tiene una puntuación muy alta con respecto a la mayoría, pero es menor que la de "Hellox world", que dificilmente es la que buscamos. De todas formas esto probablemente sea un bug, más que un problema de concepto.
El modelo de lenguajes se encuentra en el directorio src/lang-model/.
Intérprete y cruce
Aquí no hay mucho que decir, el intérprete es simplemente uno de brainfuck (por simplicidad) y los cruces... son mediocres, simplemente muta todos menos el mejor, la cantidad de mutaciones depende de la puntuación obtenida, a mejor puntuación menos mutaciones. Después itera sobre la peor mitad de programas y los cruza aleatoriamente, alternando un símbolo de cada uno de los dos individuos a cruzar.
Resultados
Lo cierto es que esperaba que no funcionara en absoluto y se quedara como un experimento con el que refrescar conceptos, pero es capaz de encontrar soluciones a problemas... ridículamente sencillos, eso sí
Copiar la entrada en la salida (solo son necesarios los 14 primeros caracteres, y de ellos 10 sobran)
1 2 3 4 5 6 7 8 9 10 | |
Sumar 1 a todas las entradas (solo los primeros 10, de los que vuelven a sobrar 4)
1 2 3 4 5 6 7 8 9 10 | |
Sin embargo si pasamos a algo más complejo (sumar a todo 5) ya hay problemas.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | |
Esto es problema tanto del modelo de lenguaje, que da puntuaciones muy altas a cadenas poco coherentes y del lenguaje a evolucionar, ya que para cosas muy simples requiere combinaciones complejas de operaciones.
54. Beware of the Turing tar-pit in which everything is possible but nothing of interest is easy.
-- Alan Perlis. Epigrams on Programming.
Siguientes pasos
Por supuesto esto no quedará ahí, lo próximo sería afinar la puntuación que se le asigna a las cadenas y reemplazar el uso de brainfuck por otro lenguaje más expresivo, espero que los resultados vayan mejorando a medida que se implementan estas mejoras.
Hasta la próxima.