Łamanie haseł z wykorzystaniem CPU/GPU

Wstęp

Coraz częściej słyszy się o dostępnych w Internecie bazach haseł wykradzionych  z popularnych portali – w czerwcu 2012 roku był to LinkedIn, z którego wyciekło około 6.5 miliona haseł użytkowników,  kilka miesięcy wcześniej – popularny serwis dla graczy Steam.

Najczęściej tego typu bazy zawierają hasła użytkowników przechowywane w formie tzw.  “zaszyfrowanej” (zahashowanej), choć czasem różnie z tym bywa…

“Zaszyfrowana” forma hasła tego typu wygląda np. tak: ceac9c9933e9f2187d5ad6887078dc2a (w tym przypadku to wynik funkcji MD5 na haśle: trudne123).

Zaszyfrowane hasło

Nie jest to idealny (patrz dalej w tekście rozdział metody ochrony ), choć bardzo popularny sposób przechowywania haseł w bazie.

Można zadać sobie dwa pytania – czy atakujący jest w stanie odszyfrować tego typu informację aby uzyskać hasło w formie jawnej?  Tutaj odpowiedź jest negatywna: nie może, jeśli hasło jest odpowiednio skomplikowane. Co to znaczy odpowiednio skomplikowane? Na to pytanie postaram się odpowiedzieć w dalszej części tekstu.

Ostatnio zwiększyły się wymagania dla hasła uznawanego jako odpowiednio silne – a to za sprawą kart graficznych, dzięki którym proces łamania hashy można w pewnych przypadkach wykonać nawet 1000 razy szybciej niż z wykorzystaniem nowoczesnych CPU. Niecałe dwa lata temu zostało szczegółowo pokazane rozwiązanie łamiące hashe MD5 z prędkością ponad 33 miliardów sprawdzeń na sekundę, mieszczące się w obudowie zwykłego PC i zbudowane z czterech kart graficznych GPU:

(C) zorinaq – zoptymalizowana wersja crackera whitepixel pracuje na tym sprzęcie z prędkością ponad 33 miliardów MD5/sec.
Za: http://blog.zorinaq.com/?e=42

Tego typu zestaw może poradzić sobie z dowolnym 10 znakowym hasłem składającym się z małych liter i cyfr, w czasie niewiele dłuższym niż jeden dzień. Warto zaznaczyć, że jest to wartość pesymistyczna, wymagana do sprawdzenia wszystkich możliwych kombinacji haseł – realny czas tej operacji może być jeszcze krótszy. Zobaczmy to w tabeli:

Update, 13.07.2012 – projekt Erebus, (8x Radeon HD7970) osiągnął niedawno wydajność 74 miliardy md5 / sekundę – to przeszło 2 razy szybciej niż whitepixel!

Zestawienie wygląda nieco lepiej na prostym sprzęcie będącym w zasięgu budżetu domowego (Radeon HD 6850 kosztujący ok 550 PLN), łamiący z szybkością ok. 2,745 miliarda hashy / sek. W tym przypadku, łamanie tego samego hasła jest realizowane w około 15,5 dnia:

Dla porównania, poniżej zestawienie dla popularnego narzędzia Cain & Abel, które na procesorze Core2Duo @3GHz osiąga prędkość ok 10 milionów MD5/sek. W tym przypadku mamy aż 4231 dni!

Osobom chcącym wykonać własne symulacje tego typu polecam arkusz Excela udostępniany przez SANS. Wracając do porównania wydajności – skąd taka drastyczna różnica pomiędzy GPU a CPU? Nieco upraszczając, można powiedzieć, że za sprawą nawet tysięcy tzw. ALU (specjalizowanych jednostek mogących wykonać proste operacje arytmetyczne), jakie składają się na nowoczesne GPU, mamy dostępną moc obliczeniową analogiczną z CPU składającym się z tysięcy rdzeni. Przykładowy benchmark dla realizacji funkcji MD5() można zobaczyć poniżej (wyniki dla GPU zostały oddzielone od CPU poziomą linią).

Powyższe zestawienie na podstawie:
http://ixplizit.wordpress.com/2010/05/01/hashcat-v0-34-vs-passwordspro-v3-0-0-0/
http://hashcat.net/hashcat/
http://golubev.com/gpuest.htm
http://3.14.by/en/read/md5_benchmark
http://forum.notebookreview.com/hardware-components-aftermarket-upgrades/436718-barswf-benchmark-results-thread-who-can-get-highest.html

Cele crackowania / odzyskiwania haseł

