Muchos diseñadores afirmaron que su esquema de criptografía tiene seguridad de 80 bits. Entonces, ¿cómo calcular el tiempo de ejecución de este esquema de criptografía de seguridad de 80 bits, como RSA de seguridad de 80 bits usando un tipo de CPU?
Comentarios
- RSA de 80 bits se puede romper en un abrir y cerrar de ojos, usando por ejemplo GMP-ECM . Para obtener información sobre los registros de factorización RSA, consulte esto . Para obtener información sobre la seguridad de 80 bits, consulte esto . Para elegir el tamaño de la clave, consulte esto .
- Gracias por su respuesta. Ahora tomo la seguridad de 128 bits como ejemplo. Quiero preguntar que la seguridad de 128 bits significa 2 ^ 128 operaciones básicas para atacar este esquema. ¿Es esto cierto？ Y la operación básica significa multiplicación o suma general? ¿Y cómo calcular el tiempo concreto para atacar este esquema? ¿2 ^ 128 multiplica el tiempo de hacer una multiplicación o suma general?
- Ah, entonces su pregunta es: ¿qué significa seguridad de $ n $ -bit? Estoy ' tratando de encontrar una Q / A sobre esto. En pocas palabras: significa que se necesitan $ 2 ^ n $ pasos para romper el sistema, donde " paso " está vagamente definido. Para la criptografía simétrica, generalmente es " tanto trabajo como un cifrado o hash ". Para el trabajo teórico sobre criptografía asimétrica, " paso " tiende a ser " un grupo ( o campo) operación o un hash ". Para RSA, eso podría ser 1 mod de multiplicación modular N (de la clave pública) o 1 hash. Pero en la práctica, la seguridad de $ n $ -bit a menudo se usa para: tanto trabajo (informático) como para romper un cifrado simétrico con seguridad de $ n $ -bit.
- Había una pregunta sobre Inseguridad de 64 bits . Las supercomputadoras como Summit pueden llegar a $ 2 ^ {72} $ en un año. Sin embargo, un grupo dedicado como los mineros de Bitcoin puede llegar a $ 2 ^ {92} $ en un año, por lo que 80 bits no es más seguro. Si el ataque de múltiples objetivos disponible, incluso AES-128 no es seguro para todos los objetivos, consulte aquí y ¿Qué es un ataque de múltiples objetivos? y aquí ¿AES-128 se ha roto por completo?
- @fgrieu Gracias por tu respuesta. También quiero saber si 2 ^ {128} pueden verse como ciclos de reloj. Como veo, el tiempo de ejecución también se puede medir por ciclos de reloj.
Respuesta
La pregunta se reduce en gran medida para:
¿Qué significa $ n $ -bit seguridad en la práctica para un valor dado de $ n $ ?
TL; DR: tan seguro como un buen cifrado simétrico con una clave de $ n $ -bit.
No existe una definición más precisa, incluso si restringimos a los atacantes que usan computadoras (en lugar de computadoras cuánticas), como lo hace esta respuesta.
Un significado generalmente aceptado es que se cree que el número de «pasos» para romper el sistema es $ 2 ^ n $ ; o más precisamente, que la probabilidad de romper el sistema con $ s $ «pasos» no sea superior a $ s \, 2 ^ {- n} $ por cualquier método para cualquier $ s $ . Sin embargo, «pasos» y «ruptura» no están definidos con precisión.
En la teoría del cifrado simétrico, «paso» se toma normalmente como una ejecución del cifrado con una nueva clave. De esta manera, un cifrado ideal con una clave de $ n $ bits tiene una seguridad de $ n $ -bit, bajo búsqueda de clave de fuerza bruta. Cuando pasamos a la práctica, los atacantes no están obligados a realizar búsquedas de claves por fuerza bruta, y la definición de «paso» debe convertirse en un número de subpasos comparables en número y costo computacional a los subpasos requeridos para uno. ejecución del cifrado con una nueva clave para un texto sin formato del tamaño de la clave . Con esta definición, un cifrado práctico con una clave de $ n $ bits tiene como máximo $ n $ – seguridad de bits y apunta a ese ideal.
Cuando pasamos a los hash, la definición de un paso podría convertirse en un número de subpasos comparables en número y costo computacional a los subpasos requeridos para hacer hash en un mensaje nuevo el tamaño de la salida hash .
Uno de los muchos problemas con lo anterior es que no hay acuerdo sobre si debemos contar o no el costo de la memoria y los accesos a la memoria en el costo computacional. Lo seguro desde la perspectiva del usuario es no contarlo, pero eso puede ser de suma importancia para un atacante.
La definición de «pasos» se vuelve aún más confusa cuando se trata de criptografía asimétrica como RSA.En teoría, los «pasos» podrían ser un cálculo en la estructura algebraica utilizada para el criptosistema; como, para RSA, una evaluación de multiplicación modular $ (a, b) \ mapsto a \, b \ bmod N $ para enteros arbitrarios $ a $ y $ b $ en $ [0, N) $ , donde $ N $ es el módulo público. Pero hay problemas para llevar esto a la práctica, en particular para RSA: el ataque más conocido es factorizar el módulo público $ N $ utilizando GNFS , cuyo costo computacional está dominado por operaciones que tienen poca similitud con la multiplicación modular, y de costo práctico dominado por la memoria y los accesos a la memoria. Lo que vuelve a utilizar la vaga definición del TL; DR.
cómo calcular el tiempo de ataque a este esquema de criptografía de seguridad de 80 bits, como ¿RSA de seguridad de 80 bits usando una especie de CPU?
«RSA de seguridad de 80 bits» no debe entenderse como RSA con un público de 80 bits módulo $ N $ , que es terminalmente inseguro. Si tuviéramos el tamaño de $ N $ , podríamos estimar la dificultad basándonos en eso y en la experiencia anterior (consulte este y sus enlaces). Pero no lo hacemos, y no hay consenso sobre el tamaño de $ N $ para RSA con seguridad de 80 bits: a menudo se citan 1024 bits, pero según la hipótesis , y a quién le preguntas, eso es demasiado o muy poco. Por lo tanto, lo mejor es ignorar que estamos hablando de RSA y volver a: tanto tiempo como sea necesario para romper un buen cifrado simétrico con un código de 80 bits clave.
Lo que nos lleva a: $$ \ text {Time} = \ frac {2 ^ n \ times k \ times p} {\ text {Frecuencia } \ times \ text {Number-of-CPUs}} $$ donde $ n $ es el nivel de seguridad en bits, $ k $ es una estimación del número de ciclos de CPU para evaluar un buen cifrado utilizando un algoritmo ultra optimizado y $ p $ es la probabilidad residual de éxito de un adversario. Dependiendo de la perspectiva, podríamos tomar $ k = 1 $ (lo que ahorra examinar los detalles), $ k = 32 $ (porque eso es aún menor que en los mejores ataques contra buenos cifrados usando una computadora de propósito general), o mucho más. Dependiendo de la perspectiva, podemos tomar $ p = 1 $ (lo más prudente desde la perspectiva de un usuario legítimo), $ p = 1/2 $ (obteniendo el tiempo esperado en el caso de un cifrado de bloque), o un $ p $ más pequeño si queremos un margen de seguridad¹.
Por ejemplo, con $ n = 80 $ , $ k = 1 $ , $ p = 1/1000 \ approx2 ^ {- 10} $ , $ \ text {Frecuencia} = 4 \ text {GHz} \ approx2 ^ {32} \ text {s} ^ {- 1} $ , $ \ text {Number-of-CPUs} = 1000 \ approx2 ^ {10} $ , obtenemos $ \ text {Time} \ approx2 ^ {80-10-32-10} \ text {s} = 2 ^ {28} \ text {s} $ , eso es aproximadamente 8 años. En otras palabras, nuestras 1000 CPU tienen solo una probabilidad muy pequeña de éxito contra criptografía simétrica de 80 bits, hasta que se vuelven técnicamente obsoletas.
Por otro lado, 1000 CPU es una pequeña fracción de CPU en todo el mundo y la minería de bitcoins muestran de manera concluyente que la criptografía de 80 bits ya no es suficiente contra adversarios con la capacidad de diseñar ASIC, construirlos en cantidades masivas y mantener los costos de energía para su operación; ver esto .
¹ El término $ p $ en la fórmula es la más prudente desde la perspectiva de un usuario legítimo, pero hace que $ \ text {Time} $ se subestime en muchos escenarios de ataque. Por ejemplo, en búsqueda de colisión, el término correcto sería más como $ \ sqrt p $ .