Indistinguibilidad del texto cifrado

La indistinguibilidad del texto cifrado es una propiedad de muchos sistemas de cifrado . Intuitivamente, si un sistema tiene la propiedad de indistinguibilidad, entonces un atacante no podrá distinguir pares de textos cifrados en función de los textos sin formato que cifran. La propiedad de indistinguibilidad para los ataques basados en el texto sin formato elegido se considera un requisito básico para los criptosistemas de clave pública probablemente más seguros , aunque algunos sistemas de cifrado también tienen una propiedad de indistinguibilidad para los ataques basados en el texto sin formato elegido y para los ataques adaptativos basados en el texto cifrado elegido. La indistinguibilidad de los ataques de texto sin formato elegido es el equivalente a la seguridad semántica de un sistema, por lo que estas definiciones se consideran intercambiables en muchas pruebas criptográficas.

Un criptosistema se considera seguro desde el punto de vista de la indistinguibilidad [1] si ningún atacante, después de haber recibido un texto cifrado seleccionado aleatoriamente de un espacio de mensaje de dos elementos definido por el adversario, puede identificar el texto sin formato correspondiente a este texto cifrado con una probabilidad significativamente mejor que con adivinanzas aleatorias (1⁄2 ). Si cualquier atacante puede lograr discernir el texto cifrado elegido con una probabilidad significativamente mayor que 1⁄2, entonces se dice que ese atacante tiene una "ventaja" para discernir el texto cifrado, y el sistema no se considera seguro desde el punto de vista de la indistinguibilidad . . Esta definición incluye la noción de que, en un sistema seguro, un atacante no debe obtener ninguna información al ver el texto cifrado . Por lo tanto, un atacante no debería poder distinguir entre textos cifrados mejor que si adivinara al azar.

Definiciones formales

La seguridad en términos de indistinguibilidad tiene muchas definiciones, dependiendo de las suposiciones sobre las capacidades del atacante. Generalmente se usa la siguiente analogía. Un criptosistema es una especie de juego . Además, un criptosistema se considera seguro si ningún participante puede ganar el juego con una probabilidad significativamente mayor que un participante que actuará al azar. Los conceptos más comunes utilizados en criptografía son la indistinguibilidad de los ataques de texto sin formato elegido (abreviado como IND-CPA), la indistinguibilidad de los ataques de texto cifrado elegido (no adaptativo) (IND-CCA1) y la indistinguibilidad de los ataques de texto cifrado elegido adaptativo (IND-CCA). CPA).CCA2). La seguridad en el sentido de cada una de las definiciones anteriores implica seguridad en el sentido de cada una de las anteriores: un criptosistema que es seguro IND-CCA1 también es seguro IND-CPA y, en consecuencia, un sistema que es seguro IND-CCA2 es a la vez IND-CCA1 e IND-CPA seguro. Por lo tanto, la seguridad en el sentido de IND-CCA2 es la más sólida de las tres definiciones.

Indiscernibilidad para ataques de texto sin formato elegidos (IND-CPA)

Para un algoritmo probabilístico para el cifrado de claves asimétricas, la indistinguibilidad en el sentido de IND-CPA [2] está determinada por el siguiente juego entre el atacante y el probador. Para los sistemas basados en seguridad computacional, el atacante es modelado por una máquina de Turing polinómica probabilística , lo que significa que debe completar el juego y adivinar un número polinomial de pasos de tiempo. En esta definición, E(PK, M ) representa el texto cifrado del mensaje M , obtenido mediante la clave PK :

El probador genera un par de claves PK , SK basado en algún parámetro de seguridad k (por ejemplo, el tamaño de la clave en bits) y publica el PK para el atacante. El probador salva a SK .
Un atacante puede realizar un número polinomialmente limitado de encriptaciones u otras operaciones.
Eventualmente, el atacante presenta dos textos sin formato separados al probador. ${\ estilo de pantalla \ estilo de script M_{0}, M_{1))$
El probador elige el bit b {0, 1} al azar y envía el texto cifrado probado C = E (PK, ) de vuelta al atacante. ${\ estilo de pantalla \ estilo de script \ en }$ ${\ estilo de pantalla \ estilo de script M_ {b}}$
Un atacante puede realizar cualquier cantidad de cálculos o cifrados adicionales. Finalmente, imprime solo el valor de b .

Un criptosistema es seguro en el sentido de IND-CPA si cualquier atacante creíble en tiempo polinomial tiene solo una pequeña "ventaja" para distinguir los textos cifrados sobre las conjeturas aleatorias. El atacante tiene una "ventaja" insignificante si gana el juego anterior con probabilidad , donde es una función insignificante para el parámetro de seguridad k , es decir, para cualquier función polinómica (distinta de cero) , que tiene , tal que para todos . $\scriptstyle \left({\frac {1}{2}}\right)\,+\,\epsilon (k)$ ${\ estilo de pantalla \ estilo de script \ epsilon (k)}$ ${\ estilo de pantalla \ estilo de script poli ()}$ ${\ estilo de pantalla \ estilo de script k_ {0))$ $\scriptstyle |\epsilon (k)|\;<\;\left|{\frac {1}{poly(k)))\right|$ ${\displaystyle \scriptstyle k\;>\;k_{0))$

