Criptografía Hardcore: Concurso post cuántico del NIST y mucho más

La criptografía cambia rápidamente y, con la computación cuántica en el horizonte, ¿para qué debemos prepararnos?

Nos sentamos con David Hook en PrimeKey Tech Days 2021 para saber más sobre lo que nos espera en un mundo post-cuántico. Esto es lo que nos contó.

El Concurso Postcuántico (PQC) del NIST sigue avanzando. Aunque en un principio se esperaba que concluyera en el primer semestre de 2021, se ha prorrogado de nuevo, con la actual fecha de decisión final fijada para diciembre de 2021. A medida que nos acercamos al final de este concurso, hay que tener en cuenta algunas actualizaciones importantes:

• SP 800-208, "Stateful Signature Schemes XMSS and LMS" ya está disponible. Sin embargo, aunque la norma está completa, todavía hay algunas áreas marcadas como "TBD". Esto es un poco inusual, pero probablemente se deba al hecho de que XMSS y LMS son algoritmos de clave privada con estado y los equipos que trabajan en ellos consideraron que el esfuerzo adicional no era beneficioso. Dicho esto, los algoritmos de SP 800-208 proporcionan un enfoque para abordar un requisito de firma PQC que puede aplicarse hoy, en lugar de esperar a que se publiquen las normas del NIST.
• El NIST ha confirmado que sólo aceptará un algoritmo de cada tipo. Aunque parece bastante obvio dónde puede estar la competencia más reñida, el NIST también nos recuerda que no debemos sacar conclusiones precipitadas sobre lo que va a cruzar la línea en un caso concreto.
• La razón para no saltar es que la competencia ha dado lugar a un montón de nuevas investigaciones, y el trabajo para determinar la seguridad de los algoritmos y sus parámetros sigue en marcha, por lo que definitivamente aún no ha terminado. De hecho, lo que hoy parece una idea sólida puede resultar no serlo tanto mañana, a medida que se siga investigando y revisando el trabajo.

Dicho esto, hay algunos algoritmos que conviene vigilar:

• Crystals y Falcon siguen en la lista de finalistas de firma, y Crystals y Saber también están en la lista de algoritmos de cifrado. Todos ellos son algoritmos basados en celosías. No todos van a conseguirlo.
• Hay varios algoritmos en la lista de candidatos alternativos que siguen suscitando mucho debate, como ^SPHINCS+, que es un algoritmo basado en hash que resuelve algunos de los problemas con XMSS y LMS, y Frodo, que ya está estandarizado para su uso en varios lugares.

Mirando al futuro nos encontramos con algo que el equipo de PrimeKey acaba de añadir a Bouncy Castleconocido como Evidence Record Syntax (ERS) y descrito en el RFC 4998. Los registros de pruebas son un formato de sellado de tiempo diseñado para hacer frente a los cambios que estamos viendo en la tecnología, ya que están diseñados pensando en la longevidad y la capacidad de actualización.

ERS proporciona una estructura de datos más sofisticada que puede utilizarse además de los protocolos de sellado de tiempo habituales. Por ejemplo, ERS proporciona estructuras para hacer uso de los árboles de Merkle, de modo que se puede utilizar un único ArchiveTimeStamp para verificar documentos individuales de un grupo, así como un grupo entero de documentos. También proporciona un protocolo para prolongar la vida de una ArchiveTimeStamp que permite añadir nuevos algoritmos y firmas para cuestiones como la caducidad o la sustitución de algoritmos.

El primer caso de uso de ERS se centra en la renovación de la marca de tiempo, que suele surgir cuando hay un problema con el algoritmo hash (por ejemplo, SHA-1) o un problema con la firma actualmente en uso. 

La ERS proporciona mecanismos para hacer frente a estas situaciones cambiando la estructura que representa la marca de tiempo. Concretamente, lo hace archivando la secuencia de marcas de tiempo para permitir un cambio de firma o sustituir el algoritmo hash.

En su forma más simple, un ArchiveTimeStamp contiene un timestamp clásico, igual que lo que ya hemos visto en protocolos timestamp anteriores. Si desea poner una marca de tiempo a un grupo de documentos con ERS, también puede utilizar una estructura de registro adicional llamada PartialHashTree, que almacena la información de hoja asociada a los documentos o grupos de documentos. Esto le permite hacer un seguimiento de los documentos individuales con hashes, pero manteniendo todo el grupo cubierto por una única marca de tiempo.

La razón por la que podemos rastrear documentos individuales en un grupo con PartialHashTree es que las estructuras PartialHashTree representan un Merkle Tree. Los Merkle Trees son una estructura versátil que se entiende muy bien desde el punto de vista de la seguridad y se utiliza en todo, desde blockchain hasta transparencia de certificados. 

En este caso, los árboles Merkle son útiles porque permiten construir un hash raíz que representa todos los datos de los nodos hoja del árbol. El hash del nodo raíz proporciona entonces los datos para enviarlos a un servidor de marcas de tiempo normal y recibir una marca de tiempo. El resultado de esto es que te permite poner una marca de tiempo a un grupo de documentos y validar documentos individuales o todo el grupo más tarde. De hecho, lo reduce todo hasta el punto de que puedes seguir utilizando un servidor de marcas de tiempo común para generar una firma que valide tu ArchiveTimeStamp.

