Muliminty Note

06-哈希函数

10分钟阅读

哈希函数（Hash Functions）

哈希函数是将任意长度的输入数据转换为固定长度输出的数学函数，在网络安全中用于数据完整性验证、密码存储和数字签名

什么是哈希函数

哈希函数（也称散列函数或摘要函数）是一种数学函数，它将任意长度的输入数据映射为固定长度的输出值。

哈希函数的基本流程

输入数据（任意长度）
        │
        ▼
    [哈希算法]
        │
        ▼
哈希值（固定长度）

哈希函数的特点

  1. 固定输出长度：无论输入多长，输出长度固定
  2. 确定性：相同输入总是产生相同输出
  3. 高效性：计算哈希值速度快
  4. 不可逆性：从哈希值难以推导出原始输入
  5. 抗碰撞性：难以找到产生相同哈希值的不同输入

密码学哈希函数属性

1. 雪崩效应

输入数据的微小变化会导致输出哈希值的巨大变化。

输入1: "Hello World"
输出: a591a6d40bf420404a011733cfb7b190d62c65bf0bcda32b57b277d9ad9f146e

输入2: "hello World" (仅首字母小写)
输出: 64ec88ca00b268e5ba1a35678a1b5316d212f4f366b247724e7d24b375f114bb

2. 单向性

从哈希值计算原始输入在计算上是不可行的。

3. 抗碰撞性

弱抗碰撞性：给定输入x，难以找到y≠x使得hash(x)=hash(y)

强抗碰撞性：难以找到任意两个不同的x和y，使得hash(x)=hash(y)

常见哈希算法

1. MD系列

MD5（Message Digest 5）

  • 输出长度：128位（16字节）
  • 设计者：Ron Rivest
  • 状态：已被证明不安全，不建议用于安全应用
  • 适用场景：非安全场景的数据完整性检查
import hashlib
hash_md5 = hashlib.md5(b"Hello World")
print(hash_md5.hexdigest())
# 输出: b10a8db164e0754105b7a99be72e3fe5

2. SHA系列

SHA-1（Secure Hash Algorithm 1）

  • 输出长度：160位（20字节）
  • 设计者：美国国家安全局（NSA）
  • 状态：已被证明不安全，不建议使用
  • 应用历史：曾广泛用于Git、SSL证书

SHA-2（SHA-256, SHA-384, SHA-512）

SHA-2系列包含多个算法，输出长度不同：

算法输出长度内部块大小轮数
SHA-224224位512位64
SHA-256256位512位64
SHA-384384位1024位80
SHA-512512位1024位80

SHA-256示例：

import hashlib
hash_sha256 = hashlib.sha256(b"Hello World")
print(hash_sha256.hexdigest())
# 输出: a591a6d40bf420404a011733cfb7b190d62c65bf0bcda32b57b277d9ad9f146e

SHA-3（Keccak）

  • 标准时间：2015年
  • 特点：与SHA-2完全不同的内部结构（海绵结构）
  • 优势：抗长度扩展攻击
  • 变体：SHA3-224, SHA3-256, SHA3-384, SHA3-512

3. 其他哈希算法

BLAKE2

  • 特点：比SHA-3更快，安全性高
  • 变体：BLAKE2b（64位）和BLAKE2s（32位）
  • 应用：Argon2密码哈希、一些加密货币

RIPEMD-160

  • 输出长度：160位
  • 应用：比特币地址生成
  • 特点：与SHA-1结合使用增强安全性

哈希算法内部结构

1. MD4/MD5结构

  1. 填充：使输入长度为512位的倍数
  2. 初始化：设置4个32位缓冲区（A、B、C、D）
  3. 处理：64轮操作，每轮使用不同的非线性函数
  4. 输出：连接4个缓冲区的值

2. SHA-256结构

  1. 初始化：设置8个32位工作变量（H0-H7）
  2. 填充：添加’1’位、零位和64位长度信息
  3. 分块处理：每512位分块，64轮操作
    • 消息调度：扩展16个字为64个字
    • 压缩函数：更新工作变量
  4. 输出：连接8个工作变量

3. SHA-3（Keccak）结构

SHA-3使用海绵结构，分为吸收阶段和挤压阶段：

吸收阶段:
输入 → [状态变换函数] → 状态

挤压阶段:
状态 → [状态变换函数] → 输出

密码学应用

1. 密码存储

哈希函数用于安全存储用户密码，防止密码泄露。

基本密码哈希（不推荐）

import hashlib
def hash_password(password):
    return hashlib.sha256(password.encode()).hexdigest()

