Ten artykuł dotyczy Algorytmu metodą Brute Force. Sprawdź też: Brute force – inne znaczenia.

Algorytm siłowy, algorytm brute force (ang. "brutalna siła" tj. niewspomagana umysłem) – określenie algorytmu, który ma za podstawę 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 oraz najbardziej skuteczna metoda postępowania (ponieważ teoretycznie dopuszcza ona złamać każde hasło – praktycznie może to potrwać nawet tysiące oraz miliony lat). W zależności od kontekstu, w którym termin brute force zostaje użyty, może posiadać on nieznacznie zróżnicowane definicje.

W programowaniu

W slangu programistycznym, termin ten odnosi się do dowolnego algorytmu, który rozwiązuje problemy przez weryfikację oraz ocenę wszystkich wariantów postępowania, dla przykładu wszystkich możliwych ścieżek pomiędzy dwoma punktami, by wybrać optymalną trasę poruszania się postaci w grze komputerowej.

W bezpieczeństwie komputerowym

W bezpieczeństwie pojęcie ataku brute force używane jest do opisania przeprowadzanych przez człowieka albo program komputerowy prób przełamania zabezpieczeń – dla przykładu odgadnięcia hasła – przez sukcesywne sprawdzanie wszystkich możliwości.

Przykładowy kod w języku Python (porównuje hash wszystkich kombinacji z zestawu znaków tab z podanym hashem dla podanej soli - salt; wykorzystuje funkcję crypt):

from crypt import *
from datetime import datetime
import itertools
import string
 
hash="A1sFDi3eZIVkM"
salt="A1"
 
tab=string.ascii_lowercase+string.digits+string.ascii_uppercase
print "Zestaw znakow: "
print tab
 
brejk=False
 
d1=datetime.now()
for oraz in range(1,8):
        print "Sprawdzam dla liczby znakow rownej %d" % (i)
        kombinacje=itertools.product(tab, repeat = i)
        for slowo in kombinacje:
                haslo="".join(slowo)
                if crypt(haslo,salt)==hash:
                        print "Haslo: %s" % haslo
                        brejk=True
                        break
        if brejk:
                break
d2=datetime.now()
d=d2-d1
 
print d

Jako atak kryptologiczny

W kryptologii, przykład zastosowania algorytmu brute force to metoda, w której wypróbowywane są wszystkie możliwe kombinacje cyfr, liter oraz 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 opierać się 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ę zaledwie z dziewięciu cyfr.

Atak brute-force bywa przeprowadzony wobec prawie wszystkich szyfrów symetrycznych oraz szyfrów asymetrycznych. Szczególnie jeśli znanych jest parę par tekst jawny-szyfrogram (atak ze znanym tekstem jawnym) albo jeśli znana jest cząstka szyfrogramu (Atak z szyfrogramem) oraz możliwe jest rozróżnienie poprawnego tekstu jawnego od niepoprawnego. Dla przykładu 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 dopuszcza skrót MD5 tekstu jawnego wiadomości, której szyfrogram łamany. Oczywiście, kiedy skrót MD5 dla wiadomości jest znany.

Na atak brute-force całkowicie odporny jest szyfr z kluczem jednorazowym wykorzystujący szyfrowanie XOR albo 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. Dla przykładu jeśli podczas wyboru hasła, zamiast stosować wszelkie możliwe kombinacje liter cyfr oraz znaków, których liczba dla sześciu znaków hasła wynosi ok. , 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 oraz 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 mała 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 oraz długości klucza oraz wynosi w najgorszym wypadku:

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

Dla przykładu jeśli klucz ma 32 bity oraz jedna próba trwa milionową cząstka sekundy, to łamanie potrwa średnio:

, czyli nieco ponad pół godziny

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

, czyli półtora dnia

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

dni

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

miliardów lat,

czyli prawie czas życia wszechświata (który wynosi niecałe 14 miliardów lat).