Definitions and security (16 min)

La semana pasada, aprendimos la teoría numérica
necesaria para la criptografía de clave pública.

Esta semana vamos a poner a trabajar ese
conocimiento y vamos a construir varios

esquemas de criptografía de clave pública seguros.
Pero primero es necesario definir qué es

la criptografía de clave pública y qué significa
que la criptografía de clave pública sea

segura. Así, permitidme recordaros que en un
esquema de criptografía de clave pública hay un

algoritmo de encriptación, normalmente denotado
como E, y un algoritmo de

desencriptado que denotamos como D. En cualquier
caso, aquí el algoritmo de encriptación usa una

clave pública, mientras que el de desencriptado
usa una clave privada. Este par se denomina

par de claves. Y la clave pública se utiliza para
encriptar mensajes mientras que la clave privada

se utiliza para desencriptarlos. Por tanto, en este
caso, un mensaje "m" se encripta usando

la clave pública y lo que se obtiene de ello es el
texto cifrado, "c". Y, de forma similar,

el texto cifrado se usa para alimentar el algoritmo de
desencriptado usando la clave privada y lo que

se obtiene del algoritmo de desencriptado es
el mensaje original, "m". La encripción de clave

pública tiene muchas aplicaciones. La semana
pasada vimos la aplicación clásica, el

establecimiento de sesión, esto es, intercambio de
claves. Y por ahora vamos a limitarnos al intercambio de

claves que sea seguro sólo contra escucha. Y, si
recordáis cómo funciona el protocolo,

básicamente Alice, lo que ella hará es generar
un par de claves pública y privada.

Enviará la clave pública a Bob. Bob
generará un valor aleatorio "x", que

servirá como su secreto compartido y,
entonces, envía "x" encriptada a Alice,

encriptada con su clave pública [de Alice]. Alice puede
desencriptar, recuperar "x" y ahora ambos

disponen de este secreto compartido, "x", que
pueden utilizar para comunicarse de forma segura

entre ellos. El atacante, por supuesto, todo lo que
puede ver es la clave pública, la

encriptación de "x" con la clave pública, de la cual
no debería poder obtener ninguna

información sobre "x". Vamos a definir esto
de forma más precisa para entender

qué significa no ser capaz de averiguar nada
sobre "x". La criptografía pública,

de hecho, tiene muchas otras aplicaciones.
Por ejemplo, es muy útil en

aplicaciones no interactivas. Así, pensad en un
sistema de correo electrónico, por ejemplo. Aquí, Bob

quiere enviar correo a Alice y, cuando Bob
envía el correo, el correo pasa de

agente de transporte a agente de transporte hasta que
llega a Alice, momento en el que Alice deberá

desencrciptar. La forma en que el sistema de correo
está implementado está diseñada según una

configuración no interactiva en la que Bob envía
el correo y entonces Alice se supone que lo

recibirá. Y Alice no debería tener que comunicarse
con Bob a fin de desencriptar

el correo. Por tanto, en este caso, a causa de la
falta de interactividad, no existe la oportunidad

de establecer un secreto compartido entre Alice y
Bob. Por tanto, en este caso, lo que

ocurrirá es que Bob, básicamente, enviará
el correo encriptado utilizando la clave pública de

Alice. Del mismo modo que él envía el correo, cualquiera
en el mundo puede enviar el correo encriptado a

Alice, encriptado usando su clave pública [de Alice].
Cuando Alice recibe este correo, ella utiliza

su clave privada para desencriptar el texto cifrado y
recuperar el mensaje en texto llano.

Por supuesto, el inconveniente en un sistema como
éste es que, de hecho, Bob necesita, de algún modo,

obtener la clave pública de Alice. Así, por ahora, vamos
a asumir, simplemente, que Bob ya dispone

de la clave pública de Alice, pero más adelante,
cuando hablemos sobre firmas digitales,

veremos cómo se puede hacer esto de
forma muy eficiente utilizando lo que se

llama gestión de clave pública y, como ya he
dicho, volveremos a ello más adelante.

Lo más importante que quiero que recordéis es
que la criptografía de clave pública se

utiliza para establecer sesiones. Esto es muy
común en la web, donde la criptografía de

clave pública se utiliza para establecer una clave
segura entre un navegador web y un servidor web.

Y la criptografía de clave pública también es muy
útil para aplicaciones no interactivas,

en las que cualquiera en el mundo, de forma
no interactiva, necesita enviar un mensaje

a Alice, pudiendo encriptar el mensaje usando la
clave pública de Alice y Alice puede desencriptar

y recuperar el texto llano. Por tanto, permitidme que
os recuerde con algo más de detalle qué

es un sistema de criptografía de clave pública. Bien,
consiste en tres algoritmos, G, E y D.

