03.08.2015 | 22:04

Adam Haertle

Kolizja MD5 dwóch kluczy publicznych ssh-rsa

W sieci nie brakuje przykładów kolizji MD5 np. dwóch plików binarnych. Te można sobie wygenerować używając tanich chmur obliczeniowych, jednak najwyraźniej ciągle niewystarczająco przemawia to do wyobraźni programistów używających MD5 jako mechanizmu weryfikacji uwierzytelnienia lub integralności danych. Co zatem powiecie na dwa klucze ssh-rsa które, choć różne, mają identyczny skrót MD5?

ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAABAQD74ICRUoaAXkRwqGW51botLrFygSC1SN3C7NR6cfFmpSdRuXZt6d20+GvAzOQKJpPTItK3YRjds1izapAqSM6o/BYWOikTKLHgzJ2s5Lwm6MZnPsnRJ9o9KbnXCytCrj3wFCcay0Re+TJrlPvXggFZlane2yMit2rWx/Fbly44wNzsJLIGTIhsz6UnfmR7Wi7GfiMZ2p48xn3rSHJ3lNPTOzWfg3PFgc2YftzUow1TQ5xaamyPRD/UOXBOj2pfCp75v3TWDwwq3qliBV6pxUhe/ou8ut1zaRET5VTN4kFNziQZoxY4WVmCnCJxjBPt71hM9VzoujZggRNXct8uPdri hostname

ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAABAQD74ICRUoaAXkRwqGW51botLrFygSC1SN3C7NR6cfFmpSdRuXZt6d20+GvAzOQKJpPTItK3YRjds1izapCqSM6o/BYWOikTKLHgzJ2s5Lwm6MZnPsnRJ1o+KbnXCytCrj3wFCcaS0Re+TJrlPvXggFZlane2yMit2rWx/FbFy44wNzsJLIGTIhsz6UnfmR7Wi7GfiMZ2p68xX3rSHJ3lNPTOzWfg/PFgc2YftzUow1TQ5xaamyPRD/UOXBOj2pfCp75v3TWDwwq3qliBV6pxUhe/ou8ut1zaRET5VTN4kFNziQZoxY4WVmCnCJxjBPt71hM9VzoujZggRNXct8uPdri hostname

Na pierwszy rzut oka identyczne, jednak różnią się kilkoma znakami i przepuszczone przez funkcję skrótu MD5 dają identyczny wynik. Autorem tej sztuczki jest Nathaniel McHugh.

Jeśli ufacie wbudowanym funkcjom ssh-keygen, to by samodzielnie sprawdzić prawdziwość powyższych twierdzeń wystarczy zapisać oba klucze do plików i uruchomić polecenie

ssh-keygen -l -E md5 -f nazwapliku

Jeśli wolicie zrobić to krok po kroku, to najpierw trzeba usunąć początek i koniec klucza (ssh-rsa oraz hostname), następnie zdekodować postać base64 i policzyć md5 z wyniku.

cut -d ' ' -f 2 < nazwapliku | base64 -d | md5sum

Teraz czekamy jeszcze na kolizję MD5 na krótkich (idealnie poniżej 32 znaków) ciągów ASCII o wartościach z przedziału 32-126 i pędzimy testować mechanizmy przechowywania haseł serwisów internetowych.

Powrót

Komentarze

  • 2015.08.04 00:30 kamil

    „Teraz czekamy jeszcze na kolizję MD5 na krótkich (idealnie poniżej 32 znaków) ciągów ASCII o wartościach z przedziału 32-126 i pędzimy testować mechanizmy przechowywania haseł serwisów internetowych.”
    To że są 2 hasła co mają taki sam hash to jakieś zagrożenie dla bezpieczeństwa? (Pomijając już samo trzymanie haseł w md5) Bo nie przychodzi mi do głowy jak można by to wykorzystać (ale zbytnio się nie znam).

    Odpowiedz
    • 2015.08.04 09:27 Piotr

      Kamil

      Po stronie serwera powinno sie trzymac hash hasla. Jesli hash jest w md5 i istnieje taka kolizja, o ktorej pisze Adam, to znajac „swoje” haslo bedziesz w stanie zalogowac sie na „czyjes” konto, poniewaz hash obu hasel bedzie identyczny.

      Odpowiedz
      • 2015.08.04 10:56 darek

        Mam wrażenie, że w komentarzach robi się małe zamieszanie. Jeśli dobrze rozumiem, opisany atak polegał na manipulowaniu OBOMA kluczami, tak aby uzyskać ten sam hash. W przypadku haseł hash w bazie jest niezmienny więc opisywany atak nie ma tutaj zastosowania. Problem pojawi się gdy ktoś wymyśli, jak dla danego skrótu MD5 dobrać string wejściowy, wtedy MD5 definitywnie przejdzie do lamusa – nie będzie potrzeby łamania MD5’tek wystarczy wyliczyć sobie string, dla którego MD5 wynosi tyle ile wartość przechowywana w bazie.

        Odpowiedz
      • 2015.08.04 11:08 kamil

        Ale żeby wiedzieć, że hashe są identyczne, musiałbym znać hasło, nie?

        Odpowiedz
        • 2015.08.04 11:22 Adam

          Zakładasz konto z hasłem 1, logujesz się hasłem 2 o identycznym hashu MD5. Jeśli działa to znaczy że przechowują hasła w MD5.

          Odpowiedz
          • 2015.08.04 18:30 kamil

            Teraz rozumiem, dziękuję.

          • 2015.08.31 12:37 dzikus

            Bez soli! Jeśli solą hasła to hasło 2 nie zadziała nawet jeśli hashują md5.

  • 2015.08.04 09:36 Filip

    Hasło jest przechowywane jako hash. W momencie próby logowania z wpisanego hasła jest robiony hash i porównywany z przechowywanym. Kolizja hasha pozwalałaby zalogować się innym hasłem.

    Odpowiedz
  • 2015.08.04 11:40 Ja

    A wystarczy posolić, żeby nie było tak prosto…

    Odpowiedz
  • 2015.08.04 12:30 Marcin

    Tak. Faktycznie problem. To tak jakbym znalazł na ulicy klucz identyczny jako do mojego mieszkania i zastanawiał się kto w Polsce ma taki sam zamek. Trochę możliwości jest….

    Odpowiedz
    • 2015.08.04 12:56 Adam

      Jeśli np. poznasz tylko hash MD5 to możesz znaleźć kolizję i się zalogować. Twój argument jest inwalidą.

      Odpowiedz
      • 2015.11.19 08:41 Marcin

        Adamie, czytam Twoje artykuły od dłuższego czasu i uważam że są świetne, ale ostatnio zrobiłeś się zgryźliwy.
        „Twój argument jest inwalidą?” To jakiś specyficzny żart? Bo to brzmi jak chamskie tłumaczenie google translatorem 'your argument is invalid’

        Odpowiedz
        • 2015.11.19 09:09 Adam

          To faktycznie był żart. Jak na to wpadłeś? :)

          Odpowiedz
          • 2015.11.19 09:48 Marcin

            Specyficzne poczucie humoru, rozbieżne z moim, ale OK :)
            Ale reasumując, pozdrawiam i powodzenia, Z3S to kawał dobrej roboty.

          • 2015.11.19 10:04 Adam

            Bywa. Dzięki!

Zostaw odpowiedź do Marcin

Jeśli chcesz zwrócić uwagę na literówkę lub inny błąd techniczny, zapraszamy do formularza kontaktowego. Reagujemy równie szybko.

Kolizja MD5 dwóch kluczy publicznych ssh-rsa

Komentarze