Distancia de unicidad

Para un cifrador la distancia de unicidad, también llamada punto de unicidad, es el valor mínimo de caracteres del texto cifrado que se necesitan para reducir a una el número de claves posibles y, por tanto, romper el cifrado. Es decir, después de intentar todas las posibles claves (fuerza bruta del espacio de claves) sólo hay una que puede hacer que el descifrado tenga sentido. La distancia de unicidad es posible a causa de la redundacia de los idiomas humanos (puesta de manifiesto cuando se estudia su ratio de entropía).

El concepto de distancia de unicidad fue introducido por C. E. Shannon.^[1]

La distancia de unicidad permite medir el secreto de un cifrador a partir de la cantidad de incertidumbre (entropía) de la clave condicionada por el conocimiento del texto cifrado ( $H_{C}(K)$ ). Si $H_{C}(K)=0$ entonces no hay incertidumbre y el cifrador es teóricamente rompible teniendo los suficientes recursos. La distancia de unicidad es la longitud mínima del texto cifrado que se necesita para determinar de forma única la clave.^[2]

Un cifrador se dice que es incondicionalmente seguro si $H_{C}(K)$ nunca se aproxima a 0 incluso para longitudes largas de texto cifrado.^[2] De la propia definición de secreto perfecto se puede concluir que un cifrador que tiene secreto perfecto no tiene distancia de unicidad y por tanto es incondicionalmente seguro. Shannon usaba el término secreto ideal para describir sistemas que no logran el secreto perfecto pero sin embargo no se pueden romper porque no dan suficiente información para determinar la clave.^[2]

Formalización teórica

Entropías condicionales interesantes en un sistema de cifrado

Para un sistema de cifrado hay una serie de entropías condicionales interesantes:^[3]^[4]

Supongamos

Un mensaje M₁ es sometido a un proceso de cifrado usando la clave K₁ obteniendo E(K₁,M₁)=C₁.
$P_{C}(K)$ representan la probabilidad condicional de la clave K dado el criptograma recibido C. A veces también se denota por $P(K|C)$
$P_{C}(M)$ representan la probabilidad condicional del mensaje M dado el criptograma recibido C. A veces también se denota por $P(M|C)$

Entonces:

Podemos medir la incertidumbre (la entropía) del conocimiento de la clave una vez conocido el texto cifrado, y por tanto medir la equivocación del mensaje (en inglés message equivocation), $H_{C}(K)$ , también denotada por $H(K|C)$ , mediante la fórmula:

$H_{C}(K)=-\sum _{E,K}P(E,K)\log _{P_{E}}(K)=-\sum _{E}P(E)\sum _{K}P_{E}(K)\log _{P_{E}}(K)$

La primera igualdad es por la definición de la entropía condicional y la segunda por aplicación del teorema de Bayes.

Observar que si

H_{C}(K)=0

significa que se podrá romper el cifrado pues ya no hay incertidumbre. Esta anulación nos introduce en el concepto de distancia de unicidad.

Podemos medir la incertidumbre (la entropía) del conocimiento del mensaje una vez conocido el texto cifrado, y por tanto medir la equivocación de la clave (en inglés key equivocation), $H_{C}(M)$ , también denotada por $H(M|C)$ , mediante la fórmula:

$H_{C}(M)=-\sum _{E,M}P(E,M)\log _{P_{E}}(M)=-\sum _{E}P(E)\sum _{M}P_{E}(M)\log _{P_{E}}(M)$

La primera igualdad es por la definición de la entropía condicional y la segunda por aplicación del teorema de Bayes.

Podemos medir la incertidumbre (la entropía) del conocimiento de la clave una vez conocido el texto cifrado y el mensaje en claro, y por tanto medir la equivocación del aspecto de la clave (en inglés key appearance equivocation), $H_{C,M}(K)$ , también denotada por $H(K|M,C)$ , mediante la fórmula:

