Interludio

Notas para una clase sobre Information Theoretical Crypto Emiliano Kargieman 2003

1

Interludio “When I use a word,” Humpty Dumpty said, in a rather scornful tone, “it means just what I choose it to mean - neither more nor less.” - Through the looking glass

El objetivo de este interludio es proveer de alg´ un contexto a los op´ usculos criptogr´aficos que componen este seminario. Dada la brevedad de espacio, es imprescindible resaltar el ’alg´ un’. Vamos a tocar algunos temas de la historia de la criptograf´ıa y algunas discusiones centrales al desarrollo de esta ciencia en los u ´ltimos a˜ nos. Vamos a intentar dar pistas sobre como se formalizan una cantidad de conceptos bastante elusivos en el marco de teorias que no podemos ni empezar a tratar, y en este sentido vamos a trabajar con algunas definiciones y presentar algunas demostraciones bajo la metodolog´ıa general conocida como ’hand-waving’ 1 . Espero que no se interpreten estas licencias formales como un signo de vagancia, sino como un atajo hacia la introducci´on de una variedad de conceptos interesantes.

1.1

Introducci´ on

Ron Rivest[], dijo alguna vez que “la criptolog´ıa2 se trata de estudiar la comunicaci´ on en presencia de adversarios”. De la misma manera podemos pensar que la seguridad en inform´atica, en un sentido m´as general, se trata del estudio de la computaci´on en presencia de adversarios. Hablamos de comunicaci´on y computaci´on, cuando nos gustar´ıa hablar de la transmisi´on y el procesamiento de la informaci´on. El problema es que la informaci´on es 1 Donde los pasos mas dificiles de las demostraciones en general son remplazados por vigorosos movimientos de brazos y gesticulaciones diversas. 2 Rivest dijo criptograf´ıa. Si bien puede parecer en un primer acercamiento que ’criptograf´ıa y criptolog´ıa son palabras intercambiables, y muchas veces son tratadas asi en la literatura, nosotros vamos a hacer una distinci´ on, que tambien es com´ un. Vamos a hablar de criptolog´ıa como una ciencia que tiene dos caras: la criptograf´ıa, la cara creadora, que se preocupa de encontrar metodos para transmitir mensajes de manera segura; y el criptoan´ alisis, la cara destructora, que se ocupa de buscar las falencias en esos metodos.

1

intangible, inasible.¿Que es la informaci´on? Hay muchas respuestas para esa pregunta, la mayor´ıa en el campo de la filosof´ıa. Gregory Bateson, un antropologo y fil´osofo americano, di´o una definici´on iluminadora. “Informaci´on es la diferencia que crea una diferencia”. Sutilmente la definici´on de Bateson nos habla de dos universos distintos: el de la diferencia original (el objeto percibido) y la diferencia que se crea en el sujeto que percibe. Para ser informaci´on, la diferencia original tiene que ser diferenciada por el sujeto y generarle una diferencia. ¿Una persona leyendo el mismo texto por segunda vez, se informa? Antes de perdernos en discusiones filos´oficas, recordemos la anecdota del marciano.

Anecdota 1 Un marciano llega a la tierra en su nave espacial del tama˜ no de una cacerola, con la idea de aprender todo lo posible sobre la raza humana. Se pasa varios a˜ nos realizando estudios (m´edicos, antropologicos, sociologicos, psicologicos, historicos, etc.) y anotando sus resultados en cuadernos de hojas oficio. Al mismo tiempo, recorre todas las bibliotecas y disquerias de la tierra y copia y fotocopia todo lo que le interesa. Hasta que llega el d´ıa en que tiene que irse a presentar su reporte final de vuelta a su planeta. El problema que tiene es que todo lo que junt´ o no entra en la cacerola voladora. La soluci´ on del marciano es la siguiente: escribe todo lo que se quiere llevar, una cosa atras de la otra, en un papiro muy largo. Despues, interpreta todo el contenido de ese papiro como un n´ umero en la base adecuada (si el marciano escribiera espa˜ nol, ser´ıa base 28), digamos M . Por u ´ltimo, agarra un escarbadientes y, llamando 1 al largo del escarbadientes, le hace una marca exactamente a distancia 0, M de una de las puntas y se va a su casa. Si encontraramos el escarbadientes, la marca (la diferencia) ser´ıa visible para nosotros, pero ¿Que aprender´ıamos de eso? Ah´ı encontramos el

1.2

Comunicaci´ on en presencia de adversarios

Los problemas que plantea la “comunicaci´ on en presencia de adversarios” son diversos, y por lo tanto son diversos los tipos de problemas que se plantea resolver la criptograf´ıa. Para nombrar solo algunos:

• Comunicaci´on entre dos sujetos, A y B, cuando el adversario (M ) tiene acceso al canal de comunicaci´on Confidencialidad (o privacidad). Se pretende que M no pueda conocer el contenido del mensaje siendo transmitido. Al adversario, le alcanza con tener acceso “de lectura” al canal de comunicaci´ on. Autenticidad. Se busca que el adversario, inclusive pudiendo insertar mensajes en el canal de comunicaci´ on, no pueda enviar un mensaje impersonando (“haciendose pasar”) por otra persona. Esta propiedad se puede describir de otra 2

