Hispanopedia Wiki
Articulo de referencia

Indistinguibilidad del texto cifrado

La indistinguibilidad de los textos cifrados es una propiedad de muchos esquemas de cifrado . Intuitivamente, si un criptosistema posee esta propiedad , un adversario no podrá d...

Hispanopedia WikiContenido en espanolLectura gratuita

La indistinguibilidad de los textos cifrados es una propiedad de muchos esquemas de cifrado . Intuitivamente, si un criptosistema posee esta propiedad , un adversario no podrá distinguir pares de textos cifrados basándose en el mensaje que cifran. La indistinguibilidad ante ataques de texto plano elegido se considera un requisito básico para la mayoría de los criptosistemas de clave pública con seguridad demostrable , aunque algunos esquemas también ofrecen indistinguibilidad ante ataques de texto cifrado elegido y ataques adaptativos de texto cifrado elegido . La indistinguibilidad ante ataques de texto plano elegido es equivalente a la seguridad semántica , y muchas pruebas criptográficas utilizan estas definiciones indistintamente.

Un sistema criptográfico 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 mayor que la de adivinar al azar ( 1/2). Si algún adversario logra 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 obtener 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 sobre las capacidades del atacante. Normalmente se presenta como un juego , donde el criptosistema se considera seguro si ningún adversario puede ganar con una probabilidad significativamente mayor que la de un adversario que debe adivinar al azar. Las definiciones más comunes utilizadas en criptografía son la indistinguibilidad bajo un ataque de texto plano elegido (abreviado IND-CPA), la indistinguibilidad bajo un ataque de texto cifrado elegido (no adaptativo) (IND-CCA1) y la indistinguibilidad bajo un ataque de texto cifrado elegido adaptativo (IND-CCA2). La seguridad bajo cualquiera de estas últimas definiciones implica seguridad bajo las anteriores: un esquema que es seguro según IND-CCA1 también lo es según IND-CPA, y un esquema que es seguro según IND-CCA2 lo es tanto según IND-CCA1 como según IND-CPA. Por lo tanto, IND-CCA2 es la más robusta de las tres definiciones de seguridad.

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

Para un algoritmo de cifrado de clave asimétrica probabilístico , la indistinguibilidad bajo un ataque de texto plano elegido (IND-CPA) se define mediante el siguiente juego entre un adversario y un retador. Para esquemas basados ​​en seguridad computacional , el adversario se modela mediante una máquina de Turing probabilística de tiempo polinomial , 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 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 conserva SK .
  2. El adversario puede realizar un número polinomialmente limitado de cifrados u otras operaciones.
  3. Finalmente, el adversario presenta al retador dos textos planos elegidos distintos, M 0 , M 1 .
  4. El retador selecciona un bit b ∈ {0, 1} uniformemente al azar y envía el texto cifrado de desafío C = E ( PK , M b ) de vuelta al adversario.
  5. El adversario tiene libertad para realizar cualquier número de cálculos o cifrados adicionales.
  6. Finalmente, el adversario produce una suposición para el valor de b .

Un criptosistema es indistinguible bajo un ataque de texto plano elegido si cada adversario de tiempo polinomial probabilístico tiene solo una " ventaja " insignificante sobre la adivinación aleatoria. Se dice que un adversario tiene una "ventaja" insignificante si gana el juego anterior con probabilidad(12)+ϵ(k){\displaystyle \left({\tfrac {1}{2}}\right)\,+\,\epsilon (k)}, dóndeϵ(k){\displaystyle \epsilon (k)}es una función insignificante en el parámetro de seguridadk{\displaystyle k}, es decir, para cada función polinómica (distinta de cero) poly() existek0{\displaystyle k_{0}}de tal manera que|ϵ(k)|<|1pagoly(k)|{\displaystyle |\epsilon (k)|\;<\;\left|{\tfrac {1}{\mathrm {poly(k)} }}\right|}a pesar dek>k0{\displaystyle k\;>\;k_{0}}.

Aunque el adversario conoce M 0 , M 1 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 0 , M 1 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, puede adaptarse al caso simétrico reemplazando la función de cifrado de clave pública por un oráculo de cifrado , que conserva la clave de cifrado secreta y cifra textos planos arbitrarios a petición del adversario.

Juego IND-CPA simétrico, formalizado

El proceso adversario de realizar un ataque de texto plano elegido se suele describir en forma de juego criptográfico . Para probar el IND-CPA simétrico, se define el juego descrito anteriormente. [ 1 ] SeaK{\displaystyle {\mathcal {K}}}ser una función de generación de claves,mi{\displaystyle {\mathcal {E}}}ser una función de cifrado yD{\displaystyle {\mathcal {D}}}Sea una función de descifrado.Smi=(K,mi,D){\displaystyle {\mathcal {S}}{\mathcal {E}}=({\mathcal {K}},{\mathcal {E}},{\mathcal {D}})}ser un esquema de cifrado simétrico. El juego "Adivina" se define como:

