Reto: Fucked-OTP (La venganza de AESito)

Imagen de Agustín
Enviado por Agustín en

Foros: 

Por Agustín

Bueno, pues este Fucked-OTP es hijo ilegítimo de AESito32, que tan poca fortuna tuvo en vuestras manos, especialmente por la implacable pericia de LlamameX, que tardó menos en descerrajarlo que yo en concebirlo. He mantenido casi todos los rasgos de su papá, sobre todo porque así la implementación que ya tenéis funcionará perfectamente, con un leve cambio.

La única diferencia es que, a partir del segundo bloque, la clave se va formando con los propios caracteres del texto plano, para crear una especie de falso OTP. De este modo podríamos averiguar si el flujo de caracteres del propio fichero proporciona una clave razonablemente fuerte, es decir, si un falso OTP se puede comportar como un OTP, cosa que dudo mucho.

Vamos p'allá...

 

1. El alfabeto

Es el habitual, de 32 caracteres

ABCDEFGHIJKLMNÑOPQRSTUVWXYZ_.,:;

 

2. La clave

La clave inicial es de 32 caracteres, que se completa, si es necesario, por el viejo procedimiento

K[L+i] = K[i] + 1

Por ejemplo, la clave

LOS_LAMELIBRANQUIOS

se convierte en

LOS_LAMELIBRANQUIOSMPT.MBNFMJCSB

 

3. Nuevo Alfabeto

El mismo procedimiento para obtener el alfabeto desordenado que se mantendrá durante todo el cifrado -hay que dar alguna oportunidad a los criptoanalistas- Lo copio de AESito32 tal cual

a) Se obtienen las posiciones de la clave en el alfabeto base, lo que nos dará la lista:

12 16 20 28 12 01 13 05 12 09 02 19 01 14 18 22 09 16 20 13 17 21 29 13 02 14 06 13 10 03 20 02

b) Luego se ordena esta lista para obtener una secuencialización, de forma que podamos tratar con las repeticiones.

Clave ordenada
01 01 02 02 02 03 05 06 09 09 10 12 12 12 13 13 13 13 14 14 16 16 17 18 19 20 20 20 21 22 28 29
Secuencia
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

c)Ahora procedemos a desordenar el alfabeto de la siguiente manera: Tomamos la primera letra, que es, lógicamente, la A. Como el primer valor de la clave es el 12, que aparece por primera vez en la posición 11 (empezando por cero) de la secuencia, la letra A irá a la posición 11 del alfabeto

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_ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __

Hay que marcar de algún modo que la posición 11 ya está ocupada. Yo lo he implementado borrando el valor 11 de la matriz de posiciones de la clave.
A continuación tomamos la B, a la que le corresponde el valor 16 de la clave, cuya primera posición en la secuencia es la 20, luego la B va a la posición 20:

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_ __ __ __ __ __ __ __ __ __ __ __

y así sucesivamente, hasta que nos queda el alfabeto desordenado de esta forma:

FMKX;,HZJP.AEIGSW_NYBQTÑLCR:UODV

 

4. Bloques de 32 caracteres, que se desordenan

Empezamos a cifrar un texto como éste

