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 dobrą 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 external link

Nie można - projekt zarchiwizowałem.