manera, pidiendo que el receptor del mensaje tenga un mecanismo para verificar la identidad real del emisor. Integridad. Frente a la posibilidad de que existan canales de comunicaci´ on ruidosos, se busca que el receptor pueda verificar que el mensaje no fue alterado en transito. • Cuando el adversario es A o B! No-repudio. Se busca que el emisor del mensaje pueda demostrar, frente a terceros, que el mensaje fue recibido por el receptor (como en el caso de una carta certificada). Commitment (¿compromiso?). El equivalente electronico de guardar una carta en un sobre lacrado: se asume un compromiso sobre el contenido de la carta. Demostraci´on de conocimiento. A quiere convencer a B que conoce determinada informaci´on (por ejemplo el mecanismo de resoluci´on de un problema) sin que B aprenda la nada sobre la informaci´on original (por ejemplo, sin que B aprenda a resolver el problema). Simultaneidad. “Yo te muestro si vos me mostras”. A y B quieren transferirse informaci´on mutuamente, pero ning´ uno quiere ser el primero en hacerlo. Un caso donde esto se utiliza es en la firma de contratos, donde ninguna parte quiere firmar primero. Elecci´on. Ya vimos ’coin flipping’. Bueno, como elegir un bit al azar entre dos sin que ninguno pueda hacer trampa? oblivious transfer. A quiere mandarle cierta informaci´on a B de tal manera que no pueda saber si llego o no con certeza. • Entre mas de dos personas (Multiparty) Compartir un secreto. Se quiere repartir un secreto entre varias (m) personas, de tal manera que se necesite n de ellos para recuperarlo (n < m). Transacciones anonimas (e-cash). Dise˜ nar cheques electronicos que al mismo tiempo permitan saber si tienen respaldo y que sean an´onimos. Voto secreto. Otra aplicaci´on de anonimato, pero en este caso la importancia es que una persona no pueda votar dos veces y nadie se pueda hacer pasar por ella. • Entre mas de dos personas, con traidores Busqueda de traidores (traitor-traicing. Si se les env´ıa la misma informaci´on secreta a un grupo de personas, y la informaci´on se hace p´ ublica, ¿quien fue el traidor? Resistencia (resilliance). Se busca que distintos protocolos entre varias personas puedan seguir funcionando incluso si una cantidad de los participantes son traidores. 3

Estudiando estos problemas se fueron identificando objetos matem´aticos, abstracciones, que se repet´ıan frecuentemente y que se pueden usar para constru´ır las soluciones. A estos bloques de construcci´on se los llama primitivas. Algunas primitivas que vamos a ver son: sistemas de encripci´on simetricos, sistemas de encripci´on asimetricos, sistemas de firma, one-way hash functions.

1.3

Historia

Hist´oricamente, el primer problema que se identific´ o, fue el de la confidencialidad. Los primeros intentos de ocultar el contenido de un mensaje se basaron directamente en utilizar m´etodos de codificaci´on secretos. Se cuenta por ejemplo que Cesar, en la ´epoca romana, utilizaba un m´etodo de codificaci´on sencillo para la comunicaci´ on con sus tenientes: reemplazando cada letra del alfabeto por la treceava siguiente. Garantizar la confidencialidad de un mensaje ocultando, como en este caso, el mecanismo con el cual fue codificado, depende claramente de la posibilidad de mantener ese mecanismo secreto. El cifrado del Cesar es un ejemplo de lo que se conoce como un mecanismo de cifrado monoalfab´etico, ya que a cada letra del mensaje original le corresponde siempre la misma letra en el mensaje cifrado. Incluso suponiendo que uno decidiera no sumar siempre trece, sino otro n´ umero, ser´ıa muy sencillo para un atacante que tuviera a su disposici´on un texto cifrado, probar con todos los valores posibles (habiendo solo 28) y encontrar el n´ umero siendo sumado. Mas adelante, los sistemas de encripci´on comenzar´ıan a incorporar el concepto de clave, donde lo novedoso es que el m´etodo utilizado para codificar y decodificar puede hacerse p´ ublico y el mensaje ser inteligible unicamente para quien conoce una palabra o un n´ umero secretos. Los primeros sistemas de encripci´on con clave eran simples transformaciones afines, y eran suceptibles a una variedad de ataques. En particular, si el atacante conoc´ıa algunas caracter´ısticas de los mensajes siendo cifrados (por ejemplo, la distribuci´on de probabilidad de las distintas letras en el idioma en que el mensaje estaba escrito), pod´ıa construir ataques para recuperar el texto original e incluso descubrir la clave3 . 3

Como ejemplo, valga el siguiente fragmento de las “Memorias de Casanova”, cuando describe un episodio de su relaci´ on con Madame D’Urfe: “Paracelsus was her favourite author, and according to her he was neither man, woman, nor hermaphrodite, and had the misfortune to poison himself with an overdose of his panacea, or universal medicine. She showed me a short manuscript in French, where the great work was clearly explained. She told me that she did not keep it under lock and key, because it was written in a cypher, the secret of which was known only to herself. - You do not believe, then, in steganography. - No, sir, and if you would like it, I will give you this which has been copied from the original. - I accept it, madam, with all the more gratitude in that I know its worth.” [...] “ She firmly believed me to be an adept of the first order, making use of another name for purposes of my own; and five or six weeks later she was confirmed in this wild idea on her asking me if I had diciphered the manuscript which pretended to explain the Magnum Opus.

4

Para encontrar el siguiente salto ’evolut´ıvo’ tenemos que llegar hasta mediados del siglo XVI, y reparar en el trabajo del diplom´atico frances Vigen`ere4 . El sistema de cifrado de Vigen`ere sigue siendo una transformaci´on af´ın polialfab´etica (la misma letra del plaintext puede ser reemplazada por distintas letras en el ciphertext, dependiendo de su posici´on) y utiliza una clave de longitud variable. El tama˜ no variable de la clave dificulta la tarea de correlacionar la distribuci´on del texto plano con el texto cifrado y, durante un par de siglos, el sistema de Vigen`ere fue considerado inviolable. A mediados del 1800, un alem´an de nombre Friederich Kasiski, ser´ıa el primero en mostrar como se puede, a partir del texto cifrado y del conocimiento de la distribuci´on del texto plano, reconstruir la longitud de la clave y romper el sistema. Kasiski fundo su trabajo en ideas del inventor ingl´es Charles Babbage, buen amigo de Ada Lovelace y considerado por muchos como el abuelo de las computadoras a partir de sus trabajos en el Difference Engine y su Analytical machine. Esto es una coincidencia simp´atica dado que un siglo despues ser´ıa otro ingl´es, familiarizado con su trabajo, el padre de la computaci´on y uno de los primeros cript´ologos de la modernidad. Nos referimos, sin dudas, a Alan Turing. El origen de la criptograf´ıa es, hasta este momento, de un car´acter eminentemente pr´actico: surgida de las necesidades puntuales de situaciones de conflicto (guerras, espionaje). Sin desentonar, la genesis del per´ıodo te´orico (el nacimiento de la criptograf´ıa moderna) se sit´ ua tambien en un conflicto b´elico. Los avances en la tecnolog´ıa entrando en la segunda guerra mundial, la llegada de la radio y las maquinas mec´anicas de calcular sobre todo, dan lugar a una escalada t´ecnica en el per´ıodo de unos pocos a˜ nos. Los sistemas de encripci´on que se utilizaban segu´ıan siendo basados en transformaciones lineales, permutaciones y substituciones, a´ un que la mecanizaci´on de los algoritmos de cifrado y decifrado habia permitido aumentar la complejidad de los sistemas y dificultar los ataques manuales. Por otro lado, si antes era preciso interceptar a un mensajero para obtener un mensaje cifrado, ahora los mensajes pod´ıan ser literalmente - Yes -said I- I have deciphered it, and consequently read it, and I now beg to return it you with my word of honour that I have not made a copy; in fact, I found nothing in it that I did not know before. - Without the key you mean, but of course you could never find out that. - Shall I tell you the key? - Pray do so. I gave her the word, which belonged to no language that I know of, and the marchioness was quite thunderstruck. - This is too amazing -said she- I thought myself the sole possessor of that mysterious word, for I had never written it down, laying it up in my memory, and I am sure I have never told anyone of it. I might have informed her that the calculation which enabled me to decipher the manuscript furnished me also with the key, but the whim took me to tell her that a spirit had revealed it to me. This foolish tale completed my mastery over this truly learned and sensible woman on everything but her hobby. This false confidence gave me an immense ascendancy over Madame dUrfe, and I often abused my power over her.” 4 Blaise de Vigen`ere (1523-1596), se bas´ o para sus trabajos de criptograf´ıa en las obras del matem´ atico italiano Leon Battista Alberti (1404-), del alem´ an Johannes Trithemious (1492-)y del tambien italiano Giovanni Porta (1535-)

5

obtenidos del eter, lo que permiti´a conseguir una cantidad de mensajes cifrados varios ordenes de magnitud mas elevada y dise˜ nar ataques de correlaci´on que antes eran imposibles. Para llevar estos ataques a la pr´actica se dise˜ nan y construyen computadores cada vez mas potentes y, hacia fines de la guerra, el primer computador electr´onico universal. El per´ıodo esta lleno de an´ecdotas interesantes y es una t´esis generalmente aceptada que el accionar de los criptoanalistas ingleses de Bletchley Park, sobre todo el monitoreo de las comunicaciones entre los submarinos alemanes, fue fundamental para la victoria de los aliados. Los tipos de ataques que se realizaban en Bletchley Park, podr´ıan ser divididos en tres categor´ıas: • cyphertext-only. Donde, como en el caso de Casanova, los atacantes solo disponen de ejemplos del texto cifrado y un conocimiento general sobre la distribuci´on del espacio de mensajes. • known-plaintext. Junto con el texto cifrado, el atacante conoce partes del mensaje y su ubicaci´on. Por ejemplo, decifrando una carta, uno podr´ıa suponer que la misma empieza diciendo: “Estimado Sr. XXXXXX”. En el caso de las comunicaciones entre submarinos, habia un protocolo de mensajes que era conocido. • chosen-plaintext. De alguna manera, el atacante se las arregla para que el emisor encripte un texto elegido por ´el. Un ejemplo extraido de la segunda guerra mundial cuenta que se hac´ıan llegar, por medio de esp´ı as infiltrados, informaciones falsas pero veros´ımiles a conocidos espias alemanes con el fin de que fueran transmitidas cifradas. Este tipo de ataque es m´as poderoso que los anteriores, dado que puede explotar debilidades espec´ıficas de construcci´on de los mecanismos de encripci´on. Durante la segunda guerra mundial la criptolog´ıa comienza su etapa te´orica, gracias al aporte fundamental de dos cientificos ingleses: Claude Shannon y Alan Turing.

1.4

Sistemas de encripci´ on simetricos

Vamos a analizar, desde dos perspectivas, nuestra primer primitiva: los sistemas de encripci´on simetricos. 1.4.1

Teor´ıa de la informaci´ on

En 1948, con la publicaci´on de su trabajo “A mathematical theory of communication”[] Shannon funda lo que hoy conocemos como teor´ıa de la informaci´on. Al a˜ no siguiente, en “Communication theory of secrecy systems”[], articula por primera vez la idea de seguridad demostrable de un sistema de encripci´on. Ambos articulos estan fuertemente basados en sus trabajos como cript´ografo durante la segunda guerra, que fueron desclasificados reci´en en 1948. Como cript´ografo, y frente al c´ırculo vicioso existente de 6

“nuevos sistemas de encripci´on mas complicados” vs. “nuevos sistemas de criptoanalisis mas eficientes”, Shannon se pregunta si existe un sistema de encripci´on que pueda ser demostrablemente seguro. La teor´ıa de la informaci´on que estaba desarrollando, basada, como la estad´ıstica, en la teor´ıa de probabilidades, le ofrece un lenguaje singularmente apto para estudiar esta pregunta. Para ver la formulaci´ on de Shannon, necesitamos formalizar primero algunas cosas. Definici´ on 1 Un sistema de encripci´on es una 5-tupla hP, C, K, E, Di tal que: i) P, C y K son conjuntos finitos, donde P es el espacio del texto plano (o plaintext) C es el espacio del texto cifrado (o cyphertext) K es el espacio de claves (key space) ii) E = {Ek kk ∈ K} es una familia de funciones Ek : P → C que se usan para encriptar y D = {Dk kk ∈ K} es una familia de funciones Dk : C → P que se usan para desencriptar. iii) Para toda clave e ∈ K existe una clave d ∈ K tal que para todo p ∈ P: Dd (Ee (p)) = p. El sistema de encripci´on se dice sim´etrico si d = e. Cuando no haya lugar para confusi´ones, podremos referirnos a un sistema de encripci´on simplemente como el triplo hK, E, Di. Si Alicia y Bernardo se comunican usando un sistema de encripci´on sim´etrico hP, C, K, E, Di, y Eva (la atacante) tiene acceso al canal de comunicaci´ on inseguro por el que pasan los textos cifrados. El trabajo de Eva es, al ver un c ∈ C, intentar obtener informaci´on sobre el texto plano original p ∈ P. En orden, lo que sucede es: • A elige un texto plano p, distribuido en P de acuerdo a una distribuci´on de probabilidad PrP que puede ser dependiente del lenguaje. • A elige una clave k del espacio de claves K, de acuerdo a una distribuci´on de probabilidad PrK . A le comunica k a B a traves de un canal de comunicaci´ on seguro al que Eva no tiene acceso. • A calcula c = Ek (p) y se lo env´ıa a B por el canal de comunicaci´ on inseguro. • E ve el texto cifrado c e intenta adivinar el texto plano original (p). • para completar la comunicaci´ on, cuando B recibe c puede calcular p = Dk (c) PrP y PrK inducen una distribuci´on Pr = PrP×K en PrP×K tal que, para cada texto plano p y clave k, Pr(p, k) = Pr(p) Pr(k) P

