SipHash 流密码算法的密钥初始化与轮函数细节
SipHash 是一个伪随机函数（PRF）家族，设计目标是在短消息输入上快速、安全地生成一个加密哈希值，常用于哈希表（如字典、集合）中的键控哈希，以对抗哈希泛洪拒绝服务（HashDoS）攻击。其核心是一个基于 ARX（加法、循环移位、异或）操作的流密码/伪随机函数，通过特定的密钥初始化和轮函数迭代来处理输入消息。下面我将详细解析其密钥初始化过程和轮函数内部细节。
1. 算法背景与基本参数
SipHash 通常有两个版本：SipHash-2-4 和 SipHash-4-8，其中第一个数字表示“压缩轮数”（c），第二个数字表示“最终轮数”（d）。以 SipHash-2-4 为例：
- 输入：一个 128 位的密钥
k（16 字节）和一条可变长度的消息m。 - 输出：一个 64 位的哈希值。
- 核心结构：一个类似海绵结构的状态机，但其核心是一个基于 ARX 的置换函数，用于混合密钥、消息和内部状态。
2. 初始状态设置与密钥初始化
SipHash 的内部状态是 4 个 64 位字，记为 v0、v1、v2、v3。初始状态的设置将密钥和几个预定义的常量（称为“初始化向量”）进行组合。这个步骤至关重要，因为它确保了哈希的伪随机性从起始就依赖于密钥。
-
密钥拆分：128 位密钥
k被拆分成两个 64 位字。k0= 密钥的低 64 位（k[0..7]，采用小端序解释）。k1= 密钥的高 64 位（k[8..15]，采用小端序解释）。
-
常量设置：定义了四个 64 位常量，它们包含一些固定的字节模式，用于增加状态的“熵”和避免固定点。
v0_iv=0x736f6d6570736575（ASCII 码近似为“somepseu”）v1_iv=0x646f72616e646f6d（ASCII 码近似为“dorandom”）v2_iv=0x6c7967656e657261（ASCII 码近似为“lygenera”）v3_iv=0x7465646279746573（ASCII 码近似为“tedbytes”）
-
初始状态生成：通过异或运算，将密钥注入到初始化向量中。这是密钥初始化的核心一步。
v0 = v0_iv XOR k0v1 = v1_iv XOR k1v2 = v2_iv XOR k0v3 = v3_iv XOR k1
这个设计的巧妙之处在于，k0 和 k1 分别与 v0/v2 和 v1/v3 结合，确保了密钥的每一位都至少影响状态中的两个字，并且在后续的轮函数中会被充分扩散。
3. 轮函数详解
轮函数是 SipHash 的核心置换操作，记为 SipRound。它接受 4 个 64 位状态字 v0, v1, v2, v3 作为输入，原地更新它们。一个 SipRound 包含四次 ARX 操作，对四个状态字进行两两混合。
一个完整的 SipRound 如下：
- 加法-移位-异或操作：
v0 = v0 + v1 - 循环移位：
v1 = (v1 ROTL 13)（ROTL表示循环左移，13是移位位数） - 异或：
v1 = v1 XOR v0 - 再次移位：
v0 = (v0 ROTL 32) - 另一对字的混合：
v2 = v2 + v3 - 循环移位：
v3 = (v3 ROTL 16) - 异或：
v3 = v3 XOR v2 - 最后混合：
v0 = v0 + v3 - 循环移位：
v3 = (v3 ROTL 21) - 异或：
v3 = v3 XOR v0 - 另一对的最终混合：
v2 = v2 + v1 - 循环移位：
v1 = (v1 ROTL 17) - 异或：
v1 = v1 XOR v2 - 最后移位：
v2 = (v2 ROTL 32)
理解轮函数的设计思想：它通过加法、循环移位、异或操作，实现了状态字之间的快速、高扩散的混淆。加法（+）是模 2^64 加法，提供了非线性；循环移位（ROTL）在不同距离上（13, 16, 21, 17, 32）扩散比特；异或（XOR）将不同字的比特快速混合。这种 ARX 结构在现代密码设计中很流行，因为它通常在软件实现中非常高效。
4. 消息处理流程（简述以理解轮函数应用）
理解了轮函数后，我们简要看它在整个哈希流程中的应用，这有助于理解“压缩轮”和“最终轮”的概念：
- 初始化：如前所述，用密钥设置初始状态
v0, v1, v2, v3。 - 消息压缩：
- 消息
m被填充并分割成若干个 64 位块（最后一个块包含消息长度模 2^64）。 - 对于每个消息块
mi：- 状态注入：
v3 = v3 XOR mi（将消息块混入状态）。 - 执行
c轮压缩：执行c次（例如 SipHash-2-4 中 c=2）SipRound操作，对状态进行充分的混淆和扩散。 - 状态反馈：
v0 = v0 XOR mi（将处理后的消息影响反馈到状态中）。
- 状态注入：
- 消息
- 最终化：
- 在处理完所有消息块后，会注入一个表示“结束”的标记：
v2 = v2 XOR 0xff。 - 然后，执行
d次（例如 SipHash-2-4 中 d=4）SipRound操作，对最终状态进行“最后的混淆”，确保输出的不可预测性。
- 在处理完所有消息块后，会注入一个表示“结束”的标记：
- 输出生成：
- 最终哈希值是四个状态字的异或和：
哈希值 = v0 XOR v1 XOR v2 XOR v3。
- 最终哈希值是四个状态字的异或和：
总结：
SipHash 的安全性建立在两个基础之上：1. 密钥初始化：将密钥与精心选择的常量结合，形成随机的初始状态。2. 轮函数：通过多轮的 ARX 操作，对内部状态（包含了密钥、消息和常量）进行彻底的混淆和扩散。压缩轮数（c）保证了每个输入块被充分处理，而最终轮数（d）确保了最终输出无法被逆向推导出中间状态。这种设计使得即使攻击者能够选择消息，也无法在未知密钥的情况下预测或制造哈希冲突，从而有效防御了针对哈希表的 HashDoS 攻击。