SipHash

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 in late 2011.[3]

Although designed for use as a hash function in the computer science sense, SipHash is fundamentally different from cryptographic hash functions like 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 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

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,[4]:496[2] thus 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 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.

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.

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

Usage

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

Implementations

gollark: Personal faith = still bad, because you're going around believing in stupid things and *cannot* reasonably isolate that from the rest of your mental framework.
gollark: They are still maybe conscious and sophont?
gollark: I would totally do this if we had the ability to simulate humans at high speed on computers and completely ignored the ethical issues.
gollark: It's an interesting idea.
gollark: [REDACTED]

See also

References
  1. Dobraunig, Christoph; Mendel, Florian; Schläffer, Martin (29 November 2014). Differential Cryptanalysis of SipHash. International Workshop on Selected Areas in Cryptography. Lecture Notes in Computer Science. 8781. pp. 165–182. doi:10.1007/978-3-319-13051-4_10. ISBN 978-3-319-13050-7. Retrieved 28 February 2018.
  2. Jean-Philippe Aumasson & Daniel J. Bernstein (2012-09-18). "SipHash: a fast short-input PRF".
  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: forwarding at 20gbps and beyond. Proceedings of the ACM SIGCOMM 2013 Conference on SIGCOMM. p. 495. doi:10.1145/2486001.2491699. ISBN 9781450320566. 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.
  6. "SipHash: a fast short-input PRF". 2016-08-01. 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. Jean-Philippe Aumasson; Daniel J. Bernstein (2016-08-01). "SipHash: a fast short-input PRF, Users". Retrieved 2017-01-21.
  9. "Perl security – Algorithmic Complexity Attacks". 2016-05-16. Retrieved 2017-01-21.
  10. Christian Heimes (2013-09-27). "PEP 456 – Secure and interchangeable hash algorithm". Retrieved 2017-01-21.
  11. "Implement SipHash, use as our hashing function w/ 64bit hashvals". 2018-07-16. Retrieved 2018-07-16.
  12. Graydon Hoare (2012-07-24). "Add core::hash containing SipHash-2-4 implementation. Re: #1616 and #859". Retrieved 2017-01-21.
  13. Lennart Poettering (2013-12-22). "shared: switch our hash table implementation over to SipHash". Retrieved 2017-01-21.
  14. "Compact Block Relay". GitHub. Retrieved 2018-09-27.
  15. bslh_siphashalgorithm.h
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.