MD5 prolomena, SHA-1,256,512,384,224 bezpečné, HMAC s MD napůl

Stránka věnovaná kolizím hašovacích funkcí ( v přípravě....)

Vlastimil Klíma

poslední aktualizace stránky 3.5. 2006

Vlastimil Klima: Tunnels in Hash Functions: MD5 Collisions Within a Minute (extended abstract), IACR ePrint archive Report 2006/105, 18. 3. 2006, lokální pdf: English ,Czech , zdrojový kód verze 0 (neoptimalizovaný), zdrojový kód verze 1 - nejrychlejší program a metoda hledání kolizí MD5 na světě

Dej mi tři soubory a já ti vrátím jiné tři se stejnou MD5 haší... Program pack3 napsal Ondrej Mikle. Je založen na kolizním programu MD5 collision program Vlastimila Klímy. Použití: pack3 file1 file2 file3 file4 file5 file6 vytvoří dva samorozbalovací archivy package1.exe a package2.exe. Oba budou mít sejnou MD5 haš, přičemž package1.exe extrahuje soubory 1-3 a package2.exe soubory 4-6. Více informací

Daniel Joščák: Hledání kolizí v hašovacích funkcích, diplomová práce, MFFUK, Praha, 21.4.2006. Abstrakt: Hlavním obsahem této práce je hledání kolizí v hašovací funkci MD5. Představíme náš nový algoritmus založený na metodě kolizí podle Wangové a kol. V průběhu psaní této práce Stevens a Klíma publikovali dva nové algoritmy. Uvádíme popis všech tří algoritmů a jejich výpočetní složitost.

Marc Stevens, "Fast Collision Attack on MD5", 17 March 2006, IACR ePrint archive Report 2006/104, pdf and source code .

První porovnání algoritmů Klímy a Stevense je zde.

Pavel Dufek: Modifikace programu Klímy verze 1, modifikovaný program umožňuje zvolit inicializační hodnotu (jako parametr programu), a vytváří nové textové a binární výstupy. Zdrojový a spustitelný kód jsou zde.

J. Black, M. Cochran, T. Highland: "A Study of the MD5 Attacks: Insights and Improvements", March 3, 2006, pdf, toolkit.

Jun Yajima and Takeshi Shimoyama: Wang’s sufficient conditions of MD5 are not sufficient, Cryptology ePrint Archive: Report 2005/263, 10 Aug 2005, http://eprint.iacr.org/2005/263.pdf .

Yu Sasaki and Yusuke Naito and Noboru Kunihiro and Kazuo Ohta: Improved Collision Attack on MD5, Cryptology ePrint Archive: Report 2005/400, 7 Nov 2005, http://eprint.iacr.org/2005/400.pdf .

Liang J. and Lai X.: Improved Collision Attack on Hash Function MD5, Cryptology ePrint Archive: Report 425/2005, 23 Nov 2005, http://eprint.iacr.org/2005/425.pdf .

8.5.2005

Prezentace mnohonásobných modifikací zprávy

Vlastimil Klima: Finding MD5 Collisions on a Notebook PC Using Multi-message Modifications, 3rd Int. Conference Security and Protection of Information 2005, Brno, Czech Republic, May 3 - 5, 2005, prezentace(ppt).

31.3.2005

Nalézání kolizí MD5 na notebooku pomocí mnohonásobných modifikací zprávy

Ve stejnojmenném článku jsem uveřejnil metodu nalézání kolizí z 5.3.2005 a návrh dalších metod. Vlastimil Klíma: Nalézání kolizí MD5 na notebooku pomocí mnohonásobných modifikací zprávy, 31.3. 2005, verze 1

