REWARD offered for hash collisions for SHA1, SHA256, RIPEMD160 and other

[ymgve2]

Well, you say we can't do RIPEMD-160 directly on public keys, well I have done it and have got valid addresses, FYI, all the "theories" about the possible collisions are inaccurate, almost all of the Y coordinates could be used as X coordinates for other addresses, and vice versa.

There are only 2^32 truly unique compressed addresses and 2^32 truly unique uncompressed addresses without a single collision, that's because of the nature of 64 bit architecture in computers. Unless you didn't know about the limits of physically possible collisions where you can't have any collision under 64 bit.

I just gave you an attack vector, which has nothing to do with bitcoin, it just happens that bitcoin has put itself in the middle of 2 hash collisions ( rather who ever designed them did ).
You should ignore me, I'm just a stupid troll.

Well, you "can" do anything. You could do RIPEMD-160 on the works of Shakespeare and it will be a "valid" address, but you won't have the private key for that address since no software support Shakespeare as the key. (And no Bitcoin node supports skipping the SHA256 step)

Also where do you get the 2^32 number from? And what does it have to do with the 64 bit architecture? That's like saying there are no human numbers above 9 because we only have the digits 0-9.

Bitcoin works just fine on certain 32 bit processors, the current version has an ARM32 download link.

[digaran]

My bad about the OS arc bit confusion. But I'm not wrong about the collision, if you hash the Shakespeare to derive the address, but if you manage to get a hold of that address on bitcoin network, you'd have yourself a SHA-256 collision. Thanks to the nature of 160 bit hashes in bitcoin, we can now safely collide with a 256 bit hash only by looking in 160 bit range.

[ymgve2]

What do you even mean by "get a hold of that address on bitcoin network"? And how does something unrelated to SHA-256 result in a SHA-256 collision?

If you mean "generate address through some nonstandard means, then check if someone else used that address on the Bitcoin network", then the probability of that happening is exactly the same as if you generated a standard Bitcoin address and checked if that was used on the Bitcoin network, basically (number of addresses on the blockchain)/2^160, which would still be around 2^150, which is completely unlikely to happen by chance. And in any case, you would have a RIPEMD160 collision, not SHA256, since it is the RIPEMD160 function that would generate the same hash for two different inputs.

[BlackHatCoiner]

My bad about the OS arc bit confusion. But I'm not wrong about the collision, if you hash the Shakespeare to derive the address, but if you manage to get a hold of that address on bitcoin network, you'd have yourself a SHA-256 collision.

An SHA256 collision happens when two inputs give the same output-- different messages, same hash. If you hash a Shakespeare image or text, you need another different input to check for collision.

Thanks to the nature of 160 bit hashes in bitcoin, we can now safely collide with a 256 bit hash only by looking in 160 bit range.

If you happen to have two SHA256 hashes that begin with the same 160 first bits, it doesn't make it a collision.

[vjudeu]

Another example is trying to use less bits in a hash function. If you have SHA-1, you have IV equal to "0x67452301,0xefcdab89,0x98badcfe,0x10325476,0xc3d2e1f0", and you have k-values equal to "0x5a827999,0x6ed9eba1,0x8f1bbcdc,0xca62c1d6". There are three types of left rotations, equal to "1,5,30". You can switch from 32-bit values into 8-bit values, and produce 40-bit hashes, instead of 160-bit hashes. You can use IV equal to "0x67,0xef,0x98,0x10,0xc3", k-values equal to "0x5a,0x6e,0x8f,0xca", and left rotations, equal to "1,5,6". Then, you can produce a message, where w-values will be also 8-bit. After that, you can find some 128-bit chunk with many leading zeroes:

Code:

00 2e 35 3c
f9 80 00 00
00 00 00 00
00 00 00 28

It has "0000000093" hash, so it has eight leading nibbles, that means at least 32 leading zero bits. So far so good, but then, the question is, how to use that in real SHA-1, and produce an equivalent, so a hash with 128 leading zero bits? As I said, you will have only a random message, it won't help you in that case. And even if you check 2^40 combinations to find a full 40-bit preimage in this fake hash, it won't help you to get closer to the real 160-bit preimage, because even if many SHA-1 properties are preserved, the avalanche effect will make a complete mess, and a single different computation in the middle, will alter the whole result.

