英语

中文（简体）

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。在这样做时，务必确保结构体没有填充空洞（padding holes）。最简单的方法是按大小降序排列结构体的成员，并使用 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 用户。

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

警告

切勿使用 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)];
}