Klucz RSA 4096 bitów niby złamany, ale nie ma powodów do niepokoju

dodał 17 maja 2015 o 21:33 w kategorii Krypto  z tagami:
Klucz RSA 4096 bitów niby złamany, ale nie ma powodów do niepokoju

(źródło: takacsi75)

Badacze ogłosili, że ku swojemu zaskoczeniu złamali właśnie klucz RSA o długości 4096 bitów, należący do jednego z najważniejszych programistów jądra Linuks. Jest to jednak – z wielu powodów – bardziej ciekawostka, niż powód do zmartwienia.

Autorzy projektu „Phuctor: The RSA Super Collider.” właśnie poinformowali, że stworzony przez nich system odkrył fatalny błąd w kluczu PGP Hansa Petera Anvina, programisty znanego ze stworzenia wielu funkcji jądra Linuks. Przyczyny powstanie błędu są nieznane, ale jego skutkiem jest trywialna możliwość złamania bezpieczeństwa klucza. Nie wszystko jednak w tej sprawie jest jasne.

Liczba pierwsza podzielna przez 77 (i 3)

Zanim rzucicie się do pisania komentarzy o treści „tytuł pierwszego akapitu zawiera błąd logiczny” przeczytajcie wyjaśnienie. Siłę algorytmu RSA zapewnia matematyka. Jego podstawowa konstrukcja opiera się na tzw. problemie faktoryzacji iloczynów liczb pierwszych. O ile łatwo jest pomnożyć przez siebie dwie liczby pierwsze, takie jak np. 65537 i 65539, o tyle ustalenie, wynikiem jakiego mnożenia jest liczba 4295229443 zajmuje znacząco więcej czasu. Można próbować dzielić 4295229443 przez wszystkie kolejne liczby, jednak to bardzo pracochłonne zajęcie. Można także skorzystać z algorytmu sita kwadratowego (dla liczb krótszych niż 150 cyfr dziesiętnych) lub algorytmu GNFS (dla liczb większych niż 100 cyfr dziesiętnych), jednak dla liczb dłuższych niż ok. 232 liczby dziesiętne (768 bitów) te ataki stają się całkowicie nieprzydatne – czas ich trwania rośnie wykładniczo wraz z długością atakowanej liczby.

Jak zatem udał się atak na klucz o długości 4096 bitów? Badacze nie wierzyli temu, co zobaczyli. Okazuje się, że w badanym kluczu jedna z liczb pierwszych, składających się na iloczyn, była zaskakująco mała – i do tego nie była liczbą pierwszą. Algorytm badaczy odkrył, że dla tego klucza iloczyn jest podzielny przez liczbę 231 (która sama jest podzielna przez 3 i 77).

817023023960376946633975507110154649249407598806798730414849884461776172171921668594148071323527016137506405823108520062504849249423700259406905313281403901410082762097159560221463048924336192384026777502177262731045200322200149773127502888545234973139480887644585192600631058962876114156934248895171959246969597637127280010272143593885240940877456234662196130491400738438731832514335353824697930453078426722191105157568392826870043655708008545411143367763836566011740499383456592129662585004880376777597714978023542434421914201119537685489173509942329090631662014650033142642110914360849421856179611226450806562235534802516081595259914768497444702718749402330070488028751073730349460752771915484847399385631524708487646079936572410398967582895983187640798072309362094727654167628620105981459021548290415800096769214437425690934372015628796027498219902441288189398386359846661623243493534897411417685435424010451956954083531228374002591372549525280610594684910812811287436481207089763125424247793044043309737269468709710679872269272855389945385386467765509880648929743498214329578288874987193768439353382305260108425688024147656806932474058888992099083804597481699305852902662863062054067183925164590726103552998367994727700722491707 `mod` 231 = 0

Oznacza to, ze dla tego konkretnego klucza publicznego można bez problemu obliczyć wartości potrzebne do wygenerowania klucza prywatnego. Klucz zatem jest złamany, ale trzeba jeszcze odpowiedzieć na kilka zaj… errr bardzo ważnych pytań.

Losowy obrazek z kluczami (źródło: bohman

Losowy obrazek z kluczami (źródło: bohman)

To tak można generować klucze?

Czy generatory kluczy PGP/GPG powinny dopuszczać do takich sytuacji, że jedna z liczb pierwszych jest śmiesznie mała? I do tego nie jest liczbą pierwszą? Odpowiedź brzmi oczywiście: NIE. Nie wiemy, jak ten klucz został wygenerowany. Możliwe scenariusze to:

  • wyjątkowo słaby generator liczb pseudolosowych/losowych
  • niski poziom entropii zasilającej generator
  • fatalna implementacja generowania kluczy, która nie potrafi wykryć takich przypadków i ich odrzucić
  • celowe działanie wroga (tylna furtka)
  • celowe działanie trolla (o tym za chwilę).

Tak czy inaczej, pojawienie się takich wartości w kluczu RSA nie powinno mieć miejsca. Sam algorytm RSA nie jest tym odkryciem zagrożony – jedyne ryzyko wiąże się z tym, że być może tak błędnie wygenerowanych kluczy jest gdzieś więcej. Już wcześniejsze badania wykazywały, że źle wygenerowanych klucz nie brakuje w sieci.

Troll miesiąca?

Wiadomość o odkryciu szybko obiegła tę część internetu, gdzie nikt nie śpi bo pilnuje swoich kluczy i wzbudziła zrozumiałe obawy i wątpliwości ekspertów. Eksperci przystąpili zatem do własnych eksperymentów i ustalili, że:

  • klucz ten jest jednym z pod-kluczy klucza głównego Hansa Petera Anvina,
  • z trzech pod-kluczy akurat ten jeden nie jest przez niego podpisany,
  • nie we wszystkich źródłach, z których klucz Anvina można pobrać, klucz ten wygląda identycznie.
gpg --verbose --keyserver hkp://hkps.pool.sks-keyservers.net --recv-key 0xbda06085493bace4
  gpg: requesting key 0xBDA06085493BACE4 from hkp server hkps.pool.sks-keyservers.net
  gpg: armor header: Version: SKS 1.1.5
  gpg: armor header: Comment: Hostname: keyserver.witopia.net
  gpg: pub  4096R/0xBDA06085493BACE4 2011-09-22  H. Peter Anvin <[email protected]>
  gpg: key 0xBDA06085493BACE4: invalid subkey binding
  gpg: key 0xBDA06085493BACE4: skipped subkey
  gpg: key 0xBDA06085493BACE4: "H. Peter Anvin (hpa) <[email protected]>" not changed
  gpg: Total number processed: 1
  gpg:              unchanged: 1

Wygląda zatem na to, że mamy raczej do czynienia z prawie udanym atakiem na system dystrybucji kluczy niż z atakiem na algorytm RSA. Autorzy badania utrzymują, że klucz do testu pobrali z publicznego, zaufanego źródła. Jak zatem tam się znalazł? Czekamy na aktualizacje. Na razie śpijcie spokojnie, Wasze klucze są nie do złamania (przynajmniej oficjalnie). Polecamy także wątek na Hacker News.