SipHash流密码算法的轮函数设计与压缩过程
字数 2369 2025-12-18 18:12:23

SipHash流密码算法的轮函数设计与压缩过程

算法概述

SipHash是一种流密码算法，但它常被设计用作一个键控哈希函数（或消息认证码MAC），特别适用于短输入（如哈希表键）的快速计算。它的核心是一个伪随机函数（PRF），具有抗碰撞和抗第二原像攻击的安全性，并能抵抗哈希泛洪拒绝服务攻击。SipHash算法基于添加-旋转-异或（ARX）操作构建，结构简洁高效。我们重点讲解其核心轮函数（SipRound）的设计，以及如何通过迭代轮函数来完成数据的压缩。

核心状态与初始化

SipHash内部维护一个64位的状态，由四个64位字（v0, v1, v2, v3）组成。

  1. 初始化：算法使用一个128位的密钥K（分为两个64位字k0和k1）和两个64位的常量（c0=0x736f6d6570736575, c1=0x646f72616e646f6d, c2=0x6c7967656e657261, c3=0x7465646279746573）来初始化状态。
    • v0 = c0 ⊕ k0
    • v1 = c1 ⊕ k1
    • v2 = c0 ⊕ k0
    • v3 = c1 ⊕ k1
    • 这里，c2和c3稍后在处理消息结束时使用。

轮函数SipRound详解

SipRound是算法的核心变换，它对四个状态字（v0, v1, v2, v3）进行一系列ARX操作。其设计目标是实现良好的扩散和非线性。让我们一步一步拆解：
假设当前状态为 (v0, v1, v2, v3)。

步骤1：对 v0 和 v1 的运算

  1. 加法（A）： v0 = v0 + v1
    • 将 v0 和 v1 作为无符号64位整数相加，结果对 2^64 取模（即自然的溢出进位被丢弃）。
  2. 循环左移（R）： v1 = v1 <<< 13
    • 将 v1 向左循环移动13位。<<< 表示循环左移。
  3. 异或（X）： v1 = v1 ⊕ v0
    • 将移位后的 v1 与新的 v0 进行按位异或。
  4. 再次循环左移： v0 = v0 <<< 32
    • 将 v0 向左循环移动32位。

步骤2：对 v2 和 v3 的运算（对称操作）
5. 加法： v2 = v2 + v3
6. 循环左移： v3 = v3 <<< 16
7. 异或： v3 = v3 ⊕ v2
8. 再次循环左移： v2 = v2 <<< 32

步骤3：交叉混合
9. 交叉加法： v0 = v0 + v3
* 将步骤1处理过的 v0 与步骤2处理过的 v3 相加。
10. 循环左移： v3 = v3 <<< 21
11. 异或： v3 = v3 ⊕ v0
12. 交叉加法： v2 = v2 + v1
* 将步骤2处理过的 v2 与步骤1处理过的 v1 相加。
13. 循环左移： v1 = v1 <<< 17
14. 异或： v1 = v1 ⊕ v2
15. 最后移位： v2 = v2 <<< 32

至此，一轮SipRound完成。它通过加法引入非线性（因为进位传播是非线性的），通过循环移位实现比特位的扩散，通过异或实现快速的混合。整个操作非常高效，在现代CPU上只需少量指令。

消息压缩过程

SipHash将任意长度的消息M压缩成一个64位的哈希值。这个过程可以看作一个海绵结构的简化版，分为两个主要阶段：吸收（Compression） 和 挤压（Finalization）。

阶段一：吸收（消息处理）

  1. 消息分组：将消息M填充并分割成多个8字节（64位）的分组 m_i。填充规则是在消息末尾添加一个字节0x80，然后填充零直到总长度（包括原始消息、0x80和填充零）是8字节的倍数，最后8字节存储原始消息长度的低64位（小端序）。
  2. 循环处理每个分组：对于每个消息分组 m_i：
    a. 注入：将分组异或到状态的一个字上。具体是 v3 = v3 ⊕ m_i。
    b. 应用 c 轮 SipRound：连续执行 c 次 SipRound 函数。c 是一个安全参数，通常取2（即SipHash-2-4中的第一个数字）。
    c. 再次注入：将同一个分组再次异或到另一个状态字上。具体是 v0 = v0 ⊕ m_i。
    这个过程确保了每个消息分组都与状态进行了两次混合（前一次和后一次），并经过多轮SipRound的充分混淆。

阶段二：挤压（最终化）
在处理完所有消息分组后，进入最终化阶段，输出最终的哈希值。

  1. 终态标记：将状态字 v2 与一个常量进行异或，作为处理结束的标记：v2 = v2 ⊕ 0xff。
  2. 应用 d 轮 SipRound：连续执行 d 次 SipRound 函数。d 是另一个安全参数，通常取4（即SipHash-2-4中的第二个数字）。
  3. 最终混合：
    • v0 = v0 ⊕ v1
    • v0 = v0 ⊕ v2
    • v0 = v0 ⊕ v3
      这一步将四个状态字的信息压缩到 v0 中。
  4. 输出：v0 的64位值就是最终的SipHash哈希值。

总结

SipHash的设计精髓在于其简洁而有效的轮函数SipRound，它通过ARX操作在极少的CPU周期内实现了良好的密码学强度。整个压缩过程通过“注入-混淆-再注入”的模式处理消息，最后经过一个带标记的最终混淆阶段产生输出。其安全性参数（c 和 d）可以调整以平衡速度和安全，SipHash-2-4是常用的快速安全配置。这使得SipHash非常适合需要高速、抗碰撞且能抵抗恶意输入的哈希场景，如编程语言中的哈希表（例如Python、Ruby从3.4/2.1版本开始使用SipHash防御哈希碰撞攻击）。

