SipHash - 短输入 PRF¶

作者:: 由 Jason A. Donenfeld <jason@zx2c4.com> 编写

SipHash 是一种密码学安全的 PRF（伪随机函数）——一种键控哈希函数——它在短输入时表现非常出色，因此得名。它由密码学家 Daniel J. Bernstein 和 Jean-Philippe Aumasson 设计。它旨在替代以下一些用途：jhash、md5_transform、sha1_transform 等。

SipHash 接受一个填充有随机生成的数字的密钥，以及一个输入缓冲区或多个输入整数。它输出一个与随机数无法区分的整数。然后，您可以将该整数用作安全序列号、安全 cookie 的一部分，或者将其屏蔽以在哈希表中使用。

生成密钥¶

密钥应始终从密码学安全的随机数源生成，可以使用 get_random_bytes 或 get_random_once

siphash_key_t key;
get_random_bytes(&key, sizeof(key));

如果您不是从这里派生密钥，那您就做错了。

使用函数¶

该函数有两个变体，一个接受整数列表，另一个接受缓冲区

u64 siphash(const void *data, size_t len, const siphash_key_t *key);

和

u64 siphash_1u64(u64, const siphash_key_t *key);
u64 siphash_2u64(u64, u64, const siphash_key_t *key);
u64 siphash_3u64(u64, u64, u64, const siphash_key_t *key);
u64 siphash_4u64(u64, u64, u64, u64, const siphash_key_t *key);
u64 siphash_1u32(u32, const siphash_key_t *key);
u64 siphash_2u32(u32, u32, const siphash_key_t *key);
u64 siphash_3u32(u32, u32, u32, const siphash_key_t *key);
u64 siphash_4u32(u32, u32, u32, u32, const siphash_key_t *key);

如果您将长度恒定的内容传递给通用 siphash 函数，它将在编译时进行常量折叠，并自动选择其中一个优化函数。

哈希表键函数用法

struct some_hashtable {
        DECLARE_HASHTABLE(hashtable, 8);
        siphash_key_t key;
};

void init_hashtable(struct some_hashtable *table)
{
        get_random_bytes(&table->key, sizeof(table->key));
}

static inline hlist_head *some_hashtable_bucket(struct some_hashtable *table, struct interesting_input *input)
{
        return &table->hashtable[siphash(input, sizeof(*input), &table->key) & (HASH_SIZE(table->hashtable) - 1)];
}

然后，您可以像往常一样迭代返回的哈希桶。

安全性¶

SipHash 具有非常高的安全裕度，其 128 位密钥。只要密钥保持秘密，攻击者就无法猜测函数的输出，即使能够观察到许多输出，因为 2^128 个输出是相当大的。

Linux 实现了 SipHash 的“2-4”变体。

结构体传递的陷阱¶

通常，XuY 函数不够大，您需要将预填充的结构体传递给 siphash。执行此操作时，务必始终确保该结构体没有填充空洞。最简单的方法是简单地按照大小降序排列结构体的成员，并使用 offsetofend() 而不是 sizeof() 来获取大小。出于性能考虑，如果可能，最好将结构体对齐到正确的边界。这是一个例子

const struct {
        struct in6_addr saddr;
        u32 counter;
        u16 dport;
} __aligned(SIPHASH_ALIGNMENT) combined = {
        .saddr = *(struct in6_addr *)saddr,
        .counter = counter,
        .dport = dport
};
u64 h = siphash(&combined, offsetofend(typeof(combined), dport), &secret);

资源¶

如果您有兴趣了解更多信息，请阅读 SipHash 论文：https://131002.net/siphash/siphash.pdf

HalfSipHash - SipHash 的不安全的小表弟¶

作者:: 由 Jason A. Donenfeld <jason@zx2c4.com> 编写

万一 SipHash 的速度不够快，您或许可以考虑使用 HalfSipHash，这是一个可怕但可能很有用的选择。HalfSipHash 将 SipHash 的轮数从“2-4”减少到“1-3”，更可怕的是，使用容易被暴力破解的 64 位密钥（具有 32 位输出）而不是 SipHash 的 128 位密钥。但是，这可能会吸引一些高性能的 jhash 用户。

通过“hsiphash”函数系列提供 HalfSipHash 支持。

警告

永远不要使用 hsiphash 函数，除非作为哈希表键函数，并且只有当您可以绝对确定输出永远不会在内核之外传输时。这仅仅比 jhash 作为一种缓解哈希表泛洪拒绝服务攻击的方法稍微有用一些。

在 64 位内核上，hsiphash 函数实际上实现的是 SipHash-1-3，它是 SipHash 的一种减少轮数的变体，而不是 HalfSipHash-1-3。这是因为在 64 位代码中，SipHash-1-3 不比 HalfSipHash-1-3 慢，而且速度可能更快。请注意，这并不意味着在 64 位内核中 hsiphash 函数与 siphash 函数相同，或者它们是安全的；hsiphash 函数仍然使用安全性较低的减少轮数算法，并将其输出截断为 32 位。

生成 hsiphash 密钥¶

密钥应始终从密码学安全的随机数源生成，可以使用 get_random_bytes 或 get_random_once

hsiphash_key_t key;
get_random_bytes(&key, sizeof(key));

如果您不是从这里派生密钥，那您就做错了。

使用 hsiphash 函数¶

该函数有两个变体，一个接受整数列表，另一个接受缓冲区

u32 hsiphash(const void *data, size_t len, const hsiphash_key_t *key);

和

u32 hsiphash_1u32(u32, const hsiphash_key_t *key);
u32 hsiphash_2u32(u32, u32, const hsiphash_key_t *key);
u32 hsiphash_3u32(u32, u32, u32, const hsiphash_key_t *key);
u32 hsiphash_4u32(u32, u32, u32, u32, const hsiphash_key_t *key);

如果您将长度恒定的内容传递给通用 hsiphash 函数，它将在编译时进行常量折叠，并自动选择其中一个优化函数。

哈希表键函数用法¶

struct some_hashtable {
        DECLARE_HASHTABLE(hashtable, 8);
        hsiphash_key_t key;
};

void init_hashtable(struct some_hashtable *table)
{
        get_random_bytes(&table->key, sizeof(table->key));
}

static inline hlist_head *some_hashtable_bucket(struct some_hashtable *table, struct interesting_input *input)
{
        return &table->hashtable[hsiphash(input, sizeof(*input), &table->key) & (HASH_SIZE(table->hashtable) - 1)];
}