Połam to jeszcze raz

Niedawno sekurak.pl zorganizował kolejny konkurs z łamaniem hashy. Tym razem dowiedziałem się o nim przypadkiem – ot, wpadło powiadomienie z Discorda, które akurat zauważyłem. Rzuciłem okiem, jest link do wpisu, są hashe, więc warto spróbować, bo do wygrania był kolejny dostęp do Akademii Sekuraka 2024.

Miałem w zasadzie gotowca na podstawie poprzedniego wpisu i writeupu, więc liczyłem, że kilka sztuk wpadnie. I faktycznie, nie zawiodłem się. Opisane wcześniej metody pozwalały złamać 7 do 9 hashy. Skąd rozbieżność? Zależy jak liczyć i jaki się utworzyło dedykowany słownik.

Zajmijmy się trzema hashami, z którymi mógł być problem. Pierwszy to db13ca089eb4860896567399a30558f2c1fc69e7:sekurak.academy.
Przyznaję, że zwyczajnie miałem szczęście. W słowniku zagościł bowiem ciąg sekurakacademy, a OneRuleToRuleThemAll zrobiło resztę. Aż się zdziwiłem, czemu to wpadło, więc sprawdziłem.

Sprawdzenie, która reguła spowodowała dopasowanie robi się zgodnie z opisem z dokumentacji hashcata poprzez dodanie parametrów

--debug-mode=1 --debug-file=matched.rule

Okazuje się, że OneRuleToRuleThemAll ma takie cudo jak

l i7.

Przekładając na bardziej zrozumiały język: zamień wszystkie litery na małe i wstaw kropkę po siódmym znaku. Chwilę po godzinie dziewiętnastej odesłałem 8 złamanych hashy.

Kolejne hasło, które mogło sprawić trudność to złożenie nie dwóch, ale trzech wyrazów. Czułem, że będzie, bo tego typu pojawiały się w poprzednich edycjach. Schemat był zawsze ten sam – dwa wyrazy oddzielone krótkim spójnikiem. Sprawdziłem, ile jest krótkich spójników w moim słowniku. Samych dwuznakowych było aż 428. Uznałem, że to zbyt wiele. W dodatku większość się nie nadawała – zz czy yy po prostu mi nie pasowały.

Postanowiłem spróbować z dwuliterowymi. Ręcznie przejrzałem wszystkie dwuliterowe słowa, wybrałem 25, które wydały mi się najbardziej prawdopodobne, zapisałem do pliku. Dorzuciłem jeszcze 3 jednoliterowe spójniki: i, o, a. Na koniec dodałem 19 wyrazów trzyznakowych. Tak powstał plik laczniki.txt.

Stwierdziłem też, że dla pełnego słownika języka polskiego i tak wyszłoby wiele kombinacji. Hasła z poprzednich edycji były umiarkowanej długości. Postanowiłem wziąć na warsztat tylko wyrazy od 2 do 9 znaków. Nazwałem go 29_slownik_all_nopl.txt. Liczył 845 tys. wierszy.

Krótkim skryptem w Pythonie utworzyłem słownik z wszystkimi kombinacjami wyrazów z 29_slownik_all_nopl.txt oraz 57 łączników. Wynikiem był spory, ale nadal akceptowalny słownik zawierający 48 mln wierszy.

Potem już standardowo – operacja na dwóch słownikach. Pierwszym był 29_slownik_all_nopl_laczniki.txt zaś drugim 29_slownik_all_nopl.txt. Tak udało się złamać 61d54fe02ce6edcde2f5762f2677b3c83d876417:trudnotozgadnac
i kwadrans po dwudziestej pierwszego dnia odesłałem 9 haseł.

Wersja z tworzeniem słownika na dysku nie jest może najefektywniejszym podejściem do haseł zbudowanych z trzech słów, ale jak widać wystarczyła.

Warto w tym miejscu odnotować, że słowo to pojawiało się wcześniej i gdyby człowiek pomyślał, to mógł przyjąć, że będzie i tym razem. Cóż, po fakcie każdy mądry.

Ostatnie hasło jest ciekawą i pouczającą sprawą. Na discordowym kanale pojawiła się informacja, że już dwie osoby mają 9 haseł, w dodatku gdyby połączyć ich odpowiedzi, to będzie komplet, czyli wszystkie hasła z konkursu zostały złamane. Dopuszczałem możliwość, że coś przeoczyłem, bo jak wspominałem do konkursu przystąpiłem w pośpiechu. Na innym kanale Patryk (jego writeup z łamania haseł znajdziecie na tutaj – polecam) też pochwalił się złamaniem 9 hashy.

