Shrnutí zabezpečení funkce hash - Hash function security summary

Tento článek shrnuje veřejně známé útoky proti kryptografické hashovací funkce. Upozorňujeme, že ne všechny položky mohou být aktuální. Souhrn dalších parametrů hash funkce viz srovnání kryptografických hashovacích funkcí.

Barevný klíč tabulky

  Žádný útok nebyl úspěšně prokázán - útok rozbije pouze sníženou verzi hash nebo vyžaduje více práce, než je deklarovaná úroveň zabezpečení hash
  Teoreticky prokázaný útok - útok prolomí všechna kola a má nižší složitost než bezpečnostní tvrzení
  Útok prokázán v praxi

Běžné hashovací funkce

Odolnost proti kolizi

Hlavní článek: Kolizní útok
Funkce hashBezpečnostní požadavekNejlepší útokDatum zveřejněníKomentář
MD5264218 čas2013-03-25Tento útok na běžném počítači trvá několik sekund. Kolize dvou bloků za 218, kolize jednoho bloku za 241.[1]
SHA-1280261.22020-01-08Papír Gaëtana Leurenta a Thomase Peyrina[2]
SHA256212831 ze 64 kol (265.5)2013-05-28Kolize dvou bloků.[3]
SHA512225624 z 80 kol (232.5)2008-11-25Papír.[4]
SHA-3Až 25126 z 24 kol (250)2017Papír.[5]
BLAKE2s21282,5 z 10 kol (2112)2009-05-26Papír.[6]
BLAKE2b22562,5 z 12 kol (2224)2009-05-26Papír.[6]

Zvolený prefix kolizní útok

Funkce hashBezpečnostní požadavekNejlepší útokDatum zveřejněníKomentář
MD52642392009-06-16Tento útok na běžném počítači trvá hodiny.[7]
SHA-1280263.42020-01-08Papír Gaëtana Leurenta a Thomase Peyrina[2]
SHA2562128
SHA5122256
SHA-3Až 2512
BLAKE2s2128
BLAKE2b2256

Preimage odpor

Hlavní článek: Preimage útok
Funkce hashBezpečnostní požadavekNejlepší útokDatum zveřejněníKomentář
MD521282123.42009-04-27Papír.[8]
SHA-1216045 z 80 kol2008-08-17Papír.[9]
SHA256225643 ze 64 kol (2254.9 čas, 26 Paměť)2009-12-10Papír.[10]
SHA512251246 z 80 kol (2511.5 čas, 26 Paměť)2008-11-25Papír,[11] aktualizovaná verze.[10]
SHA-3Až 2512
BLAKE2s22562,5 z 10 kol (2241)2009-05-26Papír.[6]
BLAKE2b22562,5 z 12 kol (2481)2009-05-26Papír.[6]

Prodloužení délky

Hlavní článek: Útok prodloužení délky
  • Zranitelné: MD5, SHA1, SHA256, SHA512
  • Není zranitelný: SHA384, SHA-3, BLAKE2

Méně časté hashovací funkce

Odolnost proti kolizi

Funkce hashBezpečnostní požadavekNejlepší útokDatum zveřejněníKomentář
GOST212821052008-08-18Papír.[12]
HAVAL -128264272004-08-17Srážky původně hlášené v roce 2004,[13] v roce 2005 následoval dokument o dešifrování.[14]
MD2264 263.3 čas, 252 Paměť 2009O něco méně výpočetně nákladnější než narozeninový útok,[15] ale z praktických důvodů to požadavky na paměť zdražují.
MD42643 operace2007-03-22Nalezení kolizí téměř tak rychle jako jejich ověření.[16]
PANAMA2128262007-04-04Papír,[17] vylepšení dřívějšího teoretického útoku z roku 2001.[18]
RIPEMD (originál)264218 čas2004-08-17Srážky původně hlášené v roce 2004,[13] v roce 2005 následoval papír o dešifrování.[19]
RadioGatúnAž 2608[20]27042008-12-04Pro velikost slova w mezi 1-64 bity hash poskytuje bezpečnostní požadavek 29.5w. Útok může najít kolizi ve 211w čas.[21]
RIPEMD-16028048 z 80 kol (251 čas)2006Papír.[22]
SHA-0280233.6 čas2008-02-11Kolize se dvěma bloky pomocí útok bumerangu. U průměrného počítače trvá útok odhadem 1 hodinu.[23]
Streebog22569,5 kola po 12 (2176 čas, 2128 Paměť)2013-09-10Odražený útok.[24]
vířivá vana22564,5 z 10 kol (2120 čas)2009-02-24Odražený útok.[25]

