filippo.io/mlkem768: criptografía resistente a la computación cuántica para el ecosistema Go

 (words.filippo.io)
1 puntos por GN⁺ 2024-02-02 | 1 comentarios | Compartir por WhatsApp
  • filippo.io/mlkem768 implementa ML-KEM-768, actualmente en proceso de estandarización por NIST, en Go puro, lo que permite evaluar intercambio de claves resistente a la computación cuántica dentro del ecosistema Go
  • Está compuesto por alrededor de 500 líneas de código, 200 líneas de comentarios y 650 líneas de pruebas, y no tiene dependencias aparte de golang.org/x/crypto/sha3, por lo que es fácil de incorporar como paquete interno en la biblioteca estándar de Go
  • En lugar de portar la implementación de referencia de pq-crystals, fue escrito directamente siguiendo la especificación FIPS 203, para verificar si es posible lograr una implementación interoperable usando solo la especificación
  • Las áreas más complicadas son la compresión/descompresión y las operaciones en tiempo constante; usa Barrett reduction para evitar el riesgo de instrucciones DIV de tiempo variable que podían aparecer en la familia de implementaciones de referencia
  • Aunque la optimización de rendimiento no era el objetivo principal, la ruta de Bob es comparable a X25519 y P-256 en Go, y la de Alice se mantiene por debajo del doble, mostrando velocidades viables para uso real incluso con una implementación simple

Implementación de ML-KEM-768 en Go puro

  • filippo.io/mlkem768 es una implementación en Go puro de ML-KEM-768, con prioridad en corrección y legibilidad
  • ML-KEM, antes conocido como Kyber, es un mecanismo de intercambio de claves resistente a la computación cuántica que está en proceso de estandarización por NIST
  • El paquete está compuesto por unas 500 líneas de código, 200 líneas de comentarios y 650 líneas de pruebas
  • Su única dependencia es golang.org/x/crypto/sha3
  • El objetivo es llevarlo upstream a la biblioteca estándar de Go, inicialmente como un paquete interno usado en un experimento opt-in de crypto/tls

Un enfoque de implementación que sigue FIPS 203 al pie de la letra

  • Esta implementación no porta la biblioteca de referencia pq-crystals, sino que fue escrita desde cero sin leer a fondo otras bases de código
  • El objetivo principal era comprobar si se podía crear una implementación interoperable solo a partir de la especificación
  • El documento FIPS 203 ofrece pseudocódigo detallado, definiciones completas e información de tipos consistente, por lo que resultó adecuado como guía de implementación
  • Los nombres de funciones, variables y el orden de operaciones reflejan la especificación FIPS lo más posible para facilitar la revisión y el aprendizaje
  • La base matemática necesaria para implementar ML-KEM se explica por separado en Enough Polynomials and Linear Algebra to Implement Kyber

Compresión/descompresión e implementación en tiempo constante

  • Quedaban tres tareas principales de implementación
    • Implementar aritmética modular sobre el primo 3329
    • Implementar funciones de compresión/descompresión que mapean valores de [0, 3329) a [0, 2ᵈ) y viceversa
    • Garantizar operaciones en tiempo constante
  • La aritmética modular fue relativamente sencilla gracias a la experiencia acumulada en implementaciones de RSA y curvas elípticas, y el primo pequeño ayudó a simplificarla
  • La parte más difícil fue la compresión y descompresión
    • La especificación las define de forma abstracta mediante fracciones y reglas de redondeo
    • La implementación real debe resolverse con aritmética en tiempo constante y operaciones de bits
  • La implementación de referencia y muchas de sus variantes portadas usaban divisiones que, según la optimización del compilador y la plataforma, podían convertirse en instrucciones DIV de tiempo variable
  • Este paquete usó desde el inicio Barrett reduction, por lo que no se vio afectado, y BoringSSL emplea el mismo enfoque

