¿Cómo puedo decodificar un mensaje que fue cifrado con un teclado de una sola vez?

16

¿Cómo puedo descifrar un mensaje que fue cifrado con un teclado de una sola vez? ¿Necesitaría obtener esa almohadilla y luego revertir el proceso? Estoy confundido aquí.

    
pregunta SwaroopGiwali 02.10.2012 - 07:09
fuente

7 respuestas

27

El One-Time Pad es irrompible, asumiendo que el pad es perfectamente aleatorio, se mantiene en secreto, se usa solo una vez y no se conoce texto en claro. Esto se debe a las propiedades de la operación exclusiva o (xor).

Aquí está su tabla de verdad:

A xor B = X

A | B | X
0 | 0 | 0
0 | 1 | 1
1 | 0 | 1
1 | 1 | 0

Number of 0s in column A = 2
Number of 1s in column A = 2
Number of 0s in column B = 2
Number of 1s in column B = 2
Number of 0s in column X = 2
Number of 1s in column X = 2

Tenga en cuenta que no introduce sesgo de bits: el número de 0 y 1 en las entradas es igual al número de 0 y 1 en la salida, es decir, dos de cada uno. Además, si conoce solo un elemento de una fila, no puede predecir los valores de los otros dos, ya que son igualmente probables.

Por ejemplo, digamos que sabemos que X es 0. Hay una probabilidad igual de que A = 0 y B = 0, o A = 1 y B = 1. Ahora digamos que sabemos que X es 1. Hay una igual probabilidad de que A = 0 y B = 1, o A = 1 y B = 0. Es imposible predecir. Por lo tanto, si solo conoce un elemento, posiblemente no pueda determinar ninguna información sobre A o B.

La siguiente propiedad interesante es que es reversible, es decir,

A xor A = 0
B xor B = 0

A xor 0 = A
B xor 0 = B

A xor B xor B  =  A xor 0  =  A
A xor B xor A  =  B xor 0  =  B

Entonces, si tomamos cualquier valor y lo acompañamos, el resultado se cancela y siempre da como resultado 0. Esto significa que, si xor un valor A con un valor B, luego, más tarde, para obtener el resultado con A o B, obtenemos B o A respectivamente. La operación es reversible.

Esto se presta bien a la criptografía, porque:

  • xor no introduce bitskew
  • xor tiene entradas igualmente probables para cualquier salida dada
  • dados dos de A, B, X podemos calcular el tercero

Como tal, lo siguiente es perfectamente seguro:

ciphertext = message xor key

pero solo si el mensaje tiene la misma longitud que la clave, la clave es perfectamente aleatoria, la clave solo se usa una vez y el atacante conoce un solo elemento. Si conocen el texto cifrado, pero no la clave o el mensaje, es inútil para ellos. No pueden romperlo. Para descifrar el mensaje, debe conocer la clave completa y el texto cifrado.

Tenga en cuenta que la clave debe ser completamente aleatoria, es decir, cada bit debe tener la misma probabilidad de ser 1 o 0, y ser completamente independiente de todos los demás bits de la clave.

Esto resulta en realidad bastante poco práctico, por varias razones:

  • Generar claves perfectamente aleatorias es difícil. Los generadores de software (y muchos generadores de hardware) a menudo tienen sesgos minúsculos y propiedades de repetición impares. Es casi imposible obtener datos verdaderamente aleatorios en cualquier cosa que no sean cantidades mínimas.
  • Si el atacante conoce el texto cifrado y puede adivinar correctamente partes del mensaje (por ejemplo, sabe que es un ejecutable de Windows y, por lo tanto, debe comenzar con MZ ) puede obtener los bits de clave correspondientes para el rango conocido. Estos bits no sirven para descifrar otras partes del mensaje, pero pueden revelar patrones en la clave si están mal generados.
  • Debe poder distribuir la clave, y su clave debe ser igual a su mensaje. Si puede mantener su clave 100% secreta entre aquellos de ustedes que están autorizados para leer el mensaje, ¿por qué no mantener su mensaje 100% en secreto?

