Nonces dans Schnorr et MuSig2 : analyse mathématique et métriques

Analyse des nonces cachés dans Schnorr et MuSig2 : Fondements mathématiques et métriques

Les signatures cryptographiques modernes, telles que Schnorr (BIP340) et MuSig2 (BIP327), nécessitent non seulement des vérifications de validité, mais aussi une analyse approfondie de leurs caractéristiques structurelles. Cet article explore une méthode pour transformer les signatures en un ensemble de contraintes affines afin de révéler des motifs cachés dans les nonces. Cette approche passe d'une vérification binaire à une évaluation quantitative de la géométrie de la famille de nonces, ce qui est crucial pour l'analyse forensique en cas de fuites partielles de données.

Principes fondamentaux de la représentation affine

L'idée clé consiste à interpréter l'équation de la signature comme une contrainte affine. Pour BIP340, l'équation s = k + e·d mod n sert de base pour construire la fonction de nonce caché k_i(d') = s_i - e_i·d' mod n, où d' est une clé secrète candidate. Lorsque d' = d est correcte, cette fonction récupère les véritables nonces canoniques. Pour des candidates incorrectes, elle génère une famille pseudaléatoire aux propriétés statistiques qui diffèrent fortement des données réelles.

Pont d'appartenance BIP340

La transition normalisante via la récupération du point R* = sG - eP permet une classification stricte des signatures selon cinq critères :

• r dans le corps
• s dans la plage valide
• Point R* non nul
• Parité de la coordonnée Y
• Correspondance de la coordonnée X

Ce pont élimine les faux positifs dans l'analyse en filtrant les chaînes parasites avant d'appliquer les métriques. Sans cette étape, toute analyse ultérieure devient vulnérable aux artefacts d'analyse syntaxique.

Géométrie de la famille de nonces

Métriques de compression

L'analyse d'un ensemble de signatures pour une clé unique repose sur la mesure de la compression de la famille K(d') :

• Nonces uniques : U_k(d') = |{k_i(d')}|
• Collisions : C_k(d') = m - U_k(d')
• Analyse des deltas :

- Deltas uniques : U_Δ(d') = |{Δ_i(d')}|

- Deltas répétés : C_Δ(d') = (m-1) - U_Δ(d')

• Métriques de préfixe pour les niveaux de bits 128/64/32/16 :

- U_pref_b(d') = |{Pref_b(k_i(d'))}|

Ces métriques révèlent des motifs caractéristiques :

• Réutilisation de nonces → collisions accrues
• Génération en échelle → deltas répétés
• Nonce court → entropie anormalement faible dans les préfixes élevés

Modèle de connectivité

Pour détecter les structures locales, un système à deux feuilles est utilisé :

K_plus = sorted([k_i(d') for i in range(m)])
K_minus = sorted([-k_i(d') % n for i in range(m)])

L'analyse est effectuée en quatre modes de voisinage (++/--/+-/-+), en calculant :

• Support local des deltas : Support_local(d') = max_mode max_δ count_mode(δ)
• Masse des répétitions : Mass_repeat(d') = Σ max(count(δ)-1, 0)
• Support de préfixe pour les niveaux 128/96/64/32/16

Cette approche met au jour des grappes cachées et des symétries locales inaccessibles à l'analyse globale.

Spécificités de MuSig2

Linéarisation valide au protocole

Pour MuSig2, l'analyse porte non pas sur la signature finale, mais sur les signatures partielles avec le contexte complet de session. Composants clés :

• Clé agrégée Q
• Nonce partagé R
• Coefficients b, e, a
• Facteurs de parité g et gacc

La parité de clé est déterminée par par_key = g·gacc mod n, permettant une gestion correcte des coordonnées Y paires/impaires. Les signatures partielles sont réduites à une forme affine via la récupération du nonce brut à partir du contexte de session.

Différences clés par rapport à BIP340

• Pas d'équation directe s = k + ed
• Nécessité de tenir compte de l'agrégation de clés
• Dépendance aux paramètres spécifiques à la session
• Gestion double de la parité (clé + nonce)

Cela nécessite de modifier toutes les métriques pour qu'elles fonctionnent avec des structures valides au protocole au lieu de données brutes.

Points clés à retenir

• Pont d'appartenance — étape de filtrage obligatoire avant l'analyse
• Les métriques de compression détectent efficacement la réutilisation et les motifs en échelle
• L'analyse de connectivité met au jour les structures locales via le modèle à deux feuilles
• MuSig2 nécessite un traitement séparé via le contexte de session
• Toutes les conclusions reposent sur des propriétés mathématiques mesurables, non sur des heuristiques

Implémentation pratique

Le système est implémenté sous forme de démo interactive sur GitHub. Composants clés :

• Validateur d'appartenance BIP340
• Générateur de famille affine pour un d' donné
• Suite de métriques de compression/-connectivité
• Visualiseur de géométrie des nonces

Exemple de calcul de support de préfixe :

def top_prefix_support(k_list, bits):
    prefix_mask = (1 << (256 - bits)) - 1
    prefixes = [k & prefix_mask for k in k_list]
    return max(Counter(prefixes).values())

Les artefacts du projet confirment l'efficacité des métriques sur des données réelles avec des vulnérabilités connues. Important : le système ne récupère pas directement les clés privées, mais fournit des signaux mesurables pour une analyse ultérieure.

Cette approche élargit l'arsenal de cryptoanalyse, en transformant la tâche de tâtonnements en propriétés mathématiques mesurables. Pour les développeurs, elle offre un moyen de vérifier la qualité de génération des nonces et de détecter des vulnérabilités cachées dans les implémentations.

— Editorial Team