散列函数安全性概要

本页使用了标题或全文手工转换，现处于中国大陆简体模式
求闻百科，共笔求闻

本文总结了已知公开的针对密码散列函数的攻击。请注意，此列表可能不及最新研究成果新。有关其他参数的摘要，请参阅密码散列函数比较。

图例


 没有攻击——攻击只能用于散列函数的一个简化版本，或攻击复杂性比散列自身声明的最低值还高

 攻击理论可行——攻击可用于完整的散列函数，攻击复杂性也比散列函数原先声明的最低值要低

 攻击实际可行

常用散列函数

抗碰撞

主条目：碰撞_(计算机科学)
散列函数 安全声明 最佳攻击[a] 发表日期 注释
MD5 264 218时间 2013-03-25 在普通PC上只需几秒钟。双块碰撞[b]需218，单块碰撞需241。[1]
SHA-1 280 263.1 2017-02-23 论文发表。[2]
SHA256 2128 64轮中的31轮（265.5） 2013-05-28 双块碰撞。[3]
SHA512 2256 80轮中的27轮 2015-12-30 论文发表。[4]
SHA-3 最大2512 25轮中的6轮（250） 2017 论文发表。[5]
BLAKE2s 2128 10轮中的2.5轮（2112） 2009-05-26 论文发表。[6]
BLAKE2b 2256 12轮中的2.5轮（2224） 2009-05-26 论文发表。[6]
SM3 2128 64轮中的20轮 2013-02 论文发表。[7]

选择前缀碰撞攻击

选择前缀碰撞攻击是采用默克尔-达姆加德结构的散列函数的特有问题。

散列函数 安全声明 最佳攻击 发表日期 注释
MD5 264 239 2009-06-16 普通PC上需数小时。[8]
SHA-1 280 263.4 2020-01-08 论文发表。[9]
SHA256 2128
SHA512 2256
SM3 2128

抗原像

主条目：原像攻击
散列函数 安全声明 最佳攻击 发表日期 注释
MD5 2128 2123.4 2009-04-27 论文发表。[10]
SHA-1 2160 80轮中的45轮 2008-08-17 论文发表。[11]
SHA256 2256 64轮中的43轮（2254.9时间，26内存) 2009-12-10 论文发表。[12]
SHA512 2512 80轮中的46轮（2511.5时间，26内存) 2008-11-25 论文发表[13]，且有更新[12]。
SHA-3 最大2512
BLAKE2s 2256 10轮中的2.5轮（2241） 2009-05-26 论文发表。[6]
BLAKE2b 2256 12轮中的2.5轮（2481） 2009-05-26 论文发表。[6]
SM3 2256 64轮中的32轮（2254.5时间，25内存） 2018-02-07 论文发表。[14]

长度扩展攻击

主条目：长度扩展攻击

所有基于未修改的默克尔-达姆加德结构的散列函数均受长度扩展攻击影响，包括MD4、MD5、SHA-1、SHA-2（非截断版，即SHA256和SHA512）和SM3。SHA-2截断版受影响较小，但并不免疫，因为攻击者可以穷举获得缺失的32至288位后进行攻击；其中，SHA224由于只删去了32位散列值，因而基本无法实现对长度扩展攻击的免疫。长度扩展攻击只对明文已知、密钥长度已知、使用将密钥与明文直接按顺序连接后对整个字符串直接获取的散列值作为消息验证码的程序设计有效，因此较为容易通过修改程序设计，例如应用HMAC应对。

其他散列函数

抗碰撞

散列函数 安全声明 最佳攻击 发表日期 注释
GOST 2128 2105 2008-08-18 论文发表。[15]
HAVAL-128 264 27 2004-08-17 2004年报道了碰撞方法[16]，2005年发表了密码学分析报告[17]。
MD2 264 263.3时间，252内存 2009 比生日攻击的计算成本略低[18]，但对内存的要求使其实际应用变得不现实。
MD4 264 3次操作 2007-03-22 发现碰撞几乎与验证它们一样快。[19]
PANAMA 2128 26 2007-04-04 论文发表[20]，改进自2001年的理论攻击[21]。
RIPEMD（原始版本） 264 218时间 2004-08-17 2004年报道了碰撞方法[16]，2005年发表了密码学分析报告[22]。
RadioGatún 最大2608[c] 2704 2008-12-04 对于介于1-64位之间的字大小w，散列声明29.5w安全性。攻击可以在211w时间内发现碰撞。[23]
RIPEMD-160 280 80轮中的48轮（251时间） 2006 论文发表。[24]
SHA-0 280 233.6时间 2008-02-11 使用回旋镖攻击的双块碰撞。平均上使用PC攻击估计需要1小时。[25]
Streebog 2256 12轮中的9.5轮（2176时间，2128内存） 2013-09-10 反弹攻击。[26]
Whirlpool 2256 10轮中的4.5轮（2120时间） 2009-02-24 反弹攻击。[27]