G se denomina algoritmo de generación de
claves. Básicamente lo que hace es

generar este par de claves, la clave pública y la
clave privada. Tal como se indica aquí, G no usa

argumentos, pero en la vida real, G realmente usa
un argumento denominado el parámetro

de seguridad, que especifica el tamaño de las
claves que se generan con este algoritmo de

generación de claves. Luego está este algoritmo
de encriptación, como es habitual, que usa una

clave pública y un mensaje y genera un texto
cifrado, y un algoritmo de desencriptado que

usa la clave privada correspondiente y un
texto cifrado y genera el correspondiente

mensaje. Como siempre, para [la condición de]
consistencia, diremos que si encriptamos un mensaje

según una determinada clave pública y luego lo
desencriptamos con la clave privada correspondiente,

deberemos obtener de nuevo el mensaje original. Ahora,
¿qué significa para un sistema criptográfico de clave pública

que sea seguro? Voy a empezar definiendo
seguridad contra escucha

y luego definiremos la seguridad contra
ataques activos. La forma de

definir seguridad contra escucha es muy
similar a la del caso simétrico que hemos

visto la semana pasada, así que vamos a pasar
por ello rápidamente, sólo como repaso.

Básicamente, el juego de ataque se define como
sigue. Definimos estos dos experimentos,

experimento cero y experimento uno. En
cada experimento el retador generará

un par de claves pública y privada.
Le dará la clave pública

al adversario. El adversario emitirá
dos mensajes, m0 y m1 de la misma

longitud y lo que recibe es la
encripción de m0 o la

encripción de m1. En el experimento cero
obtiene la encripción de m0. En el experimento

uno obtiene la encripción de m1. Y entonces el
adversario se supone de debe indicar cuál

ha recibido, ¿Ha recibido la encripción de
m0 o ha recibido la encripción de m1? Así,

en este juego, el atacante sólo obtiene un
texto cifrado. Esto corresponde a un ataque

de escucha en el que se limita a "escuchar"
dicho texto cifrado "c". Y ahora

su objetivo es determinar si el texto cifrado "c"
es la encripción de m0 o m1. No se

permite manipular el texto cifrado "c" por ahora.
Y, como es costumbre, diremos que el

esquema de criptografía de clave pública es
semánticamente seguro si el atacante no puede

distinguir el experimento cero del experimento
uno. En otras palabras, no puede

diferenciar si recibió la encripción de m0
o la encripción de m1. Antes de pasar

a los ataques activos, quiero mencionar una
relación inmediata entre la definición que acabamos

de ver y la definición de seguridad de
escucha para cifrado simétrico.

Si lo recordáis, cuando hablamos sobre
seguridad de escucha para cifrado

simétrico, distinguíamos entre el caso en que la
clave se usaba una vez y el caso en que la

clave se usaba varias veces. Y, de hecho,
vimos que existe una clara

separación. Por ejemplo, el cuaderno de un solo
uso es seguro si la clave se usa para encriptar

un único mensaje, pero es completamente inseguro
si la clave se usa para encriptar múltiples

mensajes. Y, de hecho, teníamos dos definiciones
diferentes, si os acordáis, teníamos una

definición para seguridad de un solo uso y una
definición diferente, que era más

exigente, cuando la clave se usaba varias
veces. La definición que os he mostrado en

la transparencia anterior es muy similar a la
definición de seguridad de un solo uso para

cifras simétricas. Y, de hecho, resulta que para
la criptografía de clave pública, si un

sistema es seguro en el caso de un solo uso de la clave,
en cierto sentido, también es seguro para uso múltiple de

la clave. En otras palabras, no es necesario
proporcionar explícitamente al atacante la habilidad

para requerir encripciones de mensajes de su
elección, ya que puede crear encripciones

por si mismo. Dispone de la clave
pública y, por tanto, puede

por si mismo encriptar cualquier mensaje que desee.
Como resultado, cualquier par de claves pública y privada

de algún modo inherentemente se usan para
encriptar varios mensajes ya que el atacante

podría encriptar muchos, muchos mensajes
de su elección usando la clave

pública que le hemos proporcionado en el
primer paso. Y así, como resultado, de hecho

la definición de seguridad para un solo uso es
suficiente para implicar seguridad de varios usos y

es por ello que nos referimos al concepto como
indistinguibilidad bajo un ataque de

texto llano escogido. Así, este es sólo un punto menor
para explicar por qué en la configuración de criptografía

de clave pública no necesitamos una
definición más compleja para aprehender

la seguridad ante escucha. Ahora que
entendemos la seguridad ante escucha,

vamos a ver adversarios mas fuertes que pueden
montar ataques activos. Entonces, en

