¿Cuánto tiempo tomaría romper un correo electrónico cifrado con OpenPGP de 1024 bits?

9

Para WPA, hay calculadoras para determinar el tiempo necesario para descifrar una frase de contraseña, pero no he encontrado nada para OpenPGP.

¿Cuánto tiempo tomaría romper un correo electrónico cifrado con OpenPGP de 1024 bits (dependiendo de la potencia de la CPU)?

También estoy interesado en otros tamaños de teclas como 2048 y 4096.

Kelmat
fuente

Respuestas:

7

Si bien la respuesta de @Jens Erat fue bastante completa, investigué sobre la ruptura de RSA (el algoritmo detrás de OpenPGP), por lo que quería opinar:

Romperé con la norma y le daré el TL; DR primero: es imposible que rompas esa clave. Si estamos analizando esto de manera realista, no hay forma de factorizar un número entero de 1024 bits. Su mejor apuesta posible sería tratar de romper alguna otra parte de la cadena de seguridad (por ejemplo, el escritorio donde el receptor revisa su correo electrónico).

Con el realismo fuera del camino, consideremos las posibles estrategias:

  • Adivinanzas ciegas / Forzamiento bruto. Con un semiprime de 1024 bits, hay pocas posibilidades de que esto funcione. Sería mejor utilizar su tiempo al azar tratando de adivinar los números de lotería.

  • Generando una Mesa Arcoiris. Elimine las conjeturas al factorizar tomando cada primo por debajo de 2 ^ 1024 y multiplicándolo por cada otro primo, almacenando el resultado en una tabla. Entonces todo lo que tendría que hacer es buscar el par correcto. Como puedes imaginar, esto también es imposible. Esto implicaría x! pares para x número de primos. Por la función de recuento de primos , está viendo aproximadamente 2.95 * 10 ^ 307 primos; para comparar, se estima que el número de átomos en el universo observable está en la magnitud de 10 ^ 83, por lo que incluso si pudiéramos hacer que cada átomo almacene dos primos y su producto de manera que nuestra computadora pueda indexarlo sería imposible.

  • Utilice el tamiz de campo de número general . El GNFS es su mejor apuesta para factorizar un semiprime grande. Fue utilizado por Kleinjung y su equipo para factorizar RSA-768, un semiprime de 768 bits. Desafortunadamente, su equipo tardó más de tres años en lograrlo, y es un orden de magnitud menor que los números que desea factorizar. Incluso si gastaras millones de dólares (por día) alquilando las mejores supercomputadoras a plena capacidad, sería casi imposible factorizar el número. El primer paso de GNFS es encontrar suficientes "relaciones" que permitan resolver los subproblemas, y esto puede llevar mucho tiempo.

Su último recurso es usar una computadora cuántica, que le permitiría factorizar los números en una cantidad de tiempo factible. Desafortunadamente, estos aún no se han desarrollado hasta un punto de alguna utilidad. Entonces, por ahora, no podemos factorizar semiprimes de 1024 bits y mayores (y, por lo tanto, los algoritmos que dependen de ellos).

ahjohnston25
fuente
20

Primero, supongo que está hablando del cifrado RSA de 1024 bits.

En general, el tema es demasiado complicado para proporcionar un número simple.

tl; dr : No es factible descifrar un mensaje cifrado OpenPGP en una sola CPU, y probablemente lleve años incluso con grandes grupos de cómputo. Sin embargo, los defectos matemáticos desconocidos (para el público) podrían cambiar esto por orden de magnitud, como podrían hacer las computadoras cuánticas en algún momento en el futuro (lejos, desde el punto de vista de la "era de Internet").

La versión un poco más larga:

Descifrando el cifrado asimétrico (clave RSA de 1024 bits)

Además de las claves RSA de 1024 bits, esto también se aplica a tamaños de clave más grandes. Las claves más grandes proporcionan más seguridad (en forma de potencia informática para descifrarlas), pero recuerde que la seguridad no aumenta linealmente con el tamaño de la clave.

Hay una buena publicación sobre el intercambio de la pila de seguridad de la información, "¿Cómo estimar el tiempo necesario para descifrar el cifrado RSA?" , que no se completa con una estimación como "Utilizando un modelo Core i7 xy, podrá descifrar una clave RSA de 1024 bits en z horas estimadas", pero las respuestas coinciden en que "las claves RSA 1024 bits no pueden ser descifradas por individuos con una potencia de cómputo generalmente disponible (es decir, un puñado de máquinas de alta gama) en un tiempo razonable.