Poszukiwanie haseł odpowiadających hashowi jest różnie nazywane – niekiedy crackowaniem lub łamaniem hashy, a czasem odzyskiwaniem haseł. Patrząc od strony atakującego, crackowanie następuje w momencie przechwycenia bazy zawierającej hasła w formie hashy (przejęcie następuje często za pomocą podatności SQL injection) – oczywiście tego działania nie są legalne. Z legalnego punktu widzenia cele mogą być następujące:

• weryfikacja swojej bazy haseł – pod względem wystąpienia w nich prostych do złamania hashy (sugeruje to aby przemyśleć zasady tworzenia haseł przez użytkowników),
• uświadomienie sobie wymaganej złożoności haseł i być może podjęcie decyzji o ich zmianie,
• realizacja tzw. testów penetracyjnych (kontrolowanych ataków na infrastrukturę IT)
• poszukiwanie bitcoinów.

Funkcje skrótu a hasła

Zaleca się aby systemy IT (często są to aplikacje webowe) nie przechowywały haseł dostępowych użytkowników w formie jawnej – w tym przypadku, po uzyskaniu przez ewentualnego atakującego dostępu do bazy danych – posiada on automatycznie dostęp do haseł. Dlatego w systemach bardzo często przechowuje się nie samo hasło, a wynik funkcji skrótu na haśle (np. SHA-1(Bardzo912TrudneHaslo) = f3b7434f2d1dc16817520e73d8eab17298dbea0b )
W momencie logowania (podanie loginu oraz hasła) wykonywana jest mniej więcej tego typu operacja:

• użytkownik chcąc się zalogować podaje: swój login i hasło, np.: admin, Bardzo912TrudneHaslo
• mechanizm logowania wykonuje funkcję skrótu (np. SHA-1) na haśle podanym przez użytkownika SHA-1(“Bardzo912TrudneHaslo”) = f3b7434f2d1dc16817520e73d8eab17298dbea0b
• mechanizm logowania sprawdza czy w bazie istnieje użytkownik o podanym loginie, z obliczonym hashem hasła – jeśli tak – użytkownik poprawnie loguje się do systemu.

Czy istnieje łatwy sposób na odzyskanie hasła w formie jawnej, posiadając jedynie jego hash? Przyjrzymy się takim możliwościom w kolejnym rozdziale.

Realna odporność funkcji skrótu na łamanie siłowe

Aby spróbować siłowo uzyskać jawne hasło z formy hash atakujący ma w zasadzie trzy możliwości:

1. Atak wyczerpujący

W czasie  ataku sprawdzane są wszystkie możliwe kombinacje haseł. Dla każdej  próby hasła liczony jest hash oraz porównywany z zawartością w bazie. Jeśli w danej próbie hashe się zgodzą, hasło w formie jawnej zostało odkryte.

Przykład – jakiemu hasłu odpowiada hash: 0567d2132f50b437f34bfd172dfa003b1081fa72 ?

Liczymy:

SHA-1(“a”) =  86f7e437faa5a7fce15d1ddcb9eaeaea377667b8
SHA-1(“b”) = e9d71f5ee7c92d6dc9e92ffdad17b8bd49418f98
…
SHA-1(“aaa”) =  7e240de74fb1ed08fa08d38063f6a6a91462a815
SHA-1(“aab”) =  40b904fd8852297daeaeb426b1bca46fd2454aa3
…
SHA-1(“aaz”) =  0567d2132f50b437f34bfd172dfa003b1081fa72

Ostatni hash zgodził  się z tym wskazanym wcześniej – nasze hasło w formie jawnej to “aaz”.

Zalety metody:

• możliwość odzyskania hasła niezależnie od jego skomplikowania (do pewnych długości samego hasła). Np. jeśli użyto funkcji hashującej MD5, w rozsądnym czasie można uzyskać każde hasło o długości do 10 znaków składające z małych  liter / cyfr.

Wady metody:

• wymagana jest znaczna moc obliczeniowa (w porównaniu z CPU, zastosowanie GPU zwiększa tą moc o nawet 2-3 rzędy wielkości),
• w praktyce nie jest możliwe odzyskanie hasła długiego, ale nieskomplikowanego: np. ‘niebezpieczenstwo’

2. Próba ataku słownikowego