LA_REVOLUCION_PALESTINA_POR_RODOLFO_J._WALSH_EN_ESTE_AGOSTO_DE_EN_QUE_RECRUDECE_LA_AGRESION_DE_ISRAEL_EN
_MEDIO_ORIENTE_Y_EN_QUE,_CORRESPONDIENTEMENTE,_SE_MULTIPLICAN_LAS_MENTIRAS_IMPERIALISTAS_PROPAGADAS_POR_LOS
_GRANDES_MONOPOLIOS_DE_LA_COMUNICACION,_RESULTA_IMPRESCINDIBLE_LEER_LO_QUE_ESCRIBIERA_ESTE_INSIGNE_Y_RECONO
CIDO_PERIODISTA_Y,_MAS_QUE_ESO,_ESTE_CONSECUENTE_COMBATIENTE_REVOLUCIONARIO,_INTEGRANTE_DE_MONTONEROS,_QUE
_DESAPARECIERA_EN_MARZO_DE_A_MANOS_DE_LA_DICTADURA_DE_VIDELA._ES_ESTA_LA_VERDADERA_HISTORIA,_DOCUMENTADA_A
UN_CON_FUENTES_QUE,_COMO_LA_ONU,_SI_PUEDEN_SER_SOSPECHADAS_DE_PARCIALIDAD,_NO_ES_PRECISAMENTE_EN_FAVOR_D
E_LA_RESISTENCIA_PALESTINA,_Y_RELATADA_POR_UN_RODOLFO_WALSH_SOBRE_EL_QUE_HOY_YA_ES_UNIVERSAL_SU_CREDIBILIDA
D_Y_HONESTIDAD_INTELECTUAL,_UN_ESCRITOR_ALABADO_MUNDIALMENTE_Y_RECONOCIDO_COMO_UN_CLASICO_DE_LA_LITERATURA
_POLITICA_Y_COMO_UN_EXCELSO,_PENETRANTE_E_INSUPERABLE_INVESTIGADOR._EL_PRESENTE_TRABAJO_DE_RODOLFO_WALSH_F
UE_PUBLICADO_EN_EL_DIARIO_NOTICIAS,_EN_JUNIO_DE_._PUBLICAMOS_ADEMAS_LA_POLEMICA_POSTERIOR_ENTRE_WALSH_Y_EL_E
NTONCES_EMBAJADOR_DEL_ESTADO_DE_ISRAEL_EN_ARGENTINA._EL_CONJUNTO_DE_ESTOS_MATERIALES_ES_REPRODUCIDO_EN_BASE_
A_LOS_CUADERNOS_DE_LA_REVISTA_JOTAPE_QUE_APARECIA_EN_LOS_Y_A_LA_EDICION_REALIZADA_POR_LA_EDITORIAL_ULTIM
O_RECURSO,_EN_MAYO_DE_._

a) Tomamos el texto en bloques de 32 caracteres

Bloque
LA_REVOLUCION_PALESTINA_POR_RODO

b) Generamos una clave nueva, a partir de la anterior, por el procedimieto ya descrito, de tomar para cada carácter, el que le sigue en el alfabeto base. Aunque esto parece excesivamente trivial, no lo es tanto, porque las posiciones de esas letras van a referirse al alfabeto modificado, y la secuencia ya no será tan simple. Eso también viene de la Omelette.

Nueva clave
MPT.MBNFMJCSBÑRVJPTNQU,NCÑGNKDTC

cuyas posiciones en el alfabeto modificado son:

Posiciones de la clave
02 10 23 11 02 21 19 01 02 09 26 16 21 24 27 32 09 10 23 19 22 29 06 19 26 24 15 19 03 31 23 26
Posiciones ordenadas
01 02 02 02 03 06 09 09 10 10 11 15 16 19 19 19 19 21 21 22 23 23 23 24 24 26 26 26 27 29 31 32
Secuencia
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

c) Mediante esta clave se desordena el primer bloque de caracteres, por el procedimiento ya descrito.

Bloque desordenado
LLEURACLAERROOT__VNI_SD_OIPOPNOA

d) Se realiza XOR entre cada carácter del bloque desordenado y cada carácter de la clave, usando las posiciones de ambos en el alfabeto modificado
En nuestro caso tenemos los siguientes valores:

Bloque cifrado
C_RT:VAL.;XQP.EGCT;V;Y:X;RZSAEAN

Hasta aquí todo es idéntico al algoritmo de AESito32. La novedad viene ahora, porque no seguimos generando la clave por el naïf procedimiento anterior, sino que:

 

5. Nueva Clave: El bloque desordenado

El bloque desordenado del texto plano se toma como clave para cifrar el siguiente bloque. En nuestro ejemplo, la nueva clave será:

Nueva clave
LLEURACLAERROOT__VNI_SD_OIPOPNOA

Así de sencillo.

De este modo vamos obteniendo el siguiente texto cifrado:

C_RT:VAL.;XQP.EGCT;V;Y:X;RZSAEAN
,HHÑTTMBOZATEFFOXZNOFZ_ÑEU,NLXY;
E_WDWZBFJRXOOE:ZGBGOETXDJOT;XFÑD
EDTZ_ÑOFSXDAXWYTFPKL_IOBNOJYJZJO
SOFS;YXFD:TTXL_FIBMSDNBROIVF:ZOR
:XFSLYAZX:_OBTKTDZQKY:JC:.EQ.RTZ
ZFOCDULTTEFAY_UKNG._WZW;WRJKR,FX
VGJRKPWFVÑ;ZT;PHFYD;PS_FMNQTUUAA
RGFFQFFUP,K,AÑKXZR,CBXW;_XPQVEOJ

 