Por qué se enfoca solo en ML-KEM-768

  • La implementación apunta únicamente a ML-KEM-768 entre los tres niveles de seguridad de ML-KEM: -512, -768 y -1024
  • El equipo de Kyber recomienda -768 en lugar de -512 por un margen de seguridad más conservador frente a nuevos criptoanálisis
  • -1024 se presenta como una opción por las mismas razones que un nivel de seguridad de 256 bits: cumplimiento normativo y ajuste de fortaleza (strength matching)
  • Como la mayoría de los protocolos en experimentación o estandarización convergen en ML-KEM-768, enfocarse en un solo nivel casi no aumenta el costo
  • Apuntar a un solo objetivo reduce las partes móviles y favorece la legibilidad, la seguridad y el rendimiento
    • Por ejemplo, en lugar de manejar la serialización de enteros de 1, 4, 10 y 12 bits con un codificador genérico, se separan en codificadores/decodificadores dedicados
    • Al enfocarse solo en ML-KEM-768, no fue necesario implementar codificación de 5 ni de 11 bits

Estrategia de pruebas y vectores de prueba públicos

  • Las pruebas son, después de la legibilidad, el pilar más importante de la estrategia de seguridad de este paquete
  • Las pruebas básicas incluyen recorridos completos de generación de claves, encapsulación y desencapsulación, además de más de 95% de cobertura de pruebas
  • El alcance adicional de las pruebas incluye lo siguiente
    • Verificación de interoperabilidad con vectores de prueba obtenidos de NIST y de otras implementaciones
    • Comparación de todas las combinaciones de entrada para suma, resta y multiplicación módulo 3329 contra valores esperados calculados de forma no constante en tiempo
    • Pruebas exhaustivas de compresión/descompresión tomando como referencia math/big.Rat
    • Verificación de que las constantes precalculadas coincidan con sus definiciones
    • Confirmación de que todas las funciones produzcan errores adecuados cuando la longitud de la entrada es demasiado corta o demasiado larga
    • Ejecución de vectores de prueba proporcionados por Sophie Schmieg que en el futuro se incluirán en Wycheproof
  • Sus propios vectores de prueba se publican como parte del proyecto CCTV para que también puedan reutilizarse en otras implementaciones
  • Los vectores de CCTV incluyen valores intermedios para probar y depurar cada paso intermedio y subalgoritmo

Errores que detectan los vectores de prueba especiales

  • Los negative test vectors entregan claves de encapsulación inválidas con coeficientes mayores que 3329
    • Los vectores del equipo de Kyber y de NIST se centran en entradas válidas, por lo que este tipo de vectores se pedía con frecuencia
    • Se prueba por separado cada valor desde 3329 hasta 2¹²-1 y cada posición de coeficiente
    • Al compartir el resto de los coeficientes, se comprimen datos de 1–3MiB hasta 12–28KiB
  • Los vectores “unlucky” prueban casos donde se requiere una cantidad anormalmente alta de lecturas XOF
    • Son claves públicas en las que SampleNTT necesita leer al menos 575 bytes desde el XOF SHAKE-128, algo que normalmente ocurre con probabilidad 2⁻³⁸
    • Los vectores de Sophie fueron forzados aún más por fuerza bruta y requieren hasta 591 bytes
  • Los strcmp vectors hacen fallar implementaciones que usan strcmp() en ML-KEM.Decaps
    • Si hay bytes cero al comparar el ciphertext con la salida de K-PKE.Encrypt durante la desencapsulación, strcmp() puede terminar la comparación antes de tiempo
  • Los accumulated vectors derivan de la implementación de referencia de pq-crystals
    • En lugar de guardar 300MB de salidas aleatorias, se regeneran durante la prueba con un RNG determinista y luego se compara su hash con el valor esperado
    • También permiten generar hashes de 1 millón de pruebas aleatorias, superando las 10k de la implementación de referencia
  • En varias pruebas agregadas después de finalizar el trabajo no se encontraron problemas en filippo.io/mlkem768, y existe al menos un caso reportado en el que los negative vectors detectaron defectos en implementaciones importantes

