Kolizja MD5 dwóch kluczy publicznych ssh-rsa

dodał 3 sierpnia 2015 o 22:04 w kategorii Drobiazgi  z tagami:

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.