Abstrakt: V tomto stručném příspěvku shrnujeme výsledky našeho tříměsíčního výzkumu kolizí hašovací funkce MD5. Inspirováni prací Wangové a kol. [1] jsme vyvinuli metody nalézání kolizí, které pracují pro libovolný inicializační vektor a jsou rychlejší než metody v [1, 8]. To umožňuje nalézt kolizi MD5 na standardním notebooku asi za 8 hodin [7]. Nezávisle na [1, 8] jsme objevili a navrhli několik metod mnohonásobné modifikace zpráv, které jsou efektivnější než v [1, 8], a ukazujeme jejich podstatu.

Anglická verze: Vlastimil Klima: Finding MD5 Collisions on a Notebook PC Using Multi-message Modifications, March 31, 2005, IACR ePrint archive, Report 2005/102.

19.3.2005

Hašovací funkce, principy, příklady a kolize

Vlastimil Klíma: Hašovací funkce, principy, příklady a kolize, přednáška na semináři Cryptofest, 19.3. 2005, on line zde.

Abstrakt: Tento velmi rozsáhlý příspěvek je určen těm, kdo nemají podrobné znalosti o hašovacích funkcích, ale přitom se jich nějakým způsobem týká jejich bezpečnost. Budeme se zabývat principy konstrukce, bezpečností a novinkami v oblasti hašovacích funkcí.

9. 3. 2005

Nalézání kolizí MD5 - původní čínská metoda zveřejněna

Konečně po šesti měsících mlčení byl uveřejněn příspěvek prof. Wangové a kol. o čínském triku.

Xiaoyun Wang and Hongbo Yu: How to Break MD5 and Other Hash Functions (PDF).

Podstatou jsou dvě hlavní myšlenky. První je diferenční schéma. Druhou je tzv. metoda modifikace zpráv. Tato metoda má mnoho variant a v diferenčním schématu se použije mnohokrát. Zveřejněny byly pouze příklady. U diferenčního schématu (kolidující zprávy se liší v šesti 32bitových slovech o definovaný aritmetický rozdíl) sice známe jeho popis, ale není jasné, jak právě toto schéma bylo vybráno. Diferenčních schémat tohoto typu může být celá řada. Jinými slovy, ani tato práce ještě neodhaluje všechno z čínského zákulisí. Faktem je, že do konferenčního příspěvku se nemůže vejít všechno, a že toto je výsledkem výzkumu prof. Wangové od roku 1996. Doufejme, že v dalších pracech odhalí více. Mnohé slibuje oznámený útok na SHA-1, který vychází ze stejné metody, a kde dosáhli složitosti 2^69 místo 2^80.

8. 3. 2005

Populární článek pro www.root.cz

Nalézání kolizí MD5 - hračka pro notebook zde.

5.3. 2005

V článku Nalézání kolizí MD5 - hračka pro notebook jsem oznámil schopnost generovat kolize pro MD5 na notebooku za cca 8 hodin:

Vlastimil Klima: Finding MD5 Collisions – a Toy For a Notebook, 5th March, 2005, IACR ePrint archive, Report 2005/075, homepage, pdf: English, Czech.

8. 12. 2004

Praktická demonstrace využití čínského útoku:

K demonstraci využití čínského útoku jsem vyzval na přednášce 15.11. 2004 uvedené níže. V diskusi byly předloženy asi čtyři nebo pět nápadů. Ondra svůj nápad během několika následujících dní převedl do fungující praktické ukázky do příspěvku konferenčního typu. Blahopřeji! Ondrej Mikle, student MFF UK, ukázal, že lze využít i jednu publikovanou kolizi MD5 ke konstrukci reálných útoků (2. 12. 2004). Výsledek? Velmi stručně ten nejzajímavější. Zvolte si jakékoliv dva různé soubory (třeba smlouvy). Pomocí postupu z článku docílíte toho, že jeden uživatel dostane první z nich, druhý uživatel druhý z nich, a přitom si oba dva na základě vzájemné telefonické kontroly digitálních otisků (MD5) budou myslet, že mají tentýž soubor. Něco tady není v pořádku, že? Podrobnosti jsou na domovské stránce projektu. Nezávisle na něm o 4 dny později publikoval jiný koncept využití jediné kolize MD5 i Dan Kaminsky (6.12. 2004).

