sábado, 1 de noviembre de 2008
Distribuciones módulo 1
Hace escasos días, echando un vistazo a la página de Simon Plouffe, descubrí los interesantes gráficos que tiene allí sobre distribuciones módulo 1 de ciertas secuencias numéricas. Plouffe comenta que tales gráficos permiten observar patrones interesantes y propiedades ocultas que no son evidentes de otra manera (esto es, sirven para ganar intuición, uno de los objetivos primordiales de la matemática experimental de la que él es insigne exponente).
Esos gráficos llamaron poderosamente mi atención, y llevan varios días dándome vueltas por la cabeza; hoy, por fin, he decidido aparcar un poco el resto de cosas en que estaba trabajando y dedicarle unas horas... He estado experimentando, manual de gnuplot a la vista, con potencias modulares de tipo base^k (mod n) como las que Plouffe tiene en su página. Los resultados son muy interesantes y, amén de la calidad estética de las imágenes —francamente bonitas, en mi opinión—, he podido juguetear con esos patrones de los que él hablaba.
Es conveniente que muestre imágenes. Todas las que vienen a continuación son básicamente del mismo tipo: se toman n puntos de la circunferencia unidad (siendo n el módulo usado en las operaciones modulares) equidistribuidos, con el 0 en el oeste de la circunferencia, se calcula la secuencia 2^k (mod n) y se traza un segmento de línea entre cada 2 puntos consecutivos de la secuencia. Además, dado que a poco que pongas juntas unos cuantos centenares de líneas sin cuidado es probable que sólo veas un borrón, he tenido que jugar con los grosores de línea para poder ver patrones de distinta «relevancia», por decirlo de algún modo.
Y ahora las imágenes...
2^k (mod 1301):
5^k (mod 1301):
317^k (mod 1301):
2^k (mod 11807):
5^k (mod 11807):
5903^k (mod 11807):
Estas tres últimas son de 2^k (mod 521*751), a tres «niveles de detalle» distintos:
Creo que sería muy interesante dedicar algo de esfuerzo a hacer un visualizador que permitiese ver estas imágenes y cambiar parámetros en tiempo real. De cualquier modo, no será ahora, pues se me acumula el trabajo. Tantas cosas que hacer y tan poco tiempo...
Esos gráficos llamaron poderosamente mi atención, y llevan varios días dándome vueltas por la cabeza; hoy, por fin, he decidido aparcar un poco el resto de cosas en que estaba trabajando y dedicarle unas horas... He estado experimentando, manual de gnuplot a la vista, con potencias modulares de tipo base^k (mod n) como las que Plouffe tiene en su página. Los resultados son muy interesantes y, amén de la calidad estética de las imágenes —francamente bonitas, en mi opinión—, he podido juguetear con esos patrones de los que él hablaba.
Es conveniente que muestre imágenes. Todas las que vienen a continuación son básicamente del mismo tipo: se toman n puntos de la circunferencia unidad (siendo n el módulo usado en las operaciones modulares) equidistribuidos, con el 0 en el oeste de la circunferencia, se calcula la secuencia 2^k (mod n) y se traza un segmento de línea entre cada 2 puntos consecutivos de la secuencia. Además, dado que a poco que pongas juntas unos cuantos centenares de líneas sin cuidado es probable que sólo veas un borrón, he tenido que jugar con los grosores de línea para poder ver patrones de distinta «relevancia», por decirlo de algún modo.
Y ahora las imágenes...
2^k (mod 1301):
5^k (mod 1301):
317^k (mod 1301):
2^k (mod 11807):
5^k (mod 11807):
5903^k (mod 11807):
Estas tres últimas son de 2^k (mod 521*751), a tres «niveles de detalle» distintos:
Creo que sería muy interesante dedicar algo de esfuerzo a hacer un visualizador que permitiese ver estas imágenes y cambiar parámetros en tiempo real. De cualquier modo, no será ahora, pues se me acumula el trabajo. Tantas cosas que hacer y tan poco tiempo...
domingo, 21 de septiembre de 2008
3in1
Últimamente he estado bastante animado trabajando en cifrados relacionados con el mundo de la emulación arcade, pero no he dedicado tiempo a explicar qué estaba haciendo. Antes de que pierda definitivamente la motivación para hacerlo, ha llegado el momento de contar algo...
39in1
En este caso se trataba de uno de esos sistemas multijuego piratas que empezaron a surgir hace unos años; el equipo de MAME tiene la sospecha de que, de hecho, se está usando (de forma obviamente no autorizada) una versión de MAME para emular los juegos incluidos. De cualquier modo, se tomó la decisión de que, como máquina arcade que era, debía ser emulada por MAME, lo que llevaría a la situación inédita de que, por primera vez, MAME emularía a MAME. Divertido. :)
El caso es que la ROM de código estaba cifrada, así que se requería descifrarla antes de poder comenzar con la emulación. En principio se veían ciertos patrones al final de la ROM que, pensábamos, quizá nos darían alguna pista sobre cómo actuaba el cifrado. Sin embargo, tras algo de estudio y unos muy útiles intercambios de ideas con O. Galibert, quedó claro que en realidad lo que pasaba era esto: en un intento de dificultar un posible descifrado, el autor o autores, quienes quiera que fuesen, no quisieron dejar el final de la ROM en blanco, y la rellenaron con datos «aleatorios». Y aquí es donde viene lo divertido, porque tras algo de estudio fuimos capaces de descubrir qué generador de números pseudoaleatorios se había utilizado para rellenar esa zona (utilizaron un generador que ha sido usado en muchas implementaciones de la función rand() en compiladores ANSI C, concretamente el primero que podéis ver en esta página) y, gracias a ello, recuperamos un número suficiente de pares texto claro-texto cifrado como para entender completamente el cifrado. Así que precisamente ese intento de dificultar la comprensión del cifrado fue lo que nos permitió atacar más facilmente el sistema. ¿No es irónico? xD
Existen además otras ROMs hermanas de ésta con un distinto número de juegos, aunque creadas obviamente por las mismas personas. Es de suponer que irán apareciendo poco a poco a medida que se consiga emular estas máquinas (de momento parece que hay algún tipo de problema con una protección adicional).
Atomiswave
En este caso apenas disponíamos de datos para un par de juegos, y sólo uno de ellos completo. Las ROMs estaban cifradas y, para cuando el problema cayó en mis manos, O. Galibert ya había comprendido parte del cifrado (concretamente, la dependencia de la dirección), por lo que lo único que quedaba era una permutación del conjunto {0,1,2,...2^16-1} que se aplicaba a las palabras de 16 bits. Estaba claro que cada juego usaba la suya propia, sin relación aparente entre ellas, y apenas se tenían unos pares texto plano-texto cifrado, que se habían obtenido de la cabecera del fichero ya que ElSemi había estado trasteando con la BIOS y sabía qué había en los primeros bytes del fichero original.
Aquí, tras algunos intentos infructuosos de obtener más pares texto plano-texto cifrado mediante análisis de las estadísticas de la ROM de código, la idea que finalmente funcionó fue esta: dado que el sistema Atomiswave estaba basado en Naomi, era probable que parte de las librerías usadas en juegos Naomi también se usasen en los juegos Atomiswave; así que, tras comparar unas ROMs de Naomi y localizar algunos trozos comunes de código relativamente grandes (digamos de más de 64 bytes), intenté buscar esos mismos segmentos de código en las ROMs cifradas de Atomiswave. ¿Cómo hacerlo, si, al fin y al cabo, la ROM está cifrada y eso nos impide compararla con las secuencias de bytes que habíamos aislado? Bueno, si bien una comparación directa no era posible, si podíamos buscar trozos con la misma estructura; vale decir, dado que el cifrado que quedaba era simplemente una permutación de bloques de 16 bits, si en esos segmentos de código disponíamos de una buena cantidad de pares idénticos de palabras de 16 bits, podíamos simplemente buscar regiones dentro de las ROMs cifradas que mostrasen paren idénticos en las mismas posiciones que las secuencias de referencia.
Mediante este método, localicé unos 8000 pares texto plano-texto cifrado (si bien posteriormente me di cuenta que dos de los pares habían sido incorrectamente asignados). Y prácticamente ahí acaba la historia, porque una vez que disponíamos de tal número de pares, el cifrado claudicó rápidamente. Un simple análisis de cómo cambiaban los bits de salida cuando cambiábamos un bit de entrada tenía este aspecto:
mostrando a las claras que esa permutación de 16 bits, de hecho, tenía una estructura de bloques de la forma 5+4+4+3. Dado que el bloque más grande era de 5 bits (32 valores posibles, por tanto), con nuestros 8000 pares teníamos más que suficiente para reconstruir completamente cada uno de los bloques, dando por concluido el trabajo.
Para más detalles, échese un ojo al driver en MAME.
Neo Geo M1
En este caso, se trataba del cifrado de la ROM de sónido que incluían los últimos juegos creados para la plataforma Neo Geo; se disponía de las ROMs cifradas, así como de las ROMs supuestamente descifradas usadas en copias ilegales de las máquinas. El cifrado en este caso era un barajado de las 2^16 direcciones formadas por los 16 bits de menor peso de la dirección; tal barajado operaba en bloques de 64 KiB, en cada uno de ellos aparentemente de forma distinta.
Sin embargo, a pesar de tener los datos cifrados y los datos planos, el barajado exacto de la dirección no se conocía. ¿Cómo es posible esto? Se explica por el hecho de que, en cada bloque de 64 KiB tenemos 2^16 posiciones pero, dado que los datos en sí son de 8 bits, cada valor de ese byte de datos aparece repetido muchas veces tanto en los datos planos como en los datos cifrados, por lo que no hay forma sencilla de saber cuál corresponde a cuál.
En este caso, tras unos primeros días de estudio poco provechosos, la idea que finalmente funcióno surgió de una conversación con Haze en la que me apuntó la forma que tenían los cifrados utilizados por las otras ROMs de la Neo Geo. El hecho de que se estuviesen usando tablas de permutación de 256 bytes (tablas que toman 8 bits de entrada y establecen un buen barajado de los 2^8 posibles valores de entrada me animó a llevar al límite una idea que había probado con escaso éxito un día antes.
Se trataba de, considerando el barajado de la dirección que buscábamos como la función de referencia, que toma como entrada una direccion de las 2^16 posibles, y te devuelve la que le corresponderia tras el barajado, intentar localizar algún bit de la salida de la función que fuese obtenido como un bit de entrada de la función XOR (o exclusivo) con una función arbitraria de otros 8 bits de entrada (que produjese un solo bit de salida).
¿Cómo hacer esto? Bien, saber cuál sería ese bit de salida, cuál el de entrada y cuál los 8 utilizados por la función es algo que sólo puede ser «adivinado»; vale decir, que hay que probar todas las posibilidades hasta encontrar la buena, si es que existe. Supongamos, pues, que hemos conseguido saber cuáles son los bits que nos valdrían, ¿cómo averiguar ahora en qué consistiría esa «función arbitraria» de 8 bits de entrada y uno de salida.
Bien, una tal función puede ser expresada como un polinomio en Z/2Z[i0,i1,..., i7], esto es, un polinomio en las variables i0, i1, ..., i7 (los bits de entrada, como ya habréis supuesto) y que toma valores en los enteros módulo 2 (porque sólo tenemos un bit de salida). Si lo pensáis un poco, el número de monomios posible con n variables en este caso es 2^n, por lo que descubrir cuál es esa función arbitraria puede reducirse a descubrir cualés de nuestros 2^8 posibles monomios están presentes y cuáles no. Si nos pusiésemos a buscar sin más, no habría nada que hacer, porque, obviamente, el número de posibilidades es 2^(2^8)=2^256. La forma de salir del atolladero es ésta:
Si numeramos los posibles monomios de 0 a 255 (m_0, m_1, ..., m_n, m_n+1, ..., m_255) y, usamos unos variables x_n que nos indiquen si el monomio n-ésimo está presente en nuestro polinomio (x_n=1) o no (x_n=0), la función buscada puede expresarse como:
f = sum(m_n*x_n, n, 0, 255, Z/2Z)
Ahora, si seleccionamos uno de esos bloques de 64 KiB de una ROM cifrada donde todos los valores posibles de los bytes de datos estén presentes, podemos hacer lo siguiente:
Dado un valor A (0<=A<256), style="font-style: italic;">py)+sum(m_n*x_n[M(py)], n, [0, 255], Z/2Z) (mód. 2) , py perteneciente a E_A, Z) = sum(OB(pz), pz perteneciente a D_A, Z)
(aquí, m_n*x_n[M(py)] representa el valor del monomio en el punto py, Z y Z/2Z son los anillos de sumación y py y pz son índices, respectivamente, de E_A y D_A).
Si ahora, en los sumatorios exteriores, en lugar de sumar en Z sumamos en Z/2Z (nótese que estamos desperdiciando información; esto será importante luego).
sum(IB(py), +sum(m_n*x_n[M(py)], n, [0, 255], Z/2Z) (mód. 2) , py perteneciente a E_A, Z/2Z) = sum(OB(pz), pz perteneciente a D_A, Z/2Z), de donde
sum(IB(py), py perteneciente a E_A, Z/2Z) + sum(sum(m_n*x_n[M(py)], n, [0, 255], Z/2Z), py perteneciente a E_A, Z/2Z)) (mód. 2) = sum(OB(pz), pz perteneciente a D_A, Z/2Z), de donde, a su vez,
sum(sum(m_n*x_n[M(py)], n, [0, 255], Z/2Z), py perteneciente a E_A, Z/2Z) = sum(OB(pz), pz perteneciente a D_A, Z/2Z) - sum(IB(py), py perteneciente a E_A, Z/2Z) (mód. 2)
Ahora el segundo término de la ecuación puede ser calculado sin problemas para cada A; si denotamos por g(A) a ese segundo término (la función g nos devuelve un bit que sólo depende del valor A), tenemos
sum(sum(m_n*x_n[M(py)], n, [0, 255], Z/2Z), py perteneciente a E_A, Z/2Z) = g(A)
Si ahora intercambiamos el orden de sumación de los dos sumatorios, tenemos:
sum(sum(m_n*x_n[M(py)], py perteneciente a E_A, Z/2Z), n, [0, 255], Z/2Z) = g(A)
Sacando x_n fuera del sumatorio (piénsese por qué esto es posible):
sum(x_n*sum(m_n[M(py)], py perteneciente a E_A, Z/2Z), n, [0, 255], Z/2Z) = g(A)
Observemos que las nuevas sumas interiores pueden calcularse ya sin problemas para cada A y cada n. Si denotamos
h(A,n) = sum(m_n[M(py)], py perteneciente a E_A, Z/2Z), tenemos
sum(x_n*h(A,n), n, [0,255], Z/2Z) = g(A)
o sea, una ecuación lineal en las variables x_n, 0<=n<255.
Pero, como recordaréis de vuestras clases de secundaria, necesitaríamos 256 ecuaciones linealmente independientes para resolver un sistema con 256 variables. ¿De dónde sacaremos esas ecuaciones? En realidad, ya las tenemos, porque esa ecuación de arriba depende del parámetro A, que era un valor cualquiera de los bytes de datos. Dado que hay 256 posibles valores para A, tenemos 256 ecuaciones. ¿Hemos terminado? No, porque no es realista esperar que las 256 ecuaciones sean linealmente independientes (haciendo pruebas, vi que, en general, 2 o 3 solían ser linealmente dependientes de las demás).
Lo que haremos, entonces, será resolver el sistema dejando algunas variables libres (tantas como ecuaciones nos falten para llegar a 256); si estuviésemos resolviendo el sistema en Z, eso nos daría infinitas soluciones, pero, en Z/2Z, m variables libres tan sólo producen 2^m posibles soluciones. ¿Cómo conseguiremos distinguir la buena de las que no lo son? Lo sabremos porque, una vez que tenemos un conjunto de valores para las variables x_n que es candidato a solución de nuestro problema, podemos volver a la primera ecuación que escribimos (en la que se hacía una sumación en Z y no en Z/2Z) y ver si esa ecuación se verifica. En resumidas cuentas, es de esperar que sólo la combinación buscada sea solución de esa ecuación.
Bueno, pues este es el núcleo de la idea; implementarla me costó un par de días entre escribir el código, depurarlo, probarlo y finalmente ejecutarlo sobre los datos reales. El resultado, tras 22,5 horas de ejecución en un ordenador de dos núcleos (a 1,86 Ghz cada uno) fue positivo y mostró a las claras que existían dos tablas de 256 bytes utilizadas para hacer el barajado.
Una vez conseguido esto y aisladas las tablas, el resto era fácil. No continuaré con los detalles para no aburrir; soy consciente de que esta última parte ha quedado muy densa; el hecho de no tener un buen editor de fórmulas científicas integrado aquí hace farragosa la notación. Espero, no obstante, que podáis seguir más o menos la idea principal.
39in1
En este caso se trataba de uno de esos sistemas multijuego piratas que empezaron a surgir hace unos años; el equipo de MAME tiene la sospecha de que, de hecho, se está usando (de forma obviamente no autorizada) una versión de MAME para emular los juegos incluidos. De cualquier modo, se tomó la decisión de que, como máquina arcade que era, debía ser emulada por MAME, lo que llevaría a la situación inédita de que, por primera vez, MAME emularía a MAME. Divertido. :)
El caso es que la ROM de código estaba cifrada, así que se requería descifrarla antes de poder comenzar con la emulación. En principio se veían ciertos patrones al final de la ROM que, pensábamos, quizá nos darían alguna pista sobre cómo actuaba el cifrado. Sin embargo, tras algo de estudio y unos muy útiles intercambios de ideas con O. Galibert, quedó claro que en realidad lo que pasaba era esto: en un intento de dificultar un posible descifrado, el autor o autores, quienes quiera que fuesen, no quisieron dejar el final de la ROM en blanco, y la rellenaron con datos «aleatorios». Y aquí es donde viene lo divertido, porque tras algo de estudio fuimos capaces de descubrir qué generador de números pseudoaleatorios se había utilizado para rellenar esa zona (utilizaron un generador que ha sido usado en muchas implementaciones de la función rand() en compiladores ANSI C, concretamente el primero que podéis ver en esta página) y, gracias a ello, recuperamos un número suficiente de pares texto claro-texto cifrado como para entender completamente el cifrado. Así que precisamente ese intento de dificultar la comprensión del cifrado fue lo que nos permitió atacar más facilmente el sistema. ¿No es irónico? xD
Existen además otras ROMs hermanas de ésta con un distinto número de juegos, aunque creadas obviamente por las mismas personas. Es de suponer que irán apareciendo poco a poco a medida que se consiga emular estas máquinas (de momento parece que hay algún tipo de problema con una protección adicional).
Atomiswave
En este caso apenas disponíamos de datos para un par de juegos, y sólo uno de ellos completo. Las ROMs estaban cifradas y, para cuando el problema cayó en mis manos, O. Galibert ya había comprendido parte del cifrado (concretamente, la dependencia de la dirección), por lo que lo único que quedaba era una permutación del conjunto {0,1,2,...2^16-1} que se aplicaba a las palabras de 16 bits. Estaba claro que cada juego usaba la suya propia, sin relación aparente entre ellas, y apenas se tenían unos pares texto plano-texto cifrado, que se habían obtenido de la cabecera del fichero ya que ElSemi había estado trasteando con la BIOS y sabía qué había en los primeros bytes del fichero original.
Aquí, tras algunos intentos infructuosos de obtener más pares texto plano-texto cifrado mediante análisis de las estadísticas de la ROM de código, la idea que finalmente funcionó fue esta: dado que el sistema Atomiswave estaba basado en Naomi, era probable que parte de las librerías usadas en juegos Naomi también se usasen en los juegos Atomiswave; así que, tras comparar unas ROMs de Naomi y localizar algunos trozos comunes de código relativamente grandes (digamos de más de 64 bytes), intenté buscar esos mismos segmentos de código en las ROMs cifradas de Atomiswave. ¿Cómo hacerlo, si, al fin y al cabo, la ROM está cifrada y eso nos impide compararla con las secuencias de bytes que habíamos aislado? Bueno, si bien una comparación directa no era posible, si podíamos buscar trozos con la misma estructura; vale decir, dado que el cifrado que quedaba era simplemente una permutación de bloques de 16 bits, si en esos segmentos de código disponíamos de una buena cantidad de pares idénticos de palabras de 16 bits, podíamos simplemente buscar regiones dentro de las ROMs cifradas que mostrasen paren idénticos en las mismas posiciones que las secuencias de referencia.
Mediante este método, localicé unos 8000 pares texto plano-texto cifrado (si bien posteriormente me di cuenta que dos de los pares habían sido incorrectamente asignados). Y prácticamente ahí acaba la historia, porque una vez que disponíamos de tal número de pares, el cifrado claudicó rápidamente. Un simple análisis de cómo cambiaban los bits de salida cuando cambiábamos un bit de entrada tenía este aspecto:
56 40 44 30 30 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 60 22 42 8 0 0 0 0 0 0 0
32 44 32 14 38 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 2 10 8
0 0 0 0 0 0 0 0 0 12 34 8 20 0 0 0
0 0 0 0 0 24 10 22 98 0 0 0 0 0 0 0
0 0 0 0 0 26 40 38 26 0 0 0 0 0 0 0
48 18 46 46 40 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 62 60 4 8 0 0 0
0 0 0 0 0 0 0 0 0 12 16 12 28 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 8 0 10
86 32 48 34 32 0 0 0 0 0 0 0 0 0 0 0
62 36 52 48 88 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 10 10 0
0 0 0 0 0 0 0 0 0 48 16 10 12 0 0 0
0 0 0 0 0 50 14 30 42 0 0 0 0 0 0 0
mostrando a las claras que esa permutación de 16 bits, de hecho, tenía una estructura de bloques de la forma 5+4+4+3. Dado que el bloque más grande era de 5 bits (32 valores posibles, por tanto), con nuestros 8000 pares teníamos más que suficiente para reconstruir completamente cada uno de los bloques, dando por concluido el trabajo.
Para más detalles, échese un ojo al driver en MAME.
Neo Geo M1
En este caso, se trataba del cifrado de la ROM de sónido que incluían los últimos juegos creados para la plataforma Neo Geo; se disponía de las ROMs cifradas, así como de las ROMs supuestamente descifradas usadas en copias ilegales de las máquinas. El cifrado en este caso era un barajado de las 2^16 direcciones formadas por los 16 bits de menor peso de la dirección; tal barajado operaba en bloques de 64 KiB, en cada uno de ellos aparentemente de forma distinta.
Sin embargo, a pesar de tener los datos cifrados y los datos planos, el barajado exacto de la dirección no se conocía. ¿Cómo es posible esto? Se explica por el hecho de que, en cada bloque de 64 KiB tenemos 2^16 posiciones pero, dado que los datos en sí son de 8 bits, cada valor de ese byte de datos aparece repetido muchas veces tanto en los datos planos como en los datos cifrados, por lo que no hay forma sencilla de saber cuál corresponde a cuál.
En este caso, tras unos primeros días de estudio poco provechosos, la idea que finalmente funcióno surgió de una conversación con Haze en la que me apuntó la forma que tenían los cifrados utilizados por las otras ROMs de la Neo Geo. El hecho de que se estuviesen usando tablas de permutación de 256 bytes (tablas que toman 8 bits de entrada y establecen un buen barajado de los 2^8 posibles valores de entrada me animó a llevar al límite una idea que había probado con escaso éxito un día antes.
Se trataba de, considerando el barajado de la dirección que buscábamos como la función de referencia, que toma como entrada una direccion de las 2^16 posibles, y te devuelve la que le corresponderia tras el barajado, intentar localizar algún bit de la salida de la función que fuese obtenido como un bit de entrada de la función XOR (o exclusivo) con una función arbitraria de otros 8 bits de entrada (que produjese un solo bit de salida).
¿Cómo hacer esto? Bien, saber cuál sería ese bit de salida, cuál el de entrada y cuál los 8 utilizados por la función es algo que sólo puede ser «adivinado»; vale decir, que hay que probar todas las posibilidades hasta encontrar la buena, si es que existe. Supongamos, pues, que hemos conseguido saber cuáles son los bits que nos valdrían, ¿cómo averiguar ahora en qué consistiría esa «función arbitraria» de 8 bits de entrada y uno de salida.
Bien, una tal función puede ser expresada como un polinomio en Z/2Z[i0,i1,..., i7], esto es, un polinomio en las variables i0, i1, ..., i7 (los bits de entrada, como ya habréis supuesto) y que toma valores en los enteros módulo 2 (porque sólo tenemos un bit de salida). Si lo pensáis un poco, el número de monomios posible con n variables en este caso es 2^n, por lo que descubrir cuál es esa función arbitraria puede reducirse a descubrir cualés de nuestros 2^8 posibles monomios están presentes y cuáles no. Si nos pusiésemos a buscar sin más, no habría nada que hacer, porque, obviamente, el número de posibilidades es 2^(2^8)=2^256. La forma de salir del atolladero es ésta:
Si numeramos los posibles monomios de 0 a 255 (m_0, m_1, ..., m_n, m_n+1, ..., m_255) y, usamos unos variables x_n que nos indiquen si el monomio n-ésimo está presente en nuestro polinomio (x_n=1) o no (x_n=0), la función buscada puede expresarse como:
f = sum(m_n*x_n, n, 0, 255, Z/2Z)
Ahora, si seleccionamos uno de esos bloques de 64 KiB de una ROM cifrada donde todos los valores posibles de los bytes de datos estén presentes, podemos hacer lo siguiente:
Dado un valor A (0<=A<256), style="font-style: italic;">py)+sum(m_n*x_n[M(py)], n, [0, 255], Z/2Z) (mód. 2) , py perteneciente a E_A, Z) = sum(OB(pz), pz perteneciente a D_A, Z)
(aquí, m_n*x_n[M(py)] representa el valor del monomio en el punto py, Z y Z/2Z son los anillos de sumación y py y pz son índices, respectivamente, de E_A y D_A).
Si ahora, en los sumatorios exteriores, en lugar de sumar en Z sumamos en Z/2Z (nótese que estamos desperdiciando información; esto será importante luego).
sum(IB(py), +sum(m_n*x_n[M(py)], n, [0, 255], Z/2Z) (mód. 2) , py perteneciente a E_A, Z/2Z) = sum(OB(pz), pz perteneciente a D_A, Z/2Z), de donde
sum(IB(py), py perteneciente a E_A, Z/2Z) + sum(sum(m_n*x_n[M(py)], n, [0, 255], Z/2Z), py perteneciente a E_A, Z/2Z)) (mód. 2) = sum(OB(pz), pz perteneciente a D_A, Z/2Z), de donde, a su vez,
sum(sum(m_n*x_n[M(py)], n, [0, 255], Z/2Z), py perteneciente a E_A, Z/2Z) = sum(OB(pz), pz perteneciente a D_A, Z/2Z) - sum(IB(py), py perteneciente a E_A, Z/2Z) (mód. 2)
Ahora el segundo término de la ecuación puede ser calculado sin problemas para cada A; si denotamos por g(A) a ese segundo término (la función g nos devuelve un bit que sólo depende del valor A), tenemos
sum(sum(m_n*x_n[M(py)], n, [0, 255], Z/2Z), py perteneciente a E_A, Z/2Z) = g(A)
Si ahora intercambiamos el orden de sumación de los dos sumatorios, tenemos:
sum(sum(m_n*x_n[M(py)], py perteneciente a E_A, Z/2Z), n, [0, 255], Z/2Z) = g(A)
Sacando x_n fuera del sumatorio (piénsese por qué esto es posible):
sum(x_n*sum(m_n[M(py)], py perteneciente a E_A, Z/2Z), n, [0, 255], Z/2Z) = g(A)
Observemos que las nuevas sumas interiores pueden calcularse ya sin problemas para cada A y cada n. Si denotamos
h(A,n) = sum(m_n[M(py)], py perteneciente a E_A, Z/2Z), tenemos
sum(x_n*h(A,n), n, [0,255], Z/2Z) = g(A)
o sea, una ecuación lineal en las variables x_n, 0<=n<255.
Pero, como recordaréis de vuestras clases de secundaria, necesitaríamos 256 ecuaciones linealmente independientes para resolver un sistema con 256 variables. ¿De dónde sacaremos esas ecuaciones? En realidad, ya las tenemos, porque esa ecuación de arriba depende del parámetro A, que era un valor cualquiera de los bytes de datos. Dado que hay 256 posibles valores para A, tenemos 256 ecuaciones. ¿Hemos terminado? No, porque no es realista esperar que las 256 ecuaciones sean linealmente independientes (haciendo pruebas, vi que, en general, 2 o 3 solían ser linealmente dependientes de las demás).
Lo que haremos, entonces, será resolver el sistema dejando algunas variables libres (tantas como ecuaciones nos falten para llegar a 256); si estuviésemos resolviendo el sistema en Z, eso nos daría infinitas soluciones, pero, en Z/2Z, m variables libres tan sólo producen 2^m posibles soluciones. ¿Cómo conseguiremos distinguir la buena de las que no lo son? Lo sabremos porque, una vez que tenemos un conjunto de valores para las variables x_n que es candidato a solución de nuestro problema, podemos volver a la primera ecuación que escribimos (en la que se hacía una sumación en Z y no en Z/2Z) y ver si esa ecuación se verifica. En resumidas cuentas, es de esperar que sólo la combinación buscada sea solución de esa ecuación.
Bueno, pues este es el núcleo de la idea; implementarla me costó un par de días entre escribir el código, depurarlo, probarlo y finalmente ejecutarlo sobre los datos reales. El resultado, tras 22,5 horas de ejecución en un ordenador de dos núcleos (a 1,86 Ghz cada uno) fue positivo y mostró a las claras que existían dos tablas de 256 bytes utilizadas para hacer el barajado.
Una vez conseguido esto y aisladas las tablas, el resto era fácil. No continuaré con los detalles para no aburrir; soy consciente de que esta última parte ha quedado muy densa; el hecho de no tener un buen editor de fórmulas científicas integrado aquí hace farragosa la notación. Espero, no obstante, que podáis seguir más o menos la idea principal.
Etiquetas: emulación
jueves, 31 de julio de 2008
FD1089
Hace unos meses, Lord Nightmare me puso al corriente del problema existente con la generación de claves en los juegos de SEGA que usaban el circuito de seguridad FD1089 (del que se conocen dos variantes: FD1089A y FD1089B). Resumiendo mucho el asunto, en esa época SEGA había venido usando generadores de números pseudoaleatorios (GNPA; más concretamente, generadores de congruencia lineal, GCL de ahora en adelante) para generar las claves usadas en otros circuitos de seguridad. Dado que se conocían circuitos anteriores y posteriores a esa época que usaban un cierto GCL para generar las claves, se tenía la firme sospecha de que eso también ocurría con el FD1089, aunque aún no se había comprendido de qué forma las claves dependían del GNPA, ni se tenía la seguridad de que fuese el mismo usado en los otros circuitos.
En aquel momento no disponía de mucho tiempo pero ahora, tras haber concluido el trabajo con el SPC7110, creí que sería un buen momento de retomar el asunto.
Un primer vistazo mostraba que, para cada juego, teníamos 0x2000 octetos de clave divididos en 2 grupos de 0x1000 (uno es usado para encriptar los datos, y otro para el código). Una de las mayores dificultades del asunto era que, de hecho, debido a la forma en la que se habían recuperado esas tablas, la elección de los valores era arbitraria, y lo único que se podía garantizar era que existía una tabla fija de 256 entradas que establecía una permutación entre la salida del GNPA y los valores de las tablas. Además, observando las subtablas usada para encriptar el código, se podía ver con facilidad que uno de los 256 valores nunca estaba presente (esto ya se había visto hacer en otros circuitos: SEGA utilizaba un valor especial para marcar ciertas posiciones de las tablas de datos como «NO CIFRADO», por lo que ese valor tenía un significado especial y no podía usarse como un valor de cifrado normal).
Con todo eso, comencé a probar algunas ideas acerca de cómo operaban esas tablas de permutación (hablo en plural porque se sabía que para las dos revisiones del circuito eran distintas y para cada una de las dos subtablas de tamaño 0x1000 también) bajo la hipótesis de que, si pudiésemos estudiar las tablas de claves antes y después de aplicar esa «permutación arbitraria», se debería de observar un claro incremento en las estadísticas de aleatoriedad de las mismas. No obstante, esta línea de ataque no funcionó, pues quedó claro que los 0x1000 octetos de una sola tabla (o incluso todos los que se podían obtener para las tablas de cifrado de código para todos los juegos de una misma revisión del circuito) eran insuficientes para que esto pudiese funcionar.
Así que tocaba intentar otras cosas. Bajo la hipótesis de que el GNPA era un GCL del mismo tipo que el usado en el FD1094 y en el MC8123 (esto es, con módulo una potencia de 2), cabía intentar otro tipo de ataque directo: se sabe que, cuando el módulo usado por el GCL es una potencia de 2, cada uno de los bits de la salida generada muestra ciclos de tamaño 2^n, con n aumentando con el número de bit (esto es, si un bit muestra ciclos de tamaño 2^15, el siguiente mostrará ciclos de tamaño 2^16, y así por menudo...). De hecho, así es como Aaron se dio cuenta de que un GCL estaba siendo usado para generar (parte de) las claves usadas con el FD1094 (podéis leer sobre ello aquí: Notas de Aaron sobre el FD1094). Pero lo interesante para nosotros es que, si aislas uno de esos bits y observas el ciclo que desarrolla, puedes ver que ese ciclo se puede dividir en dos mitades de forma que una mitad es la imagen «especular» de la otra (léase: hay unos donde en la otra hay ceros, y viceversa).
Así pues, si la tabla fuese creada con bits generados por un GCL de este tipo, y tuviésemos la suerte de que en nuestros 0x1000 octetos al menos uno de los bits (el menos significativo) tuviese un ciclo de tamaño menor o igual que 0x1000, podríamos tratar de separar los 256 valores de la permutación en dos clases de equivalencia, de forma que un grupo de 128 valores estuviese asociado a uno de los dos valores posibles de ese bit, y el otro al valor restante. ¿Qué posibilidades de éxito tenía esta idea? Con la cantidad de datos disponibles, muy pocas en general para multiplicadores de GCL arbitrarios, pero me animaba el hecho de que el GCL usado por el FD1094 y el MC8123 tenía unos parámetros muy malos, que hacen que los ciclos que muestran sus bits sean menores que con parámetros óptimos. Así que, si tenía suerte y el GCL era el mismo, me bastaría que alguno de los 6 juegos para los que disponía de una tabla de cifrado de código completa tuviese una semilla inicial que fuese múltiplo de 4. Esto nos daría 6 intentos con una probabilidad de éxito del 25% cada uno; merecía la pena intentarlo.
Existía una dificultad añadida para llevar a cabo la prueba: dado que el GCL filtra uno de los 256 valores, las tablas tienen «huecos» que nos impiden emparejar de forma sencilla cada una de las dos mitades de ese ciclo. No obstante, cabía la esperanza de que el número de valores consecutivos necesarios en cada una de las dos partes del ciclo fuese bajo, lo que nos permitiría buscar 2 zonas libres de huecos que fuese «imágenes especulares» en la secuencia original. Unos cuantos experimentos después, quedó claro que esas dos zonas deberían ser de unos 256 octetos cada una para evitar la posibilidad de falsos positivos y falsos negativos. Un número mayor de lo que me hubiese gustado, pero no tan grande como para hacer inviable el ataque.
Así que, manos a la obra, implementé el ataque. Las simulaciones previas mostraban que, si el GCL era del mismo tipo que el usado en el FD1094 y el MC8123, efectivamente el ataque funcionaba si la semilla inicial era múltiplo de 4. Llegado el momento, lo comencé a aplicar sobre las tablas reales: como dije antes, tenía 6 intentos... falló el primero, el segundo, el tercero, el cuarto, el quinto y, cuando ya había perdido la fe, el sexto funcionó. ¡TOMA!
Un poco de análisis manual de los datos más tarde quedaba claro que había conseguido separar el conjunto de 256 valores en 8 clases de equivalencia de 32 valores cada una, lo que significaba que, si el GCL era el mismo que conocíamos, la semilla inicial era, de hecho, múltiplo de 16. Llegado a este punto, toda vez que ya era capaz de separar los 256 valores en 2 grupos de forma que cada uno correspondiese al valor de un cierto bit de la salida original del GCL, ya se podía intentar averiguar cuáles eran los parámetros del GCL. Fue bastante sencillo: quedó claro al poco que el generador subyacente era, como se sospechaba, exactamente el mismo usado por el FD1094 y el MC8123:
y, al mismo tiempo, fui capaz de recuperar la semilla inicial para el juego sobre el que el ataque anterior había funcionado (que era el 317-0168 para más detalles, el cual usa un FD1089B) y la tabla de permutación que establecía la correspondencia entre la salida del generador y los valores arbitrarios para las claves que Nicola había usado. Al hacerlo, también descubrí cuál era el valor del generador filtrado y me di cuenta de que la generación de las dos subtablas de claves parecía estar entrelazada de algún modo.
Tras algo más de estudio, quedó claro cómo funcionaba ese entrelazado... Como dije, hay algunas posiciones de la tabla de cifrado de datos que están marcadas como «NO CIFRAR» con ese número especial. Pues bien, la generación de las tablas se produce en dos pasadas: en la primera, para las posiciones normales, se genera un valor para la tabla de cifrado de código y después un segundo valor para la tabla de cifrado de datos. En la segunda pasada, para las posiciones marcadas en la tabla de cifrado de datos como «NO CIFRAR», sólo se genera un número, que se usa, como es lógico, en la tabla de cifrado de código. En pseudocódigo:
Con este algoritmo, una vez que tienes la semilla inicial, puedes regenerar las tablas de claves (téngase en cuenta que, para obtener los valores que están actualmente en las fuentes de MAME, habría que aplicar las permutaciones de que he hablado, que daré luego) siempre que sepas qué direcciones de la tabla de datos no deben cifrarse.
Bueno, llegado a este punto, me faltaba obtener las semillas iniciales para el resto de juegos, y completar las tablas de permutación incompletas. Dado que el primer juego cuya semilla inicial tenía correspondía a un FD1089B, era fácil atacar estos, a la vez que completaba la tabla de permutación que hacía corresponder la salida del generador con los valores arbitrarios de las tablas de datos para el FD1089B.
Hecho esto, ¿cómo conseguir eso mismo para el FD1089A? Por fortuna, hay algunos juegos que estaba claro que, a pesar de tener distintas revisiones del circuito, usaban la misma clave. Haciendo uso de ello, he sido capaz de reconstruir las tablas de permutacion correspondientes al FD1089A y, a la vez, obtener las semillas iniciales para todas las tablas que están en las fuentes de MAME actuales. No he observado errores en las tablas evidentes salvo para la «key_wb35», en la que los valores de la tabla de datos están aparentemente mal (sin embargo, los de la tabla de códigos si cuadran con lo previsto).
Las tablas de permutación que establecen la correspondencia entre la salida del GCL y los valores arbitrarios que Nicola usó son estas:
y las semillas iniciales éstas (se ve claramente que no se generaron aleatoriamente):
Visto en retrospectiva, y teniendo en cuenta el entrelazado de las dos tablas, parece que tuve bastante fortuna al encontrar un juego con una estructura de tablas tal que me permitiese aplicar el ataque. :)
En aquel momento no disponía de mucho tiempo pero ahora, tras haber concluido el trabajo con el SPC7110, creí que sería un buen momento de retomar el asunto.
Un primer vistazo mostraba que, para cada juego, teníamos 0x2000 octetos de clave divididos en 2 grupos de 0x1000 (uno es usado para encriptar los datos, y otro para el código). Una de las mayores dificultades del asunto era que, de hecho, debido a la forma en la que se habían recuperado esas tablas, la elección de los valores era arbitraria, y lo único que se podía garantizar era que existía una tabla fija de 256 entradas que establecía una permutación entre la salida del GNPA y los valores de las tablas. Además, observando las subtablas usada para encriptar el código, se podía ver con facilidad que uno de los 256 valores nunca estaba presente (esto ya se había visto hacer en otros circuitos: SEGA utilizaba un valor especial para marcar ciertas posiciones de las tablas de datos como «NO CIFRADO», por lo que ese valor tenía un significado especial y no podía usarse como un valor de cifrado normal).
Con todo eso, comencé a probar algunas ideas acerca de cómo operaban esas tablas de permutación (hablo en plural porque se sabía que para las dos revisiones del circuito eran distintas y para cada una de las dos subtablas de tamaño 0x1000 también) bajo la hipótesis de que, si pudiésemos estudiar las tablas de claves antes y después de aplicar esa «permutación arbitraria», se debería de observar un claro incremento en las estadísticas de aleatoriedad de las mismas. No obstante, esta línea de ataque no funcionó, pues quedó claro que los 0x1000 octetos de una sola tabla (o incluso todos los que se podían obtener para las tablas de cifrado de código para todos los juegos de una misma revisión del circuito) eran insuficientes para que esto pudiese funcionar.
Así que tocaba intentar otras cosas. Bajo la hipótesis de que el GNPA era un GCL del mismo tipo que el usado en el FD1094 y en el MC8123 (esto es, con módulo una potencia de 2), cabía intentar otro tipo de ataque directo: se sabe que, cuando el módulo usado por el GCL es una potencia de 2, cada uno de los bits de la salida generada muestra ciclos de tamaño 2^n, con n aumentando con el número de bit (esto es, si un bit muestra ciclos de tamaño 2^15, el siguiente mostrará ciclos de tamaño 2^16, y así por menudo...). De hecho, así es como Aaron se dio cuenta de que un GCL estaba siendo usado para generar (parte de) las claves usadas con el FD1094 (podéis leer sobre ello aquí: Notas de Aaron sobre el FD1094). Pero lo interesante para nosotros es que, si aislas uno de esos bits y observas el ciclo que desarrolla, puedes ver que ese ciclo se puede dividir en dos mitades de forma que una mitad es la imagen «especular» de la otra (léase: hay unos donde en la otra hay ceros, y viceversa).
Así pues, si la tabla fuese creada con bits generados por un GCL de este tipo, y tuviésemos la suerte de que en nuestros 0x1000 octetos al menos uno de los bits (el menos significativo) tuviese un ciclo de tamaño menor o igual que 0x1000, podríamos tratar de separar los 256 valores de la permutación en dos clases de equivalencia, de forma que un grupo de 128 valores estuviese asociado a uno de los dos valores posibles de ese bit, y el otro al valor restante. ¿Qué posibilidades de éxito tenía esta idea? Con la cantidad de datos disponibles, muy pocas en general para multiplicadores de GCL arbitrarios, pero me animaba el hecho de que el GCL usado por el FD1094 y el MC8123 tenía unos parámetros muy malos, que hacen que los ciclos que muestran sus bits sean menores que con parámetros óptimos. Así que, si tenía suerte y el GCL era el mismo, me bastaría que alguno de los 6 juegos para los que disponía de una tabla de cifrado de código completa tuviese una semilla inicial que fuese múltiplo de 4. Esto nos daría 6 intentos con una probabilidad de éxito del 25% cada uno; merecía la pena intentarlo.
Existía una dificultad añadida para llevar a cabo la prueba: dado que el GCL filtra uno de los 256 valores, las tablas tienen «huecos» que nos impiden emparejar de forma sencilla cada una de las dos mitades de ese ciclo. No obstante, cabía la esperanza de que el número de valores consecutivos necesarios en cada una de las dos partes del ciclo fuese bajo, lo que nos permitiría buscar 2 zonas libres de huecos que fuese «imágenes especulares» en la secuencia original. Unos cuantos experimentos después, quedó claro que esas dos zonas deberían ser de unos 256 octetos cada una para evitar la posibilidad de falsos positivos y falsos negativos. Un número mayor de lo que me hubiese gustado, pero no tan grande como para hacer inviable el ataque.
Así que, manos a la obra, implementé el ataque. Las simulaciones previas mostraban que, si el GCL era del mismo tipo que el usado en el FD1094 y el MC8123, efectivamente el ataque funcionaba si la semilla inicial era múltiplo de 4. Llegado el momento, lo comencé a aplicar sobre las tablas reales: como dije antes, tenía 6 intentos... falló el primero, el segundo, el tercero, el cuarto, el quinto y, cuando ya había perdido la fe, el sexto funcionó. ¡TOMA!
Un poco de análisis manual de los datos más tarde quedaba claro que había conseguido separar el conjunto de 256 valores en 8 clases de equivalencia de 32 valores cada una, lo que significaba que, si el GCL era el mismo que conocíamos, la semilla inicial era, de hecho, múltiplo de 16. Llegado a este punto, toda vez que ya era capaz de separar los 256 valores en 2 grupos de forma que cada uno correspondiese al valor de un cierto bit de la salida original del GCL, ya se podía intentar averiguar cuáles eran los parámetros del GCL. Fue bastante sencillo: quedó claro al poco que el generador subyacente era, como se sospechaba, exactamente el mismo usado por el FD1094 y el MC8123:
int rnd()
{
seed = seed*0x290029;
return (seed>>16)&0xff;
}
y, al mismo tiempo, fui capaz de recuperar la semilla inicial para el juego sobre el que el ataque anterior había funcionado (que era el 317-0168 para más detalles, el cual usa un FD1089B) y la tabla de permutación que establecía la correspondencia entre la salida del generador y los valores arbitrarios para las claves que Nicola había usado. Al hacerlo, también descubrí cuál era el valor del generador filtrado y me di cuenta de que la generación de las dos subtablas de claves parecía estar entrelazada de algún modo.
Tras algo más de estudio, quedó claro cómo funcionaba ese entrelazado... Como dije, hay algunas posiciones de la tabla de cifrado de datos que están marcadas como «NO CIFRAR» con ese número especial. Pues bien, la generación de las tablas se produce en dos pasadas: en la primera, para las posiciones normales, se genera un valor para la tabla de cifrado de código y después un segundo valor para la tabla de cifrado de datos. En la segunda pasada, para las posiciones marcadas en la tabla de cifrado de datos como «NO CIFRAR», sólo se genera un número, que se usa, como es lógico, en la tabla de cifrado de código. En pseudocódigo:
for (i=0; i<0x1000; i++)
{
if ("we must encrypt this data table position")
{
do
{
aux = rnd();
} while (aux==0x40);
opcode_table[i]=aux;
do
{
aux = rnd();
} while (aux==0x40);
data_table[i]=aux;
}
}
for (i=0; i<0x1000; i++)
{
if ("we mustn't encrypt this data table position")
{
do
{
aux = rnd();
} while (aux==0x40);
opcode_table[i]=aux;
data_table[i]=0x40;
}
}
Con este algoritmo, una vez que tienes la semilla inicial, puedes regenerar las tablas de claves (téngase en cuenta que, para obtener los valores que están actualmente en las fuentes de MAME, habría que aplicar las permutaciones de que he hablado, que daré luego) siempre que sepas qué direcciones de la tabla de datos no deben cifrarse.
Bueno, llegado a este punto, me faltaba obtener las semillas iniciales para el resto de juegos, y completar las tablas de permutación incompletas. Dado que el primer juego cuya semilla inicial tenía correspondía a un FD1089B, era fácil atacar estos, a la vez que completaba la tabla de permutación que hacía corresponder la salida del generador con los valores arbitrarios de las tablas de datos para el FD1089B.
Hecho esto, ¿cómo conseguir eso mismo para el FD1089A? Por fortuna, hay algunos juegos que estaba claro que, a pesar de tener distintas revisiones del circuito, usaban la misma clave. Haciendo uso de ello, he sido capaz de reconstruir las tablas de permutacion correspondientes al FD1089A y, a la vez, obtener las semillas iniciales para todas las tablas que están en las fuentes de MAME actuales. No he observado errores en las tablas evidentes salvo para la «key_wb35», en la que los valores de la tabla de datos están aparentemente mal (sin embargo, los de la tabla de códigos si cuadran con lo previsto).
Las tablas de permutación que establecen la correspondencia entre la salida del GCL y los valores arbitrarios que Nicola usó son estas:
int permutation_table_opcode_fd1089a[256] = {
0x8f,0x84,0x8d,0x86,0x4e,0x45,0x4c,0x47,0x9e,0x95,0x9c,0x97,0x5e,0x55,0x5c,0x57,
0x89,0x80,0x8b,0x82,0x48,0x41,0x4a,0x43,0x98,0x91,0x9a,0x93,0x58,0x51,0x5a,0x53,
0x9f,0x94,0x9d,0x96,0x5f,0x54,0x5d,0x56,0x8e,0x85,0x8c,0x87,0x4f,0x44,0x4d,0x46,
0x99,0x90,0x9b,0x92,0x59,0x50,0x5b,0x52,0x88,0x81,0x8a,0x83,0x49,0x40,0x4b,0x42,
0xef,0xe4,0xed,0xe6,0xee,0xe5,0xec,0xe7,0xf8,0xf1,0xfa,0xf3,0xf9,0xf0,0xfb,0xf2,
0x1f,0x14,0x1d,0x16,0x1e,0x15,0x1c,0x17,0x09,0x02,0x0b,0x00,0x08,0x03,0x0a,0x01,
0xfe,0xf5,0xfc,0xf7,0xff,0xf4,0xfd,0xf6,0xe9,0xe0,0xeb,0xe2,0xe8,0xe1,0xea,0xe3,
0x0f,0x04,0x0d,0x06,0x0e,0x05,0x0c,0x07,0x19,0x12,0x1b,0x10,0x18,0x13,0x1a,0x11,
0xcf,0xc4,0xcd,0xc6,0xce,0xc5,0xcc,0xc7,0xd9,0xd2,0xdb,0xd0,0xd8,0xd3,0xda,0xd1,
0x2e,0x25,0x2c,0x27,0x2f,0x24,0x2d,0x26,0x38,0x31,0x3a,0x33,0x39,0x30,0x3b,0x32,
0xdf,0xd4,0xdd,0xd6,0xde,0xd5,0xdc,0xd7,0xc9,0xc2,0xcb,0xc0,0xc8,0xc3,0xca,0xc1,
0x3e,0x35,0x3c,0x37,0x3f,0x34,0x3d,0x36,0x28,0x21,0x2a,0x23,0x29,0x20,0x2b,0x22,
0x7e,0x75,0x7c,0x77,0xaf,0xa4,0xad,0xa6,0x6f,0x64,0x6d,0x66,0xbf,0xb4,0xbd,0xb6,
0x78,0x73,0x7a,0x71,0xa9,0xa2,0xab,0xa0,0x69,0x62,0x6b,0x60,0xb9,0xb2,0xbb,0xb0,
0x6e,0x65,0x6c,0x67,0xbe,0xb5,0xbc,0xb7,0x7f,0x74,0x7d,0x76,0xae,0xa5,0xac,0xa7,
0x68,0x63,0x6a,0x61,0xb8,0xb3,0xba,0xb1,0x79,0x72,0x7b,0x70,0xa8,0xa3,0xaa,0xa1,
};
int permutation_table_data_fd1089a[256] = {
0xd5,0x60,0xc5,0x70,0xd7,0x62,0xc7,0x72,0xc4,0x74,0xd4,0x64,0xc6,0x76,0xd6,0x66,
0x34,0xb2,0x24,0xa3,0x36,0xb0,0x26,0xa1,0x25,0xa5,0x35,0xb4,0x27,0xa7,0x37,0xb6,
0xd3,0x93,0xc3,0x83,0xd1,0x91,0xc1,0x81,0xc2,0x85,0xd2,0x95,0xc0,0x87,0xd0,0x97,
0x30,0x51,0x20,0x40,0x32,0x53,0x22,0x42,0x21,0x44,0x31,0x55,0x23,0x46,0x33,0x57,
0xff,0x68,0xee,0x78,0xfd,0x6a,0xec,0x7a,0xef,0x7e,0xfe,0x6e,0xed,0x7c,0xfc,0x6c,
0x0e,0xb8,0x1e,0xa9,0x0c,0xba,0x1c,0xab,0x1f,0xaf,0x0f,0xbe,0x1d,0xad,0x0d,0xbc,
0xf9,0x99,0xe8,0x89,0xfb,0x9b,0xea,0x8b,0xe9,0x8f,0xf8,0x9f,0xeb,0x8d,0xfa,0x9d,
0x08,0x59,0x18,0x48,0x0a,0x5b,0x1a,0x4a,0x19,0x4e,0x09,0x5f,0x1b,0x4c,0x0b,0x5d,
0xde,0x69,0xce,0x79,0xdc,0x6b,0xcc,0x7b,0xcf,0x7f,0xdf,0x6f,0xcd,0x7d,0xdd,0x6d,
0x3f,0xb9,0x2f,0xa8,0x3d,0xbb,0x2d,0xaa,0x2e,0xae,0x3e,0xbf,0x2c,0xac,0x3c,0xbd,
0xd8,0x98,0xc8,0x88,0xda,0x9a,0xca,0x8a,0xc9,0x8e,0xd9,0x9e,0xcb,0x8c,0xdb,0x9c,
0x39,0x58,0x29,0x49,0x3b,0x5a,0x2b,0x4b,0x28,0x4f,0x38,0x5e,0x2a,0x4d,0x3a,0x5c,
0xf4,0x61,0xe5,0x71,0xf6,0x63,0xe7,0x73,0xe4,0x75,0xf5,0x65,0xe6,0x77,0xf7,0x67,
0x05,0xb3,0x15,0xa2,0x07,0xb1,0x17,0xa0,0x14,0xa4,0x04,0xb5,0x16,0xa6,0x06,0xb7,
0xf2,0x92,0xe3,0x82,0xf0,0x90,0xe1,0x80,0xe2,0x84,0xf3,0x94,0xe0,0x86,0xf1,0x96,
0x01,0x50,0x11,0x41,0x03,0x52,0x13,0x43,0x10,0x45,0x00,0x54,0x12,0x47,0x02,0x56,
};
int permutation_table_opcode_fd1089b[256] = {
0x8f,0x84,0x8d,0x86,0x4e,0x45,0x4c,0x47,0x9e,0x95,0x9c,0x97,0x5e,0x55,0x5c,0x57,
0x89,0x82,0x8b,0x80,0x48,0x43,0x4a,0x41,0x98,0x93,0x9a,0x91,0x58,0x53,0x5a,0x51,
0x9f,0x94,0x9d,0x96,0x5f,0x54,0x5d,0x56,0x8e,0x85,0x8c,0x87,0x4f,0x44,0x4d,0x46,
0x99,0x92,0x9b,0x90,0x59,0x52,0x5b,0x50,0x88,0x83,0x8a,0x81,0x49,0x42,0x4b,0x40,
0xef,0xe4,0xed,0xe6,0xee,0xe5,0xec,0xe7,0xf8,0xf3,0xfa,0xf1,0xf9,0xf2,0xfb,0xf0,
0x1f,0x14,0x1d,0x16,0x1e,0x15,0x1c,0x17,0x09,0x02,0x0b,0x00,0x08,0x03,0x0a,0x01,
0xfe,0xf5,0xfc,0xf7,0xff,0xf4,0xfd,0xf6,0xe9,0xe2,0xeb,0xe0,0xe8,0xe3,0xea,0xe1,
0x0f,0x04,0x0d,0x06,0x0e,0x05,0x0c,0x07,0x19,0x12,0x1b,0x10,0x18,0x13,0x1a,0x11,
0xcf,0xc4,0xcd,0xc6,0xce,0xc5,0xcc,0xc7,0xd9,0xd2,0xdb,0xd0,0xd8,0xd3,0xda,0xd1,
0x2e,0x25,0x2c,0x27,0x2f,0x24,0x2d,0x26,0x38,0x33,0x3a,0x31,0x39,0x32,0x3b,0x30,
0xdf,0xd4,0xdd,0xd6,0xde,0xd5,0xdc,0xd7,0xc9,0xc2,0xcb,0xc0,0xc8,0xc3,0xca,0xc1,
0x3e,0x35,0x3c,0x37,0x3f,0x34,0x3d,0x36,0x28,0x23,0x2a,0x21,0x29,0x22,0x2b,0x20,
0x7e,0x75,0x7c,0x77,0xaf,0xa4,0xad,0xa6,0x6f,0x64,0x6d,0x66,0xbf,0xb4,0xbd,0xb6,
0x78,0x73,0x7a,0x71,0xa9,0xa2,0xab,0xa0,0x69,0x62,0x6b,0x60,0xb9,0xb2,0xbb,0xb0,
0x6e,0x65,0x6c,0x67,0xbe,0xb5,0xbc,0xb7,0x7f,0x74,0x7d,0x76,0xae,0xa5,0xac,0xa7,
0x68,0x63,0x6a,0x61,0xb8,0xb3,0xba,0xb1,0x79,0x72,0x7b,0x70,0xa8,0xa3,0xaa,0xa1,
};
int permutation_table_data_fd1089b[256] = {
0xd5,0x62,0xc5,0x72,0xd7,0x60,0xc7,0x70,0xc4,0x74,0xd4,0x64,0xc6,0x76,0xd6,0x66,
0x34,0xb2,0x24,0xa3,0x36,0xb0,0x26,0xa1,0x25,0xa5,0x35,0xb4,0x27,0xa7,0x37,0xb6,
0xd3,0x93,0xc3,0x83,0xd1,0x91,0xc1,0x81,0xc2,0x85,0xd2,0x95,0xc0,0x87,0xd0,0x97,
0x32,0x53,0x22,0x42,0x30,0x51,0x20,0x40,0x23,0x44,0x33,0x55,0x21,0x46,0x31,0x57,
0xff,0x68,0xee,0x78,0xfd,0x6a,0xec,0x7a,0xef,0x7e,0xfe,0x6e,0xed,0x7c,0xfc,0x6c,
0x0e,0xb8,0x1e,0xa9,0x0c,0xba,0x1c,0xab,0x1f,0xaf,0x0f,0xbe,0x1d,0xad,0x0d,0xbc,
0xf9,0x99,0xe8,0x89,0xfb,0x9b,0xea,0x8b,0xe9,0x8f,0xf8,0x9f,0xeb,0x8d,0xfa,0x9d,
0x08,0x59,0x18,0x48,0x0a,0x5b,0x1a,0x4a,0x19,0x4e,0x09,0x5f,0x1b,0x4c,0x0b,0x5d,
0xde,0x69,0xce,0x79,0xdc,0x6b,0xcc,0x7b,0xcf,0x7f,0xdf,0x6f,0xcd,0x7d,0xdd,0x6d,
0x3f,0xb9,0x2f,0xa8,0x3d,0xbb,0x2d,0xaa,0x2e,0xae,0x3e,0xbf,0x2c,0xac,0x3c,0xbd,
0xd8,0x98,0xc8,0x88,0xda,0x9a,0xca,0x8a,0xc9,0x8e,0xd9,0x9e,0xcb,0x8c,0xdb,0x9c,
0x39,0x58,0x29,0x49,0x3b,0x5a,0x2b,0x4b,0x28,0x4f,0x38,0x5e,0x2a,0x4d,0x3a,0x5c,
0xf4,0x63,0xe5,0x73,0xf6,0x61,0xe7,0x71,0xe4,0x75,0xf5,0x65,0xe6,0x77,0xf7,0x67,
0x05,0xb3,0x15,0xa2,0x07,0xb1,0x17,0xa0,0x14,0xa4,0x04,0xb5,0x16,0xa6,0x06,0xb7,
0xf2,0x92,0xe3,0x82,0xf0,0x90,0xe1,0x80,0xe2,0x84,0xf3,0x94,0xe0,0x86,0xf1,0x96,
0x03,0x52,0x13,0x43,0x01,0x50,0x11,0x41,0x12,0x45,0x02,0x54,0x10,0x47,0x00,0x56,
};
y las semillas iniciales éstas (se ve claramente que no se generaron aleatoriamente):
// FD1089B games
{key_0013A,0x400001},
{key_0168, 0x400030},
{key_0034, 0x400015},
{key_0024, 0x40000f},
{key_0027, 0x400011},
{key_0037, 0x400013},
{key_5021, 0x40004b},
// FD1089A games
{key_0018, 0x400003},
{key_0022, 0x40000d},
{key_0033, 0x400013},
{key_0028, 0x400011},
{key_0167, 0x400030},
{key_0021, 0x40000b},
{key_wb35, 0x400043},
Visto en retrospectiva, y teniendo en cuenta el entrelazado de las dos tablas, parece que tuve bastante fortuna al encontrar un juego con una estructura de tablas tal que me permitiese aplicar el ataque. :)
Etiquetas: emulación
viernes, 11 de julio de 2008
SPC7110
El algoritmo de descompresión del SPC7110 está a punto de ser completamente entendido. Los raritos a los que os gusta leer sobre cómo se consiguen estas cosas, podéis seguir los detalles aquí:
Hilo en nesdev sobre el SPC7110
Hilo en nesdev sobre el SPC7110
Etiquetas: emulación
martes, 12 de febrero de 2008
Jubatu 0.1.0. Instalación.
Bien, lo primero es lo primero... podéis coger las fuentes de Jubatu de aquí, y las del módulo de ajedrez de aquí.
Y ahora, ¿cómo instalarlo? Bien, vayamos por partes; antes de poder instalarlo, habéis de instalar las tres grandes librerías en que Jubatu se apoya (wxpython, pyxmpp y panda3d). Para ello, si sois los afortunados usuarios de un sistema operativo que implemente algún sistema de descarga e instalación de programas libres (tipo apt-get), os aconsejaría que fueseis allí en primer lugar para ver si os podéis ahorrar el tostón de instalarlos a mano. Para los que no puedan, describiré a continuación dos métodos: el de instalación directa de binarios (sólo para usuarios de Windows) y el manual (para los demás).
Empecemos por el método "manual" (tenéis esta información en el README de la distribución de fuentes):
1º) Os vais a http://panda3d.org/download.php , descargáis panda3d y os lo instaláis.
2º) En http://www.wxpython.org/download.php hacéis lo mismo con wxpython.
3º) Para hacer lo mismo con pyxmpp, primero deberéis instalar sus dependencias:
Y ya debería estar todo...
PARA USUARIOS DE WINDOWS:
Si queréis ahorraros todo el follón de la instalación manual, podéis hacer lo siguiente:
He preparado un fichero zip con todos los auto-instalables necesarios para instalarlo en Windows (yo lo he probado en Windows XP). Podéis descargarlo de aquí:
jubatu_with_dependencies_for_win32.zip
(Nota: parece que massmirror ha cortado el nombre del fichero por ser éste muy largo; no debería de ser un problema.)
Cuando lo tengáis, lo descomprimís y, del directorio "bin" vais ejecutando los autoextraíbles en este orden:
1º) El de panda3d. Al instalaros panda3d, también se os instala una distribución de python contenida dentro de la de panda3d. Esa es la versión de python que deberéis usar al instalar el resto de las librerías (esto sólo es importante para aquellos que ya tengan otra versión de python instalada con anterioridad; si ese fuera el caso, al ejecutar los otros autoextraíbles, os dará a elegir entre las que tengáis.)
2º) El de wxpython.
3º) El de libxml2.
4º) El de dnspython.
5º) El de pyxmpp.
6º) El de jubatu.
7º) El de jubatu-chess.
Todos los pasos son bastante sencillos; al terminar, deberías tener un acceso directo a Jubatu en el escritorio y una opción en "menú inicio/programas".
Si tenéis problemas o hacen falta aclaraciones adicionales, hacédmelo saber. Tened en cuenta que ésta es la primera versión que ve la luz, por lo que es seguro que habrá cosas por pulir. Sed benévolos. :)
EDITADO: Por cierto, todos aquellos que lo probéis y queráis darme vuestra opinión en vivo o incluso jugar alguna partida si se tercia, sentíos libres de añadir a vuestros contactos esta cuenta mía: andreasnaive@jabberes.org Como dije, Jubatu no soporta el envío de mensajes por ahora, por lo que para hablar deberéis usar algún otro programa Jabber/XMPP.
Y ahora, ¿cómo instalarlo? Bien, vayamos por partes; antes de poder instalarlo, habéis de instalar las tres grandes librerías en que Jubatu se apoya (wxpython, pyxmpp y panda3d). Para ello, si sois los afortunados usuarios de un sistema operativo que implemente algún sistema de descarga e instalación de programas libres (tipo apt-get), os aconsejaría que fueseis allí en primer lugar para ver si os podéis ahorrar el tostón de instalarlos a mano. Para los que no puedan, describiré a continuación dos métodos: el de instalación directa de binarios (sólo para usuarios de Windows) y el manual (para los demás).
Empecemos por el método "manual" (tenéis esta información en el README de la distribución de fuentes):
1º) Os vais a http://panda3d.org/download.php , descargáis panda3d y os lo instaláis.
2º) En http://www.wxpython.org/download.php hacéis lo mismo con wxpython.
3º) Para hacer lo mismo con pyxmpp, primero deberéis instalar sus dependencias:
- En http://xmlsoft.org/downloads.html conseguís libxml2 y lo instaláis (quizá también necesitéis coger iconv de http://www.gnu.org/software/libiconv/#downloading)
- En http://www.dnspython.org/ conseguís dnspython y lo instaláis.
- Finalmente, en http://pyxmpp.jajcus.net/ descargáis pyxmpp y lo instaláis.
- Descomprimís los fuentes en un directorio.
- Abrís una consola y os situáis en ese directorio.
- Tecleáis "python setup.py install".
Y ya debería estar todo...
PARA USUARIOS DE WINDOWS:
Si queréis ahorraros todo el follón de la instalación manual, podéis hacer lo siguiente:
He preparado un fichero zip con todos los auto-instalables necesarios para instalarlo en Windows (yo lo he probado en Windows XP). Podéis descargarlo de aquí:
jubatu_with_dependencies_for_win32.zip
(Nota: parece que massmirror ha cortado el nombre del fichero por ser éste muy largo; no debería de ser un problema.)
Cuando lo tengáis, lo descomprimís y, del directorio "bin" vais ejecutando los autoextraíbles en este orden:
1º) El de panda3d. Al instalaros panda3d, también se os instala una distribución de python contenida dentro de la de panda3d. Esa es la versión de python que deberéis usar al instalar el resto de las librerías (esto sólo es importante para aquellos que ya tengan otra versión de python instalada con anterioridad; si ese fuera el caso, al ejecutar los otros autoextraíbles, os dará a elegir entre las que tengáis.)
2º) El de wxpython.
3º) El de libxml2.
4º) El de dnspython.
5º) El de pyxmpp.
6º) El de jubatu.
7º) El de jubatu-chess.
Todos los pasos son bastante sencillos; al terminar, deberías tener un acceso directo a Jubatu en el escritorio y una opción en "menú inicio/programas".
Si tenéis problemas o hacen falta aclaraciones adicionales, hacédmelo saber. Tened en cuenta que ésta es la primera versión que ve la luz, por lo que es seguro que habrá cosas por pulir. Sed benévolos. :)
EDITADO: Por cierto, todos aquellos que lo probéis y queráis darme vuestra opinión en vivo o incluso jugar alguna partida si se tercia, sentíos libres de añadir a vuestros contactos esta cuenta mía: andreasnaive@jabberes.org Como dije, Jubatu no soporta el envío de mensajes por ahora, por lo que para hablar deberéis usar algún otro programa Jabber/XMPP.
Jubatu. Ejemplo sencillo de uso.
Ya hay una primera versión de Jubatu lista para distribución. Para que podáis ver el funcionamiento básico, aquí os pongo un ejemplo con imágenes, no sin antes decir que he tratado de que sea relativamente intuitivo, por lo que supongo que podríais simplemente trastear directamente con él para aprender a usarlo.
De partida, dispongo de dos cuentas Jabber/XMPP que me he creado en dos servidores distintos (podéis ver la información en las imágenes); además, he hecho que cada una de las dos cuentas figure en la lista de amigos de la otra (esto no se puede hacer con Jubatu; podéis hacerlo con cualquier otra aplicación XMPP como kopete, pidgin/gaim, gajim, etc).
Desde un portátil con Kubuntu 7.04 arranco Jubatu:
Como podéis ver, éste está configurado en inglés; el idioma puede cambiarse en la opción de menú "Language" (sólo español e inglés por ahora).
En el menú "Jubatu", seleccionamos la opción de inicio de sesión, lo que nos despliega la correspondiente pestaña, y rellenamos los datos con la primera cuenta:
Una vez que pulsamos el botón de inicio de sesión, nos conectamos:
El icono de la esquina superior derecha indica nuestra disponibilidad (gris=desconectado; verde=conectado; rojo=no molestar; amarillo=ausente. Se puede cambiar la disponibilidad propia desde el menú "Jubatu") y se puede ver que en la ventana de la derecha ha aparecido nuestro contacto (la segunda cuenta). De nuevo, un código de colores nos indica el estado de nuestros contactos; podemos ver que nuestro amigo está desconectado (gris); en esa ventana también podría aparecer la propia cuenta desde la que nos conectamos si estuviésemos múltiples conexiones con programas distintos.
Ahora, desde un segundo ordenador con Windows XP, el segundo usuario hace lo propio para conectarse (éste tiene Jubatu configurado en español):
Una vez que pulse el botón de inicio de sesión, ambos usuarios verás en sus respectivas pantallas como el estado del otro cambia a "verde" (conectado). En realidad, hay dos pequeños iconos juntos: el primero indica la disponibilidad en la red Jabber/XMPP; el segundo, si se dispone de la misma versión del juego que esté seleccionado en ese momento.
A continuación, el primer usuario, que quiere echar una partida de ajedrez con su amigo, hace una doble pulsación sobre el juego en el panel de la izquierda y, una vez que se despliega el panel correspondiente (ver imagen abajo), hace lo siguiente para invitar al segundo usuario: Primero pincha con el ratón en el campo "oponente" del panel recién desplegado y, a continuación, hace una doble pulsación sobre el recurso con el que su amigo está conectado en el panel de la derecha (en el ejemplo, en la línea llamada "jubatu" debajo del nombre de la cuenta del segundo usuario):
Ahora, una vez que se pulse el botón de enviar invitación, al segundo usuario se le muestra un mensaje como éste:
Una vez que el segundo usuario acepta la invitación, a cada uno de ellos se le despliega una ventana independiente con el tablero de ajedrez. Esto es lo que ve el primer usuario:
... y esto lo que ve el segundo:
Después de dos tristes jugadas, la partida de ejemplo termina; esto es lo que ve el primer usuario:
... y esto lo que ve el segundo:
Espero que haya quedado más o menos claro... de todos modos, insisto en que deberías ser capaces de entender cómo funciona todo con sólo trastear un poco con el programa. Si necesitáis algo más de información sobre qué son y cómo se utilizan las cuentas Jabber/XMPP, podéis leer algo de lo que cuentan en jabberes.org, que lo tienen bien explicado.
En la siguiente nota daré instrucciones para descargar e instalar el programa y el módulo de ajedrez.
De partida, dispongo de dos cuentas Jabber/XMPP que me he creado en dos servidores distintos (podéis ver la información en las imágenes); además, he hecho que cada una de las dos cuentas figure en la lista de amigos de la otra (esto no se puede hacer con Jubatu; podéis hacerlo con cualquier otra aplicación XMPP como kopete, pidgin/gaim, gajim, etc).
Desde un portátil con Kubuntu 7.04 arranco Jubatu:
Como podéis ver, éste está configurado en inglés; el idioma puede cambiarse en la opción de menú "Language" (sólo español e inglés por ahora).
En el menú "Jubatu", seleccionamos la opción de inicio de sesión, lo que nos despliega la correspondiente pestaña, y rellenamos los datos con la primera cuenta:
Una vez que pulsamos el botón de inicio de sesión, nos conectamos:
El icono de la esquina superior derecha indica nuestra disponibilidad (gris=desconectado; verde=conectado; rojo=no molestar; amarillo=ausente. Se puede cambiar la disponibilidad propia desde el menú "Jubatu") y se puede ver que en la ventana de la derecha ha aparecido nuestro contacto (la segunda cuenta). De nuevo, un código de colores nos indica el estado de nuestros contactos; podemos ver que nuestro amigo está desconectado (gris); en esa ventana también podría aparecer la propia cuenta desde la que nos conectamos si estuviésemos múltiples conexiones con programas distintos.
Ahora, desde un segundo ordenador con Windows XP, el segundo usuario hace lo propio para conectarse (éste tiene Jubatu configurado en español):
Una vez que pulse el botón de inicio de sesión, ambos usuarios verás en sus respectivas pantallas como el estado del otro cambia a "verde" (conectado). En realidad, hay dos pequeños iconos juntos: el primero indica la disponibilidad en la red Jabber/XMPP; el segundo, si se dispone de la misma versión del juego que esté seleccionado en ese momento.
A continuación, el primer usuario, que quiere echar una partida de ajedrez con su amigo, hace una doble pulsación sobre el juego en el panel de la izquierda y, una vez que se despliega el panel correspondiente (ver imagen abajo), hace lo siguiente para invitar al segundo usuario: Primero pincha con el ratón en el campo "oponente" del panel recién desplegado y, a continuación, hace una doble pulsación sobre el recurso con el que su amigo está conectado en el panel de la derecha (en el ejemplo, en la línea llamada "jubatu" debajo del nombre de la cuenta del segundo usuario):
Ahora, una vez que se pulse el botón de enviar invitación, al segundo usuario se le muestra un mensaje como éste:
Una vez que el segundo usuario acepta la invitación, a cada uno de ellos se le despliega una ventana independiente con el tablero de ajedrez. Esto es lo que ve el primer usuario:
... y esto lo que ve el segundo:
Después de dos tristes jugadas, la partida de ejemplo termina; esto es lo que ve el primer usuario:
... y esto lo que ve el segundo:
Espero que haya quedado más o menos claro... de todos modos, insisto en que deberías ser capaces de entender cómo funciona todo con sólo trastear un poco con el programa. Si necesitáis algo más de información sobre qué son y cómo se utilizan las cuentas Jabber/XMPP, podéis leer algo de lo que cuentan en jabberes.org, que lo tienen bien explicado.
En la siguiente nota daré instrucciones para descargar e instalar el programa y el módulo de ajedrez.
miércoles, 6 de febrero de 2008
Gaelco. RAM de vídeo. (II)
Aquí está el fichero correspondiente a las funciones inversas (ver nota anterior).
Etiquetas: emulación
viernes, 1 de febrero de 2008
Gaelco. RAM de vídeo. (I)
Haré la historia corta:
Gaelco ha usado varios tipos de protección en sus máquinas; uno de ellos fue usar un cierto cifrado en la RAM de vídeo de algunos de sus juegos. Actualmente, y desde hace tiempo, MAME simula el descifrado para dos de ellos. Digo simula y no emula porque, cuando uno mira las fuentes, le es claro que el algoritmo, contrariamente a lo que muchos creen, aún no ha sido comprendido; lo que ocurre es que el cifrado usado es lo suficientemente malo como para haber permitido «comprimir» el cifrado en una cantidad de código razonable (según me ha llegado a mí la historia, fue Nicola quien se encargó de efectuar tal compresión).
Ni que decir tiene, tal situación no le es grata a nadie, así que sería buena cosa poder comprender el algoritmo (para, además de simplificar el código existente, permitir ampliar la emulación a otros juegos con la mismo cifrado sin que el código se vuelva inmanejable). Debo dejar claro que yo no he tenido acceso a las tablas completas con que trabajó Nicola pero, dado que el código actual de MAME supuestamente reproduce exactamente el contenido de las tablas, no debería haber problema en utilizarlo como referencia.
Visto el galimatías existente, cuando intenté echarle un ojo al final del verano pasado lo que hice fue encapsular el código de MAME para, inicialmente, estudiar el algoritmo como una caja negra (mi intención era no adquirir prejuicios sobre cómo funcionaba el algoritmo al ver la implementación actual); quedó claro desde el principio que el algoritmo era criptográficamente malo, y no tardé en ver las características que hicieron implementar a Nicola el algoritmo como está ahora: el algoritmo, que se aplica sobre datos de entrada de 32 bits, opera en dos pasos: primero sobre los 16 primeros bits (parte alta) y después parece utilizar el resultado obtenido para descifrar los 16 últimos bits (parte baja); observé también las 4 pseudo-permutaciones que se aplicaban al segundo trozo en función de dos bits del resultado obtenido con el primero, noté la existencia de acarreos en algunos de los bits. Total, que, llegado a ese punto, tenía información suficiente como para haber comprimido el algoritmo yo mismo como hizo Nicola, pero nada más que eso.
Hice algunos experimentos (muchos, de hecho) intentando catalogar el algoritmo (por ejemplo, parecía razonable que algún tipo de matriz lineal pudiese estar implicada, por los acarreos), pero el cabrón resistió, pese a lo simple que parecía; puse a prueba varios esquemas simples que me parecía que podían encajar e intenté buscar grupos de operaciones que pudiesen explicar algunos datos derivados que me parecían interesantes. Nada, no hubo manera.
Así que, cambiando de idea, me puse a reconstruir las funciones exactas que ligan cada uno de los bits de salida con los bits de entrada. Por ejemplo, para los 16 primeros bits (que sólo dependen de 16 bits de entrada), obtuve cosas como ésta:
Este formato requiere una explicación: cada uno de los números representa un monomio en el que aparecen todos aquellos bits de entrada correspondientes a posiciones puestas a 1; por ejemplo: si denotamos por i0,i1,...,i15 los bits de entrada, 0x4061 representaría al monomio i1*i5*i6*i14. La expresión completa correspondiente a ese bit de salida, por tanto, sería la suma de todos esos monomios.
Expresado de esta manera, era más fácil ver ciertas dependencias, como el efecto de los acarreos; de nuevo, a pesar de que esto me sugirió algunas pruebas más, no fui capaz de sacar nada firme. Uno de los problemas que me impedían sacar algo más de jugo del asunto es que algunos de los bits tienen expresiones tan simples que no puedes estar seguro de si realmente existe una cierta relación que supones o si se debe simplemente al azar. Lo ideal para poder contrastar esas hipótesis hubiese sido disponer de esas expresiones para una buena cantidad de juegos... pero sólo las teníamos para dos.
Mal asunto; me convencí de que pretender hacer retroingeniería mirando los 16 primeros bits no sería posible con sólo dos juegos, así que únicamente quedaban dos opciones: o dejarlo estar, buscando si acaso una forma más estructurada de implementar el algoritmo, o tratar de obtener esas expresiones para el segundo bloque de 16 bits de salida; eso sonaba laborioso y, dado que yo ya empezaba a estar un poco quemado después de tantos meses trabajando en problemas de cifrado, le di una patada a todo y me dediqué a otras cosas, en espera de que me volviese a picar el gusanillo.
Bueno, pues finalmente le he dedicado un poco de tiempo en las últimas dos semanas; como resultado de ello, ya dispongo de las expresiones para esos últimos 16 bits de salida. En el proceso, he obtenido información interesante: para empezar, ha quedado claro que se utiliza la misma función para los dos bloques de 16 bits (lo que todos suponíamos) y que la función tiene 32 bits de entrada y 16 de salida; en concreto, lo que ocurre es esto: Si la función es C=F(A,B), con A, B y C parámetros de 16 bits, el descifrado opera del siguiente modo:
Si el dato a descifrar es E1E2 y el dato plano es D1D2 (escribo los bits más altos primero), se tiene que
D1 = F(0, E1)
D2 = F(D1, E2)
Así pues, la única dependencia de D2 con respecto a E1 se tiene a través de D1, lo que no estaba del todo claro hasta ahora. Además, se ha visto que la «semilla» inicial es exactamente 0.
Es mi esperanza que estas expresiones nos permitan investigar el algoritmo con más facilidad; aquí tenéis un fichero con las mismas. Los números de los juegos son los mismos que tienen en MAME; el número de monomios que contiene la expresión de cada bit de salida oscila entre 2^4 y algo más de 2^14 pero, en todo caso, está muy lejos de los 2^31 que deberían esperarse para un buen algoritmo de cifrado con 32 bits de entrada (gracias a ello podemos permitirnos manejar tales expresiones, claro). De cualquier modo, no trataré de investigar nada hasta no tener las funciones inversas, quiero decir, las funciones G(A,B) tales que, fijado un A arbitrario, F(A,G(A,X))=G(A,F(A,X))=X para toda X. Esto debería de ocurrir la semana que viene; ya haré públicos los datos cuando los tenga.
Gaelco ha usado varios tipos de protección en sus máquinas; uno de ellos fue usar un cierto cifrado en la RAM de vídeo de algunos de sus juegos. Actualmente, y desde hace tiempo, MAME simula el descifrado para dos de ellos. Digo simula y no emula porque, cuando uno mira las fuentes, le es claro que el algoritmo, contrariamente a lo que muchos creen, aún no ha sido comprendido; lo que ocurre es que el cifrado usado es lo suficientemente malo como para haber permitido «comprimir» el cifrado en una cantidad de código razonable (según me ha llegado a mí la historia, fue Nicola quien se encargó de efectuar tal compresión).
Ni que decir tiene, tal situación no le es grata a nadie, así que sería buena cosa poder comprender el algoritmo (para, además de simplificar el código existente, permitir ampliar la emulación a otros juegos con la mismo cifrado sin que el código se vuelva inmanejable). Debo dejar claro que yo no he tenido acceso a las tablas completas con que trabajó Nicola pero, dado que el código actual de MAME supuestamente reproduce exactamente el contenido de las tablas, no debería haber problema en utilizarlo como referencia.
Visto el galimatías existente, cuando intenté echarle un ojo al final del verano pasado lo que hice fue encapsular el código de MAME para, inicialmente, estudiar el algoritmo como una caja negra (mi intención era no adquirir prejuicios sobre cómo funcionaba el algoritmo al ver la implementación actual); quedó claro desde el principio que el algoritmo era criptográficamente malo, y no tardé en ver las características que hicieron implementar a Nicola el algoritmo como está ahora: el algoritmo, que se aplica sobre datos de entrada de 32 bits, opera en dos pasos: primero sobre los 16 primeros bits (parte alta) y después parece utilizar el resultado obtenido para descifrar los 16 últimos bits (parte baja); observé también las 4 pseudo-permutaciones que se aplicaban al segundo trozo en función de dos bits del resultado obtenido con el primero, noté la existencia de acarreos en algunos de los bits. Total, que, llegado a ese punto, tenía información suficiente como para haber comprimido el algoritmo yo mismo como hizo Nicola, pero nada más que eso.
Hice algunos experimentos (muchos, de hecho) intentando catalogar el algoritmo (por ejemplo, parecía razonable que algún tipo de matriz lineal pudiese estar implicada, por los acarreos), pero el cabrón resistió, pese a lo simple que parecía; puse a prueba varios esquemas simples que me parecía que podían encajar e intenté buscar grupos de operaciones que pudiesen explicar algunos datos derivados que me parecían interesantes. Nada, no hubo manera.
Así que, cambiando de idea, me puse a reconstruir las funciones exactas que ligan cada uno de los bits de salida con los bits de entrada. Por ejemplo, para los 16 primeros bits (que sólo dependen de 16 bits de entrada), obtuve cosas como ésta:
int bit0_game0 = {
0x0002, 0x0004, 0x0005, 0x0008, 0x0009, 0x000c, 0x0024, 0x0025,
0x0029, 0x0041, 0x0044, 0x0060, 0x0061, 0x0064, 0x0601, 0x0604,
0x0621, 0x0624, 0x0640, 0x0641, 0x0644, 0x0660, 0x0661, 0x0664,
0x0824, 0x0860, 0x0864, 0x0e01, 0x0e04, 0x0e21, 0x0e24, 0x0e40,
0x0e41, 0x0e44, 0x0e60, 0x0e61, 0x0e64, 0x1004, 0x1005, 0x1008,
0x1009, 0x1024, 0x1025, 0x1028, 0x1029, 0x1040, 0x1041, 0x1060,
0x1061, 0x1204, 0x1205, 0x1208, 0x1209, 0x1224, 0x1225, 0x1228,
0x1229, 0x1240, 0x1241, 0x1260, 0x1261, 0x4004, 0x4005, 0x4008,
0x4009, 0x4024, 0x4025, 0x4028, 0x4029, 0x4040, 0x4041, 0x4060,
0x4061, 0x4604, 0x4605, 0x4608, 0x4609, 0x4621, 0x4624, 0x4628,
0x4640, 0x4641, 0x4660, 0x4661, 0x4e21, 0x4e61, 0x5004, 0x5005,
0x5008, 0x5009, 0x5021, 0x5024, 0x5028, 0x5040, 0x5041, 0x5060,
0x5061, 0x5204, 0x5205, 0x5208, 0x5209, 0x5221, 0x5224, 0x5228,
0x5240, 0x5241, 0x5260, 0x5261, 0x5821, 0x5861, 0x5a21, 0x5a61,
};
Este formato requiere una explicación: cada uno de los números representa un monomio en el que aparecen todos aquellos bits de entrada correspondientes a posiciones puestas a 1; por ejemplo: si denotamos por i0,i1,...,i15 los bits de entrada, 0x4061 representaría al monomio i1*i5*i6*i14. La expresión completa correspondiente a ese bit de salida, por tanto, sería la suma de todos esos monomios.
Expresado de esta manera, era más fácil ver ciertas dependencias, como el efecto de los acarreos; de nuevo, a pesar de que esto me sugirió algunas pruebas más, no fui capaz de sacar nada firme. Uno de los problemas que me impedían sacar algo más de jugo del asunto es que algunos de los bits tienen expresiones tan simples que no puedes estar seguro de si realmente existe una cierta relación que supones o si se debe simplemente al azar. Lo ideal para poder contrastar esas hipótesis hubiese sido disponer de esas expresiones para una buena cantidad de juegos... pero sólo las teníamos para dos.
Mal asunto; me convencí de que pretender hacer retroingeniería mirando los 16 primeros bits no sería posible con sólo dos juegos, así que únicamente quedaban dos opciones: o dejarlo estar, buscando si acaso una forma más estructurada de implementar el algoritmo, o tratar de obtener esas expresiones para el segundo bloque de 16 bits de salida; eso sonaba laborioso y, dado que yo ya empezaba a estar un poco quemado después de tantos meses trabajando en problemas de cifrado, le di una patada a todo y me dediqué a otras cosas, en espera de que me volviese a picar el gusanillo.
Bueno, pues finalmente le he dedicado un poco de tiempo en las últimas dos semanas; como resultado de ello, ya dispongo de las expresiones para esos últimos 16 bits de salida. En el proceso, he obtenido información interesante: para empezar, ha quedado claro que se utiliza la misma función para los dos bloques de 16 bits (lo que todos suponíamos) y que la función tiene 32 bits de entrada y 16 de salida; en concreto, lo que ocurre es esto: Si la función es C=F(A,B), con A, B y C parámetros de 16 bits, el descifrado opera del siguiente modo:
Si el dato a descifrar es E1E2 y el dato plano es D1D2 (escribo los bits más altos primero), se tiene que
D1 = F(0, E1)
D2 = F(D1, E2)
Así pues, la única dependencia de D2 con respecto a E1 se tiene a través de D1, lo que no estaba del todo claro hasta ahora. Además, se ha visto que la «semilla» inicial es exactamente 0.
Es mi esperanza que estas expresiones nos permitan investigar el algoritmo con más facilidad; aquí tenéis un fichero con las mismas. Los números de los juegos son los mismos que tienen en MAME; el número de monomios que contiene la expresión de cada bit de salida oscila entre 2^4 y algo más de 2^14 pero, en todo caso, está muy lejos de los 2^31 que deberían esperarse para un buen algoritmo de cifrado con 32 bits de entrada (gracias a ello podemos permitirnos manejar tales expresiones, claro). De cualquier modo, no trataré de investigar nada hasta no tener las funciones inversas, quiero decir, las funciones G(A,B) tales que, fijado un A arbitrario, F(A,G(A,X))=G(A,F(A,X))=X para toda X. Esto debería de ocurrir la semana que viene; ya haré públicos los datos cuando los tenga.
Etiquetas: emulación
jueves, 3 de enero de 2008
Cajón de sastre
Hora de actualizar... Pero no esperéis una línea argumental aquí. Sólo retales.
Un viejo conocido necesitaba ayuda con cierto proyecto de descifrado, así que hicimos una parada para echarle una mano. Dos cosas especialmente interesantes han surgido de ahí: una, es haber comprobado cuán útiles son algunos estadísticos a la hora de descubrir relaciones entre bits; concretamente, la coinformación de un número de bits del resultado de una función cuya estructura se pretende determinar; la segunda es haber descubierto en el proceso TestU01, una librería de P. L'Ecuyer y R. Simard que implementa una gran cantidad de pruebas estadísticas destinadas a cuantificar la bondad de generadores de números aleatorios.
Desde hace unos meses he retomado una práctica de vida saludable que tenía casi olvidada: dormir bien. Quizá todavía no duerma la cantidad de horas que los especialistas recomiendan, pero ya casi descanso como es debido. Que es algo que había dejado de hacer a los 13 años. El efecto negativo de ello es que ahora tengo menos tiempo para dedicar a mis proyectos, pero me gusta creer que ahora soy un poco más productivo. :P
Cuando tenía unos 15 años pensaba que encontrar proyectos interesantes era una tarea difícil, que todo aquello a lo que merecía la pena dedicar tiempo había sido ya pensado y hecho. Ahora, en ocasiones me agobia recordar la cantidad de problemas y proyectos que me gustaría atacar, a sabiendas de que para muchos de ellos no llegaré a tener el tiempo necesario; es algo que viene con la edad, supongo. No es que me queje, ojo, peor sería lo contrario.
Y Jubatu... bueno, pues está tal cual estaba la última vez. Sí, sé que soy demasiado disperso; trato de controlar esa tendencia, pero no siempre puedo. Y, claro, estás fechas navideñas, con todo el ajetreo de reuniones, cenas, etc, tampoco ayudan. A ver si consigo reunir la fuerza de voluntad necesaria para centrarme en ello un poco.
Un viejo conocido necesitaba ayuda con cierto proyecto de descifrado, así que hicimos una parada para echarle una mano. Dos cosas especialmente interesantes han surgido de ahí: una, es haber comprobado cuán útiles son algunos estadísticos a la hora de descubrir relaciones entre bits; concretamente, la coinformación de un número de bits del resultado de una función cuya estructura se pretende determinar; la segunda es haber descubierto en el proceso TestU01, una librería de P. L'Ecuyer y R. Simard que implementa una gran cantidad de pruebas estadísticas destinadas a cuantificar la bondad de generadores de números aleatorios.
Desde hace unos meses he retomado una práctica de vida saludable que tenía casi olvidada: dormir bien. Quizá todavía no duerma la cantidad de horas que los especialistas recomiendan, pero ya casi descanso como es debido. Que es algo que había dejado de hacer a los 13 años. El efecto negativo de ello es que ahora tengo menos tiempo para dedicar a mis proyectos, pero me gusta creer que ahora soy un poco más productivo. :P
Cuando tenía unos 15 años pensaba que encontrar proyectos interesantes era una tarea difícil, que todo aquello a lo que merecía la pena dedicar tiempo había sido ya pensado y hecho. Ahora, en ocasiones me agobia recordar la cantidad de problemas y proyectos que me gustaría atacar, a sabiendas de que para muchos de ellos no llegaré a tener el tiempo necesario; es algo que viene con la edad, supongo. No es que me queje, ojo, peor sería lo contrario.
Y Jubatu... bueno, pues está tal cual estaba la última vez. Sí, sé que soy demasiado disperso; trato de controlar esa tendencia, pero no siempre puedo. Y, claro, estás fechas navideñas, con todo el ajetreo de reuniones, cenas, etc, tampoco ayudan. A ver si consigo reunir la fuerza de voluntad necesaria para centrarme en ello un poco.
lunes, 12 de noviembre de 2007
Jubatu: funcionalidad básica
Estos días he conseguido terminar de implementar la funcionalidad básica del módulo de ajedrez; ya se informa al usuario por pantalla de las condiciones de finalización de partida (jaque mate, rey ahogado, acuerdo de tablas, reclamo de tablas de acuerdo a las reglas de repetición de posición por tercera o sucesivas veces o por al menos 50 turnos sin captura de pieza o movimiento de peón). El usuario ya puede rendirse, proponer tablas a su oponente o reclamar tablas cuando las reglas así lo permitan. Además, se muestra un listado de las jugadas ya realizadas a la derecha del tablero (por simplicidad, no he utilizado la notación algebraica estándar, sino un simple formato casilla origen-casilla destino).
Aún no lo considero listo para ser publicado ya que creo que hay ciertas detalles que deben ser pulidos pero, dado que el momento se va acercando (pongamos que en mes y medio ya debería ser publicable), va siendo hora de dar algo más de información sobre el funcionamiento del programa:
La comunicación funciona sobre el protocolo de presencia/mensajería instantánea Jabber/XMPP, lo que significa que, para jugar, debes crearte una cuenta Jabber en cualquiera de los servidores existentes por ahí (yo, por ejemplo, tengo cuenta en jabberes.org, pero tenéis una lista de servidores públicos en http://www.jabber.org/user/publicservers.shtml), añadir como contactos a tus amigos, iniciar sesión desde el programa, y... ya podrías empezar a jugar.
El programa tiene una estructura modular, lo que significa que al núcleo, que implementa la conectividad xmpp básica y muestra la información sobre tus contactos y los juegos disponibles, se le añaden los módulos (de momento, sólo hay uno: el de ajedrez) que implementan los juegos.
Cuando llegue el momento de distribuir el programa, el núcleo será liberado bajo una licencia de código libre permisiva (tipo BSD o MIT, aún no he decidido exactamente cuál) y el módulo de ajedrez con la misma pero con excepciones para no cubrir las contribuciones de Morio y Will McGugan; dado que los módulos sólo se comunican e intercambian información con el núcleo, pero no entre sí, esto debería permitir que se puedan desarrollar otros módulos bajo distintos tipos de licencia sin que haya problemas de colisión de licencias.
Por ahora he probado con éxito el programa en Linux Kubuntu 7.04 (mi actual sistema de desarrollo) y en Windows XP. Es de suponer que se podría hacerlo funcionar en otros sistemas siempre que existan versiones de las tres librerías básicas necesarias (wxpython, pyxmpp y panda3d).
Y este es el estado actual de las cosas. Manténgase a la escucha. :)
Aún no lo considero listo para ser publicado ya que creo que hay ciertas detalles que deben ser pulidos pero, dado que el momento se va acercando (pongamos que en mes y medio ya debería ser publicable), va siendo hora de dar algo más de información sobre el funcionamiento del programa:
La comunicación funciona sobre el protocolo de presencia/mensajería instantánea Jabber/XMPP, lo que significa que, para jugar, debes crearte una cuenta Jabber en cualquiera de los servidores existentes por ahí (yo, por ejemplo, tengo cuenta en jabberes.org, pero tenéis una lista de servidores públicos en http://www.jabber.org/user/publicservers.shtml), añadir como contactos a tus amigos, iniciar sesión desde el programa, y... ya podrías empezar a jugar.
El programa tiene una estructura modular, lo que significa que al núcleo, que implementa la conectividad xmpp básica y muestra la información sobre tus contactos y los juegos disponibles, se le añaden los módulos (de momento, sólo hay uno: el de ajedrez) que implementan los juegos.
Cuando llegue el momento de distribuir el programa, el núcleo será liberado bajo una licencia de código libre permisiva (tipo BSD o MIT, aún no he decidido exactamente cuál) y el módulo de ajedrez con la misma pero con excepciones para no cubrir las contribuciones de Morio y Will McGugan; dado que los módulos sólo se comunican e intercambian información con el núcleo, pero no entre sí, esto debería permitir que se puedan desarrollar otros módulos bajo distintos tipos de licencia sin que haya problemas de colisión de licencias.
Por ahora he probado con éxito el programa en Linux Kubuntu 7.04 (mi actual sistema de desarrollo) y en Windows XP. Es de suponer que se podría hacerlo funcionar en otros sistemas siempre que existan versiones de las tres librerías básicas necesarias (wxpython, pyxmpp y panda3d).
Y este es el estado actual de las cosas. Manténgase a la escucha. :)
jueves, 1 de noviembre de 2007
Implementación de reglas
Últimamente no he dispuesto de demasiado tiempo libre, lo que me ha impedido trabajar en esto lo que me hubiese gustado... pero algo hemos avanzado:
- Tras muchas pruebas, creo que he fijado los modelos de las piezas; he cribado los vértices de los modelos de Morio hasta un punto en que el motor 3d pueda moverlos incluso sin aceleración hardware (en un ordenador relativamente moderno).
- La iluminación también ha sido fijada, después de haber tenido bastantes problemas al hacer pruebas (se hace uso de sombreado Gouraud, por cierto).
- Gracias a la amabilidad de Will McGugan, que me ha autorizado a utilizar su módulo python de ajedrez, me he ahorrado tener que implementar por mí mismo las reglas; puede que haya que corregir algunos errores, pero me encanta cómo está diseñado el módulo. ¡Gracias, Will! ;)
- He continuado con la implementación del protocolo de comunicación, y ya se pueden enviar los movimientos de un tablero al otro sin problemas.
Seguimos en la brecha. ;)
