Łamanie haseł - algorytmy brute force

Techniki brute force są najskuteczniejsze nie ze względu na wymyślne algorytmy, ale ze względu na prostotę działania. Schemat sprowadza się zawsze do tej samej metody którą można opisać dokładnie jednym zdaniem: "znajdź rozwiązanie sprawdzając kolejne możliwości(kombinacje)". Oczywiście algorytm można przerwać w momencie znalezienia rozwiązania, no chyba, że oczekujemy więcej poprawnych rozwiązań.

Może warto odwołać sie do jakiegoś przykładu. Niech to będzie łamanie hasła zaszyfrowanego archiwum RAR. Załóżmy, że mamy do dyspozycji program unrar (unrar.exe w środowisku za którym nie przepadam :) ) dowolny kompilator języka C( cc, gcc), bash lub dowolny język skryptowy z którego można wywoływać polecenia zewnętrzne.

Schemat działania jest prosty:

1) Definiujemy tablice znaków char tablica_znaków[] = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

2) Piszemy podprogram do generowania wszystkich możliwych wariacji z powtórzeniami ze znaków tablicy zadeklarowanej w punkcie (1), oczywiście wariacje muszą mieć długość od 1 do length(tablica_znaków[])

3) W pętli odpalamy unrara tj. unrar nazwa_archiwum.rar i-ta_kombinacja

Cóż, wydawać by sie mogło nic trudnego; jedyna rzecz która psuje całą zabawę to czas jaki zajmie sprawdzenie wszyskich możliwości.
Jeśli hasło ma 3 znaki( ilość możliwości = length(tablica_znaków[]) + length(tablica_znaków[]) * length(tablica_znaków[]) + length(tablica_znaków[]) * length(tablica_znaków[]) * length(tablica_znaków[]) ) czas oczekiwania na odpowiedz jest w granicach naszych oczekiwań. W przypadku dłuższego hasła potrwa to o wiele, wiele dłużej (przyrost jest wykładniczy). Nawet wspomaganie sie dzieleniem zadań na wątki niewiele sie przyda w kontekście zysku czasowego.

Można oczywiści zawęzić alfabet, jeśli wiemy, że jakiś znaków na pewno nie zawiera hasło lub stosować dodatkowe algorytmy heurystyczne( np. zakładać że między spółgłoskami musi znajdować sie samogłoska) , ale wtedy istnieje prawdopodobieństwo, że nie znajdziemy hasła.

Mimo wszystko czasami warto próbować brute-for'ca, w końcu nie wszystkich chce sie wpisywać długie i wymyślnme hasła.... a nuż sie uda.