7

K

es la probabilidad de que p sea encriptado con la clave k, donde ambas variables son independientes. Pr(p) = PrP (p) es la probabilidad de que el plaintext encriptado sea p, y Pr(k) = PrK (k) es la probabilidad de que la clave usada sea k. Sin perdida de generalidad podemos suponer que Pr(p) > 0∀p y que Pr(k) > 0∀k, descartando los valores que nunca son elegidos de P y K. Tomando c como otra variable aleatoria, su distribuci´on queda determinada por el sistema, y Pr(p | c) es la probabilidad de que p sea el texto cifrado con la condici´on de que E vi´o pasar c. En este contexto, definimos secreto de Shannon como: Definici´ on 2 Se dice que un sistema de encripci´ on hP, C, K, E, Di mantiene el secreto de Shannon si y solo si: (∀p ∈ P) (∀c ∈ C) [Pr(p | c) = Pr(p)] Intuitivamente, que un sistema de encripci´on mantenga el secreto de Shannon puede interpretarse como pedir que el atacante, al ver el texto cifrado, no obtenga ninguna informaci´on adicional sobre el mensaje original. Una formulaci´on de seguridad alternativa, que vamos a usar, es la de secreto perfecto. Definici´ on 3 Se dice que un sistema de encripci´ on hP, C, K, E, Di mantiene el secreto perfecto si y solo si: · ¸ (∀c ∈ C) (∀p1 , p2 ∈ P) Pr[Ek (p1 ) = c] = Pr[Ek (p2 )) = c] K

