Kolize hashovacích funkcí (25. díl)
v minulých dílech seriálu jsme si představily hashovací funkce a to, jak fungují. Dnes se krátce zaměříme i na to, jaké v sobě skrývají úskalí.
Z podstaty hash funkcí vyplývá, že zde existuje zákonitě možnost kolizí, to znamená dvojic vstupních dat (x,y) takových, že h(x)=h(y).
Kolize jsou nežádoucí, ale v principu se jim nelze úplně vyhnout. Lze jen snižovat pravděpodobnost, že nastane kolize pro podobná data, například při náhodné změně v části vstupní posloupnosti. Cílem je vysoká pravděpodobnost, že dvě zprávy se stejným kontrolním součtem jsou stejné.
Série nalezených kolizí v hash funkcích MD5, SHA-0 a RIPEMD po roce 2004 nám dává otázku, na kolik jsou tyto algoritmy bezpečné pro budoucnost. Není jen otázkou času, než se podaří nalézt kolize i v ostatních hash funkcích. A nakolik lze důvěřovat doposud neprolomeným algoritmům do budoucnosti? Prozatím jsou SHA-256, SHA-384 nebo SHA-512 považovány za dostatečně bezpečné" (zdroj: Klíma, Vlastimil: Prolomení MD5, současné problémy hašovacích funkcí a doporučení k obraně, Security Upgrade 2006, 12. – 13. 4. 2006, TOP Hotel, Praha)
"V množině M zpráv je M(M-1)/2 dvojic. Pravděpodobnost, že dvojice má stejný otisk je tedy 1/2n, pro M = 2n/2 máme M(M-1)/2 = cca 2n/2 dvojic. Odtud tvrzení.
U MD5 to říká to, že i přesto, že existuje 2^128 různých otisků, tak nám stačí otestovat hrubou silou jen 2^64 vstupních zpráv, abychom našli s 50% šancí kolidující pár zpráv. Je to tedy 2^(n/2), kde n je počet různých prvků. Vstupem hash funkce může být jakkoliv velký "balík" dat od 0 do 2^64 bytu, z čehož jednoznačně vyplývá, že vstupních balíků dat se stejným otiskem je opravdu mnoho, ale najít jen 2 zprávy se stejným otiskem zabere minimálně 2^64operací – viz další díl seriálu, kde si představíme takzvaný narozeninový paradox."(upraveno dle: KLÍMA, Vlastimil: Prolomení MD5, současné problémy hašovacích funkcí a doporučení k obraně. Podklady, konference Security Upgrade 2006, 12. – 13. 4. 2006.
Díky kryptoanalytickým útokům čínských matematiků na MD5 v 2004 a 2005 se podařilo snížit potřebný počet operaci na úroveň, kdy lze nalézt kolizní pár dvou zpráv (nesmyslných) u MD5 během několika hodin i na běžném počítači. Také pokusy doktora Klímy vedou k nalezení kolizí na běžném počítači během několika minut – více například KLÍMA, Vlastimil: Prolomení MD5, současné problémy hašovacích funkcí a doporučení k obraně. Podklady, konference Security Upgrade 2006, 12. – 13. 4. 2006.
Díly seriálu:
Elektronický doklad v účetnictví – Podpis (1. díl)
Elektronický doklad v účetnictví – Vlastnoruční podpis (2. díl)
Elektronický doklad v účetnictví – Elektronický podpis (3. díl)
Požadavky kladené na elektronický podpis (4. díl)
Druhy elektronických podpisů (5. díl)
Náležitosti účetního dokladu (7. díl)
Co vše skrývá dokument v elektronické podobě (8. díl)
Elektronický podpis a informace v něm obsažené (9. díl)
Elektronická komunikace organizace (10. díl)
Možnosti elektronické komunikace organizace (11. díl)
Efektivní elektronická komunikace – to je EDI (12. díl)
Šifrování – kryptografické základy digitálního podpisu (14. díl)
Význam šifrování a jeho typy (15. díl)
Symetrické šifrovací algoritmy (16. díl)
Šifrování – k čemu slouží a jak ho využít (17. díl)
Ověření identity a elektronický podpis (18. díl)
Asymetrické šifrování a jeho praktické využití (19. díl)
Hybridní šifrovací algoritmy (20. díl)
Hashovací funkce a jejich využití ve spojení s elektronickým podpisem (21. díl)
Vlastnosti hashovacích funkcí (22. díl)
Použitelnost hashovacích funkcí v praxi (23. díl)
Praktický příklad použití otisku dokumentu (24. díl)
Kolize hashovacích funkcí (25. díl)
Zdroje:
[1] Klíma, Vlastimil: Prolomení MD5, současné problémy hašovacích funkcí a doporučení k obraně, Security Upgrade 2006, 12. – 13. 4. 2006, TOP Hotel, Praha.
[2] MENEZES, Alfred J. -OORSCHT, Paul C. – SCOTT, Vanstone: Handbook of Applied Cryptography. USA, CRC Press, 2001 ISBN 0-8493-8523-7.
[3] SCHNEIER, Bruce: Applied Cryptograph: Protocols, Algorthms, and Source Code in C. USA, Wiley Computer Publishing, John Wiley & Sons, 1996. ISBN 0471128457.
[4] SMART, Nigel: Cryptography: An Introduction, N. Smart. USA, McGraw-Hill, 2004. ISBN 0-07-709987-7
[5] www.root.cz/clanky/hasovaci-funkce-md5-a-dalsi-prolomeny/
Odpovědět na příspěvek