Hacker News Reader

Comment by valarauca1 | Hacker News Reader

>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.

View on HN

>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.

      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!

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

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.

Pre-image is even simpler. A good cryptographic hash also prevents second pre-image attack e.g. pre-image based on multiple hashes.

None of those properties is needed for indexing into hash table. Good collision resistance is all that is required and salting for more paranoid cases.

How is modulo invertible in the general case? If it is, can you demonstrate? I have picked certain numbers and their values modulo 10 are 6, 7, and 8. What numbers did I pick?

You can demonstrate that a number input into modulo belongs to a specific group. Even not knowing the specific value of modulus you can drive it by observing statistical properties of the output. (which is why modulo hashing gives many collisions)

It doesn't have to be. Onewayness says nothing about finding "the original x". If a function is one-way, it means that given y (a random n-bit string in the output space of h), it is hard to find any x such that h(x) = y. If your h() is just a modulo operation, this is trivial: just choose x = y.

Woah, I was completely wrong. You're right. A pseudo-inverse is sufficient. However, there are no functions known to be one-way. How interesting.

Ah, I see, way as in path, not way as in direction (which is I think the misinterpretation that leads people to the root of the misunderstanding). So, there's one path to get from x -> y, but it does not imply you can't get back to the original x. In that respect, "way" is an unfortunate word to use, at least as it's used in modern English.

Any hash function provably collides for at least two inputs, unless we're talking about perfect hashing. The only exception would be a hash function that does not compress, where the output is larger than the input. That's not a hash-function, though.

> you just lose the will never collide guarantee

There is no such guarantee, in fact, the opposite is guaranteed.

It's just very unlikely that you get a collision - that's a desirable property of any hash function -, and it should be hard to create a collision because the function is hard to reverse - that's a desirable property of any cryptographic hash function, as the OP laid out.

Reply on news.ycombinator.com