En criptografía , la ventaja de un adversario es una medida de cuán exitosamente puede atacar un algoritmo criptográfico , distinguiéndolo de una versión idealizada de ese tipo de algoritmo. Tenga en cuenta que en este contexto, el " adversario " es en sí mismo un algoritmo y no una persona . Un algoritmo criptográfico se considera seguro si ningún adversario tiene una ventaja no despreciable, sujeto a límites especificados en los recursos computacionales del adversario (ver seguridad concreta ). "Insignificante" generalmente significa "dentro de O (2 −p )" donde p es un parámetro de seguridadasociado con el algoritmo. Por ejemplo, p podría ser el número de bits en la clave de un cifrado de bloque .
Descripción del concepto
Sea F un oráculo para la función que se está estudiando y sea G un oráculo para una función idealizada de ese tipo. El adversario A es un algoritmo probabilístico, dado F o G como entrada, y que da como resultado 1 o 0. El trabajo de A es distinguir F de G, basado en hacer consultas al oráculo que se le da. Decimos:
Ejemplos de
Sea F una instancia aleatoria del cifrado en bloque DES . Este cifrado tiene bloques de 64 bits y una clave de 56 bits. Por lo tanto, la clave selecciona una de una familia de 2 56 permutaciones en los 2 64 bloques posibles de 64 bits. Una "instancia DES aleatoria" significa que nuestro oráculo F calcula DES usando alguna clave K (que es desconocida para el adversario) donde K se selecciona de las 2 56 claves posibles con la misma probabilidad.
Queremos comparar la instancia DES con un cifrado de bloque de 64 bits idealizado , es decir, una permutación seleccionada al azar de (2 64 ) . posibles permutaciones en bloques de 64 bits. Llame a esta permutación seleccionada al azar G. ¡Tenga en cuenta de la aproximación de Stirling que (2 64 )! esta alrededor, por lo que incluso especificar qué permutación se selecciona requiere escribir un número demasiado grande para representarlo exactamente en cualquier computadora real. Visto de otra manera, G es una instancia de un "cifrado" cuya "longitud de clave" es de aproximadamente 10 21 bits, que nuevamente es demasiado grande para caber en una computadora. (Sin embargo, podemos implementar G con espacio de almacenamiento proporcional al número de consultas, usando un oráculo aleatorio ).
Tenga en cuenta que debido a que los oráculos que se nos dan cifran el texto sin formato de nuestra elección, estamos modelando un ataque de texto sin formato elegido o CPA , y la ventaja que estamos calculando se puede llamar la ventaja de CPA de un adversario determinado. Si también tuviéramos oráculos de descifrado disponibles, estaríamos haciendo un ataque de texto cifrado elegido o CCA y encontraríamos la ventaja CCA del adversario.
Ejemplo 1: Adivina al azar
Llame a este adversario A 0 . Simplemente lanza una moneda y devuelve 1 o 0 con la misma probabilidad y sin hacer ninguna llamada de oráculo. Por tanto, Pr [A 0 (F) = 1] y Pr [A 0 (G) = 1] son ambos 0,5. La diferencia entre estas probabilidades es cero, por lo que Adv (A 0 ) es cero. Lo mismo se aplica si siempre devolvemos 0, o siempre devolvemos 1: la probabilidad es la misma para F y G, por lo que la ventaja es cero. Este adversario no puede distinguir F y G. Si somos diseñadores de cifrado, nuestro deseo (quizás no alcanzable) es hacer que sea computacionalmente inviable para cualquier adversario hacerlo significativamente mejor que esto. Habremos tenido éxito si podemos hacer un cifrado para el que no se distinga más rápido que la búsqueda por fuerza bruta.
Ejemplo 2: búsqueda de fuerza bruta
Este adversario (llámelo A 1 ) intentará criptoanalizar su entrada por fuerza bruta . Tiene su propia implementación de DES. Da una sola consulta a su oráculo, pidiendo que se cifre la cadena de 64 bits de todos los ceros. Llame al texto cifrado resultante E 0 . Luego ejecuta una búsqueda de claves exhaustiva. El algoritmo tiene este aspecto:
E 0 = consulta_oracle (0) para k en 0,1, ..., 2 56 -1: si DES k (0) == E 0 : volver 1 volver 0
Esto busca en todo el espacio de claves DES de 56 bits y devuelve "1" si probablemente encuentra una clave coincidente. En la práctica, se requieren varios textos sin formato para confirmar la clave, ya que dos claves diferentes pueden dar como resultado uno o más pares de texto sin formato-texto cifrado coincidentes. Si no se encuentra ninguna clave, devuelve 0.
Si el oráculo de entrada es DES, esta búsqueda exhaustiva seguramente encontrará la clave, por lo que Pr [A 1 (F) = 1] = 1. Si el oráculo de entrada es una permutación aleatoria, hay 2 64 valores posibles de E 0 , y como máximo 2 56 de ellos se examinarán en la búsqueda de claves DES. Entonces, la probabilidad de que A 1 devuelva 1 es como máximo 2 −8 . Es decir:
, entonces
por lo que la ventaja es de al menos aproximadamente 0,996. Este es un distintivo casi seguro, pero no es una falla de seguridad porque no es más rápido que la búsqueda de fuerza bruta, después de todo, es la búsqueda de fuerza bruta.