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

15 thoughts on “Hybrid Rainbow DB”

  1. Ja mam około 150 GB różnych słowników. Jakieś 20% ściągnięte resztę sam zrobiłem, takie słowniki na “polskie warunki”. Podstawa to słownik języka polskiego, imiona, nazwiska. Później można dalej kombinować, daty w różnych formatach, owoce, samochody, tytuły filmów, czy nawet zbiór adresów. Kiedys tak dla celów edukacyjnych potraktowałem md5 (ściągnięte z jakiejś stronki), które ktoś wcześniej “wydobył” różnymi wariantami ataku słownikowego.
    Oczywiście tych haseł w żaden sposób nie wykorzystałem chodziło raczej o sprawdzenie ogólnego bezpieczeństwa oraz jakich haseł nie należy stosować. Co z tego, że będziemy mieli SHA2-512 kiedy hasło mamy np. 123456789, qwerty123456789, adam1955 lub inne podobnie “długie i trudne” hasła.
    Takie zbiory md5 traktuję jako wyzwanie dla intelektu i uważam siebie za tzw. white hat, i daleki jestem od jakichkolwiek złośliwości. korzystam z baz już udostępnionych, czasami uświadamiam też swoich znajomych jak łatwo jest złamać pozornie trudne i długie hasło. “Pokazówka” z łamaniem na GPU działa dobrze na wyobraźnie.
    Szkoda, że nie znam się na programowaniu tak dobrze, bo taka hybrydowa tablica bez niepotrzebnych śmieci by się przydała.

    P.S. “najtrudniesze” hasło na jakie trafiłem to było: osiemdziewięćdziewięć88. w sumie 23 znaki, 3 cyfry słownie i 2 “normalnie”. jednak złamane zostało w 5 minut.

    Pozdrawiam. niestety maila nie posiadam może w tych czasach jest to dziwne, ale nie chce mi się zakładać.

    pozdrawiam

    1. Moja hybryda właśnie na pokazówkach bardzo fajnie się sprawdza (np. na szkoleniu z bezpieczeństwa IT) – gdy pokaże się ludziom poziom bezpieczeństwa ich haseł to szczeny im opadają. A jak się dodatkowo dowiedzą że serwer na którym ta aplikacja działa jest wydajnościowo porównywalny z przeciętnym smartphonem to ciężko im przez chwilę otwarte paszcze zamknąć 😉
      Pożytek z tego taki że przynajmniej zmienią hasła po szkoleniu, na co normalnie nie idzie ich namówić 😉

  2. Jeszcze można sobie uświadomić co może zrobić ktoś z większą ilością środków i know-how. Klaster kompów z kartami nVidii i jakieś “wypasione” hybrydowe tablice i aż strach pomyśleć. Ja już od dawna staram się zmieniać hasła na niesłownikowe i ponad 20 znakowe małe, duże litery cyfry i znaki specjalne (chyba obecnie takie hasła są bezpieczne).

    1. Wcale nie trzeba dużo kasy by uruchomić chmurkę w amazonie – nawet są już takie komercyjne usługi – za 20~30$ można złamać np. WPA2. Na forach bez problemu można znaleźć osoby dysponujące tęczowymi tablicami dla pełnego zakresu znaków i haseł o długości do 15~20 znaków – są w stanie złamać ponad 95% haseł. Ten komiks dobrze podsumowuje jak to wygląda: http://xkcd.com/936/

    1. Ja napisałem własny. Robi to na słownikach w bazie danych i generuje od razu hybrydową tablice hashy – tak by nie przechowywać samego słownika złączeń (cholerstwo może mieć nawet kilkadziesiąt gigabajtów jak przekombinujemy).

      Jeśli chodzi Ci o gotowy program, który generuje wszystkie możliwe kombinacje słów z dwóch (lub więcej) plików to takiego nie mam. Pewnie mój skrypcik dałoby się stosunkowo szybko przerobić na coś takiego… ale nie w ten weekend 😉

    2. Po chwili zastanowienia wydało mi się to banalne, więc na szybko skrobnąłem skrypcik w Pythonie, który wygeneruje co chcesz. Odpala się go tak:
      ./skrypcik.py wynikowy.txt slownik1.txt slownik2.txt
      Można też z większą liczbą słowników:
      ./skrypcik.py wynikowy.txt slownik1.txt slownik2.txt slownik3.txt

      Skrypcik pisany na kolanie, co daje praktycznie zero kontroli błędów. Nie jestem też pewien jak się będzie zachowywać na łamaniach wierszy w stylu Windowsowym.

      #!/usr/bin/python
      # -*- coding: utf-8 -*-
      
      from operator import mul
      import sys
      
      def load_dict(file_name):
          fh = open(file_name);
      
          dict = []
          for line in fh.readlines():
              y = [value for value in line.split()]
              dict.extend(y)
      
          fh.close()
          return tuple(frozenset(dict))
      
      def carthezian_set(index, lists):
          lists_len = [len(ll) for ll in lists]
          string = ""
      
          for i in xrange(0,len(lists)):
              r = index % lists_len[i]
              index = index / lists_len[i]
              string = string + lists[i][r]
      
          return string
      
      if __name__ == "__main__":   
          if len(sys.argv) < 3:
              print "Za malo parametrow!\nWywolaj %s wynik.txt slownik1.txt slownik2.txt [kolejne slowniki]" % (sys.argv[0],)
              exit(1)
          
          dict_files = sys.argv[2:]
          dicts = []
          result_file = sys.argv[1]
          
          for d in dict_files:
              print "ladowanie slownika: %s" % (d,)
              dicts.append(load_dict(d))
          
          max = reduce(mul, [len(ll) for ll in dicts])
          print "przewidywana liczba slow w slowniku zlaczen: %d" % (max,)
          
          print "generowanie slownika zlaczen %s..." % (result_file,)
          f = open(result_file, "w")
          
          for index in xrange(0, max):
              f.write(carthezian_set(index, dicts) + "\n")
      
          f.close()
          
          exit(0)
      

      Skrypcik wygenerował pliczek o rozmiarze ponad 2GB przy złączaniu dwóch ok 200kb słowników 😉

  3. Czy wiadomo Panu coś o najnowszym systemie hashowania sha3 (wydaje mi się że są 4 wersje 224, 256, 384, 512). Czy są gdzieś dostępne generatory tęczowych tablic? coś w rodzaju winrtgen na windowsa.

    1. Bardziej opłaca się bezpośrednio na PC zainstalować 4 karty graficzne z dwoma procesorami (np. AMD HD7990) pod OpenCL. Można je wtedy wykorzystać do brute force’a i tak robią to najlepsi crackerzy. Czysty bruteforce dla haseł do ok 8 znaków, potem stosuje się słowniki i hasła generowane jako iloczyny kartezjańskie z wielu słowników co pozwala łamać bardzo długie hasła.
      Lepsze do tego są karty AMD bo mają szerszą magistralę pamięci + więcej mniej skomplikowanych jednostek compute, i jakąś instrukcję wykonują w jednym cyklu zamiast w dwóch (w stosunku do NVidii) – trochę już zapomniałem, dawno się w to bawiłem 🙂

Leave a Reply

Your email address will not be published. Required fields are marked *