英語

中文（簡體）

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)];
}