1
$\begingroup$

I'm reading about hash functions at the moment, and in the book I'm reading there's a section on multicollisions. Specifically, using a 2-collision to find $2^N$ collisions in $N2^N$ time.

If, theoretically, a collision was found which was valid for cryptocurrency mining (however many 0s on the end), couldn't one find a large number of blocks which also collide with that, allowing them to be much more efficient than other miners?

Is my understanding of multicollisions correct? If so, is the difficulty of finding a 2-collision the only thing preventing this from being done?

Improve this question
$\endgroup$
2
  • $\begingroup$ @kelalaka So only the difficulty of finding a collision is what prevents this from being used? $\endgroup$ – Redwolf Programs Apr 26 '20 at 18:03
  • $\begingroup$ @kelalaka Ah, I guess I'm getting my terminology mixed up. I guess I also didn't think about the fact that to find the preimage one would find many more values with leading zeroes than by using multicollisions. Thanks! (btw, I'm reading Serious Cryptography by Jean Philippe Aumasson) $\endgroup$ – Redwolf Programs Apr 26 '20 at 18:53
3
$\begingroup$

In the Bitcoin mining, hashcash version 2 (2002), one looks for the input $m$ such that $\operatorname{SHA256d}(m)$ is the desired output hash value that is below the current threshold of zeros. In other words $$\operatorname{SHA256d}(x)/2^{(n-k)} = 0$$ where $k$ is the work factor, that is the number of leading zeros and $n$ is the output size that is 256 for SHA256. This was before factional is introduced;

$$\operatorname{SHA256d}(x)< 2^{(n-k)} $$

The required threshold is given therefore one look for the pre-images, that is given the hash value $x$ find a pre-image that the $\operatorname{SHA256d}(m) < \text{threshold}$. Since we are looking for a threshold the search easier than the preimage attack and still harder than the collision attack.

Note that BitCoin defines a term for this search pre-image with a partial output match.

The search doubles when the number of leading zeros is incremented by one. Therefore it is getting harder and harder. If someone is so lucky then they can find some of the required values easily but this probability is so lower than hitting your head with a meteorite!

The bitcoin miners reached $2^{92}$ double SHA2 searches in a year. If you consider that they find the block in one, they need two years, on average, or double the hardware and therefore the power consumption.

Is my understanding of multi collision correct? If so, is the difficulty of finding a 2-collision the only thing preventing this from being done?

Yes, one firstly needs to find the collisions to apply multi-collisions. And, SHA256 is far from finding one.

Note: Finding pre-image is harder than collision attacks. The Cryptographic hash functions like MD5 and SHA-1 are collisionally broken since one can find collisions better than the generic collision attack, which is given by the birthday attack. However, none of the cryptographic hash functions, including the MD5 and SHA-1, are vulnerable to pre-image attacks. Currently, $\operatorname{SHA256}$ requires around $2^{256}$ hash computations to find a pre-image. Actually, during the search one can find nearly all the pre-images that have hash values with leading zeros.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Yes, the argument that multi-collisions alone do not apply now stands. But there's another issue: if multi-collisions where possible in SHA-256 for the so-called header part of $m$ that's hashed in mining (described here), then indeed the later mining work for that block would apply for all the multi-colliding headers, as envisioned in the question. It so happens that the header is too short and too constrained for multi-collisions. I want to stay at distance from bitcoin (which I consider a nuisance) thus won't make that an answer. $\endgroup$ – fgrieu♦ Apr 26 '20 at 21:04
  • $\begingroup$ @fgrieu AFAIK, one cannot control the output in the multi-collision. Also, for a multi-collision, firstly one needs collisions. $\endgroup$ – kelalaka Apr 26 '20 at 21:38
  • $\begingroup$ Even if we do not initially control the output of a multi-collision, we can extend it. Assume we have one with $N$ messages $m_i$ (of the same length) colliding per SHA-256 (thus SHA256d). We can make an appendix $a$ such that the SHA256d of each $m_i\mathbin\|a$ is below $2^{210}$, at an average cost of $2^{47}$ SHA-256 compressions. That's $2^{47}/N$ per message. The main reason that it does not work in the bitcoin context is because we can't make collisions at all for SHA-256, much less multi-collisions with the small size allowed by the header, and the constraints it has. $\endgroup$ – fgrieu♦ Apr 27 '20 at 6:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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