Indistinguibilidad del texto cifrado

Propiedad de algunos criptosistemas

La indistinguibilidad de textos cifrados es una propiedad de muchos esquemas de cifrado . Intuitivamente, si un criptosistema posee la propiedad de indistinguibilidad , entonces un adversario no podrá distinguir pares de textos cifrados en función del mensaje que cifran. La propiedad de indistinguibilidad bajo un ataque de texto simple elegido se considera un requisito básico para la mayoría de los criptosistemas de clave pública demostrablemente seguros , aunque algunos esquemas también proporcionan indistinguibilidad bajo un ataque de texto cifrado elegido y un ataque de texto cifrado elegido adaptativo . La indistinguibilidad bajo un ataque de texto simple elegido es equivalente a la propiedad de seguridad semántica , y muchas pruebas criptográficas utilizan estas definiciones indistintamente.

Un criptosistema se considera seguro en términos de indistinguibilidad si ningún adversario, dado un cifrado de un mensaje elegido aleatoriamente de un espacio de mensajes de dos elementos determinado por el adversario, puede identificar la elección del mensaje con una probabilidad significativamente mejor que la de la adivinación aleatoria ( 1 ⁄ 2 ). Si cualquier adversario puede lograr distinguir el texto cifrado elegido con una probabilidad significativamente mayor que 1 ⁄ 2 , entonces se considera que este adversario tiene una "ventaja" para distinguir el texto cifrado, y el esquema no se considera seguro en términos de indistinguibilidad. Esta definición abarca la noción de que en un esquema seguro, el adversario no debería aprender ninguna información al ver un texto cifrado. Por lo tanto, el adversario no debería poder hacerlo mejor que si adivinara aleatoriamente.

Definiciones formales

La seguridad en términos de indistinguibilidad tiene muchas definiciones, dependiendo de las suposiciones hechas sobre las capacidades del atacante. Normalmente se presenta como un juego , donde el criptosistema se considera seguro si ningún adversario puede ganar el juego con una probabilidad significativamente mayor que un adversario que debe adivinar aleatoriamente. Las definiciones más comunes utilizadas en criptografía son indistinguibilidad bajo ataque de texto simple elegido (abreviado IND-CPA), indistinguibilidad bajo ataque de texto cifrado elegido (no adaptativo) (IND-CCA1) e indistinguibilidad bajo ataque de texto cifrado elegido adaptativo (IND-CCA2). La seguridad bajo cualquiera de las últimas definiciones implica seguridad bajo las anteriores: un esquema que es seguro IND-CCA1 también es seguro IND-CPA, y un esquema que es seguro IND-CCA2 es seguro tanto IND-CCA1 como IND-CPA. Por lo tanto, IND-CCA2 es la más fuerte de las tres definiciones de seguridad.

Indistinguibilidad bajo ataque de texto simple elegido (IND-CPA)

En el caso de un algoritmo de cifrado de clave asimétrica probabilístico , la indistinguibilidad bajo un ataque de texto simple elegido (IND-CPA) se define mediante el siguiente juego entre un adversario y un contrincante. En el caso de los esquemas basados ​​en la seguridad computacional , el adversario se modela mediante una máquina de Turing de tiempo polinomial probabilística , lo que significa que debe completar el juego y generar una suposición dentro de un número polinomial de pasos de tiempo. En esta definición, E ( PK , M ) representa el cifrado de un mensaje M bajo la clave PK :

1. El retador genera un par de claves PK , SK en función de algún parámetro de seguridad k (por ejemplo, un tamaño de clave en bits) y publica PK para el adversario. El retador conserva SK .
2. El adversario puede realizar un número polinomialmente limitado de encriptaciones u otras operaciones.
3. Finalmente, el adversario presenta al retador dos textos claros distintos elegidos M ₀ , M _{1 .}
4. El retador selecciona un bit b ∈ {0, 1} de manera uniforme y aleatoria, y envía el texto cifrado del desafío C = E ( PK , M _b ) de vuelta al adversario.
5. El adversario es libre de realizar cualquier número de cálculos o cifrados adicionales.
6. Finalmente, el adversario genera una estimación del valor de b .

Un criptosistema es indistinguible bajo un ataque de texto simple elegido si cada adversario de tiempo polinomial probabilístico tiene solo una " ventaja " insignificante sobre la suposición aleatoria. Se dice que un adversario tiene una "ventaja" insignificante si gana el juego anterior con probabilidad , donde es una función insignificante en el parámetro de seguridad , es decir, para cada función polinomial (distinta de cero) poly() existe tal que para todos . ${\displaystyle \left({\tfrac {1}{2}}\right)\,+\,\epsilon (k)}$ ${\displaystyle \epsilon (k)}$ ${\displaystyle k}$ ${\displaystyle k_{0}}$ ${\displaystyle |\epsilon (k)|\;<\;\left|{\tfrac {1}{\mathrm {poly(k)} }}\right|}$ ${\displaystyle k\;>\;k_{0}}$

