r   e   k   l   a   m   a
r   e   k   l   a   m   a

Za kilka lat czeka nas kryptokalipsa? Matematycy i hakerzy wierzą w możliwość złamania algorytmu RSA

Strona główna AktualnościOPROGRAMOWANIE

Gdy w latach 70 zeszłego stulecia Ron Rivest, Adi Shamir i Leonard Adleman (wszyscy z MIT) przedstawili algorytm RSA – pierwszą praktyczną implementację systemu szyfrowania na bazie klucza publicznego, a mniej więcej w tym samym czasie Whitfield Diffie i Martin Hellman pokazali, jak bezpiecznie wymieniać klucze kryptograficzne, wydawało się, że ludzkość dokonała wielkiego postępu. Oto zyskaliśmy system szyfrowania, który mimo całkowitej otwartości miał być całkowicie bezpieczny, jego bezpieczeństwo gwarantowała sama matematyka, trudność faktoryzacji dużych liczb złożonych.

Z perspektywy typowego internetowego hakera czy kryptoanalityka pracującego w jednej z agencji wywiadowczych, algorytmy RSA czy Diffiego-Hellmana wyglądają naprawdę solidnie, a możliwym siłowym atakom (do tej pory największym kluczem, jaki został rozłożony na czynniki pierwsze, jest klucz 768-bitowy – nastąpiło to na przełomie 2009 i 2010 roku) łatwo zaradzić, zwiększając długość klucza (to, jak długość klucza wpływa na odporność na atak, można zobaczyć na stronie www.keylength.com). Rozważania na temat możliwych słabości kryptograficznych algorytmów prowadzone były przede wszystkim w kręgach akademickich, a wiedza z hermetycznego świata matematyków nie przenika wcale łatwo do świata praktyków (zapewne głównie ze względu na poziom trudności matematycznego dyskursu– przepaść między matematyką, a dziedzinami w których elementy Królowej Nauk znajdują zastosowanie pogłębia się z roku na rok).

Niektórzy spośród ludzi zajmujących się bezpieczeństwem IT podejmują wysiłek, by przyjrzeć się osiągnięciom akademickiego świata. Wśród nich jest Alex Stamos, dyrektor techniczny firmy Artemis, który podczas ostatniej konferencji Black Hat przedstawił zebranym stan badań nad technikami szyfrowania stosowanymi w Internecie. Ostrzegł, że istnieje realna szansa na to, że w ciągu najbliższych czterech czy pięciu lat, algorytmy RSA i Diffiego-Hellmana przestaną się nadawać do szyfrowania, a to doprowadzi do całkowitego załamania się mechanizmów zaufania w Internecie.

Stamos nie przesadza – to właśnie kryptografia klucza publicznego i bezpieczne systemy wymiany kluczy zabezpieczają elektroniczną bankowość, umożliwiają wysyłanie poufnych e-maili, czy zdalne aktualizowanie systemów operacyjnych. Jednak z prac francuskiego matematyka Anoine'a Jouxa wynika, że cały ten kryptosystem okaże się trywialnie łatwy do złamania. Poświęcone tej kwestii prace opublikowane zostały na początku 2013 roku. Dotyczą znajdywania logarytmu dyskretnego, dziś uważanego za problem trudny, przez co przekonani do tej pory jesteśmy, że szybkie odszyfrowanie danych nie jest możliwe bez klucza użytego do zaszyfrowania – albo wykorzystania pracujących przez dziesiątki lat superkomputerów, realizujących algorytm ogólnego sita ciała liczbowego.

A jednak z prac Jouxa wynika, że powinny istnieć algorytmy znacznie efektywniejsze niż dziś stosowany do znajdywania logarytmu dyskretnego algorytm Pohliga-Hellmana, radzący sobie szybko jedynie z kryptosystemami, które wykorzystują niewielkie liczby pierwsze. Przez 25 lat prac praktycznie nie poczyniono w tej sprawie żadnego postępu, ale teraz może się to zmienić, tym bardziej że metody wykorzystane przez francuskiego matematyka nie są zupełnie nieznane – po prostu nie stosowano ich wcześniej wobec tych szyfrów. Jarved Samuel, kryptograf pracujący dla firmy ISEC Partner ocenił, że osiągnięcia Jouxa pozwolą innym badaczom przyjrzeć się zagadnieniu bliżej, przynosząc dalszy postęp.