Preimage odpor

Funkce hashBezpečnostní požadavekNejlepší útokDatum zveřejněníKomentář
GOST225621922008-08-18Papír.[12]
MD22128273 čas, 273 Paměť2008Papír.[26]
MD421282102 čas, 233 Paměť2008-02-10Papír.[27]
RIPEMD (originál)212835 z 48 kol2011Papír.[28]
RIPEMD-128212835 z 64 nábojů
RIPEMD-160216031 z 80 kol
Streebog25122266 čas, 2259 data2014-08-29Příspěvek představuje dva útoky druhé preimage s požadavky na proměnná data.[29]
Tygr21922188.8 čas, 28 Paměť2010-12-06Papír.[30]

Útoky na hashovaná hesla

Hlavní článek: Prolomení hesla

Zde popsané haše jsou navrženy pro rychlý výpočet a mají zhruba podobnou rychlost.[31] Protože většina uživatelů obvykle volí krátké hesla vytvořena předvídatelnými způsoby, hesla lze často obnovit z jejich hodnoty hash, pokud se použije rychlý hash. U špičkových zařízení je možné hledat řádově 100 miliard testů za sekundu grafické procesory.[32][33] Volaly se speciální hashe funkce odvození klíče byly vytvořeny pro zpomalení vyhledávání hrubou silou. Tyto zahrnují pbkdf2, bcrypt, scrypt, argon2, a balón.

Viz také

