Łamanie hashy
Tutorial miejscami przeredagowany, dopisałem parę rzeczy, dodałem sekcję o saltach, poprawiłem gafę o kolizjach. Nic odkrywczego, ale dla początkujących może stanowić dobrą podstawę. Tekst dość długi jak na tematykę ponieważ staram się te koncepcje wytłumaczyć a nie tylko podać przepis „ściągnij to, kliknij tu”.
Ogólnie o hashach
Jednym z filarów biznesu są kradzione maile. Hasła w bazach z wycieków i włamań z zasady są zahashowane, co nieco utrudnia nam dostęp do maili użytkowników.
Po co się hashuje? Właśnie po to, żeby utrudnić dostęp do kont użytkowników potencjalnemu włamywaczowi. Działa to tak, że z hasła wpisanego podczas logowania zostaje obliczony hash i porównany z hashem w bazie. Jeśli hashe się zgadzają to logowanie jest poprawne. I tutaj pojawia się pierwsza właściwość hashy: ten sam string zawsze zwróci ten sam hash, nie ma żadnego elementu losowego.
Czym jest hash? Tak naprawdę nie musimy tego wiedzieć, chociaż pomaga to w zrozumieniu problemu. Funkcja hashująca to skomplikowana funkcja matematyczna, która zwraca inną wartość dla każdego stringa (ciągu znaków). Przykład: każdej literze przyporządkowujemy jej numer w alfabecie. Czyli A = 1, B = 2, … z = 26. Gdybyśmy zahashowali w ten sposób hasło „DUPA” to otrzymalibyśmy wartość 4 + 21 + 16 + 1 = 42. Okej, mamy liczbę 42, ale jak wrócić do „DUPY”? W ten sposób dochodzimy do drugiej ważnej właściwości – mając hash nie możemy obliczyć stringa, z którego powstał.
Byłaby to oczywiście funkcja bardzo niedoskonała i na jej przykładzie nie mogę udowodnić trzeciej właściwości hashy – jeden string, jeden hash, dwa stringi nie powinny dać takiego samego hasha. Taka sytuacja nazywana jest kolizją i występuje każdym algorytmie hashującym, choć trudność ich znalezienia jest różna dla różnych funkcji. Wynika to z bardzo prostej właściwości każdego algorytmu – maksymalnej ilości hashy. Taki np. MD5 to nic innego jak liczba zapisana w systemie heksadecymalnym. Unikalnych hashy MD5 jest ok. 340 x 10^36. To zajebiście dużo, ale stringów można wygenerować nieskończoność – prędzej czy później kolizja musi się pojawić. Dla nas jest to niestety raczej bezużyteczne, bo oznacza tylko że istnieje inny string, który da taki sam hash jak ten, który próbujemy złamać, ale nie będzie on hasłem ofiary. W serwisie, z którego wyciekł hash zalogowanie się za pomocą takiego stringa byłoby teoretycznie możliwe (o ile jego długość nie przekraczałaby limitu długości hasła w serwisie), ale nas z zasady bardziej interesują maile – a dostawca maila niemal na 100% będzie zabezpieczał hasła w inny sposób.
Franc porównał kiedyś hashe do stolca, ja jednak użyję trochę mniej gównianej metafory: odciski palców. Wyobraź sobie, że hash to odcisk palca a człowiek to hasło. Znajdując odcisk palca możesz go zmierzyć i obejrzeć z każdej strony, ale nie możesz stwierdzić do kogo należy. Mając pod ręką człowieka możesz za to pobrać jego odcisk palca (obliczyć hash). Druga właściwość hashy brzmiała: „mając hash nie możemy obliczyć stringa, z którego powstał”. Owszem, nie możemy. Ale możemy obliczać kolejno hashe potencjalnych haseł i porównywać je z hashem do złamania. Jeśli będą się zgadzać – brawo, hasło znalezione. Wracając do odcisków palców – jeśli chcesz znaleźć właściciela konkretnego odcisku palca, to musisz sprowadzić do siebie jak najwięcej „podejrzanych” i porównywać ich odciski z tym, którego szukasz. Tak właśnie działa łamanie hashy.
Co nieco o samym łamaniu
Istnieją dwie podstawowe metody łamania hashy:
atak bruteforce – czyli dosłownie „brutalna siła” to sprawdzanie każdej możliwej kombinacji: a, b, c, potem aa, ab, ac i tak dalej. Plusem metody bruteforce jest to, że nie ma hasha, którego nie da się nią złamać. Wszystko to kwestia czasu, bo w końcu dojdzie do każdej kombinacji. Problem w tym, że np. haseł 10 znakowych złożonych tylko z małych liter jest 141167095653376 (141 bilionów). Przeciętny procesor jest w stanie obliczyć ok. 3 milionów hashy MD5 na sekundę. Sprawdzenie 141 bilionów haseł zajęłoby mu prawie półtora roku. Nie muszę przypominać, że hasła nie składają się tylko z małych liter i nieraz są dłuższe niż 8 znaków, prawda? Hashe łamać można także z pomocą kart graficznych (których wydajność idzie już w setki milionów MD5 na sekundę).
atak słownikowy – używa się w nim pliku z potencjalnymi hasłami (słownika). Plusem jest to, że atak trwa znacznie krócej (oczywiście zależnie od rozmiaru naszego słownika, 100kb to ok. 10 000 haseł, więc w sekundę sprawdzamy ok. 30 MB słowników). Minusy: oczywiście nie każde hasło będziemy mieli w słowniku.
Jest jeszcze trzecia metoda, tzw. tablice tęczowe, ale to już wyższa szkoła jazdy. Bez terabajtowego dysku, sporych pokładów gotówki lub czasu i cierpliwości nie ma co się do tego zabierać. Można także stosować wariacje: atak słownikowy + X losowych znaków na końcu, połączone hasła z dwóch lub więcej słowników (np. imiona i nazwiska) i wiele innych. Polecam eksperymentowanie z nimi we własnym zakresie.
Od czego zacząć?
Dobrze jest zacząć od gromadzenia słowników, bo ich nigdy dość, a stanowią podstawę każdego ataku. Słowniki można tworzyć samodzielnie lub ściągać. Tą pierwszą opcję polecam tylko jeśli masz dużo czasu, bo to dośc pracochłonna i żmudna robota, więc nawet nie będę jej opisywał. Podstawą dla kazdego domorosłego łamacza hashy są słowniki z polskiej edycji Backtracka. Osobiście polecam także słowniki od InsidePro, odradzam natomiast crackstation.net (słownik realuniq) – szkoda miejsca. Po więcej radzę udać się do wujka Google (albo DuckDuckGo, Google nas śledzi).
Następnie musimy wybrać narzędzie. Ja używam PasswordsPro – prosty i robi robotę, do tego jest w wersji portable. Jak najbardziej polecam go początkującym. Nawet jeśli używacie bardziej zaawansowanych narzędzi (a w końcu trzeba po nie sięgnąć) to PasswordsPro cały czas pozostaje bardzo wygodnym menedżerem baz. Popularne są również takie programy jak:
Cain – używałem przed poznaniem PasswordsPro, całkiem przyjazny, ale wkurwiało mnie wgrawanie baz przez manipulowanie plikami oraz brak wersji portable
HashCat – kotek nie ma sobie równych jeśli macie sprzęt do łamania GPU, potrafi także wycisnąć z CPU znacznie więcej niż inne crackery. Jest także wyposażony w bardzo wydajną funkcję generowania tzw. zasad, czyli modyfikowania haseł ze słowników w czasie rzeczywistym.
John the Ripper – tylko interfejs konsolowy, nie korzystałem bo niestety mam alergię na konsolę
I… to właściwie tyle. Ładujemy bazę i łamiemy. Ja zaczynam od słowników a potem puszczam bruteforce: małe litery 6 znaków, duże litery 6 znaków, małe i duże od 1 do 5 znaków cyfry do 9 znaków (numery telefonów). Całość zajmuje (łącznie ze słownikami) ok. 40 minut. Jeśli macie dostęp do GPU to oczywiście warto zwiększyć limity o parę znaków i sprawdzać także kombinacje liter z cyframi i znakami specjalnymi. Aktualnie mam 19.2 GB słowników, ale czeka je inwentaryzacja, bo skuteczność zdecydowanie mnie nie zadowala (~60%).
Dobra rada
waga słowników nie zawsze idzie w parze z ich skutecznością, a sama skuteczność rośnie logarytmicznie wraz ze wzrostem wagi. Najmniejsza wersja słownika Backtrack ma 200KB a jej średnia skuteczność na polskich bazach to (według moich testów) ~20%, podczas gdy moje 19.2 GB dają mi zaledwie ~60%. Skuteczność wzrosła o 300%, a waga o 10000000%.
bazy z wycieków możesz przygotować do crackowania choćby w Excelu
rodzaj hasha możesz sprawdzić tu
hashe, których nie udało ci się złamać możesz spróbować złamać w którejś z internetowych baz, np. md5.darkbyte.ru, ten serwis dodatkowo ma API, więc można napisać sobie wygodny skrypt (albo użyć mojego – Hashashin, hasło: torepublic). Polecam także md5decrypter.co.uk, uciążliwy, ale baza pokaźna.
do tworzenia i manipulowania słownikami polecam mały programik L517
oczywista oczywistość dla paranoika, ale jeśli zostawiamy łamanie na noc a sami idziemy spać to warto zrobić sobie osobny kontener truecrypta z softem do łamania, słownikami i bazą
przed rozpoczęciem łamania hashy zaparz sobie melisy, bo jak zobaczysz ilu debili używa „12345”, „123456” czy „qwerty” to weźmie cie kurwica
Salt, czyli posolone hashe
My wysilamy się żeby złamać jak najwięcej hashy, po drugiej stronie barykady wysilają się (choć, jak widać po udostępnianych bazach, nie za mocno), żebyśmy złamali ich jak najmniej. Jednym ze sposobów na zabezpieczanie haseł użytkowników jest tzw. sól (salt). Na czym to polega?
Zacznijmy od jeszcze jednej ważnej właściwości algorytmów hashujących. Nawet najmniejsza zmiana w stringu źródłowym (w zdecydowanej większości przypadków) powoduje kompletną zmianę hasha. Na przykładzie:
md5(cebula) = 29a7221e8b75be745990a2a77f2c26ed
md5(cebulb) = 8b6373a99606fa2b18f3436255030ea8
md5(cebulac9) = f83dd3e0f5b09dad19c2d97a5c5d0ded
Jak ta właściwość została wykorzystana przeciwko crackerom? Do hasła użytkownika dodaje się losowy string i dopiero z niego wylicza hash. Na przykład użytkownik Superman ma hasło „cebula”. Hash „cebula” znajdziemy choćby na md5.darkbyte.ru, prawdopodobnie każdy cracker ma go w słowniku a i bruteforce nie zajęłoby zbyt wiele czasu. Cwany administrator dodaje więc na końcu hasła „cebula” string „c9”, czyli sól, i wylicza hash (funkcja: md5($pass.$salt)). Podczas logowania Superman podaje „cebula”, ale przy jego hashu w bazie danych jest jeszcze jego sól.
Dla serwisu to żadna różnica. Dla nas, dzielnych łamaczy, różnica jest jednak kolosalna.
Użycie soli w bazie danych ma dla nas kilka konsekwencji. Choćby crackery online stają się w dużej mierze bezużyteczne. Oczywiście zdarza się, że w bazie akurat będzie hash stringa z solą (np. „cebulac9” jest w bazie md5.darkbyte.ru, wtedy trzeba pamiętać, żeby obciąć sól), ale jeśli nawet to będzie ich znacznie mniej niż gdyby soli nie było. W ten sam sposób osłabiony zostaje również atak tablicami tęczowymi (o tym w kolejnej części tutoriala), ale najgorszy jest cios w wydajność procesorów i kart graficznych. Dlaczego?
Jeśli w bazie mamy 1 użytkownika z niesolonym hashem a w słownikach 50.000.000 haseł, to wyliczonych zostanie 50.000.000 hashy, a następnie zostaną one porównane z hashem jednego użytkownika (hashe są porównywane w czasie rzeczywistym, to uproszczenia). Jeśli w bazie będziemy mieli 10.000 użytkowników to ilość wyliczonych hashy będzie taka sama, zmieni się tylko ilość porównań, ale przy ilości obliczeń, które są potrzebne do wyliczenia hashy można przyjąć, że porównanie w ogóle nie obciąża CPU/GPU, a te dwa przykłady wymagają takiej samej ilości obliczeń. Ilość użytkowników nie wpływa znacząco na wydajność crackera.
Jeśli hasła są posolone, to dla każdego użytkownika z jednego hasła ze słownika trzeba wyliczyć inny hash. W pierwszym przypadku (jeden użytkownik) ilośc obliczeń dla haseł posolonych będzie taka sama, w drugim (10.000 użytkowników) będzie 10.000 razy większa.
Innymi słowy posolone hasła sprawiają, że program będzie musiał wyliczyć tyle razy więcej hashy ile jest użytkowników w bazie. Mój procesor w jednym wątku wyciąga ok. 5 MHash/s (5 milionów hashy na sekundę), na 5000 bazie ok. 1000 Hash/s. Prędkość rośnie z czasem, bo im więcej hashy zostało złamanych tym mniej unikalnych hashy trzeba liczyć, ale żeby dość do połowy oryginalnej prędkości trzeba by było złamać wszystkie hashe poza dwoma.
Warto dodać, że w różnych bazach używane są różne systemy solenia. Sole mogą różnić się długością, im krótsza sól tym lepiej dla nas, bo wtedy może się powtarzać dla różnych użytkowników. Raz są to dwa znaki, raz pięć. Występują także różne funkcje dodawania soli. Najczęściej przyklejana jest przed hasłem (md5($salt.$pass)) lub za hasłem (md5($pass.$salt)), ale czasem pojawiają się bardziej skomplikowane konstrukcje, w których doklejany jest też login, liczone są podwójne hashe i wiele innych kombinacji. Na szczęście w polskich bazach to bardzo rzadka praktyka. Warto też wspomnieć o takich szatańskich wynalazkach jak funkcja występująca pod nazwą md5(phpbb3), oprócz PHPBB3 używana także w innych silnikach for i CMSach. Hash ten jest tak naprawdę pętlą wywołującą tradycyjny md5 2048 razy (2048 razy więcej obliczeń), mało tego – sam w sobie zawiera sól. Koszmar.
Na koniec części teoretycznej trochę liczb. 10.000 haseł = 100 KB, więc 1 GB to ~10.000.000.000 haseł. Na bazie 5000 użytkowników z posolonymi hashami musielibyśmy policzyć 50.000.000.000.000 hashy. Przy wydajności przeciętnego procesora, czyli ~3Mhash/s, zajęłoby ok. 192 dni. Nie uwzględniłem wzrostu prędkości w miarę łamania kolejnych hashy, ale nawet połowa tego czasu (tyle zajęłoby łamanie jeśli mielibyśmy w słowniku wszystkie cleartexty, a ostatni hash zostałby złamany ostanim cleartextem) jest nie do zaakceptowania. Dlatego łamiąc posolone hashe trzeba skupić się na wydajności.
Donnvitopasza kontra sól
Trzeba zacząć od poznania dokładnej funkcji hashującej. Detectory online nie pomogą, bo posolony hash nie różni się niczym od zwykłego. Moim sposobem na to jest wzięcie małej części bazy (zwykle biorę 100-200 rekordów) i przepuszczenie jej przez mały, wydajny słownik używając różnych funkcji. Polecam mini.txt z polskiej edycji Backtracka.
Słowników używamy zaczynając od najmniejszych i najwydajniejszych. Dzięki temu ilość userów stopnieje chociaż trochę i kolejne hashe będą liczone nieco szybciej.
Nie zaszkodzi wrzucić bazy do crackera online. Rzadko trafiają się matche, ale zawsze to kilku(dziesięciu) userów do przodu. Może lecieć w tle podczas zwykłego ataku.
GPU jest oczywiście nie do przecenienia (a całkiem niezłą używkę, znacznie poprawiającą wydajność przy łamaniu hashy, można kupić już za 200 PLN), ale nie każdy ma do niego dostęp. Dlatego warto wycisnąć z CPU ostatnie soki. Crackery takie jak Cain czy PasswordsPro są ok, ale z wydajnością nie mają wiele wspólnego, szczególnie jeśli masz wielordzeniowy procesor (ponieważ działają tylko na jednym rdzeniu, więc wykorzystują tylko 1/<ilość rdzeni> potencjalnej mocy procesora). Królem wydajności jest HashCat – nie marnuje zasobów na GUI, wykorzystuje wszystkie rdzenie i, wnioskując po osiągach, jest po prostu dobrze napisany.
[TODO] Tablice tęczowe
Eksperymentuję z tablicami tęczowymi, więc niedługo można się spodziewać aktualizacji.
Teczowe tablice byc bardzo proste wink krang dzialac tylko w ten sposob
soft i tablice do pobrania lub hashcat
Tęczowe tablice (ang. rainbow tables) – jest to baza skrótów wykorzystywana w łamaniu haseł szyfrowanych jednokierunkową funkcją skrótu. Pozwala na zaoszczędzenie mocy obliczeniowej koniecznej do złamania hasła metodą brute force. Metoda ta została wymyślona przez Philippe Oechslina z Politechniki w Lozannie.
W sieci można znaleźć wiele informacji na temat tego czym są i jak działają tęczowe tablice. Jednak większość z nich opisuje cały ten proces tak skomplikowanym językiem, że dla laika wydaję się on być dość skomplikowany. W tym artykule zostanie omówionych kilka istotnych szczegółów, które przybliżą istotę działania rainbow tables i ułatwią ich zrozumienie.
Na początku warto wspomnieć o funkcji hashującej. Kompresuje ona bity hasła do wartości o określonej długości (ang. hash value). Czyni to w sposób, który sprawia niezwykle trudnym pojawienie się wiadomości, która dałaby w rezultacie tę samą hash-wartość. Z hasła zapisanego jawnym tekstem tworzy hash w taki sposób, aby nie można było powiedzieć z jakiego hasła powstał.
Do znalezienia hasła dla danego hasha można wykorzystać dwie proste metody:
* Z przestrzeni znaków dla wszystkich możliwości haseł można tworzyć odpowiadające im hashe. Podczas generowanie każdego kolejnego hasha możn sprawdzać czy szukany hash odpowiada hashowi, który właśnie został wygenerowany. Jeśli hashe są takie same, należy zatrzymać generowanie i sprawdzać czy hasło pasuje, jeśli nie kontynuować generowanie dalej.
* Z przestrzeni znaków dla wszystkich możliwości haseł można tworzyć odpowiadające im hashe, w sposób uporządkowany zapisywać je do tabeli, a po wygenerowaniu kompletnej tablicy wyszukiwać w niej interesujący nas hash. Dzięki zapisaniu tablic na dysku twardym można je w przyszłości wykorzystywać do szukania hashy, bez konieczności ponownego ich generowania.
Obie metody mają jednak duże wady. Każdorazowe generowanie hashy zabiera bardzo dużo czasu, a przetrzymywanie każdego hasha zajmuje ogromne przestrzenie dyskowe. Tęczowe tablice są swoistym kompromisem pomiędzy wcześniejszym generowanie tablic, a niskim użyciem pamięci masowej.
Nazwa Rainbow Tables wzięła się od kolumn z użytymi różnymi funkcjami redukującymi. Jeśli każda użyta funkcja redukująca miała by w tabeli inny kolor, a na górze tabeli znajdowało by się hasło w postaci plaintekstu i hashe w środku tablicy, to tablica wyglądała by jak tęcza. Kluczem do zrozumienia tęczowych tablic, jest zrozumienie czym tak naprawdę jest funkcja redukująca. Funkcja hashująca przyporządkowuje dla danego hasła jego odpowiednik hash, zaś funkcja redukująca dla danego hasha przyporządkowuje hasło. Funkcja z hasha tworzy hasło ale oczywiście nie jest to hasło z którego dany hash powstał, jest on tak naprawdę dowolnym ciągiem znaków który powstał w wyniku konkretnego działania.
Na przykład jeśli przestrzeń znaków hasła to [0123456789], a hasło nie jest dłuższe niż sześć znaków i jest zaszyfrowane przy pomocy algorytmu md5 (sześcio-znakowe hasło numeryczne) to dla hasła „493823” hash będzie miał wartość „222f00dc4b7f9131c89cff641d1a8c50”. W takim przypadku funkcja redukująca może ograniczyć się do pobrania sześciu pierwszych cyfr z hasha 222f00dc4b7f9131c89cff641d1a8c50 co daje nowe hasło o w postaci 222004. I oto z hasha otrzymuje się kolejne hasło które posłuży do wygenerowania kolejnego hasha itd.
Hashowanie jak i redukcja są funkcjami jednokierunkowymi. Łańcuchy znaków tworzące tęczowe tablice są łańcuchami jednokierunkowych funkcji redukujących zaczynających się od konkretnego hasła i kończących się na konkretnym hashu. Łańcuch zaczyna się od hasła w plaintekscie, które później poddawane jest funkcji hashującej, której to wynik z kolei poddawany jest funkcji redukującej, a następnie znowu funkcji hashującej i redukującej itd. Łańcuch zawiera tylko początkowy plaintekst i końcowy hash. Dlatego też miliony hashy mogą być zastąpione jedynie rekordem posiadających jedno początkowe hasło i jeden końcowy hash.
Po wygenerowaniu wielu ciągów tablica ma postać podobną do tej:
Code :
plaintext hash
iaisudhiu 4259cc34599c530b1e4a8f225d665802
oxcvioix c744b1716cbf8d4dd0ff4ce31a177151
9da8dasf 3cd696a8571a843cda453a229d741843
[…] […]
sodifo8sf 7ad7d6fa6bb4fd28ab98b3dd33261e8f
Łańcuchy znaków są już wygenerowane, przyszedł więc czas aby ich użyć. Mamy hash hasła, nie znamy jego plaintekstowej formy i chcemy sprawdzić czy znajduje się on w którymś z wygenerowanych łańcuchów.
Przy generowaniu rainbow tables można napotkać na kilka problemów. Po pierwsze nigdy ma pewności, że wygenerowana tablica ma już wszystkie pożądane hashe. Oczywiście nie można być pewnym, iż wszystkie hasła w pożądanej przestrzeni znaków zostaną zahashowane, ale szanse rosną przy odpowiedniej ilości łańcuchów. Kolejnym niepożądanym zjawiskiem jest zjawisko kolizji. Polega ono na wystąpieniu sytuacji kiedy to z wielu różnych haseł otrzymuje się taki sam hash. Mogą też wystąpić zapętlenia w przypadku gdy hash został zredukowany do hasła które już wystąpiło w danym łańcuchu wcześniej. Został on jednak znacznie zminimalizowany dzięki temu iż na całej drodze w łańcuchu za każdym razem użyta jest inna funkcja redukująca.
Tęczowe tablice pozwalają na złamanie większości popularnych funkcji skrótu, w tym MD5, SHA-1, NTLM czy Cisco Pix.
Obrona
Dobrym sposobem na zabezpieczenie sie przed tym sposobem ataku jest stosowanie tzw. soli (ang. salt), czyli losowo generowanej wartości dodawanej jako argument funkcji skrótu i zapisywanej obok wartości skrótu. Sprawia to, że dla każdej soli funkcja skrótu jest inna. Żeby złamać taki skrót osoba próbująca złamać musiałaby posiadać tęczową tablicę dla każdej możliwej soli, co jest niepraktyczne.
Większość dystrybucji GNU/Linuksa i systemów BSD wykorzystuje sól do zapisywania haseł użytkowników, funkcjonalność ta jest oferowana przez pakiet shadow. Z kolei większość aplikacji internetowych w PHP wykorzystuje do kodowania haseł użytkowników zwykłe MD5, co ułatwia złamanie hasła.