22. 11. 2004

Seminář BIS

Vlastimil Klíma: Hašovací funkce, MD5 a čínský útok, Seminář Bezpečnost Informačních Systémů v praxi (http://bis.modry.cz/), MFF UK Praha, 22. 11. 2004, prezentace v powerpointu (prezentace v pdf), text bez bez Kelsey-Schneierova doplňku, viz pdf. Oproti konferenci DCD je zde minimum informací navíc, jen prezentace s obrázky.

12. 11. 2004

O čínském útoku a hašovacích funkcích podrobněji na DCD:

Protože o kolize hašovacích funkcí byl na www.root.cz velký zájem (10500 čtenářů), napsal jsem při příležitosti přednášení tohoto tématu na konferenci DCD text:

Nedůvěřujte kryptologům, IT &Security Conference, DCD Publishing, Hotel Diplomat, Praha, 10. - 11. 11. 2004, 25 stran (480 kByte pdf), který tu kauzu trochu víc vysvětluje a obnáší trochu víc informací. Dokument přetiskuje i Crypto-world jako speciál.

25. 8. 2004

Článek na www.root.cz, který tuhle stránku zapříčinil

Vlastimil Klíma: Hašovací funkce MD5 a další prolomeny!, zde

Literatura a linky

Další linky:

stránka Paula Barreta , jedna z mála aktualizovaných a hodnotných stránek o hašovacích funkcích

o hašovacích funcích a kolizích na wikipedii

ilustrovaný úvod do hašovacích funkcí

[ARCHIV] Archiv autora obsahující články o kryptologii a bezpečnosti, http://cryptography.hyperlink.cz/

[BC04a] Biham, Eli, Chen, Rafi: Near Collisions of SHA-0, CRYPTO 2004

http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/2004/CS/CS-2004-09.ps.gz

[BC04b] Eli Biham, Rafi Chen: New results on SHA-0 and SHA-1, CRYPTO 2004 Rump Session

[BoBo93] B. den Boer and A. Bosselaers. Collisions for the compression function of MD5. In Advances in Cryptology, Eurocrypt ‘93, pages 293-304, Springer-Verlag, 1994.

[D96a] H. Dobbertin, Cryptanalysis of MD4, Fast Software Encryption 1996, LNCS, Vol. 1039, Springer-Verlag, 1996, pp. 53 - 69

[DK2004] Dan Kaminsky: MD5 To Be Considered Harmful Someday, Cryptology ePrint Archive, Report 2004/357, http://eprint.iacr.org/2004/357, 6 December 2004

[DO96eu] H. Dobbertin. Cryptanalysis of MD5 Compress. Presented at the rump session of Eurocrypt ‘96, May 14, 1996.

[DO96cb] H. Dobbertin. The Status of MD5 after a Recent Attack. CryptoBytes, 2(2): 1-6, 1996.

[HAVAL] Y. Zheng, J. Pieprzyk, J. Seberry, HAVAL - A One-way Hashing Algorithm with Variable Length of Output, Auscrypt 92

[HMAC] FIPS PUB 198, The Keyed-Hash Message Authentication Code (HMAC), NIST, US Department of Commerce, Washington D. C., March 6, 2002, http://csrc.nist.gov/CryptoToolkit/tkhash.html, resp. RFC 2104, http://www.rfc-editor.org/

[HPR04] Philip Hawkes, Michael Paddon, Gregory G. Rose: Musings on the Wang et al. MD5 Collision, Cryptology ePrint Archive, Report 2004/264, 13 October 2004, http://eprint.iacr.org/2004/264.pdf

[Joux04a] Antoine Joux: Collisions in SHA-0, CRYPTO 2004 Rump Session

[Joux04b] A. Joux: Multicollisions in iterated hash functions. Application to cascaded

constructions. Proceedings of Crypto 2004, LNCS 3152, pages 306-316.

[KS2004] John Kelsey, Bruce Schneier: Second Preimages on n-bit Hash Functions for Much Less than 2^n Work, http://eprint.iacr.org/2004/304/, November 15, 2004

[LWW05a] Arjen Lenstra, Xiaoyun Wang and Benne de Weger: Colliding X.509 Certificates, Cryptology ePrint Archive, Report 2005/067, http://eprint.iacr.org/2005/067

[LWW05b] Arjen Lenstra, Xiaoyun Wang and Benne de Weger: Colliding X.509 Certificates based on SHA1-collisions, http://www.win.tue.nl/~bdeweger/CollidingCertificates/index.html

[MD245] MD2, MD4, MD5 - RFC 1319, 1320, 1321, http://www.rfc-editor.org/

[NIST05b] NIST Brief Comments on Recent Cryptanalytic Attacks on SHA-1

http://csrc.nist.gov/news-highlights/NIST-Brief-Comments-on-SHA1-attack.pdf

[NIST05a] NIST Brief Comments on Recent Cryptanalytic Attacks on Secure Hashing Functions and the Continued Security Provided by SHA-1, http://csrc.ncsl.nist.gov/hash_standards_comments.pdf,

[OOW94] P. van Oorschot and M. Wiener. Parallel collision search with application to hash functions and discrete logarithms. In Proceedings of 2nd ACM Conference on Computer

and Communication Security, pages 210-218, ACM Press, 1994.

[OM2004] Ondrej Mikle: Practical Attacks on Digital Signatures Using MD5 Message Digest, Cryptology ePrint Archive, Report 2004/356, http://eprint.iacr.org/2004/356, 2nd December 2004, http://cryptography.hyperlink.cz/2004/collisions.htm

[PKCS2] PKCS#5 v2.0: Password-Based Cryptography Standard, RSA Labs, March 25, 1999

[RIPEMD-160] H. Dobbertin, A. Bosselaers, B. Preneel, "RIPEMD-160: A Strengthened Version of RIPEMD," Fast Software Encryption, LNCS 1039, D.Gollmann, Ed., Springer-Verlag, 1996, pp. 71-82

[SHA-0] FIPS 180 (superseded by FIPS 180-1 and FIPS 180-2), Secure hash standard (SHS), NIST, US Department of Commerce, Washington D. C., May 1993

[SHA-1] FIPS 180-1 (superseded by FIPS 180-2), Secure hash standard (SHS), NIST, US Department of Commerce, Washington D. C., April 1995

[SHA-2] FIPS 180-2, Secure Hash Standard (SHS), NIST, US Department of Commerce, Washington D. C., August 2002 (change notice: February 2004), http://csrc.nist.gov/publications/fips/fips180-2/fips180-2withchangenotice.pdf, platný standard, obsahuje definice SHA-1, SHA-224, SHA-256, SHA-384 a SHA-512

[VK2005a] Vlastimil Klima: Finding MD5 Collisions – a Toy For a Notebook, Cryptology ePrint Archive, Report 2005/075, March 5, 2005, http://eprint.iacr.org/2005/075, v češtině " Nalézání kolizí MD5 - hračka pro notebook", http://cryptography.hyperlink.cz/md5/MD5_kolize.pdf.

[VK2005b] Vlastimil Klima: Finding MD5 Collisions on a Notebook PC Using Multi-message Modifications, March 31, 2005, Cryptology ePrint Archive, Report 2005/112, http://eprint.iacr.org/2005/102, v češtině " Nalézání kolizí MD5 na notebooku pomocí mnohonásobných modifikací zprávy", http://cryptography.hyperlink.cz/md5/Vlastimil_Klima_MD5_kolize.pdf .

[VK2005c] Vlastimil Klíma: Hašovací funkce, principy, příklady a kolize, přednáška na semináři Cryptofest, http://www.cryptofest.cz/, Praha, 19.3. 2005, on line na http://cryptography.hyperlink.cz/2005/cryptofest_2005.htm.

[WFLY04] X. Wang, D. Feng, X. Lai, H. Yu, "Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD", rump session, CRYPTO 2004, Cryptology ePrint Archive, Report 2004/199, http://eprint.iacr.org/2004/199

[WY2005] Xiaoyun Wang and Hongbo Yu: How to Break MD5 and Other Hash Functions, http://www.infosec.sdu.edu.cn/paper/md5-attack.pdf.

[WYY05] Wang X., Yin L., Yu H.: Collision Search Attacks on SHA1, February 13, 2005, http://theory.lcs.mit.edu/~yiqun/shanote.pdf

Další elektronicky dostupné dokumenty a populární články v češtině :

Přednášky na MFF UK (zejména první a třetí):
V. Klíma: Základy moderní kryptologie - Symetrická kryptografie III. (operační mody blokových šifer a hašovací funkce), MFF UK, prosloveno v rámci přednášek oboru "Matematické metody informační bezpečnosti", http://adela.karlin.mff.cuni.cz/~tuma/nciphers.html.

V. Klíma: Základy moderní kryptologie - Symetrická kryptografie II. (symetrická kryptografie, proudové a blokové šifry, DES, EAS), MFF UK, prosloveno v rámci přednášek oboru "Matematické metody informační bezpečnosti", http://adela.karlin.mff.cuni.cz/~tuma/nciphers.html.

V. Klíma: Základy moderní kryptologie - Symetrická kryptografie I. (nové myšlenky kryptografie, bezpečnostní cíle, kryptoanalýza, typy kryptografických systémů, kryptologie), MFF UK, prosloveno v rámci přednášek oboru "Matematické metody informační bezpečnosti", http://adela.karlin.mff.cuni.cz/~tuma/nciphers.html.

Hašovací kód HMAC:
V. Klíma, T. Rosa: Kryptologie pro praxi (8) – funkce HMAC, Sdělovací technika, 2/2004, str. 17, http://cryptography.hyperlink.cz/2004/st_2004_02_17_17.pdf.

Úvod k hašovacím funkcím a popis perspektivní SHA-1 (to bylo....):
V.Klíma: Počítačová bezpečnost (Hašovací funkce a kódy): Výživná haše, Chip, březen 1999, str. 40 - 43, http://cryptography.hyperlink.cz/1999/chip-1999-03-40-43.pdf.

Hašovací funkce MD, RIPEMD a HMAC, kompresní funkce a kolize hašovacích funkcí:
V.Klíma: Počítačová bezpečnost (Hašovací funkce a kódy): Jak se melou data, Chip, duben 1999, str. 44 - 46, http://cryptography.hyperlink.cz/1999/chip-1999-04-44-46.pdf.

Nové hašovací funkce SHA-256, SHA-384 a SHA-512:
V.Klíma: Jednoznačné otisky dat, Chip, srpen 2001, str. 138 - 139, http://cryptography.hyperlink.cz/2001/chip-2001-08-138-139.pdf.

Ilustrovaný úvod do hašovacích funkcí, velmi pěkné - http://www.unixwiz.net/techtips/iguide-crypto-hashes.html

Linky od kolegy Rosy:

O hledání kolizí MD5 hrubou silou (aneb proč se mj. už MD5 neměla řadu let používat):

T. Rosa: Podpis k narozeninám, Chip, srpen 2001, str. 131 – 133.

Projekt MD5CRK:

Domovská stránka: http://www.md5crk.com/

Cílem bylo najít kolizi MD5 hrubou silou a přesvědčit tak architekty, aby od ní konečně ustoupili. Po uveřejnění příspěvku Wangové byl projekt zastaven.

Související obecné články o podpisových schématech:

T. Rosa: Podpis pro pokročilé (2), Chip, prosinec 2000, str. 172 – 176.

T. Rosa: Podpis pro pokročilé (1), Chip, listopad 2000, str. 174-178.

T. Rosa: Vybrané problémy podpisových schémat, Chip, leden 2001, str. 134 – 137.