SipHash와 HalfSipHash 사용 지침

짧은 입력용 보안 PRF

SipHash는 secret key를 사용하는 암호학적으로 안전한 PRF(pseudorandom function), 즉 keyed hash function이다. 짧은 입력에서 성능이 좋아 이런 이름이 붙었으며 Daniel J. Bernstein과 Jean-Philippe Aumasson이 설계했다. 커널에서는 `jhash`, `md5_transform`, `sha1_transform`을 사용하던 일부 용도를 대체하도록 마련되었다.

무작위 수로 채운 secret key와 input buffer 또는 여러 정수를 입력하면 무작위 값과 구별할 수 없는 정수를 출력한다. 이 결과는 안전한 sequence number나 cookie의 일부로 사용할 수 있고, 필요한 bit만 mask하여 hash table index로도 사용할 수 있다.

===========================
SipHash - a short input PRF
===========================

:Author: Written by Jason A. Donenfeld <jason@zx2c4.com>

SipHash is a cryptographically secure PRF -- a keyed hash function -- that
performs very well for short inputs, hence the name. It was designed by
cryptographers Daniel J. Bernstein and Jean-Philippe Aumasson. It is intended
as a replacement for some uses of: `jhash`, `md5_transform`, `sha1_transform`,
and so forth.

SipHash takes a secret key filled with randomly generated numbers and either
an input buffer or several input integers. It spits out an integer that is
indistinguishable from random. You may then use that integer as part of secure
sequence numbers, secure cookies, or mask it off for use in a hash table.

SipHash 키 생성

Key는 반드시 암호학적으로 안전한 난수원에서 생성해야 한다. `siphash_key_t key`를 선언한 뒤 `get_random_bytes(&key, sizeof(key))`를 호출하거나, 같은 보안 수준을 제공하는 `get_random_once`를 사용한다. 문서는 이 경로가 아닌 방식으로 key를 유도하는 것은 잘못이라고 단호히 경고한다.

Generating a key
================

Keys should always be generated from a cryptographically secure source of
random numbers, either using get_random_bytes or get_random_once::

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

If you're not deriving your key from here, you're doing it wrong.

SipHash 함수와 hash table 예제

API는 buffer를 받는 범용 `siphash(const void *data, size_t len, const siphash_key_t *key)`와 정수 목록을 받는 최적화 함수군으로 나뉜다. 정수 함수는 1~4개의 `u64` 입력을 받는 `siphash_1u64`부터 `siphash_4u64`, 그리고 1~4개의 `u32` 입력을 받는 `siphash_1u32`부터 `siphash_4u32`까지 제공하며 모두 `u64`를 반환한다.

범용 `siphash`에 compile-time constant 길이의 데이터를 넘기면 compiler가 constant folding을 수행해 알맞은 최적화 함수를 자동으로 고른다. 호출자가 직접 길이별 함수를 선택하지 않아도 고정 길이 입력의 빠른 경로를 이용할 수 있다.

Hash table 예제는 `DECLARE_HASHTABLE(hashtable, 8)`과 `siphash_key_t key`를 같은 구조체에 둔다. 초기화 함수가 table key를 `get_random_bytes`로 채우고, bucket 함수는 입력 구조체 전체를 `siphash`한 뒤 `HASH_SIZE(table->hashtable) - 1`로 mask하여 bucket 주소를 반환한다. 호출자는 반환된 bucket을 일반적인 방식으로 순회한다.

Using the functions
===================

There are two variants of the function, one that takes a list of integers, and
one that takes a buffer::

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

And::

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

If you pass the generic siphash function something of a constant length, it
will constant fold at compile-time and automatically choose one of the
optimized functions.

Hashtable key function usage::

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

You may then iterate like usual over the returned hash bucket.

128-bit 키와 SipHash-2-4

SipHash는 128-bit key를 사용하므로 보안 여유가 매우 크다. Key가 비밀로 유지되는 한 공격자가 많은 출력을 관찰하더라도 함수 출력을 추측하는 것은 현실적으로 불가능하며, 문서는 `2^128` 규모가 충분히 크다는 점을 근거로 든다.

