December 09, 2008
Resumiré algunas pruebas realizadas durante los últimos días:
Durante una charla informal con Haze, hablando de las zonas de memoria que están asignadas a la BIOS y a las ROMs 10 y 20, se me ocurrió cómo comprobar cuál era el primer bit que cambiaba en la dirección de comienzo de la BIOS y la ROM 10 (ya sabíamos que, aparentemente, en sfiii2, la BIOS está asignada a la dirección 0 y la ROM 10 a la dirección 0x06000000): si encontraba dos zonas en blanco en la BIOS y la ROM 10 que ocupasen la misma posición con respecto al inicio de la correspondiente ROM, podría inferirse algo de información sobre la diferencia entre las direcciones a las que están asignadas simplemente mirando qué bits coincidían (pues sabemos que f#4 muestra ciclos puros de periodo 2^19 máscaras, f#5 de periodo 20, y así...).
Las zonas «en blanco» escasean en la BIOS (parece que ahí tuvieron mayor cuidado en no dejar «pistas»), pero finalmente fui capaz de encontrar dos tales zonas correspondientes en
Warzard y en
Sfiii (de 15 y 9 máscaras, respectivamente); se podía ver que, al comparar la BIOS con la ROM 10, en ambos casos los bits f#4, f#5, f#6, f#7 y f#8 eran idénticos, pero f#9 no. Ello indicaba que la diferencia de las direcciones de asignación de la ROM 10 y de la BIOS es un múltiplo impar de 0x02000000 (lo que es compatible con la hipótesis de que están ligadas a las direcciones 0 y 0x06000000 como en sfiii2, pero no la prueba).
ElSemi llamó mi atención sobre la tabla de 256 bytes situada al final de la BIOS; tras un análsis de un par de tablas, resulta claro que: 1º) la tabla se ha generado usando algún tipo de algoritmo que funciona a nivel de octetos, pues el bit #1 de cada octeto muestra regularidades estadísticas significativas cuando se observa la tabla completa (en
Jojo, de hecho, ese bit es siempre 0); 2º) por consiguiente, no es razonable suponer que esa tabla esté encriptada, sino que se trata de datos sin encriptar.
Una hipótesis tentadora es considerar que se trata de una tabla de subclaves indexada de alguna manera; sin embargo, no disponemos por el momento de ningún argumento sólido a favor o en contra de esta hipótesis, por lo que no insistiré en ello por ahora. En todo caso, si así fuese y estuviese siendo indexada con bits de la dirección, yo esperaría que fuese con bits de la parte baja, pues los bits altos de la dirección muestran propiedades de difusión mucho peores, lo que no me cuadraría con el hecho de que usasen diferentes entradas de una tabla.
Para tratar de validar el que una operación de tipo
rotate_left(x,4) XOR (x AND ???) estuviese siendo hecha (ver
CPS-3 (4)), se me ocurrió el siguiente experimento: al actuar, como operandos, una variable de 16 bits y ella misma desplazada 4 bits, se consigue que se creen cuatro clases de equivalencia en el conjunto de los 16 bits, perteneciendo a una misma clase aquellos que se afectan mutuamente por efecto del desplazamiento de 4 posiciones (de este modo, los bits #0, #4, #8 y #12 forman una clase, los bits #1, #5, #9 y #13 otra, y así con el resto). Si ahora estudiamos los números formados al juntar los cuatro bits de una misma clase, obtenemos una nueva variable x' y la operación se reduce a
rotate_left(x',1) XOR (x' AND y); y aquí empieza la fiesta: si, aun sabiendo que
x' e
y tienen que estar necesariamente correladas, suponemos que son lo suficientemente independientes una de la otra como para que la correlación sea pequeña, cabe suponer que la distribución de valores que sigan los datos reales nos dé información sobre si ese tipo de operación está siendo usada o no. Esto es así porque, si suponemos, en la operación anterior, que
x' e
y son totalmente independientes, y nos hacemos una tabla tabulando las 256 posibilidades según el resultado (de 0 a 15), obtenemos la siguiente distribución:
17 15 15 17 15 17 17 15 15 17 17 15 17 15 15 17
está distribución también la tiene la operación
rotate_left(x',1) XOR (x' OR y), pero no así otras posibles operaciones compatibles con lo que ya sabemos (o, al menos, yo no he sido capaz de encontrarlas)
Pues bien, al obtener las distribuciones reales para las cuatro clases de equivalencia correspondientes a
JojoIm1, se obtiene lo siguiente:
115163 134440 134684 123578 124325 119368 129136 138039 131465 123863 124014 134368 114033 128910 138950 132739
138511 116005 117079 133371 120561 137598 132515 113767 121234 142936 135015 120354 139340 123419 117903 137467
97696 155678 150638 107566 144235 105896 104535 149136 147566 109552 104031 153598 100741 153822 148116 114269
106225 149014 147978 108136 148715 110697 103607 151184 149013 112404 104923 149873 106272 145600 145167 108267
Se puede ver que la distribución para la segunda clase de equivalencia muestra, aproximadamente, una proporcionalidad directa con la distribución de arriba, mientras que el resto de clases muestran una proporcionalidad inversa; lo mismo ocurre con
JojobaIm1 y con
Sfiii3Im1 (aunque, en este último caso, el cuarto grupo es directamente proporcional, y los otros tres inversamente proporcional). Este tipo de distribución es la que yo esperaría si, después de haber realizado una operación como las de arriba (
rotate_left(x',1) XOR (x AND/OR y), se hubiese efectuado un XOR con un número fijo; dependiendo de la paridad de ese número, se obtendría una proporcionalidad directa o inversa.
Este experimento, de por sí, ya fue bastante interesante, pero no acabó ahí, pues, al día siguiente de haber hecho eso, tuve la feliz idea de tratar de obtener información sobre los términos
x' e
y haciendo uso de esa misma distribución. La idea fundamental es que el resultado de la operación te da información sobre los operandos, pues no todos los resultados se producen con la misma probabilidad; de esta forma, si uno dibuja la tabla de frecuencias que relaciona el resultado final (una fila por cada uno, de 0 a 15) con el término
y que le dio origen (una columna asociada con cada uno, de 0 a 15), obtiene esto:
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,},
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,},
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,},
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,},
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,},
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,},
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,},
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,},
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,},
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,},
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,},
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,},
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,},
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,},
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,},
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,},
y si hace los mismo relacionando el resultado con el término
x', esto otro:
{16,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,},
{0,0,0,0,0,0,0,0,8,0,0,0,4,0,2,1,},
{0,8,0,0,0,0,0,0,0,4,0,0,0,2,0,1,},
{0,8,0,0,0,0,0,0,0,4,0,0,0,2,2,1,},
{0,0,8,4,0,0,0,0,0,0,0,2,0,0,0,1,},
{0,0,0,4,0,0,0,0,0,0,4,2,4,0,2,1,},
{0,0,8,4,0,0,0,0,0,0,0,2,0,2,0,1,},
{0,0,0,4,0,0,0,0,0,0,4,2,0,2,2,1,},
{0,0,0,0,8,0,4,2,0,0,0,0,0,0,0,1,},
{0,0,0,0,0,0,0,2,8,0,0,0,4,0,2,1,},
{0,0,0,0,0,4,4,2,0,4,0,0,0,2,0,1,},
{0,0,0,0,0,4,0,2,0,4,0,0,0,2,2,1,},
{0,0,0,0,8,0,4,2,0,0,0,2,0,0,0,1,},
{0,0,0,0,0,0,0,2,0,0,4,2,4,0,2,1,},
{0,0,0,0,0,4,4,2,0,0,0,2,0,2,0,1,},
{0,0,0,0,0,4,0,2,0,0,4,2,0,2,2,1,},
La primera tabla da algo de información, pero no mucha: dado un resultado, asigna sesgos distintos a la probabilidad de un operando
y únicamente en función del peso de
y (número de bits puestos a 1). Ello hace que no se discrimine bien entre los valores para los bits individuales de ese término
y, e imposibilita que se pueda usar con facilidad esa información para reconstruir los ciclos esperados de los bits del término
y.
La segunda tabla, en cambio, tiene un aspecto excelente :D Permite discriminar las probabilidades de los bits individuales de x'; así, si cogemos un bloque de 2^19 máscaras consecutivas de
JojoIm1, calculamos el sesgo
a priori (usando la tabla mencionada) de que f#0 valga 0 (valores positivos indican que es más probable que valga 0 que 1; valores negativos lo contrario) y hacemos un análisis de autocorrelación, obtenemos esto:
Se observa claramente el ciclo de 2^15 máscaras que esperábamos.
Empero, si tratamos de usar esa tabla de probabilidades condicionales para calcular el valor de ese mismo bit para cada una de las 2^15 posiciones del ciclo (es de esperar que x' muestre un ciclo puro), el resultado, siendo aceptable, no es espectacular: el número de datos disponible para cada posición no es suficiente para obtener resultados incontrovertibles para cada posición. Pero la fortuna nos sonríe, porque, si observamos con más detenimiento la tabla, veremos que hay filas (correspondientes a ciertos resultados de la operación) que sólo se pueden dar para ciertos valores de los bits del operando x'; por ejemplo, si el resultado de la operación es 2 (tercera fila de la tabla), entonces necesariamente el bit #0 de x' será 1.
Esto nos permitiría recuperar los valores de algunos bits del ciclo, pero hay algo que debemos no perder de vista: dada la forma de la distribución, suponíamos que un XOR con un valor fijo estaba siendo efectuado después de la operación; cuando probé a recuperar esos bits para cada una de las máscaras XOR aceptables, otro hecho afortunado nos ayudó: al analizar los resultados, había una y sólo una máscara XOR que conseguía que en los bits del ciclo recuperados no se diesen valores idénticos separados por la mitad de tamaño del ciclo (algo que yo esperaba/deseaba, pues es una característica que es invariante ante bastantes de las operaciones que era probable encontrar antes de la que nos ocupa).
Una vez dado el salto de suponer que, efectivamente, esa característica (ser la segunda mitad exactamente como la primera pero invertida) la comparten todos los bits de
x, se obtiene, por una parte, la máscara XOR aplicada después (0xd86e en el caso de
JojoIm1 y
JojobaIm1, y 0x54ca en el caso de
Sfiii3) y, por otra, se pueden recuperar más bits de los ciclos (esta forma de obtener más bits y la anterior se retroalimentan). La escasez de máscaras disponibles no nos permite regenerar los ciclos completos, pero, al menos, obtenemos un porcentaje apreciable de algunos de ellos (los primeros bits, que muestran ciclos de longitud menor, son, por supuesto, los que pueden ser regenerados de forma más completa).
Y esto, a su vez, ha hecho surgir interesantes conclusiones:
- La parte del ciclo de tamaño 2^15 (del bit #0 de
x) que se recupera encaja perfectamente con el que recuperábamos al estudiar f#5 módulo 2^15 (ver
CPS-3 (3)). Esto ha supuesto una confirmación inesperada de algo que, si bien suponía, no encontraba manera de demostrar. :D
- Lo mismo ocurre con el ciclo de tamaño 2^16 pero invirtiendo los bits (lo cual es efecto de la operación XOR hecha después, por lo que no nos debe extrañar a estas alturas).
- El disponer de reconstrucciones parciales de los ciclos de los bits de
x' nos permite, a su vez, estudiar
y; esta es la actual línea de ataque que estoy siguiendo, pero todavía queda trabajo por hacer antes de extraer conclusiones...
Y este es el estado actual de las cosas... continuaré trabajando en esta línea, pero no será ahora. Hechos felices de la vida real (que algunos conocéis) van a alejarme de los ordenadores y de mi casa por espacio de dos o tres semanas; seguiremos con esto cuando vuelva.
Posted by Andreas Naive (noreply@blogger.com) at December 09, 2008 07:58 PM
