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 (${displaystyle H_{C}(K)}$). Si ${displaystyle 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 ${displaystyle 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]​

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

Supongamos

Entonces:

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

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

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:

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

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 ${displaystyle {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]​

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:

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

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:

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:

Por tanto:

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

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:

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:

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:

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:

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.

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