Incydent z backdoorem Dual EC DRBG

Dual Elliptic Curve Deterministic Random Bit Generator (Dual EC DRBG) był jednym z czterech mechanizmów DRBG standaryzowanych przez NIST w dokumencie SP 800-90A (2006). Generuje pseudolosowe bity za pomocą dwóch punktów krzywej eliptycznej P i Q: w każdym kroku oblicza r_i = x(s_i * P) (współrzędną x wyniku mnożenia punktu), następnie s_{i+1} = x(r_i * P) aktualizuje stan, a output = x(r_i * Q) generuje bity. Generator wyglądał wiarygodnie w notacji akademickiej. Został uwzględniony w NIST SP 800-90A, a później RSA Security zatwierdziło go jako domyślny generator w swojej bibliotece kryptograficznej BSAFE, co doprowadziło do jego rozpowszechnienia w oprogramowaniu dla przedsiębiorstw i administracji państwowej.

Backdoor w Dual EC DRBG wykorzystuje zależność między P i Q. Jeśli przeciwnik zna tajną wartość skalarną e taką, że Q = e * P, to na podstawie dowolnego bloku danych wyjściowych może obliczyć: z output = x(r * Q) metodą brute force wyznaczyć współrzędną y punktu r*Q, a następnie obliczyć r*P = (1/e) * (r*Q) mod n. Na podstawie r*P może przewidzieć wszystkie przyszłe dane wyjściowe i odzyskać stan wewnętrzny. Znajomość e jest backdoorem — odpowiada logarytmowi dyskretnemu Q względem P. Standard NIST udostępniał wartości P i Q bez wyjaśnienia, w jaki sposób zostały wybrane, przez co nie można było zweryfikować, czy wygenerowano je losowo i bez ukrytego mechanizmu.

W sierpniu 2007 roku Dan Shumow i Niels Ferguson przedstawili podczas sesji Rump Session konferencji CRYPTO przełomowy artykuł zatytułowany "On the Possibility of a Back Door in the NIST SP800-90 Dual Ec Prng." Formalnie wykazali, że jeśli ktoś zna e (ECDLP dla Q względem P), może przewidzieć cały wynik Dual EC DRBG, mając około 32 bajtów danych wyjściowych. Zademonstrowali to na prostym przykładzie. Ich prezentacja spotkała się z dużym zainteresowaniem społeczności kryptograficznej. Bruce Schneier napisał: "nie mamy możliwości stwierdzenia, czy NSA może odczytywać dane wyjściowe Dual_EC_DRBG." Mimo tego ostrzeżenia Dual EC DRBG pozostał w standardzie przez kolejnych sześć lat.

We wrześniu 2013 roku The New York Times, The Guardian i ProPublica opublikowały raporty oparte na dokumentach ujawnionych przez Edwarda Snowdena, z których wynikało, że NSA potajemnie wprowadzała luki w standardach kryptograficznych. Jeden z dokumentów, zatytułowany "Sigint Enabling Project", opisywał program o wartości 250 milionów dolarów rocznie, którego celem było "potajemne wywieranie wpływu" na standardy i produkty szyfrujące. Choć dokument nie wymieniał wprost Dual EC DRBG, w połączeniu z matematyczną demonstracją Shumowa i Fergusona skłoniło to społeczność kryptograficzną do powszechnego wniosku, że NSA umieściła backdoora, wybierając P i Q o znanej zależności e, zachowując e w tajemnicy i przekazując stałe do NIST.

W grudniu 2013 roku Reuters poinformował, że NSA zapłaciła firmie RSA Security 10 milionów dolarów za ustawienie Dual EC DRBG jako domyślnego generatora w zestawie narzędzi kryptograficznych BSAFE firmy RSA. RSA Security, będąca wówczas działem EMC, dostarczała BSAFE w oprogramowaniu korporacyjnym używanym przez instytucje finansowe, firmy z sektora ochrony zdrowia i wykonawców rządowych. W oświadczeniu RSA zaprzeczyła, jakoby świadomie zaimplementowała backdoora, ale przyznała, że zaakceptowała ten kontrakt. To ujawnienie było szczególnie szkodliwe: BSAFE był reklamowany jako produkt zapewniający bezpieczeństwo, a klienci wybierali go właśnie ze względu na gwarancje kryptograficzne. Incydent poważnie zaszkodził reputacji RSA Security i doprowadził do bojkotu konferencji RSA w 2014 roku.

Po ujawnieniach związanych ze Snowdenem NIST podjął kilka działań. We wrześniu 2013 roku NIST ponownie otworzył SP 800-90A na konsultacje publiczne i zalecił, aby w czasie trwania przeglądu nie używać Dual EC DRBG. W kwietniu 2014 roku NIST opublikował SP 800-90A Revision 1, całkowicie usuwając Dual EC DRBG — pozostały w nim wyłącznie Hash_DRBG, HMAC_DRBG i CTR_DRBG. NIST rozpoczął również przegląd wszystkich swoich standardów i wytycznych kryptograficznych, szczególnie analizując, czy wpływ NSA nie naruszył innych standardów. Powołano grupę roboczą NIST Cryptographic Standards and Guidelines Process, aby zwiększyć przejrzystość i udział społeczeństwa w przyszłych działaniach standaryzacyjnych.

