💻 computer science

Centered Arithmetic Is Not Leakage-Neutral: Finite-Noise Optimal Attacks and Minimax Laws for Modular Representations

Cet article démontre que le masquage arithmétique centré en complément à deux est intrinsèquement plus vulnérable aux attaques par canaux auxiliaires que le masquage non signé, en fournissant des attaques optimales à bruit fini exactes, une nouvelle loi de fuite spectrale, ainsi que des bornes de capacité prouvant que le stockage non signé minimise la fuite pour la plupart des modules pratiques.

Auteurs originaux : José Luis Delgado

Publié 2026-08-31

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : José Luis Delgado

Article original sous licence CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Dans le monde caché de la sécurité numérique, la protection des clés secrètes est une bataille constante contre des observateurs invisibles. Imaginez un coffre-fort qui détient une clé maîtresse ; si un voleur peut espionner la consommation d'énergie ou les signaux électromagnétiques de l'ordinateur utilisant cette clé, il pourrait voler le secret. Pour empêcher cela, les ingénieurs utilisent une technique appelée masquage. Au lieu de manipuler directement le nombre secret, ils le décomposent en plusieurs morceaux aléatoires, ou « parts », et effectuent les calculs sur ces pièces séparément. Tant que les parts restent indépendantes et bruitées, le secret reste caché. Cependant, un ordinateur ne stocke pas ces nombres dans le vide ; il les stocke sous forme de motifs d'interrupteurs électriques, appelés bits. La façon dont un ordinateur choisit d'écrire un nombre négatif — que ce soit comme une simple valeur positive ou comme un format signé spécifique — modifie le motif de ces interrupteurs. Ce choix crée un signal infime et involontaire, ou « fuite », qu'un attaquant pourrait exploiter. Pendant des années, les chercheurs ont débattu pour savoir si l'utilisation d'un format spécifique pour les nombres négatifs, courant dans le chiffrement moderne, était sûre ou si elle révélait secrètement des informations.

Une nouvelle étude de José Luis Delgado, de l'Universitat Oberta de Catalunya, tranche ce débat par une réponse définitive : le choix de la manière de stocker ces nombres importe énormement, et une méthode courante n'est pas aussi sûre qu'on le pensait. La recherche se concentre sur un type spécifique de chiffrement utilisé pour protéger les données contre les futurs ordinateurs quantiques. Dans ces systèmes, les nombres sont souvent stockés dans un format « centré », où les valeurs négatives sont représentées par de nombreux uns de tête dans leur code binaire, plutôt que dans le format « non signé » standard utilisé pour les nombres positifs. L'auteur démontre que ce format centré fuit nettement plus d'informations que l'alternative non signée. En développant un modèle mathématique précis du comportement de ces signaux sous l'effet du bruit, l'étude prouve que le format centré crée une faiblesse distincte et mesurable qu'un attaquant peut exploiter pour récupérer les clés secrètes bien plus rapidement qu'avec le format non signé.

Les chercheurs n'ont pas seulement supposé l'existence de cette faiblesse ; ils ont construit une carte complète et exacte de la fuite d'informations. Ils ont traité le stockage de l'ordinateur comme un canal transmettant des données, mais avec une nuance : les données sont brouillées par un bruit aléatoire, tout comme un signal radio est déformé par des parasites. En utilisant des outils statistiques avancés, ils ont calculé la probabilité exacte de chaque clé secrète possible basée sur les signaux bruités observés. Cela leur a permis de concevoir l'attaque la plus efficace possible, une attaque qui évalue chaque candidat secret dans un temps qui ne croît que légèrement avec la complexité du système. Ils ont découvert que, si le format non signé minimise la fuite au niveau le plus basique, le format centré introduit une distorsion de signal spécifique qui devient plus dangereuse à mesure que le nombre de « parts » protectrices augmente.