Resultados de rendimiento

  • El rendimiento no es el objetivo principal de este paquete ni de los paquetes criptográficos de Go, pero sí debe ser suficientemente rápido para resultar útil
  • ML-KEM es lo bastante rápido, y esta implementación simple ya compite con las implementaciones de P-256 y X25519 de Go optimizadas en ensamblador
  • La comparación debe hacerse según el trabajo total que cada parte realiza durante el establecimiento de claves
    • ECDH realiza dos multiplicaciones escalares, incluyendo una con punto base fijo
    • KEM hace que un lado ejecute generación de claves y desencapsulación, y el otro lado encapsulación
    • ECDH es simétrico, pero el establecimiento de claves de ML-KEM es asimétrico
  • En los benchmarks, “Alice” realiza generación de claves y desencapsulación, mientras que “Bob” realiza encapsulación
    • La desencapsulación incluye una encriptación completa para verificar que el ciphertext de entrada coincida con el resultado
    • Alice tarda más que Bob porque ejecuta encriptación, desencriptación y generación de claves
  • En consecuencia, Bob es tan rápido como X25519 o P-256, y Alice tarda menos del doble
  • Frente a implementaciones rápidas de ML-KEM como BoringSSL y libcrux, este paquete tarda aproximadamente el doble

Cifras de benchmark y margen de optimización

  • Las cifras medidas son las siguientes
    • En macOS arm64, ECDH/P256-8 tarda 49.43µs y ECDH/X25519-8 tarda 77.46µs
    • En el mismo entorno, RoundTrip/Alice-8 tarda 109.4µs y RoundTrip/Bob-8 tarda 56.19µs
    • En Linux amd64, ECDH/P256-4 tarda 78.88µs y ECDH/X25519-4 tarda 115.6µs
    • En el mismo entorno, RoundTrip/Alice-4 tarda 223.8µs y RoundTrip/Bob-4 tarda 114.7µs
  • La implementación sigue patrones de Go de alto rendimiento, como reducir las asignaciones en heap
  • Se rehizo x/crypto/sha3 para poder usarlo sin asignaciones en heap, pero como tuvo un efecto negativo en Apple M2, todavía no se ha fusionado y no está incluido en los benchmarks anteriores
  • El margen de optimización que queda es claro
    • Como la generación de claves y la desencapsulación muestrean la matriz a partir del mismo valor, si en el lado de Alice se almacena la matriz cuando ambas operaciones se ejecutan seguidas, se puede ahorrar alrededor de 10% de tiempo
    • Hay posibilidad de reducir copias en la ruta de lectura de sha3
    • Después de eso, sería necesario optimizar la implementación del campo

Dar soporte a Kyber v3 con una implementación de ML-KEM

  • NIST hizo algunos cambios menores a la propuesta de Kyber Round 3, resumidos en la sección 1.3 del borrador FIPS
  • Existen algunos protocolos experimentales basados en Kyber v3 o “draft00”, incluido el principal intercambio de claves PQ TLS desplegado
  • Es posible dar soporte a Kyber v3 con una implementación de ML-KEM sin necesidad de un paquete separado
  • Uno de los cambios agrega validación para el caso excepcional de codificación no canónica de coeficientes en la clave pública
    • Una implementación correcta no generaría esas claves, así que se pueden rechazar siguiendo el borrador FIPS
    • Este comportamiento hace que una implementación de Kyber sobre ML-KEM sea identificable, pero fuera de eso no causa problemas
  • Otro cambio elimina la etapa de hash que se aplicaba a la entrada del CSPRNG
    • Como los bytes de entrada son aleatorios, ninguna de las partes puede distinguir la diferencia
  • El cambio más grande fue aplicar hash al ciphertext dentro del secreto compartido
    • Esa diferencia puede impedir la interoperabilidad
    • Si se genera el secreto compartido K con ML-KEM y luego se aplica SHAKE-256(K || SHA3-256(c))[:32], se puede obtener el secreto compartido de Kyber
    • No hace falta romper la abstracción de ML-KEM
  • Tanto Kyber como ML-KEM hacen hash del secreto y del ciphertext para la implicit rejection durante la desencapsulación
    • Si se aplica esa derivación de clave sobre ML-KEM, el ciphertext se hashea dos veces durante la implicit rejection
    • Como la salida de implicit rejection es impredecible por diseño y no forma parte de la interoperabilidad, esto no representa un problema

Lecturas relacionadas

