Atak brute force

Atak brute force – technika łamania haseł lub kluczy kryptograficznych polegająca na sprawdzeniu wszystkich możliwych kombinacji^[1].

Jest to prosta metoda pozwalająca w teorii na odgadnięcie każdego klucza. Metoda ta ma jednak dużą złożoność obliczeniową, w związku z czym dla odpowiednio długich kluczy złamanie klucza tą metodą jest praktycznie niemożliwe^[1].

Jako atak kryptologiczny

Ta sekcja od 2013-06 wymaga zweryfikowania podanych informacji. Należy podać wiarygodne źródła, najlepiej w formie przypisów bibliograficznych. Część lub nawet wszystkie informacje w sekcji mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte. Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tej sekcji. Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tej sekcji.

W kryptologii brute force to metoda, w której wypróbowywane są wszystkie możliwe kombinacje cyfr, liter i innych znaków kodu ASCII (klucze), do momentu, aż klucz pasujący do szyfru zostanie znaleziony, czyli otrzymana zostanie informacja w postaci jawnej, odszyfrowanej.

Atak może przykładowo polegać na tym, że komputer sprawdzi wszystkie możliwe kombinacje kluczy od 000 000 000 do 999 999 999, przy założeniu, że klucz składa się jedynie z dziewięciu cyfr.

Atak brute-force może być przeprowadzony wobec prawie wszystkich szyfrów symetrycznych i szyfrów asymetrycznych. Szczególnie jeśli znanych jest kilka par tekst jawny-szyfrogram (atak ze znanym tekstem jawnym) lub jeśli znana jest część szyfrogramu (Atak z szyfrogramem) i możliwe jest rozróżnienie poprawnego tekstu jawnego od niepoprawnego. Na przykład jeśli wiadomo, że tekst jawny jest dokumentem HTML, to w większości szyfrów praktycznie wszystkie złe klucze generować będą przypadkowe dane, a ten klucz, który wygeneruje dokument HTML, będzie prawdopodobnie kluczem poprawnym. Weryfikację poprawności odszyfrowanego tekstu jawnego umożliwia skrót MD5 tekstu jawnego wiadomości, której szyfrogram łamany. Oczywiście, gdy skrót MD5 dla wiadomości jest znany.

Na atak brute-force całkowicie odporny jest szyfr z kluczem jednorazowym wykorzystujący szyfrowanie XOR lub polialfabetyczne.

Szczególnie dużego znaczenia nabiera metoda brute-force, jeśli z powodu wyboru niewłaściwej metody generacji klucza, przestrzeń możliwych kluczy zostaje zawężona do pewnego podzbioru. Na przykład jeśli podczas wyboru hasła, zamiast stosować wszelkie możliwe kombinacje liter, cyfr i znaków, których liczba dla sześciu znaków hasła wynosi ok. ${\displaystyle 36^{6},}$ zbiór kombinacji ograniczony zostanie tylko do haseł będących zdrobnieniami nazw klubów piłkarskich, których w Polsce jest kilkaset. Jeśli atakujący potrafi ocenić jaką metodę generacji kluczy wybrał szyfrujący, nawet zastosowanie formalnie bezpiecznego algorytmu szyfrowania nie zabezpiecza przed atakiem brute-force.

Ciekawym aspektem odporności na atak brute force jest następująca cecha: algorytm szyfrowania jest tym odporniejszy na atak brute force im wolniej działa. Jeśli zatem zaszyfrowanie nawet niewielkiego jawnego komunikatu wymaga dużej aktywności obliczeniowej i czasu np. rzędu 1 s, to atak brute force usiłujący sprawdzić wynik szyfrowania tekstu jawnego w celu odgadnięcia klucza straci nieporównanie więcej czasu przeszukując zbiór możliwych kluczy, niż w wypadku szybkiego algorytmu. Z punktu widzenia użytkownika niska szybkość szyfrowania może wydawać się wadą, a w pewnych wypadkach nawet ograniczać możliwość użycia algorytmu (np. szyfrowanie transmisji dźwięku).

Atak taki jest wykonywalny np. wobec algorytmu DES.

Potencjalny czas łamania szyfrów

Szybkość ataku zależy tylko od złożoności pojedynczej operacji ${\displaystyle T}$ i długości klucza ${\displaystyle k}$ i wynosi w najgorszym wypadku:

${\displaystyle 2^{k}T.}$

Statystycznie klucz znaleziony zostanie po połowie prób, czyli oczekiwany czas to:

${\displaystyle 2^{k-1}T.}$

Na przykład jeśli klucz ma 32 bity i jedna próba trwa milionową część sekundy, to łamanie potrwa średnio:

${\displaystyle \mathrm {2^{31}10^{-6}\ s\approx 2147\ s\approx 36\ min} ,}$ czyli nieco ponad pół godziny.

Jeśli klucz ma 48 bitów i używamy 1000 komputerów, z których każdy potrafi wykonać milion prób na sekundę, to czas łamania wynosi:

${\displaystyle \mathrm {2^{47}10^{-3}10^{-6}\ s\approx 39\ h} ,}$ czyli półtora dnia.

Łamanie 56-bitowego szyfru (np. DES) na tym samym sprzęcie trwałoby:

${\displaystyle \mathrm {2^{55}10^{-3}10^{-6}\ s\approx 417\ dni} .}$

Łamanie 128-bitowego szyfru (AES) na milionie komputerów, każdym potrafiącym wykonać miliard prób na sekundę zajęłoby:

${\displaystyle 2^{127}10^{-6}10^{-9}\mathrm {s} \approx 5{,}4\cdot 10^{15}}$ lat, co daje wartość blisko 400 000 razy większą niż czas życia wszechświata (który wynosi niecałe 14 miliardów lat).

Metody zabezpieczeń

Prostą metodą zabezpieczenia przed atakiem brute force jest ograniczanie możliwej liczby prób logowania w określonym czasie, co znacznie wydłuża czas działania algorytmu^[1].

Inną metodą stosowaną powszechnie na stronach internetowych, jest dodatkowe włączenie wszelkiej maści kodów obrazkowych itp. (tzw. Captcha) np. po pierwszych trzech nieudanych logowaniach.

Zobacz też

• atak słownikowy
• wyszukiwanie wyczerpujące

Przypisy