Me dieron una paliza

No tengo memoria de la última vez que me fue tan mal en una prueba. Tampoco recuerdo haberme sentido tan perdido que ni siquiera entendía lo que me estaban preguntando. Creo que la última vez que me pasó fue en las pruebas de elctromagnetismo, cuando me hizo clases mi amigo Tito Torres. Que catástrofe, di la prueba correspondiente a la primera semana del curso de criptografía y me saqué 3.37 de un máximo de 8.75, es decir como un 39%, muy lejos del 70% que necesitaría para que me den el certificado.

En fin, puedo dar tres intentos más para el mismo módulo, pero ya empezaron las clases de la segunda semana y estoy como si me viniera persiguiendo una locomotora a toda velocidad. El curso era mucho más complicado de lo que suponía, el profesor habla en inglés como ametralladora y no es fácil seguirlo y las pruebas, lamentablemente, tienen poco que ver con el contenido del curso, son las típicas preguntas de "ingenio" para las que yo soy negado, lo que menos tengo es ingenio.

En fin, aprovecharé de comentarles en resumen y sin matemáticas lo que vimos la semana pasada. Todo partió muy fácil revisando aplicaciones de la criptografía, como la comunicación web segura (HTTPS, Secure Socket Layer), la encriptación de archivos en un disco y cosas así.

Después vimos las funciones primitivas básicas para encriptación simétrica, que el algoritmo debe ser público y todo eso. También vimos que hay claves que se usan una sola vez y se descartan, mientras que otras veces se hacen varias encriptaciones usando la misma clave. Y eso de que la criptografía no soluciona todos los problemas de seguridad, sino que es parte de la seguridad.

Luego vimos algunas aplicaciones como la firma digital, la comunicación anónima, el dinero digital anónimo, conteo de votos anónimo en elecciones, determinar el ganador en subastas, consultas anónimas, etc. La criptografía es la ciencia del ocultamiento. Todo eso fue la introducción y no tenía nada muy nuevo ni especial.

Luego empezamos con la criptografía como una ciencia rigurosa y vimos los tres pasos para hacer un sistema encriptado:

1.-Especificar precisamente (matemáticamente) el modelo de amenaza
2.-Proponer una construcción (matemática)
3-Probar (matemáticamente) que para romper la construcción con el modelo de amenaza se necesita resolver un problema muy complicado

Lo primero en esto es el modelo de cifradores simétricos donde Bob y Alice (típicos) comparten la misma clave, uno para encriptar y otro para desncriptar, vimos las funciones primitivas que caracterizan al modelo simétrico.

Después hubo una clase interesante sobre historia de la criptografía explicando como funcionaban los distintos sistemas, todos basados en la idea de sustitución, cambiar una letra por otra según cierto algoritmo o clave. Desde las sustituciones más sencillas como el reordenamiento de las letras, hasta las sustituciones más complicadas como la máquina "Enigma" de la segunda Guerra Mundial, todos esos cifrados son facilícimos de romper usando computadores y estadística.

Cuando se rompió el código de la máquina Enigma se estaban empezando a usar computadores, eso terminó la era de la criptografía clásica y dio paso a la moderna con el genial paper de Claude Shannon en 1948 sobre el secreto perfecto, que dio origen a la teoría de la información y un montón de otras cosas. El secreto perfecto según Shannon, es cuando no existe forma matemática de obtener información de un texto a través de su versión encriptada.

Sahnnon demostró matemáticamente que existe a lo menos una forma de obtener el secreto perfecto y es un algoritmo muy simple que se llama "one-time-pad", pero luego de eso publicó su teorema "bad news": la única forma matemáticamente posible de lograr el secreto perfecto es usando claves del mismo tamaño o mayores que la información que vamos a intercambiar. Esto hace al one-time-pad bastante inútil en la práctica.

O sea, existe el secreto perfecto, pero sujeto a restricciones: que la clave sea igual de grande que la información que vamos a encripar y que jamás se encripten dos mensajes distintos con la misma clave. El one-time-pad es sencillísimo porque consiste solo en hacer una operación lógica (xor) entre la información y la clave, bit a bit, pero si tenemos dos textos diferentes encriptados con la misma clave es cosa de niños obtener la clave, haciendo (xor) entre ambos textos.