I tried that method, and found a block that can give us all zeroes in this hash:

Code:

b5 cd 37 67
28 80 00 00
00 00 00 00
00 00 00 28

I wonder how that can give us any clues to fill those gaps:

Code:

 0 | 67 ef 98 10 c3 | 67452301 efcdab89 98badcfe 10325476 c3d2e1f0
 1 | 56 67 fb 98 10 | ........ 67452301 7bf36ae2 98badcfe 10325476
 2 | fc 56 d9 fb 98 | ........ ........ 59d148c0 7bf36ae2 98badcfe
 3 | c1 fc 95 d9 fb | ........ ........ ........ 59d148c0 7bf36ae2
 4 | 89 c1 3f 95 d9 | ........ ........ ........ ........ 59d148c0
 5 | a1 89 70 3f 95 | ........ ........ ........ ........ ........
 6 | d9 a1 62 70 3f | ........ ........ ........ ........ ........
 7 | 44 d9 68 62 70 | ........ ........ ........ ........ ........
 8 | bc 44 76 68 62 | ........ ........ ........ ........ ........
 9 | bf bc 11 76 68 | ........ ........ ........ ........ ........
10 | 0b bf 2f 11 76 | ........ ........ ........ ........ ........
11 | 60 0b ef 2f 11 | ........ ........ ........ ........ ........
12 | a6 60 c2 ef 2f | ........ ........ ........ ........ ........
13 | 2c a6 18 c2 ef | ........ ........ ........ ........ ........
14 | 0e 2c a9 18 c2 | ........ ........ ........ ........ ........
15 | 15 0e 0b a9 18 | ........ ........ ........ ........ ........
16 | e7 15 83 0b a9 | ........ ........ ........ ........ ........
17 | 0f e7 45 83 0b | ........ ........ ........ ........ ........
18 | e0 0f f9 45 83 | ........ ........ ........ ........ ........
19 | b0 e0 c3 f9 45 | ........ ........ ........ ........ ........
20 | 53 b0 38 c3 f9 | ........ ........ ........ ........ ........
21 | 16 53 2c 38 c3 | ........ ........ ........ ........ ........
22 | 17 16 d4 2c 38 | ........ ........ ........ ........ ........
23 | 01 17 85 d4 2c | ........ ........ ........ ........ ........
24 | a5 01 c5 85 d4 | ........ ........ ........ ........ ........
25 | e8 a5 40 c5 85 | ........ ........ ........ ........ ........
26 | ed e8 69 40 c5 | ........ ........ ........ ........ ........
27 | 48 ed 3a 69 40 | ........ ........ ........ ........ ........
28 | 5d 48 7b 3a 69 | ........ ........ ........ ........ ........
29 | 19 5d 12 7b 3a | ........ ........ ........ ........ ........
30 | c3 19 57 12 7b | ........ ........ ........ ........ ........
31 | 89 c3 46 57 12 | ........ ........ ........ ........ ........
32 | 2f 89 f0 46 57 | ........ ........ ........ ........ ........
33 | 25 2f 62 f0 46 | ........ ........ ........ ........ ........
34 | d8 25 cb 62 f0 | ........ ........ ........ ........ ........
35 | 64 d8 49 cb 62 | ........ ........ ........ ........ ........
36 | 4f 64 36 49 cb | ........ ........ ........ ........ ........
37 | b5 4f 19 36 49 | ........ ........ ........ ........ ........
38 | 94 b5 d3 19 36 | ........ ........ ........ ........ ........
39 | 93 94 6d d3 19 | ........ ........ ........ ........ ........
40 | bc 93 25 6d d3 | ........ ........ ........ ........ ........
41 | d9 bc e4 25 6d | ........ ........ ........ ........ ........
42 | 6b d9 2f e4 25 | ........ ........ ........ ........ ........
43 | cd 6b 76 2f e4 | ........ ........ ........ ........ ........
44 | b7 cd da 76 2f | ........ ........ ........ ........ ........
45 | e7 b7 73 da 76 | ........ ........ ........ ........ ........
46 | 14 e7 ed 73 da | ........ ........ ........ ........ ........
47 | 36 14 f9 ed 73 | ........ ........ ........ ........ ........
48 | 0c 36 05 f9 ed | ........ ........ ........ ........ ........
49 | 23 0c 8d 05 f9 | ........ ........ ........ ........ ........
50 | 56 23 03 8d 05 | ........ ........ ........ ........ ........
51 | 20 56 c8 03 8d | ........ ........ ........ ........ ........
52 | c9 20 95 c8 03 | ........ ........ ........ ........ ........
53 | a8 c9 08 95 c8 | ........ ........ ........ ........ ........
54 | 78 a8 72 08 95 | ........ ........ ........ ........ ........
55 | 27 78 2a 72 08 | ........ ........ ........ ........ ........
56 | 1b 27 1e 2a 72 | ........ ........ ........ ........ ........
57 | 7e 1b c9 1e 2a | ........ ........ ........ ........ ........
58 | dd 7e c6 c9 1e | ........ ........ ........ ........ ........
59 | 1c dd 9f c6 c9 | ........ ........ ........ ........ ........
60 | 29 1c 77 9f c6 | ........ ........ ........ ........ ........
61 | 55 29 07 77 9f | ........ ........ ........ ........ ........
62 | 70 55 4a 07 77 | ........ ........ ........ ........ ........
63 | d3 70 55 4a 07 | ........ ........ ........ ........ ........
64 | db d3 1c 55 4a | ........ ........ ........ ........ ........
65 | 76 db f4 1c 55 | ........ ........ ........ ........ ........
66 | f8 76 f6 f4 1c | ........ ........ ........ ........ ........
67 | c3 f8 9d f6 f4 | ........ ........ ........ ........ ........
68 | 56 c3 3e 9d f6 | ........ ........ ........ ........ ........
69 | b5 56 f0 3e 9d | ........ ........ ........ ........ ........
70 | 8c b5 95 f0 3e | ........ ........ ........ ........ ........
71 | ec 8c 6d 95 f0 | ........ ........ ........ ........ ........
72 | b8 ec 23 6d 95 | ........ ........ ........ ........ ........
73 | 39 b8 3b 23 6d | ........ ........ ........ ........ ........
74 | 1a 39 2e 3b 23 | ........ ........ ........ ........ ........
75 | 37 1a 4e 2e 3b | ........ ........ ........ ........ ........
76 | f4 37 86 4e 2e | f0b47840 ........ ........ ........ ........
77 | c3 f4 cd 86 4e | bf36ae2b f0b47840 ........ ........ ........
78 | a1 c3 3d cd 86 | 9d148c09 bf36ae2b 3c2d1e10 ........ ........
79 | 11 a1 f0 3d cd | 10325477 9d148c09 efcdab8a 3c2d1e10 ........
80 | 99 11 68 f0 3d | 98badcff 10325477 67452302 efcdab8a 3c2d1e10
81 | 00 00 00 00 00 | 00000000 00000000 00000000 00000000 00000000

