En criptografía , la ventaja de un adversario es una medida de cuán exitosamente puede atacar un algoritmo criptográfico , al distinguirlo de una versión idealizada de ese tipo de algoritmo. Nótese 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 , sujeta a límites específicos en los recursos computacionales del adversario (ver seguridad concreta ). "Despreciable" generalmente significa "dentro de O (2 −p )", donde p es un parámetro de seguridad asociado con el algoritmo. Por ejemplo, p podría ser el número de bits en la clave de un cifrado de bloque .
Sea F un oráculo para la función que se estudia y sea G un oráculo para una función idealizada de ese tipo. El adversario A es un algoritmo probabilístico, que recibe F o G como entrada y cuyo resultado es 1 o 0. El trabajo de A es distinguir F de G, basándose en consultas al oráculo que se le da. Decimos:
Sea F una instancia aleatoria del cifrado de bloques 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 de 64 bits posibles. Una "instancia aleatoria de DES" significa que nuestro oráculo F calcula DES utilizando 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 idealizado de 64 bits, es decir, una permutación seleccionada al azar de las (2 64 ) ! posibles permutaciones en bloques de 64 bits. Llamemos a esta permutación seleccionada al azar G. Observe que, según la aproximación de Stirling , (2 64 )! es de alrededor de , 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 un espacio de almacenamiento proporcional a la cantidad de consultas, utilizando un oráculo aleatorio ).
Tenga en cuenta que, dado que los oráculos que nos proporcionan cifran cualquier texto simple que elijamos, estamos modelando un ataque de texto simple elegido o CPA , y la ventaja que estamos calculando se puede llamar la ventaja CPA de un adversario determinado. Si también tuviéramos disponibles oráculos de descifrado, estaríamos realizando un ataque de texto cifrado elegido o CCA y encontrando la ventaja CCA del adversario.
Llamemos a este adversario A 0 . Simplemente lanza una moneda y devuelve 1 o 0 con igual probabilidad y sin hacer ninguna llamada de oráculo. Por lo tanto, Pr[A 0 (F)=1] y Pr[A 0 (G)=1] son ambas 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 tanto para F como para G, por lo que la ventaja es cero. Este adversario no puede distinguir F de G. Si somos diseñadores de cifrados, 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 cual no haya un diferenciador más rápido que la búsqueda de fuerza bruta.
Este adversario (llamémoslo A 1 ) intentará criptoanalizar su entrada por fuerza bruta . Tiene su propia implementación DES. Realiza una única consulta a su oráculo, solicitando que se encripte la cadena de 64 bits compuesta únicamente por ceros. Llama al texto cifrado resultante E 0 . Luego ejecuta una búsqueda exhaustiva de claves. El algoritmo se ve así:
E 0 = consulta_oracle(0) para k en 0,1,...,2 56 -1: si DES k (0) == E 0 : volver 1 devuelve 0
Esta función busca en todo el espacio de claves DES de 56 bits y devuelve "1" si es probable que encuentre una clave coincidente. En la práctica, se requieren varios textos simples para confirmar la clave, ya que dos claves diferentes pueden dar como resultado uno o más pares de texto simple y 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 clave DES. Por lo tanto, la probabilidad de que A 1 devuelva 1 es como máximo 2 −8 . Es decir:
, entonces
Por lo tanto, la ventaja es de al menos 0,996. Este es un factor diferenciador casi seguro, pero no es un fallo de seguridad porque no es más rápido que la búsqueda por fuerza bruta; después de todo, es la búsqueda por fuerza bruta.
![{\displaystyle Adv(A)=|\Pr[A(F)=1]-\Pr[A(G)=1]|}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b60df68c3acb9737534781484db086cfca2324ce)
![{\displaystyle Pr[A_{1}(G)=1]\leq 2^{-8}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5793a75bbd05cb6b4ac1009811dc2e01fad792c6)
![{\displaystyle Adv(A_{1})=|Pr[A_{1}(F)=1]-Pr[A_{1}(G)=1]|\geq 1-2^{-8}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f2fd0cf4c1a40e631f3029b3ccbf7bd4e626b1e9)