Distancia de unicidad

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₁.
• ${\displaystyle P_{C}(K)}$ representan la probabilidad condicional de la clave K dado el criptograma recibido C. A veces también se denota por ${\displaystyle P(K|C)}$
• ${\displaystyle P_{C}(M)}$ representan la probabilidad condicional del mensaje M dado el criptograma recibido C. A veces también se denota por ${\displaystyle 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), ${\displaystyle H_{C}(K)}$, también denotada por ${\displaystyle H(K|C)}$, mediante la fórmula:

${\displaystyle 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 ${\displaystyle 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), ${\displaystyle H_{C}(M)}$, también denotada por ${\displaystyle H(M|C)}$, mediante la fórmula:

${\displaystyle 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), ${\displaystyle H_{C,M}(K)}$, también denotada por ${\displaystyle H(K|M,C)}$, mediante la fórmula:

${\displaystyle 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 ${\displaystyle H_{C,K}(M)}$ o por ${\displaystyle H(M|K,C)}$. Dada una clave la relación entre texto cifrado y texto en claro es uno-a-uno y por tanto ${\displaystyle H_{C,K}(M)=0}$

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

${\displaystyle 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 ${\displaystyle 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 ${\displaystyle H_{C}(M)}$ sea pequeño. Sin embargo, tener un valor pequeño de ${\displaystyle 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

Podemos calcular ${\displaystyle H_{C}(K)}$ y ${\displaystyle 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 ${\displaystyle H_{C}(K,N)}$ y ${\displaystyle H_{C}(M,N)}$. Otra notación alternativa equivalente es ${\displaystyle H(K/C^{N})}$ y ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle 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)${\displaystyle H_{C}(K,S)\leq H_{C}(K,N)}$ si ${\displaystyle S\geq N}$ (La equivocación de la clave es una función no creciente de N)

ii))${\displaystyle H_{C}(M,S)\leq H_{C}(M,N)}$ si ${\displaystyle 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)${\displaystyle 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:

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

donde ${\displaystyle 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 (${\displaystyle 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

${\displaystyle 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 ${\displaystyle H(K/C^{N})\geq 0}$, ${\displaystyle 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.

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

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

${\displaystyle T=2^{NR_{0}}}$

con ${\displaystyle R_{0}}$ la ratio absoluta con valor ${\displaystyle 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 ${\displaystyle S=2^{NR}}$ mensajes, con ${\displaystyle 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.

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

${\displaystyle 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:

${\displaystyle D=\log A-H(M)}$

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

${\displaystyle 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

${\displaystyle 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.

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:

${\displaystyle 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:

${\displaystyle H(K)=\log 26!=88.38}$ bits

Por tanto la distancia de unicidad vale aproximadamente 32 (${\displaystyle 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 (${\displaystyle 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 es debido 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.

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:

${\displaystyle 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.

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