PDF de programación - Ataque de texto claro escogido contra la clave de protocolo del cifrado de Doble Criptograma Simétrico

Ataque de texto claro escogido contra la clave de

protocolo del cifrado de Doble Criptograma Simétrico

Manuel J. Lucena López

27 de enero de 2013

Resumen

Se presenta un ataque de texto claro escogido para el sistema de cifrado Doble Crip-
tograma Simétrico, descrito en la solicitud internacional de patente WO 2012/152956 A1.
En dicho documento se describe un algoritmo de cifrado en dos fases, que cumple supues-
tamente el criterio de seguridad perfecta de Shannon. La segunda de sus fases consiste en
la aplicación de una clave de protocolo que genera una secuencia de valores comprendidos
entre 1 y 9. El ataque que se describe permite obtener el valor de la citada clave de pro-
tocolo a partir de un número relativamente pequeño de criptogramas correspondientes a
un mismo texto en claro.

Advertencia

Tanto el ataque que se propone en este documento, como la implementación parcial
del método de cifrado empleada para ponerlo en práctica, se basan en interpretaciones
realizadas sobre la solicitud de patente en la que se describe el mismo. Por lo tanto,
no se ha podido comprobar ni la exactitud de la implementación, ni la efectividad del
ataque descrito con datos de referencia, obtenidos mediante una implementación oficial
del método de cifrado Doble Criptograma Simétrico.

1.

Introducción

En la solicitud de patente internacional WO 2012/152956 se describe un algoritmo de
cifrado, que supuestamente cumple los criterios de seguridad perfecta de Shannon. Dicho
algoritmo se compone los siguientes elementos:

1. Una matriz alfanumérica.

2. Una matriz base de residuos numéricos.

3. Una clave de equivalencias.

4. Una tabla de equivalencias.

5. Un criptograma de residuos reducidos o plantilla.

6. Una clave de protocolo.

7. Un algoritmo de codificación.

8. Un criptograma final de residuos.

9. Un algoritmo de decodificación.

1

Los elementos del 1 al 5 permiten convertir cada letra del texto en claro una secuencia
de p dígitos (d1, d2, ...dp), con di comprendido entre 1 y 9. El valor de p se denomina
profundidad. La tabla que asocia cada letra con cada secuencia es estática, y se calcula a
partir de la denominada clave de equivalencias. La tabla de equivalencias puede contener
más de una entrada asociada a la misma letra, en cuyo caso se escogerá una de ellas, de
manera aleatoria, durante el proceso de cifrado. A la concatenación de todas las secuencias
generadas a partir del texto en claro se le denomina plantilla (segunda columna de la figura
2).

El siguiente paso consiste en transformar la plantilla, empleando la llamada clave de
protocolo (Kp) compuesta por una serie de números enteros (n1, n2, ...) mayores o iguales
a 1. El proceso se lleva a cabo tomando el primer valor de la clave, y expandiendo el
primer dígito de la plantilla en una secuencia de dígitos de longitud n1, el segundo en una
secuencia de n2 y así sucesivamente. En la descripción del algoritmo se sugiere emplear
los valores de Kp de forma cíclica, hasta acabar con todos los dígitos de la plantilla.

El proceso de expansión de cada dígito pi de la plantilla se hace generando una se-
cuencia de números (de longitud igual al valor correspondiente de la clave de protocolo)
comprendidos entre 1 y 9, de forma que el resto de dividir por 9 la suma de éstos sea igual
a pi. Puesto que los restos van de 0 a 8, y el valor de pi va de 1 a 9, el resto 0 es sustituido
directamente por un 9. El resultado obtenido es un criptograma (tercera columna de la
figura 2) asociado al texto claro del que partíamos inicialmente.

Como puede observarse, el número de dígitos del mensaje cifrado resulta muy superior
al número de caracteres del texto claro. Es fácil comprobar, dado el carácter aleatorio de
varios de los pasos involucrados en el proceso de cifrado, que existen múltiples criptogra-
mas diferentes asociados a un mismo texto claro cifrado con los mismos parámetros.

2. El ataque

Nos proponemos, a partir de un número relativamente bajo de criptogramas, todos
asociados al mismo texto claro, y obtenidos con los mismos parámetros del algoritmo,
recuperar tanto la clave de protocolo Kp empleada como las plantillas correspondientes a
todos los criptogramas. El proceso se basa en varios hechos:

Aunque se empleen diferentes secuencias para expandir un mismo dígito de una
misma plantilla, todas ellas poseen el mismo residuo.

Las plantillas generadas cuando se cifre varias veces el mismo mensaje serán iguales
en posiciones asociadas a las letras con una única imagen en la tabla de equivalencias.

Si una letra tiene n imágenes diferentes en la tabla de equivalencias, las plantillas
asociadas a distintos cifrados de la misma presentarán como máximo n combinaciones
de valores diferentes en las posiciones correspondientes.

