Criptosistema Cramer-Shoup

El sistema Cramer-Shoup es un algoritmo de cifrado de clave asimétrica y fue el primer esquema eficiente cuya seguridad contra ataques adaptativos de texto cifrado elegido (CCT) se demostró utilizando supuestos criptográficos estándar. Su seguridad se basa en la intratabilidad computacional (ampliamente asumida, pero no probada) del supuesto decisional de Diffie-Hellman . Desarrollado por Ronald Cramer y Victor Shoup en 1998, es una extensión del criptosistema ElGamal . A diferencia de ElGamal, que es extremadamente maleable, Cramer-Shoup añade otros elementos para garantizar la inmutabilidad incluso frente a un atacante con recursos. Esta inmutabilidad se logra mediante el uso de una función hash unidireccional universal y cálculos adicionales, lo que da como resultado un texto cifrado dos veces más grande que en ElGamal.

Ataques adaptativos de texto cifrado elegido

La definición de seguridad alcanzada por Cramer-Shoup se denomina formalmente " indistinguibilidad bajo ataque adaptativo de texto cifrado elegido " ( IND-CCA2 ). Esta definición de seguridad es actualmente la más sólida conocida para un criptosistema de clave pública: presupone que el atacante tiene acceso a un oráculo de descifrado que descifrará cualquier texto cifrado utilizando la clave secreta de descifrado del esquema. El componente "adaptativo" de la definición de seguridad significa que el atacante tiene acceso a este oráculo de descifrado tanto antes como después de observar un texto cifrado objetivo específico para atacar (aunque tiene prohibido usar el oráculo simplemente para descifrar este texto cifrado objetivo). La noción más débil de seguridad contra ataques no adaptativos de texto cifrado elegido ( IND-CCA1 ) solo permite al atacante acceder al oráculo de descifrado antes de observar el texto cifrado objetivo.

Aunque era bien sabido que muchos criptosistemas de uso generalizado eran vulnerables a un atacante de este tipo, durante muchos años los diseñadores de sistemas consideraron que el ataque era poco práctico y de interés principalmente teórico. Esto comenzó a cambiar a finales de la década de 1990, en particular cuando Daniel Bleichenbacher demostró un ataque práctico de texto cifrado elegido adaptativo contra servidores SSL utilizando una forma de cifrado RSA . ^{[ 1 ]}

El esquema de cifrado Cramer-Shoup no fue el primero en proporcionar seguridad contra ataques adaptativos de texto cifrado elegido. Naor-Yung, Rackoff-Simon y Dolev-Dwork-Naor propusieron conversiones demostrablemente seguras de esquemas estándar ( IND-CPA ) a esquemas IND-CCA1 e IND-CCA2. Estas técnicas son seguras bajo un conjunto estándar de supuestos criptográficos (sin oráculos aleatorios); sin embargo, dependen de técnicas complejas de prueba de conocimiento cero y son ineficientes en términos de costo computacional y tamaño del texto cifrado. Diversos enfoques, incluidos OAEP de Bellare / Rogaway y Fujisaki-Okamoto, logran construcciones eficientes utilizando una abstracción matemática conocida como oráculo aleatorio . Desafortunadamente, para implementar estos esquemas en la práctica se requiere la sustitución de alguna función práctica (por ejemplo, una función hash criptográfica ) en lugar del oráculo aleatorio. Un creciente conjunto de evidencia sugiere la inseguridad de este enfoque, ^[²^] aunque no se han demostrado ataques prácticos contra esquemas implementados.

El criptosistema

El algoritmo Cramer-Shoup consta de tres algoritmos: el generador de claves, el algoritmo de cifrado y el algoritmo de descifrado.

Generación de claves