Aunque el atacante conoce , y PK, la naturaleza probabilística de E significa que el texto cifrado será solo uno de muchos textos cifrados válidos y, por lo tanto , cifrar y comparar los textos cifrados recibidos con el texto cifrado del probador no le da al atacante ninguna ventaja significativa. ${\ estilo de pantalla \ estilo de script M_ {0}}$ ${\ estilo de pantalla \ estilo de script M_ {1}}$ ${\ estilo de pantalla \ estilo de script M_ {b}}$ ${\ estilo de pantalla \ estilo de script M_ {0}}$ ${\ estilo de pantalla \ estilo de script M_ {1}}$

Aunque la definición anterior es específica de los criptosistemas de clave asimétrica , se puede adaptar al caso simétrico reemplazando la función de cifrado de clave pública con el cifrado de Oracle , que almacena la clave secreta de cifrado y cifra textos sin formato arbitrarios a pedido del atacante.

Indistinguibilidad de ataques de texto cifrado elegidos/ataques de texto cifrado adaptativo (IND-CCA1, IND-CCA2)

La seguridad en el sentido de IND-CCA1 e IND-CCA2 [1] se define de manera similar a la confiabilidad del sistema en el sentido de IND-CPA. Sin embargo, además de la clave pública (o el cifrado de Oracle , en el caso simétrico ), el atacante tiene acceso al descifrado de Oracle, que descifra textos cifrados arbitrarios a petición del atacante y devuelve el texto sin formato . En la definición de IND-CCA1, un atacante solo puede consultar el oráculo hasta que haya recibido el texto cifrado bajo prueba. En la definición IND-CCA2, el atacante puede continuar consultando el oráculo después de recibir el texto cifrado bajo prueba, con la advertencia de que no puede enviarlo para descifrarlo (de lo contrario, la definición sería trivial).

El probador genera un par de claves PK , SK basado en algún parámetro de seguridad k (por ejemplo, el tamaño de la clave en bits) y publica el PK para el atacante. El probador salva a SK .
Un atacante puede realizar cualquier cantidad de cifrados , llamadas de descifrado con un oráculo basado en textos cifrados arbitrarios u otras operaciones.
Eventualmente, el atacante presenta dos textos sin formato separados al probador. ${\ estilo de pantalla \ estilo de script M_{0}, \, M_ {1))$
El probador elige el bit b {0, 1} al azar y envía el texto cifrado probado C = E (PK, ) de vuelta al atacante. ${\ estilo de pantalla \ estilo de script \ en }$ ${\ estilo de pantalla \ estilo de script M_ {b}}$
Un atacante puede realizar cualquier cantidad de cálculos o cifrados adicionales.
1. En la definición de IND-CCA1, el atacante no puede realizar más descifrado con Oracle .
2. En la definición de IND-CCA2, el atacante puede realizar más llamadas de Oracle , pero no puede usar el texto cifrado C para hacerlo .
Finalmente, el atacante adivina el valor de b .

Un criptosistema es seguro en el sentido de IND-CCA1 o IND-CCA2 si ninguno de los oponentes tiene una ventaja significativa en el juego dado.

Indistinguible del ruido aleatorio

A veces , se requieren sistemas de cifrado en los que un atacante no puede distinguir una cadena de texto cifrado de una cadena aleatoria. [3]

Si el atacante ni siquiera puede saber si el mensaje existe, esto le da a la persona que escribió el mensaje una negación plausible .

Algunas personas que crean canales de comunicación encriptados prefieren hacer que el contenido de cada texto encriptado sea indistinguible de los datos aleatorios para dificultar el análisis del tráfico. [cuatro]

Algunas personas que crean sistemas para almacenar datos cifrados prefieren que los datos no se distingan de los datos aleatorios para que sea más fácil ocultarlos . Por ejemplo, algunos tipos de cifrado de disco , como TrueCrypt , intentan ocultar datos en los datos aleatorios que quedan de ciertos tipos de destrucción de datos . Como otro ejemplo, algunos tipos de esteganografía intentan ocultar datos haciéndolos coincidir con las características estadísticas del ruido de imagen "aleatorio" en fotografías digitales .

Por el momento, existen algoritmos criptográficos especialmente diseñados para sistemas de encriptación negable , en los que los textos cifrados son indistinguibles de cadenas de bits aleatorias. [5] [6] [7]

