12:15
15/2/2012

Grupa matematyków i kryptografów odkryła ciekawą słabość generatorów liczb pseudolosowych wykorzystywanych do tworzenia kluczy prywatnych RSA zapewniających bezpieczeństwo transmisji m.in. protokokołu HTTPS czy też bezpiecznej poczty elektronicznej (PGP). Badaczom udało się “odzyskać” 2 klucze prywatne na podstawie 1000 przetestowanych kluczy publicznych.

RSA vs DSA

Badacze poddali testom 7,1 miliona publicznych kluczy RSA (1024 bit), które pozyskali z internetu (m.in. z bazy PGP oraz EFF SSL Observatory). Prawie 27 000 z nich udało się “złamać”, tj. uzyskać na ich podstawie klucz prywatny z pary, za pomocą którego można rozszyfrować wiadomości.

moduli

Badacze zauważają, że ich “eksperyment” może powtórzyć praktycznie każdy — nie jest on skomplikowany. Z tego powodu, przypuszczają, że słabość RSA została już dawno odkryta — wiadomo przecież, że tematyką tą interesują się różnego rodzaju agencje. Na potwierdzenie swoich domysłów przywołują decyzję NIST z 1991 roku, kiedy to zalecono odejście od RSA na rzecz DSA.

Algorytmy (EC)DSA/ElGamal bazują na tylko 1 sekrecie (RSA to tzw. multiple-secret). Badacze wskazują, że odnaleziona przez nich podatność na atak wynika z nieodpowiedniego seedowania generatorów liczb pseudolosowych, na których opiera się bezpieczeństwo RSA.

Wyniki badań zostały opublikowane w tym PDF-ie.

PS. Słabość w generatorze liczb pseudolosowych wykorzystywanym przez Sony pozwoliła m.in. na zhackowanie konsoli PlayStation

Przeczytaj także:



41 komentarzy

