Hispanopedia Wiki
Articulo de referencia

Ventaja (criptografía)

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 ...

Hispanopedia WikiContenido en espanolLectura gratuita

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 (véase 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 bloques .

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 que recibe F o G como entrada y produce 1 o 0 como salida. La tarea de A es distinguir F de G, basándose en consultas al oráculo que se le proporciona. Decimos: Adv(A)=|Pr[A(F)=1]−Pr[A(GRAMO)=1]|{\displaystyle Adv(A)=|\Pr[A(F)=1]-\Pr[A(G)=1]|}

Ejemplos

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⁵⁶ permutaciones en los 2⁶⁴ posibles bloques de 64 bits. Una "instancia aleatoria de DES" significa que nuestro oráculo F calcula DES usando alguna clave K (que es desconocida para el adversario), donde K se selecciona de entre las 2⁵⁶ claves posibles con igual probabilidad.

Queremos comparar la instancia DES con un cifrado de bloques 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. Nótese, según la aproximación de Stirling, que (2 64 )! es aproximadamente103.47×1020{\displaystyle 10^{3.47\times 10^{20}}}Por lo tanto, incluso especificar qué permutación se selecciona requiere escribir un número demasiado grande para representarlo con exactitud en cualquier computadora real. Dicho de otro modo, G es una instancia de un "cifrado" cuya "longitud de clave" es de aproximadamente 10²¹ bits , lo cual, de nuevo, es demasiado grande para caber en una computadora. (Sin embargo, podemos implementar G con un espacio de almacenamiento proporcional al número de consultas, utilizando un oráculo aleatorio ).

Cabe destacar que, dado que los oráculos que se nos proporcionan cifran cualquier texto plano que elijamos, estamos modelando un ataque de texto plano elegido ( CPA , por sus siglas en inglés), y la ventaja que calculamos puede denominarse ventaja CPA de un adversario determinado. Si también dispusiéramos de oráculos de descifrado, estaríamos realizando un ataque de texto cifrado elegido ( CCA , por sus siglas en inglés) y calculando la ventaja CCA del adversario.

Ejemplo 1: Adivinar al azar

Llamemos a este adversario A 0 . Simplemente lanza una moneda y devuelve 1 o 0 con igual probabilidad y sin realizar ninguna consulta al 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 ocurre 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 entre F y G. Si somos diseñadores de cifrado, nuestro objetivo (quizás inalcanzable) es lograr que sea computacionalmente inviable para cualquier adversario obtener un resultado significativamente mejor que este. Habremos tenido éxito si podemos crear un cifrado para el cual no exista ningún elemento que permita distinguirlos, más rápido que la búsqueda por fuerza bruta.

Este adversario (llamémoslo A1 ) intentará criptoanalizar su entrada por fuerza bruta . Tiene su propia implementación de DES. Realiza una única consulta a su oráculo, solicitando la cadena de 64 bits compuesta únicamente por ceros que se va a cifrar. El texto cifrado resultante se denomina E0 . A continuación, ejecuta una búsqueda exhaustiva de claves. El algoritmo es el siguiente:

E 0 = oracle_query(0) para k en 0,1,...,2 56 -1: si DES k (0) == E 0 : devolver 1 devolver 0

Esta función 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 planos para confirmar la clave, ya que dos claves diferentes pueden generar uno o más pares de texto plano-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 serán examinados 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:

PAGr[A1(GRAMO)=1]≤2−8{\displaystyle Pr[A_{1}(G)=1]\leq 2^{-8}}, entonces

Adv(A1)=|PAGr[A1(F)=1]−PAGr[A1(GRAMO)=1]|≥1−2−8{\displaystyle Adv(A_{1})=|Pr[A_{1}(F)=1]-Pr[A_{1}(G)=1]|\geq 1-2^{-8}}

Por lo tanto, la ventaja es de al menos aproximadamente 0,996. Este es un factor distintivo casi seguro, pero no es una falla 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.

Véase también

Referencias