Reto: TFTR 2.0

Imagen de tokamak
Enviado por tokamak en

Foros: 

10-Enero-2014: Superado, de forma brillante, por LlamameX

Por tokamak

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

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

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

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.

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.

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.

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

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

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.

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.

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

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.

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?

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.

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

Texto puro

  • No se permiten etiquetas HTML.
  • Saltos automáticos de líneas y de párrafos.
Imágenes
Puedes añadir hasta 10 imágenes explicativas a tus comentarios (pantallazos, etc).
Los archivos deben ser menores que 8 MB.
Tipos de archivo permitidos: png gif jpg jpeg.
By submitting this form, you accept the Mollom privacy policy.