El enlace débil aquí es su generador de números aleatorios. La seguridad de la almohadilla de un solo uso está completamente limitada por la seguridad de su generador. Dado que un generador perfecto es casi imposible, un parche perfecto es casi imposible también.

El problema final es que la clave solo se puede usar una vez. Si lo usa para dos mensajes diferentes, y el atacante conoce ambos textos cifrados, puede juntarlos para obtener el xor de los dos puntos de luz. Esto filtra todo tipo de información (por ejemplo, qué bits son iguales) y rompe completamente el cifrado.

Entonces, en conclusión, en un teclado de una sola vez perfecto, necesitas conocer el texto cifrado y la clave para descifrarlo, pero los paneles de una sola vez perfectos son casi imposibles.

    
respondido por el Polynomial 02.10.2012 - 10:01
fuente
1

Las almohadillas de una sola vez son extremadamente difíciles de romper, de hecho, aún se usan en algunas situaciones como si se hicieran correctamente, entonces son esencialmente irrompibles. En un sistema de teclado de una sola vez cada carácter se modifica mediante un flujo de datos aleatorios que comparten ambos lados, sin una copia del teclado no podrá romper el código.

Una de las pocas debilidades del sistema es el origen de datos aleatorios. En la Segunda Guerra Mundial, se rompieron una vez las almohadillas británicas y se las rastrearon hasta un trabajador cuyo trabajo era sacar de un tambor bolas numeradas al azar. La forma en que se suponía que funcionaba era que el trabajador hacía girar el tambor, sacaba una pelota al azar sin mirarla, giraba otra vez, elegía otra vez, etc., etc. El trabajador comenzó a tomar atajos extrayendo más de una bola después de Cada giro y mirando los números, seleccionando favoritos. Introdujo patrones que permitieron a la oposición romper las almohadillas, y como resultado se perdieron vidas.

Lo mismo ocurre hoy con las fuentes numéricas pseudoaleatorias. Los protocolos de cifrado que deberían tardar milenios en romperse realmente solo durarán años o décadas sin una verdadera fuente de datos aleatorios.

    
respondido por el GdD 02.10.2012 - 09:47
fuente
1

Suponiendo que el cifrado se realizó de forma competente, la única forma de descifrar es obtener el pad.

    
respondido por el ddyer 02.10.2012 - 21:22
fuente
1

Si bien es probable que el cifrado de una sola vez sea imposible de romper, tenga en cuenta que también es extremadamente raro.

Parte de la definición de OTP es que la almohadilla debe contener datos verdaderamente aleatorios, y los datos verdaderamente aleatorios pueden ser difíciles de conseguir para las computadoras. En cambio, a menudo, el teclado está compuesto de datos pseudoaleatorios , que generalmente es lo que obtienes cuando le pides a una computadora un número aleatorio.

En este caso, ya no tienes cifrado irrompible. En su lugar, tiene un mensaje XORed con la salida de un algoritmo determinista ya menudo reversible, que puede ser atacado reproduciendo la misma cadena pseudo-aleatoria. Este ataque es particularmente devastador si sabes qué algoritmo se usa y más aún si sabes cómo se genera la semilla. En tal caso, el código puede ser descifrado en cuestión de segundos. Pero incluso sin conocer la semilla de PRNG, a menudo el patrón se puede derivar del mensaje en sí.

Además, el cifrado OTP es particularmente difícil de manejar porque la clave es tan larga como el mensaje cifrado y, de alguna manera, debe transmitirse al destinatario sin ser interceptada. Cualquier software que afirme utilizar el cifrado OTP que no requiere que usted intercambie un bloque de claves tan grande como su mensaje (o mayor) no está utilizando datos verdaderamente aleatorios, y por lo tanto no está utilizando el cifrado OTP.

