Hardcore Crypto : Concours postquantique du NIST et plus encore

La cryptographie évolue rapidement et, avec l'informatique quantique qui se profile à l'horizon, à quoi devons-nous nous préparer ?

Nous avons rencontré David Hook lors des PrimeKey Tech Days 2021 pour en savoir plus sur ce qui nous attend dans un monde post-quantique. Voici ce qu'il nous a dit.

Le concours Post Quantum Competition (PQC) du NIST continue de progresser. Alors qu'il devait initialement se terminer au cours du premier semestre 2021, il a été prolongé une nouvelle fois, la date de la décision finale étant actuellement fixée à décembre 2021. Alors que nous approchons de la fin de cette compétition, quelques mises à jour importantes sont à noter :

• SP 800-208, "Stateful Signature Schemes XMSS and LMS" est maintenant disponible. Cependant, bien que la norme soit complète, il y a encore quelques zones marquées "TBD". C'est un peu inhabituel, mais probablement dû au fait que XMSS et LMS sont des algorithmes de clé privée avec état et que les équipes travaillant dessus ont estimé que l'effort supplémentaire n'était pas bénéfique. Cela dit, les algorithmes de la norme SP 800-208 fournissent une approche de l'exigence de signature PQC qui peut être appliquée dès aujourd'hui, plutôt que d'attendre la publication des normes NIST.
• Le NIST a confirmé qu'il n'accepterait qu'un seul algorithme de chaque type. Bien qu'il semble assez évident de savoir où la concurrence sera la plus serrée, le NIST nous rappelle également qu'il ne faut pas tirer de conclusions hâtives sur ce qui va franchir la ligne dans un cas particulier.
• La raison pour laquelle il ne faut pas sauter le pas est que la concurrence a donné lieu à de nombreuses nouvelles recherches, et que les travaux visant à déterminer la sécurité des algorithmes et de leurs paramètres se poursuivent - ce n'est donc certainement pas fini. En fait, ce qui semble être une bonne idée aujourd'hui peut s'avérer ne pas être une si bonne idée demain, car les gens continuent à faire des recherches et des révisions.

Cela dit, il y a quelques algorithmes à surveiller :

• Crystals et Falcon figurent toujours sur la liste des finalistes pour les signatures, et Crystals et Saber figurent également sur la liste des algorithmes de chiffrement. Ce sont tous des algorithmes basés sur des treillis. Ils ne seront pas tous retenus.
• Plusieurs algorithmes figurant sur la liste des candidats alternatifs continuent de susciter de nombreuses discussions, comme ^SPHINCS+, qui est un algorithme basé sur le hachage et qui traite certains des problèmes liés à XMSS et LMS, et Frodo, dont l'utilisation est déjà normalisée dans un certain nombre d'endroits.

En se tournant vers l'avenir, l'équipe de PrimeKey vient d'ajouter un nouvel élément à la base de données. Bouncy CastleLa syntaxe des enregistrements de preuves (Evidence Record Syntax, ERS) est décrite dans le document RFC 4998. Les enregistrements de preuves sont un format d'horodatage conçu pour faire face aux changements que nous observons dans la technologie, car ils sont conçus dans une optique de longévité et d'évolutivité.

ERS fournit une structure de données plus sophistiquée à utiliser en plus des protocoles d'horodatage habituels. Par exemple, l'ERS fournit des structures permettant d'utiliser les arbres de Merkle, de sorte que vous pouvez utiliser un seul ArchiveTimeStamp pour vérifier des documents individuels au sein d'un groupe ainsi qu'un groupe entier de documents. Il fournit également un protocole pour prolonger la durée de vie d'un ArchiveTimeStamp en vous permettant d'ajouter de nouveaux algorithmes et de nouvelles signatures pour des raisons telles que l'expiration d'un algorithme ou le remplacement d'un algorithme.

Le premier cas d'utilisation de l'ERS concerne le renouvellement de l'horodatage, qui survient généralement en cas de problème avec l'algorithme de hachage (SHA-1, par exemple) ou avec la signature en cours d'utilisation. 

L'ERS fournit des mécanismes permettant de faire face à ces situations en modifiant la structure représentant l'horodatage. Plus précisément, il archive la séquence d'horodatage pour permettre un changement de signature ou pour remplacer l'algorithme de hachage.

Dans sa forme la plus simple, un ArchiveTimeStamp contient un horodatage classique, comme nous l'avons déjà vu dans les protocoles d'horodatage précédents. Si vous souhaitez horodater un groupe de documents avec ERS, vous pouvez également utiliser une structure d'enregistrement supplémentaire appelée PartialHashTree, qui stocke les informations des feuilles associées aux documents ou aux groupes de documents. Cela vous permet de suivre des documents individuels à l'aide de hachages, tout en faisant en sorte que l'ensemble du groupe soit couvert par un seul horodatage.

La raison pour laquelle nous pouvons suivre des documents individuels dans un groupe avec PartialHashTree est que les structures PartialHashTree représentent un arbre de Merkle. Les arbres de Merkle sont une structure polyvalente très bien comprise du point de vue de la sécurité et utilisée dans tous les domaines, de la blockchain à la transparence des certificats. 

