Introducción a la Criptografía Moderna CC5301 (2019/01)

Profesor: Alejandro Hevia

Propósito del Curso: Estudiar el fascinante mundo de la Criptografía :-)

Resultados de Aprendizaje: Al finalizar el curso el alumno será capaz de:

• Razonar matemáticamente acerca de la seguridad de algoritmos criptográficos tanto del tipo simétrico (clave privada) como del tipo asimétrico (clave pública).
• Modelar y analizar formalmente algoritmos criptográficos basados en cifradores de bloque, funciones de hash y primitivas basadas en teoría de números, entre otros.
• Evaluar soluciones criptográficas para problemas prácticos (confidencialidad, autentificación) presentes en redes de computadores.

Aspectos administrativos:

Cátedra: Lunes y Miércoles 10:15am-11:45am, Sala F22
Auxiliar: Viernes 10:15am-11:45am, Sala F22
Sitio web oficial (especialmente el Foro de Discusión): ucursos
Carga académica: 10 UD,
Requisitos: CC3001, CC3102, (MA3403 / MA4701/ Autorización)
Carácter del curso: electivo Cs. de la Computación

Temario

1. Elementos Básicos:
1. Introducción y conceptos básicos: objetivo de seguridad (privacidad, autentificación), adversarios, recursos. Seguridad demostrable como una reducción.
2. Criptografía Clásica (cifrados de sustitución y variantes, ataques). One-time pad y seguridad perfecta, limitaciones.
2. Criptografía Simétrica (Clave Privada):
1. Cifradores de Bloque: Modelos, construcciones (DES, AES)
2. Funciones Pseudo-aleatorias
3. Encriptación Simétrica: Modelos de seguridad, construcciones basadas en cifradores de bloque
4. Funciones unidireccionales y resistentes a colisiones: potenciales candidatos (MD5, SHA-1, SHA-256, SHA-3, otros), modelos de seguridad, el ataque de los cumpleaños
5. Autentificación de Mensajes: modelos y construcciones (CBC-MAC, HMAC, PMAC, UMAC, y otros)
6. Encriptación autentificada
7. Mecanismos de Encapsulamientode Claves (KEM)
3. Criptografía Asimétrica (Clave Pública):
1. Teoría de Números Computacional
2. Primitivas basadas en teoría de números
3. Encriptación Asimétrica
4. Firmas Digitales
4. Criptografía en la Práctica:
1. Infraestructura de Clave Pública (PKI)
2. Acuerdo de Claves Diffie-Hellman, y SSL/TLS
3. Bitcoin y Criptomonedas
4. Problemas al implementar algoritmos criptográficos
5. Tópicos Avanzados (si el tiempo lo permite)
1. Mecanismos para compartir secretos (Secret Sharing)
2. Generación de bits pseudo-aleatorios, aleatoriedad verificable.
3. Introducción a demostraciones interactivas y protocolos de Nula Divulgación (Zero Knowledge)
4. Criptografía Umbral: Aplicación votación electrónica, y Mixnets, Computación Multi-partita Segura.

Se recomienda suplementar el material de cátedra con los siguientes libros:

• [KL] Introduction to Modern Cryptography J. Katz and Y. Lindell. Disponible en biblioteca.
Disponible en biblioteca. Ver también su errata.
• [BR] Introduction to Cryptography, Lecture Notes, University of California San Diego, 2006. Por Mihir Bellare y Phil Rogaway. Disponible en U-Cursos en dos versiones del curso (2015) para pregrado [BR-pre], y de [BR-post]) Se recomienda revisar ambos.
• [SB] A Graduate Course in Cryptography V. Shoup and D. Boneh.

• Clase 1, Lu 11/03
  Introducción a la Criptografía.
• Clase 2, Mi 13/03
  Criptografía clásica. Lecturas recomendadas: [BR] cap. 1, [KL] Capítulo 1 (sec. 1.2,1.3,1.4).
• Clase 3, Mie 18/03
  Confidencialidad Perfecta Lecturas recomendadas: [BR] cap. 2 (Sec. 2.2)
  [KL] Cap. 2 (Sec. 2.1,2.2,2.3 y 2.4.)

Evaluación:

La evaluación se basa en un control, un proyecto y un exámen (con apuntes) más varias (entre 3 y 4) tareas cortas.

El Proyecto

1. Desarrollo teórico de un sistema criptográfico (con seguridad demostrable) para algún problema propuesto por el estudiante o el profesor,
2. Diseño o implementación de un ataque criptoanalítico reciente, o de un software criptográfico novedoso.
3. Escritura y presentación de un artículo corto tipo estado del arte, discusión de artículo reciente, o investigación en algún tema relativo al curso.

