Criptografía Avanzada: La Competición Post-Cuántica del NIST y Más

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

Nos reunimos con David Hook en PrimeKey Tech Days 2021 para saber más sobre qué esperar en un mundo post-cuántico. Esto es lo que nos compartió.

La Competición Postcuántica (PQC) del NIST sigue avanzando. Aunque originalmente se esperaba que concluyera en la primera mitad de 2021, se ha prorrogado de nuevo, con la fecha de decisión final actual fijada para diciembre de 2021. A medida que nos acercamos al final de esta competición, hay algunas actualizaciones importantes a tener en cuenta:

• SP 800-208, “Esquemas de firma con estado XMSS y LMS” ya está disponible. Sin embargo, aunque el estándar está completo, todavía hay algunas áreas marcadas como “TBD” (por determinar). Esto es un tanto inusual, pero probablemente se deba a que XMSS y LMS son algoritmos de clave privada con estado y los equipos que trabajaban en ellos consideraron que el esfuerzo adicional no era beneficioso. Dicho esto, los algoritmos de SP 800-208 ofrecen un enfoque para abordar un requisito de firma PQC que puede aplicarse hoy mismo, en lugar de esperar a que se publiquen los estándares del NIST.
• El NIST ha confirmado que solo aceptará un algoritmo de cada tipo. Aunque parece bastante obvio dónde es probable que se dé 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 particular.
• La razón para evitar sacar conclusiones precipitadas es que la competición ha dado lugar a mucha investigación nueva, y el trabajo para determinar la seguridad de los algoritmos y sus parámetros sigue en curso, por lo que definitivamente aún no ha terminado. De hecho, lo que hoy parece una buena idea puede no serlo tanto mañana a medida que la gente continúa investigando y revisando el trabajo.

Dicho todo esto, hay algunos algoritmos a los que hay que prestar atención:

• 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 estos son algoritmos basados en retículos. No todos lo conseguirán.
• Hay varios algoritmos en la lista de candidatos alternativos que siguen generando mucho debate, como SPHINCS⁺, que es un algoritmo basado en hash que aborda algunos de los problemas de XMSS y LMS, y Frodo, que ya está estandarizado para su uso en varios lugares.

Mirando hacia el futuro, llegamos a algo que el equipo de PrimeKey acaba de añadir a Bouncy Castle, conocido como Evidence Record Syntax (ERS) y descrito en el RFC 4998. Los registros de evidencia 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 para ser utilizada sobre los protocolos de sellado de tiempo regulares. Por ejemplo, ERS proporciona estructuras para utilizar Árboles de Merkle de modo que se pueda usar un único ArchiveTimeStamp para verificar documentos individuales en un grupo, así como un grupo completo de documentos. También proporciona un protocolo para extender la vida útil de un ArchiveTimeStamp, permitiendo añadir nuevos algoritmos y firmas para aspectos como la caducidad de algoritmos y la sustitución de algoritmos.

El primer caso de uso de ERS se centra en la renovación del sellado 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. 

ERS proporciona mecanismos para abordar estas situaciones cambiando la estructura que representa el sellado de tiempo. Específicamente, lo hace archivando la secuencia del sellado de tiempo para permitir un cambio de firma o para reemplazar el algoritmo hash.

En su forma más simple, un ArchiveTimeStamp contiene un sellado de tiempo clásico, al igual que lo que ya hemos visto en protocolos de sellado de tiempo anteriores. Si desea sellar 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 con los documentos o grupos de documentos. Esto le permite rastrear documentos individuales con hashes, pero aún así tener todo el grupo cubierto por un único sellado de tiempo.

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

En este caso, los Árboles de Merkle son útiles porque permiten construir un hash raíz que representa todos los datos en los nodos hoja del árbol. El hash del nodo raíz proporciona entonces los datos para enviar a un servidor de sellado de tiempo regular y recibir un sellado de tiempo. El resultado de esto es que permite sellar un grupo de documentos y validar documentos individuales o el grupo completo más tarde. De hecho, lo reduce todo hasta el punto en que aún se puede utilizar un servidor de sellado de tiempo común para generar una firma que valide su ArchiveTimeStamp.