Para un único documento, el PartialHashTree será una secuencia de primitivas de cadena de octetos ASN.1. Para un grupo de datos o un conjunto de documentos, tendrás múltiples hashes (uno por documento) para construir el PartialHashTree. En el caso de un grupo de datos, se calcula una combinación de hashes individuales en el PartialHashTree, por lo que cada uno se representa como nodos de rama en el árbol de Merkle en lugar de simples nodos de hoja (como es el caso de un único documento).

Un PartialHashTree le permite verificar un documento individual o un grupo de datos y la integridad del grupo en su conjunto poniendo a su disposición todos los hashes asociados. Además, al utilizar la estructura de historial parcial, en realidad no tienes que almacenar todo el Merkle Tree (aunque sí significa que tienes que reconstruir el Merkle Tree sobre la marcha).

Afortunadamente, existe un sencillo algoritmo iterativo para reconstruir un Árbol de Merkle a partir de los PartialHashTrees, lo que significa que no tiene que almacenarlo en memoria cuando esté haciendo la verificación o los ajustes. El algoritmo iterativo se explica con más detalle con varios ejemplos gráficos en la RFC que muestran cómo se pueden construir y deconstruir Árboles Merkle.

Antes de intentar crear un ArchiveTimeStamp, necesitamos ocuparnos primero de algunas cosas:

• A diferencia de lo que ocurre con un protocolo de sellado de tiempo normal, el ERS requiere acceso a los datos a partir de los cuales se desea crear el árbol de Merkle. Con una situación normal de marca de tiempo, puedes simplemente enviar un hash sin ningún dato de origen, pero en este caso, la API requiere que realmente le proporciones los datos para que pueda hacer cálculos y procesarlos.
  
• Hemos definido una interfaz conocida como Datos ERS que le permite gestionar los datos como desee y también ha definido "grupo de datos" como una clase dentro de ERS. 
• Proporcionar una clase que reúna todos los datos y grupos de datos, construya el Árbol de Merkle y calcule un hash del nodo raíz. Es el generador ArchiveTimeStamp de la clase ERS.

A lo largo del proceso, ocurren muchas cosas bajo la superficie, como la construcción de árboles sobre la marcha, el análisis sintáctico y el hash de los datos, el almacenamiento de los hashes, etc., pero desde el punto de vista de un usuario de la API, se trata de un proceso bastante sencillo que se reduce a unas pocas líneas de código. En definitiva, se trata de un proceso de dos pasos en el que el servicio de marcas de tiempo se sitúa en el medio:

1. Primero, construye tus objetos de datos y configura una calculadora de compendio para proporcionar el hash subyacente que se utiliza para la construcción del Árbol de Merkle. A continuación, puede agregar en los objetos de datos.
2. En segundo lugar, finaliza todo creando un generador de solicitudes de marcas de tiempo, que es una API Bouncy Castle bien establecida que está configurada adecuadamente para el servicio de marcas de tiempo. A partir de ahí, puedes pasarlo al generador ArchiveTimeStamp para obtener la solicitud de marca de tiempo, que encapsula el nodo raíz del árbol Merkle. Una vez recibida la respuesta, puedes añadirla al generador ArchiveTimeStamp para producir el objeto ArchiveTimeStamp real.

Aquí está el código de ejemplo para el primer paso en la generación de un ArchiveTimeStamp:

ERSData h1Doc = new ERSByteData(…); // Setup
ERSData h2Doc = new ERSByteData(…);
ERSDataGroup h3Docs = new ERSDataGroup(
new ERSData[]{new ERSByteData(…), new ERSByteData(…)});

DigestCalculator digestCalculator = digestCalculatorProvider.get(
new AlgorithmIdentifier(NISTObjectIdentifiers.id_sha256));

ERSArchiveTimeStampGenerator ersGen =
new ERSArchiveTimeStampGenerator(digestCalculator); // Init

ersGen.addData(h1Doc);
ersGen.addData(h2Doc);
ersGen.addData(h3Docs);

TimeStampRequestGenerator tspReqGen =
nuevo TimeStampRequestGenerator();

tspReqGen.setCertReq(true);

TimeStampRequest tspReq =
ersGen.generateTimeStampRequest(tspReqGen);// Req

En el segundo paso simplemente tomamos la respuesta del servidor de sellado de tiempo y la pasamos de nuevo al generador para completar el ArchiveTimeStamp.

TimeStampResponse tsResp = ... // respuesta del servidor TSP

ERSArchiveTimeStamp ats =
ersGen.generateArchiveTimeStamp(tsResp);

Y lo que es más importante en un mundo post-cuántico, se trata de sellos de tiempo a largo plazo. Además, PrimeKey ya ha añadido soporte a este proceso para LMS, que ya está estandarizado tanto por el NIST como por el IETF, para generar ArchiveTimeStamps. Añadiremos más algoritmos de firma poscuántica a Bouncy Castle a medida que el concurso del NIST llegue a su fin.

La funcionalidad ERS descrita aquí aparecerá en BC 1.70 y ya está añadida a la BCFJA. Para saber más sobre cómo funciona exactamente, profundizar en lo último sobre el PQC del NIST y obtener referencias para saber más sobre soluciones a largo plazo para un mundo poscuántico, haga clic aquí para ver el debate completo de PrimeKey Tech Days con David Hook.