$H_{C,M}(K)=-\sum _{E,M,C}P(E,K,M)\log _{P_{E,M}}(K)$

Podemos medir la incertidumbre (la entropía) del conocimiento del mensaje una vez conocido el texto cifrado y la clave, denotado por $H_{C,K}(M)$ o por $H(M|K,C)$ . Dada una clave la relación entre texto cifrado y texto en claro es uno-a-uno y por tanto $H_{C,K}(M)=0$

Se ha demostrado^[4] que se cumple la siguiente relación entre las distintas entropías:

$H_{C,M}(K)=H_{C}(K)-H_{C}(M)$

Esta relación nos pone de manifiesto un hecho bastante curioso:^[4]

En general el objetivo de cualquiera que use un cifrador es tener un valor de

H_{C,M}(K)

alto para que el sistema tenga la máxima fortaleza posible para el caso de que el atacante disponga tanto del texto cifrado como del texto plano (ataque con texto plano conocido). Sin embargo, por la expresión de la ecuación, para ello es necesario que

H_{C}(M)

sea pequeño. Sin embargo, tener un valor pequeño de

H_{C}(M)

implica que haya poca incertidumbre respecto al texto plano una vez conocido el texto cifrado (ataque con sólo texto cifrado disponible), lo cual es contrario a los intereses de cualquiera que cifre un mensaje. Por tanto es necesario una solución de compromiso para que el sistema tenga una fortaleza aceptable para ambos tipos de ataque

Considerando la longitud del criptograma

Podemos calcular $H_{C}(K)$ y $H_{C}(M)$ para aquellos criptogramas de una cierta longitud N (en el sumatorio sólo se consideran esos criptogramas).A estos valores son denotados por $H_{C}(K,N)$ y $H_{C}(M,N)$ . Otra notación alternativa equivalente es $H(K/C^{N})$ y $H(M/C^{N})$ .

La distancia de unicidad de un sistema de cifrado, si existe, nos da el valor mínimo valor de N para el cual $H_{C}(K,N)=0$ . Es decir, da el valor mínimo de la longitud del criptograma, N, para la que cierta clave K tiene probabilidad uno y el resto tiene probabilidad 0. Este valor es posible a causa de la redundacia de los idiomas humanos (puesta de manifiesto cuando se estudia su ratio de entropía).

Hay que remarcar que aunque la distancia de unicidad da un valor para el cual $H_{C}(K,N)=0$ , esto no garantiza que la clave pueda ser encontrada para cada situación concebible.^[5] Esto sólo sucede en media. Esto es debido a los conceptos que se usan en la teoría de la información, como entropías, ratios, etc.. La distancia de unicidad representa valores medios de símbolos o letras requeridos.

Está demostrado^[1] que se cumplen las siguientes propiedades:

i)

H_{C}(K,S)\leq H_{C}(K,N)

si

S\geq N

(La equivocación de la clave es una función no creciente de N)

ii))

H_{C}(M,S)\leq H_{C}(M,N)

si

S\geq N

(La equivocación de los A primeros caracteres del mensaje es una función no creciente del número N de caracteres interceptados).

iii)

H_{C}(M,N)\leq H_{C}(K,N)

(Si N caracteres han sido interceptados, la equivocación de los primeros N caracteres del mensaje es menor o igual que la de la clave).

Además se cumple^[5] el siguiente teorema:

$H(K/C^{N})\geq H(K)-D_{N}$

donde

D_{N}

representa la redundancia del texto en claro de longitud N, la cual es la diferencia entre la ratio absoluta y la ratio del idioma (

D=R_{0}-R

).

Por tanto acotando a la longitud N y suponiendo que ε es el número de símbolos diferentes del texto en claro y del texto cifrado, obtenemos

D_{N}=N\log(\epsilon )-H(M^{N})