SipHash流密码算法的轮函数设计与压缩过程 算法概述 SipHash是一种流密码算法，但它常被设计用作一个键控哈希函数（或消息认证码MAC），特别适用于短输入（如哈希表键）的快速计算。它的核心是一个伪随机函数（PRF），具有抗碰撞和抗第二原像攻击的安全性，并能抵抗哈希泛洪拒绝服务攻击。SipHash算法基于添加-旋转-异或（ARX）操作构建，结构简洁高效。我们重点讲解其核心轮函数（SipRound）的设计，以及如何通过迭代轮函数来完成数据的压缩。 核心状态与初始化 SipHash内部维护一个64位的状态，由四个64位字（v0, v1, v2, v3）组成。 初始化 ：算法使用一个128位的密钥K（分为两个64位字k0和k1）和两个64位的常量（c0=0x736f6d6570736575, c1=0x646f72616e646f6d, c2=0x6c7967656e657261, c3=0x7465646279746573）来初始化状态。 v0 = c0 ⊕ k0 v1 = c1 ⊕ k1 v2 = c0 ⊕ k0 v3 = c1 ⊕ k1 这里，c2和c3稍后在处理消息结束时使用。 轮函数SipRound详解 SipRound是算法的核心变换，它对四个状态字（v0, v1, v2, v3）进行一系列ARX操作。其设计目标是实现良好的扩散和非线性。让我们一步一步拆解： 假设当前状态为 (v0, v1, v2, v3)。 步骤1：对 v0 和 v1 的运算 加法（A） ： v0 = v0 + v1 将 v0 和 v1 作为无符号64位整数相加，结果对 2^64 取模（即自然的溢出进位被丢弃）。 循环左移（R） ： v1 = v1 <<< 13 将 v1 向左循环移动13位。 <<< 表示循环左移。 异或（X） ： v1 = v1 ⊕ v0 将移位后的 v1 与新的 v0 进行按位异或。 再次循环左移 ： v0 = v0 <<< 32 将 v0 向左循环移动32位。 步骤2：对 v2 和 v3 的运算（对称操作） 5. 加法 ： v2 = v2 + v3 6. 循环左移 ： v3 = v3 <<< 16 7. 异或 ： v3 = v3 ⊕ v2 8. 再次循环左移 ： v2 = v2 <<< 32 步骤3：交叉混合 9. 交叉加法 ： v0 = v0 + v3 * 将步骤1处理过的 v0 与步骤2处理过的 v3 相加。 10. 循环左移 ： v3 = v3 <<< 21 11. 异或 ： v3 = v3 ⊕ v0 12. 交叉加法 ： v2 = v2 + v1 * 将步骤2处理过的 v2 与步骤1处理过的 v1 相加。 13. 循环左移 ： v1 = v1 <<< 17 14. 异或 ： v1 = v1 ⊕ v2 15. 最后移位 ： v2 = v2 <<< 32 至此，一轮SipRound完成。它通过加法引入非线性（因为进位传播是非线性的），通过循环移位实现比特位的扩散，通过异或实现快速的混合。整个操作非常高效，在现代CPU上只需少量指令。 消息压缩过程 SipHash将任意长度的消息M压缩成一个64位的哈希值。这个过程可以看作一个海绵结构的简化版，分为两个主要阶段： 吸收（Compression） 和 挤压（Finalization） 。 阶段一：吸收（消息处理） 消息分组 ：将消息M填充并分割成多个8字节（64位）的分组 m_ i。填充规则是在消息末尾添加一个字节0x80，然后填充零直到总长度（包括原始消息、0x80和填充零）是8字节的倍数，最后8字节存储原始消息长度的低64位（小端序）。 循环处理每个分组 ：对于每个消息分组 m_ i： a. 注入 ：将分组异或到状态的一个字上。具体是 v3 = v3 ⊕ m_i 。 b. 应用 c 轮 SipRound ：连续执行 c 次 SipRound 函数。 c 是一个安全参数，通常取2（即SipHash-2-4中的第一个数字）。 c. 再次注入 ：将同一个分组再次异或到另一个状态字上。具体是 v0 = v0 ⊕ m_i 。 这个过程确保了每个消息分组都与状态进行了两次混合（前一次和后一次），并经过多轮SipRound的充分混淆。 阶段二：挤压（最终化） 在处理完所有消息分组后，进入最终化阶段，输出最终的哈希值。 终态标记 ：将状态字 v2 与一个常量进行异或，作为处理结束的标记： v2 = v2 ⊕ 0xff 。 应用 d 轮 SipRound ：连续执行 d 次 SipRound 函数。 d 是另一个安全参数，通常取4（即SipHash-2-4中的第二个数字）。 最终混合 ： v0 = v0 ⊕ v1 v0 = v0 ⊕ v2 v0 = v0 ⊕ v3 这一步将四个状态字的信息压缩到 v0 中。 输出 ：v0 的64位值就是最终的SipHash哈希值。 总结 SipHash的设计精髓在于其简洁而有效的轮函数SipRound，它通过ARX操作在极少的CPU周期内实现了良好的密码学强度。整个压缩过程通过“注入-混淆-再注入”的模式处理消息，最后经过一个带标记的最终混淆阶段产生输出。其安全性参数（ c 和 d ）可以调整以平衡速度和安全，SipHash-2-4是常用的快速安全配置。这使得SipHash非常适合需要高速、抗碰撞且能抵抗恶意输入的哈希场景，如编程语言中的哈希表（例如Python、Ruby从3.4/2.1版本开始使用SipHash防御哈希碰撞攻击）。