Aunque el adversario conoce M ₀ , M ₁ y PK , la naturaleza probabilística de E significa que el cifrado de M _b será solo uno de muchos textos cifrados válidos y, por lo tanto, cifrar M ₀ , M ₁ y comparar los textos cifrados resultantes con el texto cifrado de desafío no proporciona ninguna ventaja no despreciable al adversario.

Si bien la definición anterior es específica de un criptosistema de clave asimétrica, se puede adaptar al caso simétrico reemplazando la función de cifrado de clave pública con un oráculo de cifrado , que conserva la clave de cifrado secreta y cifra textos simples arbitrarios a pedido del adversario.

Juego IND-CPA simétrico, formalizado

El proceso adversarial de realizar un ataque de texto simple elegido se describe generalmente en forma de un juego criptográfico. Para probar la IND-CPA simétrica, se define el juego descrito anteriormente. ^[1] Sea una función de generación de claves, una función de cifrado y una función de descifrado. Sea un esquema de cifrado simétrico. El juego Guess se define como: ${\displaystyle {\mathcal {K}}}$ ${\displaystyle {\mathcal {E}}}$ ${\displaystyle {\mathcal {D}}}$ ${\displaystyle {\mathcal {S}}{\mathcal {E}}=({\mathcal {K}},{\mathcal {E}},{\mathcal {D}})}$

Un adversario selecciona tantas veces como desee dos mensajes de texto claro de su elección y se los proporciona al oráculo LR , que devuelve un texto cifrado que encripta uno de los mensajes. La ventaja de un adversario está determinada por su probabilidad de adivinar el valor de b, un valor elegido al azar al comienzo del juego que determina el mensaje que está cifrado en el oráculo LR . Por lo tanto, su ventaja se define como: ^[1] $${\displaystyle \operatorname {Adv} _{\mathcal {SE}}^{\mathrm {ind-cpa} }(A)=2\cdot \Pr \left[\mathrm {Guess} _{\mathcal {SE}}^{A}\Rightarrow \mathrm {true} \right]-1}$$

Indistinguibilidad bajo ataque de texto cifrado elegido/ataque de texto cifrado adaptado (IND-CCA1, IND-CCA2)

La indistinguibilidad bajo ataques de texto cifrado elegido no adaptativos y adaptativos (IND-CCA1, IND-CCA2) utiliza una definición similar a la de IND-CPA. Sin embargo, además de la clave pública (u oráculo de cifrado, en el caso simétrico), el adversario tiene acceso a un oráculo de descifrado que descifra textos cifrados arbitrarios a pedido del adversario y devuelve el texto sin formato. En la definición no adaptativa, el adversario puede consultar este oráculo solo hasta que reciba el texto cifrado de desafío. En la definición adaptativa, el adversario puede continuar consultando el oráculo de descifrado incluso después de haber recibido un texto cifrado de desafío, con la salvedad de que no puede pasar el texto cifrado de desafío para descifrado (de lo contrario, la definición sería trivial).

1. El retador genera un par de claves PK , SK en función de algún parámetro de seguridad k (por ejemplo, un tamaño de clave en bits) y publica PK para el adversario. El retador conserva SK .
2. El adversario puede realizar cualquier número de llamadas al oráculo de cifrado y descifrado basándose en textos cifrados arbitrarios u otras operaciones.
3. Finalmente, el adversario presenta al retador dos textos claros distintos elegidos M ₀ , M _{1 .}
4. El retador selecciona un bit b ∈ {0, 1} de manera uniforme y aleatoria, y envía el texto cifrado de "desafío" C = E ( PK , M _b ) de vuelta al adversario.
5. El adversario es libre de realizar cualquier número de cálculos o cifrados adicionales.
   1. En el caso no adaptativo (IND-CCA1), el adversario no podrá realizar más llamadas al oráculo de descifrado.
   2. En el caso adaptativo (IND-CCA2), el adversario puede realizar más llamadas al oráculo de descifrado, pero no puede enviar el texto cifrado de desafío C.
6. Finalmente, el adversario genera una estimación del valor de b .

Un esquema es seguro IND-CCA1/IND-CCA2 si ningún adversario tiene una ventaja no despreciable en ganar el juego mencionado anteriormente.

Indistinguible del ruido aleatorio

A veces necesitamos esquemas de cifrado en los que la cadena de texto cifrado sea indistinguible de una cadena aleatoria por parte del adversario. ^[2]

Si un adversario no puede saber si un mensaje siquiera existe, esto le otorga a la persona que escribió el mensaje una negación plausible .

Algunas personas que construyen enlaces de comunicación cifrados prefieren hacer que el contenido de cada datagrama cifrado sea indistinguible de los datos aleatorios, con el fin de dificultar el análisis del tráfico. ^[3]

Algunas personas que construyen sistemas para almacenar datos cifrados prefieren que estos sean indistinguibles de los datos aleatorios para que sea más fácil ocultarlos . Por ejemplo, algunos tipos de cifrado de disco , como TrueCrypt, intentan ocultar los datos en los inocentes datos aleatorios que quedan de algunos tipos de borrado de datos . Como otro ejemplo, algunos tipos de esteganografía intentan ocultar los datos haciéndolos coincidir con las características estadísticas del inocente ruido "aleatorio" de la imagen en las fotos digitales.

