12 ms·

Yes, you really do need collision attack resistance in your standard hash table implementation. You know why? Because we've known for a long time that insecur

Yes, you really do need collision attack resistance in your standard hash table implementation. You know why? Because we've known for a long time that insecure defaults are broken. I'm glad rust makes the correct choice here.

AstralStorm 10y ago
No, cryptographic hash has an additional property. It is one way. So, given a hash it is hard to derive original input. Collision resistance is a separate property which can be fulfilled without one way property. Maybe you want hash numbers that are not predictable by an attacker, but sip hash is not salted either. Plus salting does not require a cryptographic hash either.
- koverstreet 10y ago
  Uh, what? Siphash isn't a cryptographic hash function. It's a keyed hash function designed not to leak the key.
- valarauca1 10y ago
  >It is one way. So, given a hash it is hard to derive original input. This is the definition of a Hash Function. Not a cryptographic Hash Function. Cryptographic Hashes should NEVER collide, on any inputs, ever, period. The moment it is found too, the algorithm is considered depreciated. This is why MD5 shouldn't be used anymore, there is a generalized algorithm for producing collisions. Cryptographic hashes are overkill for HashTables/HashMaps because you can't use 128/256/512bit address spaces unless your attempt to store all the information in the galaxy or observable universe. And modern computers just aren't there yet. Also they are very slow. So when your masking a 512bit output, down to 16bits of your HashTable you just lose the will never collide guarantee. Then something that operates at 10GB/s, and can collide sounds better then something that runs at 150MB/s and will still collide anyways.
  - luchs 10y ago
    >This is the definition of a Hash Function. Not a cryptographic Hash Function. No, a hash function is just any function which can be used to put values into a hash map. If your inputs are numbers, modulo will work fine as a hash function, but is obviously not one-way. >Cryptographic Hashes should NEVER collide, on any inputs, ever, period. This is obviously not possible, as the output of the cryptographic hash function is of fixed-length while the input is variable-length. Finding collision just needs to be hard, not impossible.
    - valarauca1 10y ago
      modulo will work fine as a hash function, but is obviously not one-way. Modulo is a one way trap door operation. Proof via arrogance: X % 100 = 50 Solve for X Solution X = F(n) where F(n) = 100*n+50 (for all n > 1) This does indeed meet the requirements of a hash functions. Modulu is a bad hash function because it is poorly distributed. Cryptographic Hashes should NEVER collide, on any inputs, ever, period. >This is obviously not possible NIPS says if you observe 2 inputs of a cryptographic hash which compute to the same digest the hash is considered depreciated. So yes my definition is correct. Obviously yes all cryptographic hashes aren't unique for every input. As they maybe N bytes long. And simply a logic will tell you there is more information in N bytes of data vs 64 bytes (512bits). The real issue is, prove it. Testing even the 512bit address space will take you longer then the heat death of the universe, so good luck!
      - dgacmu 10y ago
        No - per the definition of a trapdoor function: "For any k ∈ K, without trapdoor tk, for any PPT algorithm, the probability to correctly invert fk (i.e., given fk(x), find a pre-image x' such that fk(x' ) = fk(x)) is negligible" https://en.wikipedia.org/wiki/Trapdoor_function https://en.wikipedia.org/wiki/Trapdoor_function Note that the definition is about a pre-image, not necessarily the input used to create it in the first place. Second, that definition is absolutely not correct. "Never" would require that the size of the output of the hash function be equivalent to the size of the universe of possible inputs, which it obviously isn't. There's a very important difference between "never be observed in practice" and "never, period." You're not using the language precisely, and that's very dangerous when talking about hashing and cryptography.
