Jump to content

SipHash: Difference between revisions

From Wikipedia, the free encyclopedia
Browse history interactively
← Previous edit
Content deleted Content added
VisualWikitext
m →Overview: Fixed grammar
Tags: Mobile edit Mobile app edit Android app edit App section source
 
(41 intermediate revisions by 22 users not shown)
Line 1: Line 1:
{{Short description|Hash functions}}
'''SipHash''' is an [[block cipher#ARX (add–rotate–xor)|add–rotate–xor]] (ARX) based family of [[pseudorandom function]]s created by [[Jean-Philippe Aumasson]] and [[Daniel J. Bernstein]] in 2012,<ref>{{cite book|last1=Dobraunig|first1=Christoph|last2=Mendel|first2=Florian|last3=Schläffer|first3=Martin|title=Differential Cryptanalysis of SipHash|journal=International Workshop on Selected Areas in Cryptography|date=29 November 2014|volume=8781|issue=2014|pages=165–182|doi=10.1007/978-3-319-13051-4_10|url=https://eprint.iacr.org/2014/722|access-date=28 February 2018|ref=dcmfsm-sac2014-siphash|series=Lecture Notes in Computer Science|isbn=978-3-319-13050-7}}</ref>{{rp|165}}<ref name="paper">{{cite web
'''SipHash''' is an [[block cipher#ARX (add–rotate–XOR)|add–rotate–xor]] (ARX) based family of [[pseudorandom function]]s created by Jean-Philippe Aumasson and [[Daniel J. Bernstein]] in 2012,<ref>{{cite book|last1=Dobraunig|first1=Christoph|last2=Mendel|first2=Florian|last3=Schläffer|first3=Martin|title=Selected Areas in Cryptography -- SAC 2014 |chapter=Differential Cryptanalysis of SipHash |date=29 November 2014|volume=8781|issue=2014|pages=165–182|doi=10.1007/978-3-319-13051-4_10|url=https://eprint.iacr.org/2014/722|access-date=28 February 2018|ref=dcmfsm-sac2014-siphash|series=Lecture Notes in Computer Science|isbn=978-3-319-13050-7}}</ref>{{rp|165}}<ref name="paper">{{cite journal
|url=https://eprint.iacr.org/2012/351
|url=https://eprint.iacr.org/2012/351
|title=SipHash: a fast short-input PRF
|title=SipHash: a fast short-input PRF
|author1=Jean-Philippe Aumasson
|author1=Jean-Philippe Aumasson
|author2=Daniel J. Bernstein |author-link2=Daniel J. Bernstein
|author2=Daniel J. Bernstein |journal=Cryptology ePrint Archive
|author-link2=Daniel J. Bernstein
|name-list-style=amp
|name-list-style=amp
|date=2012-09-18
|date=2012-09-18
}}</ref> in response to a spate of "hash flooding" [[denial-of-service attack]]s in late 2011.<ref>{{cite news
}}</ref> in response to a spate of [[Collision attack#Hash flooding|"hash flooding"]] [[denial-of-service attack]]s (HashDoS) in late 2011.<ref>{{cite news
|title=Hash Table Vulnerability Enables Wide-Scale DDoS Attacks
|title=Hash Table Vulnerability Enables Wide-Scale DDoS Attacks
|first=Mike
|first=Mike
Line 12: Line 14:
|date=2011-12-28
|date=2011-12-28
|journal=SecurityWeek
|journal=SecurityWeek
|url=http://www.securityweek.com/hash-table-collision-attacks-could-trigger-ddos-massive-scale
|url=https://www.securityweek.com/hash-table-collision-attacks-could-trigger-ddos-massive-scale/
}}</ref>
}}</ref>