Maybe that result alone is not very helpful, but what about starting from single bits, and expanding it bit-by-bit? So, starting from SHA-1, simplified into single boolean values, it would take 16-bit chunk, will have 5-bit internal state A,B,C,D,E, and will produce 5-bit hash. Then, by adding a second bit, we will reach 10-bit hash. For the case above, 8-bit values can give us 40-bit hash. So, maybe by using that kind of expansion, there will be some hint? I will write some code to check it out.

[digaran]

I will write some code to check it out.

Isn't using ASICs much faster and since there are already mining software available you don't need to code, but that is for SHA-256 of course. However I doubt if working on SHA-1 would help you to figure out other hash functions.
Unless they all follow the same blueprint only producing larger values?
SHA-256 is extremely vulnerable and guess that's why Satoshi used them twice, because if you give a 256 bit input all the time, then the chance of producing 2 identical 256 bit outputs is extremely near impossible, in the case of SHA-256, you can use infinite number of different inputs.

Now if we compare it with bitcoin, by using hash 160 we are reducing the security of hash functions further, though that's just hash functions, bitcoin has 3 firewalls after the two hashes we have ECC. unfortunately there is financial incentive to find and exploit weaknesses, and IMO ASIC manufacturers will greatly suffer if there is a collision because nobody would buy their ASICs after that and their products would become obsolete.
I'd suggest anyone finding such collisions to give a heads up warning to big manufacturers before revealing the vulnerability.