particular, veamos el ejemplo del correo electronico.
Así, aquí tenemos a nuestro amigo Bob

que quiere enviar enviar un correo a su amiga
Caroline. Y resulta que Caroline tiene una

cuenta en Gmail. Y esto funciona básicamente
así, el correo electrónico se envía encriptado al

servidor de Gmail. El servidor de Gmail desencripta
el correo electrónico, mira quienes son los

destinatarios y luego, si es que el
destinatario es Caroline,

reenvia el correo electrónico a Caroline.
Si el destinatario es el atacante, se

lo reenvia al atacante. Esto es similar a
cómo trabaja realmente Gmail,

porque el remitente enviaría el correo encriptado
sobre SSL al servidor Gmail,

el servidor Gmail terminaría [la sesión] SSL y
reenviaría el mensaje a los destinatarios

apropiados. Ahora supongamos que Bob
encripta el correo usando un sistema que

permita al adversario manipular el
texto cifrado sin ser detectado. Por

ejemplo, imaginad que el correo está
encriptado usando el modo contador o

similar. Entonces, cuando el atacante intercepta
este correo puede cambiar el destinatario

de forma que ahora el destinatario sea
[e-mail]. Y sabemos que, para el

modo contador, por ejemplo. esto es muy
fácil de hacer. El atacante sabe que el

correo está dirigido a Caroline, él está sólo
interesado en el cuerpo del correo. Por tanto, puede

fácilmente cambiar el destinatario del correo
a [e-mail] y ahora, cuando el servidor

recibe el correo, lo desencriptará, verá que
el destinatario se supone que es el

atacante y reenviará el cuerpo del mensaje al
atacante. Ahora el atacante ha podido

leer el cuerpo del mensaje que
estaba destinado a Caroline. Así,

este es un ejemplo clásico de ataque activo, y
podéis ver lo que el atacante ha conseguido:

puede desencriptar cualquier texto cifrado
en el que el destinatario sea "to:attacker",

esto es, un texto cifrado en el que el texto llano
empiece por "to:attacker". Así, nuestro objetivo es
empiece

diseñar sistemas de clave pública que sean
seguros incluso si el atacante puede manipular

el texto cifrado y, posiblemente, desencriptar
algunos textos cifrados. Y, de nuevo, quiero

enfatizar que aquí el objetivo del atacante es
obtener el cuerpo del mensaje. El atacante

ya sabía que el correo estaba destinado
a Caroline. Y todo lo que él tenía que hacer

era cambiar el destinatario. Así, este
ataque mediante manipulación motiva la

definición de seguridad de texto cifrado escogido.
y, de hecho, esta es la noción estándar de

seguridad para la criptografía de clave pública. Así,
permitidme explicaros cómo funciona el esquema del

ataque. Como ya dije, nuestro objetivo es construir
sistemas que sean seguros bajo esta noción tan

conservadora de encripción. Así, tenemos un
esquema de encripción G, E, D y digamos que

está definido sobre nuestro espacio de mensajes
y de textos cifrados M, C. Como es habitual, vamos

a definir dos experimentos, experimento cero y
experimento uno. Así, aquí "b" indica si

el retador está implementando el
experimento cero el el experimento

uno. El retador empieza generando una clave
pública y una clave privada y entonces proporciona

la clave privada al adversario. Ahora el adversario
puede decir "Bien, aquí hay un puñado de

textos cifrados, por favor desencríptalos por mí." Así
que el adversario envía el texto cifrado

c1 y obtiene la desencripción del
texto cifrado c1, esto es, m1. Y lo repite

una y otra vez, de forma que envía el
texto cifrado c2 y obtiene la desencripción,

que es m2, el texto cifrado c3 y lo obtiene
desencriptado, m3, y así en adelante.

Finalmente, el adversario dice: "Esta fase
de interrogación ha acabado" y ahora

remite básicamente dos mensajes de la misma
longitud, m0 y m1, como es habitual, y

recibe en respuesta el texto cifrado de
desafío, "c", que es la encriptación de m0 o

la encriptación de m1, dependiendo de si
estamos en el experimento cero o el

experimento uno. Ahora el adversario puede
continuar enviando solicitudes de texto

cifrado. Así, puede continuar remitiendo
solicitudes de desencriptado. Así, el remite

un texto cifrado y recibe el texto desencriptado,
pero, por supuesto, ahora tiene que haver una

limitación. Si el atacante pudiese solicitar textos
cifrados arbitrarios de su elección,

por supuesto que podría romper el desafío. Lo
único que tendría que hacer es remitir al

retador el texto cifrado "c" como una solicitud de
desencriptado y entonces se le diría si en la

fase de desafío se le ha dado la encriptación
de m0 o la encriptación de m1.

