Generator hashy z bazą “w chmurze”

Temacik nieco nadmuchany a pomysł prosty – oba moje rozwiązania do łamania hasy (RainbowDB/Hybrid Rainbow DB) korzystają z Google’a jako opcji “last restort” gdy nie mogą nic znaleźć. Ta funkcja jest tym bardziej skuteczna im więcej hashy można znaleźć w Google’u. Ale Googiel idealny nie jest – nie ma ich wszystkich… jeszcze 😉

Postanowiłem pomóc Googlowi być lepszą wyszukiwarką hash’y i stworzyłem prosty generator dla kolejno generowanych haseł. Skrypcik wrzuciłem do kilku darmowych hostingów i pozostało czekać aż dane zaczną się indeksować 🙂

Wynik działania skryptu można zobaczyć choćby tutaj: www.hashe.yoyo.pl

Plik ze źródłem dostępny jest tutaj: hashes.php

Kod można obejrzeć tu:

<html>
<head>
<title>Hash List</title>
</head>
<body>
<div id="content">
<h1>Welcome to Hash List!</h1>

<p>This site will feed search engines with hashes of all common passwords :)</p>

<?
$signs = "qwertyuiopasdfghjklzxcvbnmQWERTYUIOPASDFGHJKLZXCVBNM1234567890`~!@#$%^&*()-=_+[]\\{}|;':\",./<>?";
$howmany = 500;
#$algos = hash_algos();
$algos = array("md5", "sha1");

$index = !isset($_GET['i']) ? 0 : (int)$_GET['i'];
$array_num = !isset($_GET['n']) ? 1 : (int)$_GET['n'];
$array_num = $array_num > 26 ? 25 : $array_num;

function carthezian_set($index, $count=1) {
    global $signs;
    $lists_len = strlen($signs);
    $string = "";
    
    for($i=0; $i<$count; $i++) {
        $r = $index % $lists_len;
        $index = (int)($index / $lists_len);
        $string = $string . $signs[$r];
    }
    
    return $string; 
}

function hash($alg, $pw) {
	if($alg == 'md5') {
		return md5($pw);
	} elseif($alg == 'sha1') {
		return sha1($pw);
	}
}
?>
<h3>Used signs: <?=$signs?></h3>
<h4>Word length: <?=$array_num?></h4>
<h4>Possible passwords: <?=pow(strlen($signs), $array_num)?></h4>

<?if(($index + $howmany) >= pow(strlen($signs), $array_num)):?>
        <a href="?i=0&n=<?=$array_num+1?>">Next &rsaquo;</a>
<?else:?>
        <a href="?i=<?=$index + $howmany?>&n=<?=$array_num?>">Next &rsaquo;</a>
<?endif?>

<table>
<tr>
<th>Password</th>
<?foreach($algos as $alg):?>
<th><?=strtoupper($alg)?> hash of password</th>
<?endforeach?>
</tr>
<?for($i=$index; $i<$index + $howmany; $i++):?>
	<?if($i < pow(strlen($signs), $array_num)):
		$pw = carthezian_set($i, $array_num);?>
		<tr>
		<td><strong><?=$pw?></strong></td>
		<?foreach($algos as $alg):?>
		<td class="hash"><code><?=hash($alg, $pw)?></code></td>
		<?endforeach?>
		</tr>
	<?endif?>
<?endfor?>
</table>

<br />
<?if(($index + $howmany) >= pow(strlen($signs), $array_num)):?>
	<a href="?i=0&n=<?=$array_num+1?>">Next &rsaquo;</a>
<?else:?>
	<a href="?i=<?=$index + $howmany?>&n=<?=$array_num?>">Next &rsaquo;</a>
<?endif?>
</div>
</body>
</html>

Hybrid Rainbow DB

Jakiś czas temu napisałem swoją własną tęczową tablicę i odkąd zainteresowałem się tym tematem zastanawiałem się jak jeszcze bardziej usprawnić tę aplikację. Testowałem różne długości łańcuchów i zauważyłem że zwiększanie długości łańcucha bardzo szybko powoduje znaczne zwiększenie ilości kolizji, co drastycznie obniżało wydajność (nie wspominając o czasie potrzebnym na wygenerowanie całej tablicy). Z tego powodu ostateczna implementacja choć była rzeczywiście tęczową tablicą działała bardziej jak tablica hashy – bo łańcuchy były bardzo krótkie. Ponadto ze statystyk wynikało że bardzo rzadko hasła były odzyskiwane ze środka łańcucha – zdecydowana większość trafień pochodziła z pierwszego hasła w łańcuchu. Pierwsze hasło było przeważnie słownikowe, plus czasem jakiś dodatek w postaci cyfry/zmienionej wielkości liter, itp. Pozostałe hasła w łańcuchu były praktycznie losowe.

