Łamanie funkcji skrótu - rodzaje ataków

Każdy algorytm szyfrujący musi zostać w sposób wyczerpujący przetestowany na okoliczność jego ewentualnego złamania, zanim uczynią to cyberprzestępcy. Dopóki nie istnieje możliwość odtworzenia przekazu jawnego bądź klucza na podstawie tekstu zaszyfrowanego albo odtworzenia klucza na podstawie przekazu jawnego i zaszyfrowanego, dopóty algorytm jest bezpieczny i może być wykorzystywany.

Wyróżnia się dwie klasy ataków na funkcję skrótu, będącą gwarancją integralności danych i stanowiącą ważny element bezpieczeństwa systemu informatycznego (o funkcjach skrótu szerzej piszemy tutaj). Pierwsza związana jest z istniejącą słabością wewnętrzną danej funkcji skrótu (atak różnicowy), druga zaś nie analizuje funkcji pod kątem ewentualnie występujących słabości wewnętrznych algorytmu, wykorzystując inne dostępne sposoby. Przykładami tego typu działań są ataki: brutalny, urodzinowy oraz wieloblokowy.

Atak brutalny

Atak brutalny (brute force) polega na łamaniu skrótu z wykorzystaniem wszystkich możliwych kombinacji liczbowych, z których może się on składać. Metoda brute force charakteryzuje się dużą złożonością obliczeniową i jest w związku z tym czasochłonna. Wymaga zatem zaangażowania odpowiednio wysokich mocy obliczeniowych wykorzystywanych urządzeń. Teoretycznie może służyć odgadnięciu każdego klucza. W praktyce może być ona skuteczna jedynie przy stosunkowo krótkich kluczach. Dla odpowiednio długich kluczy proces obliczeniowy i weryfikujący otrzymane wyniki jest tak skomplikowany, że złamanie hasza kryptograficznego staje się praktycznie niemożliwe. Atak tego rodzaju w przypadku funkcji skrótu polega na przeszukiwaniu losowego zbioru kombinacji cyfr, liter oraz innych znaków i porównywaniu z określoną wartością danego skrótu. Istotą takiego ataku jest znalezienie dowolnej wiadomości, która po zastosowaniu funkcji skrótu wykaże zadany skrót.

Atak urodzinowy

Atak urodzinowy jest rodzajem ataku siłowego. Oparty jest na możliwości znalezienie dowolnej pary wiadomości, dla których skróty utworzone od tych wiadomości będą ze sobą tożsame. Innymi słowy chodzi w tym przypadku o znalezienie kolizji funkcji haszującej. Jego nazwa związana jest z leżącym u podstaw tego ataku tzw. paradoksem dnia urodzin. Paradoks ten daje odpowiedź na pytanie dotyczące liczby osób, która musi znaleźć się w losowej próbce, aby prawdopodobieństwo znalezienia tam dwójki ludzi urodzonych tego samego dnia wynosiło więcej niż ½. Odpowiedź (23 osoby) pozwala domniemywać, że kolizja dla funkcji haszującej może zostać znaleziona dużo szybciej niż wskazuje na to rozmiar zbioru wartości funkcji. Atak ten polega na wygenerowaniu odpowiedniej liczby skrótów, która zawsze będzie dużo mniejsza niż pełny zbiór wszystkich skrótów, aby z 50% prawdopodobieństwem trafić na dwa takie same skróty. 64-bitowe wartości funkcji skrótu, są niewystarczające dla odparcia ataku urodzinowego. Zaleca się stosowanie funkcji dających wyniki powyżej 128 bitów, gdyż dla algorytmu MD 5 (128 bitów) udany atak może nastąpić już przy wygenerowaniu 1,1774 * 264 skrótów, przy całkowitej liczbie 2128 możliwych kombinacji.

Atak wieloblokowy (strukturalny)

W ataku tego rodzaju wykorzystuje się zarówno tzw. pseudokolizje, jak i tzw. prawiekolizje. Ideą ataku jest możliwość uzyskania dwóch różnych wiadomości, dających ten sam skrót, ale dla dwóch różnych wartościach inicjujących. Atak ten może być skuteczny przeciwko algorytmom z rodziny MD.

Atak różnicowy

Jest to bardziej efektywna metoda niż w przypadku ataku brutalnego. W kryptoanalizie różnicowej dokonuje się analizy porównawczej pary kryptogramów, które wygenerowane zostały w efekcie zaszyfrowania wielu par wiadomości jawnych o ustalonych różnicach. Metoda różnicowa wykorzystuje prawdopodobieństwo zniwelowania różnicy wewnątrz funkcji kompresującej już po kilku rundach, poprzez zmianę paru bitów w analizowanym przekazie. Idea tego ataku polega na wykorzystaniu niedoskonałości zastosowanej w algorytmie funkcji kompresującej i wskazaniu dwóch różnych wiadomości dających ten sam skrót. Różnica określana jest funkcją logiczną xor.

Pavel Kroupka