Nonce'y w Schnorr i MuSig2: analiza matematyczna i metryki

Analiza ukrytych nonce’ów w Schnorr i MuSig2: podstawy matematyczne i metryki

Współczesne podpisy kryptograficzne, takie jak Schnorr (BIP340) i MuSig2 (BIP327), wymagają nie tylko sprawdzenia poprawności, ale i głębokiej analizy cech strukturalnych. W tym artykule omawiana jest metoda przekształcania podpisów w zbiór afinicznych ograniczeń w celu wykrycia ukrytych wzorców w nonce’ach. Podejście to pozwala przejść od binarnej weryfikacji do ilościowej oceny geometrii rodziny nonce’ów, co jest kluczowe dla analizy forensics w warunkach częściowego wycieku danych.

Podstawowe zasady afinicznego przedstawienia

Kluczowa idea polega na interpretacji równania podpisu jako afinicznego ograniczenia. Dla BIP340 równanie s = k + e·d mod n staje się podstawą do zbudowania funkcji ukrytego nonce’a k_i(d') = s_i - e_i·d' mod n, gdzie d' to kandydat na klucz sekretny. Przy poprawnym d' = d ta funkcja odtwarza prawdziwe kanoniczne nonce’y. Dla fałszywych kandydatów powstaje pseudolosowa rodzina, której właściwości statystyczne gwałtownie różnią się od rzeczywistych danych.

BIP340 Membership Bridge

Normalizujące przejście poprzez odtworzenie punktu R* = sG - eP pozwala na ścisłą klasyfikację podpisów według pięciu kryteriów:

• r w granicach ciała
• s w dopuszczalnym zakresie
• Nienulowy punkt R*
• Parzystość współrzędnej Y
• Zgodność współrzędnej X

Ten most eliminuje fałszywe alarmy podczas analizy, filtrując śmieciowe ciągi przed zastosowaniem metryk. Bez tego etapu jakakolwiek dalsza analiza staje się podatna na artefakty parsowania.

Geometria rodziny nonce’ów

Metryki kompresji

Analiza zbioru podpisów jednego klucza opiera się na pomiarze kompresji rodziny K(d'):

• Unikalne nonce’y: U_k(d') = |{k_i(d')}|
• Kolizje: C_k(d') = m - U_k(d')
• Analiza delt:

- Unikalne delty: U_Δ(d') = |{Δ_i(d')}|

- Powtarzające się delty: C_Δ(d') = (m-1) - U_Δ(d')

• Metryki prefiksowe dla poziomów bitowych 128/64/32/16:

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

Te metryki ujawniają charakterystyczne wzorce:

• Ponowne użycie nonce’ów → wzrost kolizji
• Generacja ladder → powtarzanie delt
• Krótki nonce → anomalnie niska entropia wysokich prefiksów

Model łączności

W celu wykrycia lokalnych struktur stosowany jest system dwulistowy:

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

Analiza przeprowadzana jest w czterech trybach sąsiedztwa (++/--/+-/-+), gdzie obliczane jest:

• Lokalne wsparcie delt: Support_local(d') = max_mode max_δ count_mode(δ)
• Powtarzalna masa: Mass_repeat(d') = Σ max(count(δ)-1, 0)
• Prefiksowe wsparcie dla poziomów 128/96/64/32/16

To podejście ujawnia ukryte klastry i lokalne symetrie, niedostępne w analizie globalnej.

Cechy MuSig2

Liniaryzacja zgodna z protokołem

Dla MuSig2 analiza przeprowadzana jest nie na ostatecznym podpisie, lecz na częściowych podpisach z pełnym kontekstem sesji. Kluczowe komponenty:

• Agregowany klucz Q
• Wspólny nonce R
• Współczynniki b, e, a
• Czynniki parzystości g i gacc

Parzystość klucza określana jest jako par_key = g·gacc mod n, co pozwala na poprawną obsługę współrzędnych Y even/odd. Częściowy podpis sprowadzany jest do formy afinicznej poprzez odtworzenie surowego nonce’a z kontekstu sesji.

Kluczowe różnice względem BIP340

• Brak bezpośredniego równania s = k + ed
• Konieczność uwzględnienia agregacji kluczy
• Zależność od parametrów specyficznych dla sesji
• Podwójna obsługa parzystości (klucz + nonce)

To wymaga modyfikacji wszystkich metryk do pracy ze strukturami zgodnymi z protokołem zamiast surowymi danymi.

Co jest ważne

• Membership bridge — obowiązkowy etap filtracji przed analizą
• Metryki kompresji są skuteczne do wykrywania ponownego użycia i wzorców ladder
• Analiza łączności wykrywa lokalne struktury poprzez model dwulistowy
• MuSig2 wymaga osobnej obróbki poprzez kontekst sesji
• Wszystkie wnioski opierają się na mierzalnych właściwościach matematycznych, a nie heurystykach

Praktyczna implementacja

System zaimplementowany jest jako interaktywny stand na GitHub. Kluczowe komponenty:

• Walidator przynależności BIP340
• Generator rodzin afinicznych dla zadanego d'
• Zestaw metryk kompresji/łączności
• Wizualizator geometrii nonce’ów

Przykład obliczania prefiksowego wsparcia:

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())

Artefakty projektu potwierdzają skuteczność metryk na rzeczywistych danych z znanymi podatnościami. Ważne: system nie odzyskuje bezpośrednio kluczy prywatnych, ale dostarcza mierzalne sygnały do dalszej analizy.

To podejście rozszerza zestaw narzędzi kryptografii, przenosząc zadanie z dziedziny zgadywania do dziedziny mierzalnych właściwości matematycznych. Dla programistów oznacza to możliwość weryfikacji jakości generacji nonce’ów i wykrywania ukrytych podatności w implementacjach.

— Editorial Team