密码哈希函数

密码哈希函数以单向和抗碰撞的方式将任意输入压缩成短的固定长度摘要，作为完整性、认证和许多更高级协议的基本组成部分。

Definition

密码哈希函数是一个确定性函数，将任意长度的输入映射到固定长度的输出（摘要），使得找到原像、第二原像或任何两个产生相同输出的不同输入是不可行的。

Scope

本主题涵盖哈希函数的安全属性（原像抵抗、第二原像抵抗和碰撞抵抗）、其内部构造（Merkle-Damgaard、海绵结构）、标准化的SHA-2和SHA-3系列，以及完整性验证、密码存储、承诺和工作量证明等应用。它讨论了包括生日界限以及MD5和SHA-1的破解在内的密码分析攻击。它不包括密钥认证码，后者在消息认证码中处理，尽管许多MAC是由哈希函数构建的。

Core questions

• 密码哈希函数与普通校验和或哈希表函数有何区别？
• 为什么原像抵抗、第二原像抵抗和碰撞抵抗是不同的，它们之间有何关系？
• 为什么生日悖论将碰撞抵抗限制在摘要长度的一半？
• Merkle-Damgaard和海绵结构如何将固定大小的压缩扩展到任意输入？
• 哈希函数如何用于数据承诺、完整性验证和密码存储？

Key concepts

• 消息摘要
• 原像抵抗
• 第二原像抵抗
• 碰撞抵抗
• 生日攻击
• Merkle-Damgaard结构
• 海绵结构 (Keccak)
• 长度扩展攻击
• 工作量证明

Key theories

碰撞抵抗与生日界限

由于生日悖论，对n位哈希的通用碰撞查找攻击在大约2^(n/2)次工作中成功；因此，碰撞抵抗要求摘要大约是所需安全级别（例如，128位安全需要256位）的两倍。

迭代和海绵结构

Merkle-Damgaard范式通过对消息块迭代固定输入压缩函数来构建完整的哈希；SHA-3（Keccak）使用的海绵结构将输入吸收到一个大的置换状态中并从中挤出输出，从而避免了长度扩展的弱点。

Mechanisms

Merkle-Damgaard哈希对消息进行填充，将其分成块，并迭代应用一个压缩函数，将每个块混合到一个运行中的链值中，将最终值作为摘要输出。SHA-3的海绵结构则通过将消息块与Keccak-f函数置换的大状态的一部分进行异或运算来吸收消息块，然后挤出摘要位，这避免了纯Merkle-Damgaard固有的长度扩展属性。

Clinical relevance

哈希函数无处不在：它们验证软件下载的完整性，锚定数字签名（签名的是哈希，而不是整个文档），在Git和内容分发网络中索引内容，通过慢速密钥派生函数（bcrypt、Argon2）保护密码存储，并提供区块链底层的工作量证明和默克尔树。MD5和SHA-1碰撞抵抗的实际破解迫使互联网迁移到SHA-2。

Evidence & guidelines

SHA-2（SHA-256、SHA-512）在FIPS 180-4中指定，SHA-3在FIPS 202中指定；两者均获得NIST批准。MD5和SHA-1在已证明的碰撞攻击（2017年的SHAttered SHA-1碰撞是一个里程碑）后，已弃用用于安全用途。对于密码存储，标准建议使用内存密集型函数，如Argon2，而不是简单的哈希。

History

MD家族（Rivest的MD4和MD5）以及NSA设计的SHA-0/SHA-1在1990年代占据主导地位。王小云的碰撞攻击（2004-2005）破解了MD5并削弱了SHA-1，促使NIST启动了开放的SHA-3竞赛（2007-2012），最终由Bertoni、Daemen、Peeters和Van Assche的Keccak海绵设计获胜。SHA-1在2017年因SHAttered碰撞而实际被破解。

Key figures

• Ralph Merkle
• Ivan Damgaard
• Guido Bertoni
• Joan Daemen
• Xiaoyun Wang

Seminal works

• nist2015sha3
• katz2020
• menezes1996

Frequently asked questions

为什么我不能只哈希密码并存储摘要？

普通的密码哈希速度很快，这使得攻击者可以对被盗数据库每秒尝试数十亿次猜测。密码存储反而使用故意缓慢、加盐、内存密集型函数（bcrypt、scrypt、Argon2），以便暴力破解每个密码的成本很高。

SHA-1被破解后，SHA-256也失效了吗？

没有。SHA-1和SHA-256是不同的算法；对SHA-1的碰撞攻击不会转移到SHA-2。SHA-256仍然未被破解，并且是推荐的通用哈希，与SHA-3并列。