Un adversario selecciona dos mensajes en texto plano de su elección tantas veces como desee y los proporciona al oráculo LR, que devuelve un texto cifrado que encripta uno de los mensajes. La ventaja del 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 se encripta en el oráculo LR . Por lo tanto, su ventaja se define como: [ 1 ]AdvSmiinorted−dopaga⁡(A)=2⋅Pr[GRAMOtúmissSmiA⇒trtúmi]−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 adaptativo de texto cifrado elegido (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 (o el 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 plano. En la definición no adaptativa, el adversario solo puede consultar este oráculo hasta que reciba el texto cifrado de desafío. En la definición adaptativa, el adversario puede seguir 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 proporcionar dicho texto para su descifrado (de lo contrario, la definición sería trivial).

  1. 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 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 planos elegidos distintos, M 0 , M 1 .
  4. El retador selecciona un bit b ∈ {0, 1} uniformemente al azar y envía el texto cifrado de "desafío" C = E ( PK , M b ) de vuelta al adversario.
  5. El adversario tiene libertad para realizar cualquier número de cálculos o cifrados adicionales.
    1. En el caso no adaptativo (IND-CCA1), el adversario no puede realizar más llamadas al oráculo de descifrado.
    2. En el caso adaptativo (IND-CCA2), el adversario puede realizar llamadas adicionales al oráculo de descifrado, pero no puede enviar el texto cifrado de desafío C.
  6. Finalmente, el adversario produce una suposición para el valor de b .

Un esquema es IND-CCA1/IND-CCA2 seguro 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 la cadena de texto cifrado sea indistinguible de una cadena aleatoria para el adversario. [ 2 ]

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

Algunas personas que construyen enlaces de comunicación encriptados prefieren hacer que el contenido de cada datagrama encriptado sea indistinguible de datos aleatorios, para dificultar el análisis del tráfico. [ 3 ]

Algunas personas que diseñan sistemas para almacenar datos cifrados prefieren que estos sean indistinguibles de los datos aleatorios para facilitar su ocultación . Por ejemplo, algunos tipos de cifrado de disco, como TrueCrypt, intentan ocultar datos entre los datos aleatorios que quedan tras ciertos procesos de borrado . Otro ejemplo es la esteganografía , que intenta ocultar datos haciendo que coincidan con las características estadísticas del ruido "aleatorio" de las fotografías digitales.

Para respaldar estos sistemas de cifrado negables , algunos algoritmos criptográficos están diseñados específicamente para hacer que los mensajes cifrados sean indistinguibles de cadenas de bits aleatorias. [ 4 ] [ 5 ] [ 6 ]

La mayoría de las aplicaciones no requieren un algoritmo de cifrado para producir mensajes cifrados indistinguibles de bits aleatorios. Sin embargo, algunos autores consideran que dichos algoritmos de cifrado son conceptualmente más simples, más fáciles de usar y más versátiles en la práctica; y, al parecer, la mayoría de los algoritmos de cifrado IND-CPA sí producen mensajes cifrados indistinguibles de 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 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 un ataque adaptativo de texto cifrado elegido (IND-CCA2) es equivalente a la propiedad de no maleabilidad bajo el mismo ataque (NM-CCA2). Esta equivalencia no es inmediatamente obvia, ya que la no maleabilidad es una propiedad relacionada con la integridad del mensaje, no con la confidencialidad. En otros casos, se ha demostrado que la indistinguibilidad puede combinarse con otras definiciones para implicar otras definiciones útiles, y viceversa. La siguiente lista resume algunas implicaciones conocidas, aunque no es exhaustiva.

La notaciónA⇒B{\displaystyle A\Rightarrow B}significa que la propiedad A implica la propiedad B.A⇔B{\displaystyle A\flecha izquierda derecha B}significa que las propiedades A y B son equivalentes .A⇏B{\displaystyle A\not \Rightarrow B}significa que la propiedad A no implica necesariamente la propiedad B.

  • Contador Público Certificado (IND-CPA)⇔{\displaystyle \Leftrightarrow }Seguridad semántica bajo ataques de texto plano elegido.
  • NM-CPA ( no maleabilidad ante ataques de texto plano elegido)⇒{\displaystyle \Rightarrow }IND-CPA. [ 8 ]
  • NM-CPA ( no maleabilidad ante ataques de texto plano elegido)⇏{\displaystyle \not \Rightarrow }IND-CCA2. [ 8 ]
  • NM-CCA2 ( no maleabilidad bajo ataque adaptativo de texto cifrado elegido)⇔{\displaystyle \Leftrightarrow }IND-CCA2. [ 8 ]

Véase también

Referencias

  1. 1 2 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. Recuperado el 6 de abril de 2020 .
  2. ↑ Chakraborty, Debrup; Rodríguez-Henríquez., Francisco (2008). Çetin Kaya Koç (ed.). Ingeniería Criptográfica . Saltador. pag. 340.ISBN​  9780387718170.
  3. ↑ iang (2006-05-20). "Indistinguible de aleatorio" . Recuperado el 2014-08-06 .
  4. ↑ Bernstein, Daniel J.; Hamburg, Mike; Krasnova, Anna; Lange, Tanja (2013-08-28). "Elligator: puntos de curva elíptica indistinguibles de cadenas aleatorias uniformes" (PDF) . Recuperado el 2015-01-23 .
  5. ↑ Möller, Bodo (2004). "Un esquema de cifrado de clave pública con textos cifrados pseudoaleatorios". Seguridad informática – ESORICS 2004. Notas de clase en ciencias de la computación. Vol. 3193. pp. 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 . Oxford University Press. ISBN 9780191620805.
  7. ↑ Rogaway, Phillip (1 de febrero de 2004). "Cifrado simétrico basado en nonce" (PDF) . págs. 5–6 . Recuperado el 7 de agosto de 2014 . 
  8. 1 2 3 Bellare, M., Desai, A., Pointcheval, D., & Rogaway, P. (1998). Relaciones entre nociones de seguridad para esquemas de cifrado de clave pública. En Avances en Criptología—CRYPTO'98: 18.ª Conferencia Internacional Anual de Criptología Santa Bárbara, California, EE. UU. 23-27 de agosto de 1998 Actas 18 (págs. 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.