Backdoor w Dual EC DRBG miał ogromne konsekwencje dla zaufania społeczności kryptograficznej do instytucji tworzących standardy. Pokazał, że państwowa agencja wywiadowcza była gotowa celowo osłabiać standardy kryptograficzne używane na całym świecie, wpływając nie tylko na przeciwników, lecz także na sojuszników, przedsiębiorstwa i osoby prywatne. Incydent przyspieszył wdrażanie otwartych, możliwych do audytowania algorytmów z liczbami typu "nothing-up-my-sleeve": Keccak używany w SHA-3 wykorzystuje udokumentowany algorytm do wyznaczenia stałych; BLAKE2 i BLAKE3 wyprowadzają stałe z części ułamkowych stałych matematycznych; Curve25519 korzysta z liczby pierwszej (2^255 - 19), wybranej konkretnie po to, aby można było ją zweryfikować. Generowanie parametrów krzywych eliptycznych w sposób "verifiably random" stało się standardową praktyką.

Afera związana z Dual EC DRBG spopularyzowała koncepcję stałych "nothing-up-my-sleeve" (NUMS) — parametrów kryptograficznych generowanych z publicznie weryfikowalnych źródeł, które nie mogą zawierać ukrytych backdoorów. Przykłady: SHA-2 wykorzystuje początkowe wartości skrótu wyprowadzone z pierwiastków kwadratowych pierwszych 8 liczb pierwszych, a stałe rund z pierwiastków sześciennych pierwszych 64 liczb pierwszych. BLAKE2 wyprowadza stałe z rozwinięć ułamkowych liczby pi i innych stałych matematycznych. Ed25519 wykorzystuje liczbę pierwszą 2^255 - 19 oraz punkt bazowy, którego logarytm dyskretny względem dowolnego innego punktu jest dowodliwie nieznany (punkt ten wybrano jako wynik haszowania ciągu znaków). Dzięki tym praktykom każdy może zweryfikować, że stałe nie zostały wybrane na podstawie tajnej wiedzy.

W grudniu 2015 roku Juniper Networks ujawniła, że w systemie ScreenOS (jej systemie operacyjnym dla firewalli) od 2012 roku znajdował się nieautoryzowany kod. Dochodzenie wykazało obecność dwóch backdoorów: jeden zastępował stałą Q algorytmu Dual EC wartością kontrolowaną przez atakującego (umożliwiając atakującemu znającemu odpowiadające jej e odszyfrowywanie ruchu VPN), a drugi znajdował się w haśle administracyjnym SSH. Podmiana Q w Dual EC była szczególnie wyrafinowana: Juniper już wcześniej używał niestandardowej wartości Q, a atakujący zastąpił ją własną wartością, dwukrotnie wykorzystując strukturę backdoora Dual EC. Pokazało to, że nawet implementacje odbiegające od wartości P/Q z NIST mogły zostać zaatakowane przez dowolną osobę, która umieściła w nich własne Q.

Incydent związany z Dual EC DRBG uczy nas kilku rzeczy. (1) Przejrzystość: parametry kryptograficzne muszą mieć weryfikowalne pochodzenie — stałe bez dokumentacji opisującej ich wyprowadzenie należy traktować z podejrzliwością. (2) Projektowanie algorytmów: algorytmy nie powinny mieć struktur, które mogłyby ukrywać backdoory (zależność Q/P w Dual EC nie zapewnia żadnych korzyści bezpieczeństwa w porównaniu z prostszymi konstrukcjami DRBG). (3) Konflikt interesów: instytucje standaryzacyjne muszą rygorystycznie zarządzać konfliktami interesów związanymi z agencjami wywiadowczymi. (4) Przegląd środowiskowy: kryptografowie akademiccy powinni mieć możliwość zgłaszania zastrzeżeń przed opublikowaniem standardów, a nie dopiero po nim. (5) Czujność podczas wdrażania: organizacje powinny sprawdzać, których DRBG używają ich biblioteki kryptograficzne, i z wyprzedzeniem usuwać opcje, których użycie nie jest zalecane.

Po usunięciu Dual EC zalecane rozwiązania DRBG skupiły się wokół Hash_DRBG, HMAC_DRBG i CTR_DRBG. Społeczność open source przyjęła również DRBG spoza standardów NIST w kontekstach, w których standardom NIST się nie ufa: generatory RNG oparte na ChaCha20 (używane w jądrze Linux od wersji 5.17, w OpenBSD i libsodium) są powszechnie uznawane za odporne na backdoory, ponieważ ChaCha20 jest prostym szyfrem strumieniowym bez struktur backdoorów. Fortuna (używana we FreeBSD i starszych wersjach macOS) powstała przed SP 800-90A i nadal cieszy się zaufaniem. Incydent związany z Dual EC odnowił również zainteresowanie sprzętowymi generatorami RNG (RDRAND) jako źródłami entropii — choć RDRAND także spotkał się z zarzutami dotyczącymi możliwości umieszczenia backdoora, co doprowadziło do zaleceń, aby łączyć RDRAND z entropią programową, zamiast używać go wyłącznie.

Jaka zależność matematyczna umożliwia działanie backdoora w Dual EC DRBG?

Dual EC DRBG został ustandaryzowany w NIST SP 800-90A w 2006 roku. W 2007 roku Shumow i Ferguson wykazali, że znajomość e (gdzie Q=e*P) pozwala przewidzieć wszystkie dane wyjściowe na podstawie 32 bajtów. Wycieki dokumentów Snowdena w 2013 roku potwierdziły wpływ NSA na standardy kryptograficzne. Według doniesień RSA Security otrzymała 10 milionów dolarów za ustawienie Dual EC jako domyślnego generatora w BSAFE. NIST usunął Dual EC w SP 800-90A Revision 1 (2014). Incydent Juniper z 2015 roku pokazał, że backdoor został wykorzystany w rzeczywistym produkcie. Wnioski: stałe NUMS, przejrzyste wyprowadzanie parametrów, zarządzanie konfliktami interesów oraz procesy audytu po ustanowieniu standardu. Generatory RNG oparte na ChaCha20 wyłoniły się jako zaufana alternatywa.