Cuando el DES de fuerza bruta, ¿saber algo sobre el texto simple ayuda?

10

Estándar de cifrado de datos (Wikipedia)

Sé que con la fuerza bruta hay 2 ^ 56 claves posibles para verificar (56 bits, cada una de ellas 1 o 0). Pero digamos que sé que el mensaje en sí solo está formado por letras (a-z, A-Z).

¿Saber las cosas (como la limitación de solo letras) sobre el texto simple facilitaría la ruptura del cifrado?

    
pregunta AStanton 10.12.2010 - 22:23
fuente

5 respuestas

6

En una búsqueda de fuerza bruta estándar, se supone que ya conoce al menos un texto sin formato y su cifrado asociado con una clave determinada. Por lo tanto, tener el texto en claro de un conjunto restringido no ayudará a menos que haya alguna otra debilidad que esté aprovechando.

    
respondido por el James K Polk 10.12.2010 - 22:53
fuente
3

Para que un ataque de fuerza bruta tenga éxito (incluso de manera teórica), el atacante debe saber "algo" sobre el texto sin formato, para saber si encontró la clave correcta o no. Dice lo contrario: si todo lo que sabe el atacante sobre el texto sin formato es que es un conjunto de bytes aleatorios, entonces, para cada clave probada, eso es exactamente lo que obtendrá: un conjunto de bytes de aspecto aleatorio.

Por otra parte, si el atacante consideró que valía la pena atacar el sistema (debido a que una búsqueda exhaustiva 2 56 es, aunque es factible, bastante costosa), debe tener un conocimiento a priori de lo que encontrará. Esto puede ser como un formato estándar (por ejemplo, los datos son XML, comienzan con un encabezado XML; o los datos se comprimen con gzip y, por lo tanto, comienzan con un encabezado gzip ) o incluso alguna información básica como "el texto en claro es un texto que 'tiene sentido' ".

El texto en inglés con codificación ASCII utilizará solo algunos valores de byte, es decir, valores de byte de 32 a 126 (inclusive), y posiblemente también 9 (tabulación horizontal), 10 y 13 (LF y CR, respectivamente, para fines de líneas), 12 (tabulación vertical) y posiblemente 26 (fin de archivo en sistemas DOS / Windows). Así que eso es 100 de los 255 valores de byte posibles. Un descifrado de un solo bloque DES (8 bytes) con una clave incorrecta tiene una probabilidad de que (100/255) 8 consiste únicamente en este conjunto de "caracteres plausibles". Como el atacante tiene 2 claves 56 para intentar, debe descifrar los bloques n para que la probabilidad de aceptar una clave incorrecta no sea mayor que 2 -56 . Esto se logra tan pronto como n = 6 (porque (100/255) 8 * 6 & leq; 2 -56 ). Esto conduce a un ataque de búsqueda exhaustiva en el que el atacante descifra los bloques 6 por clave potencial, filtrando las claves incorrectas al mirar los caracteres obtenidos.

Ahora, seamos sinceros, "8g.; = 7Zf" no es exactamente "texto que tenga sentido". Así que el atacante realmente sabe mucho más que "el texto plano consiste solo en caracteres ASCII imprimibles". Podría filtrar el descifrado incorrecto que solo da caracteres imprimibles pero no extractos de texto plausibles. También podría obtener, digamos, mil "claves posibles" (cada una produciendo algo que, desde el punto de vista de una computadora, es un texto con sentido) y terminar el trabajo a mano (el cerebro humano es muy bueno en la detección de texto real entre una lista de personajes de aspecto galimatías). Así que un atacante podría usar, por ejemplo, dos o tres bloques y aun así hacer las cosas.

Es muy difícil cuantificar cuán eficiente será el atacante para filtrar el descifrado incorrecto, porque depende de lo que el atacante "adivine", algo que está en el ámbito de la psicología, no de la computadora. ciencia. Por lo tanto, los académicos utilizan la "convención segura" de considerar que el atacante tiene un bloque de texto simple conocido: conoce con un 100% de certeza un texto simple de 8 bytes para el que también tiene el texto cifrado correspondiente. Es posible que esto no sea cierto en una situación de ataque real, pero realmente no se puede preverlo.

    
respondido por el Thomas Pornin 13.09.2011 - 17:26
fuente
2

Dependería de cómo esté comprobando cada clave. Si comienzas en 0 y sigues aumentando, entonces deberías convertir al conjunto de caracteres y verificar si ese carácter es válido. O deberías trabajar de otra manera, comenzar con un personaje y solo incrementar por un personaje dentro del conjunto.

Creo que si incrementas por carácter en lugar de bit, tendrías un conjunto de trabajo mucho más pequeño y, por lo tanto, tomaría menos tiempo ejecutar todas las combinaciones.

    
respondido por el Steve 10.12.2010 - 22:39
fuente
0

Saber que las posibles soluciones pertenecen a un conjunto restringido lo ayudará porque puede terminar antes el proceso de descifrado.
En su caso, puede descifrar solo una cantidad limitada de texto cifrado / cifrado (los primeros 8/16 / ... bytes, por ejemplo) y guardar para una ronda posterior solo los textos descifrados / simples que solo están hechos de letras (az, az). A continuación, puede aumentar la cantidad que descifra si el espacio de soluciones guardado es demasiado grande o simplemente repasar todas ellas y decidir cuál es la correcta.

    
respondido por el Eugen Constantin Dinca 12.12.2010 - 19:57
fuente
0

La respuesta corta es "teóricamente sí" .

Pero: esa no es la razón principal por la que DES se tropieza con sus propios pies.

Déjame darte un poco más de información ...

Hoy en día, el DES se considera inseguro para la mayoría de las aplicaciones. Esto se debe principalmente a que el tamaño de la clave de 56 bits es demasiado pequeño. Lo que esto significa se vuelve obvio cuando se sabe que en enero de 1999, la "Electronic Frontier Foundation" y "Distribution.net" colaboraron para romper con éxito una clave DES en 22 horas y 15 minutos ... públicamente.

El tamaño pequeño de la clave fue una de las razones por las cuales DES fue retirado como estándar por el Instituto Nacional de Estándares y Tecnología.

Pero: se cree que el algoritmo es prácticamente seguro en forma de Triple DES, aunque existen ataques teóricos. En años más recientes, el cifrado ha sido reemplazado por el Estándar de cifrado avanzado (AES).

Mis 2 centavos: "Si puedes evitar el DES, ¡evita el DES!"

    
respondido por el user6373 27.12.2011 - 12:34
fuente

Lea otras preguntas en las etiquetas