De la expresión podemos concluir que la si la redundancia incrementa, la equivocación media de la clave y por tanto la incertidumbre con respecto de la clave usada decrece. Por tanto la redundancia hace la tarea de encontrar la clave sea más fácil. Análogamente, métodos que reduzcan la redundancia mejoran la seguridad del criptosistema.

Otra conclusión que se puede obtener de la ecuación es que, al ser

H(K/C^{N})\geq 0

,

H(K)\geq D_{N}

, es decir, la equivocación de la clave, de forma general, no será cero y por tanto la clave no podrá determinarse de forma inequívoca.

Cálculo

El método tradicional para el cálculo, normalmente aproximado, de la distancia de unicidad fue el propuesto por Shannon.^[1] Posteriormente Hellman extiende las conclusiones de Shannon y propone nuevas técnicas para estimar la distancia de unicidad.

La mayor parte de los cifradores son demasiado complejos para determinar las probabilidades requeridas para obtener la distancia de unicidad. Sin embargo Shannon mostró^[1] que es posible aproximarse al valor para cierto tipo de cifradores usando un modelo de cifrador al que llama cifrador aleatorio. En este cifrador modelo demuestra que el valor aproximado de la distancia de unicidad es ${\dfrac {H(K)}{D}}$ . Aprovechándose de este resultado Shannon estima el valor de la distancia de unicidad para otros cifradores.

Martin Edward Hellman^[6] derivó los mismos resultados que Shannon para la distancia de unicidad del cifrador aleatorio pero siguiendo un enfoque un poco diferente. Hellman usó un argumento de conteo, para dada una secuencia de símbolos de texto cifrado, encontrar el número de claves que podían haber generado esa secuencia particular. Hellman además muestra que el cifrador aleatorio tiene, entre la clase de los cifradores con el mismo tamaño de clave y tamaño de texto plano, la mínima distancia de unicidad y por tanto es el caso peor.^[7] Beauchemin and Brassard^[8] generalizaron los resultados para incluir cifradores con claves y mensajes en claro que siguen distribuciones de probabilidad uniformes (aleatorias).^[7]

Cálculo para un cifrador aleatorio

Veamos el cálculo de la distancia de unicidad para el cifrador aleatorio^[9]

Cifrador aleatorio

Shannon definió un cifrador aleatorio como un sistema de cifrado que satisface las siguientes tres condiciones:

i)El número de posibles mensajes de longitud N es

T=2^{NR_{0}}

con

R_{0}

la ratio absoluta con valor

R_{0}=\log A

donde A es el cardinal del alfabeto que usa tanto el texto plano como el texto cifrado.

ii) Los posibles mensajes de longitud N pueden ser divididos en dos grupos:

Un grupo de los que tienen a priori una probabilidad alta y casi uniforme (los mensajes con significado).
Otro grupo con una insignificante probabilidad total.

El grupo con alta probabilidad contiene

S=2^{NR}

mensajes, con

R=(1/N)H(M^{N})

es la entropía por letra de mensajes de N letras.

iii) El proceso de descifrado puede formalizarse como una serie de líneas que relacionan cada criptograma con una serie de textos en claro. Vamos a asumir que hay k claves equiprobables. Por tanto habrá k líneas hacia cada criptograma que proceden de una selección aleatoria de los posibles mensajes.

Cálculo

Para el cifrador aleatorio, dado un criptograma, la probabilidad de obtener un mensaje con significado al descifrar usando una clave dada es:

S/T=2^{-N(R_{0}-R)}=2^{-ND}

donde D es la redundancia del idioma, para mensajes de N caracteres, medida en bits/carácter.

Vamos a suponer que podemos aproximar el valor de redundancia del idioma para mensajes de N caracteres, por la redundancia del idioma. La redundancia del idioma es la diferencia entre la ratio absoluta y la ratio del idioma y por tanto se puede expresar con la ecuación:

D=\log A-H(M)