Although designed for use as a [[hash function]] to ensure security, SipHash is fundamentally different from [[cryptographic hash functions]] like [[Secure Hash Algorithm|SHA]] in that it is only suitable as a [[message authentication code]]: a ''keyed'' hash function like [[HMAC]]. That is, SHA is designed so that it is difficult for an attacker to find two messages ''X'' and ''Y'' such that SHA(''X'') = SHA(''Y''), even though anyone may compute SHA(''X''). SipHash instead guarantees that, having seen ''X<sub>i</sub>'' and SipHash(''X<sub>i</sub>'', ''k''), an attacker who does not know the key ''k'' cannot find (any information about) ''k'' or SipHash(''Y'', ''k'') for any message ''Y'' ∉ {''X<sub>i</sub>''} which they have not seen before.
SipHash is designed as a [[non-cryptographic hash function]]. Although it can be used to ensure security, SipHash is fundamentally different from [[cryptographic hash functions]] like [[Secure Hash Algorithms]] (SHA) in that it is only suitable as a [[message authentication code]]: a ''keyed'' hash-function-like hash message authentication code ([[HMAC]]). That is, SHA is designed so that it is difficult for an attacker to find two messages ''X'' and ''Y'' such that SHA(''X'') = SHA(''Y''), even though anyone may compute SHA(''X''). SipHash instead guarantees that, having seen ''X<sub>i</sub>'' and SipHash(''X<sub>i</sub>'', ''k''), an attacker who does not know the key ''k'' cannot find (any information about) ''k'' or SipHash(''Y'', ''k'') for any message ''Y'' ∉ {''X<sub>i</sub>''} which they have not seen before.


==Overview==
==Overview==