K

Que, modulo un cambio de notaci´on, podemos probar que es equivalente. Teorema 4 Un sistema de encripci´ on S cumple con secreto de Shannon ⇐⇒ cumple con secreto perfecto. Demostraci´ on: Dados p ∈ P y c ∈ C, notemos que Pr[Ek (p) = c] = Pr (c | p) = Pr(c | p) K

P×K

Ahora veamos las implicaciones. Secreto de Shannon ⇒ Secreto Perfecto. Por el teorema de Bayes sabemos que Pr(p | c) =

Pr(c | p) Pr(p) Pr(c) 8

(1)

y si Pr(p | c) = Pr(p), reemplazando tenemos que Pr(c) = Pr(c | p) ∀p y por lo tanto, para todos p1 , p2 ∈ P tenemos que Pr(c | p1 ) = Pr(c) = Pr(c | p2 ). Para ver que Secreto Perfecto ⇒ Secreto de Shannon alcanza con notar que: X X Pr(c) = Pr(c | q) Pr(q) = Pr(c | p) Pr(q) = Pr(c | p) q∈P

q∈P

y reemplazando en (1) obtenemos que Pr(p | c) = Pr(p) 2 Ambas definiciones de seguridad capturan el concepto intuitivo de lo que deber´ıa proveer un sistema de encripci´on, y se podr´ıa arguir algo sobre su elegancia. Lamentablemente, Shannon mismo ser´ıa el encargado de probar que el secreto perfecto solo es alcanzable en condiciones bastante impracticas. En primer lugar, tenemos el siguiente teorema. Teorema 5 La cota de Shannon. (Shannon [1949]) Sea S = hP, C, K, E, Di un sistema de encripci´ on que mantiene secreto de Shannon. Entonces, kKk ≥ kPk Demostraci´ on: La prueba es por el absurdo. Fijamos un c ∈ C y suponemos que existe un texto plano p ∈ P tal que para toda clave k ∈ K, p 6= Dk (c). Entonces, para ese p, Pr(p | c) = 0 < Pr(p) lo que contradice la hipotesis de secreto perfecto. Entonces vale que dado c, (∀p ∈ P) (∃k ∈ K) [p = Dk (c)] De donde se desprende que kKk ≥ kPk

2

Lo que nos dice la cota de Shannon es que para que haya secreto perfecto necesitamos, al menos, una clave tan larga como el mensaje que queramos cifrar. De modo mas general podemos probar el siguiente teorema. Teorema 6 (Shannon [1949]) Sea S = hP, C, K, E, Di un sistema de encripci´ on que cumple kCk = kKk. Entonces, S mantiene de Shannon si y solo si i) PrK es la distribuci´ on uniforme y, ii) para todo p ∈ P y para todo c ∈ C existe una u ´nica clave k ∈ K tal que Ek (p) = c. Demostraci´ on: ⇒) Para probar ii) procedemos por el absurdo. Fijemos un p ∈ P y supongamos que existe un texto cifrado c ∈ C tal que para todo k ∈ K, vale que Ek (p) 6= c. Entonces, Pr(p | c) = 0 < Pr(p) 9

y por lo tanto, S no mantendr´ıa secreto de Shannon. ® Por lo tanto, (∀c ∈ C) (∃k ∈ K) [Ek (p) = c] ´nica. Y como kCk = kKk, la clave es u Veamos ahora i). Fijamos un texto cifrado c ∈ C. Para p ∈ P, sea k(p) la u ´nica clave k que cumple Ek (p) = c. Entoces vale que Pr(c | p) = Pr(k(p)) y tenemos que , para todo p ∈ P: Pr(c | p) Pr(p) Pr(k(p)) Pr(p) Pr(p | c) = = (2) Pr(c) Pr(c) Ahora, como S mantiene secreto de Shannon, tenemos que Pr(p | c) = Pr(p) y si reemplazamos en (2) nos queda que Pr(k(p)) = Pr(c) independientemente de la elecci´on de p. Entonces, las probabilidades Pr(k) son iguales para todo k ∈ K y por lo tanto Pr(k) =

