Tablice tęczowe jako skuteczna optymalizacja algorytmu brute-force

• Autorzy: Kołodziejczyk M.

Warianty tytułu

EN

Rainbow tables as brute-force algorithm optimization

• Języki publikacji: PL

Abstrakty

PL

Publikacja jest próbą analizy bezpieczeństwa funkcji skrótów takich jak MD5 czy SHA-1. Omówione zostały podsta-wowe 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. "solenie" haseł. Metody tej nie da się niestety dynamicznie włączyć w istniejących systemach. Wymaga ona konkretnej implementacji przez producenta oprogramowania.

EN

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.

Słowa kluczowe

PL

tablica tęczowa; funkcja skrótu; funkcja redukcji; kolizje; solenie haseł; metoda Hellmana; punkty wyróżnione Rivesta; podpis cyfrowy; łamanie haseł; fałszywe alarmy

EN

rainbow table; Message Digest Function; hash function; brute-force algorithm; reduction function; collision; salt passwords; time-memory tradeoff; digital signature; distinguished points; password cracking; false alarms

• Wydawca: Wydawnictwa AGH
• Czasopismo: Elektrotechnika i Elektronika
• Rocznik: 2009
• Tom: T. 28, z. 1--2
• Strony: 7--13
• Opis fizyczny: Bibliogr. 6 poz., tab., rys.

Twórcy

autor

Kołodziejczyk M.

• Wydział Elektrotechniki, Automatyki, Informatyki i Elektroniki, Akademia Górniczo-Hutnicza w Krakowie

Bibliografia

• [1] Yilmaz B.: Time-Memory Trade-of fusing distinguished points. 2007.
• [2] Oechslin R: Making a Faster Cryptanalytic Time-Memory Trade-Off. 2003.
• [3] Maziarz R: Wykorzystywanie tęczowych tablic do łamania haseł, ha-kin9.pl, 2008.
• [4] Hellman M.: A cryptanalytic time-memory trade off. 1980.
• [5] Ogiela M.R.; Bezpieczeństwo systemów komputerowych. Wydawnictwa AGH, Kraków, 2002.
• [6] Denning D.E.: Cryptography and Data Security. Addison-Wesley, 1982.