SipHash 流密码算法的密钥初始化与轮函数细节

题目描述
SipHash是一种面向短消息（如哈希表键）的快速、安全的加密哈希函数（更准确地说，是一种键控伪随机函数）。它结合了流密码SipRound与类似MAC的认证结构。本题要求详细拆解SipHash-2-4版本（2轮压缩，4轮输出）的密钥初始化过程、核心轮函数SipRound的运算步骤，并阐明如何将任意长度消息处理为64位哈希值。

解题过程

1. 算法概述
SipHash接受一个128位密钥K和可变长度消息M，输出一个64位哈希值。核心是一个内部状态，由四个64位字(v0, v1, v2, v3)构成。算法分为三个阶段：

• 初始化：用密钥K和固定常量初始化状态。
• 压缩：将消息分块为64位块，与状态混合，并执行轮函数。
• 最终化：对最后一块处理后，进行多次轮函数与密钥二次混合，输出哈希。

2. 密钥初始化
密钥K分为两个64位字：k0 = K[0:63], k1 = K[64:127]。初始化状态时，将四个字设置如下：

v0 = 0x736f6d6570736575
v1 = 0x646f72616e646f6d
v2 = 0x6c7967656e657261
v3 = 0x7465646279746573

这些常量是“somepseudorandom”等短语的ASCII编码，用于打破对称性。接着，将密钥与v1、v3进行异或：

v3 ^= k1
v2 ^= k0
v1 ^= k1
v0 ^= k0

这使得状态与密钥绑定。

3. 核心轮函数SipRound详解
SipRound对状态(v0, v1, v2, v3)执行一系列算术与位运算，每轮包含四个步骤：

1. 加法与循环左移（v0, v1）：
   v0 = v0 + v1
   将v0循环左移13位：v0 = (v0 <<< 13)
2. 异或与循环左移（v1, v0）：
   v1 = v1 ^ v0
   将v1循环左移32位：v1 = (v1 <<< 32)
3. 加法与循环左移（v2, v3）：
   v2 = v2 + v3
   将v2循环左移16位：v2 = (v2 <<< 16)
4. 异或与循环左移（v3, v2）：
   v3 = v3 ^ v2
   将v3循环左移21位：v3 = (v3 <<< 21)
   接着，交换两对字的位置：

• 交换v1和v3：v1, v3 = v3, v1
• 交换v2和v0：v2, v0 = v0, v2
  这一步称为“换行”，确保所有字充分混合。

4. 消息压缩过程
消息M被填充为8字节（64位）的倍数。设m_i为第i个64位块，c为总块数。对每个块处理：

• 将当前块m_i与v3异或：v3 ^= m_i
• 执行2轮SipRound（称为“压缩轮数”，c=2）
• 将v0与m_i异或：v0 ^= m_i
  处理完所有块后，用结束标记（消息长度的低7位）处理最后一个块：
• 将v3与(msg_len mod 256) << 56异合（即长度编码在最高字节）
• 执行2轮SipRound
• 将v0与结束标记异或。

5. 最终化与输出
状态再次与密钥混合，确保密钥影响最终输出：

v2 ^= k1
v1 ^= k0
v3 ^= k1
v0 ^= k0

接着执行4轮SipRound（称为“最终化轮数”，d=4）。最终哈希值为：

hash = v0 ^ v1 ^ v2 ^ v3

这个64位值即为SipHash-2-4的输出。

总结
SipHash通过密钥初始化、轮函数SipRound的迭代、消息分块压缩和最终密钥混合，在保证速度的同时提供抗碰撞和抗伪造的安全性。其设计特别适合哈希表等场景，防止哈希泛洪攻击。