SHash

SHash是一种针对竞技编程用例优化的散列函数，据我所知，这是此类函数的第一个。

重要声明：尽管此readme将包括对该函数“安全性属性”的一些分析，但这些说法应仅基于实验性考虑。我不是一名专业密码学家。因此，在进一步通知之前，请避免在使用此函数时处理来自网络等不可信输入的hashmaps，尤其是在DOS（拒绝服务）攻击可能造成重大经济损失的情况下。

原理

现有的散列函数基本上可以分为两大类：非密码学散列函数（如FNV、FxHash），它们优先考虑速度而不是安全性；以及密码学散列函数（如SHA256、BLAKE3），它们优先考虑安全性而不是速度。

后一类中的大多数速度较慢，以至于在“子程序”算法中的一般使用变得有困难，这些算法与安全或密码学无关。已经有人尝试通过为非密码学函数配备种子来“弥合”这一差距，例如MurmurHash，但它广为人知地已被破解，在某种意义上，存在一种构造输入的方法，无论选择何种种子都会发生冲突。

作为对这些破解的回应，发明了SipHash——第一个旨在在散列函数中使用的足够快的密码学散列函数。许多编程语言，包括Rust，现在使用SipHash的变体作为它们散列函数的默认算法。

故事本可以到此结束...但“竞技编程”这一术语对使用要求具有独特的组合，它描述了一种竞赛风格，其中新颖的算法问题将在短时间内向参赛者展示，要求他们使用计算机程序解决。例如，包括Codeforces、AtCoder和Google Code Jam。

这类比赛通常对每个问题都设置了运行时间限制，只有当所有测试用例都在这个限制下运行时，提交才被视为正确。因此，确保算法足够快是非常重要的。然而，一般来说，超过时间限制没有额外加分，因为参赛者不需要花费大量时间在微优化上；重点是构建与输入大小具有良好的扩展性的算法，如用“大O”符号表示。

然而，仍然需要一定的安全性保障；一个过于简单的哈希函数（如身份哈希函数，或一些没有充分最终化的乘法哈希函数）可能会使易于定义的输入类别的低比特位表现出规律性，导致条目在哈希表桶之间分布不均。更具体的是，Codeforces特别允许参与者通过提交一个被认为会导致它失败的测试用例来“黑掉”其他参赛者的解决方案。因此，一个差的哈希函数可以直接通过这种方式被攻击。从密码学的角度来看，“黑客”可以被视为一个对手。

因此，我们可以使用SipHash并确信我们永远不会被“黑掉”，除非可能是某些密码学天才，他们应该立即停止参加此类比赛，转而写一篇论文描述他们如何找到一种方法来破坏SipHash的安全声明。然而，大多数情况下，时间限制足以接受这类解决方案。但是，这些时间限制是相当随意设定的——出题者预计要考虑各种编程语言在比赛时间中的“典型”实现速度来设定一个“公平”的时间限制，然而不同的出题者对这究竟意味着什么以及他们提供多少“空间”有不同的看法。此外，由于可能的实现、编程风格和语言的巨大可变性，有时一个问题会变得比通常更“紧凑”，这可能是由于出题者错误，也可能是由于出题者试图阻止高“大O”类解决方案通过，即使使用“快速”语言和常见的常数因子优化（如位集）。因此，当使用SipHash的试验提交（如此示例）在五秒内用了四秒时，就有理由担心。另一个例子是这个，它实际上没有达到时间限制。

然而，我们可以注意到，这些“黑掉”行为带来的对抗性威胁实际上比密码学家通常必须处理的威胁要弱得多。通常，密码学的实际应用需要保护可能价值数千美元，甚至数十亿美元的系统，因此我们必须假设对手愿意投入大量资源来击败密码系统。然而，一个典型的Codeforces参赛者试图“黑掉”时，必须尝试编写和运行一个程序，无论是在本地还是通过提交，以在比赛时间限制内生成对抗性测试用例，并且通常必须花费本可以用来解决其他问题的时间。因此，他们在计算资源和修改或定制生成测试用例所需的算法所需的时间上都有很大的限制。在更理论性的术语中，需要2⁴⁰次基本操作的密码破解被认为在大多数情况下是不可接受的，但通常会足够阻止这类对手。

那么，如果安全性要求有意义地较低，我们能否开发和使用一个比SipHash更快但仍然足够强大以应对此类用例的哈希函数呢？

设计

在降低的安全要求背景下，MurmurHash的破解是否有意义呢？为了回答这个问题，我们应该仔细考察这个破解究竟是什么，以及它所宣称的。经过一番思考，MurmurHash中的漏洞就变得几乎一目了然。它可以通过以下MurmurHash代码段来说明：

uint64_t k = *(uint64_t*)data;

k *= m; // const uint64_t m = 0xc6a4a7935bd1e995;
k ^= k >> r;
k *= m;

