SipHash

SipHash [sip] is a cryptographic pseudo random function with a 128-bit seed and 64-bit output. It was designed by Jean-Philippe Aumasson and Daniel J. Bernstein as a fast and secure keyed hash algorithm. It's used by Ruby, Perl, OpenDNS, Rust, Redis, FreeBSD and more. The C reference implementation has been released under CC0 license (public domain).

Quote from SipHash's site:

SipHash is a family of pseudorandom functions (a.k.a. keyed hash functions) optimized for speed on short messages. Target applications include network traffic authentication and defense against hash-flooding DoS attacks.

siphash24 is the recommend variant with best performance. It uses 2 rounds per message block and 4 finalization rounds. Besides the reference implementation several other implementations are available. Some are single-shot functions, others use a Merkle–Damgård construction-like approach with init, update and finalize functions. Marek Majkowski C implementation csiphash [csiphash] defines the prototype of the function. (Note: k is split up into two uint64_t):

uint64_t siphash24(const void *src, unsigned long src_sz, const char k[16])

SipHash requires a 64-bit data type and is not compatible with pure C89 platforms.

MurmurHash

MurmurHash [murmur] is a family of non-cryptographic keyed hash function developed by Austin Appleby. Murmur3 is the latest and fast variant of MurmurHash. The C++ reference implementation has been released into public domain. It features 32- or 128-bit output with a 32-bit seed. (Note: The out parameter is a buffer with either 1 or 4 bytes.)

Murmur3's function prototypes are:

void MurmurHash3_x86_32(const void *key, int len, uint32_t seed, void *out)

void MurmurHash3_x86_128(const void *key, int len, uint32_t seed, void *out)

void MurmurHash3_x64_128(const void *key, int len, uint32_t seed, void *out)

The 128-bit variants requires a 64-bit data type and are not compatible with pure C89 platforms. The 32-bit variant is fully C89-compatible.

Aumasson, Bernstein and Boßlet have shown [sip] [ocert-2012-001] that Murmur3 is not resilient against hash collision attacks. Therefore Murmur3 can no longer be considered as secure algorithm. It still may be an alternative is hash collision attacks are of no concern.

CityHash

CityHash [city] is a family of non-cryptographic hash function developed by Geoff Pike and Jyrki Alakuijala for Google. The C++ reference implementation has been released under MIT license. The algorithm is partly based on MurmurHash and claims to be faster. It supports 64- and 128-bit output with a 128-bit seed as well as 32-bit output without seed.

The relevant function prototype for 64-bit CityHash with 128-bit seed is:

uint64 CityHash64WithSeeds(const char *buf, size_t len, uint64 seed0,
                           uint64 seed1)

CityHash also offers SSE 4.2 optimizations with CRC32 intrinsic for long inputs. All variants except CityHash32 require 64-bit data types. CityHash32 uses only 32-bit data types but it doesn't support seeding.

Like MurmurHash Aumasson, Bernstein and Boßlet have shown [sip] a similar weakness in CityHash.

DJBX33A

DJBX33A is a very simple multiplication and addition algorithm by Daniel J. Bernstein. It is fast and has low setup costs but it's not secure against hash collision attacks. Its properties make it a viable choice for small string hashing optimization.

Other

Crypto algorithms such as HMAC, MD5, SHA-1 or SHA-2 are too slow and have high setup and finalization costs. For these reasons they are not considered fit for this purpose. Modern AMD and Intel CPUs have AES-NI (AES instruction set) [aes-ni] to speed up AES encryption. CMAC with AES-NI might be a viable option but it's probably too slow for daily operation. (testing required)

Conclusion

SipHash provides the best combination of speed and security. Developers of other prominent projects have came to the same conclusion.

hash secret

The _Py_HashSecret_t type of Python 2.6 to 3.3 has two members with either 32- or 64-bit length each. SipHash requires two 64-bit unsigned integers as keys. The typedef will be changed to an union with a guaranteed size of 24 bytes on all architectures. The union provides a 128 bit random key for SipHash24 and FNV as well as an additional value of 64 bit for the optional small string optimization and pyexpat seed. The additional 64 bit seed ensures that pyexpat or small string optimization cannot reveal bits of the SipHash24 seed.

memory layout on 64 bit systems:

cccccccc cccccccc cccccccc  uc -- unsigned char[24]
pppppppp ssssssss ........  fnv -- two Py_hash_t
k0k0k0k0 k1k1k1k1 ........  siphash -- two PY_UINT64_T
........ ........ ssssssss  djbx33a -- 16 bytes padding + one Py_hash_t
........ ........ eeeeeeee  pyexpat XML hash salt

memory layout on 32 bit systems:

cccccccc cccccccc cccccccc  uc -- unsigned char[24]
ppppssss ........ ........  fnv -- two Py_hash_t
k0k0k0k0 k1k1k1k1 ........  siphash -- two PY_UINT64_T (if available)
........ ........ ssss....  djbx33a -- 16 bytes padding + one Py_hash_t
........ ........ eeee....  pyexpat XML hash salt

new type definition:

typedef union {
    /* ensure 24 bytes */
    unsigned char uc[24];
    /* two Py_hash_t for FNV */
    struct {
        Py_hash_t prefix;
        Py_hash_t suffix;
    } fnv;
#ifdef PY_UINT64_T
    /* two uint64 for SipHash24 */
    struct {
        PY_UINT64_T k0;
        PY_UINT64_T k1;
    } siphash;
#endif
    /* a different (!) Py_hash_t for small string optimization */
    struct {
        unsigned char padding[16];
        Py_hash_t suffix;
    } djbx33a;
    struct {
        unsigned char padding[16];
        Py_hash_t hashsalt;
    } expat;
} _Py_HashSecret_t;
PyAPI_DATA(_Py_HashSecret_t) _Py_HashSecret;

_Py_HashSecret_t is initialized in Python/random.c:_PyRandom_Init() exactly once at startup.

hash function definition

Implementation:

typedef struct {
    /* function pointer to hash function, e.g. fnv or siphash24 */
    Py_hash_t (*const hash)(const void *, Py_ssize_t);
    const char *name;       /* name of the hash algorithm and variant */
    const int hash_bits;    /* internal size of hash value */
    const int seed_bits;    /* size of seed input */
} PyHash_FuncDef;

PyAPI_FUNC(PyHash_FuncDef*) PyHash_GetFuncDef(void);

autoconf

A new test is added to the configure script. The test sets HAVE_ALIGNED_REQUIRED, when it detects a platform, that requires aligned memory access for integers. Must current platforms such as X86, X86_64 and modern ARM don't need aligned data.

A new option --with-hash-algorithm enables the user to select a hash algorithm in the configure step.

hash function selection

The value of the macro Py_HASH_ALGORITHM defines which hash algorithm is used internally. It may be set to any of the three values Py_HASH_SIPHASH24, Py_HASH_FNV or Py_HASH_EXTERNAL. If Py_HASH_ALGORITHM is not defined at all, then the best available algorithm is selected. On platforms wich don't require aligned memory access (HAVE_ALIGNED_REQUIRED not defined) and an unsigned 64 bit integer type PY_UINT64_T, SipHash24 is used. On strict C89 platforms without a 64 bit data type, or architectures such as SPARC, FNV is selected as fallback. A hash algorithm can be selected with an autoconf option, for example ./configure --with-hash-algorithm=fnv.

The value Py_HASH_EXTERNAL allows 3rd parties to provide their own implementation at compile time.

Implementation:

#if Py_HASH_ALGORITHM == Py_HASH_EXTERNAL
extern PyHash_FuncDef PyHash_Func;
#elif Py_HASH_ALGORITHM == Py_HASH_SIPHASH24
static PyHash_FuncDef PyHash_Func = {siphash24, "siphash24", 64, 128};
#elif Py_HASH_ALGORITHM == Py_HASH_FNV
static PyHash_FuncDef PyHash_Func = {fnv, "fnv", 8 * sizeof(Py_hash_t),
                                     16 * sizeof(Py_hash_t)};
#endif

sys module

The sys module already has a hash_info struct sequence. More fields are added to the object to reflect the active hash algorithm and its properties.

sys.hash_info(width=64,
              modulus=2305843009213693951,
              inf=314159,
              nan=0,
              imag=1000003,
              # new fields:
              algorithm='siphash24',
              hash_bits=64,
              seed_bits=128,
              cutoff=0)

_Py_HashBytes() (Objects/object.c)

_Py_HashBytes is an internal helper function that provides the hashing code for bytes, memoryview and datetime classes. It currently implements FNV for unsigned char *.