Thank you guys for your delightful insights, I couldn't have learned this much if I wasn't here, I am proud to be amongst the elites of crypto-coders.❤

[BlackHatCoiner]

SHA-256 is extremely vulnerable

Why is SHA-256 extremely vulnerable?

that's why Satoshi used them twice, because if you give a 256 bit input all the time, then the chance of producing 2 identical 256 bit outputs is extremely near impossible

This is not correct. The fact that the SHA-256 hash of nearly every single function of Bitcoin has a 256-bit pre-image (due to double-hashing) doesn't make it more secure. The input remains the same, so the first hash remains the same.

you can use infinite number of different inputs.

To be pedantic, it's nearly infinite. SHA-256 can take up to 2^61-1 bytes as input, which is approximately 2.92 x 10^18 terabytes. The possible combinations are virtually infinite though.

unfortunately there is financial incentive to find and exploit weaknesses

I find this rather a feature. Progress comes with questioning.

[vjudeu]

Isn't using ASICs much faster

No, because ASICs can only compute hashes in a way they are designed. So, if some ASIC is designed to get 80-byte values, and hash them twice, then you cannot use it for some other purpose, and execute a different attack. You have to build a new ASIC if you want to execute things differently.

and since there are already mining software available you don't need to code

Existing software can only do brute force, and not much more than that. It can try every single value, but it won't give you solutions for reduced number of rounds, won't execute hash functions backwards, and won't allow many other things you may want to test, that will come from mathematical equations.

However I doubt if working on SHA-1 would help you to figure out other hash functions.

Working on SHA-1 is easier (and safer, because since collisions are known, then SHA-1 usage is already discouraged, so any progress will not be that harmful as it would be on SHA-256). Also, some attacks can be used on many different hash functions, because some of them have similar structure (if you know how to get all zeroes for the first 16 rounds of SHA-1, then you can use the same method to do that on SHA-256). Another thing is I don't expect to execute a successful attack, the main reason is to better understand why those things are safe.

Unless they all follow the same blueprint only producing larger values?

Internally, SHA-1 and SHA-256 use 32-bit values. Just SHA-1 uses five registers, A,B,C,D,E, and SHA-256 uses three more: F,G,H. There are also differences in internal algorithms, more K-values for SHA-256, and stronger dependencies for SHA-256, but the whole concept is similar: you have some internal state of the round, you take next 32-bit data chunk, and you compute next internal state from that, where usually some 32-bit value is altered, and the rest is only tweaked. That way or another, you work on 32-bit values, and create expressions like "a[​i+1]=rol5(a[​i])+f[​i]+e[​i]+k[​i]+w[​i]", then put known values in their places, and by having some equations like that, you try to find values matching all conditions.

SHA-256 is extremely vulnerable and guess that's why Satoshi used them twice

It is stronger than you may think. However, those hash functions are not resistant to length extension attack. So, if you know that the hash of some message is X, and you know the size of that message, then you can extend it by one block, by just putting any content, then putting '1' bit, adding a new size of the whole thing, and voila, you will have a valid hash for this extended message. But if you hash things twice, then the final hash is always computed from the single block of the same structure, and the final message has always the same size, so it cannot be extended by any attacker.

[digaran]

I hope this act as a heads up for manufacturers, miners, developers, this also could be a known fact, I haven't seen it discussed any where.
Demonstrating two collision attacks in details.

This is a unc public key:
[1]0425f587ba19c90b6e4a6606929bc6a01c44a051805797662ca2cb735dba3c009859f01d2a9e6fa d26fd0fda518271ab0dc32e9a9de6ad3b0f000bd09edfa98ca3
We perform RMD160 on it:
[3]dacb99a98b80d48adbd8b94c9a7905996503d2ab
Result:
[2]1LwtDDHxpvo6Uh9sbRTNSU7r5rukqCFRGC
Now, since there are no SHA-256 hash that long[1] if we find the actual public key of our address[2] and perform a SHA-256 on it, the resulting hash which is a 64 char long hex will produce the same RMD160[3], therefore the SHA-256 of [2]'s actual public key and our fake hash[1] of a public key collide with each other on RMD160 hash function, 2 different inputs with one unchanged output.
Second attempt, this time on SHA-256.

