5 ms·

https://en.wikipedia.org/wiki/SipHash https://en.wikipedia.org/wiki/SipHash

by mrigor 10y ago

zer0t3ch 10y ago
As someone who's not at all versed in cryptography, (yet) anyone want to put this in more laymen terms? Maybe compare it to an existing cryptographical-method I might understand or at least know of?
- semi-extrinsic 10y ago
  ELI5 (distilled from wikipedia page linked by GP, forgive me any errors): Web servers use hash tables for storing per-request data. If an attacker knows the hash function (say, SHA1), they can create a few hundred requests that yield the same hash, giving hundreds of hash collisions and creating a Denial-of-Service attack with the same effect as millions of ordinary requests. It's a form of DoS amplification. A keyed hash function fixes this by keeping part of the hash algorithm (the key) secret. You can turn e.g. SHA1 into a keyed hash function by e.g. HMAC, but that's computationally expensive. SipHash, being a "natively keyed" hash function, is much faster.
  - daveguy 10y ago
    Except if the hash is SHA1 (or any other non-compromised cryptographic hash) they would have a very difficult time creating requests that yield the same hash, that aren't the same request, right?
    - semi-extrinsic 10y ago
      I'm not sure, but I think if you're just interested in creating N collisions, as opposed to finding something that collides with given plaintext X, that the birthday paradox gives you a huge performance increase and makes it feasible. Also, I think many still use MD5 in applications where SipHash is intended (at least the Linux kernel does).
- majke 10y ago
  Hash tables are very important data structures in the computer science world. Hash tables allow you to have amortized O(1) access cost to arbitrary elements - like key/value (often called: map, dict). In order to implement hash table one need to map key onto an index in the table - this is done with a hash function: hash(string) ---> number. Here's a problem. If an attacker knows the hash function, she can produce many strings that will give the same number in return. This usually wasn't a problem, but in the web world it is. It is possible to flood the server (usually in python, ruby, perl) with such crafted requests that, for example, all headers will end up with precisely the same hash value: hash(any_given_header_in_request) ---> fixed value. This is will result in hash table collision and is generally bad. Normal hash functions can't solve this. This problem of maliciously creating hash collisions is called "hash flooding". Siphash is an attempt to solve the problem. It is more than a hash function - it's a crypto PRF function and that gives you more guarantees than dumb hash function. Most importantly it takes two values: a "string to hash" and a "crypto key": siphash(string, crypto_key) --> number. The idea is to generate this "crypto_key" randomly on each program execution, to make sure the attacker can't predict it. Crypto speaking hash functions may be reversible. There is nothing guaranteeing that they are not. But Siphash is a PRF, and in crypto-speach this means it's not reversible. If you can produce an efficient algorithm to reverse Siphash - ie: given crypto key and hash value predict input string - you can write a good paper and be famous.
  - grey-area 10y ago
    I've been looking at using this recently, and had a stupid question about using it - Is it ok to use the same random key with siphash for lots of different hashes as long as the key is secret and mutates once per launch (i.e. generating once on app startup and use it for all hashes)?
    - wolf550e 10y ago
      The danger in your scheme is that an attacker who finds a way to see lots of keyed hash values in one hash table can flood a different hash table. You should keep a 16 byte key per hash table.
- SFjulie1 10y ago
  dict (in python) or hashtables in PHP are amazing data structure that are ON AVERAGE o(1) in complexity for most operations. But, in worst case they are O(n) where n is the depht of the linked list under the hood. Hash tables have an immutable as a key of arbitrary size for which an hash is generated in a predictable way thus hash table are mainly hash => value. Problem occurs when there are collisions of hash values. You must then follow the linked list and check on the exact value of the immutable used as a key with a complete check If hash function is deterministic then collision can be triggered in order to create DOS slowing down the computer. O(1) on a 400cycle operation (memory fetching) that becomes o(1024) now requires <1 000 0000> cycles on average (complete comparaison + memory fetching). You basically can turned a 2016 computer into a 1980 computer (in terms of speed) Hash tables are used when you have sparse data structure, like caches for ephemeral ports (for a firewall) that has a fixed space bigger than memory. A practical attack for slowing down a FW (thus making it useless) would be to use combinations of IP/port to generates colliding hashes. Hashtables are used a lot in keeping states of stuff. Like connections, sessions .... Coincidently with python 2.7 cames the concern of predictable hash functions (basically close to CRC) that were fast to compute but predictable. Hence making a DoS easy to engineer when working with webservers (POST/GET parameters are stored in such data structures). The python concern seems to have spread and raise awareness on the concern. And then someone was like we need randomisation, but without side channel attack (timing) and thus, a class of hash function known as cryptographic hash function: fast to compute, hard to predict and assymmetrically hard to invert senstivite to an initial customisable parameter (called a key or secret).... To sum up: nothing new under the sun.