SipHash computes 64-bit [[message authentication code]] from a variable-length message and 128-bit secret key. It was designed to be efficient even for short inputs, with performance comparable to non-cryptographic hash functions, such as [[CityHash]],<ref>{{cite book|last1=So|first1=Won|last2=Narayanan|first2=Ashok|last3=Oran|first3=David|last4=Stapp|first4=Mark|title=Named data networking on a router: forwarding at 20gbps and beyond|journal=Proceedings of the ACM SIGCOMM 2013 Conference on SIGCOMM|pages=495|url=https://www.researchgate.net/publication/266654227|access-date=28 February 2018|ref=swnaodsmndn|quote=The recently proposed SipHash [1] offers a good balance as it provides collision resistance and comparable performance to non-crypto hashes|doi=10.1145/2486001.2491699|year=2013|isbn=9781450320566|s2cid=1457918}}</ref>{{rp|496}}<ref name="paper"/>
SipHash computes a [[64-bit computing|64-bit]] [[message authentication code]] from a variable-length message and 128-bit secret key. It was designed to be efficient even for short inputs, with performance comparable to non-cryptographic hash functions, such as [[CityHash]];<ref>{{cite book|last1=So|first1=Won|last2=Narayanan|first2=Ashok|last3=Oran|first3=David|last4=Stapp|first4=Mark|title=Proceedings of the ACM SIGCOMM 2013 conference on SIGCOMM |chapter=Named data networking on a router |pages=495–496|url=https://www.researchgate.net/publication/266654227|access-date=28 February 2018|ref=swnaodsmndn|quote=The recently proposed SipHash [1] offers a good balance as it provides collision resistance and comparable performance to non-crypto hashes|doi=10.1145/2486001.2491699|year=2013|isbn=9781450320566|s2cid=1457918}}</ref>{{rp|496}}<ref name="paper"/>
thus can be used to prevent denial-of-service attacks against [[hash table]]s ("hash flooding"),<ref>{{Cite conference
this can be used to prevent denial-of-service attacks against [[hash table]]s ("hash flooding"),<ref>{{Cite conference
|title=Hash-flooding DoS reloaded: attacks and defenses
|title=Hash-flooding DoS reloaded: attacks and defenses
|first1=Jean-Philippe |last1=Aumasson
|first1=Jean-Philippe |last1=Aumasson
Line 29: Line 31:
|conference-url=http://www.appsec-forum.ch/
|conference-url=http://www.appsec-forum.ch/
|date=2012-11-08
|date=2012-11-08
|archive-url=https://web.archive.org/web/20130913185247/https://131002.net/siphash/siphashdos_appsec12_slides.pdf
|archive-date=2013-09-13
}}</ref> or to authenticate [[network packet]]s. A variant was later added which produces a 128-bit result.<ref name="ref_impl" />
}}</ref> or to authenticate [[network packet]]s. A variant was later added which produces a 128-bit result.<ref name="ref_impl" />


An unkeyed hash function such as SHA is only collision-resistant if the entire output is used. If used to generate a ''small'' output, such as an index into a hash table of practical size, then no algorithm can prevent collisions; an attacker need only make as many attempts as there are possible outputs.
An unkeyed hash function such as SHA is collision-resistant only if the entire output is used. If used to generate a ''small'' output, such as an index into a hash table of practical size, then no algorithm can prevent collisions; an attacker need only make as many attempts as there are possible outputs.


For example, suppose a network server is designed to be able to handle up to a million requests at once. It keeps track of incoming requests in a hash table with two million entries, using a hash function to map identifying information from each request to one of the two million possible table entries. An attacker who knows the hash function need only feed it arbitrary inputs; one out of two million will have a specific hash value. If the attacker now sends a few hundred requests all chosen to have the ''same'' hash value to the server, that will produce a large number of hash collisions, slowing (or possibly stopping) the server with an effect similar to a [[Denial-of-service attack#Application-layer floods|packet flood]] of many million requests.<ref>{{cite conference
For example, suppose a network server is designed to be able to handle up to a million requests at once. It keeps track of incoming requests in a hash table with two million entries, using a hash function to map identifying information from each request to one of the two million possible table entries. An attacker who knows the hash function need only feed it arbitrary inputs; one out of two million will have a specific hash value. If the attacker now sends a few hundred requests all chosen to have the ''same'' hash value to the server, that will produce a large number of hash collisions, slowing (or possibly stopping) the server with an effect similar to a [[Denial-of-service attack#Application-layer attacks|packet flood]] of many million requests.<ref>{{cite conference
| title=Denial of Service via Algorithmic Complexity Attacks
| title=Denial of Service via Algorithmic Complexity Attacks
| first1=Scott A. |last1=Crosby
| first1=Scott A. |last1=Crosby
Line 45: Line 49:
By using a key unknown to the attacker, a keyed hash function like SipHash prevents this sort of attack. While it is possible to add a key to an unkeyed hash function ([[HMAC]] is a popular technique), SipHash is much more efficient.
By using a key unknown to the attacker, a keyed hash function like SipHash prevents this sort of attack. While it is possible to add a key to an unkeyed hash function ([[HMAC]] is a popular technique), SipHash is much more efficient.


Functions in SipHash family are specified as SipHash-''c''-''d'', where ''c'' is the number of rounds per message block and ''d'' is the number of finalization rounds. The recommended parameters are SipHash-2-4 for best performance, and SipHash-4-8 for conservative security.
Functions in SipHash family are specified as SipHash-''c''-''d'', where ''c'' is the number of rounds per message block and ''d'' is the number of finalization rounds. The recommended parameters are SipHash-2-4 for best performance, and SipHash-4-8 for conservative security. A few languages use Siphash-1-3 for performance at the risk of yet-unknown DoS attacks.<ref>{{cite web |last1=Aumasson |first1=Jean-Philippe (veorq) |title=Comment on: change Siphash to use one of the faster variants of the algorithm (Siphash13, Highwayhash) · Issue #29754 · rust-lang/rust |url=https://github.com/rust-lang/rust/issues/29754#issuecomment-156073946 |website=GitHub |access-date=28 February 2024 |language=en |quote=SipHash designer here, haven't changed my opinion about SipHash-1-3 :-) [...] There's a "distinguisher" on 4 rounds[...], or in simplest terms a statistical bias that shows up given a specific difference pattern in the input of the 4-round sequence. But you can't inject that pattern in SipHash-1-3 because you don't control all the state. And even if you could inject that pattern the bias wouldn't be exploitable anyway.|date=Nov 12, 2015}}</ref>


The [[reference implementation]] was released as [[public domain software]] under the [[CC0]].<ref name="ref_impl">{{cite web
The [[reference implementation]] was released as [[public domain software]] under the [[CC0]].<ref name="ref_impl">{{cite web
Line 52: Line 56:
| quote=Intellectual property: We aren't aware of any patents or patent applications relevant to SipHash, and we aren't planning to apply for any. The reference code of SipHash is released under CC0 license, a public domain-like license.
| quote=Intellectual property: We aren't aware of any patents or patent applications relevant to SipHash, and we aren't planning to apply for any. The reference code of SipHash is released under CC0 license, a public domain-like license.
| date=2016-08-01
| date=2016-08-01
| access-date=2017-01-21}}</ref>
| access-date=2017-01-21
| archive-url=https://web.archive.org/web/20170202184819/https://131002.net/siphash/
⚫
| archive-date=2017-02-02
}}</ref>


==Usage==
==Usage==


SipHash is used in '''[[hash table]] implementations''' of various software:<ref>{{cite web
SipHash is used in ''[[hash table]] implementations'' of various software:<ref>{{cite web
| url=https://131002.net/siphash/#us
| url=https://131002.net/siphash/#us
| title=SipHash: a fast short-input PRF, Users
| title=SipHash: a fast short-input PRF, Users
| author1=Jean-Philippe Aumasson |author2=Daniel J. Bernstein
| last1=Aumasson |first1=Jean-Philippe
| last2=Bernstein |first2=Daniel J.
| date=2016-08-01
| date=2016-08-01
| access-date=2017-01-21}}</ref>
| access-date=2017-01-21
| archive-url=https://web.archive.org/web/20170202184819/https://131002.net/siphash/#us
| archive-date=2017-02-02
}}</ref>


* [[Programming language]]s
{{div col}}
* [[Haskell (programming language)|Haskell]]
** [[Haskell]]
* [[Linux]]
** [[JavaScript]]
⚫
*** [[Node.js]]<ref>{{cite web
⚫
* [[OpenBSD]]
⚫
| url = https://github.com/nodejs/node/pull/26367
⚫
* [[OpenDNS]]
| title = build: enable v8's SipHash for hash seed creation
⚫
* [[Perl 5]] (available as compile-time option)<ref>{{cite web
| last = Vagg | first = Rod
⚫
| url = http://perldoc.perl.org/perlsec.html#Algorithmic-Complexity-Attacks
| work = [[Node.js]]
| via = [[GitHub]]
⚫
| date = 2019-02-28
| access-date = 2021-10-21
}}</ref>
**** [[V8 (JavaScript engine)]] (available as a compile-time option)<ref>{{cite web
| url=https://chromium-review.googlesource.com/c/v8/v8/+/1382463/
| title=Optionally use halfsiphash for integer hashing
| last=Guo | first=Yang
| work = [[V8 (JavaScript engine)|V8]]
| date=2019-01-09
⚫
| access-date=2021-10-21}}</ref>
** [[OCaml]]<ref>{{cite web
| url=https://v2.ocaml.org/enwiki/api/Hashtbl.html
| title=OCaml Library: Hashtbl
| access-date=2024-02-17}}</ref>
⚫
** [[Perl]] 5 (available as a [[compile time]] option)<ref>{{cite web
⚫
| url = https://perldoc.perl.org/perlsec#Algorithmic-Complexity-Attacks
| title = Perl security – Algorithmic Complexity Attacks
| title = Perl security – Algorithmic Complexity Attacks
| website = Perldoc Browser
| date = 2016-05-16
| date = 2016-05-16
| access-date = 2017-01-21}}</ref>
| access-date = 2021-10-21}}</ref>
* [[Python (programming language)|Python]] (starting in version 3.4)<ref>{{cite web
** [[Python (programming language)|Python]] (starting in version 3.4,<ref>{{cite web
| url=https://www.python.org/dev/peps/pep-0456/
| url=https://www.python.org/dev/peps/pep-0456/
| title=PEP 456 – Secure and interchangeable hash algorithm
| title=PEP 456 – Secure and interchangeable hash algorithm
| author=Christian Heimes
| last=Heimes |first=Christian
| date=2013-09-27
| date=2013-09-27
| access-date=2017-01-21}}</ref> SipHash 1-3 since 3.11<ref>{{cite web |title=Moving to SipHash-1-3 #73596 |website=[[GitHub]] |url=https://github.com/python/cpython/issues/73596}}</ref>)
⚫
| access-date=2017-01-21}}</ref>
* [[Raku (programming language)|Raku]]<ref>{{cite web
** [[Raku (programming language)|Raku]]<ref>{{cite web
| url = https://github.com/MoarVM/MoarVM/commit/d9a3270aa290c8dd3b547d4deceb5e76dc8c8e47
| url = https://github.com/MoarVM/MoarVM/commit/d9a3270aa290c8dd3b547d4deceb5e76dc8c8e47
| title = Implement SipHash, use as our hashing function w/ 64bit hashvals
| title = Implement SipHash, use as our hashing function w/ 64-bit hashvals
| last = McVey | first = Samantha
| work = [[MoarVM]]
| via = [[GitHub]]
| date = 2018-07-16
| date = 2018-07-16
| access-date = 2018-07-16}}</ref>
| access-date = 2018-07-16}}</ref>
** [[Ruby (programming language)|Ruby]] (SipHash 1-3)<ref>{{cite web | url=https://bugs.ruby-lang.org/issues/13017 | title=Feature #13017: Switch SipHash from SipHash24 to SipHash13 - Ruby master - Ruby Issue Tracking System }}</ref>
⚫
* [[Ruby (programming language)|Ruby]]
* [[Rust (programming language)|Rust]]<ref>{{cite web
** [[Rust (programming language)|Rust]] (SipHash 1-3)<ref>{{cite web
| url=https://github.com/rust-lang/rust/commit/fada46c4214f26dbdc0fd150a713aced476e75b5
| url=https://github.com/rust-lang/rust/commit/db1b1919baba8be48d997d9f70a6a5df7e31612a
| title=std: use siphash-1-3 for HashMap
| title=Add core::hash containing SipHash-2-4 implementation. Re: #1616 and #859
| last=McArthur | first=Sean
| author=Graydon Hoare
| work = [[Rust (programming language)|Rust]]
⚫
| date=2012-07-24
| via = [[GitHub]]
⚫
| access-date=2017-01-21}}</ref> (SipHash 1-3)
| date=2016-06-30
⚫
* [[Swift (programming language)|Swift]]
| access-date=2017-01-21}}</ref>
⚫
* [[systemd]]<ref>{{cite web
⚫
** [[Swift (programming language)|Swift]]

* [[Operating system]]s
⚫
** [[Linux]]
*** [[systemd]]<ref>{{cite web
| url=https://cgit.freedesktop.org/systemd/systemd/commit/?id=9bf3b53533cdc9b95c921b71da755401f223f765
| url=https://cgit.freedesktop.org/systemd/systemd/commit/?id=9bf3b53533cdc9b95c921b71da755401f223f765
| title=shared: switch our hash table implementation over to SipHash
| title=shared: switch our hash table implementation over to SipHash
| author=Lennart Poettering
| last=Poettering | first=Lennart
| author-link=Lennart Poettering
| author-link=Lennart Poettering
| work = [[systemd]]
| via = [[freedesktop.org]]
| date=2013-12-22
| date=2013-12-22
| access-date=2017-01-21}}</ref>
| access-date=2017-01-21}}</ref>
** [[OpenBSD]]<ref>{{cite web | url=https://github.com/openbsd/src/blob/master/sys/crypto/siphash.h | title=SRC/Sys/Crypto/Siphash.h at master · openbsd/SRC | website=[[GitHub]] }}</ref>
{{div col end}}
** [[FreeBSD]]<ref>{{cite web | url=https://svnweb.freebsd.org/base/head/sys/crypto/siphash/ | title=&#91;base&#93; Index of /Head/Sys/Crypto/Siphash }}</ref>
⚫
** [[OpenDNS]]
** [[Wireguard]]<ref>{{cite web | url=https://github.com/WireGuard/wg-dynamic/commit/360b9c8c8b4c4364b755dc0935f05e4ba4429cb0 | title=Use siphash for hashtables · WireGuard/Wg-dynamic@360b9c8 | website=[[GitHub]] }}</ref>


The following programs use SipHash in other ways:
The following programs use SipHash in other ways:
{{div col}}
* [[Bitcoin]] for short transaction IDs<ref>{{Cite web|url=https://github.com/bitcoin/bips/blob/master/bip-0152.mediawiki|title=Compact Block Relay|website=GitHub|language=en|access-date=2018-09-27}}</ref>
* [[Bitcoin]] for short transaction IDs<ref>{{Cite web|url=https://github.com/bitcoin/bips/blob/master/bip-0152.mediawiki|title=Compact Block Relay|website=GitHub|language=en|access-date=2018-09-27}}</ref>
* Bloomberg BDE as a C++ object hasher<ref>[https://github.com/bloomberg/bde/blob/master/groups/bsl/bslh/bslh_siphashalgorithm.h bslh_siphashalgorithm.h]</ref>
* Bloomberg BDE as a [[C++]] [[Object (computer science)|object]] hasher<ref>[https://github.com/bloomberg/bde/blob/master/groups/bsl/bslh/bslh_siphashalgorithm.h bslh_siphashalgorithm.h]</ref>
* [[InterPlanetary File System]] (IPFS) for its seven [[Bloom filter]] hashes<ref>{{cite web | url=https://github.com/ipfs/bbloom/blob/73e3f896a4f8bbed8589df6ff5c28ebfbd728e31/sipHash.go#L15 | title=Bbloom/SipHash.go at 73e3f896a4f8bbed8589df6ff5c28ebfbd728e31 · ipfs/Bbloom | website=[[GitHub]] }}</ref>
* [[IPFS]] for its seven [[Bloom filter]] hashes
{{div col end}}


'''Implementations'''
'''Implementations'''
{{div col}}
* [https://github.com/veorq/SipHash C] (Public domain reference implementation)
* [https://github.com/veorq/SipHash C] (Public domain reference implementation)
* [https://github.com/jedisct1/rust-siphash Rust]
* [https://github.com/google/highwayhash C++] (Wassenberg & Alakuijala 2017, part of their "highwayhash" work)
⚫
* [https://github.com/paya-cz/siphash C#]
* [[Crypto++]]
* [[Crypto++]]
* [https://github.com/paya-cz/siphash C#]
* [https://github.com/dchest/siphash Go]
* [https://gist.github.com/ar-nelson/12bd5ea968c145045200 Haskell]
* [https://gist.github.com/ar-nelson/12bd5ea968c145045200 Haskell]
* [https://github.com/jedisct1/siphash-js JavaScript]
* [https://github.com/jedisct1/siphash-js JavaScript]
⚫
* [https://github.com/pemb/siphash VHDL]
⚫
* [https://github.com/secworks/siphash Verilog]
⚫
* [https://godoc.org/github.com/dchest/siphash Go]
⚫
* [https://github.com/attaswift/SipHash Swift]
* [https://web.archive.org/web/20180207062939if_/https://bitbucket.org/mihailp/tankfeeder/src/default/hash/siphash.l PicoLisp]
* [https://web.archive.org/web/20180207062939if_/https://bitbucket.org/mihailp/tankfeeder/src/default/hash/siphash.l PicoLisp]
* [https://github.com/jedisct1/rust-siphash Rust]
{{div col end}}
⚫
* [https://github.com/attaswift/SipHash Swift]
* [https://github.com/secworks/siphash Verilog]
⚫
* [https://github.com/pemb/siphash VHDL]


==See also==
==See also==
Line 134: Line 174:


==External links==
==External links==
* {{cite web|url=https://github.com/veorq/SipHash|title=SipHash: a fast short-input PRF – Project Page|author1=Jean-Philippe Aumasson|author2=Daniel J. Bernstein|date=2016-08-01}}
* {{cite web|url=https://github.com/veorq/SipHash|title=SipHash: a fast short-input PRF – Project Page|author1=Jean-Philippe Aumasson|author2=Daniel J. Bernstein|website=[[GitHub]] |date=2016-08-01}}
* {{cite web|url=https://www.aumasson.jp/siphash/siphash.pdf|title=SipHash: a fast short-input PRF|author1=Jean-Philippe Aumasson|author2=Daniel J. Bernstein|date=2012-09-18}}
* {{cite web|url=https://www.aumasson.jp/siphash/siphash.pdf|title=SipHash: a fast short-input PRF|author1=Jean-Philippe Aumasson|author2=Daniel J. Bernstein|date=2012-09-18}}
* {{cite web|url=https://www.aumasson.jp/siphash/siphash_slides.pdf|title=SipHash: a fast short-input PRF – Presentation slides|author1=Jean-Philippe Aumasson|author2=Daniel J. Bernstein|date=2012-08-15}}
* {{cite web|url=https://www.aumasson.jp/siphash/siphash_slides.pdf|title=SipHash: a fast short-input PRF – Presentation slides|author1=Jean-Philippe Aumasson|author2=Daniel J. Bernstein|date=2012-08-15}}
Line 148: Line 188:
{{Cryptography navbox | hash }}
{{Cryptography navbox | hash }}


[[Category:Hash functions]]
[[Category:Hash function (non-cryptographic)]]
[[Category:Public-domain software with source code]]
[[Category:Public-domain software with source code]]
[[Category:Creative Commons-licensed works]]
[[Category:Creative Commons-licensed works]]

Latest revision as of 05:08, 21 August 2024

SipHash is an add–rotate–xor (ARX) based family of pseudorandom functions created by Jean-Philippe Aumasson and Daniel J. Bernstein in 2012,[1]: 165 [2] in response to a spate of "hash flooding" denial-of-service attacks (HashDoS) in late 2011.[3]

SipHash is designed as a non-cryptographic hash function. Although it can be used to ensure security, SipHash is fundamentally different from cryptographic hash functions like Secure Hash Algorithms (SHA) in that it is only suitable as a message authentication code: a keyed hash-function-like hash message authentication code (HMAC). That is, SHA is designed so that it is difficult for an attacker to find two messages X and Y such that SHA(X) = SHA(Y), even though anyone may compute SHA(X). SipHash instead guarantees that, having seen Xi and SipHash(Xi, k), an attacker who does not know the key k cannot find (any information about) k or SipHash(Y, k) for any message Y ∉ {Xi} which they have not seen before.

Overview

[edit]

SipHash computes a 64-bit message authentication code from a variable-length message and 128-bit secret key. It was designed to be efficient even for short inputs, with performance comparable to non-cryptographic hash functions, such as CityHash;[4]: 496 [2] this can be used to prevent denial-of-service attacks against hash tables ("hash flooding"),[5] or to authenticate network packets. A variant was later added which produces a 128-bit result.[6]

An unkeyed hash function such as SHA is collision-resistant only if the entire output is used. If used to generate a small output, such as an index into a hash table of practical size, then no algorithm can prevent collisions; an attacker need only make as many attempts as there are possible outputs.

For example, suppose a network server is designed to be able to handle up to a million requests at once. It keeps track of incoming requests in a hash table with two million entries, using a hash function to map identifying information from each request to one of the two million possible table entries. An attacker who knows the hash function need only feed it arbitrary inputs; one out of two million will have a specific hash value. If the attacker now sends a few hundred requests all chosen to have the same hash value to the server, that will produce a large number of hash collisions, slowing (or possibly stopping) the server with an effect similar to a packet flood of many million requests.[7]

By using a key unknown to the attacker, a keyed hash function like SipHash prevents this sort of attack. While it is possible to add a key to an unkeyed hash function (HMAC is a popular technique), SipHash is much more efficient.

Functions in SipHash family are specified as SipHash-c-d, where c is the number of rounds per message block and d is the number of finalization rounds. The recommended parameters are SipHash-2-4 for best performance, and SipHash-4-8 for conservative security. A few languages use Siphash-1-3 for performance at the risk of yet-unknown DoS attacks.[8]

The reference implementation was released as public domain software under the CC0.[6]

Usage

[edit]

SipHash is used in hash table implementations of various software:[9]

The following programs use SipHash in other ways:

Implementations

See also

[edit]

References

[edit]
  1. ^ Dobraunig, Christoph; Mendel, Florian; Schläffer, Martin (29 November 2014). "Differential Cryptanalysis of SipHash". Selected Areas in Cryptography -- SAC 2014. Lecture Notes in Computer Science. Vol. 8781. pp. 165–182. doi:10.1007/978-3-319-13051-4_10. ISBN 978-3-319-13050-7. Retrieved 28 February 2018.
  2. ^ a b Jean-Philippe Aumasson & Daniel J. Bernstein (2012-09-18). "SipHash: a fast short-input PRF". Cryptology ePrint Archive.
  3. ^ Lennon, Mike (2011-12-28). "Hash Table Vulnerability Enables Wide-Scale DDoS Attacks". SecurityWeek.
  4. ^ So, Won; Narayanan, Ashok; Oran, David; Stapp, Mark (2013). "Named data networking on a router". Proceedings of the ACM SIGCOMM 2013 conference on SIGCOMM. pp. 495–496. doi:10.1145/2486001.2491699. ISBN 9781450320566. S2CID 1457918. Retrieved 28 February 2018. The recently proposed SipHash [1] offers a good balance as it provides collision resistance and comparable performance to non-crypto hashes
  5. ^ Aumasson, Jean-Philippe; Bernstein, Daniel J.; Boßlet, Martin (2012-11-08). Hash-flooding DoS reloaded: attacks and defenses (PDF). Application Security Forum – Western Switzerland 2012. Archived from the original (PDF) on 2013-09-13.
  6. ^ a b "SipHash: a fast short-input PRF". 2016-08-01. Archived from the original on 2017-02-02. Retrieved 2017-01-21. Intellectual property: We aren't aware of any patents or patent applications relevant to SipHash, and we aren't planning to apply for any. The reference code of SipHash is released under CC0 license, a public domain-like license.
  7. ^ Crosby, Scott A.; Wallach, Dan S. (2003-08-06). Denial of Service via Algorithmic Complexity Attacks. Usenix Security Symposium. Washington, D.C.
  8. ^ Aumasson, Jean-Philippe (veorq) (Nov 12, 2015). "Comment on: change Siphash to use one of the faster variants of the algorithm (Siphash13, Highwayhash) · Issue #29754 · rust-lang/rust". GitHub. Retrieved 28 February 2024. SipHash designer here, haven't changed my opinion about SipHash-1-3 :-) [...] There's a "distinguisher" on 4 rounds[...], or in simplest terms a statistical bias that shows up given a specific difference pattern in the input of the 4-round sequence. But you can't inject that pattern in SipHash-1-3 because you don't control all the state. And even if you could inject that pattern the bias wouldn't be exploitable anyway.
  9. ^ Aumasson, Jean-Philippe; Bernstein, Daniel J. (2016-08-01). "SipHash: a fast short-input PRF, Users". Archived from the original on 2017-02-02. Retrieved 2017-01-21.
  10. ^ Vagg, Rod (2019-02-28). "build: enable v8's SipHash for hash seed creation". Node.js. Retrieved 2021-10-21 – via GitHub.
  11. ^ Guo, Yang (2019-01-09). "Optionally use halfsiphash for integer hashing". V8. Retrieved 2021-10-21.
  12. ^ "OCaml Library: Hashtbl". Retrieved 2024-02-17.
  13. ^ "Perl security – Algorithmic Complexity Attacks". Perldoc Browser. 2016-05-16. Retrieved 2021-10-21.
  14. ^ Heimes, Christian (2013-09-27). "PEP 456 – Secure and interchangeable hash algorithm". Retrieved 2017-01-21.
  15. ^ "Moving to SipHash-1-3 #73596". GitHub.
  16. ^ McVey, Samantha (2018-07-16). "Implement SipHash, use as our hashing function w/ 64-bit hashvals". MoarVM. Retrieved 2018-07-16 – via GitHub.
  17. ^ "Feature #13017: Switch SipHash from SipHash24 to SipHash13 - Ruby master - Ruby Issue Tracking System".
  18. ^ McArthur, Sean (2016-06-30). "std: use siphash-1-3 for HashMap". Rust. Retrieved 2017-01-21 – via GitHub.
  19. ^ Poettering, Lennart (2013-12-22). "shared: switch our hash table implementation over to SipHash". systemd. Retrieved 2017-01-21 – via freedesktop.org.
  20. ^ "SRC/Sys/Crypto/Siphash.h at master · openbsd/SRC". GitHub.
  21. ^ "[base] Index of /Head/Sys/Crypto/Siphash".
  22. ^ "Use siphash for hashtables · WireGuard/Wg-dynamic@360b9c8". GitHub.
  23. ^ "Compact Block Relay". GitHub. Retrieved 2018-09-27.
  24. ^ bslh_siphashalgorithm.h
  25. ^ "Bbloom/SipHash.go at 73e3f896a4f8bbed8589df6ff5c28ebfbd728e31 · ipfs/Bbloom". GitHub.
[edit]
Retrieved from "https://en.wikipedia.org/enwiki/w/index.php?title=SipHash&oldid=1241439160"