1. Entrega de propuesta de proyecto
   Viernes 22 de Marzo, 23:59hrs, vía ucursos.
   Consiste en una página web o documento (PDF) explicando el proyecto, su importancia/motivación, objetivos concretos y tiempos.
   Porcentaje de la nota de proyecto: 10 por ciento
2. Entrega del proyecto
   Se realiza en dos partes. La primera es vía ucursos; debe entregar un reporte escrito (en LaTeX o similar), y código fuente (si es necesario) o lo que estime necesario para evaluar el trabajo. La segunda parte es presencial: la entrega se realizará en una sesión especial donde deberá presentar al curso su proyecto, via una presentación y/o demo.
   Porcentaje de la nota de proyecto: 90 por ciento

Reporte Final:

El reporte final del proyecto, de ser escrito, debe estar escrito en el computador (ojalá en LaTeX, nunca manuscrito). La claridad y calidad de la exposición son fundamentales en la nota. En particular, sea claro, conciso y convincente. Explique las motivaciones del trabajo, su metodologóa, resultados, trabajo previo y conclusiones. En caso de requerirlo, use lenguaje matemático en forma correcta. Intente hacerlo comprensible para una audiencia más o menos general, al menos para sus compañeros del curso. Venda y defienda su idea y/o trabajo!

Recomendaciones:

• Su proyecto debe ser al menos entretenido para Ud. e interesante para otros. Algo valioso, "vendible", y factible de hacer en un semestre.
• NO funciona: tratar de adivinar lo que el profesor considera un buen proyecto, que no me guste pero igual intente hacerlo. O pensar que el proyecto es sólo para aprender o comprender la materia.
• SI funciona: encuentre algo que a Ud. le gustaría hacer y convenza al profesor que vale la pena hacerlo. Piense que el propósito del proyecto es crear, criticar, informar, hacer, sorprender, mejorar el mundo, o hacer algo conceptualmente bello.
• Trabajo grupal: se recomienda escoja con cuidado a su compañero(a) de grupo. Se espera que un grupo de dos personas entregue algo mejor que un estudiante trabajando solo.

Sugerencias Generales para Proyecto:

• Aplicaciones: plugin de encriptación o firma para gmail (firma de anillo? o de grupo?); lo mismo para facebook. Casino online. Aplicación móvil para firma de grupo. Aplicaciones para usar/estudiar certificate transparency. Aplicaciones para usar/estudiar blockchains (varios tipos). Otros ejemplos
  • Survey (estado del arte) en téecnicas y aplicaciones de private data mining, una implementación de un caso especial simple
  • Survey en Criptografía Post-cuántica: qué es, principales algoritmos. Implementar uno en un contexto nuevo (nuevo lenguaje, mejor API)
  • Survey en técnicas y aplicaciones de encriptación buscable o encriptación determinista o encriptación funcional o encriptación que preserva el orden o encriptación que preserva el formato. Implementación de un caso particular o mejora de una implementacióm existente.
• Primitivas: Proponer nuevas nociones (definiciones) de seguridad para problemas novedosos. Relacion con nociones existentes.
  • Definición formal (por ej. usando indistinguibilidad) de un foro anónimo
  • Definición formal (por ej. usando indistinguibilidad) de un protocolo donde dos partes (un vendedor y un comprador, donde el primero tiene un precio mínimo de venta, y el segundo tiene un precio máximo de compra) pueden acordar un precio de venta sin revelar sus precios máximos.