Na dobrą sprawę takie wyniki można wytłumaczyć od dawna znaną prawdą: “ludzie nie używają skomplikowanych haseł”. Pomyślałem więc że dużo lepiej byłoby generować hashe ze słów, które są potencjalnie prawdopodobnymi hasłami a nie dla różnych losowych śmieci. Szczególnie można by wykorzystać pewne złe nawyki powielane przez wiele osób, np. typowe “skomplikowane” hasło zaczyna się od dużej litery, później jest kilka małych, a na końcu cyfra lub dwie – przy czym ciąg liter jest wyrazem słownikowym. Tego typu wzorców jest wiele i pomyślałem że można by to wykorzystać. Na dobra sprawę jeżeli zamierzamy sprawdzić jakość haseł z jakiejś aplikacji to nie potrzebujemy 100% trafień, wystarczy że 20% to hasła kiepskiej jakości i te będą wymagały poprawienia.

Czym są hybrydowe tęczowe tablice?

Gdy zacząłem drążyć temat trafiłem na artykuł opisujący podejście, o którym myślałem. Klasyczne tęczowe tablice “wychodzą” od pewnego hasła, z którego generujemy hash, redukujemy go do nowego losowego hasła itd… Zapisujemy pierwsze hasło i ostatni hash a resztę da się odtworzyć gdy będzie potrzebna. Hybrydowe tęczowe tablice mają bardziej rozbudowaną funkcję redukującą – nie tworzy ona całkiem losowych haseł, ale hasła wygenerowane przez sklejenie słów które potencjalnie częściej powinny w hasłach występować. Czyli zamiast generować hasła typu: L;adfa=2ja, tworzone są hasła: abc123, Qwert, Bezpieczne5, itd.

Oba podejścia mają swoje zalety i wady: odpowiednio duże tęczowe tablice mogą przechować większość haseł z danego zakresu – ale będą też przechowywać masę pseudolosowych śmieciowych haseł, których prawdopodobieństwo wykorzystanie jest małe. Hybrydy przechowują dużo mniejszy zakres haseł ale za to takich “stosunkowo prawdopodobnych”, więc mniejsza tablica powinna dawać równie dobre wyniki (dla prostych zestawów haseł).

Koncepcja okazała się znaną ale nie wykorzystywaną równie często jak tęczowe tablice. Cóż… nic nowego nie wymyśliłem ale realizacja pomysłu wydawała mi się ciekawą wprawka do kilku nowych technologii, którym miałem zamiar się przyglądnąć.

Realizacja

O ile RainbowDB działa na bazie: PHP + PostgreSQL + moduł w C do Postgresa, to w Hybrid Rainbow DB postanowiłem wykorzystać zupełnie nowe narzędzia i frameworki. Baza to MySQL, aplikację pisałem w Pythonie na Django.

Realizacja zaczynała się od wygenerowania kilku słowników “składowych” dla złych haseł np.: liczby (od 0 do 100, powtarzające się cyfry do 10 znaków), daty (od 1950 do 2015, we wszystkich kombinacjach np.: YYMMDD, itd.), znaki (pojedyncze, jak również w przeróżnych kombinacjach z klawiatury, alfabetycznie, itd.). Mając takie słowniki zamierzałem wygenerować zbiory hashy ze sklejonych z nich słów na zasadzie: każde słowo z jednego słownika z każdym z drugiego. Jeśli pojedynczy słownik potraktujemy jako zbiór to taka operacja na dwóch lub więcej zbiorach nazywana jest iloczynem kartezjańskim. Wykonanie tego typu operacji jest stosunkowo proste ale nie zamierzałem zapisywać wyniku hashowania każdego tak wygenerowanego hasła. Idealnie byłoby móc zapisać wyniki w sposób podobny jak w tęczowych tablicach, czyli w jednym polu zakodować wynik kilku czy nawet kilkuset hashowań. Do tego musiałem opracować algorytm pozwalający przypisać danemu hasłu z iloczynu kartezjańskiego unikatowy jednoznacznie reprezentujący go numer. Odnosząc to do implementacji tęczowej tablicy, chodziło o funkcje redukującą, która zamieniała hash na numer a następnie generowała n-ty wynik iloczynu kartezjańskiego bez generowania wcześniejszych elementów. To podejście pozwoliło mi przechowywać nawet bardzo długie hasła w postaci kilku bajtów (jako numer) a przez to bardzo efektywnie wykorzystać miejsce.

By dodatkowo poprawić jakość generowanej “hybrydowej tęczowej tablicy” w czasie generowania wykorzystałem wektor bitowy by “odznaczyć” już wygenerowane hasła. Więc gdy dochodziło do ponownego zredukowania hasha na hasło, które już zostało wcześniej wykorzystane i byłby to powodem wystąpienia kolizji to zapisywany zostawał poprzedzający go hash, a proces generowania łańcucha był przerywany. Ten mechanizm znacznie zmniejszył częstotliwość występowania kolizji (więc późniejsze wykorzystanie tablic będzie szybsze), a jako efekt uboczny skrócił czas generowania tablic.

