¿Cómo puede el cifrado implicar aleatoriedad?

8

Si un algoritmo de cifrado está destinado a convertir una cadena en otra cadena que luego se puede descifrar de nuevo al original, ¿cómo podría este proceso implicar alguna aleatoriedad?

Seguramente tiene que ser determinista, de lo contrario, ¿cómo podría la función de descifrado saber qué factores estuvieron involucrados en la creación de la cadena encriptada?

CJ7
fuente
3
No haga preguntas idénticas en varios sitios de Stack Exchange, como este en Crypto.SE .
Paŭlo Ebermann

Respuestas:

5

Puede haber más de un texto cifrado que se correlacione con el mismo texto sin formato. En términos matemáticos, el algoritmo de cifrado debe ser inyectivo para que pueda recuperar el texto sin formato para el texto cifrado, pero esto no evita que el texto cifrado codifique más información que el texto sin formato.

Como ejemplo concreto, considere modos de operación de cifrado de bloque como CBC , CTR u OFB . Todos estos modos implican un IV (vector de inicialización) además del texto sin formato, el algoritmo de cifrado de bloque y su clave. (Para CTR, el IV se llama nonce, pero juega un papel similar). La función de cifrado es determinista para un IV dado. El IV, por otro lado, puede elegirse al azar (para CTR, debe elegirse al azar). Por lo tanto, a menos que el protocolo especifique un método determinista para elegir el IV (como una constante acordada), el IV se envía junto con el texto cifrado. De hecho, la salida del software de cifrado a menudo consiste en el IV seguido del texto cifrado stricto sensu. El IV mismo se envía en texto sin formato; no contiene (no debe) ninguna información confidencial.

Como otro ejemplo, considere el modo PKCS1.5 ("esquema de relleno") de RSA (definido en PKCS # 1 versión 1.5 - consulte las páginas 22–25 de PKCS # 1 v2.1 ). Simplificando un poco, este modo consiste en concatenar una cadena aleatoria con el mensaje y luego aplicar la operación de exponenciación. El texto cifrado es donde es concatenación, es el mensaje y es una cadena de relleno cuya mayoría de los bits son aleatorios. Para recuperar el mensaje del texto cifrado , aplique la operación de descifrado sin formato y divida en relleno (que se descarta) y mensaje.(PM)emodnMPCCdmodnC

Gilles 'SO- deja de ser malvado'
fuente
4

Los esquemas de cifrado no solo pueden ser aleatorios, sino que en algunos casos (por ejemplo, cifrado de clave pública ), deben ser aleatorizados. Esto no es un problema ya que requerimos un esquema de cifrado para que sea correcto , es decir, para cualquier mensaje cualquier clave contenga que sobre la aleatoriedad .mk

Pr[ DEC( ENC(k,m,R) )=m]=1
R

La razón por la que los esquemas de clave pública deben ser aleatorios se deriva de la forma en que definimos la seguridad: no deseamos que el texto cifrado filtre ninguna información sobre el mensaje cifrado. El ejemplo clásico es el siguiente. Suponga que es la clave pública y secreta, respectivamente, y que el adversario intercepta un mensaje cifrado enviado a alguna unidad en el campo. El adversario sabe que el mensaje es "ATAQUE" o "RETIRADA", pero no sabe cuál. Una cosa que el adversario puede hacer es encriptar ambos mensajes usando el público . deje que y . If(pk,sk)cpkcA=ENCpk("ATTACK ")cR=ENCpk("RETREAT")ENCes determinista, el adversario puede encontrar el mensaje con certeza comparando con y .ccAcR

La forma en que esta noción se define formalmente se conoce como seguridad semántica :

Un esquema de cifrado es semánticamente seguro si algún adversario no puede ganar el siguiente juego con una probabilidad notablemente mayor que :A1/2

  1. Un retador genera claves y envía la clave pública al adversario.C(pk,sk)pk
  2. A elige dos mensajes de igual longitud y y los entrega a ambos a .m0m1C
  3. C recoge uniformemente un bit y envía de vuelta .b{0,1}ENC(mb)
  4. A necesita decir qué mensaje se cifró: o , es decir, necesita generar el bit .m0m1b

(Estoy omitiendo el parámetro de seguridad , que es crítico para definir "insignificante" o "notable"; Necesitamos suponer que la generación de las claves depende de , y que la ventaja que tiene es superior es insignificante en , es decir, menor que ) κκA1/2κκω(1)

Sonó.
fuente
podemos agregar una cadena aleatoria al final de la entrada antes de realizar el cifrado para evitar el problema y siempre tener , es decir, la condición puede ser más fuerte que la que ha indicado en la parte superior . DEC(ENC(k,m,R))=m
Kaveh
3

No ha indicado qué tipo de cifrado estamos discutiendo, pero permítame señalar lo que realmente se necesita para la seguridad de los protocolos cartográficos (además de lo que se indica en otras respuestas).

Lo que realmente necesitamos es esto: las claves deben generarse al azar (esto puede hacerse en colaboración como en criptografía de clave pública como RSA o por una entidad como en criptografía de clave privada). La aleatoriedad de la clave asegura que un adversario no pueda predecir las claves (y usarlas para romper el protocolo). Mientras las claves parezcan aleatorias para el adversario, el protocolo será seguro. A menudo, las claves son generadas por un algoritmo aleatorio y luego entregadas a las partes, mientras que los algoritmos de cifrado y descifrado no son aleatorios sino deterministas.

También recuerde que ser aleatorio no significa que el proceso no sea invertable. Un ejemplo simple es el siguiente: dado , generar aleatoriamente , salida . Para invertir, podemos generar la primera parte del par.xrx,r

Kaveh
fuente
su ejemplo es importante: sin relleno aleatorio, vanilla RSA es inseguro. con relleno aleatorio, se puede demostrar que RSA tiene buenas propiedades de seguridad en el modelo de oráculo aleatorio
Sasho Nikolov
1

Tanto el algoritmo de cifrado como el de descifrado se pueden aleatorizar siempre que pueda probar algún teorema de que el cifrado seguido del descifrado le dará el mensaje original la mayoría de las veces .

¿Por qué alguien querría tal esquema de encriptación? Porque: 1) existen situaciones en las que no queremos tener la razón todo el tiempo, pero solo 99999999 veces de cada 100000000 y 2) permitir errores tan pequeños a menudo mejora algo más (como la eficiencia) en una cantidad desproporcionada.

