Foros:
Por sqrmatrix
¡Resuelto! Enhorabuena a Agustín, LlamameX y el equipo criptoanalítico habitual
Hola a todos. Lo primero de todo, pedir disculpas por la ausencia tan larga. En mi defensa diré que no fue intencionada, sino consecuencia de ciertas circunstancias personales. En este tiempo no he podido dedicarme a ningún reto.
Bueno, y ahora que ya está aclarado todo, deciros que me he cambiado de bando, y ahora, en lugar de ponerme a atacar algún reto, voy a proponer uno. Como nunca he propuesto retos, no sé si éste estará a la altura. Ya veremos. Antes de plantearlo eché un vistazo por encima a los retos propuestos anteriormente, para no repetirlo, y no me pareció ver ninguno similar a éste, aunque no los miré a fondo (eran muchos). Espero que no se repita.
He ideado un cifrario que se puede definir como un XOR con doble clave. El cifrario es bastante simple.
Siendo este cifrario un XOR, necesita un alfabeto cuyo número de letras sea una potencia de 2. Utilizaremos el alfabeto de 32 letras "ABCDEFGHIJKLMNÑOPQRSTUVWXYZ_.,:;".
Este cifrario dispone de dos claves. Una la llamaremos clave par, y la otra clave impar. Por cada letra que avancemos en el cifrado, elegiremos una de las claves. Si estamos situados en la letra i-ésima, consultaremos la letra (i-1)-ésima del mensaje original en claro. Si esta letra ocupa una posición par en el alfabeto, elegiremos la clave par, y si ocupa una posición impar en el alfabeto, elegiremos la clave impar. Cuando estemos en la primera letra del mensaje, como no tenemos letra (0-1)-ésima, tomaremos en este caso la clave par.
Para el cifrado, crearemos una copia del mensaje sobre la que trabajaremos. Es decir, inicialmente el criptograma será el mensaje claro.
Empezamos en la primera letra. Como estamos en la primera letra, tomamos la clave par. Enfrentamos las letras de la clave con las letras del criptograma, a partir de la primera letra, y hacemos XOR de las letras de la clave con las del criptograma, dejando el resultado en el criptograma.
Avanzamos a la posición 1 del criptograma. Consultamos la letra de la posición 0 del mensaje claro. Si ocupa una posición par en el alfabeto, tomamos la clave par, y si es impar, la clave impar. Colocamos las letras de la clave elegida encima de las correspondientes letras del criptograma, a partir de la posición 1, y repetimos la operación XOR como se hizo antes.
Pasamos a la siguiente posición y repetimos el proceso. Cuando nos acerquemos al final del criptograma, a la hora de colocar las letras de la clave sobre el criptograma, habrá letras que sobrepasen el final del criptograma. Estas letras se descartan.
Para descifrar, el procedimiento es el mismo. Cuando estemos sobre la primera letra, aplicamos la clave par. Al realizar la operación XOR, obtenemos la primera letra del mensaje, con la cual podemos determinar qué clave se eligió para la segunda letra, y así sucesivamente.
Para verlo mejor, se pondrá un ejemplo:
Mensaje: EN_UN_LUGAR_DE_LA_MANCHA
Clave par: SANCHO
Clave impar: QUIJOTE
Empezamos por la primera letra del criptograma. Elegimos la clave par, "SANCHO", y hacemos XOR de las letras de la clave enfrentadas a las letras del criptograma:
SANCHO EN_UN_LUGAR_DE_LA_MANCHA ----------------------------------- WNVWKTLUGAR_DE_LA_MANCHA
Pasamos a la segunda letra del criptograma. Ahora debemos consultar la primera letra del mensaje claro para ver qué posición ocupa en el alfabeto y así elegir la clave. La letra es la "E", y en el alfabeto ocupa la posición 4 (empezamos a contar desde 0), que es par, luego elegimos la clave par, "SANCHO", otra vez:
SANCHO WNVWKTLUGAR_DE_LA_MANCHA ----------------------------------- W:VZISEUGAR_DE_LA_MANCHA
Estamos en la tercera letra del criptograma. Consultamos la segunda letra del mensaje claro, que es la "N", y vemos que ocupa la posición 13, que es impar, luego elegimos la clave impar, "QUIJOTE":
QUIJOTE W:VZISEUGAR_DE_LA_MANCHA ----------------------------------- W:HOAZLBCAR_DE_LA_MANCHA
Seguimos aplicando este procedimiento. Al final, resultará que la clave sobrepasará el final del criptograma. Tenemos el caso:
QUIJOTE W:H:EVÑL.X;SCX_SAMZATUMA ----------------------------------- W:H:EVÑL.X;SCX_SAMLU..DT
Que, como se ve, se descarta la letra que sobra. En el siguiente caso se hace lo mismo:
SANCHO W:H:EVÑL.X;SCX_SAMLU..DT ----------------------------------- W:H:EVÑL.X;SCX_SAMLG.QBS
Es decir, se descartan las letras de la clave que sobrepasen el final del criptograma:
SANCHO W:H:EVÑL.X;SCX_SAMLG.QBS ----------------------------------- W:H:EVÑL.X;SCX_SAMLGOQMQ
Queda al final el criptograma:
W:H:EVÑL.X;SCX_SAMLGOAKI
Para descifrar, los pasos son casi idénticos. Empezamos por la primera letra y, como sabemos, se aplica la clave par:
SANCHO W:H:EVÑL.X;SCX_SAMLGOAKI ----------------------------------- E:K.DYÑL.X;SCX_SAMLGOAKI
En esta operación hemos obtenido la primera letra del mensaje, que nos permitirá decidir qué clave hay que elegir a continuación. En este caso, como antes, es la letra "E", que ocupa la posición 4 y, por tanto, debemos coger de nuevo la clave par "SANCHO":
SANCHO E:K.DYÑL.X;SCX_SAMLGOAKI ----------------------------------- ENKQB:BL.X;SCX_SAMLGOAKI
Hemos obtenido la segunda letra, que es la "N", y que ocupa la posición 13 y, por tanto, tenemos que elegir la clave impar "QUIJOTE":
QUIJOTE ENKQB:BL.X;SCX_SAMLGOAKI ----------------------------------- EN_EJWÑ;XX;SCX_SAMLGOAKI
Seguimos así. Los últimos pasos quedan:
QUIJOTE EN_UN_LUGAR_DE_LA_MANSBY ----------------------------------- EN_UN_LUGAR_DE_LA_MANCTQ
SANCHO EN_UN_LUGAR_DE_LA_MANCTQ ----------------------------------- EN_UN_LUGAR_DE_LA_MANCHQ
QUIJOTE EN_UN_LUGAR_DE_LA_MANCHQ ----------------------------------- EN_UN_LUGAR_DE_LA_MANCHA
Aquí está el enlace del reto: https://sites.google.com/site/sqrmatrix/criptograma.txt?attredirects=0&d=1. Son 79956 caracteres. No sé si será suficiente. Si alguien necesita más, sólo tiene que pedirlo.
No sé si este reto será demasiado fácil o demasiado difícil. Ya veremos según avancen las cosas.
Un saludo a todos.
No: es clave impar, par y texto
Voy a darle vueltas a lo de Alemania, de momento doy alguna más:
FOQUE GINETA AQUI_
DONEAR GILITO AQUEL_
Ps: LEMUR y LOGOMAQUIA no son inicio del texto, sino las claves impar y par respectivamente. Como en las 2 líneas de más arriba o como:
BUCHONA GRANCILLA ALGUN_
JAZMIN GRIPO ALGUNA_
Al margen de las pistas sobre
Al margen de las pistas sobre el inicio del mensaje hay una característica de este cifrado, que ya hemos comentado y que convendría explotar: su descarada periodicidad, tanto del texto cifrado como de la clave que en última instancia cifra el texto: me explico. Cifré un texto (ese del Nilo, que se utilizó en Lapyznos) con dos claves de 10 caracteres, después hice un xor entre el claro y el cifrado, obteniendo la pseudo-OTP que cifra el texto, y resulta que es tremendamente periódica: por ejemplo, saqué estos 15-gramas de Cryptool:
1 BNSHMQLWKFAZH,Q 0.0279 7
2 MBNSHMQLWKFAZH, 0.0199 5
3 ,QLV,QLV,QLV,QL 0.0159 4
4 ÑMBNSHMQLWKFAZH 0.0159 4
5 ÑXOO_UGÑ,BMTERA 0.0159 4
6 A:Ñ,QKBXZWLSRTB 0.0159 4
7 KA:Ñ,QKBXZWLSRT 0.0159 4
8 LV,ALWLDTPMERPJ 0.0159 4
9 MQLWKFAZH,Q_PY. 0.0159 4
10 NSHMQLWKFAZH,Q_ 0.0159 4
11 XOO_UGÑ,BMTERA: 0.0159 4
12 ZVNHX;XÑYXKBJZV 0.0159 4
13 ,EDQÑXOO_EWO_FQ 0.0120 3
14 ,USVNHXÑXO:KFAZ 0.0120 3
15 .GÑMBNSHMQLWKFA 0.0120 3
16 :Ñ,QKBXZWLSRTBN 0.0120 3
Tenemos una clave de 15 caracteres que se repite ¡7 veces a lo largo del texto! otra 5. Me gustaría ver un ataque sobre estas premisas antes que irle sonsacando al buenazo de sqrmatrix...
Reedición: claro, que en el fondo esto es una tontería: no se trata realmente de periodicidad, sólo se repiten aquellas cadenas de la clave que codifican el mismo texto, así que no nos sirven de mucho. Vaya por Dios, a ver como camelamos a Sqrmatrix...
El problema de este ataque
El problema de este ataque Kasiski es que aparentemente no se puede determinar la longitud de las claves. Habría que mirar a ver si hay alguna manera de sacarla, aunque puede que no haya manera, no lo sé. Conociendo la longitud de las claves, quizá se pueda hacer algo más, pero eso tampoco lo sé. LlamameX llamó la atención sobre las letras previas a estos bloques repetidos, que quizá permitirían sacar algo. Bueno, seguid intentándolo, que seguro que al final se os ocurre algo.
(para camelarme, un buen soborno ayudaría :) )
Ahí la gracia es otra
La gracia de encontrar texto cifrado igual no es la misma que la de encontrar trozos iguales de la "OTP" que calcula Tokamak. Tener texto cifrado igual implica trozos de texto en claro igual, pero también paridades iguales en los L caracteres anteriores a dicho trozo. No es aventurado pensar que esa paridad igual provenga de carácteres también iguales, con lo que podemos estudiar los inmediatamente anteriores distintos, puesto que probablemente serán iguales salvo un carácter de una de las claves que además será el último de la misma. Eso nos da una buena pista sobre él.
Confirmo teoria
Mientras espero el resultado de una prueba he vuelto sobre una cosa que teoricé pero que no había comprobado.
En absolutamente todas las combinaciones salvo 1 (volveré sobre ese resultado interesante) entre las parejas de las siguientes combinaciones
Los XOR entre los últimos carácteres distintos antes de la coincidencia dan 19. Los casos son:
Sabemos pues que esos carácteres cifrados Ci corresponden a un mismo Ai al que se aplica una secuencia de XOR Kx(0)..Kx(L-1) más un Kx(L) que es lo que los diferencia entre cada pareja de secuencias. Si las dos claves tienen igual longitud entonces existirá un KP(L) y un KI(L) y el XOR entre ambos será exactamente 19. Si hay una más larga que la otra entonces ese 19 corresponde al último carácter de la más larga y por tanto acaba en "S".
Ahora empiezo a estudiar los casos de carácteres anteriores y las más que interesantes excepciones. Es un hilo hacia el ovillo que había desestimado demasiado apresuradamente. Ah, y lo que es más bonito, no proviene de ninguna de las pistas de Sqrmatrix :)))
Carácteres anteriores
Estudiando posibles casos que pueden darse en los caracteres anteriores: Tenemos las secuencias (trozos de cifrado) que empiezan en las posiciones "i" y "j" donde C(i)=C(j) y C(i-1)<>C(j-1). Asumamos de nuevo que las caracteres A(i-2) y A(j-2) coinciden. La posición C(i-2) diferirá pues de C(j-2) en KP(L-1)^KI(L-1)^x(L)^y(L), donde los factores x e y corresponden a las claves implicadas por la paridad de A(i-L) y A(j-L) respectivamente. Entonces pueden darse dos casos que ambos caracteres tengan la misma paridad o que la tengan distinta. Puesto que sabemos a ciencia cierta que la de A(i+L+1) y A(j+L+1) son distintas, al xorear C(i-2) con C(j-2) deberíamos encontrar sólo dos grupos de valores dependiendo de si x(L)=y(L) o si x(L)<>y(L).
Si lo comprobamos vemos que tenemos sólo las siguientes combinaciones posibles
Con lo que comprobamos que efectivamente estamos en lo cierto y nos permite agrupar las combinaciones donde A(i-L) comparte paridad con A(j-L) y repetir el proceso para A(i-3). Si tenemos suficientes combinaciones podremos llegar hasta L posiciones. Sabremos que hemos acabado cuando obtengamos más de 2 grupos de valores, puesto que ahí o A(i-L)<>A(j-L) o habremos agotado la longitud de clave con lo que la habríamos determinado.
Posición -3 y -4
Cojo los grupos que dan 23, que son de los que hay más para calcular las paridades correspondientes a la posición -3. Tenemos:
Podemos seguir para A(i-4) con los 31
Genial, y como siempre
Genial, y como siempre Llamamex es el que aporta la solución diferencial
Los 32 primeros caracteres del cifrado son:
G;ULSC;RW:_DF:JN;ÑEV;UMRW:_DF:JN
y se repite la cadena en negrita en tan corto tramo. Además la subcadena F:JN es el tetragama más abundante del criptograma. Con estos mimbres debería ser más fácil descifrar el mensaje, aplicando aquí tu sistema. Si unimos a esto los candidatos a caracteres iniciales obtenidos por Agustín, el éxito se vislumbra en el horizonte. Sois unos criptoanalistas fenomenales!
Sin haberlo comprobado a priori
Eso apunta a una longitud de clave máxima para la más larga de 7. He de verificarlo sin embargo en secuencias con más repeticiones. He de buscar un ngrama con más ocurrencias para poder bajar 8 niveles y en el último he de conseguir 4 grupos de resultados.
Edito:
Comprobado que como mínimo los 3 carácteres anteriores a RW (posiciones 4,5 y 6 empezando en 0) también coinciden. Seguramente bastantes más. Si se me permite una conjetura es el título del texto que se repite al inicio del mismo. Ya es tarde. Mañana verifico el resto. De ser así ese error del cifrador es nuestra piedra de rosetta.
Es extraño
Según los datos que estoy obteniendo una de las claves tendría 5 caracteres. Me parece corta, pero me cuadra. Obviamente si la clave termina en A no estaré contando ese carácter, pero tampoco influiría en el cifrado.
Edito: Incluso debería concluir que la clave más larga tiene esos 5 caracteres. Por más que lo reviso no veo otra explicación
Los xores que afectan a la repetición de inicio són
Cuando los árboles posibles hasta las 4 primeros caracteres anteriores (los he obtenido hasta una profundidad de 7) son
Con lo cual queda claro que a partir del tercer anterior a esa secuencia ya se le están aplicando todas las Kx que le tocan, con lo que la clave más larga está cubierta y ha de tener 5 caracteres de largo (salvo 'A's finales)
CORRIJO!!!!
Bobo de mi, esas posiciones están afectadas por la primera clave par que viene forzada por las especificaciones del algoritmo, con lo que el que esto sea correcto dependerá de si la clave inducida por A(15) es también par (podría serlo puesto que la clave par afectaría tanto a C(3), el primer carácter díscolo, como a C(4) que se adapta bien al árbol)
¿Qué, cómo va la cosa? sobre
¿Qué, cómo va la cosa? sobre todo en lo que se refiere a la longitud de las claves: no me acaba de cuadra que sean tan cortas, ya hubiera obtenido algo con mi AG. Por descartes creo que deben de ser al menos de 7 caracteres.
Creo que han de ser cortas
Salvo tremendas coincidencias o claves muy escogidas (con 3 o 4 letras en común en las mismas posiciones). El análisis del árbol de paridades muestra grupos de más de dos a partir de la quinta posición hacia atrás en muchas ramas. Además las repeticiones iniciales son muy sintomáticas. Tenemos algo del estilo
, es decir, 7 caracteres diferentes, 9 comunes, 7 diferentes, 9 comunes. Salvo coincidencias, hemos de suponer que los caracteres comunes corresponden al mismo texto en claro. Para que a dos A[i] y A[j] tengan la misma codificación C, habrán tenido que ser cifrados con la misma secuencia de Kx (salvo esas coincidencias de las claves que mencionaba), ahora bien, esas secuencias vienen determinadas por la longitud de la clave más larga L , que en las posiciones del principio además, serán, series incompletas (el primer carácter solo se xorea 1 vez, el segundo 2, etc) hasta el caracter L-1 (empezando en 0) no se habrán usado todos los xores que corresponden. Así, salvo coincidencias (o As finales que no cuentan), queda claro que la longitud de clave no puede ser superior a 7 puesto que en esa posición empieza el bloque de los caracteres comunes.
En cuanto al carácter distinto previo al primer bloque comun, vemos que xoreándolo con el previo del segundo bloque común obtenemos el famoso 19, cosa que cuadra con suponer que el caracter en claro de esas posiciones también coincide y sólo son distintos por que la paridad del último carácter de la clave que le afecta es diferente, pero la clave se aplica completa. Lo mismo pasa con los dos carácteres anteriores pero ya no más atrás, cosa que me llevo a pensar que ahí la clave no se aplica entera.
Calculo corregido
Pongo las posiciones posibles del texto probable con las diferentes longitudes de clave.
Para una clave de 5
0....:....1....:....2....:....3. ABCDEFGHIJKLMNÑOPQRSTUVWXYZ_.,:; PIIPIIIIIPPPPIPPPII 0 1 2 3 4 5 6 7 8 9 0 1 2 3 EL_MUNDO_CIVILIZADO N D O _ C I V I L I Z A D O (palabra probable P) P I I I I I P I I I I I P P .PPPPP............. I I I I I P I I I I I P P P ..IIIII............ I I I I P I I I I I P P P P ...IIIII........... I I I P I I I I I P P P P I ....IIIII.......... I I P I I I I I P P P P I P .....IIIII......... ......IIIII........ Para una C(i) dada calculamos X(j)=P(j)^C(i+j) .......PPPPP....... X0=X6 ........IIIII...... X1=X7 .........IIIII..... X2=X8 ..........IIIII.... X8^X10=X3^X4 ...........IIIII... X3^X13=X2^X12 ............IIIII.. X0^X11=X2^X12 .............PPPPP. X12=X1^X3^X4^X5^X6 ..............PPPPP ...............PPPP ................PPP .................II ..................PLas posiciones obtenidas
Para una clave de 6
0....:....1....:....2....:....3. ABCDEFGHIJKLMNÑOPQRSTUVWXYZ_.,:; PIIPIIIIIPPPPIPPPII 0 1 2 3 4 5 6 7 8 9 0 1 2 EL_MUNDO_CIVILIZADO D O _ C I V I L I Z A D O (palabra probable P) P I I I I I P I I I I I P .PPPPPP............ I I I I I P I I I I I P P ..IIIIII........... I I I I P I I I I I P P P ...IIIIII.......... I I I P I I I I I P P P P ....IIIIII......... I I P I I I I I P P P P I .....IIIIII........ I P I I I I I P P P P I P ......IIIIII....... Para una C(i) dada calculamos X(j)=P(j)^C(i+j) .......PPPPPP...... X0=X6 ........IIIIII..... X1=X7 .........IIIIII.... X7^X9=X2^X3 ..........IIIIII... X8^X10=X3^X4 ...........IIIIII.. X12=X1^X3^X4^X5^X6 ............IIIIII. .............PPPPPP ..............PPPPP ...............PPPP ................PPP .................II ..................PLas posiciones obtenidas
Mirando de unir ambos caminos
He buscado n-gramas en las posiciones donde puede aparecer el texto probable, pensando en que pudiera aparecer más de una vez y he encontrado estas coincidencias:
Cosa que da muy buena impresión.
Frase objetivo
Hum, pues si se repite nos sirve, pero, ojo, exactamente para lo contrario, o sea para descartar que sea el texto conocido, ya que Sqrmatrix dijo que sólo aparecía una vez.
Si alguna de esas concurrencias se repite, lo mismo, la descartamos.
No le valen
Estoy seguro de que no le valen a LlamameX mis resultados, porque se han obtenido a partir de varias generosas pistas dadas por sqrmatrix, y creo que él está buscando una solución general, no contaminada por esa circunstancia.
Claro que valen!
Faltaría más, es un análisis muy bueno y en criptoanálisis hay que usar toda la información de inteligencia de que se disponga. Que se lo hubieran dicho si no a los de BP. Lo único que busco es un ataque que sea válido aunque no se disponda de esos datos, pero en ningun caso (el FSM me libre) intento menoscabar otros esfuerzos,
No es menoscabo
Entiendo que busques una solución general. Por otra parte, estoy convencido de que el ataque por fueza bruta al pincipio del texto es posible aun sin las pistas del autor, sólo que rqueriría más potencia de cómputo. Por ejemplo, la reducción a 16 letras para la inicial del texto tiene validez general asumiendo, eso sí, que las claves son legibles.
No creo que sea para tanto
Estamos diciendo que a cualquier carácter del texto se le aplica una secuencia Kx0...KxL donde L es la longitud de la clave más larga y x es P o I dependiendo de la paridad de los L caracteres anteriores. Eso implica que repetir una secuencia de paridades repetirá el trozo de "OTP" correspondiente y dado que no prefijamos ninguna secuencia de paridades en concreto estamos ante una "colisión de cumpleaños" (de aquello que encontrar a dos personas con el mismo cumpleaños en un grupo de n personas es mucho más probable -en un factor raiz de n- que encontrar una con una fecha de cumpleaños en concreto). Así encontrar repeticiones de secuencias de paridad en un texto tan largo no debería ser sorprendente.
Estáis descubriendo cosas de
Estáis descubriendo cosas de mi criaturita que ni siquiera me había imaginado. Me pregunto cuánto tiempo le queda a la pobre...
Es lo que pasa siempre, por
Es lo que pasa siempre, por eso es muy bueno que los algoritmos de cifrado sean públicos: enseguida se ven las debilidades y las fortalezas, lo que es muy útil para perfeccionarlos y para aprender de todo el proceso; y sí, yo creo que ya le queda poco tiempo, jejeje...
Diez incógnitas
Debo reconocer que se me escapa una gran parte de los razonamientos de LlamameX, pero si sus trabajos confirman que la clave más larga tiene 5 caracteres, el problema del ataque al texto conocido sería posible, ya que tendríamos 20 - 5 = 15 ecuaciones, y sólo tendríamos 10 incógnitas, como ya se vio en posts anteriores.
Evidentemente, habría que localizar la posición de la famosa cadena "_EL_MUNDO_CIVILIZADO", quizá mediante los artilugios del propio LlamameX, o habría que ir probando por todo el texto, lo que sería tedioso.
¿Es en eso en lo que estamos?
Determinar la longitud de clave
Tengo ya los mecanismos para determinar de una vez la longitud de clave máxima dentro de los márgenes en los que nos movemos. Fundamentalmente se trata de que una clave de 5 también es una clave de 6 si le añadimos una "A" al final, con lo que las restricciones para una clave 6 también han de estar incluidas en las de 5, pero no al revés. Y lo mismo entre 6 y 7.
Asi pues una clave de 7 ha de cumplir (entre otras) en el texto probable
Mientras que una de 6 cumplirá (entre otras)
Nótese que las condiciones a,b y c son equivalentes, puesto que en una clave con un carácter menos estamos empezando en el carácter anterior en el cifrado. La condición d, sin embargo no se cumple en la clave de 7, ya que incluye X0 que correspondería a X(-1). De este modo, si las posiciones que obtenemos para una longitud de 7 incluyen a las que obtengamos para una longitud de 6 (desplazadas 1 puesto), eso implicará que se trata de la misma clave con una "A" al final, con lo que la longitud efectiva es de 6. Lo mismo se aplicaría a la comparación entre 5 y 6.
Voy a comprobarlo con un cifrado de prueba y pongo las conclusiones.
Resultado interesante.
Con clave de 7 letras en la posición 31890, con la particularidad de que el XOR KP6^KI6 (obtenido de X(1)^X(2)^X(5)^X(10)) da precisamente 19. Es el único resultado con el que obtengo este valor.
Coincidencias
Muy bien, es un gran avance. Como te decía el sabado los resultados que prometen más los obtenía con claves de 7 caracteres, me cuadra muy bien.
O _ C I V I L I Z A D O
; C C MÑ A_ I Ñ B R A
¿Es así como coincidirían el cifrado y el texto?
No exactamente
No se si es por empezar a contar en cero, pero para mi es
La otra línea de ataque
Volviendo a mi otra línea de ataque, la de los "anteriores" (los caracteres prévios a un n-grama que se repite). Para clarificar la idea vuelvo un poco a los orígenes y la explico entera.
Imaginemos un caso como el del esquema. Tenemos 2 n-gramas repetidos, que aparecen en las posiciones i y j del cifrado y supongamos que la longitud de la clave más larga es L. Asumamos que nuestros n-gramas se repiten por que las porciones de texto claro al que representan también están repetidas (en n-gramas largos podemos asumir que no es por casualidad, sobre todo si tenemos varias repeticiones, como es el caso).
Cojamos uno de ellos. Represento en amarillo la parte que es igual en ambos. Para que dos caracteres iguales en claro se cifren por la misma letra necesitaremos que la secuencia de XORs que reciben de las claves sean iguales, es decir que las paridades de los carácteres previos que las determinen también coincidan. Pinto en verde esas claves que se aplicarán igual en ambos n-gramas.
Vamos a fijarnos ahora en los carácteres previos. Haré ahora una suposición: algunos de esos carácteres (inmediatamente) anteriores corresponden también a carácteres en claro iguales, pero que se cifran distintos por que las paridades de los carácteres que les afectan son diferentes. Pinto en naranja esas posiciones y en rojo las claves que son diferentes en cada uno de los n-gramas.
Puestos aqui vamos a xorear los carácteres anteriores de un n-grama con los del otro.
Si cogemos los de la posición i-1 y j-1, es decir C(i-1)^C(j-1), vemos que todo debería anularse salvo KP(L)^KI(L) ya que todo lo demás es igual en ambos n-gramas. Es decir, lo que hace que el cifrado sea distinto en ambos casos es la última letra de la clave, que en un caso será la par y en otro la impar. Aquí es donde nace el famoso 19. Si cogemos TODOS los n-gramas con múltiples repeticiones y xoreamos por parejas el carácter anterior al trozo común SIEMPRE obtenemos 19. Señal inequívoca de que estamos en lo cierto. Aquí obtenemos una ecuación XOR:
KP(L)^KI(L)=19
Vamos a ir más allá. Pensemos en la pareja C(i-2), C(j-2). En este caso tenemos dos posibles diferencias: la clave derivada de C(i-L) -la que determina C(i-1)- y la derivada de C(i-L-1). Al hacer el XOR desaparecerá todo salvo KP(L-1)^KI(L-1)^Kx(L)^Ky(L). Nótese que sabemos que KP(L-1) y KI(L-1) estarán presentes por que nos vienen de la posición anterior, pero de la nueva pareja de claves que nos afecta no sabemos nada. Pudiera ser que ambas fueran pares, ambas impares o una de cada tipo.
Ahora bien, si ambas son pares o impares Kx(L) se anulará con Ky(L), y si ambas son distintas estaremos ante KP(L)^KI(L) que ya sabemos que es 19. Por tanto o Kx(L)^Ky(L) o es 0 o es 19. Esto nos genera dos ecuaciones xor posibles:
KP(L-1)^KI(L-1)=C(i-2)^C(j-2)^19
o
KP(L-1)^KI(L-1)=C(i-2)^C(j-2)
Dado que los valores que he encontrado para C(i-2)^C(j-2) son 4 o 23 en todos los casos podemos determinar esas ecuaciones como
KP(L-1)^KI(L-1)=23
o
KP(L-1)^KI(L-1)=4
Cosa que casa perfectamente puesto que 23^4=19
Podemos seguir mientras podamos asumir que nos movemos en la "zona naranja". En cada paso nos aprecerá el doble de ramas nuevas ya que tendremos 2 posibilidades para la clave que nos afecta. En algunos casos he llegado hasta 7 niveles obteniendo resultados coherentes (suficientes resultados iguales) con los que determinar la dependencia XOR entre todos los componentes de la clave hasta esa longitud.
Bueno dejo aquí el rollo y luego os pongo en que se concreta todo esto.
Imágenes:
Sigo con atención los
Sigo con atención los progresos de los ataques. Éste está muy interesante. Tenéis acorralada a mi criaturita. Pobrecita :)
Todo el árbol que puedo obtener
Al menos con unas ciertas garantías, es decir que el XOR entre las ramas sea 19, que haya suficientes casos en el texto (mínimo 2 o 3 por cada resultado), que las subramas también sean coherentes, etc. Me he basasdo en el n-grama más repetido y en todas las operaciones XOR entre ellas. Salían en total cerca de 200 y el árbol de opciones es el siguiente. (Nota: para facilitar las comparaciones esta construido empezando desde C(i-1) hacia atrás, es decir el árbol está al revés de como se encuentra en el cifrado).
Los resultados -- representan los casos en que a partir de ese resultado no hay suficiente evidencia para ir más allá. Nótese como en algunos (pocos) casos he llegado hasta el nivel 7 pero ya no hasta el 8. Las líneas que parecen duplicadas las mantengo por presentar el árbol completo.
Luego continuo sacando conclusiones.
¡Confirmación!
Desarrollando los sistemas de ecuaciones suponiendo los resultados para la posición 31890 obtengo las siguientes conclusiones:
Que encajan totalmente en una de las ramas del arbol. Se determina por tanto la longitud máxima, la posición del texto probable y la relación entre los carácteres de las claves. Sólo queda dar la puntilla.
Se respira tensión
Se respira tensión en el ambiente... ¿Habrá acertado, o habrá sido engañado?. Todos estamos expectantes...
LlamameX es uno de los grandes genios.
Sus hallazgos son apabullantes. Sí señor, el mismísimo Albert Einstein le felicitaría.
Un genio
Un genio es lo que es, sí señor, me uno al coro de alabantes.(Todavía estoy intentando entender el ataque, vergüenza me da decirlo...)
Me alegro
Me alegro de que lo digas, porque yo no me atrevía a reconocerlo. Espero que cuando todo termine nos ofrezca una explicación detallada de todos los pasos. Lo de la tablita final de los XOR entre las claves es la culminación de un trabajo formidable, y creo que equivale a la solución matemática del problema.
Lo voy a contar
Lo voy a contar porque lo resolví esta tarde, y ya no puedo esperar más.
Antes que nada, quiero decir que mi solución no tiene ningún mérito, ya que me he limitado a aplicar los análisis de LlamameX a los resultados de mis ataques al tetragrama inicial, que se vieron favorecidos por algunas pistas de sqrmatrix. La solución está ahora a la vista, y cualquiera podría verla. No solamente el mérito es de LlamameX, sino que ni siquiera he podido entender cómo ha obtenido esta magnífica tabla. Por eso hubiera preferido que rematara él, pero no creo que se dedique a mirar mis tetragramas, así que, armado con la tabla de XOR de todas las letras con todas las letras, voy p'allá.
LlamameX dixit
que, equivale a:
De modo que la primera letra de la clave par y la primera de la clave impar han de ser iguales. Resulta que el repertorio de primeras letras para la clave par es muy limitado, disponiendo sólo de A C E G T; y la circunstancia de que coincida con la primera letra de la clave impar nos limita la muestra a unos pocos casos, como
Pero al aplicar la segunda condición se descartan casi todas. Tomemos la serie GR: La segunda letra de la clave impar ha de ser la E, y aunque el ataque no daba ninguna pista de la tercera letra de la clave impar, ahora sabemos que se debe combinar con la su homóloga de la clave par según las ecuaciones de LlamameX. Si la clave par es GRA, la clave impar ha de ser GEN, y si la clave par es GRAN, la clave impar ha de ser GENI. A partir de ahí no hay que ser uno de ellos para ver, rutilantes, las dos claves: GRANDES GENIOS. Entonces va uno a la implementación, y obtiene:
ALBERT_EINSTEIN_ALBERT_EINSTEIN_ULM,_ALEMANIA,_DE_MARZO_DE_U_PRINCETON,_ESTADOS_UNIDOS,_DE_ABRIL_DE_FUE_UN_FISICO_ALEMAN_DE_ORIGEN_JUDIO,_
Gracias, LlamameX, por esta lección -que espero expliques con detalle- y a tí, sqrmatrix, por este interesante reto... y por las pistas.
Hombre pues sí que tiene
Hombre pues sí que tiene mérito, porque la primera aproximación, con los descartes de las iniciales de las claves, la hiciste tú, llegando finalmente a la solución gracias al genial aporte de LlamameX.
Con este reto me lo he pasado mejor que con otros aunque al final no llegase a nada. Quizá fuese más divertido porque se veía que el cifrario era vulnerable, por las repeticiones de texto, también las pistas tenían su aquello incitante, y se avanzaba más rápidamente que con otros, así que me uno también a los agradecimientos a Sqrmatrix por proporcionar este comecocos gratuito, y quedo a la espera de la explicación extendida del ataque de LlamameX, ¿cómo hará para "ver" esas cosas?
Bombillita
Debe tener una bombillita como las que asociaban en los tebeos antiguos a las ideas "brillantes". Algún día le preguntaremos su C.I.
Ole!
Hehehe, me has adelantado. Iba a publicar mi resultado (el mismo, claro) aunque yo lo he obtenido por otro medio sin recurrir a los lemarios. He usado la "piedra de rosetta". Tal y como conjeturé los 16 primeros carácteres se repiten. Aplicando los anteriores vemos que C(6)^C(22)=19, cosa esperable puesto que ambos carácteres reciben todas las Kx. Ya es más raro es que C(5)^C(21)=23, puesto que sigue el árbol a pesar de que le falta Kx(6). La única explicación es que Kx(6)='A', es decir que la clave impar tenga 6 letras (la par tiene 7 ya que es la que se usa en primer lugar y cubre C(6). Por tanto:
KP(6)="S" KI(6)=""
Vamos ahora a por el sexto carácter. Dado que tenemos que la clave par afecta a C(6) forzosamente C(22) ha de estar afectada por la clave impar. Aquí tenemos que C(4)^C(20)=12, que también sigue el árbol. Ahora tenemos dos posibilidades o KI(5)="A" o bien KI(5)=KP(6) para que se anulen. Dado que si KI(5)="A" entonces KP(5)="W" que no tiene sentido concluimos que:
KP(5)="E" KI(5)="S"
En la siguiente posición nos alejamos del árbol. Seguimos con la suposición (acertada) del texto repetido al inicio. Tenemos C(3)^C(19)=29. Tenemos 2 posibilidades para KP(4) combinar con los KI(6)-KP(6) y KI(5)-KP(5) que ya tenemos. La que nos casa es
KP(4)="D" KI(4)="O"
Etc. Finalmente obtenemos
KP="GRANDES"
KI="GENIOS"
Y olé
Me gusta más tu método, aunque tengo que echarle una segunda lectura.
Enhorabuena por el magnífico análisis que has realizado.
¡¡¡Enhorabuena!!!
Y esta enhorabuena va para todos, porque todos habéis contribuido a resolver el reto, y todos habéis aportado cosas muy interesantes al mismo. Por supuesto, una enhorabuena adicional a Agustín y a LlamameX por resolver el reto. Cuando Agustín dijo "Sí señor, el mismísimo Albert Einstein le felicitaría", no sabía si era porque ya conocía la solución, o si era una de esas curiosas casualidades, pero en vista de los avances, me sospechaba lo primero. Las conclusiones de LlamameX me sorprendieron bastante (sobre todo aquella en la que decía que el título se repetía).
Bueno, el texto lo cogí de la Wikipedia. Me cogí las entradas para Albert Einstein y para Isaac Newton. Las claves, evidentemente, se aplican a estos personajes, pero creo que también se pueden aplicar a los participantes de este reto.
Un saludo y una enhorabuena a todos.
P.D.: Por cierto, ¿qué tal se os dan las congruencias y el Teorema Chino de los Restos?. Porque en este tiempo he estado pensando en otro reto, aunque todavía no lo he desarrollado, y ni siquiera sé si se puede implementar. En caso de que sí, creo que sería un reto bastante facilito de atacar, y su interés está en el uso de estos elementos matemáticos, más que en su dificultad, elementos que se usan más bien poco en los retos
Asias y gracias a ti
Respecto a los temas que comentas, ¿quieres implementar algo del estilo de RSA?. Me parece que estamos ya hablando de palabras mayores. Igual eso es mucho para un reto.
Declive y caída de XOR2
Aunque el grueso del ataque ya está explicado, voy a mirar de ampliar algunos conceptos, que a veces en el fragor del combate hay cosas que, por tenerlas tanto tiempo en la sesera, uno las da por ya explicadas y no lo están.
El cifrado XOR con 2 claves de Sqrmatrix parece a primera vista muy sólido. Los caracteres se cifran varias veces y hay 2 claves implicadas. La selección de claves en cada caso, además, depende del texto en claro y por tanto es otra incógnita.
Sin embargo tiene una debilidad intrínseca que, junto a particularidades del texto en claro del reto, nos abren la puerta para atacarlo. La gran debilidad surge en los n-gramas, puesto que trozos suficientemente grandes de texto en claro que se repitan causarán que también nos aparezca texto cifrado asimismo duplicado.
Para entender por que esto es así vamos a cambiar la manera de ver la aplicación del cifrado por una más fácilmente formulable. El algoritmo nos dice que, empezando por la clave par, haremos xor del texto en claro con cada una de las claves, escogiéndolas en base a la paridad del carácter en claro previo al que estamos cifrando. Esto ocasiona un cifrado acumulativo puesto que también estaremos afectando a los caracteres siguientes.
En lugar de verlo así vamos a fijarnos en la serie de XORs que se hacen a cada carácter. Vamos ahora a obviar los primeros ya que no reciben la serie completa. Por comodidad, vamos también a asumir que ambas claves tienen la misma longitud (L), cosa que no afecta puesto que podemos completar la más corta con "A"s por la derecha sin afectar al cifrado.
Fijémonos en un trozo del cifrado correspondiente a la posición i. Esté estará construido por el XOR entre el texto en claro A(i) y una serie de Kx(0)^...^Kx(L-1) . Las Kx pueden corresponder a par o impar (KP o KI) y obviamente pueden ser distintas en cada línea.
... C(i-2) C(i-1) | C(i) | C(i+1) C(i+2) ... ... A(i-2) A(i-1) | A(i) | A(i+1) A(i+2) ... ... Kx(L-1) | | ... Kx(L-2) Kx(L-1) | | ... Kx(L-3) Kx(L-2) | Kx(L-1) | ... Kx(L-4) Kx(L-3) | Kx(L-2) | Kx(L-1) ... ... | ... | ... Kx(0) | Kx(1) | Kx(2) ... | Kx(0) | Kx(1) ... (Nota: las Kx no tienen por que coincidir, simplemente indican que no sabemos si son KP o KI)Pasamos a ver pues la codificación como la aplicación de una secuencia de Kx(0)...Kx(L-1) a un determinado A(i) para obtener C(i). Esta secuencia sólo puede variar entre 2 valores para cada Kx(i), con lo que en el fondo sólo habrá 2**(L) secuencias posibles. Dado que la selección en cada caso depende de la paridad del texto claro, la repetición de texto claro causará la repetición de las secuencias, con lo que tras algunos caracteres (mientras agotamos las "colas" de las claves previas distintas) generará texto cifrado idéntico, es decir un n-grama repetido.
La principal gracia está precisamente en los caracteres anteriores al n-grama repetido en el cifrado. Concretamente al carácter inmediatamente previo al n-grama, es decir si las repeticiones empiezan en las posiciones i y j, fijémonos en C(i-1) y C(j-1). Como decíamos, C(i)=C(j) es la primera manifestación del n-grama (el primer carácter igual en el cifrado), pero para que el n-grama exista los caracteres previos del texto en claro también tienen que estar repetidos aunque los representemos distintos en el cifrado. Precisamente lo que los hace distintos es lo que nos va a dar la clave.
Nota: Aunque 2 secuencias iguales de L+n letras en el claro generan un n-grama repetido (de longitud n) en el cifrado, un n-grama repetido en el cifrado no tiene por que estar generado por secuencias iguales de L+n letras en el claro, con que las L anteriores mantengan la paridad es suficiente. Sin embargo ya veremos que si tenemos un número suficientemente grande de repeticiones de un mismo n-grama podremos descartar aquellos casos en que sólo coincide la paridad, al menos hasta un cierto nivel.
Volvamos sobre nuestros C(i-1) y C(j-1). Podemos asumir que A(i-1)=A(j-1) pero que el cifrado es distinto por algún motivo. Veamos cual es. Ambas secuencias de Kx que se aplican han de ser casi iguales, puesto que son casi las mismas que se aplican a C(i) y C(j) que son idénticas. La única diferencia (ese "casi") está en el Kx(L-1). Así pues en un caso se estará aplicando la clave par y en el otro la impar, ya que esta es la única razón la por la que pueden ser distintos.
Entonces, si C(i-1) tiene casi todos los componentes iguales a C(j-1), si los xoreamos entre ellos anularemos todas las partes iguales y nos quedaremos sólo con el XOR de las partes diferentes, que será KP(L-1)^KI(L-1). Por tanto ya tenemos una primera ecuación XOR puesto que C(i-1)^C(j-1) será un valor conocido. En nuestro caso el número mágico 19.
Pongamos un ejemplo concreto: Supongamos que L=4 y que la secuencia que afecta a la C(i) por orden de aplicación es Par, Impar, Par, Impar. Pongo un n-grama encima del otro y recordemos que desde C(i)=C(j) coinciden pero que antes son distintas
... C(i-2) C(i-1) | C(i) | C(i+1) C(i+2) ... ... A(i-2) A(i-1) | A(i) | A(i+1) A(i+2) ... -------------------------------------------------- ... C(j-2) C(j-1) | C(j) | C(j+1) C(j+2) ... ... A(j-2) A(j-1) | A(j) | A(j+1) A(j+2) ... -------------------------------------------------- ... Kx(2) Kx(3) | | ... KP(1) KP(2) | KP(3) | KI(0) KI(1) | KI(2) | KI(3) KI(0) | KI(1) | KI(2) KI(3) | KI(0) | KI(1) KI(2) ... C(i-1)=A(i-1)^Kx(3)^KP(2)^KI(1)^KI(0) C(j-1)=A(j-1)^Kx(3)^KP(2)^KI(1)^KI(0) (Nota: las Kx no tienen por que coincidir, simplemente indican que no sabemos si son KP o KI)Si A(i-1)=A(j-1) como estipulamos, entonces, dado que C(i-1)<>C(j-1) las Kx(3) han de ser distintas, por tanto tenemos una de la clave par y otra de la impar. Así pues:
Este es el primer paso. Veamos el carácter anterior. Estamos en C(i-2), C(j-2). Seguimos asumiendo A(i-2)=A(j-2) (aunque pueda parecer una condición muy fuerte no lo es tanto, puesto que si tenemos n carácteres del cifrado repetidos y vienen de secuencias del claro repetidas los L primeros carácteres de esa secuencia pueden tener una representación distinta en el cifrado si están afectados por alguna paridad diferente de los caracteres en claro distintos inmediatamente anteriores, por lo que será una cosa que normalmente nos ocurrirá. Ahora veremos un criterio para descartar los casos en los que sólo nos afecta la paridad)
Aquí tendremos la afectación de una clave más que ignoramos, que nos aportará una Kx(L-1), mientras que la desconocida de la posición anterior ahora nos aporta Kx(L-2). En el ejemplo:
Kx(2) proviene de la misma línea que nos dio Kx(3) en el caso anterior, mientras que la nueva clave que incorporamos nos aporta Kx(3)
Sabemos que las Kx(L-2) son distintas puesto que las Kx(L-1) lo fueron y pertenecen a las mismas claves. Así, la diferencia entre las C(i-2) y C(j-2) puede provenir de este hecho o de que las Kx(L-1) también lo sean. Se nos darán pues dos casos: Kx(L-1) provienen ambas de claves iguales o provienen de claves distintas. En el caso en que coincidan al xorear C(i-2) con C(j-2) se anularán, pero si son distintas estaremos en el caso del punto anterior y su XOR valdrá C(i-1)^C(j-1).
Así, en el ejemplo, tendremos las siguientes posibilidades:
Vemos claramente que xorear entre ambas expresiones nos dará de nuevo la expresión "mágica" C(i-1)^C(j-1). Este será pues un criterio para saber si aún podemos seguir asumiendo que A(i-2)=A(j-2), es decir al ir haciendo los xores entre los penúltimos carácteres antes de un n-grama los resultados han de ser de sólo de 2 tipos y el XOR entre ellos nos tiene que dar el número mágico (nuestro 19).
Esto que nos acaba de pasar lo tendremos también para caracteres anteriores. Podemos agrupar nuestros n-gramas repetidos de manera que tratamos juntos los que tienen el mismo valor para C(i-2)^C(j-2). Con esta restricción trataremos C(i-3), C(j-3), con los que de nuevo nos encontraremos con un elemento nuevo Kx(L-1) (de la clave nueva), un Kx(L-2) cuyo XOR hemos fijado al restringir C(i-2)^C(j-2) y un Kx(L-3) que proviene de la primera línea. También en este caso los XOR de los Kx(L-1) se comportarán igual, es decir o valen 0 o valen el número mágico. En el ejemplo:
Obtenemos pues 4 resultados equivalentes 2 a 2. vemos también inmediatamente que sus XORs respectivos nos darán el número mágico, con lo que lo podremos mantener el mismo criterio para saber si vamos bien.
De esta manera podemos construir un árbol binario con las relaciones entre las diferentes letras de las claves. Vemos que forzosamente deberán cumplir alguna de las ramas del árbol puesto que su XOR ha de ser un número fijo independiente del texto que estemos analizando. Si conseguimos suficiente profundidad del árbol (L en un caso ideal) podremos prefijar el comportamiento de todos los elementos de las claves. Esto nos dará 2**L casos a tratar por otros medios.
En nuestro caso particular, en el reto, las particularidades del texto claro nos echaron una buena mano. Por un lado tenemos muchas ocurrencias de n-gramas largos. Concretamente el n-grama "FPMP;NJY:X" aparece unas 20 veces y en algunos casos con bastantes caracteres previos comunes que apuntan a más letras compartidas ocultas. Los XORs entre todas las posibles parejas de n-gramas permitieron obtener unas 200 secuencias que, una vez agrupadas se resumen en el siguiente árbol:
Esta era una de las vías de ataque. Por otra parte se trataba de determinar la longitud de clave máxima. De nuevo la construcción del reto venía en nuestra ayuda: Los carácteres iniciales tenían un n-grama, concretamente "RW:_DF:JN" con la "casualidad" de presentar 7 caracteres previos al mismo distintos
Esto era tremendo, puesto que de una tacada fijaba el límite máximo para la clave más larga a 7 puesto que no podría ser superior y replicar la misma secuencia a esa distancia, ya que estaría afectada por distintos Kx(L-1). Al mismo tiempo estaba ocupando posiciones de inicio, que por construcción del algoritmo, tiene particularidades que más adelante aprovecharemos para determinar las claves.
Además, haciendo nuestro estudio de los carácteres previos al n-grama vemos que 3 de ellos cumplen el árbol. Esto, aunque es una ayuda, me despistó haciéndome pensar en una clave de 5, pero lo descarté rápidamente ya que la afectación provenía de otras fuentes como vi más adelante. En cualquier caso estábamos viendo que un mínimo de 6 letras compartia paridad entre las previas a los n-gramas y 3 de ellas además los textos claros. De ahí aventuré que el n-grama en claro repetido podría tener perfectamente las 16 letras comunes (ya tenía 12, sólo me faltaban 4 por lado que además cumplían paridad) con lo que era muy posible que se tratara del título del texto que se repitiera 2 veces. Asumiendo eso finalemente se obtienen las claves.
Con los datos que ya teníamos: árbol de relaciones y longitud máxima ya se podría atacar el cifrado con un esfuerzo aceptable. Sin embargo para reducir más el coste use un comodín, el del texto probable. Sabíamos que la cadena "EL_MUNDO_CIVILIZADO" aparecía en el texto claro. Mirando las relaciones que implica este hecho pueden establecerse los siguientes condicionantes sobre el cifrado para determinar su posición, asumiendo siempre una longitud de 7, ya que con ello cubrimos tambien longitudes inferiores:
(ver figura 1)
Es decir, si para una C(i) llamomos X(j) al XOR entre C(i+j)^S(j) siendo S el string "O_CIVILIZADO" entonces debe cumplirse que:
Además, como hecho determinante, buscamos el valor para esa posición de KP(6)^KI(6) que podemos obtener de las mismas relaciones puesto que
Buscando estas posibles ubicaciones obtengo un pleno en 31890 donde además de cumplirse las condiciones el valor para el número mágico implicado es 19. Bingo!. Además, al tratarse de Kx(6), se certifica que la longitud exacta de la clave más larga es 7.
Desde ahi ya todo es bajada. Establecemos las ecuaciones para esa posición
Añadimos nuestros condicionantes para parejas de XOR y resolvemos. Encontramos que efectivamente se adecuan a una de las ramas del árbol, con lo que encajamos ambas vías de ataque y obtenemos confirmación de todos nuestros supuestos
Desde este punto Agustín se lanzó a sus tablas de tetragramas y yo continué buceando por las relaciones XOR a la búsqueda de un resultado más genérico. Aquí rescaté la "piedra de rosetta", los 16 carácteres repetidos en claro del inicio. Sabía que la clave era de 7 con lo que tenía todo el bloque distinto cubierto por la primera clave par (si hubiera sido la impar de 7 habría llegado hasta C(7) y no coincidiría con el segundo bloque), con lo que los 7 distintos del segundo bloque tenían que estar cubiertos por la impar, puesto que C(6)<>C(22) y además C(6)^C(22)=19, nuestro número mágico, cosa que implica que el resto de secuencia de Kx es la misma.
Ahora bien, para la pareja C(6) y C(22) se reciben, en ambos bloques, 7 XORs con Kx, desde Kx(0) hasta Kx(6), con lo que obtener el 19 es normal. Sin embargo para C(5) y C(21) se reciben, en el primer bloque, sólo desde Kx(0) hasta Kx(5) mientras que en el segundo se recibe la secuencia entera. Esta diferencia, sin embargo no afecta a C(5)^C(21)=23 siguiendo aún así el árbol. La única explicación es que la KI(6) no le afecte en absoluto, con lo que no existe o vale "A" (lo mismo a efectos prácticos). Así pues tenemos ya la primera pareja:
KP(6)="S"; KI(6)="".
Para determinar la siguiente pareja volvemos a fijarnos en el XOR entre las C(i) implicadas C(4)^C(20)=12, que también sigue el árbol. En este caso nos faltan tanto Kx(6) como Kx(5) en C(4) a diferencia de C(20). Sabiendo que KI(6)="", para que este XOR siga el árbol, o bien KI(5) tampoco existe y la clave impar tiene longitd máxima 5 o bien KI(5)=KP(6) y se anulan en el XOR para C(20). En el primer caso si KI(5)=0 entornces KP(5)=23="W" y la clave par acabaría en "WS" cosa que descartamos. Así pues KI(5)=KP(6)="S" y KP(5)="E"
KP(5)="E" y KI(5)="S"
Para la siguiente posición ya hemos de contemplar más opciones puesto que ya no sigue el árbol. En la primera parte, en C(3) nos faltan Kx(6), Kx(5) y Kx(4) que si estarán presentes en C(19). Miramos a que combinaciones pueden corresponder al xorear C(3)^C(19)
Vemos que la única opción válida es
KP(4)="D"; KI(4)="O"
Seguimos este procedimiento y a medida que vamos descubriendo letras ya aceleramos buscando el string completo y acabamos obtniendo la pareja de claves
Que descifran el reto por
Que coincide con el texto (una vez normalizado) que puede encontrarse en la Wikipedia, en http://es.wikipedia.org/wiki/Albert_Einstein
Hay que destacar en este reto el trabajo de equipo. Tanto Agustín como Tokamak, con su desmenuzamiento sistemático del texto y localización de n-gramas (especialmente del primero, aunténtica piedra de Rosetta) han sido claves para tumbar a XOR2 y su complejidad.
Mi agradecimiento a Sqrmatrix y a todos los creadores de retos por hacerme más llevaderos los atascos de tráfico, donde nacen las más locas de mis ideas (algo de bueno han de tener).
PD. El CHE (Cifrado Homofónico Evolutivo) está ya rompiendo el cascarón. En breve haré su presentación en sociedad, no sea que os vayais a apoltronar en los laureles. XD
Imágenes:
Aplausos
Hay personas que ven con facilidad caminos que a otros nos resultan completamente invisibles. Creo que este ataque deberá grardarse para la posteridad, porque es un modelo en muchos sentidos.
Gracias, LlamameX
Esagerao!
Pero gracias mil. ;)
Además hay que resaltar la
Además hay que resaltar la calidad de la última explicación, extensa y con gráficos, un artículo interesantísimo por si misma.
Pues a la espera de quien diga otra vez "yo maté al Che" os recuerdo que TFTR 1.0 y 2.0 están mordidos y magullados, si, pero no acabados. Y ya pasan mucho del año...¿hacen falta más pistas?....
No lo olvido, no
Y de hecho tengo nuevas ideas para restringir el ataque. Como ya dije, claves de hasta 8 caracteres que cumplan trigramas tolerando hasta un fallo las obtengo en cuestión de horas. Dos o más fallos ya disparan los tiempos una barbaridad. Lo que tengo previsto para TFTR2 es un ataque en 3 fases, obtención del árbol XOR válido, poda en base a frecuencias y explotación. De esta manera se podrán aprovechar más los esfuerzos en caso de vueltas atrás parciales y reducir el tiempo global.
Pero dado que es un camino que hago muy solo, para mantener ocupada a la gente os dejaré a mi pequeña criaturita a la que ya le están saliendo los dientes.
Yo, de los TFTR, no veo
Yo, de los TFTR, no veo manera de hincarles el diente. Será que los cifrarios de transposición no son lo mío.
Por otro lado, opino igual que tú respecto de la última explicación de LlamameX. Y añado mi admiración por tus algoritmos genéticos, que se me olvidó indicar en el post en el que daba la enhorabuena, sobre todo cuando permiten descubrir cosas (como ha sido el caso en este reto, en el que se observó cómo claves totalmente distintas de las originales permitieron descifrar casi todo el texto del subreto) que quizá no se hubieran descubierto por los medios tradicionales
A mí no me liéis
A mi no me liéis con nuevos cifrados, que he decidido hacer un máster a base de estudiar la "solución" de LlamameX.
Nuevos no
pero hay te recuerdo que hay un señor -apellidado Sartori, Sertori o Sirtori- que lleva meses revolviéndose en su tumba...
¡Ostras!
Me había olvidado del muerto.
Páginas
opinar