Para el cifrador aleatorio, como hay k claves equiprobables entonces el valor de su entropía es $H(K)=\log _{2}k$ y por tanto $k=2^{H(K)}$ . Entonces, el valor esperado de criptogramas descifrados con significado es:

2^{H(K)-ND}

Por tanto:

Si H(K)>>ND, entonces hay una gran probabilidad de obtener un criptograma descifrado con significado y entonces una baja probabilidad de determinar la clave y el mensaje correctos.
Si H(K)<<ND, entonces tan pronto como se obtenga un criptograma descifrado con significado, entonces tiene casi toda probabilidad de ser el único correcto.

La frontera entre estas dos situaciones está determinada por la cantidad

N_{0}=H(K)/D

a la cual se le llama distancia de unicidad.

Cuando la información de la fuente es baja, sólo se requieren un pequeño número de símbolos (N) para llegar a la distancia de unicidad. En la práctica esto puede paliar asegurando una mínima información para los mensajes, por ejemplo usando un sistema de codificación.

Cálculo para un cifrador por sustitución monoalfabética aplicado al idioma inglés

Podemos aplicar lo obtenido a un cifrador por sustitución monoalfabética aplicado al idioma inglés.^[4] Consideremos un cifrado en inglés (alfabeto de 27 letras) cifrado usando una sustitución monoalfabética. Si suponemos válida la aproximación a la ratio del idioma, H(M)=2, obtenemos los siguientes resultados:

D=\log(\epsilon )-H(M)=\log 26-2=2.7

bits

Estos sistemas tienen 26! posibilidades para la clave. Asumiendo que la incertidumbre para cada clave es la misma, la información de cada clave es:

H(K)=\log 26!=88.38

bits

Por tanto la distancia de unicidad vale aproximadamente 32 ( $N_{0}=H(K)/D=88.38/2.7=32.73$ caracteres). Por tanto, de media se necesitará un criptograma de 32 letras para encontrar la clave correcta.

Para el caso del cifrado Cesar H(K)=26 y por tanto ( $N_{0}=H(K)/D=4.70/2.7$ ) es aproximadamente 2.^[2] Observar que este resultado no parece plausible ya que ningún cifrador por sustitución puede ser resuelto con sólo 2 caracteres. Hay que tener dos cosas en cuenta:

La estimación que usamos de D=2.7 es aplicable sólo para mensajes de longitud razonable.
El cifrador es una pobre aproximación del cifrador aleatorio. Esto se debe a que la mayoría de los criptogramas no son producidos por mensajes con significado. Por ejemplo el criptograma QQQQ sólo puede ser producido por AAAA,...,ZZZZ. Por tanto los mensajes en claro descifrados no están uniformemente distribuidos sobre el espacio completo de mensajes. Sin embargo, los cifradores por desplazamiento pueden ser generalmente resueltos con sólo unos pocos caracteres del criptograma.

Cálculo para el DES

Consideremos el cifrador DES, el cual cifra bloques de 64 bits usando claves de 56 bits. Al DES se relativamente similar al modelo del cifrador aleatorio. Si suponemos que D=3.2 la distancia de unicidad es:

N_{0}=H(C)/D=56/3.2=17,5

caracteres

Si doblamos la clave a 112 bits, la distancia de unicidad aumentará a más o menos 35 caracteres.

Observar que de que la distancia de seguridad para un cifrado de sustitución genérico sea mayor que el del DES, no se puede inferir que el cifrado de sustitución sea más seguro que el DES. Realmente el DES es más seguro porque no es susceptible a ser roto usando técnicas de análisis de frecuencias.

Cálculo en otros cifradores

Deavours^[10] estudia la distancia de unicidad en algunos cifradores clásicos.

Limitaciones

