¿Por qué no es bueno cifrar con el mismo pad único?

20

Para cifrar un mensaje con una tecla de teclado de una sola vez , debe hacer . k E n c ( m 1 , k ) = m 1km1kEnc(m1,k)=m1k

Si usa la misma para cifrar un mensaje diferente , obtiene , y si realiza Xor de los dos textos cifrados, obtiene m 2 E n c ( m 2 , k ) = m 2k ( m 1k ) ( m 2k ) = m 1m 2km2Enc(m2,k)=m2k

(m1k)(m2k)=m1m2

entonces, OK, hay alguna fuga de información porque aprendes , pero ¿por qué no es seguro? No tengo forma de aprender (digamos) menos que sepa . Entonces, ¿por qué está mal usar dos veces?m 1 m 2 km1m2m1m2k

Sonó.
fuente
Sí, esto está sembrando. Principalmente, sembrando el debate sobre la frontera entre crypto.se y cs.se.
Ran G.
Consulte aquí para una discusión de las etiquetas utilizadas.
Raphael
Recuerdo que vi una visualización que lo deja muy claro, pero no puedo encontrarlo ahora. ¿Alguien sabe de lo que estoy hablando? (Espero no confundirlo con otra imagen criptográfica como ECB linux-pinguin, etc.)
Ran G.
1
@Sonó. : correcto: la pregunta correspondiente de crypto.se está en ¿ Aprovechando la reutilización de una sola vez de la tecla del teclado?
David Cary

Respuestas:

14

No tengo forma de aprender (digamos) menos que sepa .m 2m1m2

Ese es exactamente el problema: si reutiliza la misma clave y alguien tiene acceso a un mensaje que cifró en texto plano y encriptado, puede usarlo para encontrar su clave:

(m2k)m2=k

Como escenario alternativo, si usa la misma clave una y otra vez, los atacantes pueden adivinar solo partes de varios mensajes cifrados, y cada suposición exitosa revela una parte de la clave , de modo que con el tiempo más y más La clave se revela.k

Esta estrategia general para romper un sistema de cifrado se conoce como un ataque de texto sin formato conocido . Se cree que muchos sistemas, como AES y RSA, son seguros contra estos ataques. Pero una almohadilla de una sola vez se vuelve completamente insegura contra ellos a menos que se use una nueva almohadilla para cada cifrado, por lo que se denominan "almohadillas de una sola vez".

Carl Mummert
fuente
11

Es inseguro precisamente por la razón que mencionas: hay alguna fuga de información.

Básicamente, si tiene alguna suposición sobre los textos simples (texto en inglés, archivos con estructura conocida, etc.), esto lleva a un análisis estadístico fácil. Probablemente usarlo dos veces no cambia significativamente la practicidad del ataque, pero usarlo muchas veces con un texto plano no aleatorio, eventualmente revela suficiente información para recuperar la clave.

Finalmente, si tiene la capacidad de usarlo solo dos veces , también tiene la capacidad de usarlo solo una vez ; la restricción es que estas almohadillas de una sola vez no se deben usar potencialmente desconocidas y con el tiempo, dañando varias veces.

m1m2

Los ataques de texto sin formato conocidos son bastante comunes, es razonablemente fácil forzar un mecanismo de encriptación para encriptar algo que usted conoce a priori. Si no, generalmente puede hacer suposiciones estadísticas razonables.

qdot
fuente
Además, los pads de una sola vez tienen la propiedad de que si conoce el texto cifrado e incluso parte del texto sin formato, puede recuperar inmediatamente la parte correspondiente de la clave, lo que significa que parte de todos los mensajes futuros cifrados con el mismo pad se envían efectivamente en el claro (lo que hace que sea más fácil adivinar algo más de texto sin formato, revelar más de la clave, etc.). Si está encriptando muchas cosas, como el correo electrónico o las solicitudes HTTP, el atacante casi siempre puede conocer parte del texto sin formato simplemente debido a la estructura de estos protocolos.
Ben
6

(m1k)(m2k)=m1m2

log226=4.7

Si desea utilizar dos veces una almohadilla única, primero debe comprimir su mensaje. E incluso entonces, si no usa un algoritmo de compresión casi perfecto, y usa el pad de una sola vez varias veces, habrá suficiente entropía para recuperar teóricamente los mensajes. No sé lo difícil que sería en la práctica.

Peter Shor
fuente
4

m1m2m1m2

En realidad, para muchos casos, es muy simple. Aquí hay una visualización simple.

Sonó.
fuente
2

Aquí hay una forma intuitiva de representar el enfoque sin recurrir a las matemáticas. Digamos que tiene dos mensajes encriptados que han sido encriptados por el mismo pad de una sola vez.

  1. Adivine una palabra o frase que puede estar contenida en uno de los mensajes. Digamos la frase "Informe meteorológico"
  2. Comenzando con el mensaje 1, suponga que "Informe meteorológico" aparece en la posición de la primera letra.
  3. Calcule los primeros 14 caracteres del pad de una sola vez.
  4. Descifre los primeros 14 caracteres del mensaje 2 utilizando la OTP calculada de forma inversa.
  5. Si el texto sin formato se parece a gobble-di-gook, vuelva al paso 2 y repita en la posición de la segunda letra. Sin embargo, si obtiene un texto significativo (por ejemplo, "Buenos días I", felicidades, ha resuelto los primeros 14 caracteres de la OTP (y los primeros 14 caracteres de cada letra)
  6. Si llega al final del mensaje 1 sin arrojar nada que no sean letras aleatorias, puede concluir que la frase "Informe meteorológico" no aparece en el mensaje 1. Vuelva al paso 1 con una frase diferente como "Estimado coronel "
Johnno
fuente