Sprawdzanie wygląda podobnie jak we wcześniejszym przykładzie, natomiast nie weryfikowane są wszystkie możliwe kombinacje haseł, a jedynie hasła występujące w słownikach (np. imiona, popularne nazwy itp). W tym przypadku dostępne są zarówno często wykorzystywane hasła  jak i całe słowniki języka polskiego – również z odmianą . Pewną odmianą tej metody jest podejście hybrydowe – tj. połączenie ataku wyczerpującego (poprzedni punkt) ze słownikowym. Np. do każdego słowa ze słownika dołączamy liczby od 1 do 99 (w ten sposób znajdziemy np. hasło magdalena12) , lub próbujemy podwójne sklejenia słów ze słownika, np.: aniaania. Niektóre narzędzia, choćby: http://www.insidepro.com/eng/egb.shtml umożliwiają stosowanie zaawansowanych ataków hybrydowych, np.: użycie reguły: ilove@?d?d?d?d spowoduje:

• sprawdzenie wszystkich kombinacji haseł rozpoczynających się od słowa ‘ilove’,
• po nim następuje dowolne słowo z dostarczonego słownika (znak @),
• hasło kończy się na dowolną kombinację czterocyfrową.

Zalety metody:

• możliwość odzyskania pozornie skomplikowanych haseł.

Wady metody:

• wymagane posiadanie odpowiednio rozbudowanych słowników oraz duże doświadczenie w dobieraniu odpowiednich reguł.

3. Tzw. zesłownikowanie hashy

Jednorazowe stworzenie “prostej bazy danych” – zawierającej hasła oraz odpowiadające im hashe. W tym przypadku po jednorazowym stworzeniu tego typu bazy danych, możliwe jest późniejsze szybkie jej przeszukiwanie (ta szybkość jest główną zaletą w porównaniu do omawianej wcześniej metody wyczerpującej; z kolei wadą tutaj jest rozmiar samej bazy, często idący w setki megabajtów).  Najpopularniejszą techniką dość optymalnie realizującą pomysł “zesłownikowania” są tablice tęczowe (ang. rainbow tables).

Zalety metody:

• wysoka szybkość działania w porównaniu z atakami wyczerpującymi.

Wady metody:

• wymagana duża pojemność przestrzeni dyskowej,
• niewielka elastyczność jeśli pracujemy tylko na stworzonej wcześniej bazie.

Narzędzia łamiące hashe

1. CPU

Jednym z chyba najdłużej rozwijanych narzędzi tego typu, działających w oparciu o CPU jest John The Ripper, obsługujący bardzo dużą liczbę algorytmów, dający bardzo dużą elastyczność (tworzenie reguł – o tym pisałem wcześniej), a ostatnio także wsparcie dla GPU.

Innym narzędziem jest Cain & Abel – choć w tym przypadku tzw. cracker jest jedynie częścią większego rozwiązania.

Godny polecenia jest na pewno intensywnie rozwijany hashcat, posiadający też wersje na GPU – tym później.

Istnieją również narzędzia specjalizowane –  przygotowane dla konkretnego rodzaju sposobu niejawnego przechowywania haseł – np. dla bazy Oracle.

Jaka jest szybkość działania tych narzędzi? Zależy to od szybkości procesora, tzn. w tym przypadku głównie chodzi o:

• ilość core-ów (możliwość zrównoleglenia obliczeń),
• taktowanie procesora (ilość wykonanych instrukcji w jednostce czasu),
• obsługę SSE2 (dzięki temu można w jednym takcie zegara wykonać kilka instrukcji).

Co ciekawe, obecnie wiele mniejsze znaczenie (choć nie znikome) ma generacja procesora – pod warunkiem, że obsługuje przynajmniej zestaw instrukcji SSE2 (daje to możliwość realizacji kilku prostych operacji arytmetycznych w jednym cyklu zegara).  Generalnie faworyzowane są również procesory Intela (m.in. ze względu na lepszą obsługę SSE) oraz uruchamianie crackera w środowisku 64 bitowym.

Po drugie, bardzo istotnym czynnikiem są optymalizacje samego algorytmu wykonującego łamanie hasha (w tym również optymalizacje zastosowane przez kompilator).
Przykładowo dla funkcji MD5, korzystając z Cain&Abel na średniej klasy procesorze – Core2Duo E2140 (2 rdzeniowy, 3GHz) można osiągnąć prędkość ok. 10 milionów sprawdzeń hashy MD5 na sekundę. Na tym samym sprzęcie, narzędziem BarsWF udało się osiągnąć prędkość około 100 milionów sprawdzeń , choć jest to efekt wielokrotnych oraz dość drastycznych optymalizacji –  twórca narzędzia zresztą przedstawił graficznie optymalizacje swojego algorytmu (od pierwszej wersji przyspieszenie około 100 razy!).

 Za http://3.14.by/en/md5/

2. GPU