• Sistemas: Variantes/plugins para Bitlocker, FileVault, Truecrypt/Veracrypt; librerías para almacenar/comunicar información encriptada entre varios para móviles; Análisis del protocolo de autentificación SQRL. Sistema para compartir un archivo encriptado grande (GBs) en forma segura pero que sea simple para el receptor (clave comunicada por mensajerí móvil).
• Ataques: Implementacion de variantes de ataques sobre WEP, SSL (DROWN, CRIME, POODLE, Lucky13, BEAST, FREAK, Logjam, HEIST, NOMORE, Sweet-32,Robot(Return of Bleichenbacher's Oracle Attack)).
• Estándares: Analizar/implementar algoritmos propuestos para la competencia CAESAR o para la competencia de Password Hashing. Revisar/implementar nuevos RFC (6955, 6979, etc.) y formalizar sus objetivos criptográficos.
• Implementaciones interesantes: Implementar nuevos algoritmos (propuestos en conferencias de cripto en los últimos 2-3 años) o algoritmos conocidos en nuevas plataformas (en forma eficiente!).
• Educacional: Videos, herramientas educacionales, o juegos en temas de criptografía.

Propuestas Concretas:

• Investigar y evaluar la seguridad del sistema de encriptación y autentificación del sistema de base de datos MONGO.
• Investigar la operación (algoritmos concretos) y evaluar la seguridad de los esquemas de generación pseudo-aleatoria (PRNG, Pseudo-Random Number Generator) usados en los principales navegadores.
• Hacer un tutorial/video educativo sobre como funciona la criptografía de Curvas Elípticas: en qué consiste, algoritmos para calculos, seguridad y ataques recientes, etc.
• Hacer tutorial/video explicativo/resumen sobre como opera la máquina Enigma, y variantes y ataques.
• Hacer un resumen anotado de la historia de los principales (unos 6-7?) cifradores en la historia, su surgimiento (nuevas ideas), su análisis, y sus posteriores ataques. Debiera incluir: ejemplos de Cifradores monoalfabeticos, polialfabeticos, Enigma, DES, AES, encriptacion autenticada.
• Hacer tutorial/video explicativo/resumen sobre como opera y ataques de sistemas de Single-Sign-On, como Kerberos.
• Hacer tutorial con estado del arte sobre encriptación autenticada.
• Una aplicación/implementaci&oacue;n para usar/visualizar/ estudiar los certificados publicados en el proyecto de certificate transparency.
• Una aplicación/implementaci&oacue;n para usar/visualizar/ estudiar alguna blockchain interesante (y cuyo visualizador no exista).
• Dar una definición formal (por ej. usando indistinguibilidad) de un foro anónimo. Debe incluir una propuesta inicial de un prototipo de sistema (cómo funcionaría, qué primitivas usaría) (sindemostración).
• Dar una definición formal (por ej. usando indistinguibilidad) de un protocolo donde dos participantes (un vendedor y un comprador, donde el primero tiene un precio mínimo de venta, y el segundo tiene un precio máximo de compra) pueden acordar un precio de venta sin revelar sus precios máximos. Debe incluir una propuesta inicial de un prototipo de sistema (sindemostración).
• Implementar un esquema eficiente de firmas transitivas de grafos (referencia, (presentación).

Ejemplos Años Pasados: Nota: Se incluyen solo como referencia; en ningun caso se aceptará que su proyecto sea similar a alguno de estos.

• Implementación de un algoritmo de firma post-quantica
• Calculadora criptográfica: debe permitir ingresar números p y n, donde el primero es un primo (verificar) si ya compuesto, y luego calcular suma, multiplicación, etc. en GF(2^m). Debe calcular inversos, generadores en grupos cíclicos (mod p), así como cálculos simples en enteros mod p, raíces cuadradas mod p. También debe poder testear si un entero es residuo cuadrático (mod p o mod n) o no.
• Reimplementación del ataque basado en factores comunes en los módulos RSA de clave públicas de empresas que hacen factura electrónica o que tienen en certificados emitidos por autoridades certificadoras locales. Se denomina ataque de módulos de RSA. El paper original describe el ataque en detalle. Más info acá.
• Implementación de prueba de concepto para vulnerabilidad DROWN: Breaking TLS using SSLv2.
• Implementación de prueba de concepto de esquema de encriptación homomórfico Boneh-Goh-Nissim.
• Implementación de ataque Breaking RSA-based PIN Encryption, de N.P. Smart.
• Survey y estado del arte de fully homomorphic encryption.

Tareas

Notas y situación final

• NC = (C1+NProyecto + Ex)/3
• NT = (NT1+.. +NTn)/n
• NF = 0,7*NC + 0,3*NT

• NC≥4.0
• NProyecto ≥ 4.0
• NT ≥ 4.0

Bibliografía:

1. Mihir Bellare y Phil Rogaway, “Introduction to Cryptography, Lecture Notes”, University of California San Diego, 2006. (En ucursos, disponible transparencias de versiones del curso para pregrado, y de postgrado) Se recomienda revisar ambos.
2. J. Katz and Y. Lindell. Introduction to Modern Cryptography, Chapman & Hall/CRC Press, 2007. Disponible en biblioteca. Ver la errata y la sec. 4.6.3 revisada.
3. A Graduate Course in Cryptography V. Shoup and D. Boneh, 2017. Disponible online gratis.
4. Cryptography, An Introduction N. Smart, 2013. Disponible online gratis.
5. A Computational Introduction to Number Theory and Algebra, V. Shoup, 2008.
Disponible online gratis.
6. J. Katz, Digital Signatures, Springer, 2010
7. Douglas Stinson, “Cryptography, Theory and Practice”, Second edition, Editorial Cgapman and Hall/CRC, 2002
8. Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, “Handbook of Applied Cryptography”, CRC press, 1997. Disponible online.

Última modificación: 22 de Marzo 2019.