14d3beaa0SMauro Carvalho Chehab=========================== 24d3beaa0SMauro Carvalho ChehabSipHash - a short input PRF 34d3beaa0SMauro Carvalho Chehab=========================== 44d3beaa0SMauro Carvalho Chehab 54d3beaa0SMauro Carvalho Chehab:Author: Written by Jason A. Donenfeld <jason@zx2c4.com> 64d3beaa0SMauro Carvalho Chehab 74d3beaa0SMauro Carvalho ChehabSipHash is a cryptographically secure PRF -- a keyed hash function -- that 84d3beaa0SMauro Carvalho Chehabperforms very well for short inputs, hence the name. It was designed by 94d3beaa0SMauro Carvalho Chehabcryptographers Daniel J. Bernstein and Jean-Philippe Aumasson. It is intended 106b0b0fa2SEric Biggersas a replacement for some uses of: `jhash`, `md5_transform`, `sha1_transform`, 114d3beaa0SMauro Carvalho Chehaband so forth. 124d3beaa0SMauro Carvalho Chehab 134d3beaa0SMauro Carvalho ChehabSipHash takes a secret key filled with randomly generated numbers and either 144d3beaa0SMauro Carvalho Chehaban input buffer or several input integers. It spits out an integer that is 154d3beaa0SMauro Carvalho Chehabindistinguishable from random. You may then use that integer as part of secure 164d3beaa0SMauro Carvalho Chehabsequence numbers, secure cookies, or mask it off for use in a hash table. 174d3beaa0SMauro Carvalho Chehab 184d3beaa0SMauro Carvalho ChehabGenerating a key 194d3beaa0SMauro Carvalho Chehab================ 204d3beaa0SMauro Carvalho Chehab 214d3beaa0SMauro Carvalho ChehabKeys should always be generated from a cryptographically secure source of 224d3beaa0SMauro Carvalho Chehabrandom numbers, either using get_random_bytes or get_random_once:: 234d3beaa0SMauro Carvalho Chehab 244d3beaa0SMauro Carvalho Chehab siphash_key_t key; 254d3beaa0SMauro Carvalho Chehab get_random_bytes(&key, sizeof(key)); 264d3beaa0SMauro Carvalho Chehab 274d3beaa0SMauro Carvalho ChehabIf you're not deriving your key from here, you're doing it wrong. 284d3beaa0SMauro Carvalho Chehab 294d3beaa0SMauro Carvalho ChehabUsing the functions 304d3beaa0SMauro Carvalho Chehab=================== 314d3beaa0SMauro Carvalho Chehab 324d3beaa0SMauro Carvalho ChehabThere are two variants of the function, one that takes a list of integers, and 334d3beaa0SMauro Carvalho Chehabone that takes a buffer:: 344d3beaa0SMauro Carvalho Chehab 354d3beaa0SMauro Carvalho Chehab u64 siphash(const void *data, size_t len, const siphash_key_t *key); 364d3beaa0SMauro Carvalho Chehab 374d3beaa0SMauro Carvalho ChehabAnd:: 384d3beaa0SMauro Carvalho Chehab 394d3beaa0SMauro Carvalho Chehab u64 siphash_1u64(u64, const siphash_key_t *key); 404d3beaa0SMauro Carvalho Chehab u64 siphash_2u64(u64, u64, const siphash_key_t *key); 414d3beaa0SMauro Carvalho Chehab u64 siphash_3u64(u64, u64, u64, const siphash_key_t *key); 424d3beaa0SMauro Carvalho Chehab u64 siphash_4u64(u64, u64, u64, u64, const siphash_key_t *key); 434d3beaa0SMauro Carvalho Chehab u64 siphash_1u32(u32, const siphash_key_t *key); 444d3beaa0SMauro Carvalho Chehab u64 siphash_2u32(u32, u32, const siphash_key_t *key); 454d3beaa0SMauro Carvalho Chehab u64 siphash_3u32(u32, u32, u32, const siphash_key_t *key); 464d3beaa0SMauro Carvalho Chehab u64 siphash_4u32(u32, u32, u32, u32, const siphash_key_t *key); 474d3beaa0SMauro Carvalho Chehab 484d3beaa0SMauro Carvalho ChehabIf you pass the generic siphash function something of a constant length, it 494d3beaa0SMauro Carvalho Chehabwill constant fold at compile-time and automatically choose one of the 504d3beaa0SMauro Carvalho Chehaboptimized functions. 514d3beaa0SMauro Carvalho Chehab 524d3beaa0SMauro Carvalho ChehabHashtable key function usage:: 534d3beaa0SMauro Carvalho Chehab 544d3beaa0SMauro Carvalho Chehab struct some_hashtable { 554d3beaa0SMauro Carvalho Chehab DECLARE_HASHTABLE(hashtable, 8); 564d3beaa0SMauro Carvalho Chehab siphash_key_t key; 574d3beaa0SMauro Carvalho Chehab }; 584d3beaa0SMauro Carvalho Chehab 594d3beaa0SMauro Carvalho Chehab void init_hashtable(struct some_hashtable *table) 604d3beaa0SMauro Carvalho Chehab { 614d3beaa0SMauro Carvalho Chehab get_random_bytes(&table->key, sizeof(table->key)); 624d3beaa0SMauro Carvalho Chehab } 634d3beaa0SMauro Carvalho Chehab 644d3beaa0SMauro Carvalho Chehab static inline hlist_head *some_hashtable_bucket(struct some_hashtable *table, struct interesting_input *input) 654d3beaa0SMauro Carvalho Chehab { 664d3beaa0SMauro Carvalho Chehab return &table->hashtable[siphash(input, sizeof(*input), &table->key) & (HASH_SIZE(table->hashtable) - 1)]; 674d3beaa0SMauro Carvalho Chehab } 684d3beaa0SMauro Carvalho Chehab 694d3beaa0SMauro Carvalho ChehabYou may then iterate like usual over the returned hash bucket. 704d3beaa0SMauro Carvalho Chehab 714d3beaa0SMauro Carvalho ChehabSecurity 724d3beaa0SMauro Carvalho Chehab======== 734d3beaa0SMauro Carvalho Chehab 744d3beaa0SMauro Carvalho ChehabSipHash has a very high security margin, with its 128-bit key. So long as the 754d3beaa0SMauro Carvalho Chehabkey is kept secret, it is impossible for an attacker to guess the outputs of 764d3beaa0SMauro Carvalho Chehabthe function, even if being able to observe many outputs, since 2^128 outputs 774d3beaa0SMauro Carvalho Chehabis significant. 784d3beaa0SMauro Carvalho Chehab 794d3beaa0SMauro Carvalho ChehabLinux implements the "2-4" variant of SipHash. 804d3beaa0SMauro Carvalho Chehab 814d3beaa0SMauro Carvalho ChehabStruct-passing Pitfalls 824d3beaa0SMauro Carvalho Chehab======================= 834d3beaa0SMauro Carvalho Chehab 844d3beaa0SMauro Carvalho ChehabOften times the XuY functions will not be large enough, and instead you'll 854d3beaa0SMauro Carvalho Chehabwant to pass a pre-filled struct to siphash. When doing this, it's important 864d3beaa0SMauro Carvalho Chehabto always ensure the struct has no padding holes. The easiest way to do this 874d3beaa0SMauro Carvalho Chehabis to simply arrange the members of the struct in descending order of size, 88*12fe4343SDov Murikand to use offsetofend() instead of sizeof() for getting the size. For 894d3beaa0SMauro Carvalho Chehabperformance reasons, if possible, it's probably a good thing to align the 904d3beaa0SMauro Carvalho Chehabstruct to the right boundary. Here's an example:: 914d3beaa0SMauro Carvalho Chehab 924d3beaa0SMauro Carvalho Chehab const struct { 934d3beaa0SMauro Carvalho Chehab struct in6_addr saddr; 944d3beaa0SMauro Carvalho Chehab u32 counter; 954d3beaa0SMauro Carvalho Chehab u16 dport; 964d3beaa0SMauro Carvalho Chehab } __aligned(SIPHASH_ALIGNMENT) combined = { 974d3beaa0SMauro Carvalho Chehab .saddr = *(struct in6_addr *)saddr, 984d3beaa0SMauro Carvalho Chehab .counter = counter, 994d3beaa0SMauro Carvalho Chehab .dport = dport 1004d3beaa0SMauro Carvalho Chehab }; 1014d3beaa0SMauro Carvalho Chehab u64 h = siphash(&combined, offsetofend(typeof(combined), dport), &secret); 1024d3beaa0SMauro Carvalho Chehab 1034d3beaa0SMauro Carvalho ChehabResources 1044d3beaa0SMauro Carvalho Chehab========= 1054d3beaa0SMauro Carvalho Chehab 1064d3beaa0SMauro Carvalho ChehabRead the SipHash paper if you're interested in learning more: 1074d3beaa0SMauro Carvalho Chehabhttps://131002.net/siphash/siphash.pdf 1084d3beaa0SMauro Carvalho Chehab 1094d3beaa0SMauro Carvalho Chehab------------------------------------------------------------------------------- 1104d3beaa0SMauro Carvalho Chehab 1114d3beaa0SMauro Carvalho Chehab=============================================== 1124d3beaa0SMauro Carvalho ChehabHalfSipHash - SipHash's insecure younger cousin 1134d3beaa0SMauro Carvalho Chehab=============================================== 1144d3beaa0SMauro Carvalho Chehab 1154d3beaa0SMauro Carvalho Chehab:Author: Written by Jason A. Donenfeld <jason@zx2c4.com> 1164d3beaa0SMauro Carvalho Chehab 1174d3beaa0SMauro Carvalho ChehabOn the off-chance that SipHash is not fast enough for your needs, you might be 1184d3beaa0SMauro Carvalho Chehabable to justify using HalfSipHash, a terrifying but potentially useful 1194d3beaa0SMauro Carvalho Chehabpossibility. HalfSipHash cuts SipHash's rounds down from "2-4" to "1-3" and, 1204d3beaa0SMauro Carvalho Chehabeven scarier, uses an easily brute-forcable 64-bit key (with a 32-bit output) 1214d3beaa0SMauro Carvalho Chehabinstead of SipHash's 128-bit key. However, this may appeal to some 1224d3beaa0SMauro Carvalho Chehabhigh-performance `jhash` users. 1234d3beaa0SMauro Carvalho Chehab 1245a7e470eSEric BiggersHalfSipHash support is provided through the "hsiphash" family of functions. 1255a7e470eSEric Biggers 126ec862155SBagas Sanjaya.. warning:: 1275a7e470eSEric Biggers Do not ever use the hsiphash functions except for as a hashtable key 1285a7e470eSEric Biggers function, and only then when you can be absolutely certain that the outputs 1295a7e470eSEric Biggers will never be transmitted out of the kernel. This is only remotely useful 1305a7e470eSEric Biggers over `jhash` as a means of mitigating hashtable flooding denial of service 131ec862155SBagas Sanjaya attacks. 1324d3beaa0SMauro Carvalho Chehab 1335a7e470eSEric BiggersOn 64-bit kernels, the hsiphash functions actually implement SipHash-1-3, a 1345a7e470eSEric Biggersreduced-round variant of SipHash, instead of HalfSipHash-1-3. This is because in 1355a7e470eSEric Biggers64-bit code, SipHash-1-3 is no slower than HalfSipHash-1-3, and can be faster. 1365a7e470eSEric BiggersNote, this does *not* mean that in 64-bit kernels the hsiphash functions are the 1375a7e470eSEric Biggerssame as the siphash ones, or that they are secure; the hsiphash functions still 1385a7e470eSEric Biggersuse a less secure reduced-round algorithm and truncate their outputs to 32 1395a7e470eSEric Biggersbits. 1405a7e470eSEric Biggers 1415a7e470eSEric BiggersGenerating a hsiphash key 1425a7e470eSEric Biggers========================= 1434d3beaa0SMauro Carvalho Chehab 1444d3beaa0SMauro Carvalho ChehabKeys should always be generated from a cryptographically secure source of 1452fbfeb4fSBagas Sanjayarandom numbers, either using get_random_bytes or get_random_once:: 1464d3beaa0SMauro Carvalho Chehab 1474d3beaa0SMauro Carvalho Chehab hsiphash_key_t key; 1484d3beaa0SMauro Carvalho Chehab get_random_bytes(&key, sizeof(key)); 1494d3beaa0SMauro Carvalho Chehab 1504d3beaa0SMauro Carvalho ChehabIf you're not deriving your key from here, you're doing it wrong. 1514d3beaa0SMauro Carvalho Chehab 1525a7e470eSEric BiggersUsing the hsiphash functions 1535a7e470eSEric Biggers============================ 1544d3beaa0SMauro Carvalho Chehab 1554d3beaa0SMauro Carvalho ChehabThere are two variants of the function, one that takes a list of integers, and 1564d3beaa0SMauro Carvalho Chehabone that takes a buffer:: 1574d3beaa0SMauro Carvalho Chehab 1584d3beaa0SMauro Carvalho Chehab u32 hsiphash(const void *data, size_t len, const hsiphash_key_t *key); 1594d3beaa0SMauro Carvalho Chehab 1604d3beaa0SMauro Carvalho ChehabAnd:: 1614d3beaa0SMauro Carvalho Chehab 1624d3beaa0SMauro Carvalho Chehab u32 hsiphash_1u32(u32, const hsiphash_key_t *key); 1634d3beaa0SMauro Carvalho Chehab u32 hsiphash_2u32(u32, u32, const hsiphash_key_t *key); 1644d3beaa0SMauro Carvalho Chehab u32 hsiphash_3u32(u32, u32, u32, const hsiphash_key_t *key); 1654d3beaa0SMauro Carvalho Chehab u32 hsiphash_4u32(u32, u32, u32, u32, const hsiphash_key_t *key); 1664d3beaa0SMauro Carvalho Chehab 1674d3beaa0SMauro Carvalho ChehabIf you pass the generic hsiphash function something of a constant length, it 1684d3beaa0SMauro Carvalho Chehabwill constant fold at compile-time and automatically choose one of the 1694d3beaa0SMauro Carvalho Chehaboptimized functions. 1704d3beaa0SMauro Carvalho Chehab 1714d3beaa0SMauro Carvalho ChehabHashtable key function usage 1724d3beaa0SMauro Carvalho Chehab============================ 1734d3beaa0SMauro Carvalho Chehab 1744d3beaa0SMauro Carvalho Chehab:: 1754d3beaa0SMauro Carvalho Chehab 1764d3beaa0SMauro Carvalho Chehab struct some_hashtable { 1774d3beaa0SMauro Carvalho Chehab DECLARE_HASHTABLE(hashtable, 8); 1784d3beaa0SMauro Carvalho Chehab hsiphash_key_t key; 1794d3beaa0SMauro Carvalho Chehab }; 1804d3beaa0SMauro Carvalho Chehab 1814d3beaa0SMauro Carvalho Chehab void init_hashtable(struct some_hashtable *table) 1824d3beaa0SMauro Carvalho Chehab { 1834d3beaa0SMauro Carvalho Chehab get_random_bytes(&table->key, sizeof(table->key)); 1844d3beaa0SMauro Carvalho Chehab } 1854d3beaa0SMauro Carvalho Chehab 1864d3beaa0SMauro Carvalho Chehab static inline hlist_head *some_hashtable_bucket(struct some_hashtable *table, struct interesting_input *input) 1874d3beaa0SMauro Carvalho Chehab { 1884d3beaa0SMauro Carvalho Chehab return &table->hashtable[hsiphash(input, sizeof(*input), &table->key) & (HASH_SIZE(table->hashtable) - 1)]; 1894d3beaa0SMauro Carvalho Chehab } 1904d3beaa0SMauro Carvalho Chehab 1914d3beaa0SMauro Carvalho ChehabYou may then iterate like usual over the returned hash bucket. 1924d3beaa0SMauro Carvalho Chehab 1934d3beaa0SMauro Carvalho ChehabPerformance 1944d3beaa0SMauro Carvalho Chehab=========== 1954d3beaa0SMauro Carvalho Chehab 1965a7e470eSEric Biggershsiphash() is roughly 3 times slower than jhash(). For many replacements, this 1975a7e470eSEric Biggerswill not be a problem, as the hashtable lookup isn't the bottleneck. And in 1985a7e470eSEric Biggersgeneral, this is probably a good sacrifice to make for the security and DoS 1995a7e470eSEric Biggersresistance of hsiphash(). 200