Dobrych kilka lat temu zaprezentowane zostały crackery oparte o nowoczesne karty graficzne (NVIDIA – technologia CUDA lub AMD Radeon – technologia Stream). Ich główną zaletą jest skokowy wzrost wydajności w porównaniu do odpowiedników działających na procesorach. Skąd ten przyrost mocy obliczeniowej? Otóż nowoczesne GPU (NVIDIA lub Radeon) złożone są z wielu ALU (Aritmetic Logic Unit) czy tzw. procesorów strumieniowych (ang. stream processor) – w przypadku łamania haseł chodzi po prostu o jednostki mogące równolegle realizować pewne operacje matematyczne na liczbach całkowitych. Obecnie, niektóre karty graficzne mogą się składać z przeszło 3000 ALU (np. Radeon HD 5970 posiada ich 3200). Obrazowo można powiedzieć, że łamanie pojedynczego hasha (wyliczanie funkcji hashującej) jest zrównoleglane na procesory strumieniowe. To w pewnym uproszczeniu tak jakbyśmy posiadali 3000 corowy CPU.

Jaką możemy osiągnąć szybkość? Przykładowo, na wspomnianym Radeonie HD 5970 jest to około 8.5 miliarda hashy md5 / sekundę! Czyli nawet blisko 1000 razy szybciej niż daje Cain&Abel na CPU. W znacznej części przypadków przyrost wydajności przy zastosowaniu GPU nie jest aż tak imponujący, choć i tak spory (ok 50-100 razy) – w porównaniu z CPU o podobnej cenie.

Ciekawe porównanie szacujące prędkość dla różnych kart graficznych dostępne jest tutaj:  Warto zwrócić uwagę na ostatnią kolumnę, gdzie wyliczony jest stosunek: szybkość łamania / cena.

(C) Ivan Golubev, za http://golubev.com/gpuest.htm

Z tego ostatniego można wyczytać jeszcze jeden interesujący fakt: z punktu widzenia odzyskiwania haseł, o wiele bardziej wydajne są karty Radeon.  Z czego to wynika? AMD ma strategię budowania kart zbudowanych z większej liczby procesorów strumieniowych, natomiast są to jednostki o wiele prostsze niż konkurencji. Nvidia nadrabia właśnie większą specjalizacją jednostek oraz szybkością zegara (co całkiem nieźle wychodzi w głównym zastosowaniu: tj. przetwarzanie grafiki). W przypadku odzyskiwania haseł prace można bardzo mocno zrównoleglać (1 hash liczę na osobnym ALU) – wygrywa więc AMD (średnio około trzykrotnie – patrz  stosunek SHA1 perf. per $). Z innej strony, o wiele trudniej napisać jest odpowiedni algorytm na procesory graficzne AMD niż nVidii (głównie za sprawą kiepskiej dokumentacji dostarczanej przez AMD). Zmienia się to wprawdzie za sprawą OpenCL, choć jeszcze nie jest idealnie.

Popularnymi narzędziami, które implementują algorytmy łamiące na GPU są:

• hashcat – tzw. wersje OCL tego narzędzia (dostępne na systemu Windows oraz Linux) – osobna wersja specjalizowana jest do odzyskiwania pojedynczego hashu (oclHashcat-lite), a osobna do odzyskiwania wielu hashy (oclHashcat-plus). Aktywnie rozwijany.

oclhashcat-lite (optymalizacja dla łamania 1 hashu) – pracujący z szybkością 10 miliardów hashy na sekuncę, (C) atom, za http://hashcat.net/oclhashcat-lite/

• ighashgpu (dostępny tylko na Windows)

ighashgpu pracujący w trybie hybrydowym – 2 GPU oraz 4 core-y procesora, pracujący z szybkością 5,8 miliarda hashy / sek. (C) Ivan Golubev, za http://www.golubev.com/hashgpu.htm

• rainbowcrack (Windows lub Linux)
• cryptohaze (Windows lub Linux)
• http://3.14.by/en/md5/ – bardzo szybki cracker dla MD5, niestety nie rozwijany od dłuższego czasu
• whitepixel – eksperymentalny cracker MD5, dostępny w również w formie OpenSource
• John The Ripper – rozszerzenia dla GPU – choć tutaj wsparcie jest od niedawna
• Komercyjne narzędzia z: Elcomsoft czy InsiderPro

3. Opłacalność wynajmowania Amazon Elastic Compute Cloud (EC2)

