Zadaniem będzie napisanie w ANSI C wielowątkowego współbieżnego programu do łamania zahaszowanych haseł metodą słownikową. Zakładamy, że hasła są generowane metodą skrótów kryptograficznych MD5. Ze względu na dużą ilość obliczeń, program (wątek) główny będzie generował szereg wątków roboczych, i koordynował ich pracę nad łamaniem haseł.
Program łamania haseł powinien być zorganizowany według analizowanego
wcześniej schematu producentów i konsumentów. Zadaniem wątku głównego jest
wczytanie do pamięci globalnej programu podanej przez użytkownika listy
zahaszowanych haseł do łamania, oraz podanego (lub domyślnego) słownika.
Jedno i drugie jest listą słów, przy czym słownik może zawierać nawet
bardzo dużą liczbę słów różnej długości, i powinien być załadowany do
pamięci dynamicznej zaalokowanej funkcją malloc o dokładnie określonym
rozmiarze. Natomiast lista zahaszowanych haseł jest typowo mniejsza (można
przyjąć maksymalnie 1000 haseł) i będą one miały stałą długość 32 znaków,
zatem może dla nich być użyta tablica statycznie alokowana.
Następnie wątek główny powinien uruchomić zdefiniowany zestaw wątków ,,producentów''. Zadaniem każdego z producentów jest próba złamania kolejno wszystkich zadanych haseł określoną metodą. Każdy z producentów będzie implementował inną metodę budowy haseł, w celu zrównoleglenia procesu ich łamania. Każdy producent będzie po kolei budował próbne hasła swoją metodą, następnie obliczał 32-znakowy skrót kryptograficzny MD5 każdego hasła, i porównywał ten skrót z całą listą zahaszowanych haseł. Jeśli któreś hasło zgodzi się z obliczonym haszem, to oznacza, że znalezione zostało hasło źródłowe. W takim przypadku należy poinformować wątek konsumenta, który zarejestruje złamane hasło i oznaczy odpowiednie hasło w tablicy globalnej, aby nie było już ono dalej sprawdzane.
Podatne na złamanie metodą słownikową hasła są budowane ze słów danego języka, wraz z zestawem nazw własnych tego języka (imion, popularnych nazwisk, nazw geograficznych, itp.), z uwzględnieniem pewnych modyfikacji.
Przykładami modyfikacji mogą być: słowo zapisane tylko małymi lub tylko wielkimi literami, albo pierwszą wielką i pozostałymi małymi, słowo z dodatkiem jakiejś liczby na początku lub na końcu, albo z dodatkiem jakiegoś znaku interpunkcji na początku lub na końcu. Możliwe są również połączenia tych modyfikacji (np. wielka litera na początku, reszta słowa małymi literami, potem jakiś znak interpunkcji i potem liczba).
Prowadzący zajęcia określi jakich producentów należy obowiązkowo zaimplementować w danej grupie ćwiczeniowej.
Wątek konsumenta powinien natychmiast wyświetlać na ekranie każde kolejno znalezione złamane hasło w miarę otrzymywania ich od producentów. Warto wykorzystać w tym celu mechanizm zmiennej warunkowej.
Przez cały czas pracy program (wątek) główny powinien czytać stdin gdzie
użytkownik może w dowolnym momencie wpisać nazwę nowego pliku haseł do
łamania. Gdy to się zdarzy, program główny powinien wykonać ,,reset'',
tzn. spowodować żeby zarówno producenci jak i konsument zarzucili pracę nad
poprzednimi hasłami i zaczęli pobierać i łamać nowe.
Dodatkowo, program powinien obsługiwać ,,przerwanie'' od użytkownika. Po otrzymaniu sygnału SIGHUP przez program, wątek konsumenta powinien wyświetlić podsumowanie osiągniętych wyników dla bieżącego pliku haseł.
Zadanie powinno być wykonane w ciągu dwóch kolejnych terminów zajęć.
W pierwszej kolejności należy zaimplementować i uruchomić najprostsze
konstrukcje producentów (generatorów haseł), oraz przetestować ich na małym
zbiorze haseł testowych z minimalnym słownikiem. Szczegółowe instrukcje i
zbiory danych do tej części ćwiczenia dostępne są na stronie:
https://kcir.pwr.edu.pl/~krzewnicka/?page=haszowanie
Napisz program, który wczyta do zwykłej tablicy w programie plik słownika podany w punkcie "Test 1" i --- wykorzystując funkcję pokazaną we wskazówce w powyższym linku --- będzie obliczał hasze MD5 kolejnych słów ze słownika i porównywał je z zadanym zahaszowanym hasłem, wyświetlając wynik w przypadku wykrycia dokładnej zgodności.
Zahaszowane hasła powinny być załadowane z pliku do drugiej tablicy w programie. Program powinien w zewnętrznej pętli generować kolejne hasze słów ze słownika, i w wewnętrznej pętli każdy wygenerowany hasz porównywać ze wszystkimi haszami haseł.
Wynikiem powinno być znalezienie wszystkich haseł pokazanych w "Test 1".
Zaimplementuj łamanie haseł metodą opisaną w punkcie "Test 2". Do każdego kolejnego słowa ze słownika program powinien po kolei dopisywać liczby jedno- i dwucyfrowe na początku, na końcu, oraz na początku i końcu każdego słowa.
Wynikiem powinno być znalezienie wszystkich haseł pokazanych w "Test 2".
Zaimplementuj łamanie haseł metodą opisaną w punkcie "Test 3". Dla każdego kolejnego słowa ze słownika program powinien po kolei haszować wersję samymi małymi literami, wszystkimi wielkimi, oraz pierwszą wielką i resztę małymi. Ta wersja powinna działać w dodatku do wersji z poprzedniego zadania, czyli do wszystkich wersji pisowni danego słowa należy dopisywać liczby.
Wynikiem powinno być znalezienie wszystkich haseł pokazanych w "Test 3".
Należy zmodyfikować program w celu obsługi dużego słownika, takiego jak
podany w punkcie "Test 5" zadania. W tym przypadku nie można już tworzyć
zwykłej tablicy, tylko należy zaalokować pamięć na stercie funkcją malloc
i do niej załadować słownik.
Należy zaimplementować program w docelowej wielowątkowej postaci. Poszczególne metody łamania haseł powinny być uruchomione jako niezależnie pracujące wątki producentów. W momencie złamania hasła przez jednego z producentów powinien on poinformować wątek konsumenta, który zaznaczy hasło jako złamane blokując jego dalsze sprawdzanie, a następnie wyświetli znalezione hasło na wyjściu. Program powinien również wyświetlić pełną listę złamanych haseł po otrzymaniu sygnału SIGHUP, a także w momencie zakończenia pracy, gdyby wszystkie możliwości sprawdzania wszystkich haseł zostały wyczerpane.
W drugim terminie będzie kontynuacja zadania w zakresie ogłoszonym bezpośrednio na zajęciach przez prowadzącego. Będzie to zadanie do wykonania wyłącznie na zajęciach. Konieczne będzie posiadanie uruchomionej i działającej przynajmniej najprostszej wersji programu do łamania MD5 (Zad.1 powyżej).
Wersję źródłową algorytmu do obliczania skrótów MD5 można znaleźć na
stronie Wikipedii:
http://en.wikipedia.org/wiki/MD5#Simple_implementation
Implementacja obliczania skrótów MD5 znajduje się również w bibliotece
OpenSSL, która z dużym prawdopodobieństwem jest zainstalowana na każdym
komputerze Unix/Linux. Przykładowy program obliczający skóty
kryptograficzne różnymi algorytmami można znaleźć na stronie:
https://www.openssl.org/docs/crypto/EVP_DigestInit.html
https://www.ef.com/wwen/english-resources/english-vocabulary/top-3000-words/
https://www.mit.edu/~ecprice/wordlist.10000
https://www.wordgamedictionary.com/english-word-list/download/english.txt
https://sjp.pl/sl/growy/
https://sjp.pl/sl/growy/sjp-20231203.zip
Zbiory przykładowych haseł do łamania można znaleźć na stronie:
https://twitter.com/PastebinLeaks
Przykładowe zbiory haseł:
https://pastebin.com/JhN64Qkc
https://pastebin.com/Ef5gXBrU
https://pastebin.com/bwT3T0M7
https://pastebin.com/GuRjzY3Z