Atak brute force
[edytuj]
Z Wikipedii
Skocz do: nawigacji, szukaj
Ujednoznacznienie
Ten artykuł dotyczy brute force. Zobacz też: Brute Force - gra wideo z 2003.
Brute force (ang. "brutalna siła") – określenie algorytmu, który opiera się na sukcesywnym sprawdzeniu wszystkich możliwych kombinacji w poszukiwaniu rozwiązania problemu, zamiast skupiać się na jego szczegółowej analizie.
Jest to zwykle nieoptymalna, ale najprostsza do zaimplementowania i najbardziej skuteczna metoda postępowania (ponieważ teoretycznie pozwala ona złamać każde hasło - praktycznie może to potrwać nawet tysiące i miliony lat). W zależności od kontekstu, w którym termin brute force zostaje użyty, może mieć on nieznacznie różne definicje.
Spis treści
[ukryj]
* 1 W programowaniu
* 2 W bezpieczeństwie komputerowym
* 3 Jako atak kryptograficzny
* 4 Przykładowy program brute-force w C
W programowaniu [edytuj]
W slangu programistycznym, termin ten odnosi się do dowolnego algorytmu, który rozwiązuje problemy przez weryfikację i ocenę wszystkich wariantów postępowania, na przykład wszystkich możliwych ścieżek między dwoma punktami, by wybrać optymalną trasę poruszania się postaci w grze komputerowej.
W bezpieczeństwie komputerowym [edytuj]
W bezpieczeństwie, pojęcie ataku brute force używane jest do opisania przeprowadzanych przez człowieka lub program komputerowy prób przełamania zabezpieczeń – na przykład odgadnięcia hasła – przez sukcesywne sprawdzanie wszystkich możliwości.
Jako atak kryptograficzny [edytuj]
W kryptologii, przykład zastosowania algorytmu 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.
Im więcej kombinacji jest możliwych, tym wykonywanie ataku brute force jest dłuższe. Na przykład, jeśli długość klucza wynosi 10120 (1 ze 120 zerami) cyfr, zwykły komputer kryptograficzny sprawdzałby wszystkie kombinacje przez około 19 lat. Jeszcze dłużej trwałby atak tego typu, w przypadku klucza składającego się z cyfr, liter oraz innych znaków ASCII, pochodzących np. z alfabetów innych niż łaciński. Rozwiązując ten problem, kryptolodzy budują coraz szybsze i wydajniejsze komputery, wykonujące atak brute force w krótkim czasie, np. w ciągu kilka minut.
Atak brute-force może być przeprowadzony wobec 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 ze znanym 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.
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. 636, zbiór kombinacji ograniczony zostanie tylko do haseł będących zdrobnieniami nazw klubów piłkarskich, których w Polsce jest kilkadziesiąt. 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.
Szybkość ataku zależy tylko od złożoności pojedynczej operacji T i długości klucza k i wynosi w najgorszym wypadku:
2kT
Statystycznie klucz znaleziony zostanie po połowie prób, czyli oczekiwany czas to:
2k − 1T
Na przykład jeśli klucz ma 32 bity i jedna próba trwa milionową część sekundy, to łamanie potrwa średnio:
2^{31} 10^{-6} s \approx 2147 s \approx 36 m, 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:
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:
2^{55} 10^{-3} 10^{-6} s \approx 416 dni
Łamanie 128-bitowego szyfru (AES) na milionie komputerów, każdym potrafiącym wykonać miliard prób na sekundę zajęłoby:
2^{127} 10^{-6} 10^{-9} s \approx 11 milionów miliardów lat,
czyli ok. 500 tysięcy czasów życia wszechświata (przyjmując, że ma 20 miliardów lat).
Przykładowy program brute-force w C [edytuj]
#include <stdio.h>
#include <string.h>
#define CHARS 26
#define MAX_LEN 5
char sChars[CHARS];
char *sHaslo = "haslo";
// Można tu oczywiście dodać więcej zakresów znaków (nawet całe ASCII)
void prepare_chars()
{
for (char i=0; i<CHARS; i++)
sChars[i] = 'a'+i;
}
// To można zastąpić dowolną funkcją sprawdzającą dane hasło
void test_password(char *sPassword)
if (!strcmp(sPassword, sHaslo))
printf("Zgadnieto haslo! (%s=%s)\n", sPassword, sHaslo); // i prawdopodobnie: zakończ program
void brute(char *sString, int nLen, char *sPoczatek)
if (nLen == 0)
test_password(sPoczatek);
else
for (int i=0; i<CHARS; i++)
sString[0] = sChars[i];
brute(sString+1, nLen-1, sPoczatek);
int main()
prepare_chars();
char sString[MAX_LEN + 1];
sString[MAX_LEN] = 0;
brute(sString, MAX_LEN, sString);
Scorpik