1 comentarios

 
GN⁺ 2024-02-02
Opiniones en Hacker News

  • Saludos desde Kudelski Security. Es muy oportuno, porque recientemente tuvimos que descontinuar casi la única otra biblioteca de criptografía resistente a la computación cuántica para Go que existía
    La historia completa está en https://research.kudelskisecurity.com/2024/02/01/the-kybersl...

    • ¿No era que Kyber-512 había sido debilitado deliberadamente por los miembros del lado de la NSA en NIST?

  • Me pregunto qué tan lejos llegó realmente la computación cuántica como para que algo así sea necesario
    ¿Es una situación en la que, como con la IA, más que haber aparecido algo real, simplemente cambió la definición para lanzar productos nuevos bajo un nombre existente?

    • La criptografía trata la amenaza de las computadoras cuánticas de una forma particular. Porque algunos datos y conexiones cifrados hoy no deberían poder descifrarse ni siquiera dentro de 30 o 50 años
      Por eso la pregunta no es “¿vienen pronto las computadoras cuánticas?”, sino “¿pueden aparecer de forma plausible computadoras cuánticas en el próximo medio siglo?”. No hay un consenso preciso, pero la respuesta no es “no”, y por eso ahora existe esta tendencia
      Por eso se ve más avance en el intercambio de claves PQC que en las firmas. La verificación de una firma de hoy no se ve afectada por una computadora cuántica dentro de 50 años, pero el cifrado sí
    • No se trata de bloquear las computadoras cuánticas actuales
      El riesgo es que un atacante guarde los textos cifrados de hoy y pueda descifrarlos en el futuro. Mientras antes migremos a criptografía segura frente a lo cuántico, menos “textos cifrados acumulados” dejaremos vulnerables a ataques futuros
    • Si la respuesta fuera “la NSA ya está ejecutando criptoanálisis cuántico en producción y hay que considerar ECDH completamente roto”, quien lo sepa se metería en un problema enorme en el momento en que lo diga
      En realidad parece poco probable, pero esta pregunta es hasta cierto punto difícil de responder. Por ahora no es una amenaza conocida, pero qué tan paranoico ser respecto de su potencial es algo subjetivo
    • En los últimos dos años aproximadamente, NIST definió algunos algoritmos de criptografía poscuántica, y desde entonces las implementaciones han ido aumentando. La computación cuántica todavía está lejos, pero la actitud parece ser “¿qué tiene de malo empezar ahora?”
      No lo sé con certeza, pero supongo que la criptografía de curvas elípticas también ya tenía bastantes implementaciones mucho antes de usarse masivamente. Si alguien que vivió esa época sabe que estoy equivocado, que me corrija
    • Para que una computadora cuántica rompa RSA-2048, la calidad de los cúbits físicos actuales tendría que aumentar aproximadamente 10 veces, y la cantidad unas 10.000 veces. Son números muy aproximados
      El siguiente hito importante a observar es un cúbit lógico con una fidelidad 1000 veces mejor que la de los cúbits físicos que lo componen. Si eso aparece, será una señal de que la calidad de los cúbits físicos ya es suficiente y de que solo queda empezar a escalar la cantidad

  • Para esta discusión, puede ser útil la introducción de John Arundel a la implementación de sistemas criptográficos basada en la versión más reciente de Go. En la última sección se menciona brevemente la criptografía poscuántica, y cuando NIST PQ se estandarice, tal vez John actualice el libro incorporando esta biblioteca
    Explore Go: Cryptography (edición Go 1.22):
    https://bitfieldconsulting.com/books/crypto

  • Corríjanme si me equivoco, pero si está escrito en Go puro, ¿no lo vuelve vulnerable a ataques de canal lateral por tiempo/consumo de energía?

    • Es difícil decir que Go sea más vulnerable que C; incluso podría ser menos. La diferencia es que Go tiene un compilador principal y normalmente no hace optimizaciones excesivas, mientras que en C hay que usar trucos cada vez más complejos para impedir que el compilador detecte la intención y la convierta en una rama de tiempo variable más eficiente
      Esta implementación está escrita para evitar rutas de código que dependan de valores secretos. Los canales laterales de consumo de energía, que requieren acceso físico, quedan fuera del modelo de amenazas de Go
    • Dice que “todas las operaciones centrales se realizan en tiempo constante”
      Debí haber seguido los enlaces hasta la documentación del proyecto; parece que están teniendo en cuenta esta parte
    • ¿Hay algún lenguaje inmune a los ataques de canal lateral por consumo de energía? La idea en sí no parece tener sentido
      En cuanto a los ataques de timing, no veo por qué Go sería más vulnerable a canales laterales de tiempo que otros lenguajes

  • ¿Alguien conoce implementaciones para otros lenguajes como Java o C#?

  • Es genial que también pueda funcionar con draft00/kyber v3
    ¿Qué tan difícil sería soportar el modo Kyber 90’s rápido sin SHA-3? Probablemente en ese caso habría que romper la abstracción

    • Para cambiar el hash hace falta un fork. Esta implementación usa solo alrededor del 20% del tiempo de CPU en SHA-3, así que la ganancia no sería grande
      Si se optimiza la implementación del campo, esa proporción subiría, pero casi seguro no lo suficiente como para que valga la pena usar un modo no estandarizado y menos probado

  • No tiene relación, pero Filo, la tabla de llamadas al sistema de 32 bits sigue diciendo ‘coming soon’ :')

    • Jaja, lo admito. Cada vez que pienso en arreglar esa página, el alcance sigue creciendo, tipo “mejor hagamos que se genere automáticamente desde el código fuente del kernel con CI”, y por eso pasa :)

  • No tengo la capacidad de evaluar la calidad de este algoritmo o de su implementación, pero me encanta que usen Unicode en los nombres de variables
    ρ, σ := G[:32], G[32:]
    De alguna manera es mucho mejor que ver "rho", "sigma"

    • Me cuesta estar de acuerdo. Se ve genial, pero en código real no es algo que me gustaría ver
      Para empezar, no sabría cómo escribirlo con el teclado. Y la mayoría ni siquiera sabría los nombres de esos símbolos. Claro, es más probable que quienes lean ese código sí los conozcan, pero no me parece código amable
      La claridad es clave, y "rho" o "sigma" son bastante claros. Además, si tienes la constante "n" y la constante "η" juntas, es perfecto para generar confusión
    • No me gusta nada. Los caracteres que no están en mi teclado agregan un paso más al escribir y generan demasiada fricción. Además, seguro terminaría leyendo ρ como p y topándome con algún error de compilación raro
      ¿Qué tal ponerles acentos o cedillas a las letras? Solo añade complejidad. Mejor apegarse al mínimo común denominador
    • ¿Go permite subíndices Unicode en los nombres de variables?
      Entre los lenguajes que probé, Perl, Python y JavaScript no lo permitieron en Chrome y Firefox, mientras que PHP sí

  • La persona que hizo esto es la misma que hizo https://github.com/FiloSottile/age
    Me encanta esa herramienta

    • Es una pena que no tenga negación plausible integrada. Me refiero a que debería poder cifrar al menos dos archivos y, según la clave que proporciones, descifrar uno u otro
      Me parece una debilidad de seguridad de la mayoría de las herramientas de este tipo. Si solo hay una clave posible, alguien con un martillo puede obligarte a revelarla. Pero si no se puede saber cuántas claves hay, podrías entregar algunas y esperar que el atacante se vaya mientras el archivo realmente protegido queda oculto
    • Quiero que me guste esta herramienta, pero le faltan manuales o tutoriales que expliquen el uso típico. No me refiero al uso en línea de comandos, sino a cómo se deben administrar y distribuir las claves, y qué hay que tener en cuenta
      Toda la capa social que se monta encima de la tecnología no me queda clara. Me gustaría ver una historia de ejemplo con Alice y Bob
    • Age está bien, pero parece estancada. La última versión es de 2022 y no usa una función de derivación de claves basada en contraseña más moderna como argon
      Si buscas algo diseñado para almacenar/compartir secretos, podrías echarle un vistazo a rot: https://github.com/candiddev/rot

  • Especificación: https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.203.ipd.pdf, también enlazada en el artículo