Linux가 구현하는 정식 SipHash 변형은 SipHash-2-4다. 뒤에서 설명하는 reduced-round `hsiphash` 함수와 이름이나 용도를 혼동해서는 안 된다.

Security
========

SipHash has a very high security margin, with its 128-bit key. So long as the
key is kept secret, it is impossible for an attacker to guess the outputs of
the function, even if being able to observe many outputs, since 2^128 outputs
is significant.

Linux implements the "2-4" variant of SipHash.

구조체 전달과 padding 함정

고정 개수 정수용 `XuY` 함수로 입력을 표현하기 어려우면 미리 채운 structure를 `siphash`에 넘길 수 있다. 이때 structure 안에 padding hole이 없어야 한다. 초기화되지 않은 padding을 hash 범위에 포함하면 결과가 불안정해지거나 민감한 잔여 byte를 의도치 않게 입력으로 사용할 수 있다.

가장 쉬운 예방책은 member를 크기 내림차순으로 배치하고, 입력 길이를 구할 때 `sizeof()` 대신 마지막 의미 있는 member까지 포함하는 `offsetofend()`를 사용하는 것이다. 성능을 위해 가능하면 structure를 적절한 boundary에 맞춰 정렬하는 것도 권장된다.

예제의 `combined` structure는 `struct in6_addr saddr`, `u32 counter`, `u16 dport` 순서로 배치하고 `__aligned(SIPHASH_ALIGNMENT)`를 적용한다. Hash 길이는 `offsetofend(typeof(combined), dport)`로 계산하여 마지막 field 뒤의 tail padding을 제외한 뒤 `siphash`에 전달한다.

Struct-passing Pitfalls
=======================

Often times the XuY functions will not be large enough, and instead you'll
want to pass a pre-filled struct to siphash. When doing this, it's important
to always ensure the struct has no padding holes. The easiest way to do this
is to simply arrange the members of the struct in descending order of size,
and to use offsetofend() instead of sizeof() for getting the size. For
performance reasons, if possible, it's probably a good thing to align the
struct to the right boundary. Here's an example::

        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 논문

더 자세한 설계와 분석은 SipHash 공식 논문 `https://131002.net/siphash/siphash.pdf`에서 확인할 수 있다. 이어지는 구분선 뒤에는 보안 수준을 낮춰 속도를 택한 HalfSipHash 계열의 별도 지침이 시작된다.

Resources
=========

Read the SipHash paper if you're interested in learning more:
https://131002.net/siphash/siphash.pdf

-------------------------------------------------------------------------------

HalfSipHash의 제한과 엄격한 경고

SipHash 성능이 요구를 충족하지 못하는 매우 제한적인 상황에는 HalfSipHash를 고려할 수 있지만, 문서는 이를 위험한 선택으로 규정한다. HalfSipHash는 round를 `2-4`에서 `1-3`으로 줄이고, SipHash의 128-bit key 대신 brute force가 쉬운 64-bit key를 사용하며 출력도 32 bit다. 고성능 `jhash` 사용자가 고려할 수 있는 정도의 절충안이며 API는 `hsiphash` 함수군으로 제공된다.

`hsiphash` 함수는 hash table key 함수 이외의 용도로 절대 사용해서는 안 된다. 그 경우에도 결과가 kernel 밖으로 전송되지 않는다고 확실히 보장할 수 있어야 한다. `jhash` 대비 의미 있는 유일한 목적은 hash table flooding denial-of-service 공격을 완화하는 것이다.

64-bit kernel에서 `hsiphash`는 HalfSipHash-1-3 대신 reduced-round SipHash-1-3을 구현한다. 64-bit code에서는 SipHash-1-3이 HalfSipHash-1-3보다 느리지 않고 오히려 빠를 수 있기 때문이다. 그러나 이것이 정식 `siphash` 함수와 같거나 안전하다는 뜻은 아니다. 여전히 round 수가 적은 약한 algorithm을 사용하고 결과를 32 bit로 truncate한다.

===============================================
HalfSipHash - SipHash's insecure younger cousin
===============================================

:Author: Written by Jason A. Donenfeld <jason@zx2c4.com>