Aunque la distancia de unicidad aporta una forma fácil de manejar distintas distribuciones de probabilidad, el parámetro relevante que hay subyacente es la probabilidad de error, es decir, la probabilidad de incorrecta identificación de la clave que tiene el criptoanalista. Para el estudio de este error se ha desarrollado el concepto de Probabilidad de error de seguridad (en inglés Probability error-security) que normalmente se nota por Pe-seguridad (de inglés Pe-security) y se ha definido la llamada distancia Pe-seguridad.^[11]^[4]^[11] La distancia Pe-seguridad de un cifrador es la longitud mínima esperada del criptograma, generada por el cifrador, necesaria para obtener el texto plano original con una probabilidad media de error (o probabilidad de identificación incorrecta media) de al menos Pe

Referencias

↑ ^a ^b ^c ^d C. E. Shannon, "Communication Theory of Secrecy Systems"
↑ ^a ^b ^c ^d Dorothy Elizabeth Robling Denning,"Cryptography and Data Security",Addison-Wesley 1982
↑ "Applied cryptology, cryptographic protocols and computer security models", Richard A. DeMillo et all. American Mathematical Society 1983
↑ ^a ^b ^c ^d ^e "Basic methods of cryptography", J. C. A. Lubbe, Cambridge University Press 1998
↑ ^a ^b J.C.A. Lubbe "Basic Methods of Cryptography". Cambridge University Press 1998
↑ Hellman, M. E., "An extension of the Shannon Theroy Approach to Cryptography". IEEE Trans. on Info. Theory. Vol IT-23 pp. 289-994 May 1977
↑ ^a ^b A. Kh Al Jabri, "The unicity distance: An upper bound on the proability of an eavesdropper successfully estimating the secret key", King Saud University, Arabia Saudí 1996
↑ P. Beauchemin and G. Brassard, "A Generalization of Hellman's Extension to Shannon´s Approach to Cryptography". Journal of Cryptology 1988.
↑ M. Davio, J., M. Goethals, "Elements of cryptology", Philips Research Laboratory, Brussels
↑ Deavours, C. A., "Unicity Points in Cryptanalysis," Cryptologia Vol. 1 (1) pp. 46-68 (Jan. 1977).
↑ ^a ^b Johan Van Tilburg, Dick E. Boekee, "The Pe-security distance as a measure of cryptographic performance", Trattement du Signal volume 4 nº6 1987

Datos: Q1640661

[Shannon_1-1] C. E. Shannon, "Communication Theory of Secrecy Systems"

[Dorothy_Elizabeth_1-2] Dorothy Elizabeth Robling Denning,"Cryptography and Data Security",Addison-Wesley 1982

[3] "Applied cryptology, cryptographic protocols and computer security models", Richard A. DeMillo et all. American Mathematical Society 1983

[Basic_methods_1-4] "Basic methods of cryptography", J. C. A. Lubbe, Cambridge University Press 1998

[Lubbe_1-5] J.C.A. Lubbe "Basic Methods of Cryptography". Cambridge University Press 1998

[6] Hellman, M. E., "An extension of the Shannon Theroy Approach to Cryptography". IEEE Trans. on Info. Theory. Vol IT-23 pp. 289-994 May 1977

[Kh_Al_1-7] A. Kh Al Jabri, "The unicity distance: An upper bound on the proability of an eavesdropper successfully estimating the secret key", King Saud University, Arabia Saudí 1996

[8] P. Beauchemin and G. Brassard, "A Generalization of Hellman's Extension to Shannon´s Approach to Cryptography". Journal of Cryptology 1988.

[9] M. Davio, J., M. Goethals, "Elements of cryptology", Philips Research Laboratory, Brussels

[10] Deavours, C. A., "Unicity Points in Cryptanalysis," Cryptologia Vol. 1 (1) pp. 46-68 (Jan. 1977).

[Johan_Van_1-11] Johan Van Tilburg, Dick E. Boekee, "The Pe-security distance as a measure of cryptographic performance", Trattement du Signal volume 4 nº6 1987

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]