--- id: c6fb06cc6cc2bcfd669fca4de7868882 author: Lemon Mint title: 'Randflake ID : génération distribuée d''identifiants uniques de 64 bits avec le chiffrement par blocs Sparx64' description: Générateur distribué d'identifiants uniques de 64 bits combinant un horodatage de 30 bits, un identifiant de nœud de 17 bits, un compteur local de 17 bits et le chiffrement par bloc Sparx64 ARX pour des identifiants non devinables. language: fr date: 2024-12-09T14:50:44.030047Z path: /randflake go_package: gosuda.org/randflake go_repourl: https://github.com/gosuda/randflake.git category: security --- Envisageons une situation dans laquelle nous devons générer des nombres aléatoires uniques de 64 bits, et où des tiers externes ne doivent pas pouvoir prédire le nombre suivant ou précédent. Ici, nous pouvons générer une valeur aléatoire de 8 octets, vérifier si elle existe déjà dans la base de données, puis la stocker si elle est unique. Cependant, cette méthode présente plusieurs inconvénients. Nous devons stocker chaque nombre généré dans une base de données afin de garantir l'unicité. L'exigence d'au moins un aller-retour vers la base de données crée des problèmes de latence, en particulier dans un environnement distribué où la scalabilité est cruciale. Pour résoudre ces problèmes, nous présentons Randflake ID : un générateur d'identifiants aléatoires distribué, uniforme, imprévisible et unique. ## Comment fonctionne Randflake ID ? Randflake ID s'inspire de Snowflake ID, le mécanisme de génération d'identifiants triables (k-sorted) largement utilisé, développé par X (anciennement Twitter). Snowflake ID utilise l'horodatage courant, un identifiant de nœud et un compteur local pour générer un identifiant. Nous avons étendu davantage cette approche à la génération d'identifiants uniques aléatoires et y avons ajouté un nouvel élément : une clé secrète. L'idée clé consiste à ajouter une couche de chiffrement par blocs au générateur d'identifiants uniques existant, afin de rendre infaisable la prédiction de la relation entre les nombres. Un chiffrement par blocs est une fonction cryptographique fondamentale qui transforme un bloc de texte clair de longueur fixe en un bloc de texte chiffré de même longueur. Cette transformation est régie par une clé cryptographique. La caractéristique distinctive d'un chiffrement par blocs est sa réversibilité : il doit s'agir d'une fonction bijective (biunivoque), garantissant que chaque entrée unique correspond à une sortie unique, et inversement. Cette propriété est essentielle au déchiffrement, permettant de retrouver le texte clair original à partir du texte chiffré lorsque la clé correcte est appliquée. En employant un chiffrement par blocs comme fonction biunivoque, nous pouvons garantir que chaque entrée unique produit une sortie unique correspondante dans la plage définie. ## La structure et les considérations de conception En nous appuyant sur ces concepts fondamentaux, examinons comment Randflake ID met ces idées en pratique. La structure de Randflake ID comprend un horodatage Unix de 30 bits avec une précision à la seconde, un identifiant de nœud de 17 bits, un compteur local de 17 bits et un chiffrement par blocs de 64 bits fondé sur l'algorithme sparx64. Voici quelques décisions de conception : - Certaines instances de machines virtuelles dans Google Cloud Platform peuvent synchroniser l'horloge avec une précision de 0,2 ms, mais ce niveau de précision n'est pas disponible sur l'internet public ni chez d'autres fournisseurs cloud. - Nous avons choisi une précision à la seconde car nous ne pouvons synchroniser efficacement l'horloge entre les nœuds qu'à une résolution de quelques millisecondes. - Un identifiant de nœud de 17 bits permet 131 072 générateurs individuels simultanés, qui peuvent être attribués par processus, par cœur ou par thread. - Dans les systèmes à haut débit, un compteur local de 17 bits peut s'avérer insuffisant. Pour répondre au débit requis, nous pouvons attribuer plusieurs générateurs, chacun avec un identifiant de nœud distinct, à fonctionner dans un même processus ou thread. - Nous avons adopté sparx64 comme chiffrement par blocs de 64 bits, un chiffrement par blocs léger moderne fondé sur les opérations ARX. - Les identifiants Randflake offrent une traçabilité interne, ne révélant leur nœud d'origine et leur horodatage qu'à ceux qui possèdent la clé secrète. - Le débit maximal théorique est de 17 179 869 184 identifiants par seconde, ce qui est suffisant pour la plupart des applications à l'échelle mondiale. ## Pseudocode de la génération de Randflake ID Pour illustrer davantage le processus de génération de Randflake ID, le pseudocode Python suivant fournit une implémentation simplifiée : ```python import time import struct from .sparx64 import Sparx64 # Constantes RANDFLAKE_EPOCH_OFFSET = 1730000000 # Dimanche 27 octobre 2024 à 3:33:20 UTC # Allocation des bits RANDFLAKE_TIMESTAMP_BITS = 30 # 30 bits pour l'horodatage (durée de vie de 34 ans) RANDFLAKE_NODE_BITS = 17 # 17 bits pour l'identifiant de nœud (max 131072 nœuds) RANDFLAKE_SEQUENCE_BITS = 17 # 17 bits pour la séquence (max 131072 séquences) # Constantes dérivées RANDFLAKE_MAX_TIMESTAMP = RANDFLAKE_EPOCH_OFFSET + (1 << RANDFLAKE_TIMESTAMP_BITS) - 1 RANDFLAKE_MAX_NODE = (1 << RANDFLAKE_NODE_BITS) - 1 RANDFLAKE_MAX_SEQUENCE = (1 << RANDFLAKE_SEQUENCE_BITS) - 1 class Randflake: def __init__(self, node_id: int, secret: bytes): self.node_id = int(node_id) self.sequence = int(0) self.rollover = int(time.time()) self.sbox = Sparx64(secret) def _new_raw(self) -> int: while True: now = int(time.time()) self.sequence += 1 sequence = self.sequence if sequence > RANDFLAKE_MAX_SEQUENCE: if now > self.rollover: self.sequence = 0 self.rollover = now sequence = 0 else: continue timestamp = now - RANDFLAKE_EPOCH_OFFSET return (timestamp << 34) | (self.node_id << 17) | sequence def generate(self) -> int: id_raw = self._new_raw() src = struct.pack("