We take this and use it as our public key:

[6]dacb99a98b80d48adbd8b94c9a7905996503d2ab
Then we perform a SHA-256 on it to get our hash of pub ready to convert to an address:
[5]32f51406f6d584a5b62365de425d01f308fc56a33682492284cc7577ceeb8868
Now we do a RMD160 on it:
6c161fcca8bbd0fe7a393b11b0499bb0754e3f7f
And the resulting address is:
[4]1ArWUwF2WfPnDubReohn2vtPodfPpG5Evq

Once again we have arrived at the scene of a collision, if you find the actual public key of [4], and perform a SHA-256 on it, you will see that the result is the same as[5], which means [6] and the actual public key of [4] which are different in value and length etc, collide with a similar SHA-256 hash, 2 different inputs, producing 1 unchanged output.

Do that long enough on too many objects, you will have a collection of collisions, conditionally if you could find the public keys of your generated addresses though.

More over, there are some funded addresses and obviously their owners are unaware that they are holding the key to an actual collision, sooner or later people will figure this out and will exploit it, also the owners of such addresses should transfer their funds to avoid unwanted stalkers, I imagine that top level gov agencies already are aware of this, the reason for publishing this, is to prevent unexpected harm to people and to the entire crypto-system in the future.

[pooya87]

Do that long enough on too many objects, you will have a collection of collisions, conditionally if you could find the public keys of your generated addresses though.

Except that "long enough" in this context means thousands of years since there are a little less than 2²⁵⁶ public keys and you need to check about 2¹⁶⁰+1 of them to find a collision. Something that is not possible with existing hardware or in our lifetime.

More over, there are some funded addresses and obviously their owners are unaware that they are holding the key to an actual collision,

That would be like saying 2 people can choose the same atom in the universe....

[digaran]

That would be like saying 2 people can choose the same atom in the universe....

Except they have chosen the same atom due to the fact of reverse snow ball effect on SHA-256, where having an infinite combinations of different data as input will drastically increase the probability of collisions.

People always wanted to see actual collisions, I merely satisfied the general public's desire, mine as well.
I'm glad you had no comment/ mistake correction on that.

[s.john]

Second attempt, this time on SHA-256.

We take this and use it as our public key:

[6]dacb99a98b80d48adbd8b94c9a7905996503d2ab
Then we perform a SHA-256 on it to get our hash of pub ready to convert to an address:
[5]32f51406f6d584a5b62365de425d01f308fc56a33682492284cc7577ceeb8868
Now we do a RMD160 on it:
6c161fcca8bbd0fe7a393b11b0499bb0754e3f7f
And the resulting address is:
[4]1ArWUwF2WfPnDubReohn2vtPodfPpG5Evq

Once again we have arrived at the scene of a collision, if you find the actual public key of [4], and perform a SHA-256 on it, you will see that the result is the same as[5], which means [6] and the actual public key of [4] which are different in value and length etc, collide with a similar SHA-256 hash, 2 different inputs, producing 1 unchanged output.

Let's pretend there was funds in the address in your example 1ArWUwF2WfPnDubReohn2vtPodfPpG5Evq ,  still they won't be able to move those funds since they don't know the private key of that address, the steps you provided is not enough to do that.

[pooya87]

Except they have chosen the same atom due to the fact of reverse snow ball effect on SHA-256, where having an infinite combinations of different data as input will drastically increase the probability of collisions.

You mean the "avalanche effect"? That still doesn't change the fact that the probability of finding a collision is only high when you compute an unimaginably high number of hashes.
Our input is also not infinite, it is finite if we are talking about public key hashes (points on the curve which is a subgroup and finite). Although since the number is too big, it could be seen as infinite and impossible

People always wanted to see actual collisions, I merely satisfied the general public's desire, mine as well.
I'm glad you had no comment/ mistake correction on that.

I honestly didn't quite get what you said in the first part so I decided not to comment on that and let others do.

[Jason Brendon]

i haven't had time to go through all the replies here. But did anyone successfully find the collision?