1 kKk

y entonces PrP es la distribuci´on uniforme. ⇐) Supongamos ahora que i) e ii) valen, vamos a mostrar que S mantiene secreto de Shannon. Sea k = k(p, c) la u ´nica clave que verifica que Ek (p) = c, entonces tenemos que: Pr(p | c) =

Pr(p) Pr(k(p, c)) Pr(p) Pr(c | p) Pr(p) Pr(c | p) =P =P Pr(c) q∈P Pr(q) Pr(c | q) q∈P Pr(q) Pr(k(q, c))

(3)

Ahora, como las claves son uniformemente distribu´ıdas, 1 kKk

Pr(k(p, c)) = y entonces,

X

P Pr(q) Pr(k(q, c)) =

q∈P

q∈P

Pr(q)

kKk

=

1 kKk

y substituyendo en (3) tenemos que Pr(p | c) = Pr(p). Entonces S mantiene el secreto de Shannon.

2

Existe un ejemplo de un sistema de encripci´on que mantiene secreto perfecto patentado en 1919 por Gilbert Vernam, conocido tambien con el nombre de one-time pad. Se construye de la siguiente manera: 10

• Sea P = C = K = {0, 1}n para algun n > 0 entero • Dado p ∈ P, k ∈ K se define Ek (p) = p ⊕ k. Donde ⊕ representa la suma modulo 2 bit a bit. Por lo tanto, Dk (c) = c ⊕ k Es facil ver que para todo p ∈ P y para todo c ∈ C existe una u ´nica clave k ∈ K tal que Ek (p) = c (sirve tomar k = p ⊕ c). Entonces, por el teorema de Shannon, el sistema de Vernam mantiene el secreto perfecto si la elecci´on de las claves es aleatoria5 . Uno de los problemas principales que tiene este sistema al ser implementado es, justamente, que se necesita que los dos extremos que quieren comunicarse tengan una clave secreta com´ un por cada mensaje que debe ser transmitido y del mismo largo. Esto lo hace poco pr´actico en muchas situaciones, sin embargo, gracias a la cota de Shannon, sabemos que este problema no puede ser solucionado si se quiere mantener el secreto perfecto. 1.4.2

Complejidad computacional

Tratando de relajar la definici´on de seguridad de Shannon, pero al mismo tiempo conseguir sistemas de encripci´on u ´tiles en la pr´actica, se inicia una de las ramas m´as fructiferas de la criptograf´ıa moderna: la relacionada con la complejidad computacional6 . Sinteticamente, lo que se busca en la criptograf´ıa basada en teor´ıa de la complejidad, es encontrar implementaciones de primitivas que, si bien no son demostrablemente seguras, puedan resistir el ataque de adversarios con poder computacional acotado. Con este f´ın se pueden utilizar distintos modelos de computaci´on, mientras no aclaremos lo contrario vamos a asumir que los algoritmos son ejecutados por m´aquinas de Turing con acceso a una cinta de valores aleatorios ω (en ingl´es random-tape). En este sentido, vamos a distinguir los algoritmos que acceden a ω con el nombre de probabil´ısticos o aleatorizados, y conservar para los algoritmos que no acceden a w el nombre de determin´ısticos. Como es usual, un algoritmo se dice polinomial si su tiempo de ejecuci´on es polinomial con respecto al tama˜ no de su entrada. Asi, para abreviar, llamamos PPT a un algoritmo probabil´ıstico polinomial. De ac´a en adelante, el plaint-text, el cypher-text y las claves van a ser conjuntos finitos de tiras de bits (P, C, K ⊂ {0, 1}∗ ), de tama˜ no polinomial sobre un par´ametro de seguridad s. Las funciones de encripci´on y desencripci´on son computadas por algoritmos. A los algoritmos de encripci´on y desencripci´on vamos a sumarles un algoritmo para generaci´on de claves, de la siguiente manera. 5

Cuando salimos del marco de las teor´ıas y tratamos de implementar uno de estos mecanismos de seguridad, solemos chocarnos con la realidad del mundo. ¿Existe un manera de elegir aleatoriamente aunque mas no sea entre un conjunto finito de valores? 6 De aca en adelante asumimos, de parte del lector, alg´ un conocimiento de teor´ıa de complejidad y modelos de computabilidad; de parte del mundo asumimos la t´esis de Church, informalmente, que todo algoritmo puede ser descripto por una maquina de Turing.

11

Definici´ on 7 Un sistema de encripci´on computacional con par´ ametro de seguridad s ∈ N es una 3-upla de algoritmos (G, E, D): • G es un algoritmo PPT que recibe como entrada el par´ ametro de seguridad 1s y devuelve una clave k ∈ K. Lo notamos de la siguiente manera: k ←- G(1s ). • E es un algoritmo PPT que recibe como entrada dos par´ ametros, k ∈ K y p ∈ P y devuelve un cyphertext c ∈ C. Notamos c ←- E(k, p). • D es un algoritmo determin´ıstico polinomial que recibe de entrada dos par´ ametros, k ∈ K y c ∈ C y devuelve un plaintext p ∈ P. Notamos p ←- D(k, c) • Pedimos que, dado k ∈ K, D(k, E(k, p)) = p (∀p ∈ P) Lo primero que necesitamos es un adversario. En la discusi´on de seguridad en el sentido de la teor´ıa de la informaci´on no definimos detalladamente quien era nuestro enemigo, ten´ıa a su disposici´on (en terminos computacionales) un poder infinito: pod´ıa computar cualquier proceso que pudiera definir instantaneamente y sin problemas de espacio. Ahora, justamente, nos preocupamos por definir con claridad los limites del atacante. Por ejemplo, dependiendo del contexto, vamos a hablar de la seguridad de un sistema contra “un atacante polinomial”, o “un atacante probabil´ıstico polinomial con acceso a un oraculo de desencripci´on” u otros trabalenguas semejantes con los querremos capturar las sutilezas del mundo real. Necesitamos nuestro par´ametro de seguridad s porque, principalmente, la teor´ıa de la complejidad trabaja con un concepto asint´ otico, es decir que querremos probar que a medida que s crece el trabajo del atacante se vuelve intratable. Es facil ver que el problema del atacante esta en NP, dado un sistema de encripci´on computacional y un known-plaintext, un atacante no-determin´ıstico puede siempre desencriptar un ciphertext en tiempo polinomial con el siguiente algoritmo: Input (c1 , p1 ), c2 Elegir de forma no-deterministica k∈K verificar si E(k, p1 ) = c1 If True Output: D(k, c2 ) Terminar aceptando Terminar rechazando