Reference

  1. ^ Tao Xie; Fanbao Liu; Dengguo Feng (25. března 2013). „Fast Collision Attack on MD5“. Citovat deník vyžaduje | deník = (Pomoc)
  2. ^ A b Gaëtan Leurent; Thomas Peyrin (08.01.2020). „SHA-1 is a Shambles: First Chosen-Prefix Collision on SHA-1 and Application to the PGP Web of Trust“ (PDF). Citovat deník vyžaduje | deník = (Pomoc)
  3. ^ Florian Mendel; Tomislav Nad; Martin Schläffer (2013-05-28). Zlepšení místních kolizí: Nové útoky na redukovaný SHA-256. Eurokrypt 2013.
  4. ^ Somitra Kumar Sanadhya; Palash Sarkar (2008-11-25). Nové kolize útočí až na 24stupňové SHA-2. Indokrypt 2008. doi:10.1007/978-3-540-89754-5_8.
  5. ^ L. Song, G. Liao a J. Guo, linearizace non-full Sbox: aplikace pro kolizní útoky na kulatý redukovaný Keccak, CRYPTO, 2017
  6. ^ A b C d LI Ji; XU Liangyu (2009-05-26). „Útoky na BLAKE s kulatým snížením“. Citovat deník vyžaduje | deník = (Pomoc)
  7. ^ Marc Stevens; Arjen Lenstra; Benne de Weger (16. 06. 2009). "Vybrané prefixové kolize pro MD5 a aplikace" (PDF). Citovat deník vyžaduje | deník = (Pomoc)
  8. ^ Yu Sasaki; Kazumaro Aoki (2009-04-27). Hledání preimages v plném MD5 rychleji než vyčerpávajícím vyhledáváním. Eurokrypt 2009. doi:10.1007/978-3-642-01001-9_8.
  9. ^ Christophe De Cannière; Christian Rechberger (2008-08-17). Preimages for Reduced SHA-0 and SHA-1. Crypto 2008.
  10. ^ A b Kazumaro Aoki; Jian Guo; Krystian Matusiewicz; Yu Sasaki; Lei Wang (10. 12. 2009). Předpoklady pro krokově redukovaný SHA-2. Asiacrypt 2009. doi:10.1007/978-3-642-10366-7_34.
  11. ^ Yu Sasaki; Lei Wang; Kazumaro Aoki (2008-11-25). „Preimage Attacks on 41-Step SHA-256 and 46-Step SHA-512“. Citovat deník vyžaduje | deník = (Pomoc)
  12. ^ A b Florian Mendel; Norbert Pramstaller; Christian Rechberger; Marcin Kontak; Janusz Szmidt (18. 8. 2008). Kryptoanalýza hašovací funkce GOST. Crypto 2008.
  13. ^ A b Xiaoyun Wang; Dengguo Feng; Xuejia Lai; Hongbo Yu (2004-08-17). „Kolize pro hashovací funkce MD4, MD5, HAVAL-128 a RIPEMD“. Citovat deník vyžaduje | deník = (Pomoc)
  14. ^ Xiaoyun Wang; Dengguo Feng; Xiuyuan Yu (říjen 2005). „Útok na hashovací funkci HAVAL-128“ (PDF). Science in China Series F: Information Sciences. 48 (5): 545–556. CiteSeerX  10.1.1.506.9546. doi:10.1360/122004-107. Archivovány od originál (PDF) dne 9. 8. 2017. Citováno 2014-10-23.
  15. ^ Lars R. Knudsen; John Erik Mathiassen; Frédéric Muller; Søren S. Thomsen (leden 2010). "Kryptoanalýza MD2". Journal of Cryptology. 23 (1): 72–90. doi:10.1007 / s00145-009-9054-1. S2CID  2443076.
  16. ^ Yu Sasaki; Yusuke Naito; Noboru Kunihiro; Kazuo Ohta (2007-03-22). "Vylepšené kolizní útoky na MD4 a MD5". IEICE Transaction on Fundamentals of Electronics, Communications and Computer Sciences. E90-A (1): 36–47. Bibcode:2007IEITF..90 ... 36S. doi:10.1093 / ietfec / e90-a.1.36.
  17. ^ Joan Daemen; Gilles Van Assche (04.04.2007). Okamžité vytváření kolizí pro Panamu. FSE 2007.
  18. ^ Vincent Rijmen; Bart Van Rompay; Bart Preneel; Joos Vandewalle (2001). Produkce kolizí pro PANAMU. FSE 2001.
  19. ^ Xiaoyun Wang; Xuejia Lai; Dengguo Feng; Hui Chen; Xiuyuan Yu (2005-05-23). Kryptoanalýza hashovacích funkcí MD4 a RIPEMD. Eurokrypt 2005. doi:10.1007/11426639_1.
  20. ^ RadioGatún je rodina 64 různých hash funkcí. Úroveň zabezpečení a nejlepší útok v grafu platí pro 64bitovou verzi. 32bitová verze RadioGatún má nárokovanou úroveň zabezpečení 2304 a nejlépe prohlášený útok trvá 2352 práce.
  21. ^ Thomas Fuhr; Thomas Peyrin (04.12.2008). Kryptoanalýza RadioGatun. FSE 2009.
  22. ^ Florian Mendel; Norbert Pramstaller; Christian Rechberger; Vincent Rijmen (2006). O kolizním odporu RIPEMD-160. ISC 2006.
  23. ^ Stéphane Manuel; Thomas Peyrin (11. 2. 2008). Kolize na SHA-0 za jednu hodinu. FSE 2008. doi:10.1007/978-3-540-71039-4_2.
  24. ^ Zongyue Wang; Hongbo Yu; Xiaoyun Wang (10.09.2013). "Kryptoanalýza hašovací funkce GOST R". Dopisy o zpracování informací. 114 (12): 655–662. doi:10.1016 / j.ipl.2014.07.007.
  25. ^ Florian Mendel; Christian Rechberger; Martin Schläffer; Søren S. Thomsen (2009-02-24). The Rebound Attack: Cryptanalysis of Reduced Whirlpool and Grøstl (PDF). FSE 2009.
  26. ^ Søren S. Thomsen (2008). „Vylepšený preimage útok na MD2“. Citovat deník vyžaduje | deník = (Pomoc)
  27. ^ Gaëtan Leurent (10.02.2008). MD4 není jednosměrný (PDF). FSE 2008.
  28. ^ Chiaki Ohtahara; Yu Sasaki; Takeshi Shimoyama (2011). Preimage Attacks on Step-Reduced RIPEMD-128 and RIPEMD-160. ISC 2011. doi:10.1007/978-3-642-21518-6_13.
  29. ^ Jian Guo; Jérémy Jean; Gaëtan Leurent; Thomas Peyrin; Lei Wang (2014-08-29). Využití Counter Revisited: Second-Preimage Attack on New Russian Standardized Hash Function. SAC 2014.
  30. ^ Jian Guo; San Ling; Christian Rechberger; Huaxiong Wang (06.12.2010). Pokročilé útoky typu Meet-in-the-Middle Preimage: První výsledky na Full Tiger a vylepšené výsledky na MD4 a SHA-2. Asiacrypt 2010. s. 12–17.
  31. ^ „ECRYPT Benchmarking kryptografických hashů“. Citováno 23. listopadu 2020.
  32. ^ „Mind-blowing GPU performance“. Improsec. 3. ledna 2020.
  33. ^ Goodin, Dan (2012-12-10). „Klastr 25 GPU prolomí každé standardní heslo systému Windows za <6 hodin“. Ars Technica. Citováno 2020-11-23.

externí odkazy