这里的问题是，我们从输入中提取原始位，并对其应用不依赖于种子的转换。因此，攻击者只需对输入应用这种转换的逆转换，就可以保留导致冲突的差异。换句话说，从攻击者的角度来看，这些都是浪费的周期。

因此，存在一个相当高效的“现成”算法，可以生成许多对MurmurHash不依赖种子的冲突。我目前不清楚这个算法是否可以有意义地“黑客”另一个参与者的解决方案——在此过程中存在几个其他实际障碍，例如，大多数问题对输入施加严格的约束，因此，例如，太长或不符合ASCII的输入可能不会被接受为测试用例。然而，在我看来，这已经足够令人担忧，需要考虑使用另一个算法。像FxHash或FNV这样的不承认种子的算法根本不在考虑范围内，因为很容易提前生成病理输入并将其作为测试用例提交。

另一个漏洞与速度有关，而不是安全性。对于每个“单词”（64位）的输入，MurmurHash通过三次乘法和一些xorshift来将其与当前状态结合。之后，它再进行两轮乘法+ xorshift，然后输出。额外的两轮被称为“最终化”。结果是，输入大小到速度的图有一个显著的“y截距”，这是一个常数，无论输入的大小如何都会添加到时间上。不幸的是，编程竞赛中的大多数问题只需要使用单个32位或64位整数作为键，所以最终化占到了哈希所需时间的很大一部分。请注意，SipHash也有这个“漏洞”，这在Rust中使用的SipHash-1-3变体的命名中很明显。这意味着“1轮用于压缩，3轮用于最终化”。这意味着来自编程竞赛问题的典型单个单词输入将应用四到五轮SipHash（由于长度填充而增加的额外一轮）。

这些最终化器被应用以提高最终输出的扩散和“雪崩特性”，从而使哈希桶之间的分布更接近理论上的随机性。大多数已发布的任意长度哈希函数都使用某种形式的最终化器。然而，由于在我们的用例中单字输入的高频率，当为它设计哈希函数时，我们理想上应该选择一个具有良好扩散的快速压缩函数，并且具有简单或没有最终化器，因此，当编译仅由单字键（如机器整数）组成的哈希表时，我们只需在汇编代码中内联该压缩函数。

有了这个前提，我们可以检查本存储库中SHash实现的核心设计，代码SHash::write_u64

pub struct SHash(u64, u128);
impl SHash {
    #[inline] fn write_u64(&mut self, i: u64) {
        let mut z = i.wrapping_add((self.1 >> 64) as u64);
        z ^= z.rotate_right(25) ^ z.rotate_right(47);
        z = z.wrapping_mul(0x9E6C63D0676A9A99).wrapping_add(self.0);
        z ^= z >> 23 ^ z >> 51;
        z = z.wrapping_mul(0x9E6D62D06F6A9A9B);
        z ^= z >> 23 ^ z >> 51;
        self.0 = z;
        self.1 = self.1.wrapping_mul(0xda942042e4dd58b5);
    }
}

SHash结构由两个变量组成。第一个变量（self.0）是64位的状态。第二个变量（self.1）是128位的抖动。

抖动的作用实际上可以从代码的最后一行中看出——这实际上是一个Lehmer64 RNG。此外，它从不受输入的影响。

第一行将抖动的高半部分（RNG的输出）加到输入位上。通过在应用任何变换之前将这个伪随机字符串与输入结合，我们避免了MurmurHash中的种子无关碰撞缺陷，或者至少希望它们难以找到。

z上的其余变换是基于NASAM的压缩函数。基本上，输入加抖动经过一些位混合后添加到状态（该状态已经被随机初始化），然后进行更多的混合。由于NASAM在统计随机性方面比MurmurHash3的最终化或Splitmix/Variant13有更好的特性（如NASAM主页上的测试程序所描述），因此消除了单独压缩和最终化步骤的需要，解决了第二个问题。

请注意，在单词键的情况下，RNG步进实际上被优化掉了。因此，编译后的哈希代码简化为NASAM的单轮，并添加两次随机种子值。

这个提交与前面的示例相同的问题。使用SHash而不是默认的SipHash-1-3使得这个问题在两秒钟内而不是四秒钟内运行时间得到解决。

安全和初步密码分析

如果我们知道种子，我们可以构建输入，使其与抖动中的伪随机字符串结合，从而使状态中的位为零，并保持为零以生成许多碰撞。然而，如果种子不同，抖动可能会生成一个完全不同的伪随机字符串，因此我们的碰撞不会在这个不同的种子上工作。

请注意，这个函数在输出暴露的情况下相当明显地不安全。这是因为所有NASAM操作都可以逆转，暴露的种子衍生差异足以解决。在竞技编程中这不是一个因素，因为哈希值通常不会暴露。即使如此，“黑客”也无法根据特定运行的哈希值或种子更改他们的输入。