6. Descifrado

El descifrado sigue los mismos pasos para el completado de la clave y el desordenamiento del alfabeto. Al tomar el primer bloque cifrado, se hace el XOR con la clave, y lo que se obtiene es el bloque desordenado, que se tomará como clave para descifrar el siguiente. En suma:

a) Completar la clave, si es necesario
b) Desordenar el alfabeto, por el mismo procedimiento de la fase de cifrado
c) Generar una clave nueva, por el método descrito
d) Leer un bloque de 32 caracteres del cifrado
e) Hacer XOR con la clave. Eso nos proporciona el bloque en claro desordenado
f) Tomar el bloque en claro desordenado como clave para el siguiente bloque
g) Reordenar el bloque mediante la clave vigente, y escrbirlo en el fichero de salida
h) Volver a d)

Como podéis ver, no se trata de nada nuevo, sino de una forma de "self-synchronizing stream cipher" o de "ciphertext autokey" (CTAK). (http://en.wikipedia.org/wiki/Stream_cipher), que presentan diversas vías de atque, a diferencia de los auténticos OTP con clave aleatoria infinita, que tienen Secreto Seguro. Mi esperanza es que al tomar como clave el bloque desordenado se incorpore suficiente entropía como para dificultar los ataques basados en texto probable. Pero dada la voracidad reinante por estas aguas, no las tengo todas conmigo.

 

Problema

El problema consiste en descifrar este fichero:

 

LlamameX, Ya he corregido el

LlamameX, Ya he corregido el error, ¿puedes verificar que tal se adaptan estos alfabetos?

ÑPKH:YERXWCB;QO,JGFUVNATD_ZISLM. 0,1675
ÑTQXJDFU_:KBHRM;,LVPSAENWZIOC.YG 0,174
ÑGIWT;_JOFYMSZHKXU,BRVNPQD:EA.CL 0,1858
ÑPWJME,NVUT:CGIAQ;.XRHKSYZLDO_BF 0,1946

Pues tampoco demasiado bien

Producen estas claves

_LTRLCLL____L_L___K___KZLPK__KKR
FÑXB*_FFFFFÑ_FXFÑFFFXF_,FBFFOÑFF
KBBDKKBKCBKKKBBBKB_KBKK_KWBKDBKP
EÑCEÑECRAKEEÑEECCEEEAEAYRCÑÑYJEE

Vamos a probar el concepto con un cifrado conocido, por ejemplo con el de prueba de AESITO con alguna clave, con este algoritmo.

El problema es que converge

El problema es que converge muy mal, no es como una cifra de substitución en que pruebas alfabetos y la gráfica no tiene dientes de sierra, así que no sé si solo con esto valdrá. Tengo que probar con tus restricciones también. Pero estoy haciéndolo bien ¿no?. Para calcular los pesos a partir de la tabla utilizo las frecuencias reales. Luego las comparo con las del cifrado.

Voy despacio porque me ha tocado un momento de mucho curro en el trabajo, valga la redundancia, pero sigo en ello.

Uy si

Que somos muy blanditos XDDD

No hombre no, si ya mola que se resista y que obligue a retorcernos las neuronas. Yo en particular voy bastante pillado de tiempo y le dedico el que voy pudiendo.

El problema del AG de Tokamak es parecido al que me encontre con mi aproximación patatera. Los dientes de sierra en las aproximaciones. Muchas soluciones dan números válidos al converger a ellas siendo incorrectas, con lo que hay que estar de inicio muy cerca para que funcione.

No descarto que por ahi haya solución, pero hay que dar con la función adecuada.

¡Pues claro que es broma!

Si no se saca de su contexto, no cabe otra interpretación... y menos conociéndote como te conocemos; Ilustre y admirado Agustín. Así lo he interpretado yo también y me inclino a pensar que no sea por ganas, saber y saber hacer de los versados criptoanalistas habituales en este fértil y criptorrético lugar sino que, como ha apuntado tokamak, la falta de tiempo les obligará a realizar primero otras tareas que no admiten demora ya que el reto puede esperar indefinidamente y... como tampoco pide pan... ;-)