Wydaje się, że poważni gracze przeczuwają już schyłek kryptografii bazującej na liczbach pierwszych. Dowodem na to może być zachowanie amerykańskiej Agencji Bezpieczeństwa Narodowego (NSA), która wydała już w 2005 roku Suite B, oficjalnie rekomendowany zestaw algorytmów do zabezpieczania informacji w biznesie. Usunięto z niego wcześniej rekomendowane algorytmy RSA i Diffiego-Hellmana, zastępując je algorytmami kryptografii na bazie krzywych eliptycznych. Podejrzewa się, że to samo dotyczy zestawu Suite A, wykorzystywanego do zabezpieczania informacji o najwyższym poziomie tajności, dotyczących nomen omen, bezpieczeństwa narodowego, i o którym oficjalnie prawie nic nie wiadomo.

Ta grupa technik kryptografii rozwijana jest od 1985 roku i swoje bezpieczeństwo opiera na złożoności obliczeniowej dyskretnych logarytmów na krzywych eliptycznych (ECC). Algorytmy wykorzystujące krzywe eliptyczne są bardzo szybkie, pozwalają na stosowanie relatywnie niedługich kluczy (256-bitowy klucz ECC jest równoważny mniej więcej 3072-bitowemu kluczowi RSA), a najlepsze algorytmy do ich łamania (np. algorytm rho Pollarda) są znacząco mniej wydajne od algorytmów wykorzystywanych przeciwko RSA.

Nie tylko NSA sięga po krzywe eliptyczne, nawet w naszym kraju kilka lat temu zrobiło się o nich głośno w mass-mediach, z okazji nagrodzenia budowanego przez zespół prof. Gawineckiego „narodowego szyfratora”. Można by się więc spodziewać, że przejście na nowe techniki kryptograficzne nastąpi wręcz automatycznie – ale wcale to nie jest takie pewne. Problem tkwi w patentach dotyczących ECC, należących do firmy Certicom, która zaimplementowała je jako pierwsze. Należący obecnie do BlackBerry Certicom nie ma zamiaru rozdawać je za darmo. Nawet federalna administracja USA musiała wykupić licencje na stosowanie algorytmów zalecanych w Suite B. Gdy Sony wykorzystało ECC w swoich odtwarzaczach Blu-ray, jednocześnie próbując unieważnić część patentów Certicom, sprawa skończyła się sądową ugodą, a Japończycy musieli za licencje zapłacić.

Niektórzy eksperci są przekonani, że jedyną szansą na uniknięcie katastrofy kryptograficznej jest więc unieważnienie patentów Certicomu, przeprowadzone przez samą administrację amerykańską. To wymagałoby jednak zmian w prawie, które uderzałyby w interesy posiadaczy wartych miliardy patentowych portfolio – nie można przecież wydać ustawy, która unieważnia po prostu patenty jednej firmy. Jeśli jednak nawet do zmian w prawie patentowym dojdzie, to trzeba pamiętać o tym, że tzw. biznesowe IT jest wyjątkowo mało zwinne, a wdrażanie nowych technologii zajmuje tam całe lata. O ile opensource'owe społeczności, agencje wywiadowcze czy najlepsze firmy programistyczne z przejściem na ECC sobie poradzą szybko, to inni będą mieli znacznie gorzej.

Aktualizacja

Niestety oryginalny link z pracami francuskiego matematyka nie działa, ale udało się nam znaleźć inne ich źródła:

A new index calculus algorithm with complexity L(1=4 + o(1)) in small characteristic
A quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic

r   e   k   l   a   m   a
© dobreprogramy
r   e   k   l   a   m   a
r   e   k   l   a   m   a

Komentarze

r   e   k   l   a   m   a
r   e   k   l   a   m   a
Czy wiesz, że używamy cookies (ciasteczek)? Dowiedz się więcej o celu ich używania i zmianach ustawień.
Korzystając ze strony i asystenta pobierania wyrażasz zgodę na używanie cookies, zgodnie z aktualnymi ustawieniami przeglądarki.