Crucialement, l'étude écarte l'idée que cette fuite soit négligeable ou qu'elle puisse être ignorée si le bruit est élevé. L'auteur a prouvé que pour le format centré, la fuite n'est pas seulement un défaut mineur, mais une caractéristique structurelle qui persiste quel que soit le nombre de parts aléatoires utilisées, à condition que la taille du mot informatique ne soit pas parfaitement adaptée au système de numération. Ils ont identifié un seuil précis : si le mot informatique possède trois bits supplémentaires au-delà de ce qui est strictement nécessaire pour contenir le nombre, le format centré devient strictement moins sûr que le format non signé. En fait, pour les nombres spécifiques utilisés dans les normes de chiffrement mondiales actuelles, le format centré fuit tellement plus d'informations qu'un attaquant aurait besoin de beaucoup moins d'observations pour réussir. L'étude le confirme par des tests en conditions réelles, incluant des simulations et l'analyse de mesures physiques réelles provenant de dispositifs, montrant que la faiblesse théorique se traduit directement en vulnérabilité pratique.

L'article explore également s'il existe une manière parfaite de stocker ces nombres pour masquer toute fuite. Les chercheurs ont trouvé que la seule façon d'éliminer complètement le signal est d'utiliser un code spécial où chaque nombre est stocké avec exactement le même nombre d'interrupteurs « activés ». Bien que cela soit théoriquement possible, cela nécessite un espace de stockage beaucoup plus important que ce qui est pratique pour les systèmes actuels. Pour les tailles standards utilisées dans les applications réelles, un tel code parfait n'existe pas. Au lieu de cela, l'étude fournit une loi claire décrivant exactement comment la fuite se comporte, montrant que le format centré crée un motif d'erreurs prévisible qu'un attaquant peut utiliser. Ce motif est si distinct qu'il permet une séparation entre les deux méthodes de stockage qui est mathématiquement garantie, quel que soit le niveau de bruit.

Les implications de ces découvertes sont immédiates pour la conception de logiciels sécurisés. L'étude montre que la pratique courante consistant à utiliser des représentations centrées pour les nombres négatifs dans la cryptographie sur les réseaux euclidiens (lattice-based) n'est pas neutre ; elle nuit activement à la sécurité. L'auteur fournit des formules exactes que les ingénieurs peuvent utiliser pour calculer le risque pour toute configuration de système spécifique. Ils proposent également une nouvelle méthode de test de sécurité qui est bien plus efficace que les techniques précédentes, capable d'analyser des systèmes complexes en une fraction du temps requis. En prouvant que le format centré n'est pas neutre en termes de fuite, la recherche force une réévaluation de la manière dont ces systèmes de chiffrement critiques sont construits. Elle suggère que pour atteindre le plus haut niveau de sécurité, les développeurs devraient éviter le format centré au profit de l'alternative non signée, ou du moins être pleinement conscients des vulnérabilités spécifiques qu'il introduit. Ce travail constitue une analyse rigoureuse et complète qui transforme une inquiétude vague sur la « représentation » en une compréhension précise et exploitable du risque numérique.

Résumé Technique : L'arithmétique centrée n'est pas neutre vis-à-vis des fuites

Énoncé du Problème

Dans les implémentations logicielles de la cryptographie à base de réseaux (par exemple, ML-KEM, ML-DSA), les valeurs sensibles sont protégées par un masquage arithmétique, où un secret est divisé en parts aléatoires dont la somme est égale au secret modulo $q$ . Bien que l'opération mathématique soit une arithmétique modulaire, le stockage physique de ces parts nécessite un choix de représentation au sein du mot machine. Typiquement, les parts sont stockées soit sous forme de résidus non signés dans $[0, q)$ , soit sous forme d'entiers signés centrés en complément à deux dans $[-\lfloor q/2 \rfloor, \lceil q/2 \rceil - 1]$ .

Bien que les deux encodages implémentent une arithmétique modulaire identique, ils diffèrent considérablement dans leur représentation binaire. Spécifiquement, les entiers négatifs en complément à deux présentent une extension de signe (des uns de tête), contrairement à leurs homologues non signés. Des travaux antérieurs ont exploité cet effet d'« extension de signe » pour des attaques par canaux auxiliaires (par exemple, les prédicteurs de valeur absolue). Cependant, un cadre théorique complet caractérisant comment ce choix de représentation affecte les fuites pour tous les ordres de masquage, sous un bruit fini et pour des moduli arbitraires, faisait défaut. Cet article répond à la question fondamentale : L'arithmétique centrée est-elle neutre vis-à-vis des fuites par rapport au stockage non signé ?

Méthodologie

L'article emploie une approche mathématique rigoureuse combinant la théorie des probabilités, l'analyse de Fourier et la théorie combinatoire des nombres pour modéliser le canal de fuite par canaux auxiliaires.

Modélisation du canal à bruit fini : L'auteur modélise la fuite des parts masquées comme des canaux de bruit additifs indépendants. Il dérive la vraisemblance exacte de la somme masquée en traitant le problème comme une convolution cyclique des distributions de fuite des parts individuelles.
Analyse de Fourier : L'analyse utilise la transformée de Fourier discrète (DFT) pour convertir la convolution en un produit dans le domaine fréquentiel. Cela permet de dériver des attaques optimales et la décomposition spectrale de la fuite.
Minimax de Représentation : L'étude évalue différentes « sections » (représentations) de $\mathbb{Z}_q$ en minimisant l'énergie du spectre de fuite. Cela implique de comparer des sections contiguës (non signées vs centrées) et des dictionnaires de codes binaires injectifs arbitraires.
Décomposition Spectrale : Une innovation méthodologique clé est la décomposition du spectre de fuite du complément à deux centré en termes d'extension de signe et de défaut de retenue (carry), permettant une analyse asymptotique précise.
Validation Algorithmique : Les bornes théoriques sont vérifiées par des calculs exacts, des expériences synthétiques avec les paramètres complets de ML-KEM et ML-DSA, et l'analyse de traces physiques publiques.

Contributions Clés

1. Inférence Optimale à Bruit Fini

L'article établit que la vraisemblance complète d'une somme masquée peut être calculée en temps quasi-linéaire $O(dq \log q)$ en utilisant une convolution circulaire évaluée via la transformée de Fourier rapide (FFT).

Résultat : Cela fournit une stratégie d'attaque optimale qui évalue simultanément les $q$ hypothèses.
Condition de Suffisance : L'auteur dérive une condition exacte sous laquelle la statistique de produit couramment utilisée (multiplier les parts centrées) conserve toute l'information de vraisemblance. Il prouve que pour une table de fuite non négative avec un zéro unique, la statistique de produit est strictement insuffisante pour tout module $q \ge 2$ et ordre $d \ge 2$ sous un bruit fini. L'observation complète contient strictement plus d'informations (divergence de KL, divergence de Rényi, etc.) que la statistique de produit.

2. Lois Minimax de Représentation Globale

L'article optimise le choix de la représentation pour minimiser la fuite :

Fuite de Premier Ordre : Parmi toutes les sections contiguës, le stockage non signé ( $[0, q)$ ) est l'unique minimiseur de la fuite de premier ordre, sauf si le module $q$ occupe la totalité du mot machine ( $q=2^m$ ), auquel cas toutes les sections sont équivalentes.
Fuite d'Ordre Supérieur : L'optimalité du stockage non signé n'est pas permanente. L'article identifie un « changement de phase » exact où, pour des paramètres spécifiques (ex: $q=14, \beta=4$ ), le stockage centré devient l'unique minimiseur pour les ordres $d \ge 4$ , alors que le non signé est optimal pour les ordres inférieurs.
Loi Lexicographique : Pour toute famille finie de représentations, le minimiseur final lorsque l'ordre de masquage $d \to \infty$ est déterminé par le spectre des coefficients de fuite trié de manière lexicographique la plus petite.
Dictionnaires à Poids Constant : Pour des encodages binaires arbitraires, la fuite disparaît exactement si et seulement si le dictionnaire possède un poids de Hamming constant. L'article fournit une borne de capacité nette pour l'existence de tels dictionnaires ( $q \le \binom{\beta}{\lfloor \beta/2 \rfloor}$ ) et calcule la largeur de mot minimale requise pour les modules standards du NIST (ex: $\beta=14$ pour $q=3329$ ).

3. La Loi de Fuite de la Réduction Centrée

Le résultat théorique central de l'article est une décomposition spectrale exacte de la fuite du complément à deux centré :

Décomposition : Le spectre de fuite est divisé en un terme macroscopique d'extension de signe et un défaut de retenue binaire.
Seuil de Dominance : L'article prouve un seuil uniforme net : trois bits excédentaires ( $s = \beta - \lceil \log_2 q \rceil \ge 3$ ) sont nécessaires pour que le stockage centré présente une magnitude de fuite strictement supérieure au stockage non signé au premier mode de Fourier. Spécifiquement, la condition $D(q, \beta) > 2U(q)$ est vérifiée si et seulement si $s \ge 3$ .
Asymptotique : Pour un excès de largeur fixe, le ratio des coefficients de fuite centré par rapport au non signé converge vers $s+1$ . Pour le cas spécifique de $q=2^m-1$ , le ratio de fuite converge vers une constante liée à la somme des tangentes ( $\kappa \approx 1.81$ ).
Neutralité : L'arithmétique centrée n'est pas neutre vis-à-vis des fuites. Elle n'est neutre (équivalente au non signé) que dans le cas exact où $q=2^m$ et $\beta=m$ . Dans tous les autres cas, le stockage centré entraîne une fuite strictement plus élevée au premier mode de Fourier (et typiquement pour les faibles ordres de masquage), bien qu'il puisse devenir la représentation optimale à des ordres très élevés pour certains ensembles de paramètres.

4. Robustesse et Complexité d'Échantillonnage

Radii de Robustesse : L'article définit des rayons de robustesse exacts pour les modèles de poids de Hamming pondérés, montrant que la séparation stricte entre le stockage centré et non signé se maintient même avec des variations de sensibilité de bits, à condition que l'excès de largeur soit d'au moins 3.
Complexité d'Échantillonnage : Un test harmonique à confiance exponentielle est proposé. L'article prouve que le ratio de complexité d'échantillonnage entre les attaques centrées et non signées évolue selon la puissance $2d$ du ratio de leurs coefficients spectraux. Cela implique que pour des ordres de masquage plus élevés, la pénalité pour l'utilisation du stockage centré (qui possède une fuite plus élevée au premier mode) croît exponentiellement, à moins que l'ensemble de paramètres spécifique ne place le système dans un régime où le stockage centré est le minimiseur global.

Résultats et Validation

Expériences Synthétiques : Des implémentations complètes pour ML-KEM ( $q=3329$ ) et ML-DSA ( $q=8380417$ ) confirment les facteurs de complexité d'échantillonnage théoriques. Pour $d=3, 4, 6$ , la représentation centrée nécessite nettement plus de traces que la représentation non signée pour atteindre le même taux de succès, s'alignant sur les limites asymptotiques dérivées.
Traces Physiques : L'analyse a été validée par rapport à des traces physiques publiques d'une implémentation masquée de ML-DSA. Le prédicat de signe a atteint un Welch $|t|$ de 155,73 et une précision équilibrée de 90,80 %, confirmant la présence du canal de fuite par extension de signe prédit par la théorie.
Efficacité Algorithmique : L'attaque optimale proposée (utilisant la convolution par FFT) a réussi à scorer toutes les hypothèses pour $q=8\,380\,417$ en moins de 35 secondes, démontant sa faisabilité pratique.

Signification

Cet article modifie fondamentalement la compréhension du masquage arithmétique dans les logiciels. Il démontre que le choix de la représentation machine (centrée vs non signée) n'est pas un simple détail d'implémentation, mais un composant critique du canal de fuite par canaux auxiliaires.

Réfutation de la Neutralité : L'auteur démontre de manière concluante que « L'arithmétique centrée n'est pas neutre vis-à-vis des fuites ». L'extension de signe inhérente à la représentation en complément à deux introduit un spectre de fuite distinct qui n'est pas atténué par le masquage seul.
Directives de Conception : Le travail fournit des directives exactes et exploitables pour les implémenteurs :
- Utiliser le stockage non signé pour la sécurité de premier ordre et lorsque l'excès de bits est faible ( $s < 3$ ), car il est l'unique minimiseur de la fuite de premier ordre.
- Être conscient que le stockage centré entraîne généralement une lourde pénalité en termes de complexité d'échantillonnage en raison d'une magnitude de fuite plus élevée au premier mode, ne devenant optimal qu'à des ordres très élevés pour des ensembles de paramètres spécifiques (démontant un changement de phase dans l'optimalité).
- Les dictionnaires à poids constant offrent une voie théorique vers une fuite nulle, mais nécessitent des largeurs de mots qui peuvent ne pas correspondre aux contraintes matérielles standards.
Fondation Théorique : En fournissant des lois spectrales exactes et des conditions d'optimalité à bruit fini, cet article comble l'écart entre la sécurité théorique du masquage et les réalités pratiques de l'implémentation, offrant une base rigoureuse pour évaluer et concevoir des systèmes cryptographiques à base de réseaux résistants aux canaux auxiliaires.