Si el algoritmo de cifrado E puede construirse de tal manera que un atacante (generalmente definido como un observador de tiempo polinomial) que conoce el texto sin formato del mensaje m no puede distinguir entre E(m) y una cadena de bits aleatoria recién generada del misma longitud, como E(m), entonces se deduce que si E(m1) tiene la misma longitud que E(m2), estos dos textos cifrados serán indistinguibles entre sí para un atacante, incluso si conoce el texto sin formato m1 y m2 (IND-CPA). [ocho]

La mayoría de las aplicaciones no requieren un algoritmo de cifrado para crear textos cifrados que no se pueden distinguir de los bits aleatorios. Sin embargo, algunos autores creen que dichos algoritmos de encriptación 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 encriptación IND-CPA parecen producir mensajes encriptados que no se distinguen de los bits aleatorios. [9]

Equivalentes y su significado

La indiscernibilidad es una propiedad importante para mantener la confidencialidad de los mensajes cifrados. Sin embargo, se ha encontrado que en algunos casos la propiedad de indistinguibilidad implica otras propiedades no relacionadas explícitamente con la seguridad. A veces, tales definiciones equivalentes tienen significados completamente diferentes. Por ejemplo, se sabe que la propiedad de indistinguibilidad en el sentido de IND-CPA es equivalente a la propiedad de inflexibilidad para ataques de escenarios similares (NM-CCA2). Esta equivalencia no es inmediatamente obvia, ya que la inflexibilidad es una propiedad relacionada con la integridad del mensaje, no con la confidencialidad. También se ha demostrado que la indistinguibilidad puede derivarse de alguna otra definición o viceversa. La siguiente lista enumera algunas consecuencias conocidas, aunque están lejos de ser completas:

Seguridad semántica IND-CPA para CPA. [diez] ${\ estilo de pantalla \ estilo de script \ Leftrightarrow}$
NM-CPA (Inflexibilidad para ataques de texto sin formato elegidos ) IND-CPA. [una] ${\ estilo de pantalla \ estilo de script \ flecha derecha}$
NM-CPA (inflexibilidad para ataques de texto sin formato elegidos ) IND-CCA2 . [una] ${\ estilo de pantalla \ estilo de script \ no \ flecha derecha}$
NM-CCA2 (Inflexibilidad para ataques basados en texto cifrado adaptativo) IND-CCA2. [una] ${\ estilo de pantalla \ estilo de script \ Leftrightarrow}$

Notas

↑ 1 2 3 4 5 Krohn, Maxwell. Sobre las definiciones de seguridad criptográfica : revisión del ataque de texto cifrado elegido . — 1999.
↑ Katz, Jonathan; Lindell, Yehuda. Introducción a la Criptografía Moderna : Principios y Protocolos . — Chapman y Hall/CRC, 2007.
↑ Chakraborty, Debrup; Rodríguez-Henríquez., Francisco. Ingeniería criptográfica (neopr.) / Çetin Kaya Koç. - 2008. - S. 340. - ISBN 9780387718170 .
↑ ian. Indistinguible de aleatorio (20 de mayo de 2006). Consultado el 6 de agosto de 2014. Archivado desde el original el 15 de agosto de 2014. (indefinido)
↑ Bernstein, Daniel J.; Hamburgo, Mike; Krasnova, Anna; Lange, Tanja Elligator: Puntos de curva elíptica indistinguibles de cadenas aleatorias uniformes (28 de agosto de 2013). Consultado el 23 de enero de 2015. Archivado desde el original el 5 de noviembre de 2014. (indefinido)
↑ Möller, Bodo. Un esquema de cifrado de clave pública con textos cifrados pseudoaleatorios // Seguridad informática - ESORICS 2004 (neopr.) . - 2004. - T. 3193. - S. 335-351. — (Apuntes de clase en informática). — ISBN 978-3-540-22987-2 . -doi : 10.1007 / 978-3-540-30108-0_21 .
↑ Moore, Cristóbal; Mertens, Stephan. La naturaleza de la computación (neopr.) . - 2011. - ISBN 9780191620805 .
↑ Reingold, Omar Pseudo-Random Synthesizers, Functions and Permutations 4 (noviembre de 1998). Consultado el 7 de agosto de 2014. Archivado desde el original el 19 de febrero de 2014. (indefinido)
↑ Rogaway, Cifrado simétrico basado en Phillip Nonce 5–6 (1 de febrero de 2004). Consultado el 7 de agosto de 2014. Archivado desde el original el 10 de mayo de 2013. (indefinido)
↑ Silvio Micali, Shafi Goldwasser Cifrado probabilístico (1984). (indefinido)

Literatura

Katz, Jonathan; Lindell, Yehuda. Introducción a la Criptografía Moderna : Principios y Protocolos . -Chapman & Hall / CRC Press , 2007. -ISBN 978-1584885511 .