Además, una de las características clave de OTP es que no se pueden reutilizar las almohadillas viejas. Si reutiliza uno viejo una vez, puede ser suficiente para permitir que se rompa el código.

    
respondido por el tylerl 02.10.2012 - 23:05
fuente
1

La pregunta era, ¿cómo se puede descifrar un mensaje que se creó desde un pad de tiempo, bastante seguro de que aún no se ha respondido?

Originalmente, el pad de una vez se usaba solo con caracteres, y es muy básico. Digamos que tiene un mensaje 'killtheking' (tomado de una respuesta), y desea cifrarlo para que necesite una clave. Para la clave, necesita al menos la misma cantidad de caracteres que el mensaje, por lo que tira un dado que tiene 26 lados (uno para cada letra) 11 veces, porque hay 11 caracteres en el mensaje.

Suponga que el resultado es aqheivlekrw

ahora restamos la posición en el alfabeto de la letra en la clave, de la posición en el alfabeto de la letra en el mensaje, y el número resultante es la posición en el alfabeto del texto cifrado. Envuelva cualquier letra que cree un resultado negativo como se muestra a continuación (como si el resultado fuera 30, luego use 26 - 30 = 4 o 'd'.

por ejemplo:

k - a = (11 - 1) = 10 = j 

'j' es la décima letra del alfabeto, así que usamos eso.

para el resto del mensaje que recibimos:

i - g = (9 - 7) = 2 =   b
l - h = (12 - 8) = 4 =  d
l - e = (12 - 5) = 7 =  g
t - i = (16 - 9) = 7 =  g
h - v = (8 - 22) = -14 (26 - 14 = 12) = l
e - l = (5 - 12) = - 7 (26 - 7 = 19) = s
k - e = (11 - 5) = 6 = f
i - k = (9 - 11) = -2 (26 - 2 = 24) = x
n - r = (14 - 18) = -4 (26 - 4 = 22) = v
g - w = (7 - 23) = -16 (26 - 16 = 10) = j

así que al final

your message    = killtheking
you key         = agheivlekrw
your cypher     = jbdgglsfxvj

pase el texto cifrado a quien quiera que lo reciba y ellos hacen lo contrario de lo que han hecho para cifrarlo, tienen que agregar la clave al texto cifrado:

j + a = (10 + 1 = 11) k
b + g = (2 + 7 = 9)   i
d + h = (4 + 8 = 12)  l
g + e = (7 + 5 = 12)  l
...

y así sucesivamente.

Las computadoras usan XOR porque hace lo mismo y es mucho más rápido y más fácil de implementar, pero para entender cómo funciona, descubrí que es bueno ver el ejemplo utilizable "humano". Así que en una computadora puedes cifrar el mensaje haciendo:

Cypher = Mensaje XOR Key

y descifre nuevamente usando:

Mensaje = Cypher XOR Key

Es tan simple como eso.

    
respondido por el Neil H 17.03.2016 - 07:12
fuente
-2

Si no tienes la clave ...

Brute forza el texto cifrado (permutarlo) y analiza la salida en busca del texto claro potencial en el lenguaje esperado.

El análisis estadístico puede ayudar en la detección de posibles lenguajes generados por humanos en la salida (¿quizás chi-cuadrado?)

    
respondido por el adric 02.10.2012 - 22:26
fuente
-6

un pad de tiempo podría ser fácilmente agrietado si conoces el formato de salida. Como encabezados de audio, imágenes de gifs, etc. Mediante ingeniería inversa, la transmisión regresa. Podría ser bueno para algún tipo de caracteres, pero no para otros campos donde el formato de salida podría identificarse fácilmente por otros medios. Hoy en día, nada es 100% seguro.

    
respondido por el user35107 05.12.2013 - 16:49
fuente

Lea otras preguntas en las etiquetas