ventajas del no-determinismo

Por esto es que uno de los m´etodos m´as utilizados para fabricar nuevos mecanismos de encripci´on pr´acticos, consiste en tratar de plantearle al adversario problemas en NP. 12

Si resulta que P=NP7 , nada impide definir conceptos de seguridad pr´actica dentro de los limites de lo polinomial, ya que en el mundo real existen diferencias materiales entre un poder computacional de s3 y uno de s30 , y si hay algo que esta demostrado en el contexto del capitalismo es que nunca va a tener sentido gastar m´as plata en encontrar un secreto que lo que ese secreto vale. Volvamos a las cuestiones que nos ata˜ nen y vamos a definir una noci´on de seguridad para sistemas de encripci´on sim´etricos que es el equivalente computacional del secreto perfecto. Definici´ on 8 Decimos que una funci´ on g : N → R es negligible si, para todo c ∈ N −c existe un entero nc tal que |g(n)| ≤ n para todo n ≥ nc . Es decir, que una funci´on es negligible si se acerca a cero m´as r´apido que la reciproca de cualquier polinomio. Definici´ on 9 (Indistinguibilidad de mensajes) (IND) Sea S = (G, E, D) un sistema de encripci´ on con par´ ametro de seguridad s. Decimos que S es seguro en el sentido de indistinguibilidad si para todo PPT A existe una funci´ on negligible ² tal que: ¯ ¯ (∀p1 , p2 ∈ P) ¯ Pr[A(E(k, p1 )) = 1] − Pr[A(E(k, p2 ) = 1]¯ ≤ ²(s) Tomando la probabilidad sobre la elecci´ on de k ←- G(1s ), y los random-tapes de A y E renovados en cada ejecuci´ on. Es decir, un sistema de encripci´on se dice seguro en el sentido de indistinguibilidad si un adversario polinomial no puede distinguir con una probabilidad decente entre la encripci´on de dos mensajes distintos. A la funci´on ² se la llama tambien la ventaja de A. Si el adversario fuera no-acotado, y su ventaja fuera 0, tendriamos una definici´on equivalente a la de secreto perfecto. Hay otra noci´on de seguridad para sistemas de encripci´on sim´etricos que captura una intuici´on diferente, y es la de seguridad semantica. Definici´ on 10 (Seguridad sem´ antica) Un sistema de encripci´ on S = (G, E, D) con par´ ametro de seguridad s se dice sem´anticamente seguro si para toda distribuci´ on PrP deP, para toda funci´ on f : P → {0, 1}∗ , para todo adversario PPT A, existe una funci´ on negligible ² tal que: Pr[A(E(p)) = f (p)] ≤ max {Pr[f (p) = v]} + ²(s) v

Donde las probabilidades estan tomadas sobre PrP para la elecci´ on de p, k ←- G(1s ), y los random-tapes de A y E renovados en cada ejecuci´ on. 7

o que los avances en las computadoras cuanticas terminan por desformular la pregunta al estilo zen

13

Podemos pensar que seguridad sem´antica es la contraparte computacional del secreto de Shannon, por lo menos en el sentido en que trata de captar la intuici´ on de que “ver el ciphertext no ayuda a contestar preguntas sobre el plaintext”. Como en el caso de teor´ıa de la informaci´on, podemos relacionar los dos conceptos. Teorema 11 Un sistema de encripci´ on S = (G, E, D) con par´ ametro de seguridad s es indistinguible ⇐⇒ es semanticamente seguro. Demostraci´ on: Indistinguible ⇒) semanticamente seguro. Sea A cualquier adversario PPT, f : P → {0, 1}∗ cualquier funci´on. Fijo un p˜ ∈ P y quiero ver que, sobre una elecci´on aleatoria de p, k, ωA , ωB vale la desigualdad: Pr[A(Ek (p)) = f (p)] ≤ Pr[A(Ek (˜ p)) = f (p)] + neg(s)

(4)

Supongamos por un momento que no valiera, entonces existr´ıa un pˆ ∈ P tal que Pr[A(Ek (ˆ p)) = f (ˆ p)] > Pr[A(Ek (˜ p))¯ = f (ˆ p)] + δ con δ no-negligible. Entonces ¯ podemos ¯ constru´ır un algoritmo B tal que Pr[B(Ek (ˆ p)) = 1] − Pr[B(Ek (˜ p)) = 1]¯ > δ de la siguiente manera: Input c ejecutar A(c) If A(c) = f (ˆ p) Output: 1 Aceptar Else Output: 0 Aceptar End Algoritmo que distingue Ek (ˆ p) de Ek (˜ p)

Entonces vale la desigualdad (4) y nos alcanza con ver que Pr[A(Ek (˜ p)) = f (p)] ≤ max Pr[f (p) = v] v

(5)

vale ya que la elecci´on de p es independiente de p˜ y por lo tanto de A(Ek (˜ p)). Entonces, juntando (4) y (5) obtenemos lo que buscabamos: Pr[(A(Ek (p)) = f (p)] ≤ max Pr(f (p) = v) + neg(s) v

Sem´anticamente seguro ⇒) indistinguible. Vamos a probar que no indistinguible implica no sem´anticamente seguro. Supongamos que S no es indistinguible, entonces existen p1 , p2 tal que ¯ ¯ ¯ Pr[A(Ek (p1 )) = 1] − Pr[A(Ek (p2 )) = 1]¯ > δ(s) 14

