Tablice tęczowe jako skuteczna optymalizacja algorytmu brute-force

Abstract

Publikacja jest próbą analizy bezpieczeństwa funkcji skrótów takich jak MD5 czy SHA-1. Omówione zostały podstawowe właściwości i wymagania stawiane przed takimi funkcjami. Artykuł przechodzi kolejno przez poszczególne metody łamania skrótów, zaczynając od prymitywnych metod typu brute-force, poprzez tablice Hellmana oraz ich optymalizację, opartą na punktach wyróżnionych Rivesta, a skończywszy na tablicach tęczowych. Pokazana została ewolucja metod kryptoanalitycznych, które korzystają z ogromnej mocy obliczeniowej komputerów, nie wykorzystując przy tym słabości konkretnych funkcji skrótu. W artykule poruszone zostały praktyczne zagadnienia implementacyjne oraz wskazano na pewne ograniczenia wyżej wymienionych metod kryptoanalizy. Zaprezentowano również rzeczywiste pomiary skuteczności omówionych wyżej metod. Publikacja opisuje również kolizje jako zjawisko niepożądane i w znacznym stopniu utrudniające kryptoanalizę. W publikacji rozdzielone zostały systemy i algorytmy odporne na opisane ataki, takie jak podpis cyfrowy oraz części systemu podatne na atak z wykorzystaniem tablic tęczowych, takie jak krótkie hasła, które w chwili obecnej są jeszcze wykorzystywane. Na koniec podano praktyczną metodę zabezpieczania się przed możliwymi atakami, tzw. &quot,solenie&quot, haseł. Metody tej nie da się niestety dynamicznie włączyć w istniejących systemach. Wymaga ona konkretnej implementacji przez producenta oprogramowania.

This article is the analysis of the message digest functions' security, such as MD5 or SHA-I. Ali basie, common properties and requirements for message digest functions are described in this article. This publication presents the whole path of cryptanalytic method's evolution, beginning from simple methods like brute-force, going through the Hellman's tables and optimization based on distinguished points, described by Rivest and finishing on the rainbow tables. It is shown the evolution path of methods which uses huge computer's power, not some bugs or vulnerabilities in specific functions. This article contains some practice advices, describes potential implementation problems and shows some disadvantages of described cryptanalytic methods. Some, simple real examples are presented and the results of real measurements are contained in this article. One of the parts describes collisions in message digest functions and shows how hard can be cryptanalytic process with many collisions. Author distinguished safe parts of the system or algorithm (like digital signature) and rulnerable parts (like passwords) which are still used. The practical and very safe method (salt passwords) was described at the end of the article. Salt passwords require specific implementation by software developers. Unfortunately, this method cannot be enabled in easy way in existing system.