La discusión sobre romper claves de 1024 bits con mucha más potencia de cálculo solo se consideró desde un punto de vista académico:

Recientemente aprendí que la selección de los parámetros para una factorización de números de 1024 bits ha comenzado (esa es la parte "inteligente"); el tamizado es técnicamente factible (será costoso e implicará años de cálculo en muchos grupos universitarios) pero, por el momento, nadie sabe cómo hacer la parte de reducción lineal para un entero de 1024 bits. Por lo tanto, no espere un descanso de 1024 bits en el corto plazo.

Esto probablemente también se aplica a instituciones grandes y bien financiadas con mucha potencia informática como la NSA.

Las cosas podrían cambiar rápidamente si

  • alguien encuentra una falla matemática, que reduce la complejidad de RSA en órdenes de magnitud (algunas instituciones como la NSA emplean a un gran número de grandes matemáticos), o
  • Las computadoras cuánticas finalmente funcionan y se vuelven lo suficientemente potentes y capaces de ejecutar ciertos algoritmos. No se espera que ocurra en los próximos años.

Para DSA / ElGamal, las cosas son un poco diferentes. Una clave DSA del mismo tamaño que una clave RSA proporciona más seguridad, pero al mismo tiempo DSA es más vulnerable a los números aleatorios incorrectos (compárese con la falla del generador de números aleatorios de Debian ). La criptografía de curva elíptica que se avecina para OpenPGP en este momento no tiene ataques conocidos para los algoritmos admitidos y generalmente se considera segura, pero quedan algunas dudas, especialmente en las curvas recomendadas por NIST (NIST ha perdido bastante reputación por hacer un azar roto generador de números un estándar), y algunos trucos de implementación.

Descifrando el cifrado simétrico

Para los rasons de rendimiento, OpenPGP utiliza cifrado híbrido, por lo que el mensaje se cifra con cifrado simétrico y una clave simétrica aleatoria (en OpenPGP, a menudo llamada "clave de sesión"). Esta clave de sesión nuevamente se cifra utilizando el algoritmo de cifrado asimétrico, por ejemplo. RSA.

Si puede descifrar la clave de cifrado simétrica de un mensaje, también puede leer el mensaje (a diferencia de descifrar la clave asimétrica, donde puede leer todos los mensajes cifrados en esta clave).

A diferencia de las primeras versiones de PGP (que usaban un algoritmo de cifrado simétrico diseñado por el propio Zimmermann llamado BassOmatic , que se considera roto), todos los algoritmos simétricos definidos para OpenPGP no tienen ataques conocidos relevantes.

A menos que alguien elija no usar cifrado simétrico (¡lo cual es realmente posible!), Romper un mensaje usando el algoritmo de cifrado simétrico no debería considerarse factible en este momento.

Jens Erat
fuente
Tengo que preguntar ... ¿el error ortográfico de "asimétrico" es intencional?
David Z
No, por supuesto que no; ninguno de los dos estaba "copulando". Gracias por avisarme.
Jens Erat
No existe tal cosa como "una clave DES del mismo tamaño que una clave RSA". DES utiliza claves de 56 bits, punto . Solo se define con claves de 56 bits; no puede ejecutar DES con ningún otro tamaño de clave. Tampoco es vulnerable a los números aleatorios incorrectos, porque DES no usa números aleatorios en ningún punto del algoritmo (ni ningún otro cifrado de bloque primitivo); usos particulares de la misma pueden incluir un aspecto aleatorio (por ejemplo, un IV para el modo CBC debe ser aleatorio), pero el DES en sí es completamente determinista. El DES tampoco se usa (el DES triple se usa ocasionalmente, pero el DES nunca lo hace) ¿Estás seguro de que querías hablar sobre DES?
cpast
Por supuesto que no quería. Confundir DES con DSA no debería haber sucedido. DES, PGP, RSA, NSA, DSA: ¡Necesitamos menos siglas de tres letras!
Jens Erat
La mayoría de las claves openpgp de 1024 bits (a diferencia de las claves ssl / tls) son DSA, no RSA. Encuentro mucha discusión en línea sobre descifrar RSA de 1024 bits pero poco sobre descifrar DSA de 1024 bits.
plugwash