论文 eprint.iacr.org/2012/351.pdf

代码位置 library/core/src/hash/sip.rs

SipHash 是一类针对短消息设计的伪随机函数族，相较于其他的哈希函数有在短消息上性能高、由于随机输入的存在难以构造哈希 dos 攻击的优点，是 rust 、python 的内置哈希函数实现。

实现

对于 SipHash-c-d 函数族，输入为一个 128 bit 的 k 和 可为空的输入 m，输出为一个 64 位长度的 SipHash-c-d(k,m)。其中 c 为 “compression rounds” 的次数， d 为 “finalization rounds” 的次数，“compression rounds” 和 “finalization rounds” 在之后中有说明具体的实现步骤。

初始化

首先使用 k0、k1 初始化四个值 v0 、v1 、v2 、v3，其中 k0、k1 为 输入 k 的 64 位的小端编码 (也就是两个 u64 值 k0 、k1 组成了 k )。

对于其中的常量，论文的选取解释为:

The initial state constant corresponds to the ASCII string “somepseudorandomlygeneratedbytes”, big-endian encoded.

论文中提出只需要满足 v0 和 v1 不同于 v2 和 v3 即可(也没分析为啥。。。)。

the only requirement was some asymmetry so that the initial v0 and v1 differ from v2 and v3.

Compression Round

在初始化状态后，将输入的字符串进行编码，将输入的字符串以每 8 字节作为一组以小端序编码成 64 位的数 mim_i ，最后不够的用 0 做填充，最后一个字节的值为输入的字符串长度 len mod 256len \bmod 256。具体来说，编码的过程如下图:

在将输入 s 编码成 m0,m1…m⌈(len+1)8⌉m_0,m_1 \dots m_{\lceil \frac{(len+1)}{8} \rceil} 后，对于每个 mim_i 执行以下步骤，迭代执行完所有的输入后，Compression Round 完成。

v3 ⊕=miSipRound(v0,v1,v2,v3) for c timesv0 ⊕=mi\begin{aligned} v_3 \ \oplus = m_i \\ SipRound(v_0,v_1,v_2,v_3)\ for\ c \ times \\ v_0 \ \oplus = m_i \end{aligned}

PS: 巨💩🤡的是论文中的 “For example, the one-byte input string m = ab is parsed as m0 = 01000000000000ab”。开始我还以为输入的是字符串 “ab”，没看到 “one-byte input”，导致编码输入 m 这块卡了一会。感觉写成 “0xab” 和 “0x01000000000000ab” 会好一点🤡。

Finalization Round

在所有的输入字节处理在 Compression Round 处理完成后，将 v2v_2 和常量 0xff0\mathrm{xff} (也是一个随机的非零值即可) 进行异或，再进行 d 轮 SipRound 之后，将 v0v_0 、v1v_1、v2v_2、v3v_3 进行异或和后得到最终的 64 位哈希值。

v2 ⊕=0xffSipRound(v0,v1,v2,v3) for d timesres=v0⊕v1⊕v2⊕v3\begin{aligned} v_2 \ \oplus = 0\mathrm{xff} \\ SipRound(v_0,v_1,v_2,v_3)\ for\ d \ times \\ res = v_0 \oplus v_1 \oplus v_2 \oplus v_3 \end{aligned}

SipRound

SipRound 的运算过程如下:

安全性分析

#todo

  • [ ] SipHash 安全性分析

🦻🦻🦻🦻🦻🦻🦻🦻