sobre una tirada aleatoria de ωA , ωB y k ∈ K, con δ no negligible. Sin perder generalidad puedo suponer que Pr[A(Ek (p1 )) = 1] > Pr[A(Ek (p2 )) = 1] + δ(s)

(6)

Ahora construyo una funci´on f : P → {0, 1} tal que f (p) =

n1 0

si p = p1 sino

y fijo una distribuci´on PrP tal que Pr(p1 ) = Pr(p2 ) = 21 . entonces max{Pr[f (p) = v]} = max{Pr[f (p) = 1], Pr[f (p) = 0]} = {0,1}

1 2

1 1 Pr[A(Ek (p1 )) = 1] + Pr[A(Ek (p2 )) = 0] 2 2 1 1 > Pr[A(Ek (p2 )) = 1] + δ(s) + Pr[A(Ek (p2 )) = 0] 2 2 1 = + δ(s) 2

Pr[A(Ek (p)) = f (p)] = por (6)

2 Hasta ahora, las definiciones de seguridad que vimos, tratan de captar la intuici´ on de los ataques que tiene que resistir un sistema de encripci´on frente a un atacante con conocimiento de la distribuci´on del plaintext (el idioma?) y con acceso a mensajes encriptados. Esto capturar´ıa los ataques que conocemos con los nombres de cyphertext only y known-plaintext8 . Vamos a ver ahora una manera de definir indistinguibilidad frente a ataques del tipo chosen-plaintext. Nota 1 Sobre la notaci´ on. Vamos a introducir una notaci´ on particular para trabajar con algoritmos probabil´ısticos, espacios de probabilidad y experimentos. Si A es un algoritmo probabil´ıstico entonces, para entradas x, y, . . . la notaci´ on A(x, y, . . .) se va a referir al espacio de probabilidad determinado por la salida de A. Si S es un espacio de probabilidad, entonces x ←- S denota un algoritmo que a x le asigna un elemento aleatorio elegido de acuerdo a S. Dados espacios de probabilidad S, T, . . ., la notaci´ on Pr[x ←- S; y ←- T ; . . . : p(x, y, . . .)] denota la probabilidad de que el predicado p(x, y, . . .) sea verdadero despues de la ejecuci´ on, ordenada, de los algoritmos x ←- S, y ←- T , etc. 8

Las definiciones de seguridad que estamos viendo (sobre 1 mensaje) se pueden hacer extensiones para los casos de multiples mensajes, esto es necesario para definir ataques de known-plaintext de un modo mas intuitivo. De todos modos, si tomamos una distribuci´ on PrP de tal manera que Pr(p) > 0 si y solo si pref (p) = x para un x conocido por el adversario, donde pref (p) indica un prefijo de p, podemos modelar known-plaintext con estas definiciones.

15

Definici´ on 12 (Indistinguibilidad de mensajes frente a chosen-plaintext) (IND-CPA) Sea S = (G, E, D) un sistema de encripci´ on con par´ ametro de seguridad s. Llamamos un CP-adversario a una dupla (F, A) tal que A es cualquier PPT y F es un PPT que recibiendo de entrada 1s devuelve un par de elementos del plaintext p0 , p1 ∈ P. Decimos que S es seguro en el sentido de indistinguibilidad frente a chosen plaintext si para todo CP-adversario PPT (F, A) existe una funci´ on negligible ² tal que: Pr[k ←- G(1s ); (p0 , p1 ) ←- F (1s ); b ←- {0, 1}; c ←- E(k, pb ) : A(c, p0 , p1 ) = b] ≤

1 + ²(s) 2

donde b es un bit elegido uniformemente al azar entre 0 y 1. Esta divisi´on del adversario en dos algoritmos distintos nos permite diferenciar una etapa de setup de la etapa propia del ataque. Al permitirle al atacante elegir p0 y p1 , capturamos la idea de chosen-plaintext. Es facil ver que IND-CPA implica IND.

1.5 1.5.1

Funciones con trampa Revoluci´ on

En 1976, Whitfield Diffie y Martin Hellman publicaron un trabajo que marcar´ıa un antes y un despues en la criptograf´ıa moderna. Lo novedoso de “New directions in cryptography”, es sin duda el concepto de encripci´on de clave p´ ublica. Hasta el momento, todos los mecanismos de encripci´on con clave que se conoc´ıan requer´ıan que quienes se iban a comunicar tuvieran un canal de comunicaci´ on seguro para comunicarse una clave que se mantendr´ıa privada entre ellos. La habilidad de encriptar y de desencriptar un mensaje depend´ıa del conocimiento de esa clave. Diffie y Hellman mostrar´ıan por primera vez como establecer una comunicaci´ on encriptada entre dos personas sin que existiera previamente un secreto en com´ un. Definici´ on 13 Un generador de trapdoor permutations (permutaciones con trampa) es un algoritmo PPT G∗ que recibe una entrada 1s , donde s es un par´ ametro de seguri−1 dad, y produce como salida una 3-upla de algoritmos (f, f , d). Los primeros dos son determin´ısticos y d es probabil´ıstico. Se pide ademas que: • El soporte [d(1s )] de d sea un subconjunto de {0, 1}s . • f y f −1 computan permutaciones sobre [d(1s )], una la inversa de la otra. • Existe un polinomio p tal que f , f −1 y d son computables en tiempo p(s) • Por ultimo, se pide que exista una funci´ on negligible ² tal que para todo adversario PPT M Pr[(f, f −1 , d) ←- G∗ ; x ←- d(1s ); y ←- f (x) : M (f, d, y) = x] = ²(s) 16

