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
¿Donde estás, reto? (y un huevo duro)
Por una conjunción astral de esas a Admin y a un servidor se nos ocurrió subir al mismo tiempo el artículo sobre el cifrado TFTR, sólo que yo subí la primera versión que es, precisamente, la que tiene el reto.
Con todo, voy a aprovechar la circunstancia para añadir otro reto para TFTR 2.0, un cifrado un poco más potente. Ya sabéis a pan duro, diente agudo...aunque os aconsejo empezar por la primera versión.
y aquí está:
Reto 2.0
Como de costumbre doy la longitud de la clave: 8 exiguos caracteres, 8 (y ni siquiera aleatorios).
Añado también el enlace a la versión online
Puedes acceder aquí http://llamamex.nixiweb.com/tftr/ a todas las versiones de TFTR, incluyendo la 1.1 que ya no me acuerdo de donde salía
Gracias por recordarmelo, voy
Gracias por recordarmelo, voy a poner también tu mega-implementaçao en la primera versión
....no me digas que no te tienta...sólo 8 caracteres de clave, ahí solos, desvalidos los pobres, ni siquiera es un número primo...
Me parece que tengo algo mal en mi implementación.
¿Podrías enviarme la codificación que a ti te consta para este texto con la clave SANCHO?
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._UNA_OLLA_DE_ALGO_MAS_VACA_QUE_CARNERO,_SALPICON_LAS_MAS_NOCHES,_DUELOS_Y_QUEBRANTOS_LOS_SABADOS,_LENTEJAS_LOS_VIERNES,_ALGUN_PALOMINO_DE_AÑADIDURA_LOS_DOMINGOS,_CONSUMIAN_LAS_TRES_PARTES_DE_SU_HACIENDA._EL_RESTO_DELLA_CONCLUIAN_SAYO_DE_VELARTE,_CALZAS_DE_VELLUDO_PARA_LAS_FIESTAS_CON_SUS_PANTUFLOS_DE_LO_MISMO,_LOS_DIAS_DE_ENTRE_SEMANA_SE_HONRABA_CON_SU_VELLORI_DE_LO_MAS_FINO._TENIA_EN_SU_CASA_UNA_AMA_QUE_PASABA_DE_LOS_CUARENTA,_Y_UNA_SOBRINA_QUE_NO_LLEGABA_A_LOS_VEINTE,_Y_UN_MOZO_DE_CAMPO_Y_PLAZA,_QUE_ASI_ENSILLABA_EL_ROCIN_COMO_TOMABA_LA_PODADERA._FRISABA_LA_EDAD_DE_NUESTRO_HIDALGO_CON_LOS_CINCUENTA_AÑOS,_ERA_DE_COMPLEXION_RECIA,_SECO_DE_CARNES,_ENJUTO_DE_ROSTRO_GRAN_MADRUGADOR_Y_AMIGO_DE_LA_CAZA._QUIEREN_DECIR_QUE_TENIA_EL_SOBRENOMBRE_DE_QUIJADA_O_QUESADA_QUE_EN_ESTO_HAY_ALGUNA_DIFERENCIA_EN_LOS_AUTORES_QUE_DESTE_CASO_ESCRIBEN_,_AUNQUE_POR_CONJETURAS_VEROSIMILES_SE_DEJA_ENTENDER_QUE_SE_LLAMA_QUIJANA_PERO_ESTO_IMPORTA_POCO_A_NUESTRO_CUENTO_BASTA_QUE_EN_LA_NARRACION_DEL_NO_SE_SALGA_UN_PUNTO_DE_LA_VERDAD.
Gracias
1.0 o 2.0
¿en qué versión?
con 2.0
con la 2.0
Me parece que no separo los bloques de 512 en la 2.0.
Por cierto has colgado el bloque de 177 y ahí coincidimos. El texto que te he puesto es de unos 1200 carácteres
es que no lo veo
pásamelo como código
Te paso La Regenta
La Regenta texto plano:
Cifrado con clave MAGISTRAL
Te lo había enviado por privado
antes de ver esto, puedes ignorarlo que ya me vale la regenta.
Gracias
No sé donde está el fallo
Las 2 primeras posiciones las hacemos igual
MAGISTRAL, suma 94. Multiplicado por (9-4) =1222, que módulo mod 512 es 198.
La posición 198 de un vector, para el que la primera posición es 0, es la E (ENTE_DE_LOS_REMOLINOS_DE_POLVO...).
M xor E = I
la cadena de texto cifrado recibe la I en la posición (198 +1), (las cadenas no tienen posición cero). Pensaba que esta triquiñuela podría ser el origen de la discrepancia, pero parece que no.
Para la segunda posición cifrada, usamos la clave EAGISTRAL, que suma 180, que apunta a la U (UE_EL_RUMOR...)
La segunda posición de la clave recibe la U
A XOR U = U
La posición 180 + 1 recibe la U.
En realidad hacemos todo igual durante 460 codificaciones de caracteres, hasta la 461, en que obtengo un "_" que pongo en la posición 949+1 del cifrado, donde tu tienes una E.
En ese momento, el vector con los punteros está así:
Lo mismo soy yo el que lo está haciendo mal, soy capaz de eso y de mucho más..
Uy seguro que es cosa mia, que ya se que hay algo mal
Pues eso que ya me lo miro y te digo algo
No me cuadra tu ejemplo
De acuerdo la primera I para 198, pero EAGISTRAL suma 86, que da (86*14)%511=182 que para mi es "_" ^ "A" = "_"
Parece que está bien
86 * 14 = 1204; 1204 MOD 512 = 180. De hecho lo haces igual, en la implementación JAVA coincide.
pero por que módulo 512?
Si ya sólo tenemos 511 elementos en el vector?
No, es que el vector siempre
No, es que el vector siempre tiene 512 elementos, se expulsa el índice ocupado, y se resecuencia el vector, cogiendo otro elemento del texto. Así que nunca cambia, salvo si la longitud texto no es múltiplo, que al final el último bloque será más pequeño.
Ejemplo, tenemos 6 elementos, y un bloque de 3 la situación original del vector es así:
Tomamos el elemento 2 y resecuenciamos
Espero que se me entienda, soy muy malo dando explicaciones...
Si, ahora si,
No se por que seguía con el bloque de 512 y había reducido el texto a esa cantidad para manejarlo mejor.
Cogiéndolo entero la regenta me queda exactamente igual que a ti. Por cierto, la textarea del texto cifrado por defecto no esta vacía, hay carácteres en blanco (ya subierá una versión con eso corregido) con lo que si no se limpia antes de poner un texto a descifrar puede dar problemas.
Genial!
Estupendo! ¿ya está online?
Si: lo había visto, pero online todavía no va
Sí, es un problema bastante común, que se suele ver en aplicaciones Web. Ya tenía cuidado de borralos antes, no le dí mayor importancia.
No sé si es que no está subido aún, pero no obtengo el mismo resultado con el programa Java...
Date cuenta que cuando ya no hay más caracteres del texto que añadir, el vector de punteros va disminuyendo de tamaño, a medida que "consumimos" las posiciones, 512, 511, 510...
Cosillas al respecto de TFTR
Bueno pongo algunas cosas respecto a este engendro, que como dije ya hace tiempo va a ser muy duro de roer.
TFTR es en el fondo un XOR entre las letras del texto claro. Salvo las primeras posiciones que se harán con texto claro y la clave, el resto se harán entre ellas, incluyendo el salto al siguiente bloque.
Así pues, el factor crucial es el orden en que se realizan las XOR. La clave nos genera las primeras posiciones que condicionarán la evolución del resto. Dado que en la 2.0 se ha mejorado mucho la gestión de las posiciones va a ser complicado poder pillar el texto por la mitad, obviando la clave.
El principal punto débil que le veo (y no lo es mucho) está en el cálculo de la posición a partir de la clave. Se trata (antes de cálcular el producto y el módulo) de una suma de variables aleatorias discretas con probabilidad conocida, cosa que nos va a dar una forma más o menos de distribución normal, con lo que los valores de esa suma pueden ser acotados para reducir la fuerza del ataque.
Las operaciones, por otra parte son XOR, lo que nos indica que las "A" corresponden a carácteres iguales en el texto claro y la posición de la clave cuando se calcularon. Podríamos esperar que, por probabilidad, buena parte de ellas representen el "_".
Por la parte de la dificultad, va a costar encontrar un criterio de validación rápido, puesto que aunque atacáramos la clave y diéramos con ella habría que descifrar una cantidad importante de texto antes de poder determinar si la hipótesis es aceptable o no.
Esto va a ser francamente duro. Si TFTR permanece intacto es por un buen motivo.
Por eso limité la clave
Bueno,a mí me parece más bien un sistema de trasposición, antes que un simple XOR, ya que vamos dejando el texto cifrado un poco por todas partes.
El cálculo de las posiciones ya me habías de dicho que era un sistema un tanto débil, y que no aprovechaba toda la entropía de la clave. Ya lo sé; pero como también es un sistema que me parece bonito, lo mantengo, mejorando en su lugar la calidad de la trasposición.
Como me figuraba que sería duro de roer, me limité a una clave de 8 caracteres. En general creo que los demás autores de cifrados podrían facilitar también las longitudes de las claves correspondientes, y limitarlas también mucho en longitud, hasta lo estrictamente necesario para no poderse romper por fuerza bruta: 8 caracteres parece una cifra bastante apropiada; si el algoritmo es lo suficientemente perverso, no se necesita más.
Por favor, admin, bórralo
Error
Siempre que viene Frau Menguela, lo mismo..
Venga a llamar a admin: bórralo!, bórralo, bórralo!. Que nooo, que admin no está en la clínica. Además, ese enema que te trae La Menguela en esa bandejita de porcelana tan mona es buenísimo, es que todos los lunes de madrugada estamos igual..
Reíros
Reíros, reíros. Pero el día que te conviertas en el arcángel San Gabriel, como me pasó a mí, y nadie te crea, ya verás.
El nivel de dificultad
En general, estoy de acuerdo en limitar las dificultades de los retos, sin alterar su esencia, para que resulten asequibles dentro de su dificultad. Por cierto, creo que MIMIC tiene el nivel un poquito alto. Pero tampoco hay que prohibir que los ponentes presenten algoritmos seguros, si los dioses les han concedido el don de saber construirlos. En esos casos la solución del reto podría consistir precisamente en "demostrar" que el criptosistema es irrompible, o en estimar su complejidad. O simplemente en "mostrar" una serie de ataques que avalen la fuerza del cifrado.
Me parece bien limitar la longitud de la clave, aunque no tanto el revelarla, porque en algunos algoritmos eso equivaldría a romperlos. Por otra parte, la fuerza del cifrado en función de la longitud de la clave dependerá de cada caso. En algunos sistemas el ataque no consistirá en descubrir la clave, por lo que su longitud podria ser irrelevante.
Con una clave de 8 caracteres sobre un alfabeto sencillo de 26 símbolos ya se consigue un número de combinaciones (26^8 ~ 2*10^11) lo bastante grande como para evitar un ataque de fuerza bruta sobre la clave, que es lo que menos interesa. Al menos estaría fuera del alcance de muchos equipos domésticos, como el mío.
Pero por otra parte si la solución del cifrado pasa por conocer la longitud de la clave, como ocurre con el Vigènere (vale, vale, ya sé que no lo utilizáis), con un máximo de 8 caracteres las pruebas necesarias para romper el sistema serían relativamente escasas, haciéndolo trivial.
Creo que lo mejor sería que en cada caso el autor valorara las características de su criatura y le cortara un poco las garras y las alas, si es necesario, o que diera alguna informacion complementaria para que no resulte completamente inaccesible a los mortales.
pa lo que ha durao
Pues si el nivel llega a estar más fácil no me dan tiempo ni a acabar de colgarlo XD. pero ya veran, ya...
Columpiada
Me he pegado una columpiada de aúpa. Mejor me callo durante un tiempo.
Complejidad
Más que cortar las alas de la criatura, yo lo que pediría es sencillez de funcionamiento y claridad de diseño.
En efecto, creo que no está justificado construir un algoritmo que sea más complicado que RC4 (que son un puñado de instrucciones observese la implementación en C) y que, en cambio, resulte mucho más fácil de romper. Es que si no hacemos así, yo os puedo proponer tropecientos criptosistemas con varios pasos sucesivos, con trasposiciones, sustituciones y nuevamente trasposiciones, que sean feos como mandriles, pero eficientes en su propósito.
Para mí el ideal es ese: un pequeño número de pasos que generen la máxima entropía.
(Vaya, me he equivocado de hilo...)
La elegancia de la sencillez
Yo en mi caso busco ideas lo más nuevas y originales posibles para generar algoritmos de cifrado. Obviamente la sencillez es una virtud que busco en ellos, pero en la idea en que me baso, no en su implementación. También por hacerla didáctica y asequible la implemento en javascript.
Podría codificarla en C y apretujar el código para minimizar líneas condensándolo, pero no es una implementación buscando la eficiencia en ejecución si no pruebas de concepto para validar el algoritmo.
En el caso de Mimic, con todas sus florituras (y sus carencias) el código base es el siguiente:
function Desordenar(balfa,pclave) { var talfa=""; var palfa=balfa; var k=0; for (var i=0;i<alfabase.length;i++) { k=(k+alfabase.indexOf(pclave.substr(i%pclave.length,1)))%palfa.length; talfa=talfa+palfa.substr(k,1); palfa=palfa.substr(0,k)+palfa.substr(k+1); } return (talfa); } function CmdCifrar() { var Ai=''; var Ci=''; var Ki=''; var iAi=0; var iCi=0; var iKi=0; var cifrado=''; var clave=document.Frmmimic.TxtClave.value; alfacript=Desordenar(alfabase,clave); var contador=new Array (alfacript.length) for (j=0;j<contador.length;j++) contador[j]=0; for (i=0;i<document.Frmmimic.TxtClaro.value.length;i++) { Ai=document.Frmmimic.TxtClaro.value.substr(i,1); Ki=alfacript.substr(i%alfacript.length,1); iAi=alfabase.indexOf(Ai); iKi=alfabase.indexOf(Ki); iCi=iAi^iKi; Ci=alfabase.substr(iCi,1); if (++contador[iAi] > 1) { for (j=0;j<contador.length;j++) contador[j]=0; k=i; t=clave; while (k>0) { t=t+alfabase.substr(k%alfabase.length,1); k=Math.floor(k/alfabase.length); } alfacript=Desordenar(alfacript,t); } cifrado=cifrado+Ci; } document.Frmmimic.TxtCifrado.value=document.Frmmimic.TxtCifrado.value+cifrado; }Que obviamente podría ser reducido, pero que no me parece ningún exceso de código
Sí, yo me refiero sobre todo
Sí, yo me refiero sobre todo a la sencillez de la idea; la del código es más bien (casi siempre) su consecuencia. Todos los algoritmos que visto hasta ahora en los retos cumplen bastante bien con esa premisa. Digo esto para evitar lo que comentaba: que se presenten algoritmos de supercifrados sucesivos e ideas muy retorcidas y poco claras, como aquel engendro del QWERTY.
Vía de ataque
Dado que es laborioso comprobar, por pura aplicación del algoritmo de descifrado, la idoneidad de un candidato a clave (se requiere obtener un número elevado de carácteres en claro, ya que al no ser correlativos es difícil buscar palabras y hay que ir a ver si se ajustan a distribuciones coherentes con el castellano), creo que el camino va a tener que ser otro. Propongo atacar directamente el texto en claro.
La idea sería partir del rango de mayor probabilidad [40-120] (bastante a ojo, con un 90% nos vale) para la suma de 8 valores y probarlo entero. Para cada uno de esos valores empezaríamos buscando el carácter cifrado al que apunta y asumiríamos como carácter en claro alguno de los de mayor probabilidad dentro de una distribución tipo regenta. Con eso obtendríamos un valor para el primer carácter de la clave. Si lo consideramos coherente tendríamos un apuntador al segundo carácter del cifrado que corresponde y repetiríamos con el la operación.
Habría que ir viendo si con esta operación obtenemos un valor válido para la clave (por ejemplo texto claro). En caso de que no probamos nuevos valores para el texto claro. Para limitar el ataque podemos quedarnos con los 10 primeros valores de la regenta que nos dan más de un 70% de probabilidad (recordemos que no buscamos palabras si no carácteres sueltos) y una longitud de ataque de 5 carácteres.
Con estos parámetros la complejidad del ataque la podemos cifrar en
80 * 10^5 = 800000
Que es muy asequible. La dificultad está en filtrar los resultados que consideremos correctos. Ahí seguramente sería útil el sistema que ha usado sqrmatrix para atacar a mimic (snif). Si me lo puedes hacer llegar me ahorraría bastante trabajo.
Saludos
Ataque
Muy bien, veo que lo retomas justo donde lo dejaste, pero esto no es TFTR 1.0, no es tán fácil saber a que posición apunta. Se apunta a las posiciones de un vector, que a su vez tiene las posiciones reales de los caracteres cifrados. Cada vez que se cifra un caracter, se resecuencia el vector sacando el índice ocupado.
Esta reorganización, altamente ineficiente, está buscada para hacer más difícil el ataque, pero vosotros lo conseguiréis, sin duda.
No,si ya asumo eso
Pero no tiene que afectarme, puesto que la nueva posición puedo obtenerla de la suposición del carácter que entra y del que se va de la clave. Creo, pero lo reviso.
No sé qué dijimos
No sé qué dijimos acerca de graduar la dificultad de los retos, pero yo los veo cada vez más difíciles, aunque seguramente sqrmatrix y LlamameX -entre otros- ya han visto dónde pegar la próxima dentellada.
Últimamente he tenido poco tiempo para analizar el problema, pero como tú has explicado, la esencia del algoritmo está en la transposición de los caracteres del texto plano en los bloques de 512 bytes (salvo el de cola).
Salvando las distancias, me recuerda algunos aspectos de la Omelette -que es posterior a TFTR-1.0, lo reconozco-, en la que se trasponían los bits. En ambos casos la entropía procede de la clave, aunque en TFTR-2.0 la clave va variando, de manera que el batido de caracteres no es el mismo en todos los bloques, lo que le da una mayor robustez. Como detalle secundario, creo que sería más redondo aún si el bloque residual se completara con algún tipo de padding.
Pero vamos a lo importante: En la idea de probar la fortaleza de algoritmos sencillos, dijimos que era preferible no embarullarlos con operaciones superpuestas que servían para -las palabras son tuyas- "tapar las vergüenzas", y justo ése es el papel que, a mi entender, desempeña la operación XOR. No estoy tratando de modificar TFTR-2.0, que está muy bien como está, y va a resultar robusto, con el permiso de sqrmatrix y LlamameX. Quiero decir que, en el caso de que este par de mostruos roe-enigmas no pudieran destriparlo en un tiempo razonable, sería interesante enfrentarnos a un TFTR-lite, en el que sólo estuviera el batido de caracteres. Caigo ahora en que no recuerdo cómo era TFTR-1.0, mecachis.
Respecto a la versión lite
De hecho considero que con las rebajas que nos ha hecho Tokamak aún en la versión 2.0 ya estamos en una versión lite. Si no podemos con una clave de 8 carácteres (que saber la longitud ya es un regalo) no aleatoria es que ya sólo podemos pedir pistas del estilo del "veo veo".
Por mi parte creo que tengo un ataque decente medio hilvanado que lanzaré esta semana. Si es efectivo (eso está por ver) seguramente sería aplicable a longitudes mayores de clave.
Así que por mi déjalo como está, al menos de momento, que aún me queda medio incisivo para seguir royendo.
Pues sí, y a ver si
Pues sí, y a ver si generaliza esto de dar la longitud de la clave, coñe. Después de todo, era algo conocido para criptoanalizar las máquinas Enigma, Hagelin y otros bichos, y no por eso tenía menos mérito precisamente.
Que emoción, este cifrado se enfrenta a su peor pesadilla en su semana decisiva..¿se desgastará el mediomonoincisivo de llamameX antes de llegar al final de la clave?
Xor y demás
Hola, bueno pues es robusto pero no tanto: la suma de los valores de la clave se mantiene en un rango discreto de caracteres. Esto ya me lo había dicho LlamameX antes de preparar 2.0 pero lo he mantenido intencionadamente porque me gusta el método, sobre todo.
En su momento ya había comentado que una implementación del algoritmo que utilizo para mis cosillas usa un sistema ligeramente distinto, alguna pista di y todo, pero no os asusteis, nunca lo voy a plantear como reto. TFTR 3.0 jamás saldrá de su casita.
En cuanto al Xor, date cuenta que no hago cambios de alfabeto, así que lo empleo como método lineal, combinado con el no lineal de la suma de la clave, como mandan los cánones esos.
Por otra parte el batido de caracteres no se traspone en los bloques de 512 caracteres exactamente, sino en todo el texto, pero procesando de 512 en 512. Si miras el vector de punteros verás que en un bloque puede haber caracteres de cualquier parte del texto. Después, al tratar el último bloque, el tamaño va disminuyendo hasta terminarse.
Vale
Me habéis convencido. No me entero bien de un algoritmo hasta que lo implemento.
Demasiados positivos
Aunque creo que el ataque es correcto recibo demasiados falsos positivos (unos 130.000) para analizarlos individualmente todos. Alguno era interesante, por eso, como LAGRA(NGE), ESPAÑ(OLA), LA_CL(AVE), DECEN(CIA), LAS_T(RES), etc.
Miraré de refinar más el filtro a ver si puedo reducir resultados. Ahora estoy trabajando sobre unos 4.500 trigramas y un rango inicial de valores de suma de 25 a 90, que debería abarcar un 97% de los casos. Igual deberé reducirlos aún a riesgo de crear falsos negativos.
Los falsos positivos fueron
Los falsos positivos fueron el pan de cada día cuando los implementé en mi AG. Claro que yo utilizaba palabras de un diccionario de español, tu ataque está más centrado. El cerco se estrecha. Esto es inquietante...
Nueva vía de ataque
Aunque ya tengo alguna idea para mejorar el filtrado (acotar la suma de los carácteres restantes), siguiendo la ejecución del ataque he visto una nueva posibilidad interpretando los resultados del XOR respecto a la siguiente posición en el bloque.
Me explico. Si tenemos una "A" en el cifrado sabemos que tanto la letra de la clave como la del texto claro coincidieron ahí. Eso, por tanto, tendrá incidencia en la posición siguiente puesto que la clave no variará (sale el mismo carácter que entra). Así pues repetiremos posición. Dado que en la 2.0 eso se trata con el vector de disponibles, del que habremos retirado la posición actual, eso implica la siguiente posición no usada. Si nos limitamos a los 8 carácteres de la clave, la distancia máxima de una "A" al siguiente carácter será, pues, de 8.
En el caso de tener una "B" eso implica que la diferencia está sólo en el bit menos significativo, es decir, que el carácter de la clave y el texto claro están a +-1 posición en el alfabeto y por tanto la nueva suma de carácteres de la clave también diferirá en +-1 respecto la anterior. Traducir esto a posición en el bloque puede ser algo más complicado, ya que la suma de dígitos puede variarnos bastante, pero siempre dentro un rango conocido.
Lo mismo aplica a las "C", ya que cambia el segundo bit menos significativo y por tanto implica una diferencia de +-2 en la suma de la clave. Las "E" serán +-4, etc.
Creo que analizando esto con un cierto cariño puede determinarnos el posible orden de aplicación del cifrado, al menos en los primeros carácteres en los que el efecto del vector de disponibles sea menos dramático.
ROC ROC ROC...
Genial
Me parece una idea muy elegante. A partir de ahí cabe hacer una búsqueda recursiva de combinaciones de letras, descartando las que no tengan sentido mediante el diccionario -o las reglas gramaticales-, para reducir la profundidad de la recursión. Bravo
Efectivamente
Buenos días LlamameX:
Claro, por ejemplo la primera "A" que genera el cifrado del texto de la Regenta ocurre con la clave "_HNQ_NMET", mediante su último caracter, la "T", obtenemos el puntero 188, que apunta a la posición real del texto 201. Y en la última posición de la clave, dejamos la "T".
A continuación tenemos la misma clave "_HNQ_NMET", y con su primer caracter "_", obtenemos otra vez el puntero 188, que nos apunta a la posición real del texto 202, donde ponemos una "E". En la primera posicón de la clave, dejamos la "E".
malditos roedores...
Más sobre el XOR
La cosa tiene más atractivo del que parece. Fundamentalmente parece que puedo obviar casi todo el desorden de TFTR. Obviando los cálculos tenemos
Sea S la suma de los carateres de la clave, expresado como 3 dígitos tenemos
S=[abc]=100a+10b+c
Si p es la posición que le corresponde (obviando la aritmética modular) tenemos
p=(100a+10b+c)(a+b+c)=100a^2+110ab+101ac+10b^2+11bc+c^2
Sea y el valor correspondiente al carácter cifrado (XOR) en la posición p. Para simplificar suponemos y<10 (carácteres de la "A" a la "J"). Si p' es la posición siguiente tendremos
d=p'-p=(100a+10b+c+y)(a+b+c+y)-(100a+10b+c)(a+b+c)=101ay+11by+2cy+y^2=(S+a+b+c)y+y^2
Por ejemplo,
Clave ABADIA. Suma 12. Posición 12*3=36
Supongamos C36="E" (y=4)
Calculándolo de la manera normal: Nueva clave EBADIA. Suma 16. Posición 16*7=112
Calculándolo con la fórmula: d=(12+1+2)*4+16=76 => p'=p+d=36+76=112
Es decir, que suponiendo una suma inicial (que ya sabemos que tiene una distribución muy acotada) y del valor del XOR que encontremos en ella podemos tener una idea bastante clara del orden seguido. No necesitamos saber nada más, puesto que tenemos p, S, a, b, c e y
Óbviamente aquí hay algunas simplificaciones que habrá que tratar. Estoy en el caso en que el XOR es menor que 10 para añadir un sólo dígito, pero trabajar con un desplazamiento de 2 tampoco debería suponer demasiada complicación. También hay que asumir que las diferencias d pueden ser positivas o negativas, con lo que para cada P tendríamos 2 posibles P' siguientes. Esta también el tema de la aritmética modular pero nos afectará poco ya que se aplica después del cálculo y podemos obviarla hasta el momento de localizar el valor XOR. Finalmente el tema del vector de disponibles. Aquí nos es una ayuda respecto a la 1.0 ya que sólo deberemos comprobar si la posición es mayor que alguna que hayamos obtenido antes y sumar 1 por cada una de ellas.
Aún no está roído
Con la función que comentas, que es una genialidad, (me acabo de enterar, soy muy lento) a partir de una suma y de un caracter, mediante (S+a+b+c)y+y^2 sí que puedes obtener la posición del vector, pero no la posición real. Si miras el vector de punteros de más arriba, la posición 112 nos daría la real 294:
Pero observarás que no tiene todas las posiciones reales. Por ejemplo no está la 295, pues ya la hemos rellenado en la codificación de otro bloque de 512 caracteres anterior, así que hay posiciones reales que nunca obtendrás, a menos que sigas el procedimiento desde su mismo inicio.
O al menos eso espero
(He encontrado esto en mi algoritmo)
Imágenes:
cielos pillaste a mi agente (de campo)!
...pero que sepas que hay más y que a estas alturas se han comido la mitad de los cimientos XDD.
Dos cuestiones respecto a la fórmula. Por una parte que el ejemplo no queda del todo claro puesto que el valor Y=4 corresponde a la "E" del cifrado, no a la "E" del claro con el que se calcula de la manera tradicional (al estar hecho el XOR con "A" coinciden).
Por otra parte esa fórmula me temo que se podrá aplicar sólo en una parte de los casos. El "exploit" de la vulnerabilidad habrá que hacerlo por un algoritmo. Como apuntaba Agustín, habrá que recorrer un árbol binario, el de los resultados +-d, pero será bastante corto: con una clave de longitud 8 será de 2^7=128 ramas.
Cada rama va a representar un camino único que testear. Creo que el ataque puede ser también bastante corto ya que a partir de un único posible primer carácter de la clave puede caer el resto.
Así pues sólo nos quedará la suma inicial, pero como decía está muy acotada. Partiendo de simulaciones (me daba pereza calcularlo exactamente) con una distribución tipo regenta, para una clave de longitud 8, obtenía más de un 95% de los casos con sumas entre 25 y 90, cosa muy asequible.
Respecto al uso del módulo y del vector de disponibles, dado que sólo voy a atacar los 8 valores de la clave me basta con los primeros 519 carácteres del cifrado. Toda la aritmética modular será pues base 512. A partir de ahí ya gestionaré los disponibles de la manera normal a medida que vaya ocupando nuevas posiciones.
Con esto espero encontrar 65*128=8320 combinaciones de carácteres XOReados.
Eso que veo ahí ¿es una grieta?
vector de disponibles
Estos roedores, también exploran ramas..¿serán ardillas?
Respecto al uso del módulo y del vector de disponibles, dado que sólo voy a atacar los 8 valores de la clave me basta con los primeros 519 carácteres del cifrado
Ojo: Los primeros 512 caracteres del texto claro no tienen porque ser los primeros 512 caracteres del texto cifrado, con el cifrado de La Regenta, cuando ciframos el caracter de la posición 53 del texto, la suma de la clave nos proporciona la posición del vector 460, que ya nos lleva a la posción del texto cifrado 513.
Siguiendo el proceso, la posición 74 del claro la ciframos en la posición 448, que apunta a la 522.
En total el primer bloque cifrado cuenta con 187 caracteres que no pertenecen a los primeros 512 caracteres del claro, aunque la mayoría sí que pertenecen a él, lo que constituye una grieta que puede facilitar el criptoanálisis.
Siguiendo el orden
Mientras la longitud del bloque sea mayor o igual a 512 haremos módulo con ese valor extrayendo las posiciones usadas del vector de disponibles, con lo que siempre estaremos con las primeras 512 posiciones de ese vector. Así pues, si en el primer paso quitamos la 53, en la posición 53 tendremos el valor 54 y en la 512 el valor 513. Así, si 8 pasos más adelante, hemos quitado hasta 8 posiciones, en la posición 512 tendremos el valor 520 (pero con 519 me bastan porque la 520 ya no la usaré). O al menos así lo veo yo.
Para más aclaración
La primer posición de vector en el cifrado de La Regenta es 198
Y nos queda así:
La segunda es 180, y nos queda así:
Por eso,
Las posiciones ocupadas tras la aplicación de los 8 caracteres de la clave no excederán de 520. Evidentemente tras aplicar TODO el cifrado tendremos muchos más caracteres posteriores al 512 dentro del primer bloque, pero los que hayamos asignado con los 8 primeros los mantendremos y son los que me interesan.
Páginas
opinar