De todas formas ya es todo un Sr. Reto; ¿no crées? Puede que no tanto como el del documento Sertori -o Sirtori- que, aunque en otra línea, también está ahí como un referente de altura.

El nivel, en mi opinión, es alto y eso hace que mantener la calidad -base y sustento de Kriptópolis- no sea una tarea fácil... llevadera sí, puesto que el substrato técnico es de lo mejor y sobra talento; pero de ninguna manera fácil.

Paciencia, ya verás como ellos también saben que es una broma... ¡faltaría más!

Saludos cordiales,

Pedro Fernández
--

Otra vía de ataque

Bueno, que no se detenga la máquina. Aunque esos caminos no parecen conducirnos a resultados directos no se acaba ahí el mundo, con permiso de los mayas.

Se me ocurre una nueva vía de ataque basándome en la misma teoría que el anterior, pero en este caso apuntando a los caracteres menos frecuentes. Resulta chocante tener sólo 393 ocurrencias de V (frente a las 2419 Ñs, 6 veces menos) cuando hay 32 emparejamientos (16 si no distinguimos los simétricos AB-BA) que nos pueden proporcionar ese carácter, especialmente cuando pensamos que entre esas parejas estarán forzosamente incluidas las que contengan carácteres muy frecuentes como el espacio, la A o la E.

Esto me lleva a pensar que en esas parejas deben estar formadas por un carácter frecuente junto con un infrecuente, de manera que sus apariciones se compensen y que no debe haber muchas maneras de conseguir esto. Así, debería ser posible aislar las combinaciones de parejas que nos den una frecuencia baja para un carácter consiguiendo, por tanto, restricciones del tipo f("V")=f(A[i])^f(A[j]) que deberíamos poder trasladar al alfabeto derivado.

Combinación

La idea es que hay 16 parejas de valores (no distinguiendo simétricos) que producirán al xorearse el valor que traduciremos como V. De esas parejas, por fuerza, una contendrá el "_", otra la "A", otra la "E", etc. Si la pareja que contiene a "_" también contuviera a la "A" (u otro carácter frecuente) aparecería muchas veces, cosa que sabemos que no ocurre. Por tanto el "_" tiene que estar emparejado, para producir la V, con un carácter poco frecuente, pongamos el ";". Lo mismo para el resto.

La idea es conseguir un juego de 16 parejas que minimize la frecuencia de un carácter y la acerque al valor que encontramos en el cifrado.

Año nuevo n-gramas nuevos

Más que nada por hacer el esfuerzo de recuperar la actividad tras la hibernación obligada por las digestiones navideñas os cuento en que ando: Tengo algunos métodos que dan resultados parciales pero usando cantidades absurdas de texto (trabajo con 3 novelas enteras concatenadas de B.P.Galdós para conseguir varios millones de caracteres). Algunos de los métodos són:

- Buscar "quasi-palindromos" de la forma "K_abc_K" (la K es mi 0 en mi cifrado, como la Ñ lo es en el de Agustín) de manera que obtenemos que f(a)^f(b)=f(c). Esto funciona bastante bien (no 100% puesto que la K también puede provenir de otros carácteres probables como f('A')^f('A') o f('E')^f('E') con lo que el palíndromo sería otro) aunque hay muy pocos casos aún con mucho texto.

- Buscar tetragramas con inicios conocidos pero con finales distintos. Por ejemplo

Sabemos que K+K+L corresponde a _+_+_+A, con lo que el siguiente más probable empezando por K+K+L (en mi caso K+K+L+D) debería corresponder a _+_+_+A+E, obteniéndose que f('A')^f('E')=f('D'). Podemos verificarlo además sabiendo que si K+K+Ñ es _+_+_+E entonces K+K+Ñ+D debe ser la más frecuente de los que empiecen por K+K+Ñ como efectivamente ocurre.

