En criptografía , la distancia de unicidad es la longitud de un texto cifrado original necesario para romper el cifrado reduciendo el número de posibles claves falsas a cero en un ataque de fuerza bruta . Es decir, después de probar todas las claves posibles , debería haber solo un descifrado que tenga sentido, es decir, la cantidad esperada de texto cifrado necesario para determinar la clave por completo, asumiendo que el mensaje subyacente tiene redundancia. [1]
Claude Shannon definió la distancia de unicidad en su artículo de 1949 " Teoría de la comunicación de los sistemas secretos ".
Considere un ataque a la cadena de texto cifrado "WNAIW" cifrada utilizando un cifrado Vigenère con una clave de cinco letras. Posiblemente, esta cuerda se podría descifrar en cualquier otra cuerda; RIVER y WATER son ambas posibilidades para ciertas teclas. Esta es una regla general del criptoanálisis : sin información adicional es imposible decodificar este mensaje.
Por supuesto, incluso en este caso, solo un cierto número de claves de cinco letras dará como resultado palabras en inglés. Probando todas las claves posibles no solo obtendremos RIVER y WATER, sino también SXOOS y KHDOP. Es probable que el número de claves "en funcionamiento" sea mucho menor que el conjunto de todas las claves posibles. El problema es saber cuál de estas teclas "operativas" es la correcta; el resto son falsos.
Relación con el tamaño de la clave y posibles textos sin formato
En general, dadas las suposiciones particulares sobre el tamaño de la clave y la cantidad de mensajes posibles, existe una longitud promedio de texto cifrado donde solo hay una clave (en promedio) que generará un mensaje legible. En el ejemplo anterior, solo vemos caracteres en mayúsculas en inglés, por lo que si asumimos que el texto sin formato tiene esta forma, entonces hay 26 letras posibles para cada posición en la cadena. Del mismo modo, si asumimos claves de cinco caracteres en mayúsculas, hay K = 26 5 claves posibles, de las cuales la mayoría no "funcionarán".
Se puede generar una gran cantidad de mensajes posibles, N, utilizando incluso este conjunto limitado de caracteres: N = 26 L , donde L es la longitud del mensaje. Sin embargo, solo un conjunto más pequeño de ellos es texto sin formato legible debido a las reglas del lenguaje, tal vez M de ellos, donde M es probable que sea mucho más pequeño que N. Además, M tiene una relación de uno a uno con el número de teclas que funcionan, por lo que dadas K teclas posibles, solo K × (M / N) de ellas "funcionarán". Uno de ellos es la clave correcta, el resto son falsos.
Dado que M / N se vuelve arbitrariamente pequeño a medida que aumenta la longitud L del mensaje, eventualmente hay algo de L que es lo suficientemente grande como para hacer que el número de claves falsas sea igual a cero. En términos generales, esta es la L que hace que KM / N = 1. Esta L es la distancia de unicidad.
Relación con la entropía clave y la redundancia de texto plano
La distancia de unicidad se puede definir de manera equivalente como la cantidad mínima de texto cifrado requerido para permitir que un adversario computacionalmente ilimitado recupere la clave de cifrado única. [1]
Entonces se puede demostrar que la distancia de unicidad esperada es: [1]
donde U es la distancia de unicidad, H ( k ) es la entropía del espacio de clave (por ejemplo, 128 para 2 128 claves equiprobables, algo menos si la clave es una frase de contraseña memorizada). D se define como la redundancia de texto plano en bits por carácter.
Ahora, un alfabeto de 32 caracteres puede transportar 5 bits de información por carácter (como 32 = 2 5 ). En general, el número de bits de información por carácter es log 2 (N) , donde N es el número de caracteres del alfabeto y log 2 es el logaritmo binario . Entonces, para el inglés, cada carácter puede transmitir log 2 (26) = 4.7 bits de información.
Sin embargo, la cantidad promedio de información real transportada por carácter en un texto significativo en inglés es de solo 1,5 bits por carácter. Entonces, la redundancia de texto sin formato es D = 4.7 - 1.5 = 3.2. [1]
Básicamente, cuanto mayor sea la distancia de unicidad, mejor. Para una almohadilla de un solo uso de tamaño ilimitado, dada la entropía ilimitada del espacio clave, tenemos, lo que es consistente con la almohadilla de un solo uso irrompible.
Distancia de unicidad del cifrado de sustitución
Para un cifrado de sustitución simple , ¡el número de claves posibles es 26! = 4.0329 × 10 26 = 2 88.4 , el número de formas en que se puede permutar el alfabeto. Suponiendo que todas las claves son igualmente probables, H ( k ) = log 2 (26!) = 88,4 bits. Para texto en inglés D = 3.2 , entonces U = 88.4 / 3.2 = 28 .
Entonces, dados 28 caracteres de texto cifrado, debería ser teóricamente posible elaborar un texto plano en inglés y, por lo tanto, la clave.
Aplicación práctica
La distancia de unicidad es una medida teórica útil, pero no dice mucho sobre la seguridad de un cifrado en bloque cuando es atacado por un adversario con recursos del mundo real (limitados). Considere un cifrado de bloque con una distancia de unicidad de tres bloques de texto cifrado. Aunque claramente hay suficiente información para que un adversario sin límites computacionales encuentre la clave correcta (búsqueda exhaustiva simple), esto puede ser computacionalmente inviable en la práctica.
La distancia de unicidad se puede aumentar reduciendo la redundancia de texto sin formato. Una forma de hacer esto es implementar técnicas de compresión de datos antes del cifrado, por ejemplo, eliminando las vocales redundantes mientras se conserva la legibilidad. De todos modos, esta es una buena idea, ya que reduce la cantidad de datos a cifrar.
Se puede suponer que los textos cifrados mayores que la distancia de unicidad tienen solo un descifrado significativo. Los textos cifrados más cortos que la distancia de unicidad pueden tener múltiples descifrados plausibles. La distancia de unicidad no es una medida de cuánto texto cifrado se requiere para el criptoanálisis, [ ¿por qué? ] pero cuánto texto cifrado se requiere para que haya una sola solución razonable para el criptoanálisis.
Referencias
- ↑ a b c d Alfred J. Menezes , Paul C. van Oorschot , Scott A. Vanstone . "Capítulo 7 - Cifrados en bloque" (PDF) . Manual de criptografía aplicada . pag. 246.Mantenimiento de CS1: utiliza el parámetro de autores ( enlace )
enlaces externos
- Bruce Schneier : How to Recognize Plaintext (Crypto-Gram Newsletter 15 de diciembre de 1998)
- Distancia de unicidad calculada para cifrados comunes