3 ms·

The only way we know to make a secure hash function is with a random seed. This is the "correct" way to do it. Anything else claiming "cryptographical strong" w

The only way we know to make a secure hash function is with a random seed. This is the "correct" way to do it. Anything else claiming "cryptographical strong" without a secret random seed is coolaid. It is true that timing attacks to guess the key could be an issue, but I have yet to see reports of this having been done. Also, it wouldn't be hard to fix in the hash table implementations.

rurban 10y ago
Nonsense. The only way we know to make a secure hash table function is either via universal hashing (academic literature), via non-linear collision iteration (i.e. java) or by detecting an DoS attack (by counting the collisions (i.e. djbdns). Please look at the literature. It's embarrassing. A random seed helps, but doesn't guarantee DoS-safeness. Same for SipHash. Using SipHash doesn't give you a DoS-safe hash table if you use chained hashing. It only makes it slower and hides the seed better. Secure hash functions do not exist with hash tables. I'm tried of hearing all this nonsense all over. SipHash is a secure PRF, but we don't care for "Pseudo Random Functions", we look for hash functions.
- geofft 10y ago
  > universal hashing (academic literature) Building a hash table with a function randomly selected from a PRF is universal hashing.
  - rurban 10y ago
    Not if the function is not random. A random seed for a fixed known function only gives you a few bits of randomness. This random seed is easily detectable from inside, and harder to detect from outside via ordering exposure and timings. This is not a random function. Double hashing with random seeds would qualify as universal hashing though.
    - zx2c4 10y ago
      The seed is kept secret. Observing siphash outputs will not reveal the seed, unless an entirely infeasible quantity of outputs are observed.
      - thomasahle 10y ago
        This is a nice "worst case" feature of siphash. However I don't think its authors would recommend using it in case you know outputs will be easily observable.
        zx2c4 10y ago
        Citation?
        dchest 10y ago
        It's not "worst case" feature, it's the standard, minimal feature of any secure cryptographic PRF.
        thomasahle 10y ago
        It's worst cast in the model of security that hash tables are usually evaluated under. The authors of Siphash state as much: > Stopping advanced hash flooding. The _worst possible_ exposure of hash-table indices would simply show the attacker H(m) mod `for any attacker-selected string m. We advocate protecting against this maximum possible exposure, so that applications do not have to worry about how much exposure they actually provide. The attacker’s goal, given this exposure, is to find many strings m having a single value H(m) mod `. https://131002.net/siphash/siphash.pdf https://131002.net/siphash/siphash.pdf They also state that the "Target applications include network traffic authentication and hash-table lookups protected against hash-flooding denial-of-service attacks". It's nice to have a fast random hash function, that is also reasonably cryptographically strong, in case an attacked gets access to the hash values. That doesn't mean it's as cryptographically strong as hash functions specifically designed for full exposure. I'm just saying, use it for hash-tables, but don't use it as a general replacement for HMAC-SHA-1 in your encryption schemes. At least I don't see the authors recommending that anywhere.
- tptacek 10y ago
  It's OK to be wrong on HN, and even OK to be militantly wrong, but you can't be uncivil. The people you're talking to are very familiar with the literature --- seemingly more familiar than you are, although I'm holding onto hope that this is just a really bad miscommunication --- and don't deserve invective.
- thomasahle 10y ago
  > Nonsense. The only way we know to make a secure hash table function is either via universal hashing (academic literature). This is my point. A universal hash function is a random distribution over deterministic functions. You can always create a single deterministic function with a seed in such a way, that it acts as drawing a random function from a distribution. I don't know that siphash is universal, certainly not all seeded functions are. Perhaps that's your point. I'm just saying that using randomness is the only way to create universality. Actually the Aumasson, Bernstein paper http://cr.yp.to/siphash/siphash-20120918.pdf http://cr.yp.to/siphash/siphash-20120918.pdf has some interesting considerations on timing attacks against universal hash functions.

rurban 10y ago

Nonsense. The only way we know to make a secure hash table function is either via universal hashing (academic literature), via non-linear collision iteration (i.e. java) or by detecting an DoS attack (by counting the collisions (i.e. djbdns). Please look at the literature. It's embarrassing. A random seed helps, but doesn't guarantee DoS-safeness. Same for SipHash. Using SipHash doesn't give you a DoS-safe hash table if you use chained hashing. It only makes it slower and hides the seed better. Secure hash functions do not exist with hash tables. I'm tried of hearing all this nonsense all over. SipHash is a secure PRF, but we don't care for "Pseudo Random Functions", we look for hash functions.

geofft 10y ago
> universal hashing (academic literature) Building a hash table with a function randomly selected from a PRF is universal hashing.
- rurban 10y ago
  Not if the function is not random. A random seed for a fixed known function only gives you a few bits of randomness. This random seed is easily detectable from inside, and harder to detect from outside via ordering exposure and timings. This is not a random function. Double hashing with random seeds would qualify as universal hashing though.
  - zx2c4 10y ago
    The seed is kept secret. Observing siphash outputs will not reveal the seed, unless an entirely infeasible quantity of outputs are observed.
    - thomasahle 10y ago
      This is a nice "worst case" feature of siphash. However I don't think its authors would recommend using it in case you know outputs will be easily observable.
      - zx2c4 10y ago
        Citation?
      - dchest 10y ago
        It's not "worst case" feature, it's the standard, minimal feature of any secure cryptographic PRF.
        thomasahle 10y ago
        It's worst cast in the model of security that hash tables are usually evaluated under. The authors of Siphash state as much: > Stopping advanced hash flooding. The _worst possible_ exposure of hash-table indices would simply show the attacker H(m) mod `for any attacker-selected string m. We advocate protecting against this maximum possible exposure, so that applications do not have to worry about how much exposure they actually provide. The attacker’s goal, given this exposure, is to find many strings m having a single value H(m) mod `. https://131002.net/siphash/siphash.pdf https://131002.net/siphash/siphash.pdf They also state that the "Target applications include network traffic authentication and hash-table lookups protected against hash-flooding denial-of-service attacks". It's nice to have a fast random hash function, that is also reasonably cryptographically strong, in case an attacked gets access to the hash values. That doesn't mean it's as cryptographically strong as hash functions specifically designed for full exposure. I'm just saying, use it for hash-tables, but don't use it as a general replacement for HMAC-SHA-1 in your encryption schemes. At least I don't see the authors recommending that anywhere.
tptacek 10y ago
It's OK to be wrong on HN, and even OK to be militantly wrong, but you can't be uncivil. The people you're talking to are very familiar with the literature --- seemingly more familiar than you are, although I'm holding onto hope that this is just a really bad miscommunication --- and don't deserve invective.
thomasahle 10y ago
> Nonsense. The only way we know to make a secure hash table function is either via universal hashing (academic literature). This is my point. A universal hash function is a random distribution over deterministic functions. You can always create a single deterministic function with a seed in such a way, that it acts as drawing a random function from a distribution. I don't know that siphash is universal, certainly not all seeded functions are. Perhaps that's your point. I'm just saying that using randomness is the only way to create universality. Actually the Aumasson, Bernstein paper http://cr.yp.to/siphash/siphash-20120918.pdf http://cr.yp.to/siphash/siphash-20120918.pdf has some interesting considerations on timing attacks against universal hash functions.