On the off-chance that SipHash is not fast enough for your needs, you might be
able to justify using HalfSipHash, a terrifying but potentially useful
possibility. HalfSipHash cuts SipHash's rounds down from "2-4" to "1-3" and,
even scarier, uses an easily brute-forcable 64-bit key (with a 32-bit output)
instead of SipHash's 128-bit key. However, this may appeal to some
high-performance `jhash` users.

HalfSipHash support is provided through the "hsiphash" family of functions.

.. warning::
   Do not ever use the hsiphash functions except for as a hashtable key
   function, and only then when you can be absolutely certain that the outputs
   will never be transmitted out of the kernel. This is only remotely useful
   over `jhash` as a means of mitigating hashtable flooding denial of service
   attacks.

On 64-bit kernels, the hsiphash functions actually implement SipHash-1-3, a
reduced-round variant of SipHash, instead of HalfSipHash-1-3. This is because in
64-bit code, SipHash-1-3 is no slower than HalfSipHash-1-3, and can be faster.
Note, this does *not* mean that in 64-bit kernels the hsiphash functions are the
same as the siphash ones, or that they are secure; the hsiphash functions still
use a less secure reduced-round algorithm and truncate their outputs to 32
bits.

hsiphash 키 생성

`hsiphash` key 역시 반드시 암호학적으로 안전한 난수원에서 얻어야 한다. `hsiphash_key_t key`를 선언하고 `get_random_bytes(&key, sizeof(key))` 또는 `get_random_once`로 채운다. 알고리즘 자체의 보안 여유가 작다는 이유로 약한 key 생성이 허용되는 것은 아니며, 다른 방식으로 key를 유도하는 것은 잘못이다.

Generating a hsiphash key
=========================

Keys should always be generated from a cryptographically secure source of
random numbers, either using get_random_bytes or get_random_once::

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

If you're not deriving your key from here, you're doing it wrong.

hsiphash 함수

범용 함수 `hsiphash(const void *data, size_t len, const hsiphash_key_t *key)`는 buffer를 받아 `u32`를 반환한다. 정수 입력용 함수는 `hsiphash_1u32`부터 `hsiphash_4u32`까지이며 1~4개의 `u32`와 key를 받아 모두 `u32`를 반환한다.

범용 `hsiphash`에 compile-time constant 길이의 값을 넘기면 compiler가 constant folding을 수행하고 최적화된 고정 입력 함수를 자동 선택한다.

Using the hsiphash functions
============================

There are two variants of the function, one that takes a list of integers, and
one that takes a buffer::

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

And::

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

If you pass the generic hsiphash function something of a constant length, it
will constant fold at compile-time and automatically choose one of the
optimized functions.

hsiphash hash table 예제

Hash table 예제는 `DECLARE_HASHTABLE(hashtable, 8)`과 `hsiphash_key_t key`를 구조체에 저장한다. 초기화할 때 key 전체를 `get_random_bytes`로 채운다.

Bucket 함수는 `hsiphash(input, sizeof(*input), &table->key)` 결과를 `HASH_SIZE(table->hashtable) - 1`로 mask하여 해당 `hlist_head` 주소를 반환한다. 이후 반환된 bucket은 일반 hash table과 같은 방식으로 순회한다. 이 패턴은 앞서 명시한 kernel 내부 hash table 용도에 한정된다.

Hashtable key function usage
============================

::

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

You may then iterate like usual over the returned hash bucket.

성능과 DoS 저항성 절충

`hsiphash()`는 `jhash()`보다 대략 세 배 느리다. 그러나 많은 교체 사례에서는 hash table lookup 자체가 병목이 아니므로 실제 문제가 되지 않는다. 일반적으로 이 비용은 `hsiphash()`가 제공하는 보안성과 hash table flooding DoS 저항성을 얻기 위해 감수할 만한 절충이다.

Performance
===========

hsiphash() is roughly 3 times slower than jhash(). For many replacements, this
will not be a problem, as the hashtable lookup isn't the bottleneck. And in
general, this is probably a good sacrifice to make for the security and DoS
resistance of hsiphash().