Con la llegada de los computadores nos olvidamos de las letras y de las señales: todo se pasa a bit (0 o 1) y toda la criptografía se hace con bits, por eso se debe usar lo que se llama "estadística discreta" es decir que opera con conjuntos finitos de dimensión conocida, típicamente del tipo (0,1) elevado a n. Por ejemplo un universo U=(0,1)^2 tendría 4 elementos (00,01,10,00) que son todas las combinaciones que se pueden hacer con 2 bits.

La estadística discreta estudia las distribuciones de probabilidades en combinaciones de variables que pueden tener 2 estados. Por ejemplo un conjunto (a, b, c,...etc.) donde a, b, c, etc. pueden tener valores como (0010, 1010, 0100...) en este caso son variables de 4 bits. Lo que se estudia entonces es con que probabilidad se distribuyen los valores, cuando y donde se repiten. La suma de todas las probabilidades dentro del conjunto universo debe dar uno.

Hay infinitas distribuciones posibles, pero dos son las más interesantes. La primera es la distribución puntual donde la probabilidad uno se encuentra en una sola posición y todas las demás tienen probabilidad cero. Pero la otra es la más importante y se llama distribución uniforme, donde todos los elementos tienen exactamente la misma probabilidad de aparecer.

Por ejemplo el conjunto (00,01,10,11) las probabilidades de aparecer de cada elemento son (0.25, 0.25, 0.25, 0.25) respectivamente ¡es uniforme!. Para un universo de cinco elementos conjunto (00,00,00,01,00) tendría una distribución puntual (0,0,0,1,0) etc. Esto es sencillo cuando podemos contar pero se complica para conjuntos enormes o que ni sabemos cuantos elementos tienen. Sin embargo para esos también hay forma de estudiar sus distribuciones.

En fin, ya sabemos que el one-time-pad es bonito y sencillo, pero no tiene aplicación práctica porque necesita claves enormes ¿que hacer entonces? La solución son los generadores de claves seudo-aleatorios (PRG), que consisten en entrar una pequeña "semilla" aleatoria (nuestra clave secreta) y con un algoritmo expandirla hasta el gran tamaño que necesitamos.

Y aquí empiezan los grandes problemas ¿como generar una clave grande y realmente aleatoria? La calidad del algoritmo PRG es fundamental para la seguridad, desde ya podemos despedirnos del secreto perfecto y tenemos que buscar otras definiciones como seguridad semántica.

Uno de los problemas es ¿que significa que una secuencia sea aleatoria? Que sea impredictible, que teniendo cualquier valor sea imposible predecir el valor siguiente. Eso es imposible de saber con seguridad pero hay herramientas matemáticas (heuristicas) que pueden hacer buenas conjeturas. Para probar el azar existen las pruebas estadísticas, hay cientos de ellas con distintos criterios.

Por ejemplo, uno puede cojeturar que en un grupo grande, si es al azar, debe haber más o menos la misma cantidad de unos y ceros, porque la probabilidad en una distribución uniforme es la misma para todos, pero ¿basta con eso?. Claro que no, hay millones de distribuciones con igual número de 1 y 0 que son fácilmente predecibles: imaginemos una por ejemplo donde la primer mitad sean puros unos y la segunda puros ceros. U otra donde los unos y ceros se alternen en grupos regulares, o cualquier otra donde una secuencia tenga alguna relación con la anterior.

El azar perfecto, que parece tan sencillo e intuitivo es bastante difícil de conseguir y mucho más de formalizar y probar que en el milmillonésimo bit no va a aparecer una secuencia. En fin, esa es una parte importante donde se concentran los ataques a estos cifradores y hay una serie de enredos realcionados como la ventaja, pruebas estadísticas, probabilidades y cosas por el estilo.

Luego el curso revisa varios sistemas de cifrado que ya están rotos pero se siguen usando, mostrando como funcionan y cual es la debilidad. Muestra por qué es tán fácil romper las claves WEP de la Wifi, como se rompe la encriptación de DVDs que también se usa en los celulares GSM y en el Bluetooth, también revisa cifradores modernos y hasta ahora seguros como Salsa20 y cierra volviendo al tema de la seguridad teórica y la ventaja, con experimentos imaginarios más enredados que un paquete de virutillas.

Todo esto es para cifradores de flujo (stream ciphers) que consisten en encriptar un chorizo de bits de largo variable. En esta semana empezamos con los cifradores de bloque, a ver si con estos tengo mejor suerte. Mejor me pongo a estudiar de nuevo.