Odwracanie hashy - część druga
Jak już wcześniej pisałem jeśli nam zależy na znacznej poprawie szybkości działania programu do łamania haseł, najlepsze co można zrobić to spróbować ograniczyć liczbę kroków jaką wykonuje algorytm, przez odpowiednie spreparowanie hasha.
Teraz dalszy ciąg i nieco wyjaśnienia jak to dalej rozwinąć; ciągle zostajemy przy MD5 :)
Ostatnio skończyliśmy na barierze w formie w2. Jeśli spojrzeć nieco wyżej, cała ostatnia runda wygląda tak:
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);\ MD5STEP(I, a, b, c, d, AC53, w12, S41);\ MD5STEP(I, d, a, b, c, AC54, w3, S42);\ MD5STEP(I, c, d, a, b, AC55, w10, S43);\ MD5STEP(I, b, c, d, a, AC56, w1, S44);\ MD5STEP(I, a, b, c, d, AC57, w8, S41);\ MD5STEP(I, d, a, b, c, AC58, w15, S42);\ MD5STEP(I, c, d, a, b, AC59, w6, S43);\ MD5STEP(I, b, c, d, a, AC60, w13, S44);\ MD5STEP(I, a, b, c, d, AC61, w4, S41);\ MD5STEP(I, d, a, b, c, AC62, w11, S42);\ MD5STEP(I, c, d, a, b, AC63, w2, S43);\ MD5STEP(I, b, c, d, a, AC64, w9, S44);\
Ostatni krok usunęliśmy już wcześniej, bo nie było z tym najmniejszego problemu. Zatrzymało nas właśnie nieszczęsne w2, bo jego wartości nie sposób przewidzieć w normalny sposób. Ale my nie jesteśmy normalni ;-)
Wspomniałem też że po zbadaniu zachowania algorytmu, można dojść do wniosku że przy długości 1-7 wartość zawsze wynosi 0. Można to wykorzystać by nieco bardziej odkręcić algorytm. Zatem postanowiłem pokazać dwie drogi - prostą i trudniejszą (i wymagającą odpowiedniej konstrukcji programu).
Pierwsza sprawa jest prosta, bo wystarczy stworzyć dwie wersje algorytmu - jedna dla długości 1-7, druga dla długości większych. Oczywiście wtedy jedna wersja będzie wyższa, z racji usunięcia wielu operacji, a druga wolniejsza (początkowa, "zwykła" prędkość po usunięciu ostatniego kroku).
Przypomnę że w głównym programie - sprawdzającym - mamy początkowe przygotowanie hasha; w tym miejscu należy zrobić operacje odwrotne do tych, które usuwamy z algorytmu md5.
A więc kolejno. Mamy już zadeklarowaną wcześniej funkcję MD5STEP_REV, mamy odwrotność ROTATE_LEFT, znamy wartość [AC..] oraz [S..]. Wszystko robiąc od końca, należy mieć takie coś, o:
//hD[0]..hD[3] == a..d MD5STEP_REV( I, hD[2], hD[3], hD[0], hD[1], 0x2ad7d2bb, 0, 15); MD5STEP_REV( I, hD[3], hD[0], hD[1], hD[2], 0xbd3af235, 0, 10); MD5STEP_REV( I, hD[0], hD[1], hD[2], hD[3], 0xf7537e82, 0, 6); MD5STEP_REV( I, hD[1], hD[2], hD[3], hD[0], 0x4e0811a1, 0, 21); MD5STEP_REV( I, hD[2], hD[3], hD[0], hD[1], 0xa3014314, 0, 15); MD5STEP_REV( I, hD[3], hD[0], hD[1], hD[2], 0xfe2ce6e0, 0, 10); MD5STEP_REV( I, hD[0], hD[1], hD[2], hD[3], 0x6fa87e4f, 0, 6);
Ok, to było dość oczywiste. Najpierw jednak należy sprawdzić długość sprawdzanego słowa i wykonać te operacje tylko jeśli długość jest mniejsza niż 8. I należy utworzyć drugi algorytm do kalkulowania hasha który tych operacji nie posiada - i jego używać dla mniejszych długości. Proszę sobie tu wybić z głowy jakikolwiek if czy switch wewnątrz tych funkcji - szkoda czasu procesora na dodatkowe cmp.
Zapomniałem wyjaśnić jedną rzecz - dlaczego teraz aż tyle kroków można było odkręcić? Odpowiedź jest bardzo prosta - jeśli dowolny z w1..13 wynosi 0, to NA PEWNO wszystkie o wyższym numerze również będą wynosiły 0 (poza w14, który będzie miał wartość zależną od długości - jednak można to bardzo łatwo ustalić wcześniej, gdyż jest to długość przesunięta w prawo o pewną wartość, do znalezienia w specyfikacji). Jeśli zatem udało nam się przejść krok z w2, to kroki poprzednie - w11, w4, w13, w6, w15, w8 - również można przejść, również podstawiając tam 0.
Ok, to tyle jeśli chodzi o łatwą część. To teraz nieco więcej magii, proszę państwa. W tej magii będziemy mogli odwrócić nawet więcej, gdyż - nie inaczej - będziemy znali wszystkie w0..w14. Tyle że wtedy wymiana nie jest tak prosta jak teraz - raz wykonać operacje i spokój. Teraz podobne operacje trzeba będzie wykonywać co jakiś czas, co jakiś czas też zmieniać hash z którym porównujemy. Ale najpierw kolejne słowo wyjaśnienia. Czym są te magiczne wartości w0..w14? To nic innego jak wartości słowa wejściowego, w pewnych pozycjach. Dlatego też mając odpowiednio krótkie słowo (1-7 znaków), w2 nie było w ogóle ustawiane, a więc znamy jego wartość - 0.
Ok, a co jeśli chcemy bardziej obrócić? Należy znać wartość w0..w3, basta. Nie liczyc na to że będzie wynosiło zero. Jak? Bardzo łatwo, należy stworzyć algorytm który będzie nam obliczał te wartości na podstawie wejścia. Będzie to mniej "opłacalna" wymiana, jednak nadal dająca ogromne korzyści - możliwość odkręcenia znacznej partii kodu. Należy po prostu wyizolować funkcję która oblicza w0..w3 i zapamiętywać te wartości; następnie odejmować dokładnie te wartości w podobny sposób jak odkręcaliśmy hash poprzednio - tylko że zamiast podstawiać 0, podstawiamy te wartości. Ktoś zapyta jaki w tym sens, co generację wykonywać to samo w głównej częsci programu, zamiast w samym algorytmie? Kombinować, cudować? Otóż jest w tym sens, jeśli zbadać właściwości algorytmu i to jak on się zachowuje.
Tam tam tam (budowanie napięcia)
Wartości te się zmieniają tylko jeśli zmieni się 5 (i dalszy) znak testowanego słowa. Ciężko to wyjasnić, więc po kolei. Spacja wstawiona dla czytelności, wartości dla w0..w3 są tylko umowne, by przedstawić sens:
// wartosci aaaa aaaaaa // => w0=1, w1=2, w2=3, w3=4 aaab aaaaaa // => w0=1, w1=2, w2=3, w3=4 aaac aaaaaa // => w0=1, w1=2, w2=3, w3=4 // dopoki nie ruszamy wartosci po 4 znaku, wszystko sie zgadza! aaaa baaaaa // => w0=5, w1=6, w2=7, w3=8 aaab baaaaa // => w0=5, w1=6, w2=7, w3=8 // (..) i tak dalej
Zatem sprawa jest prosta. Nie trzeba generować tych wartości (i odkręcać hash) przy każdym wygenerowanym słowie, przy każdym teście. Wystarczy to robić wtedy (każdorazowo) gdy zmieni się wartość w znaku o indeksie wyższym niż 4. Znowu mamy do czynienia z wymianą, choć nieco mniej opłacalną - zamiast wykonywać pewne operacje za każdym razem, można te operacje - w odwrotnej kolejności - wykonywać raz na X generacji słowa. Nadal się to opłaca i daje ogromne zyski wydajnościowe. Należy tylko napisać odpowiedni generator słów - ja nad swoim pracuję jeszcze, więc na razie kodu brak; w ciągu paru dni powinien już działać.
Uff... część druga zakończona. Jeszcze co nieco napiszę o generatorze słów i w końcu pokażę jak wykonać podobne operacje na MD4. Być może też kiedyś opiszę jak odwrócić algorytm sha1 - ale mówiąc szczerze, nadal nie odkręciłem nawet jednego kroku. Ten kto tworzył ten algorytm był bardzo złośliwy, val >> x na samym końcu :(
A możesz przeprowadzićtaką znalizę dla sha1 a na koniec napisać kod dla platformy CUDA? =)
@lolek, a ile zapłacisz?
Mogę, ale nie mam sprzętu by to testować. Jeśli mi dostarczysz sprzęt to napiszę na platformę CUDA (albo na ati stream, jak wolisz - ale też potrzebuje taki sprzęt)
A skąd jesteś groszek?
Okolice Wrocławia.