抗原像

散列函数 安全声明 最佳攻击 发表日期 注释
GOST 2256 2192 2008-08-18 论文发表。[15]
MD2 2128 273时间，273内存 2008 论文发表。[28]
MD4 2128 2102时间，233内存 2008-02-10 论文发表。[29]
RIPEMD（原始版本） 2128 48轮中的35轮 2011 论文发表。[30]
RIPEMD-128 2128 64轮中的35轮
RIPEMD-160 2160 80轮中的31轮
Streebog 2512 2266时间，2259数据 2014-08-29 论文介绍了两种对可变量据有要求的次原像攻击。[31]
Tiger 2192 2188.8时间，28内存 2010-12-06 论文发表。[32]

参见

注释

  1. ↑ 这里的时间和内存都指数量级，见计算复杂性。如果没有复杂性指标，则意味着相应的攻击实际可行
  2. ↑ 指允许最多两个块不同而散列值相同，单块碰撞意义同。
  3. ↑ RadioGatún是一系列散列函数，由64种不同的散列函数组成。图表中的安全级别和最佳攻击适用于64位版本。32位版本的RadioGatún声称安全性为2304，最佳攻击攻击需要2352时间。

参考

  1. ↑ Tao Xie; Fanbao Liu; Dengguo Feng. Fast Collision Attack on MD5. 2013-03-25 [2018-10-09]. 
  2. ↑ Marc Stevens; Elie Bursztein; Pierre Karpman; Ange Albertini; Yarik Markov. The first collision for full SHA-1 (PDF). 2017-02-23 [2018-10-09]. 
  3. ↑ Florian Mendel; Tomislav Nad; Martin Schläffer. Improving Local Collisions: New Attacks on Reduced SHA-256. Eurocrypt 2013. 2013-05-28 [2018-10-09]. 
  4. ↑ Christoph Dobraunig; Maria Eichlseder & Florian Mendel. Analysis of SHA-512/224 and SHA-512/256 (PDF). International Association for Cryptologic Research. 2016.  已忽略未知参数|name-list-style= (帮助)
  5. ↑ L. Song, G. Liao and J. Guo, Non-Full Sbox Linearization: Applications to Collision Attacks on Round-Reduced Keccak, CRYPTO, 2017
  6. ↑ 6.0 6.1 6.2 6.3 LI Ji; XU Liangyu. Attacks on Round-Reduced BLAKE. 2009-05-26 [2018-10-09]. 
  7. ↑ Mendel, Florian & Nad, Tomislav & Schläffer, Martin. (2013). Finding Collisions for Round-Reduced SM3. 10.1007/978-3-642-36095-4_12.
  8. ↑ Marc Stevens; Arjen Lenstra; Benne de Weger. Chosen-prefix Collisions for MD5 and Applications (PDF). 2009-06-16 [2018-10-09]. 
  9. ↑ Gaëtan Leurent; Thomas Peyrin. SHA-1 is a Shambles: First Chosen-Prefix Collision on SHA-1 and Application to the PGP Web of Trust (PDF). 2020-01-08. 
  10. ↑ Yu Sasaki; Kazumaro Aoki. Finding Preimages in Full MD5 Faster Than Exhaustive Search. Eurocrypt 2009. 2009-04-27 [2018-10-09]. 
  11. ↑ Christophe De Cannière; Christian Rechberger. Preimages for Reduced SHA-0 and SHA-1. Crypto 2008. 2008-08-17 [2018-10-09]. 
  12. ↑ 12.0 12.1 Kazumaro Aoki; Jian Guo; Krystian Matusiewicz; Yu Sasaki; Lei Wang. Preimages for Step-Reduced SHA-2. Asiacrypt 2009. 2009-12-10 [2018-10-09]. 
  13. ↑ Yu Sasaki; Lei Wang; Kazumaro Aoki. Preimage Attacks on 41-Step SHA-256 and 46-Step SHA-512. 2008-11-25 [2018-10-09]. 
  14. ↑ Jian ZOU, Le DONG. Improved preimage and pseudo-collision attacks on SM3 hash function. 10.11959/j.issn.1000-436x.2018011.
  15. ↑ 15.0 15.1 Florian Mendel; Norbert Pramstaller; Christian Rechberger; Marcin Kontak; Janusz Szmidt. Cryptanalysis of the GOST Hash Function. Crypto 2008. 2008-08-18. 
  16. ↑ 16.0 16.1 Xiaoyun Wang; Dengguo Feng; Xuejia Lai; Hongbo Yu. Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD. 2004-08-17 [2018-10-09]. 
  17. ↑ Xiaoyun Wang; Dengguo Feng; Xiuyuan Yu. An attack on hash function HAVAL-128 (PDF). Science in China Series F: Information Sciences. 2005-10, 48 (5): 545–556 [2018-10-09]. doi:10.1360/122004-107. 
  18. ↑ Lars R. Knudsen; John Erik Mathiassen; Frédéric Muller; Søren S. Thomsen. Cryptanalysis of MD2. Journal of Cryptology. 2010-01, 23 (1): 72–90 [2018-10-09]. doi:10.1007/s00145-009-9054-1. 
  19. ↑ Yu Sasaki; Yusuke Naito; Noboru Kunihiro; Kazuo Ohta. Improved Collision Attacks on MD4 and MD5. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences. 2007-03-22, E90–A (1): 36–47. doi:10.1093/ietfec/e90-a.1.36. 
  20. ↑ Joan Daemen; Gilles Van Assche. Producing Collisions for Panama, Instantaneously. FSE 2007. 2007-04-04 [2018-10-09]. 
  21. ↑ Vincent Rijmen; Bart Van Rompay; Bart Preneel; Joos Vandewalle. Producing Collisions for PANAMA. FSE 2001. 2001 [2018-10-09]. 
  22. ↑ Xiaoyun Wang; Xuejia Lai; Dengguo Feng; Hui Chen; Xiuyuan Yu. Cryptanalysis of the Hash Functions MD4 and RIPEMD. Eurocrypt 2005. 2005-05-23 [2018-10-09]. 
  23. ↑ Thomas Fuhr; Thomas Peyrin. Cryptanalysis of RadioGatun. FSE 2009. 2008-12-04 [2018-10-09]. 
  24. ↑ Florian Mendel; Norbert Pramstaller; Christian Rechberger; Vincent Rijmen. On the Collision Resistance of RIPEMD-160. ISC 2006. 2006 [2018-10-09]. 
  25. ↑ Stéphane Manuel; Thomas Peyrin. Collisions on SHA-0 in One Hour. FSE 2008. 2008-02-11 [2018-10-09]. 
  26. ↑ Zongyue Wang; Hongbo Yu; Xiaoyun Wang. Cryptanalysis of GOST R hash function. Information Processing Letters. 2013-09-10, 114 (12): 655–662 [2018-10-09]. doi:10.1016/j.ipl.2014.07.007. 
  27. ↑ Florian Mendel; Christian Rechberger; Martin Schläffer; Søren S. Thomsen. The Rebound Attack: Cryptanalysis of Reduced Whirlpool and Grøstl (PDF). FSE 2009. 2009-02-24 [2018-10-09]. 
  28. ↑ Søren S. Thomsen. An improved preimage attack on MD2. 2008 [2018-10-09]. 
  29. ↑ Gaëtan Leurent. MD4 is Not One-Way (PDF). FSE 2008. 2008-02-10 [2018-10-09]. 
  30. ↑ Chiaki Ohtahara; Yu Sasaki; Takeshi Shimoyama. Preimage Attacks on Step-Reduced RIPEMD-128 and RIPEMD-160. ISC 2011. 2011 [2018-10-09]. 
  31. ↑ Jian Guo; Jérémy Jean; Gaëtan Leurent; Thomas Peyrin; Lei Wang. The Usage of Counter Revisited: Second-Preimage Attack on New Russian Standardized Hash Function. SAC 2014. 2014-08-29 [2018-10-09]. 
  32. ↑ Jian Guo; San Ling; Christian Rechberger; Huaxiong Wang. Advanced Meet-in-the-Middle Preimage Attacks: First Results on Full Tiger, and Improved Results on MD4 and SHA-2. Asiacrypt 2010: 12–17. 2010-12-06 [2018-10-09]. 

外部链接

散列函数 & 消息认证码
常用函数
SHA-3入围
其他函数
MAC算法
认证加密模式
攻击
设计
标准化
实际应用
密钥推导函数
取自“https://www.qiuwenbaike.cn/index.php?title=散列函数安全性概要&oldid=7068529”