Jak działają ataki brute force

Atak brute force na szyfrze polega na wypróbowaniu każdego możliwego klucza aż do znalezienia prawidłowego. Dla klucza o długości n bitów istnieje 2^n możliwych kluczy. W przypadku klucza 3-bitowego istnieje tylko 8 możliwości, natomiast dla klucza 56-bitowego jest ich ponad 72 biliardy. Podstawową obroną przed atakiem brute force jest wybór kluczy na tyle długich, aby wyczerpujące przeszukanie było obliczeniowo niewykonalne w jakimkolwiek praktycznie istotnym czasie.

DES (Data Encryption Standard) używa klucza 56-bitowego, co daje przestrzeń kluczy o rozmiarze około 7,2 * 10^16. W 1977 roku wydawało się to ogromną wartością. W 1998 roku maszyna Deep Crack firmy EFF złamała DES w 56 godzin za 250 000 USD. W 2006 roku wyspecjalizowany klaster mógł złamać DES w mniej niż 9 dni za mniej niż 10 000 USD. Wniosek był jasny: 56 bitów nie zapewniało już wystarczającego bezpieczeństwa przed zmotywowanym przeciwnikiem.

AES-128 używa kluczy 128-bitowych, co daje 2^128 możliwych kluczy, czyli około 3,4 * 10^38. Gdyby każdy atom w obserwowalnym Wszechświecie był komputerem wykonującym miliard testów klucza na sekundę od Wielkiego Wybuchu, przeszukiwanie nadal nie byłoby nawet blisko ukończenia. Nawet przy przyszłym sprzęcie o wykładniczo większej szybkości klucze 128-bitowe powinny pozostać bezpieczne przed klasycznym brute force w dającej się przewidzieć przyszłości.

Ataki brute force online są wymierzone w działające systemy i polegają na wielokrotnym wysyłaniu żądań uwierzytelniania. Ograniczają je opóźnienia sieciowe, czas odpowiedzi serwera i limity liczby żądań, dlatego są powolne. Ataki brute force offline działają na skradzionych danych, takich jak baza hashy haseł. Mając hashe, atakujący może testować miliardy kandydatów na sekundę, korzystając z lokalnego sprzętu i nie podlegając ograniczeniom sieciowym.

Nowoczesne procesory GPU zawierają tysiące rdzeni przetwarzania równoległego zoptymalizowanych pod kątem arytmetyki zmiennoprzecinkowej. Hashcat, wiodące narzędzie do łamania hashy za pomocą GPU, może testować ponad 100 miliardów hashy MD5 na sekundę na jednej wysokiej klasy karcie GPU. Zestaw z ośmioma kartami GPU może testować ponad 800 miliardów kandydatów na sekundę. Sprawia to, że źle dobrane hasła i słabe funkcje hashujące są podatne na szybkie łamanie offline.

Układy scalone do zastosowań specjalnych to układy projektowane wyłącznie do wykonywania jednego rodzaju obliczeń. Górnicy Bitcoin używają układów ASIC, które obliczają hashe SHA-256 z szybkością dziesiątek terahaszy na sekundę, znacznie większą niż w przypadku dowolnego GPU. Chociaż układy ASIC używane w Bitcoinie wykonują inną operację niż łamanie haseł, zasada pozostaje taka sama: sprzęt zaprojektowany do konkretnego zadania zapewnia przy określonych obliczeniach kryptograficznych przyspieszenie o rzędy wielkości w porównaniu ze sprzętem ogólnego przeznaczenia.

Prawo Moore’a mówiło, że gęstość tranzystorów mniej więcej podwaja się co dwa lata, co w przeszłości przynosiło porównywalny wzrost mocy obliczeniowej. Długość klucza uznawana dziś za bezpieczną musi pozostać bezpieczna przez dziesięciolecia przyszłych ulepszeń sprzętu. Dlatego zalecenia dotyczące bezpieczeństwa uwzględniają znaczne marginesy bezpieczeństwa. AES-128 wymagałby 2^64-krotnego przyspieszenia obliczeń, aby stać się podatnym na klasyczny atak brute force, co znacznie przekracza wszelkie realistyczne przewidywania wynikające z prawa Moore’a.

NIST SP 800-57 określa poziomy bezpieczeństwa dla algorytmów kryptograficznych. Bezpieczeństwo na poziomie 112 bitów jest obecnie minimalnym poziomem zalecanym dla nowych systemów. W przypadku długoterminowej ochrony zaleca się poziom 128 bitów. Klucze symetryczne o długości 256 bitów zapewniają margines bezpieczeństwa wykraczający poza obecnie przewidywalne zagrożenia ze strony klasycznych komputerów. NIST odradza poziomy bezpieczeństwa 80-bitowe i niższe, uznawane za niewystarczające dla każdej nowej aplikacji.

Kwantowy algorytm wyszukiwania Grovera zapewnia kwadratowe przyspieszenie w przypadku nieustrukturyzowanego przeszukiwania, co oznacza, że może przeszukać przestrzeń kluczy zawierającą N elementów w około sqrt(N) krokach zamiast N. W przypadku AES-128 efektywny poziom bezpieczeństwa wobec przeciwnika kwantowego zmniejsza się do 64 bitów. W przypadku AES-256 efektywny poziom bezpieczeństwa wobec algorytmu Grovera wynosi 128 bitów, dlatego w celu zapewnienia bezpieczeństwa postkwantowego zaleca się symetryczne klucze 256-bitowe.

Aby zachować 128-bitowy poziom bezpieczeństwa wobec komputera kwantowego uruchamiającego algorytm Grovera, klucze symetryczne muszą mieć co najmniej 256 bitów. AES-256 już ma taką długość i jest uznawany za odporny na ataki kwantowe w przypadku szyfrowania symetrycznego. Dla porównania podwojenie długości klucza ze 128 do 256 bitów nie podwaja kosztu obliczeń po stronie uprawnionego użytkownika (dodaje tylko kilka rund AES), ale wymaga od atakującego podniesienia zasobów kwantowych do kwadratu.

Zespoły ds. bezpieczeństwa używają narzędzi brute force podczas autoryzowanych audytów haseł, aby wykryć słabe dane uwierzytelniające, zanim zrobią to atakujący. Hashcat i John the Ripper uruchamia się przeciwko wyeksportowanym bazom hashy haseł, aby określić, jaki odsetek haseł można złamać. Wyniki audytów pomagają ulepszać politykę haseł: wymagania dotyczące minimalnej długości, zasady złożoności oraz wdrażanie nowoczesnych algorytmów haszowania haseł, takich jak bcrypt lub Argon2.

Atak brute force sprawdza każdy możliwy klucz; bezpieczeństwo wymaga przestrzeni kluczy zbyt dużej, aby można ją było praktycznie wyczerpująco przeszukać. DES z kluczem 56-bitowym został złamany w 1998 roku. AES-128 z przestrzenią 2^128 kluczy jest niewykonalny dla klasycznych komputerów. Klastry GPU łamią hashe offline z szybkością setek miliardów na sekundę. Algorytm kwantowy Grovera zmniejsza bezpieczeństwo mierzone w bitach o połowę, dlatego do uzyskania 128-bitowego bezpieczeństwa postkwantowego wymagane są klucze 256-bitowe. NIST zaleca co najmniej 128-bitowy poziom bezpieczeństwa dla nowych systemów.