Zastosowałem jeszcze jedną sztuczkę by dodatkowo zmniejszyć rozmiar tablic. W większości tablic które utworzyłem nie było potrzeby przechowywać pełnych hashy aby móc odtworzyć hasło. W małych tablicach wystarczające były pierwsze 2~3 bajty, w większych 4~8. Zacząłem więc skracać długość przechowywanych hashy tak by utrzymać stosunkowo małą ilość kolizji. Dzięki tej optymalizacji mogłem na tej samej powierzchni dyskowej zapisać nawet 10-krotnie więcej danych.

Wnioski

Pobawiłem się moimi nowymi tablicami i mam kilka spostrzeżeń. Ogólnie koncepcja się sprawdziła i hybrydy “trzaskają” nawet hashe, których moje wcześniejsze narzędzie nie ruszało (np. kilka hashy z pierwszej strony Top uncracked poprzedniego narzędzia). Użycie tego narzędzia przy audytach jest o tyle bardziej zasadne że złamie ono sporą część “kiepskich” haseł, które powinny zostać zmienione – a odpuści pseudolosowe, których prawdopodobieństwo wykorzystania a realnym ataku jest dużo mniejsze.

Hybrydowe Tablice mają też wady, których nie miało wcześniejsze rozwiązanie:

  • jest dużo wolniejsze – ponieważ funkcja redukująca generuje nowe hasło w dość zawiły sposób (w przypadku dużych słowników jest to zapytanie do bazy danych) to sprawdzenie całego łańcucha trwa znacznie dłużej, niż w zwykłej tęczowej tablicy,
  • by przyspieszyć redukcję część danych słowników jest cache’owana – przyspieszenie jest duże, podobnie jak zużycie pamięci ;-/

Cóż… Coś za coś 🙂

P.S. Ostatnio pobawiłem się chwilę Web Workerami – dzięki czemu wrzucenie dużej ilości danych spowoduje ich przetworzenie w osobnym wątku bez zamrożenia okna przeglądarki.

Narzędziem można pobawić się tutaj: Hybrid Rainbow DB

RainbowDB

Pewnego popołudnia przeczytałem artykuł o tęczowych tabelach i pod jego wpływem zacząłem kombinować jak zrobić coś takiego ale swojego.

Do bazy wrzuciłem cały słownik z aspell’a dla języka polskiego (słowa z ogonkami i bez), angielskiego, kilka słowników z popularnymi hasłami, długą listę haseł z yourock i kilka innych. Sporo się nakombinowałem aby wygenerować dużo kombinacji szczególnie pod kątem polskich haseł (wszystkie: misiaczki, dupeczki, itp…) razem z różnymi popularnymi modyfikacjami (typu: misiaczki1, DUPECZKI, etc…). Na tym etapie miałem już wystarczająco dużo haseł aby bawić się dalej.

Zacząłem kombinować z różnymi długościami łańcuchów – niestety funkcja redukująca zmniejszała nieco entropię kolejnych hashy w łańcuchu, co dla długich łańcuchów mocno zmniejszało wydajność przeszukiwania bazy. Ostatecznie postawiłem na bardzo krótkie łańcuchy (a nuż się coś tafi a przynajmniej nie będzie mocno opuźniać wyszukiwań).

Obecnie baza ma ponad 200 milionów haseł i dla nich wygenerowane łańcuchy o długości 10 ogniw. Co daje teoretycznie możliwość sprawdzenia ok 2 miliardów hashy. Wydaje się to sporo ale w stosunku do innych baz dostępnych w sieci jest to kropla w morzu. A co do innych baz… pomyślałem, że skoro ktoś już zrobił taką bazę dobrze to można by to wykorzystać. I tak dorzuciłem funkcję “obsysania” innych bazy hashy w przypadku gdy moja danego hasha nie potrafi rozpoznać. Taki zabieg (którego implementacja zajęła mi 1 popołudnie) wdrożony dla kilku różnych wyszukiwarek znacznie poprawił efektywność rozpoznawania haseł.

Bazę postanowiłem udostępnić w postaci strony www – jak na razie ze stosunkowo liberalnymi zasadami korzystania (czyli bez ograniczeń na liczbę wyszukiwań, konieczności rejestracji itp).

Z bazy można korzystać pod poniższym linkiem:

RainbowDB

Wyłączyłem tą stronkę po dobrych dwóch/trzech latach działania – ruch jest przekierowany na nowy projekt Hybrid Rainbow DB, w którym oprócz tęczowych tablic zaimplementowałem hybrydową tęczową tablicę – nowa aplikacja sprawdza o wiele więcej haseł.