Dans ce cas, les arbres de Merkle sont utiles car ils permettent de construire un hachage de la racine représentant toutes les données contenues dans les nœuds feuilles de l'arbre. Le hachage du nœud racine fournit alors les données à envoyer à un serveur d'horodatage ordinaire et à recevoir un horodatage. Cela permet d'horodater un groupe de documents et de valider ultérieurement des documents individuels ou l'ensemble du groupe. En fait, tout est réduit au point que vous pouvez toujours utiliser un serveur d'horodatage commun pour générer une signature afin de valider votre ArchiveTimeStamp.

Pour un document unique, l'arbre de hachage partiel sera une séquence de primitives de chaînes d'octets ASN.1. Pour un groupe de données ou un ensemble de documents, vous aurez plusieurs hachages (un par document) pour construire l'arbre de hachage partiel. Dans le cas d'un groupe de données, une combinaison de hachages simples est calculée dans l'arbre de hachage partiel, de sorte que chacun est représenté comme un nœud de branche dans l'arbre de Merkle plutôt que comme un simple nœud de feuille (comme c'est le cas pour un seul document).

Un PartialHashTree vous permet de vérifier un document individuel ou un groupe de données ainsi que l'intégrité du groupe dans son ensemble en mettant à disposition tous les hachages associés. En outre, en utilisant la structure de l'historique partiel, il n'est pas nécessaire de stocker l'intégralité de l'arbre de Merkle (bien que cela signifie que vous devez reconstruire l'arbre de Merkle à la volée).

Heureusement, il existe un algorithme itératif simple pour reconstruire un arbre de Merkle à partir des PartialHashTrees, ce qui signifie qu'il n'est pas nécessaire de le stocker en mémoire lorsque vous effectuez des vérifications ou des ajustements. L'algorithme itératif est expliqué plus en détail dans le RFC, avec plusieurs exemples graphiques montrant comment construire et déconstruire les arbres de Merkle.

Avant d'essayer de créer un ArchiveTimeStamp, nous devons d'abord régler quelques problèmes :

• Contrairement à un protocole d'horodatage classique, ERS nécessite l'accès aux données à partir desquelles vous souhaitez créer l'arbre de Merkle. Dans une situation d'horodatage normale, vous pouvez simplement envoyer un hachage sans aucune donnée source, mais dans ce cas, l'API exige que vous lui fournissiez les données afin qu'elle puisse effectuer des calculs et des traitements.
  
• Nous avons défini une interface appelée ERS Data qui vous permet de gérer les données comme vous le souhaitez et nous avons également défini le "groupe de données" comme une classe au sein d'ERS. 
• Fournissez une classe qui rassemble toutes les données et tous les groupes de données, construit l'arbre de Merkle et calcule le hachage du nœud racine. Il s'agit du générateur ArchiveTimeStamp de type ERS.

En cours de route, il se passe énormément de choses sous la surface, avec des arbres construits à la volée, des données analysées et hachées, des hachages stockés, et ainsi de suite ; mais du point de vue d'un utilisateur de l'API, il s'agit d'un processus assez simple qui se réduit à quelques lignes de code. En fin de compte, on obtient un processus en deux étapes avec le service d'horodatage au milieu :

1. Tout d'abord, construisez vos objets de données et mettez en place un calculateur de condensé pour fournir le hachage sous-jacent utilisé pour la construction de l'arbre de Merkle. Vous pouvez ensuite ajouter des objets de données.
2. Ensuite, nous finalisons le tout en créant un générateur de requêtes d'horodatage, qui est une API Bouncy Castle bien établie et configurée de manière appropriée pour le service d'horodatage. À partir de là, vous pouvez le passer au générateur ArchiveTimeStamp pour récupérer la demande d'horodatage, qui encapsule le nœud racine de l'arbre de Merkle. Une fois la réponse reçue, vous pouvez l'ajouter au générateur ArchiveTimeStamp pour produire l'objet ArchiveTimeStamp proprement dit.

Voici un exemple de code pour la première étape de la génération d'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) ;

Générateur de requêtes d'horodatage tspReqGen =
nouveau TimeStampRequestGenerator() ;

tspReqGen.setCertReq(true) ;

Demande d'horodatage tspReq =
ersGen.generateTimeStampRequest(tspReqGen);// Req

Dans la deuxième étape, nous prenons la réponse du serveur d'horodatage et la renvoyons au générateur pour compléter l'ArchiveTimeStamp.

TimeStampResponse tsResp = ... // réponse du serveur TSP

ERSArchiveTimeStamp ats =
ersGen.generateArchiveTimeStamp(tsResp) ;

Fait important dans un monde post-quantique, il s'agit d'horodatages à long terme. En outre, PrimeKey a déjà ajouté à ce processus la prise en charge de LMS, qui est désormais normalisé à la fois par le NIST et l'IETF, pour la génération d'ArchiveTimeStamps. Nous ajouterons d'autres algorithmes de signature post-quantique à Bouncy Castle au fur et à mesure que la compétition du NIST s'achèvera.

La fonctionnalité ERS décrite ici apparaîtra dans BC 1.70 et est déjà ajoutée au BCFJA. Pour en savoir plus sur le fonctionnement exact de cette fonctionnalité, consultez les dernières informations sur le PQC du NIST et obtenez des références pour en savoir plus sur les solutions à long terme pour un monde post-quantique, cliquez ici pour visionner l'intégralité de la discussion de David Hook lors des PrimeKey Tech Days.