Amazon udostępnia dość elastycznie kosztową usługę wynajęcia klastrów obliczeniowych – w naszym przypadku szczególnie interesujące może być zapewnienie klastrów z GPU NVIDII. Bazują one jedna na układach TESLA, które wypadają słabiej niż nawet proste karty RADEON za około 350 zł. Sprawia to, że pomysł z punktu widzenia ekonomicznego ma niewielki sens (choć nie wymaga zakupu własnego sprzętu). Problematyczna może być również kwestia poufności (wysyłamy jednak hashe na zewnętrzny serwer).

Metody ochrony

1. Wybór funkcji hashującej

Warto zauważyć że z popularnie wykorzystywanych funkcji skrótu największą szybkość hashowania można osiągnąć dla funkcji MD5, wolniejsze jest wykonanie funkcji SHA-1, a jeszcze wolniejsze – funkcji SHA-512. Z kolei im wolniejsze wykonanie funkcji, tym wolniejszy proces odzyskiwania hasła. Spadek wydajności można zaobserwować np. na benchmarkach publikowanych na stronie wykorzystującego GPU oclHashcat-lite (optymalizacja dla jednego hasha).

MD5 –  8223 miliona hashy na sekundę
SHA-1 – 2852 miliona hashy na sekundę
SHA-512 – 81 miliona hashy na sekudnę

Z punktu widzenia ochrony są istotne są tutaj dwa elementy:

• im wolniej działa funkcja hashująca tym wolniej działa crackowanie
• funkcje MD5 oraz SHA1 nie są całkowicie bezpieczne kryptograficznie – głównie występuje w nich problem z tzw. kolizjami. Nie ma to bezpośredniego wpływu na zastosowanie przechowywania haseł w formie zahashowanej, jednak używanie funkcji, o których wiadomo że mają pewne problemy z bezpieczeństwem nie jest zalecane.

2. Hashe solone

Niekiedy do przechowywania w bazie stosuje się tzw. hashe solone. Na czym polega różnica pomiędzy składowaniem samego hashu? Metoda ta daje odporność ataki polegające na zesłownikowaniu hashy (np. opisana wcześniej metoda tablic tęczowych), nie chroni jednak przed pozostałymi opisanymi wcześniej typami ataków (wyczerpujące, słownikowe, hybrydowe).

W momencie zapisu w bazie hasła użytkownika tworzony jest dodatkowy losowy ciąg, tzw. salt. Następnie do soli doklejane jest hasło i na tak powstałym ciągu wykonywana jest funkcja hashująca. W bazie przechowywany jest zarówno cały hash wynikowy jak i wygenerowany per użytkownik salt.

Hasło “solone”

Co nam to daje? Każde hasło może być zapisywane na tyle sposobów na ile można zapisać salt – utrudnia to słownikowanie, ale nie uniemożliwia np. ataków siłowych (atakujący posiada hash oraz salt – i te dwie wartości wprowadza do crackera). W tym przypadku, można również liczyć na spowolnienie ataku w przypadku jednoczesnego crackowania wielu hashy (dla każdego hasła salt będzie inny). Przykładowymi narzędziami, które wspierają odzyskiwanie haseł solonych jest wcześniej wspominana rodzina hashcat. Warto też wspomnieć, że salt jest ideą a nie konkretnym algorytmem (można np. zamienić kolejność sklejania – na początek hasło, później salt, czy zastosować jeszcze inne kombinacje).

3. Wielokrotne hashowanie

Dość skuteczną metodą zwiększenia mocy obliczeniowej wymaganej do złamania hasła jest wielokrotne wykonywanie funkcji hashującej na danym haśle. Przykładowo, w nowszych systemach Linux, hasło przechowywane w pliku /etc/shadow jest hashowane soloną funkcją SHA-512, a ilość hashowań per hasło wynosi domyślnie 5000. Zresztą ta ostatnia wartość jest konfigurowalna. Tego typu zachowanie powoduje spadek wydajności crackerów właśnie o 5 000, przy jednoczesnym niezauważalnym spadku wydajności dla użytkownika podczas logowania (znacznie mniejszym niż 1 sekunda).

Inne zastosowania GPU

W tekście wspominałem głównie o łamaniu hashy. GPU znalazły jednak podobne zastosowanie również dla innych algorytmów:

• Łamanie PSK WPA/WPA2 – np. narzędzie pyrit
• Łamanie wolumenów Truecrypt, backupów iPhone, Blackberry, WPA/WPA2 PSK, np.: IGPRS
• Łamanie RAR, np.: crark
• Łamanie ZIP: komercyjne narzędzie by accent  
• Jeśli już mowa o komercyjnych łamaczach haseł, to warto wspomnieć o bogatej ofercie firmy elcomsoft (m.in. wsparcie dla PDF, MS Office).

— Michał Sajdak (michal.sajdak<at>securitum.pl)