Esta verificación nos permite distinguir falsos positivos como, por ejemplo, que K+K+L+J sea el siguiente en frecuencia nos llevaría a pensar que proviene de _+_+_+A+O, pero como sabemos que K+K+I proviene de _+_+_+O entonces K+K+I+J vendria de _+_+_+O+A con lo que sería la más frecuente de las que empiezan por K+K+I y no es así. Sin embargo, sabiendo que K+K+M proviene de _+_+_+S si nos cuadra que provenga de _+_+_+A+S puesto que K+K+M+J es la más frecuente de las que empizan por K+K+M.

Como se ve se trata de avances lentos con pasitos cortitos, consiguiendo definir reglas que permitan limitar un ataque contra el alfabeto derivado. Dichas reglas, además, tampoco son absolutas puesto que el xor compensa muuucho las diferencias en frecuencias y a la que nos vamos de los caracteres más habituales aparece mucha contaminación proviniente de otras parejas que generan los mismos resultados.

Bueno pues eso, que seguimos en la brecha y feliz año 1 maya a todos.

Es que es difícil. Hoy he

Es que es difícil. Hoy he dedicado un buen rato a RUBIK2, no está abandonado aunque no saco por ahora. Creo que esperaré un poco más para desvelar EL GRIAL, sólo atascaría más el cotarro, porque va a ser complicadillo, me temo...

Estoy avanzando con el texto largo

He encontrado una técnica que me está permitiendo avanzar bastante rápidamente en el análisis y validación del texto largo (descarto de momento trabajar con el corto) en base a confirmaciones cruzadas de trigramas equivalentes, cosa que me permite filtrar la contaminación que viene de parejas del mismo resultado XOR. Tengo ya muy fijas las relaciones entre los XOR de los carácteres más probables (son los fáciles) con lo que con 6 suposiciones consigo 14 caracteres del alfabeto derivado.

Los caracteres de frecuencia más baja me van a dar problemas, pero si consigo relacionarlos con los de frecuencia más alta (a través de un tercer carácter) podría obtenerlos también.

No se si acabaré llegando a alguna parte, pero por fin tengo la sensación de estar pisando terreno (algo) sólido con FOTP.

Frecuencias filtradas

Al final del proceso de limpieza de frecuencias obtengo los siguientes valores.

Ai|Reg|Peso
--+---+-----
J | _ | 2206
R | A | 2066
M | E | 2055
X | O | 1833
V | S | 1286
P | R | 1270
Y | N | 1078
: | I | 1065
Z | L | 1040
A | D | 867
L | U | 785
C | T | 759
; | C | 639
? | M | 477
, | P | 463
W | B | 448
K | . | 294
H | , | 230
S | Q | 227
E | V | 167
B | G | 142
D | H | 105
F | Y | 102
_ | F | 79
U | J | 39
. | Z | 19
I | ; | 15
G | Ñ | 0
N | X | 0
O | : | 0
Q | K | 0
T | W | 0

Que corresponden a las relaciones tipo f(Ci)=f("_")^f(Ai) . La columna central es la correspondiente a la distribución Regenta. Los números de la derecha no son frecuencias absolutas sino pesos asignados por el proceso pero que se equiparan a éstas. Así podemos asumir, por ejemplo, que f("J")=f("_")^f("_") o que f("R")=f("_")^f("A"). Siempre digo que f(Ai) es la función de sustitución, que es correcto, pero quizás es más claro decir que f(Ai) es la posición de Ai en el alfabeto derivado.

Considero este paso como muy relevante aunque queda bastante por hacer. Como puede verse no hay datos de los caracteres poco frecuentes, que deberán obtenerse de manera indirecta por su aparición en otras relaciones. También puede verse que hay pesos muy parecidos, como los que corresponderían a la E y la A o la S y la R, con lo que buscaré nuevas verificaciones para acabar de fijarlas.

Estos datos corresponden al XOR con el espacio, pero el mismo proceso lo estoy preparando para el XOR con la A y la E, que aparte de verificaciones me proporcionarán nuevas restricciones para el alfabeto.

Espero poder llegar a algún resultado ya que esto, de momento, promete.

Páginas

opinar

Texto puro

  • No se permiten etiquetas HTML.
  • Las direcciones de las páginas web y las de correo se convierten en enlaces automáticamente.
  • Saltos automáticos de líneas y de párrafos.
By submitting this form, you accept the Mollom privacy policy.