La indistinguibilidad del texto cifrado es una propiedad de muchos esquemas de cifrado . Intuitivamente, si un criptosistema posee la propiedad de indistinguibilidad , el adversario no podrá distinguir pares de textos cifrados en función del mensaje que cifran. La propiedad de indistinguibilidad bajo el ataque de texto plano 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 el ataque de texto cifrado elegido y el ataque de texto cifrado adaptable elegido. La indistinguibilidad bajo el ataque de texto plano elegido es equivalente a la propiedad de la seguridad semántica , y muchas pruebas criptográficas usan estas definiciones indistintamente.
Un criptosistema se considera seguro en términos de indistinguibilidad si ningún adversario, dado el cifrado de un mensaje elegido al azar 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 adivinar al azar ( 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 al azar.
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 al azar. Las definiciones más comunes utilizadas en criptografía son indistinguibilidad bajo ataque de texto plano 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 IND-CCA1 seguro también es IND-CPA seguro, y un esquema que es IND-CCA2 seguro es tanto IND-CCA1 como IND-CPA seguro. Por lo tanto, IND-CCA2 es la más sólida de las tres definiciones de seguridad.
Indistinguibilidad bajo ataque de texto sin formato elegido (IND-CPA)
Para un algoritmo de cifrado de clave asimétrico probabilístico , la indistinguibilidad bajo el ataque de texto plano elegido (IND-CPA) se define por el siguiente juego entre un adversario y un retador. Para esquemas basados en seguridad computacional , el adversario es modelado por una máquina de Turing de tiempo polinomial probabilístico , 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 :
- El retador genera un par de claves PK , SK basado en algún parámetro de seguridad k (por ejemplo, un tamaño de clave en bits) y publica PK al adversario. El retador retiene a SK .
- El adversario puede realizar un número limitado polinomialmente de cifrados u otras operaciones.
- Finalmente, el adversario presenta dos textos planos distintos elegidos al retador.
- El retador selecciona un bit b {0, 1} uniformemente al azar y envía el texto cifrado de desafío C = E (PK,) de vuelta al adversario.
- El adversario es libre de realizar cualquier número de cálculos o cifrados adicionales. Finalmente, genera una estimación del valor de b .
Un criptosistema es indistinguible bajo un ataque de texto llano elegido si cada adversario de tiempo polinomial probabilístico tiene sólo una " ventaja " insignificante sobre la conjetura aleatoria. Se dice que un adversario tiene una "ventaja" insignificante si gana el juego anterior con probabilidad, dónde es una función insignificante en el parámetro de seguridad k , es decir, para cada función polinomial (distinta de cero) existe tal que para todos .
Aunque el adversario sepa , y PK, la naturaleza probabilística de E significa que el cifrado de será sólo uno de los muchos textos cifrados válidos y, por lo tanto, cifrará , y comparar los textos cifrados resultantes con el texto cifrado de desafío no ofrece ninguna ventaja nada despreciable para el adversario.
Si bien la definición anterior es específica de un sistema de cifrado 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 retiene la clave de cifrado secreta y cifra los textos sin formato arbitrarios a petición del adversario.
Juego simétrico IND-CPA, formalizado
El proceso de confrontación de realizar un ataque de texto sin formato elegido generalmente se describe en forma de un juego criptográfico . Para probar el IND-CPA simétrico, se define el juego descrito anteriormente. [1] Deja ser una función de generación de claves, ser una función de cifrado, y ser una función de descifrado. Dejarser un esquema de cifrado simétrico. El juego Se define como:
Todas las veces que quisiera, un adversario selecciona dos mensajes de texto plano de su propia elección y se los proporciona al oráculo LR que devuelve un texto cifrado que cifra 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á encriptado en el oráculo LR . Por tanto, su ventaja se define como: [1]
Indistinguibilidad bajo ataque de texto cifrado elegido / ataque de texto cifrado adaptable elegido (IND-CCA1, IND-CCA2)
Indistinguibilidad bajo ataque de texto cifrado elegido no adaptativo y adaptativo (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 petición del adversario, devolviendo 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 aprobar el texto cifrado de desafío para el descifrado (de lo contrario, la definición sería trivial).
- El retador genera un par de claves PK , SK basado en algún parámetro de seguridad k (por ejemplo, un tamaño de clave en bits) y publica PK al adversario. El retador retiene a SK .
- El adversario puede realizar cualquier número de cifrados, llamadas al oráculo de descifrado basándose en textos cifrados arbitrarios u otras operaciones.
- Finalmente, el adversario presenta dos textos planos distintos elegidos al retador.
- El retador selecciona un bit b ∈ {0, 1} uniformemente al azar y envía el texto cifrado de "desafío" C = E (PK,) de vuelta al adversario.
- El adversario es libre de realizar cualquier número de cálculos o cifrados adicionales.
- En el caso no adaptativo (IND-CCA1), es posible que el adversario no realice más llamadas al oráculo de descifrado.
- En el adaptativa caso (IND-CCA2), el adversario puede realizar más llamadas al oráculo de descifrado, pero no podrá presentar el reto texto cifrado C .
- 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 para ganar el juego anterior.
Indistinguible del ruido aleatorio
A veces necesitamos esquemas de cifrado en los que el adversario no pueda distinguir la cadena de texto cifrado de una cadena aleatoria. [2]
Si un adversario no puede decir si un mensaje existe, le da a la persona que escribió el mensaje una negación plausible .
Algunas personas que crean enlaces de comunicación encriptados prefieren que el contenido de cada datagrama encriptado sea indistinguible de los datos aleatorios, para dificultar el análisis del tráfico. [3]
Algunas personas que crean sistemas para almacenar datos cifrados prefieren que los datos sean indistinguibles de los datos aleatorios para facilitar la ocultación de datos . Por ejemplo, algunos tipos de cifrado de disco , como TrueCrypt, intentan ocultar datos en los datos aleatorios inocentes 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 ruido de imagen "aleatorio" inocente en las fotografías digitales.
Para admitir tales sistemas de cifrado negables , algunos algoritmos criptográficos están diseñados específicamente para hacer que los mensajes de texto cifrado no se puedan distinguir 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 pueden distinguir de los bits aleatorios. Sin embargo, algunos autores consideran que dichos algoritmos de cifrado son conceptualmente más simples y fáciles de trabajar, y más versátiles en la práctica, y la mayoría de los algoritmos de cifrado IND-CPA aparentemente producen mensajes cifrados que son indistinguibles 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, haciendo que dos definiciones sean equivalentes; por ejemplo, se sabe que la propiedad de indistinguibilidad bajo ataque de texto cifrado elegido 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 se ocupa de la integridad del mensaje, más que de la confidencialidad. En otros casos, se ha demostrado que la indistinguibilidad se puede combinar con algunas otras definiciones, a fin de 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.
- IND-CPA seguridad semántica bajo CPA.
- NM-CPA ( no maleabilidad bajo ataque de texto plano elegido) IND-CPA.
- NM-CPA ( no maleabilidad bajo ataque de texto plano elegido) IND-CCA2.
- NM-CCA2 ( no maleabilidad bajo ataque de texto cifrado elegido adaptativo) IND-CCA2.
Ver también
- Ataque distintivo
- Indistinguibilidad computacional
- Ataque de texto cifrado elegido
- Ataque adaptable de texto cifrado elegido
Referencias
- ^ a b Bellare, Mihir; Rogaway, Phillip (11 de mayo de 2005). "Introducción a la criptografía moderna, capítulo 5: cifrado simétrico" (PDF) . pag. 93 . Consultado el 6 de abril de 2020 .
- ^ Chakraborty, Debrup; Rodríguez-Henríquez., Francisco (2008). Çetin Kaya Koç (ed.). Ingeniería criptográfica . pag. 340. ISBN 9780387718170.
- ^ iang (20 de mayo de 2006). "Indistinguible de aleatorio" . Consultado el 6 de agosto de 2014 .
- ^ Bernstein, Daniel J .; Hamburgo, Mike; Krasnova, Anna; Lange, Tanja (28 de agosto de 2013). "Eligador: puntos de curva elíptica indistinguibles de cadenas aleatorias uniformes" (PDF) . Consultado el 23 de enero de 2015 .
- ^ Möller, Bodo (2004). "Un esquema de cifrado de clave pública con textos cifrados pseudoaleatorios". Seguridad informática - ESORICS 2004 . Apuntes de conferencias en informática. 3193 . págs. 335–351. doi : 10.1007 / 978-3-540-30108-0_21 . ISBN 978-3-540-22987-2.
- ^ Moore, Cristopher; Mertens, Stephan (2011). La naturaleza de la computación . ISBN 9780191620805.
- ^ 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 .
- Katz, Jonathan; Lindell, Yehuda (2007). Introducción a la criptografía moderna: principios y protocolos . Chapman & Hall / CRC Press . ISBN 978-1584885511.