Breaking AES encryption using descrypted data

Question

Después de una discusión sobre el cifrado, un amigo mío me desafió a descifrar un archivo que cifró utilizando AES con una clave de 128 bits.

Sé que el archivo era originalmente una imagen GIF, por lo que debería comenzar con 'GIF8'. Me pregunto si es posible derivar la contraseña de este conocimiento en un tiempo razonable (es decir, una semana o menos).

No es posible robar la clave de otra manera que no sea analizar el archivo encriptado, ya que se derrota el punto del desafío.

Si es así, los indicadores serían bienvenidos. No pude encontrar una descripción decente del flujo de cifrado del primer bloque. Recuerdo que tuve uno de un curso en Uni, pero por supuesto, no está en ninguna parte.

Answer 1

wvdschel, aunque ciertamente le deseo buena suerte, considere que si resuelve este problema, probablemente tenga derecho a un doctorado en informática o matemáticas. AES fue diseñado para ser extremadamente difícil de romper (es decir, en el orden exponencial de la cantidad de bits) incluso si conoce algunos detalles menores sobre el archivo cifrado.

Cualquier ataque que pueda reducir la complejidad de aproximadamente 2 a la potencia de la longitud de bit de la clave será un gran avance. En el pasado, tales ataques contra DES (que simplemente disminuyeron su fuerza unas pocas veces) ganaron la aclamación de sus autores.

Lectura en el criptoanálisis lineal de AES.

Answer 2

Piensa en esto: si pudieras obtener la contraseña simplemente conociendo las primeras letras, ¿cuántos mensajes encriptados serían inútiles? Cuántas cartas/correos electrónicos comienzan con "Hola", cuántos de ellos tienen una firma estándar (y conocida) (especialmente en empresas). Todos serían defectuosos. Y en los protocolos también conoces mucha información clara. El cifrado no valdría nada.

Answer 3

Puede tener una oportunidad si no ha usado Cipher-block chaining; vea la imagen en el artículo de Wikipedia señalado por el enlace. Aparte de eso, los comentarios que has recibido son acertados.

Answer 4

La única manera de intentar romper el cifrado AES es utilizar criptoanálisis lineal o diferencial. ¡Ahora, esto es extremadamente difícil de hacer!

Incluso para DES, que se considera más débil, se tardó 50 días para romper el cifrado mediante criptoanálisis lineal. Un tipo llamado Matsui en 1994 utilizó 2^43 pares de texto plano y texto cifrado. Y esto es solo con 56 bits (que es el número de bits que DES usa, o al menos usa en ese momento).

Eso es mucho más que la semana o menos que proponga, y sinceramente creo que le tomaría demasiados años resolver esto, incluso sabiendo que tiene GIF8.

Answer 5

Esto es altamente improbable que se consiga, no sólo de AES, pero de cualquier algoritmo de cifrado moderno decente debido a (entre otras cosas):

Cipher-Block Chaining (mediante el cual los resultados de la encriptación del anterior bloque" "se utilizan en la codificación de la siguiente 'bloque')

y también:

The Avalanche Effect (el efecto de avalancha es evidente si, cuando una entrada se cambia ligeramente, la salida cambia significativamente)

Answer 6

Si vas por la fuerza bruta entonces espero que tenga un superordenador y una máquina del tiempo

Suponiendo que se podría construir una máquina que podría recuperar una clave DES en un segundo (es decir, intente con 2^55 teclas por segundos), luego tomaría esa máquina aproximadamente 149 mil millones (149 billones) de años para descifrar una clave AES de 128 bits. Para poner en perspectiva, el universo es que se cree que es menos de 20 mil millones años.

¡Guau! Aproximadamente un 149 billones años a 1 segunda proporción.

Además, tenga en cuenta que cualquier método de recuperación de la clave más rápido que un ataque de fuerza bruta se considera un "corte" y el AES no se ha roto.

Su mejor opción es hacer un poco de caucho-manguera de criptoanálisis

http://en.wikipedia.org/wiki/Rubber-hose_cryptanalysis

Answer 7

Según Wikipedia:

En criptografía, el Advanced Encryption Standard (AES) es un estándar cifrado adoptado por el gobierno de los EE. UU. El estándar comprende tres cifras de bloque, AES-128, AES-192 y AES-256, adoptado de una colección más grande originalmente publicada como Rijndael. Cada cifrado AES tiene un tamaño de bloque de 128 bits, con tamaños de clave de 128, 192 y 256 bits, respectivamente. Los cifrados AES tienen se han analizado extensamente y ahora son utilizados en todo el mundo, como fue el caso con su predecesor , el estándar de cifrado de datos (DES).

En otras palabras, las claves de 128 bits con este algoritmo fueron desarrolladas por el gobierno de los EE. UU. Y se utilizan en todo el mundo.

Nunca podrá romper la clave AES de 128 bits.

Si la clave proviene de una contraseña, entonces tiene la posibilidad de un ataque de diccionario o ataque de fuerza bruta contra la contraseña.

Answer 8

Mientras que cualquier intento de romper AES será sin duda inútil, aquí hay una buena explicación, amable del algoritmo en sí:

http://www.moserware.com/2009/09/stick-figure-guide-to-advanced.html

Answer 9

Sí, a menos que el implimentation es muy mala (se pueden encontrar otros encriptado datos usando la misma clave y IV que conoces el texto plano de) eres básicamente una manguera. Su mejor opción es tratar de solucionarlo por la espalda, ya sea obtener la clave del usuario de alguna manera O INTENTAR usar las teclas de fuerza bruta y las IV (buena suerte) utilizando un texto claro conocido: texto cifrado conocido.

Answer 10

Buen tema.

Interesante qué tan rápido evolucionan la tecnología y la ciencia. Recientemente leí este artículo relacionado con la NSA: http://www.hpcwire.com/hpcwire/2012-03-19/nsa_employs_cutting-edge_supercomputing_for_domestic_surveillance.html (desde 2012, 19 de marzo, menos de 3 años después de la pregunta original en esta publicación).

Gran parte de los datos se cifran embargo, y ahí es donde la supercomputación entra. Para extraer la información, la NSA tenía que emplean algoritmos de fuerza bruta, y que requiere una gran cantidad de computación poder. Bamford informa que la Instalación de Investigación de Multiprogramas era construida en el Laboratorio Nacional de Oak Ridge para albergar una supercomputadora para el trabajo . Esa instalación, conocida como Building 5300, abarcó 214,000 pies cuadrados y costó $ 41 millones para construir en 2006. Mientras que el supercomputador no clasificado "Jaguar" se estaba desplegando en el otro lado del campus de Oak Ridge, la NSA estaba instalando un aún más sistema de gran alcance en el edificio 5300. Escribe Banford-:

máquina de la NSA fue probablemente similar a la no clasificada Jaguar, pero que era mucho más rápido fuera de la puerta, modificado específicamente para criptoanálisis y dirigido contra una o más específica algoritmos, como el AES. En otras palabras, estaban pasando de la fase de desarrollo de investigación y a atacar realmente los sistemas de cifrado extremadamente difíciles . El esfuerzo de descifrado de códigos estaba funcionando.

Según Binney, una gran cantidad de datos del gobierno extranjero la agencia fue no romper (cifrado de 128 bits) podría ahora descifrable.

La eficacia con la NSA está haciendo esto, creo que va a ser bastante difícil saber a los mortales normales como nosotros (bueno, es NSA! :-))

embargo debemos considerar que no están planeando en rompiendo 1 clave pero número enorme de ellos ... Así que romper un mensaje AES de 128 bits ya no parece ser ciencia ficción o matemática teórica.