0
$\begingroup$

I was reading about hash functions in crypto and a website had mentioned that they were collision free, which obviously isn't possible if there are infinite input values that are mapped to outputs of a finite length. So what happens in the event of a hash collision? How do crypto currencies overcome this problem?

Also, this is slightly off topic, but why can't a hash value be decoded? I mean if values are being mapped, to mapped to an output finite list of encoded values why can't you reverse engineer the process? It can't be truly random there has to be a method for which a hash function maps its values right?

Please let me know if I am using any terminology wrong or am completely mistaken in any assumptions I make in my question. I am just trying to learn so please let me know.

$\endgroup$
3
  • $\begingroup$ The whole point of hash functions is that they are hard to find collisions in. A mathematical definition would use a random key $k$, and would require the hash function to satisfy that with high probability it will be hard to find a pair $x\neq y$ such that $h_k(x)=h_k(y)$ $\endgroup$
    – nir shahar
    Apr 6, 2022 at 20:51
  • $\begingroup$ Also, the point of hash functions is to not have easy-to-find collisions (and is not to be unreversable. But rather, by its mathematical definition at least - its a perk that comes along with it. In practice its easy to reverse them using pre-computed lookup tables) $\endgroup$
    – nir shahar
    Apr 6, 2022 at 20:54
  • $\begingroup$ @nirshahar [it's] easy to reverse [cryptographic hash functions] same size input&output? Pointless, too. $\endgroup$
    – greybeard
    Apr 7, 2022 at 7:55

2 Answers 2

1
$\begingroup$

I was reading about hash functions in crypto and a website had mentioned that they were collision free, which obviously isn't possible if there are infinite input values that are mapped to outputs of a finite length.

Just wonder which site is that. If we are talking about cryptographic hash functions that this is obviously false due to the pigeonhole principle. Well, that is the most simple argument in the combinatorics that rules!

One should really read some good books before a random page on the web.

So what happens in the event of a hash collision?

That really depends on the case; for example, if you are using MD5 or SHA-1 (The collision resistance of MD5 and SHA-1 is broken!) for digital signatures for hashing the message then signature forging is easy.

For example, a secretary can prepare two documents $a$ and $b$ such that $H(a) = H(b)$ and gives their boss $a$ to sign then use $b$ on their advantage - where $a$ says 'Transfer Alice 1M' and $b$ says 'Transfer Bob 1M'.

Hopefully, cryptography comes a long way to produce hood hash functions that has collision resistance which is $2^{128}$ for SHA-256 by the birthday paradox with 50% probability.

Note that, if you trying to forge someone's signature you need the second-preimage attack that has $2^{256}$ expected cost on SHA-256.

How do crypto currencies overcome this problem?

By using a good cryptographic hash function that has good collision resistance like SHA-256. One needs to produce around $2^{128}$ documents to find a collision with 50% probability. One may argue that the 50% advantage is too high for the adversary they even can live with 0.1% advantage for which they need to produce $1.5×10^{37} \approx 2^{123}$ documents and this is still not possible. In cryptography, for such even we say negligible.

Also, this is slightly off topic, but why can't a hash value be decoded? I mean if values are being mapped, to mapped to an output finite list of encoded values why can't you reverse engineer the process? It can't be truly random there has to be a method for which a hash function maps its values right?

As D.W. noted they aimed the be one-way and this is similar to the pre-image resistance of hash functions; given a hash value $x$ it must be hard to find one input $m$ such that $H(m)=x$. The expected cost for $n$-bit hash function is $c\cdot 2^n$.

Reversing a hash function has been asked many times around. Even this is not a well-defined question. Hash functions are clearly not 1-1 functions therefore inverse of an element doesn't need to exist uniquely. Assuming that one needs to find any of them, then how wan can turn back where information is lost. Yes, the non-linear operations destroy information this is why one cannot revert hash functions easily. The computation cost of searching or making a big table is not possible ( say Rainbow). Note that although MD5 and SHA-1 has collision resistance is broken, their pre-image resistance are still there. There is no major cryptographic hash function that has lost it pre-image resistance on the literature.

Hash functions are deterministic, however, they are candidates for Random Oracles (RO) in which (analogy) there is a box in which there is a gnome with a notebook, pencil, and dice. When you asked the hash of a message, they check the list, if exists return this value, if not toss the coin n-times, write the value into the book and return the value to you. As you can see this is similar to hash functions if you ask hash of a message $m$ you get it, if you ask again $m$ then you get the same message (deterministic). If you ask a new message $m'$ that never hashed, you cannot predict that before hashing (random tosses). SHA-256 has an extra property that is not expected in RO; length extension attack, on the other hand, SHA-512/256,SHA-3,BLAKE has immunity to such attacks that makes them close to RO.

$\endgroup$
9
  • $\begingroup$ Alright but lets say a random collision occurs however unlikely that may be. What happens, would someone notice if it did? Basically what would happen to the block/blockchain itself? And how would it be fixed? $\endgroup$
    – Joe
    Apr 7, 2022 at 22:53
  • $\begingroup$ Also, if you have any recommendations for some actual quality material to read up on that would be great. I have sort of given up on google because of the amount of useless information I find. So, I came here because people seem to know what they are talking about and are very open to sharing their knowledge. $\endgroup$
    – Joe
    Apr 7, 2022 at 22:58
  • $\begingroup$ Security of the blockchain is not dependent on the collision, it is rather on finding a specific hash value, this is pre-image attack. If you find a fast method then you can use this to double spending. $\endgroup$
    – kelalaka
    Apr 7, 2022 at 22:59
  • $\begingroup$ You should say your current base knowledge and target knowledge. $\endgroup$
    – kelalaka
    Apr 7, 2022 at 23:00
  • 1
    $\begingroup$ Start from Cryptography Engineering: Design Principles and Practical Applications $\endgroup$
    – kelalaka
    Apr 7, 2022 at 23:12
1
$\begingroup$

No, hash functions are normally not collision-free. Instead, they are collision-resistant, which is different. Collision-resistant means that it is computationally difficult to find collisions, not that they don't exist.

Normally hash functions are not invertible (can't be "decoded"), often because the input space is larger than the output space, and also because they are one-way.

$\endgroup$
1
  • $\begingroup$ Alright but what happens in the even of let say an accidental collision? Like if two inputs mapped to the same output by chance? How does the algorithm compensate? $\endgroup$
    – Joe
    Apr 7, 2022 at 22:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.