SipHash
SipHash
设计者
Jean-Philippe Aumasson, Daniel J. Bernstein
首次发布
2012年
类别
MAC / 快速哈希
输出长度
64 / 128 bit
密钥长度
128 bit
结构
ARX (Add-Rotate-Xor)
推荐变体
SipHash-2-4
速度
~1.5 GB/s
安全状态
安全
SipHash 是由 Jean-Philippe Aumasson 和 Daniel J. Bernstein 于 2012 年设计的快速消息认证码（MAC）算法。SipHash 专门解决哈希洪水攻击（Hash Flooding）问题——攻击者通过构造大量碰撞输入使哈希表退化为链表，导致 O(n) 的最坏性能。
设计动机
传统的非加密哈希函数（如 MurmurHash、CityHash）速度极快，但攻击者可以找到大量碰撞。2012年的研究显示，多个编程语言（包括 Python、Ruby、PHP、Java 等）的哈希表实现都容易受到哈希洪水攻击。
SipHash 的目标是：既足够快（可用于哈希表的每次插入和查找），又具备密码学安全性（攻击者在不知道密钥的情况下无法构造碰撞）。
算法描述
SipHash 使用 128 位密钥，基于 ARX（加法-旋转-异或）结构。命名规则：SipHash-c-d，其中 c 为压缩轮数，d 为终结轮数。
SipHash-2-4 核心操作：
SipRound(v0, v1, v2, v3):
v0 += v1; v1 = ROTL(v1, 13); v1 ^= v0; v0 = ROTL(v0, 32)
v2 += v3; v3 = ROTL(v3, 16); v3 ^= v2
v0 += v3; v3 = ROTL(v3, 21); v3 ^= v0
v2 += v1; v1 = ROTL(v1, 17); v1 ^= v2; v2 = ROTL(v2, 32)
return (v0, v1, v2, v3)
# SipHash-2-4: 2 轮压缩 + 4 轮终结
# SipHash-4-8: 4 轮压缩 + 8 轮终结 (更安全, 更慢)
变体
| 变体 | 压缩轮 | 终结轮 | 输出 | 速度 | 安全级别 |
|---|---|---|---|---|---|
| SipHash-2-4 | 2 | 4 | 64 bit | 快 | 推荐（默认） |
| SipHash-4-8 | 4 | 8 | 64 bit | 较慢 | 更高安全裕度 |
| SipHash-2-4-128 | 2 | 4 | 128 bit | 快 | 128位输出 |
| HalfSipHash-2-4 | 2 | 4 | 32 bit | 极快 | 仅32位平台 |
采用情况
- Rust：默认哈希表哈希函数（SipHash-1-3，2021年起改用 aHash）
- Python：3.4+ 版本用于 dict/set 的哈希随机化
- Redis：用于防止恶意键碰撞
- Ruby：用于哈希表实现
- Perl：用于哈希随机化
- Swift：标准库哈希函数
参考文献
- Aumasson, J.-P., Bernstein, D.J. (2012). "SipHash: a fast short-input PRF". IACR ePrint 2012/358.
- Crosby, S.A., Wallach, D.S. (2003). "Denial of Service via Algorithmic Complexity Attacks". USENIX Security 2003.