Alice genera una descripción eficiente de un grupo cíclico. $G$ del orden $q$ con dos generadores aleatorios distintos $g_{1},g_{2}$ .
Alice elige cinco valores aleatorios. $({x}_{1},{x}_{2},{y}_{1},{y}_{2},z)$ de $\{0,\ldots ,q-1\}$ .
Alice calcula $c={g}_{1}^{x_{1}}g_{2}^{x_{2}},d={g}_{1}^{y_{1}}g_{2}^{y_{2}},h={g}_{1}^{z}$ .
Alice publica $(c,d,h)$ , junto con la descripción de $G,q,g_{1},g_{2}$ , como su clave pública . Alice conserva $(x_{1},x_{2},y_{1},y_{2},z)$ como su clave secreta . El grupo puede ser compartido entre usuarios del sistema.

Cifrado

Para cifrar un mensaje $m$ a Alice bajo su clave pública $(G,q,g_{1},g_{2},c,d,h)$ ,

Bob se convierte $m$ en un elemento de $G$ .
Bob elige uno al azar $k$ $k$ de $\{0,\ldots ,q-1\}$ $\{0,\ldots ,q-1\}$ , luego calcula:
- $u_{1}={g}_{1}^{k},u_{2}={g}_{2}^{k}$
- $e=h^{k}m$
- $\alpha =H(u_{1},u_{2},e)$ , donde H () es una función hash unidireccional universal (o una función hash criptográfica resistente a colisiones , que es un requisito más estricto).
- $v=c^{k}d^{k\alpha }$
Bob envía el texto cifrado $(u_{1},u_{2},e,v)$ a Alicia.

Descifrado

Para descifrar un texto cifrado $(u_{1},u_{2},e,v)$ con la llave secreta de Alicia $(x_{1},x_{2},y_{1},y_{2},z)$ ,

Alice calcula $\alpha =H(u_{1},u_{2},e)\,$ y verifica que ${u}_{1}^{x_{1}}u_{2}^{x_{2}}({u}_{1}^{y_{1}}u_{2}^{y_{2}})^{\alpha }=v\,$ Si esta prueba falla, se interrumpe el descifrado y se rechaza el resultado.
De lo contrario, Alice calcula el texto plano como $m=e/({u}_{1}^{z})\,$ .

La etapa de descifrado descifra correctamente cualquier texto cifrado con el formato adecuado, ya que

{u}_{1}^{z}={g}_{1}^{kz}=h^{k}\,

, y

m=e/h^{k}.\,

Si el espacio de mensajes posibles es mayor que el tamaño de $G$ , entonces Cramer-Shoup puede usarse en un criptosistema híbrido para mejorar la eficiencia en mensajes largos.

Referencias

↑ Daniel Bleichenbacher. Ataques de texto cifrado elegido contra protocolos basados en el estándar de cifrado RSA PKCS #1. Avances en criptología – CRYPTO '98.
↑ Ran Canetti, Oded Goldreich , Shai Halevi. La metodología del oráculo aleatorio, una revisión . Journal of the ACM, 51:4, páginas 557–594, 2004.

Ronald Cramer y Victor Shoup . «Un criptosistema práctico de clave pública con seguridad demostrable frente a ataques adaptativos de texto cifrado elegido». En las actas de Crypto 1998, LNCS 1462, pág. 13 y siguientes ( ps , pdf ).
Implementaciones sencillas del algoritmo Cramer-Shoup en Emacs Lisp y Java.
Cobertura periodística de 1998 sobre la publicación de Cramer y Shoup en Wired News y en Crypto-Gram de Bruce Schneier .
Ronald Cramer y Victor Shoup : «Pruebas hash universales y un paradigma para el cifrado de clave pública seguro frente a ataques de texto cifrado elegido». En las actas de Eurocrypt 2002, LNCS 2332, págs. 45-64. Versión completa (pdf).

[1] Daniel Bleichenbacher. Ataques de texto cifrado elegido contra protocolos basados en el estándar de cifrado RSA PKCS #1. Avances en criptología – CRYPTO '98.

[2] Ran Canetti, Oded Goldreich , Shai Halevi. La metodología del oráculo aleatorio, una revisión . Journal of the ACM, 51:4, páginas 557–594, 2004.

[ 1 ]

[