Para respaldar estos sistemas de cifrado negables , se han diseñado específicamente algunos algoritmos criptográficos para que los mensajes de texto cifrado sean indistinguibles de las cadenas de bits aleatorias. ^{[4] [5] [6]}

La mayoría de las aplicaciones no requieren un algoritmo de cifrado para producir mensajes cifrados que no se puedan distinguir de los bits aleatorios. Sin embargo, algunos autores consideran que estos algoritmos de cifrado son conceptualmente más simples y fáciles de usar, y más versátiles en la práctica; y la mayoría de los algoritmos de cifrado IND-CPA aparentemente producen, de hecho, mensajes cifrados que no se pueden distinguir de los bits aleatorios. ^[7]

Equivalencias e implicaciones

La indistinguibilidad es una propiedad importante para mantener la confidencialidad de las comunicaciones cifradas. Sin embargo, en algunos casos se ha descubierto que la propiedad de indistinguibilidad implica otras propiedades de seguridad aparentemente no relacionadas. A veces, estas implicaciones van en ambas direcciones, lo que hace que dos definiciones sean equivalentes; por ejemplo, se sabe que la propiedad de indistinguibilidad bajo un ataque de texto cifrado seleccionado adaptativo (IND-CCA2) es equivalente a la propiedad de no maleabilidad bajo el mismo escenario de ataque (NM-CCA2). Esta equivalencia no es inmediatamente obvia, ya que la no maleabilidad es una propiedad que tiene que ver con la integridad del mensaje, más que con la confidencialidad. En otros casos, se ha demostrado que la indistinguibilidad se puede combinar con otras definiciones determinadas, para implicar otras definiciones útiles, y viceversa. La siguiente lista resume algunas implicaciones conocidas, aunque de ninguna manera es completa.

La notación significa que la propiedad A implica la propiedad B. significa que las propiedades A y B son equivalentes . significa que la propiedad A no implica necesariamente la propiedad B. ${\displaystyle A\Rightarrow B}$ ${\displaystyle A\Leftrightarrow B}$ ${\displaystyle A\not \Rightarrow B}$

• Seguridad semántica IND-CPA bajo CPA. ${\displaystyle \Leftrightarrow }$
• NM-CPA ( no maleabilidad bajo ataque de texto simple elegido) IND-CPA. ^[8] ${\displaystyle \Rightarrow }$
• NM-CPA ( no maleabilidad bajo ataque de texto simple elegido) IND-CCA2. ^[8] ${\displaystyle \not \Rightarrow }$
• NM-CCA2 ( no maleabilidad bajo ataque de texto cifrado elegido adaptativo) IND-CCA2. ^[8] ${\displaystyle \Leftrightarrow }$

Véase también

• Ataque distintivo
• Indistinguibilidad computacional
• Ataque de texto cifrado seleccionado
• Ataque de texto cifrado adaptable

Referencias

1. Bellare, Mihir; Rogaway, Phillip (11 de mayo de 2005). "Introducción a la criptografía moderna, Capítulo 5: Cifrado simétrico" (PDF) . pág. 93. Consultado el 6 de abril de 2020 .
2. Chakraborty, Debrup; Rodríguez-Henríquez., Francisco (2008). Çetin Kaya Koç (ed.). Ingeniería Criptográfica. pag. 340.ISBN​ 9780387718170.
3. iang (2006-05-20). "Indistinguible de lo aleatorio" . Consultado el 2014-08-06 .
4. Bernstein, Daniel J.; Hamburg, Mike; Krasnova, Anna; Lange, Tanja (28 de agosto de 2013). "Elligator: puntos de curva elíptica indistinguibles de cadenas aleatorias uniformes" (PDF) . Consultado el 23 de enero de 2015 .
5. Möller, Bodo (2004). "Un esquema de cifrado de clave pública con textos cifrados pseudoaleatorios". Seguridad informática – ESORICS 2004. Apuntes de clase en informática. Vol. 3193. págs. 335–351. doi :10.1007/978-3-540-30108-0_21. ISBN 978-3-540-22987-2.
6. Moore, Cristopher; Mertens, Stephan (2011). La naturaleza de la computación. ISBN 9780191620805.
7. Rogaway, Phillip (1 de febrero de 2004). "Cifrado simétrico basado en nonce" (PDF) . págs. 5-6 . Consultado el 7 de agosto de 2014 .
8. Bellare, M., Desai, A., Pointcheval, D. y Rogaway, P. (1998). Relaciones entre nociones de seguridad para esquemas de cifrado de clave pública. En Advances in Cryptology—CRYPTO'98: 18th Annual International Cryptology Conference Santa Barbara, California, EE. UU. 23-27 de agosto de 1998 Actas 18 (pp. 26-45). Springer Berlin Heidelberg.

• Katz, Jonathan; Lindell, Yehuda (2007). Introducción a la criptografía moderna: principios y protocolos. Chapman & Hall / CRC Press . ISBN 978-1584885511.