Błędy w implementacji krzywej FourQ od Cloudflare pozwalały na odzyskanie klucza prywatnego [CVE-2025-8556]

Na początku października 2025 r. badacze bezpieczeństwa z firmy Botanica Technologists opublikowali raport z analizy audytu OSS (Open Source Software) Elliptic Curve. Wyniki badań są niepokojące, ponieważ został wykryty szereg błędów kryptograficznych, związanych z nieprawidłową implementacją krzywej eliptycznej FourQ w bibliotece CIRCL (Cloudflare Interoperable, Reusable Cryptographic Library). Jeden z błędów mógł nawet doprowadzić do ujawnienia klucza prywatnego w protokole ECDH (Elliptic Curve Diffie-Hellman). 

TLDR:

• Badacze bezpieczeństwa z firmy Botanica Technologists opublikowali raport z analizy bezpieczeństwa implementacji krzywej eliptycznej FourQ w bibliotece CIRCL od Cloudflare. 
• Wykryte podatności budzą niepokój, ponieważ pozwalały na odtworzenie klucza prywatnego podczas ustalania wspólnego sekretu w protokole Elliptic Curve Diffie-Hellman (ECDH).
• Atak wykorzystuje technikę invalid point attack (użycie nieprawidłowych punktów), polegającą na wysłaniu do serwera specjalnie spreparowanych punktów, nie należących do krzywej eliptycznej FourQ.
• Atak był możliwy do przeprowadzenia, z uwagi na nieprawidłową walidację punktów na różnych etapach obliczeń, tj.: deserializacji punktu, porównania punktów, mnożenia przez kofaktor oraz mnożenia skalarnego.
• Podatność została oznaczona jako CVE-2025-8556. 
• Cloudflare naprawił wykryte błędy w wersji 1.6.1 biblioteki CIRCL.

Biblioteka kryptograficzna CIRCL została opracowana i rozwijana przez zespół Cloudflare Research jako projekt open source. Zawiera implementację popularnych algorytmów i protokołów kryptograficznych, w tym rozwiązań postkwantowych (m.in.: Kyber, Dilithium) oraz klasycznej kryptografii bazującej na  krzywych eliptycznych (FourQ). Krzywa eliptyczna FourQ została zaprojektowana przez Microsoft Research, głównie pod kątem opracowania efektywnego rozwiązania, dedykowanego do wymiany kluczy ECDH i podpisów cyfrowych. Oferuje poziom bezpieczeństwa na poziomie 128 bitów. Została zdefiniowana w postaci skręconej krzywej Edwardsa (twisted Edwards) nad ciałem GF(p²), gdzie p = 2¹²⁷ – 1 jest liczbą pierwszą Mersenne’a. Wzór definiującą krzywą wygląda następująco:

E: -x² +y² = 1 + dx²y²

Liczby Marsenne’a charakteryzują się efektywną arytmetyką modularną, co sprawia że znalazły szerokie zastosowanie w kryptografii. Ich specjalna postać binarna (2^p – 1) znacząco przyspiesza operacje modularne w stosunku do krzywych eliptycznych postaci NIST.

​Na czym więc polegał błąd?

Tak jak często bywa, błędem nie okazała się matematyka, jednak problemy implementacyjne. W tym przypadku weryfikacja punktu na krzywej eliptycznej, przed rozpoczęciem drugiego etapu protokołu ECDH, czyli ustalenie wspólnego sekretu. Zanim jednak wyjaśnimy jakie ten błąd ma znaczenie, należy wspomnieć o arytmetyce na krzywej eliptycznej.

Operacjami realizowanymi na krzywych eliptycznych są dodawanie, podwojenie oraz wyznaczanie krotności punktu, czyli iteracyjne dodawanie do siebie tego samego punktu. Wszelkie operacje realizowane są w ciele liczb skończonych, a co za tym idzie, dodając do siebie ten sam punkt n razy, mamy pewność, że żaden punkt się nie powtórzy i za każdym razem otrzymamy inne wartości. Świadczy o tym parametr zdefiniowany jako rząd punktu. W tym momencie należy rozróżnić rząd grupy punktów na krzywej eliptycznej od rzędu krzywej eliptycznej. Rząd krzywej eliptycznej jest parametrem mówiącym ile punktów rzeczywiście znajduje się na krzywej eliptycznej. Warto jeszcze dodać, że rząd grupy punktów na krzywej eliptycznej FourQ składa się z 392*q, gdzie q jest dużym czynnikiem pierwszym reprezentującym bezpieczną podgrupę punktów.

Po zdefiniowaniu operacji arytmetycznych na krzywych eliptycznych, można przystąpić do opisu protokołu ECDH. Protokół ECDH służy do ustalenia wspólnego sekretu pomiędzy stronami A i B. Składa się z dwóch etapów, w pierwszy kroku zarówno strona A jak i strona B wyznaczają klucz publiczny postaci: Q_A=[k_A]G oraz Q_B=[k_B]G. Kluczem prywatnym jest odpowiednio k_A oraz k_B. W następnym kroku strony wymieniają się kluczami publicznymi, a następnie realizują analogiczną operację na punktach otrzymanych od rozmówcy. W tym momencie przeprowadzając operację:

Strona A: Q=[k_A]Q_B=[k_A*k_B]G=(x_k,y_k,1),