Po krótkiej rozmowie czego komu brakuje i ustaleniu, że faktycznie chodzi o nas, Patryk rzucił podpowiedzią, że brakujący hash jest podobny do już złamanego, ale po polsku. Cóż, wielkiego wyboru nie było i wkrótce, po dosłownie czterech próbach wykonanych ręcznie, do złamanych dołączył:
283d5cb401e9de6a2e56f97166a639479fb86aee:akademiasekuraka
Komplet haseł odesłałem o 20:23 drugiego dnia konkursu.

Zarówno słowo akademia jak i sekurak oczywiście miałem w słowniku. Zabrakło wersji z deklinacją. Mam zatem pewne wnioski dotyczące słownika na przyszłość…

UPDATE: Artykuł z oficjalnym rozwiązaniem konkursu i statystykami rozwiązań.

Połam to lepiej

Niedawno brałem udział w konkursie organizowanym przez Sekurak.pl. Konkurs polegał – jak to się potocznie mówi – na „łamaniu haseł”. Poprawniej byłoby rzec, że polegał na odzyskiwaniu haseł na postawie hashy, ale mniejsza o to. Udało mi się wygrać, tzn. złamałem największą ilość haseł jako pierwszy. Teoretycznie więc mógłbym na tym poprzestać, ale – z perspektywy patrząc – pewne rzeczy można było zrobić albo opisać lepiej. Oryginalny writeup mój i innych zwycięzców można znaleźć w tym artykule, natomiast ten wpis jest jedynie jego uzupełnieniem.

Dla przypomnienia, jeśli chodzi o gotowce, skorzystałem ze reguł wbudowanych w hashcata, reguły OneRuleToRuleThemAll[1]. Zaś jeśli chodzi o gotowe słowniki to użyłem RockYou, Ignis (10 mln) oraz słownika języka polskiego dostępnego w Debianie w pakiecie wpolish.

Co można zrobić lepiej? Przede wszystkim ten wpis na blogu daje namiar na „growy” słownik języka polskiego. Jest on mniejszy od tego z wpolish. Zawiera 3,2 mln linii, zamiast 4,3 mln. Mogłoby wydawać się to wadą, ale… przy skomplikowanych operacjach większy słownik nie musi być lepszy.

Słownik growy zawiera znaki końca linii w formacie windowsowym. Można je przekształcić na format uniksowy np. w taki sposób:

cat slowa.txt | perl -ne 'chomp; /(\S+)/ && print $1,$/' > slowa_unix.txt

Taka wersja przyda się w kolejnych operacjach.

Słownik wpolish można z kolei znormalizować przez usunięcie wielkich liter. Nie mają one znaczenia, bo występują na początku i któraś reguła hashcata z pewnością uwzględnia takie przekształcenie. Polecenie

cat /usr/share/dict/polish | tr "[:upper:]" "[:lower:]" | sort -u > wpolish_lower.txt

redukuje wielkość słownika o 46k wierszy, czyli nieco ponad 1%.

Z kolei jeśli chodzi o najbardziej kompletny słownik języka polskiego, to będzie nim złączenie znormalizowanego wpolish oraz growego z poprawionymi końcami nowej linii:

cat slowa_unix.txt wpolish_lower.txt | sort -u > slownik_all.txt

Wynik jest o jedynie 5k linii większy od oryginalnego wpolish.

Pozbycie się pl-znaków ze słownika:

cat slownik_all.txt | tr "ąćźżńłóęś" "aczznloes" | sort -u > slownik_all_nopl.txt

Łatwo zauważyć, że jeśli ktoś będzie miał hasło, które jest wyrazem w języku polskim, ale zapisanym w sposób mieszany, częściowo z polskimi znakami, częściowo wersją polskawą, to nasze słowniki taki wyraz ominą. Przykładem takiego słowa może być wyraz żółty zapisany jako zólty. Co wtedy?

Pomóc może zrobienie własnej reguły hashcata, wykorzystującą zastąpienie, czyli s:

Replace sXY Replace all instances of X with Y

Można od razu w podobny sposób potraktować „jednoliterowe” błędy ortograficzne i regułą zastąpić u przez ó i na odwrót. Niestety, z tego co widzę przy pomocy samego hashcata nie da się zrobić ani przekształcenia ch -> h, ani odwrotnego. W dodatku powyższe zastąpienie dotyczy wszystkich wystąpień, a niezupełnie o to chodzi. Jednak lepszy rydz, niż nic.