Como resultado, ponemos la siguiente limitación,
que dice que él puede de hecho enviar cualquier

texto cifrado de su elección, excepto el texto
cifrado del desafío. Así, el atacante

podrá solicitar el desencriptado de cualquier
texto cifrado de su elección que no sea el

texto cifrado del desafío. Y, a pesar de que se le hayan
dado todos esos textos desencriptados, a pesar de todo

no debería ser capaz de decir si ha
recibido la encriptación de m0 o la

encriptación de m1. Por tanto, daros cuenta de que
se trata de una definición muy conservadora. Proporciona

al atacante más poder del que vimos en la
transparencia anterior. En la transparencia anterior,

el atacante sólo podía desencriptar mensajes
si el texto llano empezada con "to:attacker".

Aquí, lo que vemos es que el atacante puede
desencriptar cualquier texto cifrado de su elección,

siempre se que sea distinto del texto cifrado del
desafío, "c". ¿De acuerdo? Y entonces su

objetivo es decir si el texto cifrado del
desafío es la encriptación de m0 o la

encriptación de m1. Y, como es habitual, si no
puede hacerlo, en otras palabras, su respuesta

ante el experimento cero es básicamente la
misma respuesta que en el experimento

uno, sin ser capaz de diferenciar la
encriptación de m0 de la encriptación de

m1 a pesar del poder del que disponía,
entonces decimos que el sistema es semánticamente

seguro frente a ataque de texto cifrado escogido,
seguro CCA. En ocasiones se utiliza este acrónimo,

el acrónimo de INDistinguible frente a un Ataque
de texto Cifrado esCogido [IND-CCA], pero me voy

a limitar a llamarlo "seguro CCA". Así, vamos a ver
como esto refleja el ejemplo con el correo electrónico

que vimos antes. Supongamos que el sistema de
encriptación usado es tal que simplemente dada

un mensaje encriptado el atacante puede
cambiar el destinatario, digamos, de Alice

a Charlie. Entonces, así es como él
ganaría el juego CCA. Bien, en el

primer paso recibe, por supuesto, la clave
pública. Y entonces el atacante lo que hará

es proporcionar dos mensajes de igual longitud,
esto es, en el primer mensaje el cuerpo contendrá

un cero. En el segundo mensaje el cuerpo contendrá
un uno. Pero ambos mensajes están dirigidos a

Alice. Y, en respuesta, él recibirá el
texto cifrado del desafío, "c".

Bien, así que ahora tenemos nuestro texto
cifrado del desafío, "c". Ahora, lo que hará el

atacante es utilizar su habilidad para
modificar el destinatario.

Y devolverá un texto cifrado c' [c prima]
en el que c' es la encriptación del

mensaje para Charlie con el cuerpo del
desafío, "b". Esto es, si os acordáis, o

cero o uno. Ahora, como que el
texto llano es diferente, sabemos que

el texto cifrado debe también ser diferente.
En particular, c' debe ser diferente del

texto del desafío "c", ¿no es así? Esto es,
c' debe ser diferente de "c". Y como

consecuencia, el pobre retador ahora tiene
que desencriptar, por definición del juego CCA.

El retador tiene que desencriptar cualquier texto
crifrado que no sea igual a un texto cifrado enviado

por el retador. Así, el retador desencripta, le
da al adversario m'. Básicamente proporciona

al adversario "b". Y ahora el adversario
puede mostrar "b" como resultado del desafío

y gana el juego con ventaja 1. Así, su
ventaja con este esquema particular

era uno. Simplemente porque el atacante
era capaz de cambiar el texto cifrado del

retador de un destinatario a otro, lo
que le permite ganar el juego CCA con

ventaja uno. Así, como ya dije, [el modelo] de
seguridad de texto cifrado escogido es en

realidad la noción de seguridad correcta para los
sistemas de criptografía de clave pública. Y este es

un concepto muy interesante. De algún modo,
aunque el atacante tenga la habilidad para

desencriptar todo lo que quiera, excepto el
texto cifrado del desafío, no es capaz de

conocer el texto cifrado del retador. Así, lo que haremos
lo que haremos durante lo que queda de este módulo y,

de hecho, también el próximo, es construir
sistemas seguros CCA. Se tiene que

destacar que es posible y voy a
mostraros exactamente cómo

hacerlo. Y, de hecho, los sistemas
seguros CCA que construiremos

son los que se utilizan en el mundo real.
Y cada vez que se ha intentado implementar un

sistema de criptografía de clave pública que no ha
sido seguro CCA, alguien ha encontrado un

ataque y ha sido capaz de romperlo. Y vamos
a ver algunos ejemplos de esos ataques

en unos pocos segmentos.