[digaran]

[6]dacb99a98b80d48adbd8b94c9a7905996503d2ab

[5]32f51406f6d584a5b62365de425d01f308fc56a33682492284cc7577ceeb8868

Let's pretend there was funds in the address in your example 1ArWUwF2WfPnDubReohn2vtPodfPpG5Evq ,  still they won't be able to move those funds since they don't know the private key of that address, the steps you provided is not enough to do that.

If you hash the public key of the address above, you will get [5], if you hash [6] you'd still get [5]. And I don't know how we could spend the funds if it was loaded, I'm not trying to find people's private keys, this is about hash collisions.

"avalanche effect"?

Not applicable to SHA-256, I just exercised the method to prove avalanche effect  is an illusion, Satoshi inadvertently created an algorithm that can be used to draw a map of all SHA-256 collisions, it's like a knife cutting it's own handle.
This is as far as I am willing to go on this matter, I have decided to stop working on it and will not publish further findings, telling people 5x5=25 makes it easy, but showing them "25" makes it hard for them to figure out the proper equation. I need to confuse the outsiders, while the insiders know what 5-5-2-5 means.

i haven't had time to go through all the replies here. But did anyone successfully find the collision?

No, we are just talking about how to easily find them, one way is brute force, other way is beyond my comprehension, you should read "vjudeu's posts to know what I mean.😉

Even if we find a collision, we must not publicly disclose it to the world, instead we should convince the world that the algorithm "is no longer secure".
If anyone is interested to further discussing the issue, come and visit my special penthouse at digaran's tower.

[ymgve2]

i haven't had time to go through all the replies here. But did anyone successfully find the collision?

If someone found a SHA256 collision it would be all over tech news. The only collision so far is the SHA1 one, where someone simply copied the collision published by Google at https://security.googleblog.com/2017/02/announcing-first-sha1-collision.html.

[Jason Brendon]

is SHA512 better than SHA256? if yes, why don't we use that?

[ABCbits]

is SHA512 better than SHA256? if yes, why don't we use that?

First of all, define "better". SHA-512 probably have better collision better resistance due to longer output, but SHA-256 have shorter output which save bandwidth/storage which have some importance when using Bitcoin. And if we're looking for better hash algorithm, we probably should look for to more modern/secure standard rather than SHA-2 standard (such as SHA-256 and SHA-512).

[digaran]

Question regarding hash functions:
Do they all operate based on 2 character set hexadecimal or we can hash a single hex character as well?
I'm asking this because I have found 2 strings with only 1 character difference having the same digest, maybe it's a bug?
Like if they are not supposed to give you any hash for a single bit, then all the 16 bit hex chars used bit by bit should never produce a hash while they do, so why is it when I use a 30 long char hex string and a 31 long char string they both produce the same output?

*For example: "1234567890" and "12345678901" give me the same output.

*=Fake example.

Real example: "1" and "01" give this "4bf5122f344554c53bde2ebb8cd2b7e3d1600ad631c385a5d7cce23c7785459a"

Am I missing something?
And please don't tell me the algorithm pads a 0 to 1 when we only use 1 as input, because I have 2 strings not starting with a 0 but have the same hash.

[ymgve2]

Question regarding hash functions:
Do they all operate based on 2 character set hexadecimal or we can hash a single hex character as well?
I'm asking this because I have found 2 strings with only 1 character difference having the same digest, maybe it's a bug?
Like if they are not supposed to give you any hash for a single bit, then all the 16 bit hex chars used bit by bit should never produce a hash while they do, so why is it when I use a 30 long char hex string and a 31 long char string they both produce the same output?

*For example: "1234567890" and "12345678901" give me the same output.

*=Fake example.

Real example: "1" and "01" give this "4bf5122f344554c53bde2ebb8cd2b7e3d1600ad631c385a5d7cce23c7785459a"

Am I missing something?
And please don't tell me the algorithm pads a 0 to 1 when we only use 1 as input, because I have 2 strings not starting with a 0 but have the same hash.

Whatever you use to calculate hashes is broken and deletes leading nulls.


SHA-256 can technically be used on an arbitrary number of bits that don't divide by 8, but in practice no implementations ever use that feature, and only do full byte sequences.