问题：

  • 相同密码产生相同哈希（彩虹表攻击）
  • 计算速度快，易于暴力破解

加盐哈希（Salted Hash）

在密码中添加随机盐值再哈希：

import hashlib
import os
 
def hash_password_with_salt(password):
    salt = os.urandom(16)  # 16字节随机盐
    salted_password = salt + password.encode()
    hash_value = hashlib.sha256(salted_password).hexdigest()
    return salt.hex() + hash_value
 
def verify_password(stored_hash, password):
    salt = bytes.fromhex(stored_hash[:32])  # 前32位是盐
    stored_hash_part = stored_hash[32:]
    salted_password = salt + password.encode()
    calculated_hash = hashlib.sha256(salted_password).hexdigest()
    return calculated_hash == stored_hash_part

密码哈希函数

专门的密码哈希函数设计为计算慢，抗暴力破解：

  • bcrypt：基于Blowfish，内置盐值，可配置计算成本
  • PBKDF2：基于HMAC，可配置迭代次数
  • Argon2：2015年密码哈希竞赛冠军，抗GPU/ASIC攻击

2. 数字签名

哈希函数用于数字签名，先将消息哈希，然后对哈希值签名：

消息 → [哈希函数] → 哈希值 → [私钥签名] → 数字签名

3. 消息认证码（MAC）

结合密钥和哈希函数生成认证码：

  • HMAC：基于哈希的消息认证码
  • CMAC：基于密码的消息认证码
import hmac
import hashlib
 
def generate_hmac(key, message):
    return hmac.new(key, message, hashlib.sha256).hexdigest()

4. 数据完整性验证

校验文件或数据传输的完整性：

def verify_file_integrity(file_path, expected_hash):
    with open(file_path, 'rb') as f:
        file_hash = hashlib.sha256(f.read()).hexdigest()
    return file_hash == expected_hash

哈希表应用

非密码学应用中，哈希函数用于快速数据查找：

1. 哈希表结构

数组索引 = hash(key) % array_size

2. 冲突解决

  • 链式法：相同哈希值的元素存储在链表中
  • 开放寻址法：寻找下一个空闲位置
  • 二次探测：使用二次函数寻找位置
  • 双倍哈希：使用两个哈希函数

哈希函数攻击

1. 碰撞攻击

找到两个不同输入产生相同哈希值。

MD5碰撞示例

# 两个不同的PDF文件具有相同的MD5哈希
file1_md5 = "79054025255fb1a26e4bc422aef54eb4"
file2_md5 = "79054025255fb1a26e4bc422aef54eb4"

碰撞攻击应用

  • 伪造数字签名：创建与合法文件相同哈希的恶意文件
  • 软件后门：创建与原软件相同哈希的恶意版本

2. 长度扩展攻击

某些哈希函数（如MD5、SHA-1、SHA-2）易受长度扩展攻击：

已知: hash(message) 和 message
计算: hash(message || padding || extension)
无需: 知道message的内容

防御：使用HMAC或SHA-3

3. 彩虹表攻击

预计算大量密码的哈希值，用于快速破解：

彩虹表项: 密码1 → 哈希1 → 约简1 → 密码2 → 哈希2 → ...

防御：

  • 使用盐值
  • 使用专门设计的密码哈希函数
  • 增加计算成本

哈希函数选择指南

1. 安全场景

应用场景推荐算法理由
数字签名SHA-256、SHA-3安全性高，广泛支持
密码存储bcrypt、Argon2专门设计，抗破解
消息认证HMAC-SHA256标准化，安全可靠
区块链SHA-256、Keccak工作量证明，安全性高

2. 非安全场景

应用场景推荐算法理由
数据校验CRC32、MD5速度快，适合错误检测
哈希表城市哈希、MurmurHash分布均匀，性能好
缓存键CityHash、xxHash速度快，冲突少

安全实践建议

1. 算法选择

  • 避免使用：MD5、SHA-1（除非用于非安全目的）
  • 推荐使用：SHA-256、SHA-3
  • 密码存储：使用专门的密码哈希函数

2. 实现安全

  • 使用标准库：避免自己实现哈希算法
  • 避免已知漏洞：了解算法的已知攻击
  • 定期更新：关注密码学社区最新发现

3. 使用最佳实践

  • 密码存储：加盐+慢哈希函数
  • 数据完整性：使用HMAC或数字签名
  • 随机数生成：使用密码学安全的随机数生成器

🔗 相关链接

最后更新：2025-01-26 维护规范：详见 笔记规范文档

哈希函数 SHA MD5 密码存储 HMAC

关系图谱

反向链接