Foros:
Por tokamak
Nota: Este cifrado se presentó en Kriptópolis.org el 30 de agosto de 2011. Deriva de una primera versión, que incluía un reto que aún continúa vigente. En la presentación original pueden encontrarse algunos comentarios interesantes para ayudar a su resolución.
Ha llegado la hora de actualizar TFTR, minimizando una característica de este cifrado que podría hacer viable el criptoanálisis del mismo. Digo podría, porque ni siquiera se ha demostrado la viabilidad de tal ataque. Pero vamos a poner el parche, antes de la herida.
Como sabréis, este algoritmo genera unos índices que se utilizan para efectuar una transposición del texto, pero con la característica de que cuando generamos un índice que apunta a una posición que ya hemos ocupado, hemos de recorrer el texto, desde esa posición, hasta obtener un lugar libre en la que situar el caracter codificado, lo que puede dar origen a la agrupación de algunas letras, disminuyendo así la calidad de la transposición.
La novedad que presento es que ahora los índices obtenidos no sirven para apuntar al texto, al menos directamente, sino a un vector que almacena las direcciones de las posiciones libres del texto; de esta forma calculo un índice, luego, con ese índice me voy al vector para obtener la dirección que me corresponde, y después de insertar el caracter, resecuencio el vector con todas las posiciones libres del texto, de manera que el caracter codificado siempre caiga en la posición generada por el algoritmo: así nunca hay que buscarle una libre si ya está ocupada.
He aquí el procedimiento en detalle; el algoritmo y el código fuente han experimentado una variación verdaderamente pequeña, sigue siendo un código muy simple y compacto, aún susceptible de llevarse con papel y lápiz..
Normalmente utilizo la tabla ASCII, pero en este ejemplo utilizaré un alfabeto reducido, de 32 símbolos; así con 5 bits me funciona el operador XOR de VB.
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 A B C D E F G H I J K L M N Ñ O P Q R S T U V W X Y Z _ . @ * ,
Por ejemplo, utlizamos la clave SANCHO para cifrar el primer párrafo del Quijote:
EN_UN_LUGAR_DE_LA_MANCHA,_DE_CUYO_NOMBRE_NO_QUIERO_ACORDARME,_NO_HA_MUCHO_TIEMPO_QUE_VIVIA_UN_HIDALGO_DE_LOS_DE_LANZA_EN_ASTILLERO,_ADARGA_ANTIGUA,_ROCIN_FLACO_Y_GALGO_CORREDOR.
Antes de nada, crearemos un vector, como máximo de 512 bytes, cuyos índices apuntarán a cada posición libre del texto:
Posición texto: 0 1 2 3...176 Indice vector..: 0 1 2 3...176
Después sumamos los valores de los caracteres de la clave:
S A N C H O 19 + 0 + 13 + 2 + 7 + 15 = 56
Ahora sumamos los dígitos del resultado:
5 + 6 = 11
multiplicamos este resultado por el anterior:
56 * 11 = 616
Ahora obtenemos el módulo con la longitud del bloque, 177. Normalmente serán 512 bytes, salvo, como en este caso, que el mensaje tenga menos de 512 bytes, o que el avance del descifrado vaya disminuyendo esa longitud, como veremos.
616 mod 177 = 85
Ahora nos vamos a la posición 85 de nuestro vector de punteros, para saber a que posición del texto apunta la dirección 85; resulta ser la 85.
Estas operaciones las realizamos para obtener la posición del caracter que vamos a cifrar; en este caso hemos obtenido la posición 85, que está ocupada por la letra V en el mensaje.
A continuación hacemos un XOR entre el valor del primer carácter de la clave (S) y V:
19 XOR 22 = 5
5 es el valor del carácter F que pasará a ocupar la posición 85 del texto cifrado.
A continuación marcaremos la posición 85 del texto, como ya ocupada y reconstruiremos el vector de punteros con las direcciones del texto, excluyendo las ya ocupadas y con hasta 512 direcciones como máximo.
Posición texto: 0 1 2 3...84 86 87... Indice vector..: 0 1 2 3...84 85 86...
De esta forma cada vez que se codifique un caracter, si el texto es lo suficientemente largo, el tamaño del bloque permanecerá invariable, en 512 bytes, hasta que lleguemos al final del texto, en cuyo momento el tamaño del bloque comienza a disminuir, mientras se completan los huecos que han ido quedado libres.
Además, la primera posición de la clave se cambia por V: VANCHO
Proseguimos con esta lógica y recalculamos el valor de la clave (el tamaño del bloque ha disminuido en una unidad):
22+0+13+27+15=59; 5+9=14; 59*14=826;826 mod 176=122
Ahora nos vamos a la posición 122 de nuestro vector de punteros, para saber a que posición del texto apunta la dirección 122;
resulta ser la 123:
Posición texto: 0 1 2 3...121 123 124... Indice vector..: 0 1 2 3...121 122 123..
La posición 123 está ocupada por la T. Haciendo un XOR con la segunda posición de la clave tenemos:
0 XOR 20 = 20
La posición 123 del texto cifrado será una T; además cambiaremos la segunda posición de la clave: VTNCHO.
Una vez que lleguemos al final de la clave daremos la vuelta, utilizando la primera posición. De esta forma la clave varía continuamente durante el cifrado, utilizando los caracteres del texto en claro, tomados de una forma no consecutiva.
El texto cifrado es:
ENAVX_DÑAEZ_VAÑEOJINCB.GP_W,YW*_EÑVDWÑRJTYLJVÑZRVIA_YL*._,J,GXAOTFLSMQYELTTZJLFTNAÑ@TFFVDHAÑAVOKMIQGPTXVWPT*P,GALE,YOWGR,_*TFEY,@,E,UFUBÑATAVOZTUCPPYEKM,<a href="mailto:JJO_BTXYP@AZHTXCJ">JJO_BTXYP@AZHTXCJ</a>,G_PT@*
El programa:
Function cifrar(clave_i, entrada_i, cifrar_descifrar) Dim mensaje() As String Dim clave() As String Dim ocupada() As String Dim puntero() As Long longitud = Len(entrada_i) lclave = Len(clave_i) ReDim mensaje(longitud) ReDim clave(lclave) ReDim ocupada(longitud) For i = 1 To longitud mensaje(i - 1) = Mid$(entrada_i, i, 1) Next i For i = 1 To lclave clave(i - 1) = Mid$(clave_i, i, 1) Next i cifrado = String(longitud, " ") posicion_clave = -1 longitud_bloque = resecuencia_puntero(puntero(), -1, mensaje(), ocupada()) For t = 1 To longitud posicion_clave = posicion_clave + 1 posicion_clave = posicion_clave Mod lclave j = sumar_clave(clave(), longitud_bloque) x = puntero(j) longitud_bloque = resecuencia_puntero(puntero(), x, mensaje(), ocupada()) letra = mensaje(x) y = inv_caracter(clave(posicion_clave)) Xor inv_caracter(letra) Mid$(cifrado, x + 1, 1) = caracter(y) If cifrar_descifrar = "C" Then clave(posicion_clave) = letra Else clave(posicion_clave) = caracter(y) End If Next t cifrar = cifrado End Function Function sumar_clave(clave() As String, longitud) total = 0 For i = 0 To UBound(clave) - 1 a = clave(i) x = inv_caracter(a) total = total + x Next i cadena = Format$(total, "000000") resuma = 0 For i = 1 To Len(cadena) resuma = resuma + CDbl(Mid$(cadena, i, 1)) Next i total = total * resuma total = total Mod longitud sumar_clave = total End Function Function caracter(numero) caracteres = Array("A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", _ "Ñ", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z", "_", ".", "@", "*", ",") caracter = caracteres(numero) End Function Function inv_caracter(caracter) caracteres = Array("A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", _ "Ñ", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z", "_", ".", "@", "*", ",") For i = 0 To 31 If caracteres(i) = caracter Then inv_caracter = i: Exit Function Next i End Function Function resecuencia_puntero(puntero() As Long, x, mensaje() As String, ocupada() As String) As Long If x > -1 Then ocupada(x) = "*" indice = 0: i = 0 Erase puntero Do If ocupada(i) <> "*" Then ReDim Preserve puntero(indice + 1) puntero(indice) = i indice = indice + 1 End If i = i + 1 Loop Until indice = 512 Or i = UBound(mensaje) resecuencia_puntero = indice End Function
Ok
Pues si, vale. Aguardo espectante el ataque, encima del árbol de abajo (y mira que puese el letrero...)
Imágenes:
Royendo otra pata
Posteo para que no creas que lo he dejado. Sigo en ello aunque los progresos son lentos.
El tema de las posiciones sigue siendo muy prometedor aunque cuesta encontrarle un exploit efectivo. En esa línea estoy puesto que en los ataques con texto claro, aunque me salen candidatos muy prometedores (como "LA_LUCHA" o "LAGRANGE") parece que al final, con tantas ampliaciones, se acabaría convirtiendo en simple fuerza bruta y querría evitarlo.
Pues buscando como sacar partido a la relativamente fácil obtención de las primeras posiciones del cifrado he dado con otra vulnerabilidad que también promete: A Los caracteres del texto claro se les hace 2 veces XOR, una cuando son texto claro y otra cuando son parte de la clave. Dado que podemos relacionar las posiciones de ambas situaciones podemos obtener mucha información de ahí.
Es decir si tenemos que para la primera posición de la clave K[0] le corresponde un caracter en claro A[i] que se cifra como C[i] (siendo i la posición en el bloque) tendremos
C[i]=K[0] xor A[i]
Después de terminar 8 pasos del algoritmo, en el 9º tendremos
C[j]=K[9] xor A[j], pero K[9]=K[0]=A[i] puesto que usamos de nuevo la primera posición de la clave.
Con lo que C[j]= A[i] xor A[j] = C[i] xor K[0] xor A[j]
Si calculamos
C[i] xor C[j] = C[i] xor C[i] xor K[0] xor A[j] = K[0] xor A[j]
Dado que las posiciones i y j pueden seguirse por el árbol binario que indicaba en el otro post podemos tener unos valores conocidos como C[i] xor C[j], con lo que tendremos dos valores relacionados con K[0].
ROC ROC ROC
Parece que te hemos dejado solo
Pero no es del todo verdad: Yo sigo tus avances con mucho interés, pero creo que llevas tanta ventaja que no creo poderte servir de ayuda.
Esto progresa
Sí, esto avanza y con mucha elegancia, además
La igualdad final:
C[i] xor C[j] = K[0] xor A[j] podemos obtenerla ya del paso inicial: C[j] = C[i] xor K[0] xor A[j] aplicando XOR C[i] a ambos miembros de la igualdad ¿no? no estoy familiarizado con el álgebra binaria.
Ps:
Resulta que pedí la camiseta con la leyenda (en su parte posterior: TFTR 2.0 THIS IS A CHALLENGE) ¿me dará tiempo a lucirla? en caso contrario ¿a quién reclamo yo? ¿al gremio de castores?
Nada, que no lo puedo dejar
No puedo dejar de darle vueltas al TFTR2 y mientras siga ahí poco puedo hacer en otros temas, léase Sertori. Así que vuelvo a la carga. Os pongo la explicación del último (y espero que definitivo salvo fuerzas muy brutas) ataque.
Ataque a TFTR
Sea C[Pi] el caracter cifrado que encontramos en la posición Pi y A[Pi] el carácter en claro que le corresponde. Sea Kj el caracter en la posición j de la clave. Pi será la posición en el bloque derivada de f(Si) donde Si=∑Kj
Sabemos
1. C[P0]=A[P0] XOR K0 => A[P0] = K0 XOR C[P0]
2. S1 = S0 + A[P0] - K0=> S1 - S0= K0 XOR C[P0] - K0
3. P0 =f(S0)=f(∑Kj; j=0..7) Esta función se calcula como el producto de Si por la suma de sus dígitos módulo tamaño de bloque y con la aplicación del vector de disponibles. Es un valor conocido para toda Si si se aplica en orden.
Ataque
Si evaluamos las posibles S0 como los valores entre 25 y 90 cubrimos el 95% de las posibilidades para ella. Para cada uno tendremos
S1 = S0 ±Dk, donde Dk son los posibles valores derivados de C[P0]. Habrá como máximo 2^n donde n es el número de bits a 1 de C[P0] (máximo 5) que representa las diferencias entre A[P0] y K0. Cada valor posible de S1 obtendremos un K0 y repetiremos el proceso para obtener valores de S2 y K1. Se continuará, aplicando los filtros siguientes, hasta obtener todos los valores Kj con j=0..7.
Filtrados:
Se filtrarán contra tabla de trigramas cada grupo [Kj ,Kj+1 ,Kj+2] j=0..5 a medida que se vayan obteniendo, debiendo obtener un valor positivo superior a 10. Si se incumple en cualquier punto se abortará ese camino. (Nota: se dispone de una tabla de unos 4500 trigramas posibles en castellano obtenida del análisis de 10 millones de caracteres en texto estandarizado)
Los caminos que concluyan con j=7 se filtrarán con la verificación ∑Kj = S0
Un conjunto K que pase los filtros se verificará como posible clave. La verificación será contra una tabla de máximos regenta. Se obtendrán los 100 primeros carácteres y si cualquiera de ellos supera el máximo admitido se dará como no válida.
Tabla de máximos regenta para 100 carácteres
Cómo se ve este ataque se basa en todas las cosas que he ido encontrando como debilidades hasta el momento. El número de iteraciones, sin embargo sigue siendo muy alto y ya pocas cosas más se me ocurren para acotarlas. Posiblemente lo acabe implementando como 2 fases, la primera hasta obtener los conjuntos K que pasen los 2 primeros filtros y una segunda de decodificación y verificación de máximos regenta sobre estos.
A título de curiosidad y por si a alguien le inspira también he analizado ataques parciales:
Por un lado, disponer del texto claro permitiría fácilmente obtener la clave usada en un cifrado con sólo buscar las posibles posiciones de inicio (A[P0]), ya que el doble uso de cada A[Pi] nos permitiría saber cuando estamos reusando el texto como clave Se valida así esa posición de inicio y se obtendría la clave con el XOR de los siguientes carácteres claro/cifrado. Con este método tampoco nos sería necesario saber previamente la longitud de clave, que podría ser aleatoria.
También podríamos descifrar fácilmente si supiéramos la secuencia exacta de posiciones (la transposición). De hecho el ataque explicado crece en iteraciones por no conocerla, generando un árbol de posibilidades 2^n (donde n es el número de bits a 1 del carácter cifrado). Si ese árbol fuera un único camino ya tendríamos los Si+1 en cada caso trivializando la obtención de las K, con lo que de nuevo sólo necesitaríamos obtener la posición de inicio.
Pues ya os seguiré contando
Muy interesante, haces bien
Muy interesante, haces bien en seguir pues tienes un ataque viable, que además has formalizado con mucho rigor, con esto podrías publicar un libro, e incluso un artículo académico, es mejor que muchos bodrios.
Una cosa: he dicho que la clave no es aleatoria, y no lo es, y además tiene algún significado, pero tampoco he dicho que los 8 caracteres conformen una palabra, pues haría trivial el ataque por diccionario.
No debería importar
Ya que los trigramas que uso para el filtro también contemplan el carácter espacio, con lo que aunque la clave esté formada por varias palabras no sería descartada
Tokamak, ¿Puedes hacer una prueba?
Hola,
Necesitaría comprobar que estemos haciendo las cosas igual. Estoy consiguiendo obtener las claves de 8 caracteres sin demasiados problemas cifrando con claves mías, pero con la del reto no hay manera. O una de tres, o mi implementación del algoritmo difiere en algún punto de la tuya, o la clave no me cumple los trigramas (cosa que podría ocurrir, por ejemplo, si hay más de una palabra sin separador "_" entre ellas, como "HOYLUNES", donde "OYL" no cumpliría), o el texto en claro está muy alejado del castellano tradicional (plagado de Ñs, Ws, @s, etc.).
Para descartar la primera te pediría si puedes probar la implementación en
http://llamamex.nixiweb.com/tftr/tftr3.html
a ver si codifica y decodifica igual que la tuya.
Saludos
DA LO MISMO
Cifrando el texto que tienes de La Regenta con la clave MAGISTRAL, yo obtengo:
De hecho ya me había dado cuenta:
Que es lo mismo que tú.
Anteriormente no daba lo mismo, (ojo el texto que empleé tenía un guón más al final que este)
http://www.kriptopolis.com/comment/858#comment-858
http://www.kriptopolis.com/comment/743#comment-743
Ahora parecen iguales ¿Qué está pasando?
Me lo miro
pero podría ser la causa por la que tengo menos neuronas vivas
Sí, da lo mismo, es que antes
Sí, da lo mismo, es que antes contesté que no porque utilicé la versión con el guión de más. Es igual.
Je je, lo único que te puedo
Je je, lo único que te puedo confirmar es que la clave es de 8 dígitos, que no es aleatoria y que es significante. El texto cifrado es un texto en castellano bien conocido y muy normalito en términos estadísticos. También reiterar que tu programa y el mío son exactamente iguales.
Qué emoción, por Dios! ¿quién necesita la Eurocopa, teniendo a LlamameX versus TFTR 2.0? Creo que están en la prórroga, no sé si terminarán a penaltis...
No des pistas
Ya bastantes datos tenemos. Esto ha de ser cosa mía en algún punto que aún no alcanzo a ver. Lo único que te pediría es que mires de usar esa implementación para descifrar el reto a ver si es capaz de hacerlo para descartar ese obstáculo. Siendo puristas eso ya es una ayuda extra de la que un criptoanalista no dispondría, pero bueno, mañana empiezan las rebajas parece ser.
Euroquecosa?
Con Java descifra OK
Eso, tu programa descifra el reto a la perfección, ya lo comprobé. No necesitas pistas, si acaso un vale para el dentista para un implante de incisivos, tras esta roída...
Comodín de la llamada.
En el punto en que estoy casi que me pido el comodín de la llamada. La distancia que separa mi ataque de la fuerza bruta cada día se va reduciendo y la única posibilidad es que la clave, aunque inteligible, no esté formada por palabras castellanas y sus separadores (o que usen sílabas rarísimas). Claves normales de 8 letras las ataco y como mucho en 24 horas las voy obteniendo, pero con el reto no hay manera.
A fin de comprobar esto último, te pediría si puedes comprobar si la clave pasa este test (no me digas que números salen), sólo si sale algún cero (tampoco digas donde)
http://llamamex.nixiweb.com/tftr/tritest.html
Si no aparece ningún 0 lo pasaría. En caso de que salga alguno implica que hay algún trigrama raro. Ya se que esto descafeina aún más el reto, pero ya sólo me queda la fuerza bruta y dejar un ataque total durante todo el verano.
PD. La clave hay que normalizarla a mano, que se me ha olvidado poner esa parte.
PD2. Si más no el reto ya me ha servido para hacerme un par de herramientas interesantes. El test de trigramas es una de ellas.
Clave del reto
Hola, bueno es que la clave es de solo 8 caracteres. Evidentemente con una longitud tan exigua no iba a utilizar frases como LA_CLAVE, o palabras o nombres de 8 letras que facilitasen un ataque por diccionario o por exhaución; no obstante reitero que la clave no es aleatoria, aunque no sea sencilla. Y no es rarísima, también significa algo, en realidad no es para tanto. En cuanto a tu test, sí que aparece algún cero.
Por cierto, y ya puesto a dar comodines, que no todo van a ser recortes, tengo que decir que la clave de TFTR 1.0 sí que es una frase.
PD. Genial que te haya servido todo esto para aumentar la panoplia de tu arsenal. Puedes dejar a tu programa que roya tranquilamente a TFTR y mirar algo del enigam Sertori, que reportaría a Kriptópolis y a tí no poca gloria.....
Me engorilé con los trigramas
La verdad es que es un filtro sencillo y efectivo, siempre y cuando podamos garantizar su cumplimiento. Asumí que ese sería el caso en el reto y lo he mantenido hasta la extenuación. Demasiado tiempo desde luego.
Descartado su total cumplimiento sólo queda o asumir un cumplimiento parcial o desecharlo completamente. En el primer caso estaré un poco como hasta ahora, puesto que no sabré cuantos errores de trigramas tolerar. Uno sólo sería asumible en tiempo de cálculo pero puede crear aún falsos negativos. Más de 3 incluirá demasiadas comprobaciones por paso de algoritmo y quizás no valga la pena.
Desechar este filtro nos deja a las puertas de la fuerza bruta, puesto que no tengo criterios válidos de filtro para no recorrer todo el árbol de posibilidades. Del texto claro no puedo sacar casi nada con sólo 8 caracteres y aunque tenga el árbol de posiciones precreado para cada suma los tiempos se me van a disparar.
En definitiva, dado que lo más asequible hoy por hoy es permitir un fallo de trigramas (un único 0 en el test) incluiré eso en mi ataque a ver si hay suerte. Calculo que eso, a ojo, puede suponer un tiempo de cálculo asumible, sin aumentar órdenes de mágnitud. Si esto falla publicaré los detalles de mi implementación a ver si a alguien le inspiran y me retiraré a mi cubil a lamerme las heridas.
Hola, tengo complejo de culpa
Hola, tengo complejo de culpa por la cantidad de tiempo que llevas invertido en esto. Entonces el algoritmo no es tan vulnerable como me llegó a parecer, puesto que una clave de 8 caracteres aleatorios podría causar bastantes dificultades, por lo que veo (y la del reto no puede calificarse de aleatoria).
Dicho esto, si necesitas más comodines, ya sabes donde estoy...
Uf engaña mucho
Hay caminos de ataque, pero son tortuosos. Es una especie de n ecuaciones con n+1 incognitas o parece seguir el principio de indeterminación de Heisenberg. Puedes fijar la distancia o el valor pero no todo a la vez. Todo acaba dependiendo de lo mismo, con lo que lo que parecen dos condiciones distintas acaban siendo casi la misma y dan poca información. No se si es un efecto buscado o fruto de la casualidad, pero le dan mucha robustez.
¡Qué nivel!
.
Hay que ver esta gente qué raro habla, pero parece que se entienden entre ellos, y todo. Creo que el Haloperidol me ha apartado para siempre de estas tertulias.
A ver si terminas pronto con el TFTR y vienes al Sertori, que estamos más secos que el desierto de Arizona.
Calla calla
que el TFTR2 me está dando el verano.
Dado que los trigramas es una vía muerta busco nuevas maneras de acortar el ataque. La única que me queda viva es aprovechar el doble uso de las Ai, una como carácter en claro y otra como carácter de la clave, aún así me está costando acabar de definirlo sin que implique un coste equivalente a una fuerza bruta total.
La idea, por si alguien más se apunta, es que podemos definir, a partir de los Ci el conjunto de todos los posibles Ci+1 sin necesidad de descifrar Ci y que sabemos que el número de esos Ci+1 estará entre 1 y 16. Así, a grandes rasgos se trata de construir el árbol desde un C0 hasta todos los posibles C7 (muchisimos. ahí el problema). A partir de ahí coger los K0 comunes a una rama para un determinado C1 y comprobar si obtenemos valores aceptables para A0 y desde A0 para A8. Si es asi subir un nivel por esa rama y repetir la prueba para K1 obteniendo A1 y A9. Si Llegamos a un K7 aceptable entonces aún tendrá que cumplir que la suma K0+...+K7=S0 corresponde a C0.
Las S0 a contemplar también están bastante limitadas ya que aunque los valores posibles serían entre 0 y 256, la suma seguirá una campana de Gauss, que además, si la clave no tiene carácteres raros, estará bastante desviada a la izquierda por que los valores más probables són bastante bajos.
Evidentemente se trata de encontrar algoritmos con pocas operaciones. Ya tengo bastante resuelto el tema de la gestión de los disponibles sin tener que enredar con todo el texto cada vez (uso los ocupados ordenando de menor a mayor y sumo 1 a la posición por cada carácter usado anterior o igual al actual) y reduzco el texto a tratar a 528=512+16. De esta manera en el peor de los casos sólo tengo que hacer 16 operaciones en cada carácter. También tengo acotadas las posiciones de las Ci+1 en una tabla a partir de la Ci y las Ki que pueden corresponder a cada Ci+1, con lo que ese cálculo es bastante ágil.
El problema es ir podando el árbol para evitar que crezca demasiado y eternice las comprobaciones posteriores. La principal gracia es que las Ci a partir de C7 són únicas puesto que podemos fijar los valores que nos llevan a ellas (las Ai que vamos comprobando). Una vez obtenido un candidato válido tengo ya un test bastante fiable para hacer una comprobación más exhaustiva generando los primeros 100 caracteres en claro y analizando el perfil de frecuencias que se obtiene.
Como idea en la que estoy ahora es en hacer un preanálisis generando todos los caminos posibles C0..C7 para todas las S0 analizadas en un fichero (calculo que ocupará unos 4Gb) pero que puede agilizar las comprobaciones posteriores, facilitando paralelizarlas.
Y hasta aquí el tocho.
Ala a seguir calentándome la cabeza por dentro y por fuera.
Santo cielo!, si lo llego a
Santo cielo!, si lo llego a saber no saco TFTR. No sé si tanto podar ramas del árbol de claves no se traducirá en un desbroce equivalente de neuronas del nódulo prefontal ¿y con LlamameX lobotomizado quién atacará a Sirtori? No sé si tendremos sitio para tantos en El Puzzle Asesino...
Si fuera yo quizá implentase un AG de los míos, pero la función de coste no sería la diferencia entre las frecuencias obtenidas y las esperadas de los bigramas y trigramas del texto en claro, sino las claves que generen mayor número de ramas con candidatos válidos.
Pos ya m'ha quedao claro
Tal como lo cuentas me recuerda los esfuerzos de Aureliano Buendía (Babilonia) para descifrar los manuscritos de Melquiades (Los Buendia llevaban un siglo intentándolo), y cuando por fin lo consigue, la profecía ya se está cumpliendo:
Ya que no te puedo ayudar, al menos te recuerdo estos fragmentos de esta joya de la literatura, donde se muestra, con gran belleza, el drama fundamental del criptoanálisis.
http://biblio3.url.edu.gt/Libros/100sole.pdf
Curiosidad más que vulnerabilidad
Durante mi última ausencia estuve pensando algún tiempo en este reto. Aprovecho un huequecito para hablar de dos observaciones que hizo LlamameX, que me imagino que él ya conocerá, pero que no se han expuesto aún. Como bien dice el título de este mensaje, esto es más una curiosidad que una vulnerabilidad.
La primera observación es la de que el método que determina la siguiente posición a cifrar normalmente no cubre de forma uniforme todas las posibles posiciones del bloque.
Partiendo de esto, y sabiendo que la clave tiene 8 caracteres, sabemos que la suma de los caracteres puede estar comprendida entre 0 (la clave es todo "A") y 248 (8*31, la clave es todo ","). Así, pues, esta suma podrá tomar como máximo 248 valores diferentes. Sabemos que la primera letra se obtiene multiplicando el producto de esta suma por la suma de los dígitos de la suma, y haciendo el resultado módulo el tamaño del bloque de datos con el que estamos trabajando.
Como el reto tiene un tamaño mayor de 512 caracteres, el tamaño de este bloque es de 512 caracteres. Así, pues, la primera letra que se codificará estará en una de, como máximo, 248 posiciones posibles.
No obstante, veremos que este número de posiciones distintas posibles será menor, y determinaremos cuáles son estas posiciones. Así, en un ataque por fuerza bruta, evitaremos empezar en posiciones imposibles para las condiciones indicadas.
Para ello, como no sabemos cuál es la suma de la clave, vamos a tratar con todas las posibles sumas, es decir, con todos los valores comprendidos entre 0 y 248, ambos inclusive. Esto ya lo hice para la versión anterior. Consiste en tomar un valor y aplicar el método indicado para calcular la posición de la primera letra a codificar. Con esto se obtienen 188 posibles posiciones donde podrá codificarse la primera letra. Todavía es mucho, pero al menos es mucho menos que 512. Éstas son las posiciones donde se puede codificar la primera letra:
0, 1, 3, 4, 5, 8, 9, 10, 11, 12, 16, 22, 25, 29, 30, 32, 33, 36, 38, 40, 48, 49, 52, 53, 54, 55, 56, 58, 63, 64, 66, 68, 70, 81, 84, 88, 90, 91, 92, 94, 95, 96, 98, 100, 104, 110, 112, 115, 118, 120, 122, 124, 125, 126, 128, 130, 135, 136, 139, 143, 144, 146, 148, 151, 156, 160, 162, 164, 169, 172, 175, 176, 180, 184, 188, 190, 191, 192, 197, 198, 200, 202, 203, 205, 208, 212, 217, 218, 220, 226, 227, 228, 230, 238, 240, 242, 243, 246, 250, 251, 252, 254, 256, 264, 268, 271, 272, 274, 277, 280, 281, 284, 285, 288, 290, 293, 296, 298, 301, 302, 306, 308, 314, 319, 324, 327, 328, 330, 332, 333, 334, 336, 337, 344, 350, 352, 353, 356, 359, 360, 362, 364, 365, 367, 368, 370, 384, 388, 392, 398, 400, 401, 405, 408, 411, 412, 416, 417, 418, 419, 424, 426, 427, 432, 434, 440, 444, 448, 449, 460, 461, 466, 468, 472, 474, 476, 482, 483, 484, 486, 488, 489, 490, 492, 496, 500, 503, 505
Por otro lado, puesto que en la clave, a medida que se va cifrando una letra del texto claro se sustituye una letra de la clave por ésta, y la nueva posición se calcula de la misma manera, estas posibles pociciones calculadas serán siempre las mismas mientras el bloque de datos con el que trabajamos tiene 512 caracteres, lo que reduce aún más el espacio de búsqueda, aunque sigue siendo excesivamente grande. No hay que olvidar que, una vez codificada una letra, ésta se descartará, de forma que todos los índices indicados antes, a partir del de la letra codificada, se incrementarán en al menos 1 (si el incremento de un índice coincide con una letra ya descartada, habrá que incrementarlo de nuevo, hasta encontrar una letra no descartada, y todos los índices a partir de él se deberán incrementar de la misma manera, repitiendo el proceso en caso de que alguno acabe apuntando a una letra descartada), aunque también puede verse como que se eliminará la letra, y todas las que hay a partir de ella se desplazarán una posición a la izquierda, con lo que los índices no cambiarán.
La otra observación que hizo LlamameX era sobre las operaciones XOR.
A medida que ciframos el texto, vamos sustituyendo las letras de la clave por letras del texto en claro. Cuando hemos recorrido la clave por completo, el resto de letras que cifran el texto son letras del propio texto, aunque desordenadas. Además, sabemos que estas letras no se repiten, ya que una vez cogida una de ellas, se elimina del bloque. Eso significa que, salvo por las letras de la clave, estamos cifrando el texto con el propio texto desordenado.
Este cifrado podemos verlo de esta manera. Tenemos el texto original, y una copia del mismo. Esta copia la desordenamos según indica la clave. Ahora colocamos el texto ordenado y debajo el desordenado, y obtenemos un nuevo texto haciendo XOR con las letras en las mismas posiciones. Después, puesto que las letras de la clave también participan de esta operación XOR, colocamos las letras de la clave en las posiciones que corresponda, y colocamos también las letras del texto desordenado en los lugares que ocupen las letras de la clave. Ahora hacemos XOR de estas letras, de forma que teníamos antes la codificación Li XOR Lj, Li la letra del texto claro, Lj la letra desordenada del texto claro. Lo que hemos hecho ahora es Li XOR Lj XOR Lj XOR Lc, con Lc la letra de la clave correspondiente. Puesto que Lj XOR Lj=0, nos queda lo anterior Li XOR Lc, que es lo que queríamos obtener.
Una curiosidad de este método es que, si no hubiéramos añadido las letras de la clave, y sólo hubiéramos hecho la codificación con las letras del texto desordenadas, podríamos hacer ahora la operación XOR de las letras del criptograma, de forma que al final hubiéramos obtenido 0 como resultado. Esto es porque cada letra está repetida dos veces, de forma que si las reagrupamos, tendríamos (L1 XOR L1) XOR (L2 XOR L2) XOR ... XOR (Ln XOR Ln)=0 XOR 0 XOR ... XOR 0=0.
Pero como hemos añadido las letras de la clave, y eliminado las correspondientes letras del texto desordenado, nos encontramos con lo siguiente: podemos ver la operación XOR con todas las letras del criptograma de la siguiente forma: seguimos los pasos indicados antes, es decir, hacemos XOR del texto en claro con el texto desordenado, y luego XOR con las letras de la clave y con las letras del texto desordenado correspondientes a las letras de la clave. Es decir, hacemos (L1 XOR L2 XOR ... XOR Ln) XOR (L'1 XOR L'2 XOR ... XOR L'n) XOR (Lc1 XOR Lc2 XOR ... XOR Lcm) XOR (L"1 XOR L"2 XOR ... XOR L"m)
El primer paréntesis corresponde con el texto ordenado, el segundo con el texto desordenado, el tercero con la clave, y el cuarto con las letras del texto desordenado que ocupan las mismas posiciones que ocupan las letras de la clave. Si agrupamos la operación de los dos primeros paréntesis, como vimos antes, el resultado será 0, esto es, (L1 XOR L2 XOR ... XOR Ln) XOR (L'1 XOR L'2 XOR ... XOR L'n)=0, con lo que lo anterior nos queda simplemente como (Lc1 XOR Lc2 XOR ... XOR Lcm) XOR (L"1 XOR L"2 XOR ... XOR L"m). Y aquí está la curiosidad, porque el conjunto de operaciones se corresponde con la operación XOR de las letras del criptograma y, como vemos, el resultado es el mismo que el de las letras de la clave con las letras del texto desordenado que han sustituido. Lamentablemente, esto no nos ayuda mucho.
El ataque que propone LlamameX, si lo he entendido bien, nos va proporcionando claves candidatas. Si pudiéramos conocer las supuestas letras desordenadas que les corresponden, podríamos quizá acelerar los tests, porque supuestas las letras de la clave Lc1, Lc2, ..., Lcm, y las del texto desordenado que les corresponden, L"1, L"2, ..., L"m, bastaría hacer XOR de todas estas letras y comparar con la operación XOR de las letras del criptograma (operación que sólo hay que hacer una vez) para poder descartar el candidato si no coinciden. Esto seguramente aceleraría el ataque propuesto por LlamameX. En teoría, sólo 1 de cada 32 candidatos pasaría este test. Lo malo es que lo único que podemos obtener con las supuestas letras de la clave son las supuestas letras del texto claro que les corresponden, y no se me ocurre cómo obtener estas supuestas letras del texto desordenado de una forma rápida. Estas letras sólo se pueden obtener, que yo sepa, cifrando por completo el texto. Simplemente, hacemos una copia del texto ordenado, y a medida que vamos tomando letras del texto para incorporarlas a la clave, las vamos eliminando de la copia del texto claro. Al terminar el proceso, las letras de la copia del texto claro que queden serán las letras L"1, L"2, ..., L"m. Esto hace el proceso muy lento para el ataque. Quizá a alguien se le ocurra una forma más rápida de obtener estas letras. Si fuera así, el ataque de LlamameX podría acelerarse al eliminar falsos positivos. O quizá a alguien se le ocurra la forma de obtener estas letras L"1, L"2, ..., L"m del criptograma, lo que permitiría obtener el valor de la operación XOR de las letras de la clave y utilizarlo para descartar falsos positivos.
Haciendo XOR en los caracteres del reto, obtengo como resultado 12. Es decir, que si lo que he expuesto es correcto, y la operación la he hecho correctamente, eso significa que la operación XOR entre los caracteres de la clave y los que sustituyó la clave dan como resultado 12.
Por otro lado, y como se ha visto antes, este cifrario parece un cifrario con clave pseudoaleatoria, pero los caracteres de esta clave tienen estadísticas muy parecidas a las del texto claro que se cifra (la única diferencia son las letras de la clave). No sé si para esto existe alguna forma de atacar directamente. Lo único que se me ocurre es lo que ya expuse en su día para la versión anterior, y es hacer XOR con espacios con la esperanza de que haya un grupo de espacios seguidos en la clave lo suficientemente grande como para desvelar alguna palabra relevante, pero parece que no funciona. Con la letra "E" también he probado, y la única palabra que he visto ha sido "LEJOS", cerca del final, pero ni siquiera sé si es una palabra del texto original, o una coincidencia. Aunque obtuviera alguna palabra, esto no permitiría obtener el resto del texto. Podría obtener todos los textos, cada uno aplicándole XOR con una letra del alfabeto, e intentarlos combinar para obtener palabras, pero no creo que se pudiera avanzar así.
Apuntes a tus apuntes
Aunque tengo algo arrinconado (aunque no totalamente olvidado) a TFTR, hay algunas cosas del ataque que me vienen ahora a la cabeza.
- Por un lado, trabajo sólo con las sumas y considero la posición a la que se refieren como una función que depende de ésta (y de los huecos que vamos creando y que se van llenando con caracteres posteriores).
- No ataco el texto en claro. Demasiado complicado. Voy a por la clave que sabemos que también sigue una distribución de texto en castellano.
- Relaciono la posición de siguiente caracter en base al XOR que se realiza. Esto me genera una serie de posibilidades (no muchas) puesto que por un lado la siguiente suma es igual a la anterior menos el caracter que se va más el caracter que entra, y por otro el caracter cifrado de la posición actual es el XOR con el caracter que se va. Así la distancia desde la posición actual a la siguiente esta condicionada por ese XOR, pudiendo ser de 2 a 16 posibilidades. Ese árbol que se genera puede irse podando por que al final las Ki que van saliendo tienen que sumar la posición inicial, así si ya no podemos llegar o nos pasamos no hace falta seguir por ese camino.
- Por otra parte no hace falta explorar todas las posibles posiciones para la primera suma. Aunque sean posibles, la distribución de probabilidad para un texto en castellano seguirá una campana bastante acotada.
- Dado que a medida que avanzamos rellenamos los huecos en el bloque con los carácteres siguientes (vamos colapsando el texto) y que limito el ataque a la longitud de clave necesitamos sólo analizar el texto cifrado correspondiente al bloque + los 8 caracteres siguientes.
- Para agilizar el ataque, dado que sólo trataremos 8 huecos es más eficiente sumar 1 a la posición por cada hueco anterior a la posición actual que hayamos dejado que colapsar todo el texto cada vez.
- Una vez obtengo un candidato se testea descifrando con el los 100 primeros carácteres y calculando la distancia de lo obtenido con una distribución tipo Regenta.
- Mi ataque obtiene la clave si ésta cumple (no es el caso del reto) la restricción de que todos sus trigramas sean posibles en texto castellano (incluyendo espacios y estructuras tipo A_B). Lo dejé aparcado mientras estudiaba nuevas formas de poda del árbol aunque tenía un par de ideas al respecto.
Esto es lo que tengo en la cabeza ahora respecto a TFTR, tendria que hacer memoria del tema y la tengo bastante ocupada con FOTP :). A ver si algo de todo esto te sirve para alguna cosa, que demasiado tranquilo estaba Tokamak con su monstruito.
Pues menos mal que lo tuyo no
Pues menos mal que lo tuyo no son los cifrados de bloque, menudo repaso le acabas de dar, eso sí, no andas muy acertado con lo de la palabra LEJOS. No aparece en todo el texto.
Efectivamente es un cifrado pseudoaleatorio, como todas mis autocifras, al final las estadísticas son muy parecidas a las del texto original. Pero he comprobado que esto no ayuda, el mensaje es desconocido por el atacante y es una fuente ofuscación mejor que cualquier generador pseudoaleatorio.
Los dos habéis podido con los cifrados más complejos, basados siempre en paradigmas estrictamente matemáticos, pero mis trastos , aún siendo más simples, parece que duran un poquitín más. Cifrar con el mismo texto, y con muy poco código: Ese es mi ideal, mi Grial, aunque el que he posteado no sea, todavía no, el Santo Grial. Estoy explorando otras fuentes de azar, como la semántica del texto, junto a un generador pseudoaleatorio. Pero para después del verano...
Páginas
opinar