Strona B: Q=[k_B]Q_A=[k_B*k_A]G=(x_k,y_k,1),

strony otrzymają ten sam punkt – wspólny sekret. Dzieje się tak na skutek przemienności operacji mnożenia. 

Przechodząc do sedna, może się okazać, że grupa punktów krzywej eliptycznej o rzędzie n składa się z podgrup, będących dzielnikami rzędu n. W kontekście ataków z użyciem nieprawidłowych punktów, atakujący może wybrać punkt należący do krzywej eliptycznej o innej strukturze grupowej, składającej się z małych czynników pierwszych. W tej sytuacji, używając punktu generującego tę podgrupę można częściowo odzyskać tajny klucz metodą brute force, a następnie korzystając z Chińskiego Twierdzenia o Resztach odzyskać sekret.

Implementacja arytmetyki na krzywej eliptycznej FourQ była właśnie podatna na tego typu atak (w obecnej wersji podatność ta została załatana). Atakujący mógł skonstruować specjalny punkt postaci (0,y), który nie należał do krzywej eliptycznej FourQ, ale był błędnie akceptowany przez funkcje walidacyjne. W efekcie podczas drugiego etapu protokołu ECDH, wyznaczanie k-tej krotności punktu (0, y^k), spowodowało ujawnienie częściowej informacji o kluczu prywatnym. Powtarzając powyższą czynność l-razy, atakujący był w stanie odtworzyć tajny sekret.

W tym momencie warto wspomnieć o specjalnej postaci punktu użytego do przeprowadzenia ataku. Krzywa FourQ została zdefiniowana w postaci Edwardsa, a co za tym idzie formuły matematyczne do dodawania punktu, związane są ze współrzędna x jako zmienną użytą w wielu miejscach. Założenie, że x=0 skutkuje uproszczeniem formuły dodawania punktu, a wyznaczenie k-tej krotności sprowadza się do obliczenia y^k. Biorąc pod uwagę powyższy fakt, wynikowym punktem jest punkt (0,y^k), a co za tym idzie zamiast wykonywania złożonych operacji związanych z wyznaczaniem logarytmu dyskretnego w grupie punktów krzywej eliptycznej, atakujący operuje w grupie multiplikatywnej ciała skończonego o stosunkowo niskim rzędzie, podatnym na ataki typu brute force.

CVE-2025-8556

Oprócz ww. błędu wykryto jeszcze inne nieprawidłowości, związane z:

• metodą weryfikacji, czy dwa punkty są sobie równe. Implementacja przewidywała porównanie współrzędnych punktu X, Y oraz Z (w przypadku reprezentacji punktów w postaci afinicznej, współrzędna Z=1). Jeśli współrzędna Z punktu G przyjmie wartość 0 funkcja pointR1.isEqual zawsze zwraca wartość true, niezależnie od wartości parametrów x i y.
• brakiem weryfikacji czy punkt po wykonaniu funkcji ClearCofactor znajduje się na krzywej. Funkcja ta polega na pomnożeniu punktu przez kofaktor 392 (specyficzny dla krzywej FourQ). Jeżeli  wynikiem operacji jest punkt w nieskończoności (element neutralny grupy), oznaczałoby to, że oryginalny punkt miał mały rząd, a co za tym idzie należałoby go odrzucić, a procedura ustalania wspólnego sekretu powinna zostać przerwana. Implementacja w CIRCL dopuszczała użycie niebezpiecznych punktów, a co za tym idzie atakujący mógł użyć punktów o małych rzędach i w ten sposób podjąć próbę odzyskania klucza prywatnego.
• błędną walidacją danych w funkcji Point.Unmarshal podczas deserializacji punktu. Krzywa eliptyczna FourQ używa dwóch form krzywej Edwardsa (twisted oraz untwisted), a co za tym idzie punkty krzywej eliptycznej muszą zostać przekształcone w odpowiedni sposób przed rozpoczęciem operacji arytmetycznych. Błąd polegał na tym, że funkcja wykonywała operację transformacji punktów, jednak nie weryfikowała czy punkt rzeczywiście należy do oczekiwanej krzywej. Atakujący mógł więc wysłać punkt, który po transformacji nie znajdował się na danej krzywej eliptycznej i w ten sposób, podobnie jak w przypadku ClearCofactor, podjąć próbę odzyskania klucza prywatnego.

Wykryta podatność została zgłoszona w marcu 2025 r. poprzez program BugBounty w serwisie HackerOne. Niestety, reakcja zespołu nie była zbyt entuzjastyczna. Dopiero nawiązanie bezpośredniego kontaktu z Cloudflare spowodowało podjęcie prac nad wdrożeniem poprawek. Obecnie, w wersji 1.6.1 biblioteki CIRCL błędy zostały wyeliminowane. Wykryte luki bezpieczeństwa otrzymały identyfikator CVE-2025-8556.

Co ciekawe, podatność otrzymała stosunkowo niską ocenę CVSS 3.7 (low), mimo iż teoretycznie pozwala na odzyskanie klucza prywatnego. Najprawdopodobniej wynik ten jest podyktowany wysoką złożonością ataku oraz konieczności aktywnego udziału napastnika w procesie negocjacji klucza. W praktyce luka ta jest trudna do wykorzystania, jednak jej skutki mogą być się poważne.

Źródło: botanica.software, github/cloudflare

~_secmike