Tyle gwoli uzupełnienia. Regułę hashcata pozostawiam do samodzielnego montażu, a o zewnętrznym skrypcie do przekształceń jeszcze pomyślę.

[1] Celowo linkuję do genezy powstania, której lekturę gorąco polecam, nie samej reguły.

Dlaczego k-anonimowość nie jest dobra przy hasłach?

Na z3s.pl pojawił się artykuł o tym, czym jest k-anonimowość. Jest to dobry artykuł i warto go przeczytać przed lekturą tego wpisu. Nie zgadzam się jedynie z tezą, że w przypadku haseł jest to bezpieczna metoda sprawdzania. Napisałem komentarz, ale pewnie nie wszyscy czytelnicy bloga tam trafią. Ponieważ bawię się z bazą hashy z HIBP i planuję wkrótce wpis na ten temat, uznałem, że jest dobra okazja do wstępu.

Moja teza jest taka, że w przypadku haseł k-anonimowość wcale nie jest taka bezpieczna, jak jest to przedstawiane. Zgodnie z artykułem obecnie dla hashy z bazy HIBP pierwsze 5 znaków występuje od 381 do 584. Czyli podczas sprawdzenia strona trzecia nie poznaje ani hasła, ani jego pełnego hasha. Przekazywane jest jedynie pierwszych 5 znaków hasha, czyli – tu moja interpretacja – ma jedynie 1/381 do 1/584 prawdopodobieństwo, że zna właściwy hash.

Gdyby przyjąć, że strona trzecia jest złośliwa, warto też przyjąć, że jest inteligentna. Czyli zamiast prawdopodobieństwa zwykłego użyje prawdopodobieństwa ważonego, uwzględniając ilość wystąpień danego hasha. Dla przykładu z artykułu na z3s.pl i hasła P@ssw0rd mamy zwracanych 543 różnych hashy:

curl -s https://api.pwnedpasswords.com/range/21BD1 | wc -l

Natomiast suma wystąpień wszystkich hashy w momencie pisania tego wpisu wynosi 60808.

curl -s https://api.pwnedpasswords.com/range/21BD1 | awk -F ":" '{sum += $2} END {print sum}'

Nasz hash wystąpił 52579 razy. Znając zwyczaje ludzi dotyczące haseł i stosując prawdopodobieństwo ważone uzyskujemy 86% szansę na to, że chodzi o hash należący do hasła P@ssw0rd. Pewności nie ma, ale z 1/543 czyli z ~0,18% robi się 86%, czyli jakieś 467 razy więcej. Ups!

Oczywiście nie znamy tu samego hasła. Znamy jedynie – a i to jedynie ze sporym prawdopodobieństwem – jego hash. O tym, że to niekoniecznie jest problem, może będzie w którymś kolejnym wpisie.

W każdym razie gdybym był serwisem, to bałbym się odpytywać serwis trzeci o hashe haseł moich użytkowników. Użytkowników podejrzewam o proste, słownikowe hasła, jakiś serwis trzeci. Zwłaszcza jeśli ten serwis ma/może mieć także inne informacje, które pozwalają mu ustalić kto pyta o hasło. Tak właśnie może być w przypadku Cloudflare, który może dostawać część ruchu od użytkownika w ramach CDN, DNS lub DoH. Prosta korelacja czasowa może w tym przypadku prowadzić do powiązania hasha hasła z IP użytkownika. Jeśli chcemy sprawdzać hasła, to lepszym rozwiązaniem jest stworzenie lokalnej kopii bazy którą pobierzemy z HIBP.

Co nie znaczy oczywiście, że k-anonimowość ogólnie nie spełnia swojego zadania. Po prostu mam wrażenie, że akurat w przypadku hashy hasła i tej konkretnej implementacji nie jest tak bezpieczna, jak jest to przedstawiane.

Warto też zauważyć, że hasło z którym mamy tu do czynienia jest proste/populare. Dla innych pięcioznakowych początków hashy wystąpienia mogą rozkładać się inaczej, bez tak silnego wskazania na konkretny hash.

UPDATE Tak naprawdę nie ma potrzeby używania całej bazy hashy i ilości ich wystąpień z HIBP (>20GB). Najczęściej występujące 100 tys. hashy to raptem 3,2 MB. Najczęstszy milion – 32 MB.