Para un solo 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á múltiples hashes (uno por documento) para construir el PartialHashTree. En el caso de un grupo de datos, una combinación de hashes individuales se calcula en el PartialHashTree, de modo que cada uno se representa como nodos de rama en el Árbol de Merkle en lugar de simples nodos hoja (como es el caso de un solo documento).

Un PartialHashTree permite verificar un documento individual o un grupo de datos y la integridad del grupo en su conjunto al poner a disposición todos los hashes asociados. Además, al utilizar la estructura de historial parcial, no es necesario almacenar todo el Árbol de Merkle (aunque sí implica que hay que reconstruir el Árbol de Merkle sobre la marcha).

Afortunadamente, existe un algoritmo iterativo simple para reconstruir un Árbol de Merkle a partir de los PartialHashTrees, lo que significa que no es necesario almacenarlo en la memoria al realizar verificaciones o ajustes. El algoritmo iterativo se explica con más detalle con varios ejemplos gráficos en el RFC, mostrando cómo se pueden construir y deconstruir los Árboles de Merkle.

Antes de intentar crear un ArchiveTimeStamp, necesitábamos abordar algunas cosas primero:

• A diferencia de un protocolo de sellado de tiempo convencional, ERS requiere acceso a los datos a partir de los cuales se desea crear el árbol de Merkle. En una situación de sellado de tiempo normal, se puede enviar un hash sin datos de origen; sin embargo, en este caso, la API exige que se le proporcionen los datos para que pueda realizar cálculos y procesamientos sobre ellos.
  
• Hemos definido una interfaz conocida como ERS Data que permite gestionar los datos a voluntad, y también se ha definido "grupo de datos" como una clase dentro de ERS. 
• Se proporciona una clase que agrupa todos los datos y grupos de datos, construye el árbol de Merkle y calcula un hash del nodo raíz. Este es el generador de ArchiveTimeStamp de tipo ERS.

En el proceso, ocurren muchos eventos internos: árboles construidos sobre la marcha, datos analizados y hasheados, hashes almacenados, etc. Sin embargo, desde la perspectiva de un usuario de la API, es un proceso bastante sencillo que se reduce a unas pocas líneas de código. En última instancia, se obtiene un proceso de dos pasos con el servicio de sellado de tiempo en el centro:

1. Primero, construya sus objetos de datos y configure un calculador de digest para proporcionar el hash subyacente utilizado en la construcción del árbol de Merkle. Luego, puede añadir los objetos de datos.
2. Segundo, finalice todo creando un generador de solicitud de sellado de tiempo, que es una API de Bouncy Castle bien establecida y configurada adecuadamente para el servicio de sellado de tiempo. A partir de ahí, puede pasarlo al generador de ArchiveTimeStamp para recuperar la solicitud de sellado de tiempo, que encapsula el nodo raíz del árbol de Merkle. Una vez que la respuesta regresa, puede añadirla al generador de ArchiveTimeStamp para producir el objeto ArchiveTimeStamp real.

A continuación, se muestra 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 =
new 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 vuelta al generador para completar el ArchiveTimeStamp.

TimeStampResponse tsResp = … // respuesta del servidor TSP

ERSArchiveTimeStamp ats =
ersGen.generateArchiveTimeStamp(tsResp);

Es importante destacar que, en un mundo post-cuántico, estos son sellados de tiempo a largo plazo. Además, PrimeKey ya ha añadido soporte a este proceso para LMS, estandarizado tanto por NIST como por la IETF, para la generación de ArchiveTimeStamps. Añadiremos más algoritmos de firma post-cuánticos a Bouncy Castle a medida que la competición de NIST se acerque a su fin.

La funcionalidad ERS aquí descrita aparecerá en BC 1.70 y ya ha sido añadida al BCFJA. Para saber más sobre cómo funciona exactamente, profundice en lo último sobre PQC de NIST y obtenga referencias para aprender más sobre soluciones a largo plazo para un mundo post-cuántico, haga clic aquí para ver la discusión completa de PrimeKey Tech Days con David Hook.