The function is moved to Python/pyhash.c and modified to use the hash function through PyHash_Func.hash(). The function signature is altered to take a const void * as first argument. _Py_HashBytes also takes care of special cases: it maps zero length input to 0 and return value of -1 to -2.

bytes_hash() (Objects/bytesobject.c)

bytes_hash uses _Py_HashBytes to provide the tp_hash slot function for bytes objects. The function will continue to use _Py_HashBytes but withoht a type cast.

memory_hash() (Objects/memoryobject.c)

memory_hash provides the tp_hash slot function for read-only memory views if the original object is hashable, too. It's the only function that has to support hashing of unaligned memory segments in the future. The function will continue to use _Py_HashBytes but withoht a type cast.

unicode_hash() (Objects/unicodeobject.c)

unicode_hash provides the tp_hash slot function for unicode. Right now it implements the FNV algorithm three times for unsigned char*, Py_UCS2 and Py_UCS4. A reimplementation of the function must take care to use the correct length. Since the macro PyUnicode_GET_LENGTH returns the length of the unicode string and not its size in octets, the length must be multiplied with the size of the internal unicode kind:

if (PyUnicode_READY(u) == -1)
    return -1;
x = _Py_HashBytes(PyUnicode_DATA(u),
                  PyUnicode_GET_LENGTH(u) * PyUnicode_KIND(u));

generic_hash() (Modules/_datetimemodule.c)

generic_hash acts as a wrapper around _Py_HashBytes for the tp_hash slots of date, time and datetime types. timedelta objects are hashed by their state (days, seconds, microseconds) and tzinfo objects are not hashable. The data members of date, time and datetime types' struct are not void* aligned. This can easily by fixed with memcpy()ing four to ten bytes to an aligned buffer.

Hash value distribution

A good distribution of hash values is important for dict and set performance. Both SipHash24 and FNV take the length of the input into account, so that strings made up entirely of NULL bytes don't have the same hash value. The last bytes of the input tend to affect the least significant bits of the hash value, too. That attribute reduces the amount of hash collisions for strings with a common prefix.

Typical length

Serhiy Storchaka has shown in [issue16427] that a modified FNV implementation with 64 bits per cycle is able to process long strings several times faster than the current FNV implementation.

However according to statistics [issue19183] a typical Python program as well as the Python test suite have a hash ratio of about 50% small strings between 1 and 6 bytes. Only 5% of the strings are larger than 16 bytes.

Grand Unified Python Benchmark Suite

Initial tests with an experimental implementation and the Grand Unified Python Benchmark Suite have shown minimal deviations. The summarized total runtime of the benchmark is within 1% of the runtime of an unmodified Python 3.4 binary. The tests were run on an Intel i7-2860QM machine with a 64-bit Linux installation. The interpreter was compiled with GCC 4.7 for 64- and 32-bit.

More benchmarks will be conducted.

Pluggable

The first draft of this PEP made the hash algorithm pluggable at runtime. It supported multiple hash algorithms in one binary to give the user the possibility to select a hash algorithm at startup. The approach was considered an unnecessary complication by several core committers [pluggable]. Subsequent versions of the PEP aim for compile time configuration.

Non-aligned memory access

The implementation of SipHash24 were critized because it ignores the issue of non-aligned memory and therefore doesn't work on architectures that requires alignment of integer types. The PEP deliberately neglects this special case and doesn't support SipHash24 on such platforms. It's simply not considered worth the trouble until proven otherwise. All major platforms like X86, X86_64 and ARMv6+ can handle unaligned memory with minimal or even no speed impact. [alignmentmyth]

Almost every block is properly aligned anyway. At present bytes' and str's data are always aligned. Only memoryviews can point to unaligned blocks under rare circumstances. The PEP implementation is optimized and simplified for the common case.

ASCII str / bytes hash collision

Since the implementation of [pep-0393] bytes and ASCII text have the same memory layout. Because of this the new hashing API will keep the invariant:

hash("ascii string") == hash(b"ascii string")

for ASCII string and ASCII bytes. Equal hash values result in a hash collision and therefore cause a minor speed penalty for dicts and sets with mixed keys. The cause of the collision could be removed by e.g. subtracting 2 from the hash value of bytes. -2 because hash(b"") == 0 and -1 is reserved. The PEP doesn't change the hash value.