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 creo que sea fácil
Más bien creo que resultará un monstruo, porque cada letra se cifra chopocientas veces. Al menos el alfabeto no está desordenado, por esta vez. Le echaré un ojo en cuanto tenga un rato, que ahora no tengo tiempo, también por circunstancias personales, ni para el Sertori, donde, por cierto, te esperamos ansiosamente.
Bueno, si vemos que es
Bueno, si vemos que es demasiado difícil, siempre se puede dar alguna pista.
Con respecto a Sirtori, tendré que leerme todos los posts (!!!), porque tampoco pude seguir el progreso, y ahora mismo he perdido el hilo de lo que se había hecho al principio. Esta vez no he podido seguir los posts de Kriptópolis, salvo alguna vez esporádica que pude echar algún vistazo breve a lo que se había publicado. Tengo que ponerme al día.
¡Nada!
¡No hemos conseguido nada!
Bueno, Eloy ha propuesto una solución completa, pero algunos tenemos serias dudas al respecto.
Hecho, si que se ha hecho: las transcripciones de los garabatos, que no es poco; básicamente las realizadas por Tokamak y Asier. Yo he intentado algo, pero con la poca vista que me queda, y las bombillas de bajo consumo que hay en la clínica, ni te cuento. También ha habido muy buenas aportaciones sobre el contexto, es decir, sobre quiénes eran los personajes implicados, y cómo se escribía en aquella época, hechos relevantes, etc. De hecho, los principales avances vendrán seguramente de los ataques a las firmas, salutaciones y despedidas, espero.
Yo ya estoy tratando de implementar tu monstruo. Creo que lo primero que te pediremos será la longitud de las p. claves, pero en su momento.
En Sirtori he echado un
En Sirtori he echado un vistazo por encima de la solución, y la verdad es que me he quedado boquiabierto, ya que a primera vista parece una solución válida. También he visto por encima algunos comentarios en los que no se cree que esa sea la solución definitiva. A ver si me lo leo todo con calma para enterarme de cómo están realmente las cosas.
Parece bastante duro
El uso de las dos claves y la dependencia del mensaje en claro deja muy pocos (si es que hay alguno) resquicios por donde atacar. Demasiadas incógnitas. Como ya apunta Agustín, los carácteres centrales se cifrarán, como mínimo, tantas veces como la longitud de la clave más corta. Las únicas debilidades (por llamarles de alguna manera) que veo a priori són:
- El primer carácter se cifra una única vez y con la clave par.
- No hay desorden, cosa que abre la puerta a buscar palabras.
- Por frecuencias (aún no lo he mirado) seguramente una clave se usará más que la otra. Podrían buscarse grupos silábicos que se trataran con una única clave al principio del mensaje, donde habrá menos aplicaciones de xor.
- Las claves no evolucionan.
Ahora, no creo que pueda sacarse sin un esfuerzo titánico.
O sea
O sea, que si por ti fuera, aún sería peor. No, si ya te conocemos, ya....
Recuerda que un reto imposible acaba perdiendo todo interés. Supongo que en eso ha pensado el autor al renunciar a esos y a otros retortijones..., que diga..., retorcimientos.
Implementación
Este monstruito promete ya que emplea autocifra, al ser dependiente la clave a utilizar del propio texto.
No sé si se podrá descifrar. Pero me gusta mucho porque hace gala de una gran simplicidad funcional, y creo que he demostrado (hasta ahora) con TFTR, que eso es algo no está necesariamente reñido con la seguridad del algoritmo.
De momento os doy mi habitual implementación en VB. Hasta donde he podido probar con el ejemplo, funciona bien.
A la función "cifrar", le pasamos: la clave impar, la clave par, el texto en claro o el cifrado sgún el último parámetro: "C", si es cifrar, y "D" si queremos descifrar. Obviamente devuelve el texto en claro si desciframos, o el cifrado en caso contrario.
Mas de lo mismo...
... pero en Python. Temo no poder ayudar en el descifrado del mensaje, pero si que puedo contribuïr con algo de código fuente. Este algoritmo se podría optimizar *bastante*. Ahora solo podemos cifrar/descifrar 2.500 veces el texto propuesto por el artículo en un segundo. Lo digo por si alguien quiere usar éste código para intentar algún ataque de fuerza bruta, que avise e intentaré optimizarlo lo mas que pueda.
Nótese que todos los strings se deben especificar con la notación u"PRUEBA" y no "PRUEBA" (nótese la "u" del principio). Esta "u" significa UNICODE, necesario para cuando se trata con secuencias no ASCI en Python (como el caráter Ñ de los coj**es). También es imprescindible la primera línea comentada del programa, ya que se instruye al intérprete de Python que el código fuente del programa contiene caráteres Unicode.
Espero que les sea útil. Un saludo.
El XOR no es lo que parece
Sumándome a la búsqueda de debilidades de LlamameX, hay que tener encuenta que al recifrar n veces con XOR hay una probabilidad no nula de que se acabe dejando el carácter multicifrado con el mismo valor que tenía en el texo plano, especialmente, pero no solo, creo, si las claves tienen letras en común, aunque sea en distintas posiciones. Todo eso no significa que sea fácil explotar esta supuesta debilidad, ya que la probabilidad de que le ocurre eso a varios caracteres contiguos es muy pequeña. De hecho, un vistazo al texto cifrado no muestra ninguna agrupación de caracteres que pueda parecer un fragmento de palabra. De todos modos, un primer ataque podría ser determinar los n-gramas del cifrado, hasta n=4, por ejemplo, y ver si se encuentra algo.
Por cierto, que fiera Tokamak, con la implementación ya hecha. Yo aún estaba programando con la lengua doblada entre los dientes, y emitiendo el clásico ruidito "¡Gñññ!" de la torpeza. Menos mal que esta actividad -la de la lengua, no la de programar- es habitual en la clínica, y no llama la atención de los vigilantes.
¿Mi criaturita un monstruo?..
¿Mi criaturita un monstruo?... ¡guau!, me siento como Frankenstein cuando creó a su monstruo. De todas formas, creo que podréis con él.
Si os digo que mi primera opción era hacer este cifrario en binario, es decir, transformar claves y mensaje a binario, e ir bit a bit haciendo lo mismo. Si el bit anterior era 0, cogía la clave par (que la llamaba clave 0), y si era 1, cogía la clave impar (que la llamaba clave 1) y hacía XOR bit a bit. Luego, la ristra de bits obtenida se reconvertía a caracteres. Esa opción me pareció excesivamente difícil para atacar.
Por cierto, se me olvidaba mencionar, aunque creo que ya se daba por supuesto, que en el texto, los caracteres con tildes y demás parafernalia se transforma a caracteres normales, que los caracteres que no aparecen en el alfabeto se descartan, y que los dobles espacios se eliminan, no dejando dos o más espacios seguidos. Que después de cada signo de puntuación suele haber un espacio (salvo los puntos suspensivos, en los que hay un punto detrás de otro), aunque no puedo asegurar que esto se cumpla siempre (no lo he comprobado), y que pueden aparecer nombres propios y palabras/combinaciones de letras que no aparezcan en diccionarios, éstas últimas debidas a iniciales o a la eliminación de caracteres, y puede que a errores en el texto original.
No servirá de nada
No servirá de nada, pero como no se me ocurre nada mejor, he vuelto a lo mío, que son la tablas. En la suposicion de que los XOR múltiples puedan dejar la letra en claro, y suponiendo -que ya es suponer- que esto pueda ocurrir en posiciones correlativas, he obtenido los digramas del cifrado, con las siguientes reglas:
1. No se cuentan los digramas que contengan signos de puntuación o el separador
2. No se cuentan los digramas "casuales" que sólo aparezcan una vez
Y obtengo esto:
Llama la atención que no aparezcan digramas con frecuencias bajas, como 2, 3..., siendo el valor mínimo 9.
También es curioso que haya una gran desviación en las frecuencias, que varían gradualmente. según se ve en el gráfico adjunto, y cuya ley no puedo interpretar, aunque supongo que coresponde a un resultado bastante aleatorio.
Aparecen algunos digramas "reconocibles" con frecuencias relativamente altas, como
¿Que para qué sirve esto? Para nada, supongo. En el caso de que se considerara posible que se formaran digramas "transparentes" al cifrar con los múltiples XOR, podríamos ver las posiciones en que aparecen, para tratar de buscar alguna regularidad, algo al estilo Kasiski. Pero no estoy nada optimista al respecto.
El otro ataque, como sugería LlamameX, sería a partir de la primera letra, que sólo se cifra una vez con la primera letra de la clave par. Podría especularse con la primera letra del texto en claro, que podria ser una A, o una E, (hay menos palabras que empiecen por I, O o U) o alguna consonante frecuente como S, L, M..R. (hay menos palabras que empiecen por N, G o H) aunque estas hipótesis deberían fundamentarse estadísticamente para no hacer pruebas inútiles. Entonces tendríamos una serie de candidatos a la primera letra de la clave par, que suponemos será una palabra legible. Creo que esta vía ofrece más posibilidades, aunque no será fácil.
Imágenes:
Todas las aportaciones son
Todas las aportaciones son bienvenidas, sobre todo en este mi primer planteamiento de reto. La verdad es que impresiona el trabajo que has hecho.
Con respecto al gráfico, se parece un poco a la inversa de la raíz cuadrada, aunque no creo que sea tan simple. Adjunto imagen.
Imágenes:
Sí que se parecen
Sí que se parecen, pero en el gráfico del cifrado las abcisas no corresponden a una variable numérica, sino a los digramas ordenados por frecuencias decrecientes, sin que los valores de la x guarden ninguna relación expresa con tales frecuencias. No obstante, tal vez haya una relación más profunda, entre la función que propones y la aleatoriedad del invento.
Para descifrar (o intentarlo) con lápiz y papel
A fin de que cualquiera pueda intentar resolver el reto, aun sin disponer de herramientas de programación, aquí pongo la tabla de los XOR de todas las letras con todas las letras
Por ejemplo, la primera letra del cifrado, que es una G, se obtiene por un XOR entre la primera letra del texto en claro, y la primera de la clave-par, por lo que habría 32 posibildades, que son éstas:
y todas sus recíprocas
Por cierto, ¿podríamos disponer de la implementación del DESCIFRADO en uno de los mundialmente famosos JavaScritps de LlamameX? Ya sé que es faena, y estamos en temporada estival, pero ten en cuenta que eso ya se ha convertido en una tradición, y así cualquiera podría trastear, haciendo ataques a las claves. Así será mucho más entretenido y más social. Venga, hombre.
Ejemplo de ensayo con lápiz y papel:
0. Numeramos el alfabeto
1. Elegimos una supuesta primera letra para la clave-par. A veces los miembros de Kriptópolis homenajean a la página usando esta palabra en las contraseñas, aunque puede que éste no sea el caso. Tomaríamos entonces la K
2. XOR K G = M (en la tabla)
Si fuera M la primera letra del texto en claro, como resulta que ocupa la posición 12, se trata de una letra par (no creo que tengamos tanta suerte)
3. Entonces, la segunda letra del texto en claro habrá sido XOReada con la R (segunda letra de la clave), en la primera pasada, y con la K, en la segunda. Como la segunda letra del cifrado es el punto y coma ";", tendríamos:
segunda letra = XOR (; K R) (mantengo la notación prefija para XOR).
.
4. Como la operación XOR es asociativa podemos hacer primero XOR K R = X
5. Y ahora XOR ; X = H
Desgraciadamente es poco probable que las dos primeras letras de la primera palabra sean MH. Cachis, mala suerte.
(Todo eso si no me he equivocado)
Pero podemos seguir probando, porque uno de los p. 32 signos ha de ser la primera letra de la clave par, y no todos se usarán para inicio de palabra, si este hombre ha tenido la decencia de elegir claves legibles.
JavaScript vaaaa!!
Creado un pequeño JS para DESCRIFRAR mensajes cifrados con Doble XOR (NO vale para cifrar)
http://inedit00.github.com/xor2
O el código para quién quiera jugar/modificarlo:
http://pastebin.com/HdsP6aSZ
Temo que no sea algo tan complejo como el que hizo LlamameX para el cifrado "tftr", pero si queréis alguna mejora no dudéis en pedirlo (para algunos el verano significa VACACIONES INFINITAAAAS! jeje).
Un saludo! Espero que les sea útil!
Se agradece
Sobre todo para quienes no dispongan de herramientas de programación. Observo, no obstante, que no acepta el carácter "_" al escribir las claves.
Fixed
Sorry por eso. El carácter "_" si estaba funcionando, solo que había dejado demasiado poco espacio en el "input" para que se mostrata. He ampliado el tamaño del layout en general y ahora se ve mejor. También he incluído tu tabla de Cifrario XOR que me parece muy útil para ir haciendo pruebas.
Me da error
Cuando pulso el botón "Descifrar!" me da error. Indica "texto_cifrado no está definido"
Jummm
Temo no haber podido probar el programilla en todos los navegadores. Lo he probado en Firefox (14.0.1) y Chromium (20.0.11), ambos en Debian/Testing y sin problemas. Aún así ya he subido el fix al repositorio y en unos 10 minutos aproximadamente debería estar ya en la web.
Gracias por el reporte! Si te sigue dando problemas o encuentras alguna otra cosa, dímelo y me lo miro =)
En firefox funciona
Es verdad, que el el carácter "_" lo procesaba, pero no lo mostraba-
Ya lo he probado
Bueno, en IE sigue sin funcionar, pero lo he probado en Firefox y funciona correctamente. He descifrado el reto con él y lo descifra correctamente. Gracias por el JavaScript.
64 bits, me encanta
toma variable
Tranquilo Agustín...
...que las claves son perfectamente legibles y están formadas por palabras normales.
Por cierto, aprovecho a decir que, después de echarle de nuevo un vistazo al texto original, parece que no siempre se cumple la regla de un signo de puntuación seguido de un espacio. A veces aparece alguno seguido de una letra. Lo digo por si alguien se encuentra con la decodificación de un punto, coma, dos puntos o punto y coma, que sepa que no siempre estará seguido de un espacio. Esta comprobación no me dí cuenta de hacerla antes de enviar el reto, porque en un primer vistazo no ví que ocurría esto.
Ingeniería social
Obsérvese que el autor dice:
No dice que las claves SEAN palabas normales, sino que ESTÁN FORMADAS POR palabras normales. O sea que cada clave tiene varias palabras, normales, eso sí. Descartaremos "EL LENGUADO ES UN PEZ ACANTOPTERIGIO".
Apañaos estamos.
Forma parte de mis malvados planes...
...confundiros. Pero no, es mi primer reto planteado y no quiero empezar con mal pie. Puedo aseguraros que las claves son sencillas y fáciles (oséase, cortas y con palabras normales). Y además, estoy seguro de que le podéis dar una buena detellada (otra cosa es que esa dentellada lo acabe destruyendo, que puede ser, no lo he comprobado). Sólo tenéis que saber dónde... o mejor dicho, cómo...
Descartes
Si aceptemos la hipotesis de que ni la primera palabra del texto ni la clave, empiecen por ninguno de los caracteres del conjunto
Y tenemos en cuenta la lista de pares de letras que darían la letra G, podemos eliminar también el conjunto
Lo que nos dejaría "sólo" 18 letras disponibles
Estas letras serían iniciales de texto y de la clave, emparejadas de la siguiente forma, según la tabla de XOR
o al revés, claro está.
Aunque se ha reducido a casi la mitad el número de letrar válidas, el problema sigue siendo enorme.
Y me pregunto: ¿por qué me meteré en estos líos?
Primera palabra
De manera oscura y nebulosa empiezo a ver.... CIVIL, CIVILES., CIVILIZACION... no veo bien, ¡estas gafas!
P.S.
¿Civiles y castellanos nos niegan hasta la sombra?
Administrar un reto
Esitmado y admirado sqrmatrix. La presentación de un reto implica cierta responsabilidad. No basta con crear un buen algoritmo, hermoso (cuanto más simple más hermoso) y sólido (tampoco debe ser tan sólido que no haya ninguna posibilidad de romperlo, con los medios de que habitualmente disponemos las gentes de a pie). Hace falta, también, actuar como "mantenedor", interaccionando con el público, dando alguna pista cuando la cosa se atasca, y comentando las aportaciones del personal, porque el esfuerzo de los atacantes merece siempre un reconocimiento, aunque sea para decirles: "No, no va por ahí la cosa".
En suma, que hay que visitar la página con relativa frecuencia para ver cómo van las cosas. En este sentido estoy quejoso, porque ya hace dos días que aventuré un posible hallazgo (que no solución) sobre el cifrado, y no te has dignado contestarme.
Perdona, Agustín. No era mi
Perdona, Agustín. No era mi intención que pareciera que he desatendido el reto. He estado mirando la página estos días y he seguido lo que la gente va poniendo.
En tu caso, en el que has propuesto unas palabras, no he dicho nada porque pensaba que en los retos se prefiere dejar las pistas como último recurso, y sólo cuando se pide confirmación es cuando se da la pista o la respuesta a la pregunta. Así es como he participado yo en los demás retos, he hecho algunas propuestas, pero sin intención de que me las confirmen, sólo para que los demás las consulten, den su opinión, y hagan sus comprobaciones. La pista se daría cuando se pidiera.
En respuesta a tus propuestas de palabras, he de decir que sí, que en el texto aparecen las palabras CIVILIZADO y CIVILIZACION.
Y con respecto a comentar los comentarios de otros, tampoco quiero poner un comentario mío por cada cosa que alguien ponga. Quizá tenga que poner algo más de mi parte, eso sí, y alcanzar el equilibrio me va a costar un poco. Pero bueno, con vuestros consejos, como el que me has dado, y que se agradecen, seguro que puedo mejorar.
Gracias
Gracias, compañero. Pido perdón por haber precipitado el dar alguna pista. Tan sólo qería alguna respuesta. No te pido que confirmes ni desmientas, si no es el momento, pero a mi lo que me sale al principio es: "CIVILES_Y_CAST" (¿Civiles y castellanos?).
Para el público en general: No he podido (sabido) atacar el algoritmo, por que lo que he montado un ataque a las claves, algo patatero, eso sí.
Descripción del ataque:
Jugando con lo que yo pensaba que podrían ser las claves de sqrmatrix (que no revelaré, de momento) me sale esa secuencia que he puesto. Primero encontré el fragmento "CIVIL". Trajinando un poquito más, probando también la clave impar, me apareció la palabra "CIVILES". Frenéticamente me lancé a aporrear las dos claves y salió la serie "CIVILES_Y_" Entonces traté de ver si aparecía "CIVILES_Y_SOLDADOS" o "CIVILES_Y_MILITARES, pero me encontré con "CIVILES_Y_CAST", que sqrmatrix ni confirma ni desmiente, al menos de manera exacta.
Buscando en la Red, he encontrado la expresión gitana "Civiles y castellanos nos niegan hasta la sombra", donde por "castellanos" se refieren a los no gitanos, en general. Pero mis tejemanejes con las claves no me permiten ir más allá. No dejo de pensar que probando claves al tuntún se puedan generar textos cualesquiera, pero -corregidme si me equivoco-, la probabilidad de que combinando claves legibles salga un fragmento de texto descifrado legible y distinto del verdadero, debe ser muy pequeña.
Si esto se demostrara cierto, tendríamos que el algorimto es vulnerable a las claves, por las debilidades que señaló LlamameX, concretamente, que la primera letra se cifrara sólo una vez con la inicial de la clave-par. Pero además, ocurre que las claves -y esto es un hecho- pueden ser buenas o malas con respecto al texto en claro. Peor aún, los textos pueden ser buenos o malos para el algoritmo. Es altamente indeseable que al principio aparezca un grupo seguido de letras pares, porque en ese tramo la segunda clave es inoperante. Concretamente, si la palabra "CIVILES" fuera correcta, nos encontramos con que la C, la I y la V son pares, por lo que que la segunda clave no actúa hasta la sexta letra, dado que la primera impar es la letra L que aparece en la quinta posición. En suma. que trasteando sólo con la clave par podría aparecer el fragmento "CIVIL".
A ver si esto sirve de algo.
Pequeña, pero no nula...
...es la probabilidad de que trasteando con diferentes claves legibles salga un fragmento de texto legible, como acabas de demostrar. Y es que la palabra CIVILES no aparece en el texto original. Las únicas relacionadas son las que ya he indicado, CIVILIZADO y CIVILIZACION, y no aparecen al principio ni cerca del principio. El tema que he elegido del texto tampoco se parece en nada a lo que has mencionado.
La verdad es que me sorprende que hayas conseguido ese texto con claves legibles, texto que no se parece en nada al original del reto. Quizá este cifrario sea capaz de engañar a quienes le atacan y darles falsas esperanzas de que le están venciendo...
¡Cagontó!
Ya me parecía a mí demasiada suerte. Gracias, compadre.
Pues va a ser eso...
El cálculo de probabilidades...
... y las tribulaciones de un criptoanalista mindungui.
Pues resulta que tomando como clave par
que podría ser el inicio de algo como "esta vez kbytes no os van a faltar", o sea, que tiene sentido.
Y como clave impar
(aunque infrecuente en la vida ordinaria, MUFLA es una palabra del diccionario)
Pues bien, así se obtiene lo de
Cosas veredes.
Sospeché que algo no iba bien, cuando vi que no progresaba el descifrado al tratar de completar las claves.
Pero insisto en que un texto que empezara por un grupo de letras pares, sería vulnerable bajo el ataque a la clave.
Curioso
Es curioso cómo claves con sentido generan un texto con sentido, a pesar de no ser las correctas.
Con lo de la vulnerabilidad que indicas estoy de acuerdo. Sería equivalente a un XOR normal, hasta que se encuentre la primera letra impar. Las letras pares serían "ACEGIKMÑPRTVXZ.:". Todavía se pueden formar bastantes palabras con ellas.
La paridad del lenguaje
Quizá en este reto sea útil preguntarse si se utilizará más la clave par o la impar. Para contestar a esa pregunta he construído el concepto Paridad del Idioma (para el alfabeto del reto), que consiste en calcular, a partir de las frecuencias de las letras del castellano (caso de la Regenta), la probabilidad de que una letra elegida al azar en un texto sea par o impar. Parra ello he asignado a cada letra un 0 o u 1, según fuera par o impar. Basta con multiplicar cada frecuencia relativa por el bit correspondiente, y sumar. La Paridad se define como
P = 100 - Sumatorio( frec_rel * bit)
Si las letras fueran mayoritariamente pares, saldría una suma pequeña, y la paridad sería grande. Por el contrario cuanto mayor sea la suma, mayor será la probabilidad de encontrar una letra impar. Un resultado de 50 % indicaría un empate. Pues, bien, el resultado que se otbiene de los datos utilizados es de 54, 5 %. Es decir, es algo más probable encontrar una letra impar o, lo que es igual, se usará más veces la clave impar, aunque la diferencia no parece significativa a efectos de ataque.
Hay que tener en cuenta que otras fuentes atribuyen a las letras diferente espectro de frecuencias asignándole, por ejemplo, mayor frecuencia a la E que a la A, entre otras diferencias. Además, el espectro depende mucho del texto. Eso modificaría el cálculo, pero supongo que estaríamos simpre en torno al 50%.
O sea, que no hemos encontrado nada relevante.
.
Un concepto interesante el de
Un concepto interesante el de la paridad del lenguaje. La pena es que haya tan poco alejamiento del 50%.
Bueno, le estás dando bien al reto, lo cual agradezco. Seguro que tarde o temprano te encuentras con el talón de Aquiles y lo tumbas. Bueno, si ves que te atascas, y necesitas alguna pista, ya sabes, que tampoco quiero que esto se convierta en un suplicio o algo falto de diversión.
Claves a partir de texto conocido
Por cierto: ¿Alguien sabe como extraer información de las claves a partir de un fragmento de texto conocido? Porque con eso ya se podría atacar el reto, probando secuencialmente hasta dar con la posición donde está "civilización".
Claro que estas cosas las hacían habitualmente Llamamex (que bastante tiene el pobre con TFTR) y Sqrmatrix, que se ha pasado al otro lado de la barra.
De momento, Sqrmatrix ¿podrías proporcionarnos un fragmento cifrado con dos claves, de cuatro caracteres cada una? Esto supone una clave global de ocho, en principio no atacable por fuerza bruta; y una palabra, no muy larga, que figure en el texto y también la posición donde está. El texto podría ser corto, 300 caracteres, o poco más.
Así, si resolvemos esto quizá veamos factible la solución del reto principal.
Ya está el sub-reto
Ya he puesto el sub-reto, un texto de 300 caracteres, con claves de 4 caracteres cada una. La palabra conocida es "POSICION", en la posición 193 (empieza a contar desde 0). El reto está en https://sites.google.com/site/sqrmatrix/criptograma2.txt?attredirects=0&d=1. Lo he probado con el JavaScript de krenel00 y se descifra correctamente
Esto me suena a que vas a preparar un algoritmo genético de los tuyos, ¿no?. Bueno, a ver qué tal se os da este súf-reto :)
Muchas gracias, voy a darle
Muchas gracias, voy a darle vueltas, la verdad es que sí que tengo pensado enchufarle un AG. Si eso funciona al menos deja claro que existe alguna vulnerabilidad en el cifrario, aunque luego no sea práctico usarlo con claves de longitud desconocida (con herramientas apropiadas sería otra cosa, eso si).
Por cierto, creo que las claves del reto principal son de diez o doce caracteres, pero no me lo confirmes, ya veremos...
Buena pregunta
Aparte de que sería hacer uso de una pista "ilegítima" que le arranqué a sqrmatrix prematuramente, la pregunta es buena. Yo también me la formulé para tratar de conseguir las claves que generaran lo que yo pensaba que había que generar -y que era erróneo-
A partir de los primeros titubeantes caracteres, cada carácter del texto cifrado está XOR-ado un número de veces que oscila entre la longitud de la clave par y la longitud de la clave impar. Como la sucesiva aparición de cada clave es aleatoria, en función de la paridad del texto, que viene a ser un 50%, podemos esperar todas las combinaciones posibles entre todas las letras de las dos claves(*), o sea
(*) Los índices de las letra de la claves no guardan ninguna relación con sus posiciones, salvo la primera de la clave que se aplica al carácter (según su paridad) y que ya no se vuelve a aplicar. A menos, claro está, que la misma letra aparezca en otra posición de la clave)
Creo que hay suficiente eplosión combinatoria como para que esa vía de ataque no sea posible, pero no me hagas mucho caso, que yo tiendo a ser pesimista, en cuestiones de criptografía.
Reducción de la dimensión del problema
Nadie ha comentado mi post sobre las letras que se podrían descartar, a partir de la premisa de que ni la primera letra de la clave par ni la del texto pertenezcan al conjunto [K Ñ W _ . , : ;]. Pero yo sigo pensando que reducir los 32 símbolos a 18 es un avance. Segùn el razonamiento expuesto, la primera letra de la primera palabra tendría que ser una de éstas, y la primera letra de la clave impar debería ser su complementaria del XOR, con respecto al primer carácter cifrado, que es una G:
Podría parecer que es algo más probable que aparezca una letra impar, porque hay 10 de ellas de las 18 disponibles. Pero debemos tener en cuenta la abundancia de cada letra en el idioma, lo que equivale a calcular la paridad del conjunto, mediante una tabla como la siguiente:
No es gran cosa, desde luego. Vamos a dejarlo en un empate.
A partir de ahí se abre un gigantesco árbol (los árboles combinatorios casi siempre son gigantescos) de combinaciones, pero mucho menor del que teníamos en un principio, con los 32 caracteres.
P.S.
¿No hay nadie a quien le gustaría disponer de una estadística de "iniciales", es decir, de las letras con que se inician las palabras en castellano?
Iniciales
En vista de la avalancha de peticiones, me he sentido obligado a calcular la frecuencia de las letras iniciales de palabra en castellano, tomando como referencia La Regenta. Y sale esto:
Notas:
La frecuencia relativamente alta de la W es debida al uso de palabras "extranjeras", sobre todo las frecuenes alusiones al libro de oraciones llamado "Kempis", y a algún "kilómetro"
La W doble aparece repetidamnente por alusiones al rey godo Wamba, y por escribir la palabra "vals" en la forma parimitiva "wals"
Las repetidas X son todas debidas a la numeración romana de capítulos
No aparece la Ñ porque es escasa, aunque alguna palabra hay en castellano con esa inicial (Ñoño, Ñandú, Ñora)
También sería intersante saber la frecuencia de digramas iniciales, pero eso lo haré cuando haya aún más peticiones.
Huy es que corres mucho, yo
Huy es que corres mucho, yo soy diesel y tampoco vivo en el apacible solaz de El Puzzle Asesino, ni dispongo como tú de kilómetros de resbaladizo suelo de linóleo para escribir con tiza las tablas de frecuencias...
Interesante, pero ¿y la frecuencia de las letras de inicio de palabra en el inicio de un párrafo o al inicio del documento ? A ver si va a ser diferente, y tenemos otro conjunto de inicio...
Vacaciones
Es que la Mengela se ha ido de vacaciones a Bergen-Belsen y, la verdad, esto es la Gloria.
No creas que no detecto tu matiz de burla sobre mis búsqudas "iniciálicas". Quizá no he aclarado que toda la faena es para tratar de acometer las primeras letras del texto plano y de la clave par. Naturalmente, las estadísticas no nos van a revelar per se qué condenado texto ha elegido sqrmatrix, ni cuáles son sus diabólicas claves. Pero para plantear un ataque con algo de combinatoria podría sernos útil alguno de estos datos estadísticos.
Tampoco comentas la reducción de 32 a 18 caracteres disponibles (para la primera letra del texto y de la clave) que propongo, si te parece verosímil o, si por el contrario, crees que no tiene base.
Saludos
Huy:lo decía en serio, creo
Huy:lo decía en serio, creo que las palabras de inicio de párrafo tienen otra frecuencia, pero, claro, falta Frau Menguela y ya han descuidado la medicación otra vez...
Por cierto el mini reto empieza por "v", lo que nos da estas posibilidades:
Dado que falta la "L", que formaría artículos, creo que es muy probable que la clave o el retín, empiezen por "e".
Son interesantes (y acertadas
Son interesantes (y acertadas) vuestras suposiciones de los pares de letras de la clave par con el texto original, tanto en el súf-reto como en el reto original (las que dijo Agustín) (ojo, sólo me refiero a los pares presentados, no a la suposición de que la clave del sub-reto empiece por "e". A este respecto, no me pronunciaré). Lástima (para vosotros, no para mi criaturita) que sean tantas posibilidades. Pero bueno, estoy seguro de que tarde o temprano haréis un gran avance, si nadie lo ha hecho ya en las sombras, claro
Sigo viéndolo muy complicado
Tener que averiguar dos claves independientes lo hace extremadamente difícil. Aún así se me ocurre una cosa. Las posiciones más vulnerables son las del inicio del mensaje, puesto que se cifran menos veces. Además, es bastante probable que se pueda repetir la clave a usar (por ejemplo usar SANCHO para las pocisiones 1..6 y para 2..7). Uso la terminologia de las A(i) para texto claro, Kp(i) para la clave par, Ki(i) para la clave impar, C(i) para el texto cifrado y ^ para XOR. Si, por ejemplo la clave par se usara 2 veces seguidas tendríamos:
C(0) = A(0) ^ Kp(0)
C(1) = A(1) ^ Kp(0) ^ Kp(1)
Por tanto C(0) ^ C(1) = A(0) ^ A(1) ^ Kp(1)
Podemos disponer de una tabla de digramas castellanos que nos proporcionen las parejas más probables para calcular A(0) ^ A(1) y de ahí obtener candidatos a Kp(1) y Kp(0).
Demasiado calor.
Hum... quizá este reto sea
Hum... quizá este reto sea demasiado complicado. El sub-reto aún no ha dado resultados, y todos coincidís en que el reto principal va a ser muy complicado de resolver. Quizá me he pasao. Bueno, si necesitáis alguna pista, decidlo.
Por cierto, LlamameX, en caso de que en la segunda letra se aplique la clave impar, esto último que dices también es aplicable si la primera letra de ambas claves coincide, aunque las claves sean diferentes.
Tres primeras letras (que diga... dos)
Tengo un ataque para conseguir una lista de candidatos a las tres primeras letras del texto. De momento he realizado un ataque para las dos primeras, pero no estoy satisfecho, porque he usado los digramas iniciales de La Regenta, y creo que habría que utilizar "todos" los digramas iniciales del castellano. He impuesto la restricción de las 18 letras disponibles para el primer carácter, y que tanto los dos caracteres de las claves, como los dos del texto sean digramas iniciales del texto de referencia, y salen estos resultados
Observaréis que sale un número bastante reducido de resultados, al que se le podría dar un vistazo, aunque prefiero repetir la prueba con el lemario.
El resumen de los resultados es:
El ataque con tres caracteres es viable, salvo por el problema de que tengo un lemario que está lleno de americanismos que no creo que sean aplicables, y tengo que expurgarlo un poco para reducir su tamaño.
Me hubiera gustando hacer algo más analítico, pero no se me ha ocurrido nada.
Voy a estar toda la semana fuera, así que no podré hacer nada. Si a la vuelta no lo habéis resuelto, volveré a la carga.
Bien, bien...
La cosa va bien...
Páginas
opinar