Es decir, se pide que se pueda calcular f (x) en tiempo polinomial, pero que ningun algoritmo polinomial pueda encontrar una preimagen sin conocer f −1 . En particular, esto implica que ning´ un algoritmo polinomial puede calcular f −1 a partir de f . Quien −1 conoce f , conoce la “trampa” invertir f . Se dice tambien en este contexto que f es una one-way trapdoor permutation. Ya conocemos algunos ejemplos de candidatos a trapdoor permutations, como RSA, o sacar raices cuadradas modulo un n compuesto. Digo candidatos porque hay varias suposiciones en el medio, se supone que los problemas de fondo estan en NP y se supone que P 6= NP. Ademas, se suponen otras cosas, y este es un buen momento para hacer una nota sobre estas suposiciones (o assumptions). Nota 2 Assumtions Veamos el caso de RSA. Elegimos dos primos grandes p y q y calculamos n = pq. Ahora elegimos e y d tal que ed ≡ 1 mod φ(n). Ahora hacemos (e, n) p´ ublicos. De acuerdo a nuestra definici´ on de trapdoor functions, f (M ) = M e mod n y la clave privada (d) es la trampa que permite recuperar la preimagen. Se puede demostrar que si uno puede conseguir d a partir de (e, n) en tiempo polinomial, entonces uno puede factorizar n en tiempo polinomial. Esto, de todas maneras, no implica que romper RSA es tan dificil como factorizar, ya que podr´ıa existir un mecanismo para recuperar M sin necesidad de calcular d. La equivalencia de RSA con factorizaci´ on es todavia un problema abierto. La seguridad de RSA como trapdoor function esta basada en lo que se conoce como weak RSA assumption, es decir: dado un modulo n como el de arriba elegido al azar, un z ∈ Z∗n , y un r > 1, encontrar y tal que y r ≡ z mod n es dificil. Diffie y Hellman mostraron un protocolo para “intercambio de claves” entre dos personas. Cada uno elige un n´ umero al azar a y b. Se ponen de acuerdo de manera p´ ublica en un primo p y un generador g. Cada uno calcula y le envia al otro g a mod p y g b mod p. Ahora los dos pueden calcular un secreto compartido k = g ab mod p. Es facil ver que si un atacante puede calcular logaritmos modulo p, entonces puede averiguar k. La reciproca no esta demostrada. Que encontrar k a partir de los para´ ametros p´ ublicos es dificil es lo que se conoce como la Diffie-Hellman assumption (o DH). Una variaci´ on de este problema se conoce con el nombre de decisional DH (o DDH), donde la pregunta es: dado (g a , g b , g c ) un adversario puede decidir si c = ab o c esta elegido al azar. Esta claro que DH implica DDH, pero la reciproca no esta demostrada. Usar una one-way trapdoor function directamente para encriptar puede ser una muy mala idea. Por ejemplo, que dado f (x) sea dificil encontrar x no implica que sea dificil encontrar un prefijo de x (digamos, los primeros 5 bits), lo que claramente es una caracter´ıstica indeseable en un sistema de encripci´on. Existen, dependiendo de la trapdoor function, una variedad de ataques en estos casos. En RSA, por ejemplo, f (x1 x2 ) = f (x1 )f (x2 ), lo que puede traer muchos dolores de cabeza. Lo que si es cierto, es que cualquier one-way trapdoor permutation se puede usar para 17

construir un algoritmo de encripci´on asim´etrico (o de clave p´ ublica y privada) seguro. Veamos como. 1.5.2

Criptograf´ıa asim´ etrica demostrablemente segura

Definici´ on 14 Un algoritmo de encripci´ on asim´etrico (o de clave p´ ublica) esta definido por un PPT generador G que recibe de entrada un par´ ametro de seguridad 1s y genera un par de algoritmos probabil´ısticos (E, D) que corren en tiempo polinomial sobre s. • E recibe una entrada en P y la encripta a un elemento de C • D recibe una entrada en C y la desencripta a un elemento de P, de tal manera que D(E(x)) = x para todo x y D(y) = 0 si y no es la encripci´ on de ningun x. • Un usuario U corre G y hace p´ ublico E, manteniendo D privado. Para encriptar un mensaje x cualquiera puede ejecutar y ←- E(x) y enviarselo a U ; para desencriptar y el usuario U computa x ←- D(y). Podemos trasladar al contexto asim´etrico las definiciones de seguridad que teniamos para el caso sim´etrico. Veamos por ejemplo: Definici´ on 15 Dado un algoritmo de encripci´ on asim´etrico dado por su generador G. Llamamos un CP-adversario a una dupla (F, A) tal que A es cualquier PPT y F es un PPT que, recibiendo de entrada 1s y acceso al algoritmo de encripci´ on E, devuelve un par de elementos del plaintext p0 , p1 ∈ P. Decimos que G es seguro en el sentido de indistinguibilidad contra un ataque de chosen-plaintext (IND-CPA) si, para todo CP-adversario (F, A) existe una funci´ on negligible ² tal que: 1 Pr[(E, D) ←- G(1s ); (p0 , p1 ) ←- F (E); b ←- {0, 1}; α ←- E(pb ) : A(E, p0 , p1 , α) = b] ≤ +²(s) 2 Hay una cantidad de maneras de construir algoritmos de encripci´on a partir de trapdoor permutations, los que son demostrablemente seguros son, en general, bastante poco pr´acticos. Nosotros vamos a ver una construcci´on de Bellare y Rogaway que se asume la existencia de un generador de random. Definici´ on 16 Sea G : {0, 1}∗ → {0, 1}∞ un generador de random y G∗ un generador de trapdoor permutations. Definimos el sistema de encripci´ on asim´etrico B-R a como un algoritmo G que: • En entrada 1s , ejecuta (f, f −1 , d) ←- G∗ • genera el algoritmo E con acceso a G tal que en entrada x devuelve f (r)||G(r)⊕x para alg´ un r en el dominio de f . E G (x) = hr ←- d(1s ) : f (r)||G(r) ⊕ xi 18

• genera el algoritmo de desencripci´ on DG (ys) = s ⊕ G(f −1 (y)) Teorema 17 Si existe una colecci´ on de trapdoor permutations y un generador de random el esquema de encripci´ on asim´etrico B-R es seguro bajo IND-CPA. Demostraci´ on: 2 1.5.3

otras nociones de seguridad

Chosen ciphertext attack (IND-CCA) (IND-CCA2) Non Malleability (NM-CPA) (NMCCA) (NM-CCA2)

19