- Ar-Curunir 10y ago
  Collision resistance implies onewayness for compressing hash functions. You can invert a hashed value, and if your inversion procedure is randomised, then there is a high probability that you'll end up with a different input.
  - chias 10y ago
    > Collision resistance implies onewayness for compressing hash functions. No it doesn't. These are independent properties. That is, collision resistance does not imply onewayness, and onewayness does not imply collision resistance. Collision Resistance: it is hard to find x != x' such that h(x) = h(x') One Wayness: Given y, an n-bit string randomly chosen from the output space of h(), it is hard to find any x such that h(x) = y. Proof that CR does not imply OW: Suppose g() is collision resistant and outputs n bits. Define h(x) to be 0x if x is n bits long, otherwise 1x. Collisions are hard to find: if y starts with 1 there are no collisions, and if it starts with 0 then you'd need to find a collision in g(), which is collision resistant. h() is not one way: given a random y in the output space, with probability 1/2 it is trivial to find an x such that h(x) = y. Proof that OW does not imply CR: Suppose that g() is one-way. Define h(x) = g(x) with the last bit truncated. h() is one-way because you cannot invert h without inverting g(). h() is not collision resistant because for any x, h(x0) = h(x1)
tptacek 10y ago
Moreover, despite the author's continued invocation of the term "cryptographic hash", SIPHash was designed to be a default hash table hash. Very few things use it as a standalone cryptographic hash. You don't see a lot of SIP-based KDFs. It's not the fastest general purpose hash --- but it's not supposed to be. It's supposed to be performant enough to be used as a default, and in being a default, it's supposed to take a pretty common attack off the table. It's the right default. In the rare situations where container hashing winds up high on the profile, the faster hash should be the optional hash.
- aidenn0 10y ago
  The SipHash paper proposed two uses; the hash-table use, but also for network traffic authentication, with the idea that it's output is small enough to MAC each network packet. Do you know if the network use got any traction? I thought the justification for MACing each packet rather than groups of packets was rather weak (single forged packed means multiple packet retransmits), but if I cared about both latency and security, I could see authenticating UDP packets with this. [edit] Also, as a slight additional nitpick to the article, the term "cryptographic hash," when used in isolation, typically implies collision resistance, and SipHash is specifically not collision resistant due to its small output size.
  - tedunangst 10y ago
    OpenBSD ping uses siphash to mac packets.
- exDM69 10y ago
  SipHash is also pretty fast, on my computer I get 2 GB/s. There are hash functions that are 5x faster than that (some AES-NI based ones are 15x faster) but none of them have any credible cryptanalysis for key recovery. I studied SipHash a while ago and implemented a SIMD version but that performed slower (needs 4x64 bit int vectors and doesn't allow any instruction level parallelism). I'm sure that you could make a faster hash function with 4x32 bit vectors using similar ARX (add-rotate-xor) networks but I'm not smart enough to do the cryptanalysis. There's a new hash function called HighwayHash which was about 11GB/s but the implementation is very tied to Intel CPUs (SSE4.1 or AVX512) and uses 4x64 bit vectors. And no cryptanalysis on that either, although it looks like it has similar characteristics to SipHash. Hash table keys are typically quite short, so going crazy with SIMD to push the throughput might not be a great idea.
rurban 10y ago
Nonsense. Rust made a non-technical fear based choice. Robin-Hood is enough protection, SipHash only adds slowness. There are many twice as fast hash funcs with less collisions, and with Robin Hood you are fine with FNV1. For concurrency leapfrog would be better.
- exDM69 10y ago
  It does nothing to protect against having to do bit-to-bit comparison of keys when two keys hash to bit-exact same hash value. This is what's behind "hash flooding" algorithmic complexity DDoS attacks that cause O(n^2) CPU usage w.r.t. input length. SipHash is the only hash function that has credible cryptanalysis against key recovery and collisions. E.g. FNV1 is trivially simple to generate collisions against.
  - rurban 10y ago
    It's also trivial to produce SipHash collisions and its "security" claims are dubious in the hash table context. There's not much credibility in the siphash paper in section 7. linear chaining is not the recommended way to treat hash tables anymore, and even with that you can add a useful protection. siphash is not one. Yes, it's non-reversable, and it doesn't allow easy seed-independent multi collisions as with other hash functions. But one hash function used in a hash table can never be secure. The collision resolution adds the security part. (or/plus some other schemes which are obviously over your head).
- deleted 10y ago
  [deleted]

AstralStorm 10y ago

No, cryptographic hash has an additional property. It is one way. So, given a hash it is hard to derive original input. Collision resistance is a separate property which can be fulfilled without one way property. Maybe you want hash numbers that are not predictable by an attacker, but sip hash is not salted either. Plus salting does not require a cryptographic hash either.

koverstreet 10y ago
Uh, what? Siphash isn't a cryptographic hash function. It's a keyed hash function designed not to leak the key.
valarauca1 10y ago
>It is one way. So, given a hash it is hard to derive original input. This is the definition of a Hash Function. Not a cryptographic Hash Function. Cryptographic Hashes should NEVER collide, on any inputs, ever, period. The moment it is found too, the algorithm is considered depreciated. This is why MD5 shouldn't be used anymore, there is a generalized algorithm for producing collisions. Cryptographic hashes are overkill for HashTables/HashMaps because you can't use 128/256/512bit address spaces unless your attempt to store all the information in the galaxy or observable universe. And modern computers just aren't there yet. Also they are very slow. So when your masking a 512bit output, down to 16bits of your HashTable you just lose the will never collide guarantee. Then something that operates at 10GB/s, and can collide sounds better then something that runs at 150MB/s and will still collide anyways.
- luchs 10y ago
  >This is the definition of a Hash Function. Not a cryptographic Hash Function. No, a hash function is just any function which can be used to put values into a hash map. If your inputs are numbers, modulo will work fine as a hash function, but is obviously not one-way. >Cryptographic Hashes should NEVER collide, on any inputs, ever, period. This is obviously not possible, as the output of the cryptographic hash function is of fixed-length while the input is variable-length. Finding collision just needs to be hard, not impossible.
  - valarauca1 10y ago
    modulo will work fine as a hash function, but is obviously not one-way. Modulo is a one way trap door operation. Proof via arrogance: X % 100 = 50 Solve for X Solution X = F(n) where F(n) = 100*n+50 (for all n > 1) This does indeed meet the requirements of a hash functions. Modulu is a bad hash function because it is poorly distributed. Cryptographic Hashes should NEVER collide, on any inputs, ever, period. >This is obviously not possible NIPS says if you observe 2 inputs of a cryptographic hash which compute to the same digest the hash is considered depreciated. So yes my definition is correct. Obviously yes all cryptographic hashes aren't unique for every input. As they maybe N bytes long. And simply a logic will tell you there is more information in N bytes of data vs 64 bytes (512bits). The real issue is, prove it. Testing even the 512bit address space will take you longer then the heat death of the universe, so good luck!
    - dgacmu 10y ago
      No - per the definition of a trapdoor function: "For any k ∈ K, without trapdoor tk, for any PPT algorithm, the probability to correctly invert fk (i.e., given fk(x), find a pre-image x' such that fk(x' ) = fk(x)) is negligible" https://en.wikipedia.org/wiki/Trapdoor_function https://en.wikipedia.org/wiki/Trapdoor_function Note that the definition is about a pre-image, not necessarily the input used to create it in the first place. Second, that definition is absolutely not correct. "Never" would require that the size of the output of the hash function be equivalent to the size of the universe of possible inputs, which it obviously isn't. There's a very important difference between "never be observed in practice" and "never, period." You're not using the language precisely, and that's very dangerous when talking about hashing and cryptography.
Ar-Curunir 10y ago
Collision resistance implies onewayness for compressing hash functions. You can invert a hashed value, and if your inversion procedure is randomised, then there is a high probability that you'll end up with a different input.
- chias 10y ago
  > Collision resistance implies onewayness for compressing hash functions. No it doesn't. These are independent properties. That is, collision resistance does not imply onewayness, and onewayness does not imply collision resistance. Collision Resistance: it is hard to find x != x' such that h(x) = h(x') One Wayness: Given y, an n-bit string randomly chosen from the output space of h(), it is hard to find any x such that h(x) = y. Proof that CR does not imply OW: Suppose g() is collision resistant and outputs n bits. Define h(x) to be 0x if x is n bits long, otherwise 1x. Collisions are hard to find: if y starts with 1 there are no collisions, and if it starts with 0 then you'd need to find a collision in g(), which is collision resistant. h() is not one way: given a random y in the output space, with probability 1/2 it is trivial to find an x such that h(x) = y. Proof that OW does not imply CR: Suppose that g() is one-way. Define h(x) = g(x) with the last bit truncated. h() is one-way because you cannot invert h without inverting g(). h() is not collision resistant because for any x, h(x0) = h(x1)

tptacek 10y ago

Moreover, despite the author's continued invocation of the term "cryptographic hash", SIPHash was designed to be a default hash table hash. Very few things use it as a standalone cryptographic hash. You don't see a lot of SIP-based KDFs. It's not the fastest general purpose hash --- but it's not supposed to be. It's supposed to be performant enough to be used as a default, and in being a default, it's supposed to take a pretty common attack off the table. It's the right default. In the rare situations where container hashing winds up high on the profile, the faster hash should be the optional hash.

aidenn0 10y ago
The SipHash paper proposed two uses; the hash-table use, but also for network traffic authentication, with the idea that it's output is small enough to MAC each network packet. Do you know if the network use got any traction? I thought the justification for MACing each packet rather than groups of packets was rather weak (single forged packed means multiple packet retransmits), but if I cared about both latency and security, I could see authenticating UDP packets with this. [edit] Also, as a slight additional nitpick to the article, the term "cryptographic hash," when used in isolation, typically implies collision resistance, and SipHash is specifically not collision resistant due to its small output size.
- tedunangst 10y ago
  OpenBSD ping uses siphash to mac packets.
exDM69 10y ago
SipHash is also pretty fast, on my computer I get 2 GB/s. There are hash functions that are 5x faster than that (some AES-NI based ones are 15x faster) but none of them have any credible cryptanalysis for key recovery. I studied SipHash a while ago and implemented a SIMD version but that performed slower (needs 4x64 bit int vectors and doesn't allow any instruction level parallelism). I'm sure that you could make a faster hash function with 4x32 bit vectors using similar ARX (add-rotate-xor) networks but I'm not smart enough to do the cryptanalysis. There's a new hash function called HighwayHash which was about 11GB/s but the implementation is very tied to Intel CPUs (SSE4.1 or AVX512) and uses 4x64 bit vectors. And no cryptanalysis on that either, although it looks like it has similar characteristics to SipHash. Hash table keys are typically quite short, so going crazy with SIMD to push the throughput might not be a great idea.

rurban 10y ago

Nonsense. Rust made a non-technical fear based choice. Robin-Hood is enough protection, SipHash only adds slowness. There are many twice as fast hash funcs with less collisions, and with Robin Hood you are fine with FNV1. For concurrency leapfrog would be better.

exDM69 10y ago
It does nothing to protect against having to do bit-to-bit comparison of keys when two keys hash to bit-exact same hash value. This is what's behind "hash flooding" algorithmic complexity DDoS attacks that cause O(n^2) CPU usage w.r.t. input length. SipHash is the only hash function that has credible cryptanalysis against key recovery and collisions. E.g. FNV1 is trivially simple to generate collisions against.
- rurban 10y ago
  It's also trivial to produce SipHash collisions and its "security" claims are dubious in the hash table context. There's not much credibility in the siphash paper in section 7. linear chaining is not the recommended way to treat hash tables anymore, and even with that you can add a useful protection. siphash is not one. Yes, it's non-reversable, and it doesn't allow easy seed-independent multi collisions as with other hash functions. But one hash function used in a hash table can never be secure. The collision resolution adds the security part. (or/plus some other schemes which are obviously over your head).
deleted 10y ago
[deleted]