https://en.wikipedia.org/wiki/SipHash https://en.wikipedia.org/wiki/SipHash

by mrigor 10y ago

https://en.wikipedia.org/wiki/SipHash https://en.wikipedia.org/wiki/SipHash

As someone who's not at all versed in cryptography, (yet) anyone want to put this in more laymen terms? Maybe compare it to an existing cryptographical-method I might understand or at least know of?

semi-extrinsic 10y ago
ELI5 (distilled from wikipedia page linked by GP, forgive me any errors): Web servers use hash tables for storing per-request data. If an attacker knows the hash function (say, SHA1), they can create a few hundred requests that yield the same hash, giving hundreds of hash collisions and creating a Denial-of-Service attack with the same effect as millions of ordinary requests. It's a form of DoS amplification. A keyed hash function fixes this by keeping part of the hash algorithm (the key) secret. You can turn e.g. SHA1 into a keyed hash function by e.g. HMAC, but that's computationally expensive. SipHash, being a "natively keyed" hash function, is much faster.
- daveguy 10y ago
  Except if the hash is SHA1 (or any other non-compromised cryptographic hash) they would have a very difficult time creating requests that yield the same hash, that aren't the same request, right?
  - semi-extrinsic 10y ago
    I'm not sure, but I think if you're just interested in creating N collisions, as opposed to finding something that collides with given plaintext X, that the birthday paradox gives you a huge performance increase and makes it feasible. Also, I think many still use MD5 in applications where SipHash is intended (at least the Linux kernel does).
majke 10y ago
Hash tables are very important data structures in the computer science world. Hash tables allow you to have amortized O(1) access cost to arbitrary elements - like key/value (often called: map, dict). In order to implement hash table one need to map key onto an index in the table - this is done with a hash function: hash(string) ---> number. Here's a problem. If an attacker knows the hash function, she can produce many strings that will give the same number in return. This usually wasn't a problem, but in the web world it is. It is possible to flood the server (usually in python, ruby, perl) with such crafted requests that, for example, all headers will end up with precisely the same hash value: hash(any_given_header_in_request) ---> fixed value. This is will result in hash table collision and is generally bad. Normal hash functions can't solve this. This problem of maliciously creating hash collisions is called "hash flooding". Siphash is an attempt to solve the problem. It is more than a hash function - it's a crypto PRF function and that gives you more guarantees than dumb hash function. Most importantly it takes two values: a "string to hash" and a "crypto key": siphash(string, crypto_key) --> number. The idea is to generate this "crypto_key" randomly on each program execution, to make sure the attacker can't predict it. Crypto speaking hash functions may be reversible. There is nothing guaranteeing that they are not. But Siphash is a PRF, and in crypto-speach this means it's not reversible. If you can produce an efficient algorithm to reverse Siphash - ie: given crypto key and hash value predict input string - you can write a good paper and be famous.
- grey-area 10y ago
  I've been looking at using this recently, and had a stupid question about using it - Is it ok to use the same random key with siphash for lots of different hashes as long as the key is secret and mutates once per launch (i.e. generating once on app startup and use it for all hashes)?
  - wolf550e 10y ago
    The danger in your scheme is that an attacker who finds a way to see lots of keyed hash values in one hash table can flood a different hash table. You should keep a 16 byte key per hash table.
SFjulie1 10y ago
dict (in python) or hashtables in PHP are amazing data structure that are ON AVERAGE o(1) in complexity for most operations. But, in worst case they are O(n) where n is the depht of the linked list under the hood. Hash tables have an immutable as a key of arbitrary size for which an hash is generated in a predictable way thus hash table are mainly hash => value. Problem occurs when there are collisions of hash values. You must then follow the linked list and check on the exact value of the immutable used as a key with a complete check If hash function is deterministic then collision can be triggered in order to create DOS slowing down the computer. O(1) on a 400cycle operation (memory fetching) that becomes o(1024) now requires <1 000 0000> cycles on average (complete comparaison + memory fetching). You basically can turned a 2016 computer into a 1980 computer (in terms of speed) Hash tables are used when you have sparse data structure, like caches for ephemeral ports (for a firewall) that has a fixed space bigger than memory. A practical attack for slowing down a FW (thus making it useless) would be to use combinations of IP/port to generates colliding hashes. Hashtables are used a lot in keeping states of stuff. Like connections, sessions .... Coincidently with python 2.7 cames the concern of predictable hash functions (basically close to CRC) that were fast to compute but predictable. Hence making a DoS easy to engineer when working with webservers (POST/GET parameters are stored in such data structures). The python concern seems to have spread and raise awareness on the concern. And then someone was like we need randomisation, but without side channel attack (timing) and thus, a class of hash function known as cryptographic hash function: fast to compute, hard to predict and assymmetrically hard to invert senstivite to an initial customisable parameter (called a key or secret).... To sum up: nothing new under the sun.