Use varias computadoras para una fuerza bruta más rápida [duplicar]

27

He visto al Sr. Robot últimamente y no puedo dejar de pensar por qué fue tan difícil descifrar los archivos cifrados utilizando el cifrado AES con una clave de 256 bits.
Digamos que el único método para encontrar la clave es a través de la fuerza bruta.
¿No podemos configurar una computadora a fuerza bruta a partir de la primera clave posible, y otra para comenzar desde la última clave posible, y quizás algunas computadoras para probar las claves en el medio? ¿Eso no reduciría el tiempo dramáticamente?

    
pregunta Mero55 05.03.2016 - 17:16
fuente

3 respuestas

70

Claro que es posible, pero realmente no ayuda. El número de posibilidades es demasiado grande.

Considere que una clave de 256 bits tiene 2 256 valores posibles. Eso es 12✕10 76 , o 12 seguidos por 76 ceros. Si asumimos generosamente que una computadora puede probar un trillón (eso es 10 12 ) claves posibles por segundo, y que tenemos un billón de computadoras (¿de dónde las obtendremos?) Realizando la búsqueda de la clave, tomará 12✕10 76 / (10 12 ✕10 12 ) segundos para buscar en todo el espacio de teclas. Eso es 12✕10 52 segundos. Como solo hay 3,155,760,000 segundos en un siglo, tomará aproximadamente 4✕10 43 siglos para probar todas las claves posibles. Hay una probabilidad de 50-50 de encontrar la clave en solo la mitad de ese tiempo.

Así se diseña el cifrado. La cantidad de posibilidades es demasiado grande para ser descifrada en el tiempo que es interesante para los humanos.

    
respondido por el Neil Smithline 05.03.2016 - 17:41
fuente
40

Hice un cálculo en este una vez. Supongamos que AES solo se puede romper con la fuerza bruta. Claramente, vamos a necesitar un contador, que cuente de 0 a 2 256-1 , y en promedio deberá contar hasta 2 255 . Ejecutar este contador requiere energía. ¿Cuánta energía toma?

Resulta que aquí hay un límite termodinámico, el principio de Landauer. A una temperatura dada, hay una cantidad mínima de energía que puede tomar establecer un bit (1 bit de entropía), porque si no gastamos esa cantidad de energía, podemos disminuir la entropía del sistema, que es termodinámicamente. imposible. La energía que toma es kT ln 2, donde k es la constante de Boltzman (1.38 × 10 −23 J / K) y T es la temperatura en grados kelvin. Obviamente, queremos hacer esto lo más asequible posible, así que hagamos los cálculos a 3 kelvin, que es aproximadamente la temperatura de la radiación de fondo del universo. ¡No podemos ser más fríos que eso sin gastar más energía para enfriar el sistema de lo que habríamos gastado en voltear las brocas! Esto fija el costo de energía de voltear un poco a 2,87 × 10 −23 J / bit.

Ahora, ¿cuántos bits de flips necesitamos? La respuesta será mucho, así que para mantener las cantidades de energía en términos comprensibles para los humanos, me gustaría simplificar el problema. En lugar de resolver AES-256, simulemos que resolvimos AES-192, que solo requiere contar hasta 2 191 . ¿Cuántos flips de bits necesitamos? Si contamos en binario normal, es posible que tengamos que voltear varios bits por incremento del contador. Es molesto de calcular, así que imaginemos que podríamos hacer este contador con Códigos grises , que solo voltean un bit por incremento.

Incrementando un contador 2 191 veces, a 2,87 × 10 −23 J / bit produce 9 × 10 34 J. Eso es mucho de energía. De hecho, si voy a una de mis páginas favoritas de Wikipedia, Orden de magnitud (energía) , ver que la energía emitida por nuestro sol cada año es de 1.2 × 10 34 J. Eso es correcto. El simple hecho de ejecutar el contador que estaría en el centro del proceso de ruptura de AES tomaría la suma total de casi una década de la producción energética del sol. Todo eso.

Ahora, si revisamos el problema original de AES-256, los costos de energía aumentan en 2 64 . Por lo tanto, ese contador tomaría 1.6 × 10 54 J. De nuevo, observando el Orden de Magnitud (energía), encontramos que la energía total de masa visible en la galaxia de la vía láctea es 4 × 10 58 J. Por lo tanto, si tuviera que convertir el 0,004% de la energía de masa total de la galaxia (es decir, convertir toda la masa en energía usando E = mc 2 ), podría ejecutar una contador que podría contar de 0 a 2 255 .

Esta es la razón por la que uno nunca fuerza bruta un algoritmo criptográfico moderno. Las cantidades de energía requeridas son literalmente a nivel de "muerte térmica del universo".

    
respondido por el Cort Ammon 05.03.2016 - 19:59
fuente
3

No solo es posible, la gente lo ha hecho con éxito. Pero solo con teclas muy cortas.

distribuido.net logró romper un cifrado RC5 de 64 bits en 2002 mediante el uso de una red distribuida de computadoras. Las computadoras eran en su mayoría PC de nivel de consumidor que eran propiedad de voluntarios que instalaron un programa para procesar claves en segundo plano. Esto fue parte del el desafío clave secreto de RSA : un concurso de RSA Labs para descifrar mensajes cifrados con claves mucho más cortas de lo que utilizarías en el mundo real.

  

"Después de más de cuatro años de esfuerzo, cientos de miles de participantes y millones de horas de trabajo de cpu, Distributed.net ha forzado la clave del desafío de cifrado de 64 bits de RSA Security"

Comenzaron otro proyecto para ganar el desafío RSA de 72 bits en 2003. 13 años después, todavía están calculando y ni siquiera han probado el 4% del espacio de teclas .

Tenga en cuenta que estas son versiones extremadamente simplificadas de RSA. La longitud de clave recomendada para RSA-RC5 en el mundo real es al menos de 128 bits. Cada bit adicional duplica el tiempo de cálculo, por lo que estos enfoques distribuidos están todavía a años luz de atacar cualquier cifrado del mundo real.

    
respondido por el Philipp 07.03.2016 - 11:42
fuente

Lea otras preguntas en las etiquetas