Dado el carácter aleatorio del proceso de cifrado, cualquier subcadena de un conjunto
de criptogramas que no se corresponda exactamente con un dígito de la plantilla
presentará valores distribuidos de forma aleatoria, por lo que todas las combinaciones
de residuos serán igualmente probables.

Supongamos que queremos generar n criptogramas diferentes, todos asociados an mis-
mo texto en claro. El proceso de cifrado tomará de la tabla de equivalencias una de las
secuencias de dígitos asociadas a cada letra, de forma aleatoria. Posteriormente, cada uno
de esos dígitos se expandirá empleando la clave de protocolo, en una secuencia aleatoria de
números, con la condición de que su residuo módulo 9 (cambiando el 0 por el 9) coincida
con el dígito en cuestión.

Puesto que esas secuencias se generan de forma aleatoria (salvo por su último número,
que se ajusta para que cumpla la condición impuesta), si agrupamos todas las subcade-
nas en una posición y longitud determinadas en un conjunto suficientemente grande de

2

Figura 1: El segmento S1 del criptograma presentará tantos residuos diferentes como números
distintos haya en la tabla de equivalencias para el símbolo del texto claro, mientras que el seg-
mento S2 presentará todos los residuos siempre que haya suficientes criptogramas. El segmento
P 1 de la plantilla, al coresponder siempre a la misma letra del texto claro, contendrá pares de
valores muy correlacionados, a diferencia de S2.

criptogramas, y anotamos la cantidad de residuos diferentes que aparecen, pueden pasar
dos cosas:

Que la posición y longitud de la subcadena no coincida con la expansión de un dígito
de la plantilla (segmento S2 de la figura 2): con una alta probabilidad aparecerán
todos los posibles residuos (del 1 al 9).

Que la posición y longitud coincida con la expansión de un dígito de la plantilla
(segmento S1 de la figura 2): Solo aparecerán los dígitos que estén presentes en las
posiciones correspondientes de la tabla de equivalencias para la letra del texto claro
en cuestión.

Por lo tanto, podremos detectar las posiciones y longitudes de las subcadenas corres-
pondientes a la expansión de cada símbolo de la plantilla, siempre que en ellas no aparezcan
todos los residuos posibles. La primera fase de nuestro ataque consistirá en extraer todas
las subcadenas que no presenten todos los residuos en los criptogramas.

Después de este primer paso, es posible que queden subcadenas sin identificar, que
podrían corresponder a letras que tienen todos los dígitos en una (o varias) posiciones de
sus imágenes. Un ejemplo con profundidad 3 sería 111, 122, 133, 144, 155, 166, 177, 188, 199.
En este caso, no podríamos deducir más que la subcadena correspondiente al primer dígito,
ya que siempre tendría residuo 1. Sin embargo, si combinamos en cada criptograma el
residuo del primer dígito con el del segundo, podemos ver que solo hay 9 combinaciones
diferentes, muchas menos de las que cabría esperar si los valores tuvieran un aspecto
aleatorio (si hubiéramos seleccionado mal las subcadenas). Llevaremos entonces a cabo
una segunda fase, que consistirá en calcular los residuos de una subcadena detectada en la
fase anterior (en la figura, S1), y combinarlos con los residuos de una subcadena contigua
no marcada: si el número de pares de residuos resultante resulta claramente inferior al

3

producto de las cantidades de residuos por separado, significará que ambas subcadenas
representan valores correctos de la clave de protocolo, y además están asociadas a la misma
letra del texto claro. Por lo tanto, habremos detectado otra subcadena (y otro número de
la clave de protocolo).

Con este método podemos recuperar casi por completo la clave de protocolo, aún
con un número modesto de criptogramas (del orden de la centena), y con un número de
imágenes para cada letra relativamente elevado (del orden de la treintena).

Si finalmente conseguimos la clave de protocolo y, por tanto, las plantillas, solo quedaría
estimar la profundidad empleada para poder conocer la totalidad de imágenes diferentes
que tiene cada letra del texto claro. Esto permite convertir en la práctica la plantilla en
un cifrado monoalfabético, fácilmente susceptible de ser analizado mediante un ataque de
frecuencias.

Un método simple para deducir la profundidad sería analizar la correlación entre re-
siduos de subcadenas (o, si se prefiere, valores de la plantilla) de los criptogramas co-
rrespondientes a símbolos contiguos en la plantilla. Puesto que solo aquellas subcadenas
que pertenezcan a la misma letra del texto claro (segmento P 1 en la figura 2)tendrán
una alta correlación, los pares con baja correlación (segmento P 2 de la figura 2) deben
aparecer separados a una distancia igual a la profundidad de la plantilla. Para detectar
esa correlación, contaremos cuántos pares de valores de plantilla diferentes presentan las
dos subcadenas, en relación con el número de residuos que tienen por separado. Si no hay
correlación, es de esperar que el primer valor se aproxime al producto de los dos últimos,
y que sea mucho más pequeño en el caso contrario.

3. Resultados experi