Odwracanie hashy - optymalizacja ekstremalna
Ponieważ piszę program służący do łamania hashy, naturalnym jest że staram się go jak najlepiej zoptymalizować. Najpierw są proste metody - ograniczyć ilość wykonywanych operacji, zamienić wszystkie wartości jakie można przewidzieć na stałe; usunąć wszelkie głupoty jakie ktoś mógł wrzucić do kodu wybranego algorytmu (niech ktoś zgadnie jak wygląda zamiana wartości binarnej hasha na tekst w formie hex przy popularnych implementacjach). Dalej jest użycie optymalnych flag kompilatora (i dobry kompilator też robi swoje). To wszystko jest bardzo proste, łatwe i przyjemne, jednak nie daje zbyt oszałamiających wyników. Owszem, to też się liczy - ale to jest niewiele zmian, daje to niewielkie pole do popisu.
Dalej mamy optymalizację na nieco niższym poziomie - stosowanie różnych kruczków programistycznych typu "loop unrolling" (choć po prawdzie to kompilator też potrafi zrobić), optymalizacja pod właściwą architekturę - zamiast porównywać jeden do jednego, można stosować np. SSE i porównywać osiem do ośmiu jednocześnie. Jeszcze dalej jest właśnie odwracanie hashy.
Przykładowo, jeśli przy generowaniu hasha md5 na końcu dodawane są jakieś wartości - stałe - a następnie zwracany jest wynik, sprawa jest bardzo prosta. Można tę część usunąć z algorytmu, w zamian jednak usuwając - dokładnie tak samo, te same wartości - z hasha początkowego, z którym porównujemy. Oczywiście nie zawsze to jest tak oczywiste, ale mniejsza z tym.
Przykładowo ostatnią operacją przed zwróceniem wygenerowanego hasha MD5 jest takie coś:
wOut[0] = a+Ca; wOut[1] = b+Cb; wOut[2] = c+Cc; wOut[3] = d+Cd;
Ca, Cb, Cc, Cd są znane - ich wartości to odpowiednio 0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476.
Należy jeszcze spojrzeć na definicję czym jest wOut:
#define wOut((UINT4 *)pDigest)
No i wszystko jasne. pDigest jest typu char*, to z niego odczytuje się wygenerowany hash. Ponieważ zawsze porównujemy jeden hash z hashem wygenerowanego słowa, należy zrobić taką magię:
#define wIn((UINT4 *)hash) wIn[0] -= 0x67452301; wIn[1] -= 0xefcdab89; wIn[2] -= 0x98badcfe; wIn[3] -= 0x10325476; #undef wIn
Finito! W ten sposób hash wejściowy (oczywiście wcześniej przerobiony na wersję binarną, nie zakodowaną w hex) staje się jedną wielką bzdurą, która nijak się ma do prawdziwego hasha - jednak dokładnie taką samą bzdurę wygeneruje zmodyfikowany algorytm MD5 - należy mu po prostu wywalić część która te wartości dodaje. W ten sposób mamy pewną wymianę - na początku, gdy program startuje, jeden raz wykonujemy pewne operacje - w tym wypadku odjęcie pewnych wartości. Jednakże dla każdego wygenerowanego słowa generowany jest również hash - za każdym razem oszczędzając operacje potrzebne do dodania tych wartości. Normalnie by były wykonywane non stop, cały czas, spowalniając proces - tutaj są usunięte, nie ma ich, więc nic nie spowalniają.
Idąc dalej, należy zwrócić uwagę z czego składa się algorytm MD5. Na początku może chwilę zająć zorientowanie się co robi:
MD5STEP(I, a, b, c, d, AC49, w0, S41);\ MD5STEP(I, d, a, b, c, AC50, w7, S42);\ MD5STEP(I, c, d, a, b, AC51, w14, S43);\ MD5STEP(I, b, c, d, a, AC52, w5, S44);\
- są to cztery pierwsze operacje ostatniej rundy generowania hasha. Oczywiście samo to nic nam nie daje, należy wiedzieć co się kryje pod tymi wartościami. Nieco wyżej jest wyjaśnienie:
#define MD5STEP(f, a, b, c, d, AC, x, s) {\
(a) += f ((b), (c), (d));\
(a) += (AC) + (x);\
(a) = ROTATE_LEFT ((a), (s));\
(a) += (b);\
}
// (...)
#define I(x, y, z)((y) ^ ((x) | ~(z)))
// (...)
#define ROTATE_LEFT(x, n)(((x) << (n)) | ((x) >> (32-(n))))
I teraz już jest wszystko jasne. a, b, c, d to wartości które się non stop zmieniają, a na sam koniec generowania hasha to one są nam zwracane - po prostu przypisuje się je do wcześniej wspomnianej zmiennej wOut, na odpowiednich offsetach (w kolejności a,b,c,d właśnie). AC41, AC42, AC43, AC44 to wcześniej zdefiniowane stałe.
Proces odwracania należy oczywiście zacząć od końca - pierwszą część już mamy z głowy, teraz należy powalczyć z tymi MD5STEP. Ostatnią operacją MD5, a więc pierwszą którą należy się zająć jest:
MD5STEP(I, b, c, d, a, AC64, w9, S44);\
Brakuje nam tu tylko jednej wartości - w9. S44 i AC64 są znane (wcześniej zadeklarowane stałe). I to funkcja, b,c,d,a to liczby które się zmieniają i nas niespecjalnie obchodzą w tej chwili. Nie chce mi się tutaj tłumaczyć jak do tego dojść, ale proszę mi wierzyć na słowo że w9 to 0, zawsze gdy długość słowa jakie hashujemy jest mniejsza niz 56. Ponieważ i tak nie ma szans na złamanie takiego hasła, można przyjąć że ograniczenie nawet 15 znaków jest w porządku. Mniejsza z tym - w9 to 0 i basta. W ogóle w0 aż do w14 zależą od wejścia (słowa jakie testujemy, hashujemy) - my wejścia nie znamy, ponieważ na tym etapie programu ono nie istnieje - staramy się tylko obrócić hash.
Należy teraz napisać funkcje które pozwolą to odwrócić. Jak? Bardzo proste, należy zacząć od funkcji ROTATE_LEFT i napisać jej przeciwieństwo, o:
#define ROTATE_LEFT (x, n)(((x) << (n)) | ((x) >> (32-(n)))) // zatem... #define ROTATE_RIGHT(x, n)(((x) >> (n)) | ((x) << (32-(n))))
Teraz następna funkcja nam potrzebna - MD5STEP. Jej przeciwieństwo wygląda tak:
#define MD5STEP(f, a, b, c, d, AC, x, s) {\
(a) += f ((b), (c), (d));\
(a) += (AC) + (x);\
(a) = ROTATE_LEFT ((a), (s));\
(a) += (b);\
}
// zatem...
#define MD5STEP_REV( f, a, b, c, d, AC, x, s ) { \
(a) -= (b); \
(a) = ROTATE_RIGHT( (a), (s) ); \
(a) -= (AC) - (x);\
(a) -= f( (b), (c), (d) );\
}
Jak widać - dodawanie jest zmienione na odejmowanie, ROTATE_LEFT na ROTATE_RIGHT, a całość jest zapisana od tyłu. Wszystko do tej pory jest ładne i piękne, ponieważ znamy w9. W głównym programie przygotujemy hash do porównania (pamiętacie że mamy go przedstawionego jako UINT4* pod nazwą wIn, gdzie kolejne offsety przedstawiają zmienne a, b, c, d ?):
MD5STEP(I, b, c, d, a, AC64, w9, S44); // zatem... MD5STEP_REV( I, hD[1], hD[2], hD[3], hD[0], 0xeb86d391,0, 21 );
Tak o, bardzo łatwe. Dokładnie tak samo podstawiamy zmienne, 0xeb86d391 to inaczej AC64 (jest w #define), podobnie jak S44 to 21. Ot, takie stałe zdefiniowane w standardzie MD5. w9 to 0, więc po prostu podstawiamy 0 (należy pamiętać - NIE MAMY DOSTĘPU DO w0-w14, one są generowane na podstawie słowa które generuje hash!).
Dalej niestety są schody, i to paskudne. Ponieważ poprzednim w algorytmie (a następnym przy odwracaniu) krokiem jest takie coś:
MD5STEP(I, c, d, a, b, AC63, w2, S43);\
I tu klops. AC63 znamy, S43 znamy, ale w2 nie znamy i znać nie będziemy. Można zbadać zachowanie algorytmu i przekonać się że przy długości mniejszej niż osiem w2 zawsze wynosi 0, dla długości równej osiem - wynosi 128 (i tu wszystko by było pięknie) jednak dla długości 9 i większej - są to wartości zmienne, których nie da się przewidzieć nie mając wygenerowanego słowa. Więc dalej już tego algorytmu nie odkręcimy taką metodą. Można dalej go odkręcić, ba, można odkręcić całą 4 rundę i kawałek 3, jednak wtedy całość wygląda nieco inaczej i należy od czasu do czasu (dokładniej - gdy zmienią się 4 pierwsze znaki słowa) "przesortować" algorytm, by uzyskać dostęp do działających wartości w0-w3, które nas interesują. Te wartości są kłopotliwe i to bez ich znajomości nie da się więcej zdziałać.
No ale o tym może innym razem.
W następnym odcinku zajmiemy się algorytmem MD4, gdzie taką metodą udało mi się odkręcić całe 7 kroków (i ostateczne dodanie pewnych zmiennych) - bez sortowania, bez problemów - jeden raz wykonana operacja która równoważy wykonywanie jej przy każdym wygenerowanym słowie. Mam nadzieję że wszyscy zainteresowani zrozumieli wszystko, starałem się to w miarę łatwo przedstawić.
Implementację MD5 którą używam można znaleźć tutaj - znajdują się tam opisane zmiany. Jeśli ktoś cofnie do commita numer 34 to będzie mógl zobaczyć jak plik oryginalnie wyglądał.
Mam nadzieję że komuś taka informacja się przyda.
A jaki jest zysk wydajnościowy?
W tym przypadku, gdy udało mi się odwrócić tylko 1 krok (no i 4 operacje dodawania) to prędkość na moim komputerze, na jednym wątku, wzrosła o ok. 200k/s. Z 1,5 mln/s do 1,7 mln, więc zysk jest.
Dla porównania MD4, przy którym odwróciłem 7 kroków (i te zmienne nieszczęsne) zwiększył prędkość i niecały milion/s. Teraz jest 3 mln/s.
To i tak nic, taki barswf potrafi robić 5mln/s na jednym wątku.. ale też jest nieco inaczej zaprojektowany.