Introducción a la Criptografía Moderna CC5301 (2016/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, autentificacioĢn) presentes en redes de computadores.

Aspectos administrativos:

Cátedra: Lunes y Miércoles 10:15am-11:45am, Sala N01
Auxiliar: Viernes 10:15am-11:45am, Sala N01
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. Problemas al implementar algoritmos criptográficos
    3. Acuerdo de Claves: Diffie-Hellman y intercambio de claves autentificado (AKE).
    4. Canales seguros (SSL/TLS)
  5. Tópicos Avanzados (si el tiempo lo permite)
    1. Mecanismos para compartir secretos (Secret Sharing)
    2. Generación de bits pseudo-aleatorios
    3. Introducción a demostraciones interactivas y protocolos de Nula Divulgación (Zero Knowledge)
    4. Criptografía Umbral. aplicación a DNSSEC y votación electrónica, Mixnets y/o DCnets.
    5. Introducción a protocolos criptográficos genéricos (Computación Multi-partita Segura).

Material de lectura del curso

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

Sin embargo, los textos anteriores pueden no cubrir toda la materia discutida en clases.

Calendario de clases y lecturas del curso

 En esta sección, actualizaremos el contenido a cubrir en cada clase así como sus lecturas asociadas.
  • Clase 1, Mi 9/03
    Introducción a la Criptografía.
    Lectura complementaria: capítulos 1 y 2 de [BR-pre] (Introducción y Criptografía clásica). Capítulos 1 y 2 del libro de KL
  • Clase 2, Lu 11/03
    Cifradores clásicos y su criptoanálisis
    Cap. 2 de [BR-pre] y Sec. 1.2,1.3,1.4 del libro de KL
  • Clase 3, Mie 13/03
    Confidencialidad Perfecta (Parte I).
    KL Sec. 2.1,2.2.
  • Clase 4, Lu 21/03
    Confidencialidad Perfecta (Parte II), Enfoque de la Criptografía Moderna.
    KL Sec. 2.1,2.2,2.3,2.4,1.4
  • Clase 5, Mie 23/03
    Reducciones. Cifradores de Bloque y DES (parte I)
    Cap. 3.1, 3.2,3.3 de [BR-pre] y KL Sec. 5.2,5.3
  • Clase 6, Lu 28/03
    DES (Parte II), 2DES (y ataque MITM),3DES, AES
    Cap. 3.4,3.6 de [BR-pre] y KL Sec. 5.4,5.6
  • Clase 7, Mie 30/03
    AES. Introducción Funciones Aleatorias y Pseudoaleatorias (PRF).
    Cap. 3.5 4.1,4.2,4.3 de [BR-pre], y KL Sec. 5.5,3.6.1
  • Clase 8, Lu 4/04
    Funciones Pseudoaleatorias (PRF), candidatos y ataques.
    Cap. 4.3,4.6 de [BR-pre] y KL Sec. 3.6.1
  • Clase 9, Mie 6/04
    Seguridad PRF, cota inferior: el ataque de los cumpleaños.
    Cap. 4.8 de [BR-pre].
  • Clase 10, Lu 11/04
    PRF implica KR, noción de seguridad PRP.
    Cap. 4.6,4.4.1 de [BR-pre].
  • Clase 11, Mie 13/04
    Seguridad de encriptacion sim´trica: IND-CPA. Inseguridad de ECB.
    Cap. 5.1,5.2,5.3,5.4.1,5.5.1,5.5.2 y KL Sec. 3.1,3.2,3.5
  • Clase 12, Mie 20/04
    Inseguridad de CBCC, Seguridad de CTRC.
    Cap. 5.5.3,5.7,5.7.1 y KL Sec. 3.1,3.2,3.5
  • Clase 13, Lu 25/04
    Seguridad de CBC$ y CTR$, Seguridad IND-CCA.
    Cap. 5.8, 5.7.2,5.7.3,5.9,5.10 y KL Sec. 3.1,3.2,3.5

Tareas

 Aquí se publicarán detalles de las tareas del curso.
  • Tarea 1: fecha entrega Mi\'ercoles 4 de Mayo, 23:59hrs. Disponible en ucursos.

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

El proyecto es desarrollado durante el semestre, en grupos de a lo más dos personas. Puede ser teórico, de implementación o de ambos. Posibles alternativas para el proyecto incluyen
  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.
Plazos:
  1. Entrega de propuesta de proyecto
    Lunes 4 de Abril, 10AM, vía ucursos.
    Consiste en una página web o documento (PDF) explicando el proyecto, su importancia/motivación, objetivos concreto 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 entregare el reporte, código fuente, etc. respectivo. La segunda parte es presencial: en esa misma fecha debe solicitar una entrevista con el profesor entre el 20 y el 24 de Junio.
    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.

Ideas: (algunas cortesía de Mihir Bellare)

  • Aplicaciones: plugin de encriptación o firma para gmail (firma de anillo? o de grupo?); lo mismo para facebook. Casino online. Variantes de Bitcoin.
  • Primitivas: Proponer nuevas nociones (definiciones) de seguridad para problemas novedosos. Relacion con nociones existentes.
  • Sistemas: Variantes/plugins para Bitlocker, FileVault, Truecrypt; aplicaciones para iPhone o Android; variantes, mejoras o ataques de OTR y mensajería segura (Signal, Telegraph, Wickr). Estudio/análisis/implementación de TLS 1.3. Análisis de SQRL.
  • Ataques: Implementacion de variantes de ataques sobre WEP, SSL (DROWN, POODLE, BEAST, FREAK).
  • 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.

Tareas

Las tareas consistirán en demostraciones y resolución de problemas principalmente teóricos.

Nota Magister y Doctorado: La opción (3.) arriba es la alternativa sugerida para estudiantes de Magister o Doctorado tomando el curso. Dependiendo del caso y del alcance del proyecto, estudiantes de postgrado podrán convalidar la nota del proyecto como nota simultánea de proyecto y tareas. Tal convalidación debe ser aprobada por el profesor al momento de presentar el tema del proyecto.

Notas y situación final

Dada la nota de control C1, notas de las n>=3 tareas T1,T2,..,Tn, la nota del proyecto NProyecto, y la nota del examen Ex, la ponderación será la siguiente:
  • NC = (C1+NProyecto + EX)/3
  • NT = (NT1+.. +NTn)/n
  • NF = 0,7*NC + 0,3*NT
El examen no reemplazaró la nota de control (C1). Para aprobar el curso se requiere:
  • 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. (Disponible en 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.
    4. Disponible online gratis.
  4. Cryptography, An Introduction N. Smart
    5. Disponible online gratis.
  5. J. Katz, Digital Signatures, Springer, 2010
  6. Douglas Stinson, “Cryptography, Theory and Practice”, Second edition, Editorial Cgapman and Hall/CRC, 2002
  7. Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, “Handbook of Applied Cryptography”, CRC press, 1997. Disponible gratis!.
  8. Oded Goldreich, “Foundations of Cryptography, Basic Tools”, Cambridge University Press, 2001
  9. Oded Goldreich, “Foundations of Cryptography, Basic Applications”, Cambridge University Press, 2004
  10. Josef Pieprzyk, Thomas Hardjono, Jennifer Seberry, “Foundamentals of Computer Security”, Springer, 2003

Última modificación: 11 de Marzo 2016.