Vinayak Pathak
fuente
3
Si bien existe el cifrado probabilístico, están más bien en el lado exótico. Muchos algoritmos de cifrado cotidianos implican aleatoriedad sin ser probabilísticos.
Gilles 'SO- deja de ser malvado'
@Gilles: Una distinción importante para hacer.
Raphael
0

Solo para citar un ejemplo, en el cifrado RSA , debe generar dos primos y y un número entero que se utilizará para crear sus claves públicas y privadas.pqe

Si genera alguno de estos valores de forma determinista, su generación puede reproducirse, lo que puede comprometer su cifrado. Si estos números se generan de forma aleatoria, entonces esto no es un problema.

Actualizar

Como un ejemplo más específico de Ran G. respuesta 's, usted podría tener una mirada en criptografía de curva elíptica , donde el algoritmo requiere un parámetro aleatorio (generalmente llamado , o ) para cifrar mensajes y en descifrar. Si el mismo parámetro "aleatorio" se usa más de una vez, la clave se puede calcular a partir de dos mensajes cifrados. Este fue el problema / premisa del hack de PlayStation 3 del año pasado .dkr

Pedro
fuente
1
Esta es la aleatoriedad en la generación de claves, que dudo es la pregunta: cualquier generación de claves debe involucrar aleatoriedad, de lo contrario la clave es predecible (o derivada y no generada).
Gilles 'SO- deja de ser malvado'
No creo que ese sea el lugar para la aleatorización que el OP tiene en mente. Se proporcionan claves y estáticas para el cifrado (en | de). La forma en que elige su clave es independiente de eso.
Raphael
@Gilles: No lo consideraría tan claro. Los valores , y generalmente se almacenan en forma cifrada, con una contraseña elegida por el usuario. Estrictamente hablando, son la clave, pero desde la perspectiva del usuario , son solo valores aleatorios generados al escribir galimatías en el teclado y no tienen nada que ver con su contraseña cuidadosamente elegida. pqe
Pedro
@Pedro No entiendo cómo se relaciona tu último comentario con la pregunta. Incluso desde la perspectiva de los archivos de claves (que no veo en la pregunta), la clave evidentemente no se genera aleatoriamente, se deriva del archivo de claves y la contraseña.
Gilles 'SO- deja de ser malvado'