Dodaj komentarz
  1. Cóż… Wygląda na to że trzeba będzie zgodzić się na to ryzyko. 2 promile to jeszcze nie taka tragedia (zdecydowanie lepsze szanse niż nie szyfrować w ogóle).

    Pytanie jeszcze jak to jest z dłuższymi kluczami? Od paru lat nie widziałem nikogo kto by używał klucza <4096bit.

    • “Od paru lat nie widziałem nikogo kto by używał klucza <4096bit."
      Nie żartuj.
      mBank – 2048b
      allegro – 2048b
      gmail.com – 1024b

    • Też mnie to rozbawiło właśnie :D, właściwie rzadko widzę żeby ktoś miał 4k, większość ma 1-2k, przykładowo w Debian wheezy/sid apt-key list – 1024 – 9 kluczy, 2048 – 2 klucze, 4096 – 3 klucze.

    • Hmm… fakt, szybki wniosek wysunąłem na podstawie mojej listy kluczy znajomych i ich kluczy PGP, a może ja mam po prostu za małą “próbę” do takiej statystyki.

      Niemniej pytanie pozostaje – czy długość klucza cokolwiek zmienia w przypadku takiego ataku?

  2. W takim razie polecam Sztukę programowania Knutha, Tom II, Algorytmy seminumeryczne, rozdz. 3 Liczby losowe http://pl.wikipedia.org/wiki/Sztuka_programowania

    Jak widać problemem są nie kryptograficzne podstawy RSA, ale lekceważenie znaczenia generatorów liczb PSEUDOlosowych.

    • Dokładnie to samo miałem napisać – przecież to nie jest słabość RSA, tylko słabość generatorów liczb pseudolosowych. W kolejnych wersjach przeglądarek/serwerów WWW trzeba będzie po prostu wprowadzić lepsze generatory…

  3. Ciekawe ile z tych 27000 to np. klucze wygenerowane przez Debiana Etch i jego niesławny “feature”: http://www.debian.org/security/2008/dsa-1571

  4. ja czegoś nie rozumiem. skoro problemem jest generator liczb pseudolosowch, to czy nie wystarczy jedynie wymienić go na dobrze przetestowaną, poprawioną wersję? oczywiście potem wszyscy musieliby wygenerować sobie nowe klucze ;)

    • Co jest trochę dramatyczne, bo klucze to nie tylko podpis i szyfrowanie, również uwierzytelnienie osoby, podpisywanie innych kluczy własnym jako potwierdzenie, że masz pewność, że klucz należy właśnie do tej osoby, wiąże się to zazwyczaj ze spotkaniem w realu z daną osobą :).

    • oczywiście, ten problem jest. niemniej jednak ja tu nie widzę problemu w samym RSA. choć mogę się mylić, nie jestem specem w dziedzinie szyfrowania.

  5. OBWE: ACTA będzie miała wpływ na prawa podstawowe

  6. Jedyne co można tutaj uznać za słabość RSA jest to, że: “Cryptosystems such as RSA that require, during key-setup, multiple secrets are more a fected by the apparent difficulty to generate proper random values than systems such as Diffie-He…llman (cf. [8]), ElGamal, and (EC)DSA that require a single secret.”. Sprowadza się do tego, że dla RSA trudniej w bezpieczny sposób generować klucze bo opierają się na wielu sekretach (ochrona przez lograrytm dyskretny + faktoryzację). Panowie przeanalizowali dostępne w Internecie klucze i znaleźli mnóstwo źle wygenerowanych. Dokładniej chodzi o to, jak jeden podmiot generuje wiele kluczy, które zebrane razem są podatne na analizę.

  7. Ciekawe! Ale nie piszcie, że “RSA gwarantuje tylko x bezpieczeństwa” w tytule, bo (o czym piszecie już w pierwszym zdaniu) odkryta luka nie dotyczy RSA, lecz generatorów liczb pseudolosowych.

    Zachęcam wszystkich do przejrzenia artykułu (sam nie mogę się doczekać pełnej wersji). albo chociaż świetnego podsumowania o tu:
    https://news.ycombinator.com/item?id=3591429
    Również komentarze tam są ciekawe, ot choćby w sprawie tytułu:
    “In case it’s not obvious to everyone: Ron = Ron Rivest (the R in RSA); Whit = Whitfield Diffie (of Diffie-Hellman).”

    • Sformułowanie “RSA gwarantuje X bezpieczeństwa” pochodzi z dokumentu badaczy: “Overall, over
      the data we collected 1024-bit RSA provides 99.8% security at best”.

    • Dodanie “over the data we collected” moim zdaniem istotnie zmienia kontekst; ale to oczywiście detal i w sumie w ogóle mogłem tego nie poruszać. Przede wszystkim dzięki za notkę, linka w atrtykule i drugiego linka w komentarzu. Bardzo inspirujące, na pewno będę śledził temat.

    • sformułowanie “Overall, over the data we collected 1024-bit RSA provides 99.8% security at best”. dotyczy kluczy o długości 1024b a nie algorytmu RSA. Tytuł sugeruje, że chodzi o algorytm.

  8. Być może jest to pokłosie znanej z 2008 roku sprawy poprawek w OpenSSL z Debiana i Ubuntu , które zaaplikowano w wersji 0.9.8c-1 właśnie w generatorze liczb pseudolosowych.

    • Nie, badacze wspominają o tym w swoim dokumencie, i zdaje się, że odfiltrowali te klucze.

  9. PS3 złamano, ale nie było żadnej słabości w generatorze liczb losowych. Generatora zwyczajnie NIE BYŁO. Polecam obejrzeć to: http://mirror.fem-net.de/CCC/27C3/mp4-h264-HQ/27c3-4087-en-console_hacking_2010.mp4 – przy okazji niezła zabawa :)

  10. Jeśli uda się tą metodą odtworzyć klucz prywatny używany przez któreś zaufane centrum certyfikacji, to narażone jest 100% ruchu https.

  11. Cyber KIller.

    Promil to 0.001 %.

    0.2 % to 200 promilów.

    • Procent, to 0,01 całości,
      promil, to 0,001 całości (a nie procenta)
      czyli 1 promil = 0,1%.

    • Racja, ale promili, nie “promilów”.

    • co Ty opowiadasz. promil to 1/1000 czyli 1/10 procenta.

    • Bosh, widzisz i nie grzmisz. Co za Polak z Ciebie skoro nie wiesz ile to promil :D http://pl.wikipedia.org/wiki/Promil

    • Widać, że sami “ścisłowcy” tu piszą. Etymologia słowa:
      procent = pro cent = na sto
      promil = pro mil = na tysiąc

      Tym samym jeden procent = jeden na sto, a jeden promil = jeden na tysiąc.

      I tak sobie to pamiętając od razu wiadomo co i jak.

  12. I tak 99,8 procent lepsze od 0% bezpieczeństwa. No ale podatność ciekawa, nie powiem.

    • tutaj chodzilo o promile w organizmie;)

  13. W temacie – druga grupa researcherów wskazuje embeded devices jako źródło słabych kluczy: https://freedom-to-tinker.com/blog/nadiah/new-research-theres-no-need-panic-over-factorable-keys-just-mind-your-ps-and-qs

  14. Może czas najwyższy aby zaczęli instalować generatory TRNG i to najlepiej wraz z akceleratorami kryptograficznym! Bo tu nie chodziło o słabość samego algorytmu RSA ale o jego (dość kiepską) implementację.

  15. etam. to w sumie najpopularniejszy wektor ataku na implementacje krytpografii (tzn. ataka,
    na generator liczb pseudolosowych, jak sie komus chce to niech obada np, skad
    sie biora rozne klucze, np w trakcie instalacji swierzego systemu, instalacji srodowiska
    zwirtualizowanego (skad wtedy brac entropie jak jestesmy swierzynkami i jeszcze nic
    sie na zewnatrz nie wydazylo takiego zebysmy mieli czym sie seedowac).

    zreszta to i tak malo wazne jest w kontekscie tego ze ta budowla w cernie to dla sciemy
    niby akcelerator co szuka jakiks tam niewidzialnych czasteczek a tak naprawde to komputer kwantowy do faktoryzowania naszych kluczy…

    • Ta… rozumiem że byłeś i sprawdziłeś?

  16. “słabość generatorów liczb pseudolosowych wykorzystywanych do tworzenia kluczy prywatnych RSA”
    Znaczy, że wszytko działa na jednej bibliotece z implementacją generatora?
    Który typ generatora poległ?
    BTW(cpt obvious)
    Co do “sekretów”, to kwestią jest to, że w celu złamania mamy “lub” zamiast “i”.

    • Nie chodzi o biblioteke, ale o generator pseudolosowy, ktory to jest zależny od entropii urządzenia na jakim dziala ~ czyli bardzo zależny od sprzętu.

      Problem nie polega tu na samym RSA, a na sprzęcie na jakim zostały wygenerowane klucze. Najbardziej zrozumiały jest przykład maszyn wirtualnych (vmware) gdzie entropia prawie nie istnieje i wygenerowanie jakichkolwiek kluczy (jakiekolwiek szyfrowanie SSL) na takiej maszynie nawet 4096 mija sie z celem. Dlatego istnieja takie zabawki jak True Random Number Generator na USB itp.

      W firmach gdzie sie dba o bezpieczenstwo no nawet wszelakie klucze sa generowane na osobnych maszynach z wysoka entropia, a potem puppet/cfengine konfiguruje maszyne z odpowiednimi kluczami.

    • @Loku
      To, że sama faktoryzacja nie jest zagrożona to wiem.
      Skoro problem jest powszechny, to znaczy, że to był ten sam(implementacja) generator(czyli jedna biblioteka).
      Co do entropii to różnie bywa, bo są algorytmy korzystające np z odczytów temperatury czy innych tego typu, a poza tym o ile zrozumiałem, to jak coś jest bardzo zależne od sprzętu, to atakujący musiałby ów sprzęt mieć.

    • Zaraz, zaraz. Generator liczb pseudolosowych to algorytm, który generuje deterministyczny (!) ciąg liczb mający jednak cechy ciągu losowego (np. przechodzący różne testy statystyczne). I taki generator nie zależy od sprzętu, na którym jest uruchomiony, bo dla tych samych warunków początkowych (seed) zawsze daje taki sam ciąg liczb.

    • @Paweł
      I właśnie do tego seeda korzysta się z różnych ciężko przewidywalnych(losowych?) rzeczy jak np Tprocesora, szum z mikrofonu itd a to zależy od konkretnego kompa.

    • pamiętam, że swego czasu pojawił się pod Linuksem sterownik do odczytywania losowych liczb z bodajże chipsetu. nie interesowałem się tym, więc nie wiem na czym dokładnie to polega, natomaist nie rozumiem dlaczego takie rozwiązania nie są powszechne, przynajmniej w sprzęcie klasy enterprise? przecież wystarczy jakiś szumiący tranzystor i przetwornik ADC. jakby potem czytać tylko najmłodszy bit lub bity z przetworzonego strumienia to mamy pełną entropię na którą nie da się przewidywalnie wpłynąć czynnikami zewnętrznymi. czy może się mylę? prędkość strumienia rzędu kilku KB/s w zupełności wystarczy w większości zastosowań, a układ i kernel mogą dane buforować by użyć gdy będą potrzebne.

  17. Gdyby tysiąc małp przez tysiąc lat i tak dalej. Jak dla mnie te 2 promile to i tak znikome zagrożenie.
    MD5 z solą też potrafi złamać każdy script kiddie dysponujący tablicami, a ludzie jakoś włosów z głów nie rwą. Ba! taki np. gram.pl ( i witryny powiązane jak np. cdprojekt.pl) trzyma hasła w plaintekście :)

  18. To może zapytam specjalistów ;)

    Jak się sprawdza takie prymitywne darmowe urządzenie, jak plik /dev/urandom – utwrzony w Gentoo Linux (amd64) na kernelu 3.4.2 z procesorem Core 2 duo 2*2.66Ghz?
    Do tego karta Nvidia, tuner tv/dvb, mikrofon, głośniki, i linia tramwajowa przchodząca w odległosci kilkunastu metrów od kompa, za kilkoma ścianami. :D

    Bo w mojej opinii chyba nieźle, ale chętnie posłucham fachowców… ;)

    • Urządzenie /dev/urandom korzysta z entropii generowanej przez kartę sieciową. O ile komputer podpięty jest do sieci i jakikolwiek program coś w tej sieci grzebie to algorytm powinien całkiem dobrze generować liczby losowe (a nie pseudolosowe) jak w przypadku algorytmów deterministycznych.

Twój komentarz

Zamieszczając komentarz akceptujesz regulamin dodawania komentarzy. Przez moderację nie przejdą: wycieczki osobiste, komentarze nie na temat, wulgaryzmy.

RSS dla komentarzy: