Bitcoin Forum
May 14, 2024, 12:07:23 PM *
News: Latest Bitcoin Core release: 27.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: 1 2 3 [All]
  Print  
Author Topic: Example of BTC collision (2 different priv key to the same BTC address)  (Read 1345 times)
MrFreeDragon (OP)
Sr. Member
****
Offline Offline

Activity: 443
Merit: 350


View Profile
September 18, 2019, 03:36:18 PM
 #1

There are almost 2^256 possible private keys, and every key could be used to generate the BTC address. However the amount of possible BTC addresses is only 2^160 (because of ripemd160 hash function).

Is there any real example of at least 2 (or may be more) DIFFERENT private keys resulting to the same bitcoin address?

Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction.
1715688443
Hero Member
*
Offline Offline

Posts: 1715688443

View Profile Personal Message (Offline)

Ignore
1715688443
Reply with quote  #2

1715688443
Report to moderator
Rath_
aka BitCryptex
Legendary
*
Offline Offline

Activity: 1876
Merit: 3131



View Profile
September 18, 2019, 03:55:22 PM
Last edit: September 19, 2019, 06:39:27 AM by BitCryptex
Merited by Quickseller (1)
 #2

Is there any real example of at least 2 (or may be more) DIFFERENT private keys resulting to the same bitcoin address?

Take a look at the Large Bitcoin Collider project. See this post. They have managed to find a few collisions. This page describes in detail what kind of collision the pool is looking for.
MrFreeDragon (OP)
Sr. Member
****
Offline Offline

Activity: 443
Merit: 350


View Profile
September 18, 2019, 04:05:56 PM
Last edit: September 18, 2019, 04:16:17 PM by MrFreeDragon
 #3

Is there any real example of at least 2 (or may be more) DIFFERENT private keys resulting to the same bitcoin address?

Take a look at the Large Bitcoin Collider project. They have managed to find a few collisions. This page describes in detail what kind of collision the pool is looking for.

Thank you. I have already read that project before making a post here.
LBC just are finding the private key to the address with the balance. Most of their found addresses were just addreses from 32 BTC transaction puzzle.

My question here is about REAL example of at leat two different private keys leading to the same bitcoin address. And it does not matter if that address has the balance.

AdolfinWolf
Legendary
*
Offline Offline

Activity: 1946
Merit: 1427


View Profile
September 18, 2019, 05:54:58 PM
Last edit: September 18, 2019, 06:09:31 PM by AdolfinWolf
 #4



Thank you. I have already read that project before making a post here.
LBC just are finding the private key to the address with the balance. Most of their found addresses were just addreses from 32 BTC transaction puzzle.

My question here is about REAL example of at leat two different private keys leading to the same bitcoin address. And it does not matter if that address has the balance.
Without an exploit of sorts, i think it is highly unlikely that that has happend (or could happen.).

Quote
Actually finding any pair of different private keys that generate the same public key or address would be quite difficult. Either it would involve a huge amount of computation and/or luck, or it would be due to finding a serious vulnerability in the algorithm(s) used.
See: https://bitcoin.stackexchange.com/a/25071


This user posts an interesting answer which i don't fully understand to what exactly it refers to: https://bitcoin.stackexchange.com/a/27027
Anyone cares to explain?

MrFreeDragon (OP)
Sr. Member
****
Offline Offline

Activity: 443
Merit: 350


View Profile
September 18, 2019, 08:08:01 PM
Merited by AdolfinWolf (1)
 #5

This user posts an interesting answer which i don't fully understand to what exactly it refers to: https://bitcoin.stackexchange.com/a/27027
Anyone cares to explain?

Thank you for sharing!

That user explains that the private keys out of order (bitcoin order is FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141, it is the total amount of ECDSA curve points) result to the same BTC addresses from the start.
As an example, the private keys 000000000000000000000000000000014551231950b75fc4402da1732fc9bebb and fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffc leads to the same bitcoin address 136jNVfhtp7mKVfHjfkBcay1cbMG8GsC5Z (compressed).
Good finding!

However i want to find 2 different private keys inside the order leading to the same BTC address

gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4172
Merit: 8420



View Profile WWW
September 18, 2019, 10:26:00 PM
Merited by pooya87 (2), xandry (2), LoyceV (2), Quickseller (2), Rath_ (2), ABCbits (1), DaCryptoRaccoon (1)
 #6

Take a look at the Large Bitcoin Collider project.
That project is a malware scam. They promote their activity using jibberish technobabble and have been caught distributing actual backdoored software.
nc50lc
Legendary
*
Offline Offline

Activity: 2408
Merit: 5604


Self-proclaimed Genius


View Profile
September 19, 2019, 02:23:27 AM
Merited by xandry (1), LoyceV (1), Rath_ (1)
 #7

Is there any real example of at least 2 (or may be more) DIFFERENT private keys resulting to the same bitcoin address?
Take a look at the Large Bitcoin Collider project. They have managed to find a few collisions. This page describes in detail what kind of collision the pool is looking for.
Those "collisions" aren't really collisions.
They mostly hunt for purposely generated "weak" private keys, for example: this puzzle transaction.

That example contains addresses derived from private keys ranging from
0000000000000000000000000000000000000000000000000000000000000001 to
000000000000000000000000000000000000000af55fc59c335c8ec67ed24826 and so on...
which apparently, can be bruteforced with enough computing power.

█▀▀▀











█▄▄▄
▀▀▀▀▀▀▀▀▀▀▀
e
▄▄▄▄▄▄▄▄▄▄▄
█████████████
████████████▄███
██▐███████▄█████▀
█████████▄████▀
███▐████▄███▀
████▐██████▀
█████▀█████
███████████▄
████████████▄
██▄█████▀█████▄
▄█████████▀█████▀
███████████▀██▀
████▀█████████
▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀
c.h.
▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄
▀▀▀█











▄▄▄█
▄██████▄▄▄
█████████████▄▄
███████████████
███████████████
███████████████
███████████████
███░░█████████
███▌▐█████████
█████████████
███████████▀
██████████▀
████████▀
▀██▀▀
MrFreeDragon (OP)
Sr. Member
****
Offline Offline

Activity: 443
Merit: 350


View Profile
September 19, 2019, 09:53:26 AM
 #8

However i want to find 2 different private keys inside the order leading to the same BTC address
Likely you will not able to find it, and I don't think it will happen even future. A single btc address could not be belongs to two or more private keys. If so, then fund will be stolen from the first address. Because when you will see that you new genarated address contained with fund then likely you will move it to another address. And I don't think blockchain designed like that.

I understand that it is very unlikely. But a BTC address is created from the private key. The total possible private keys are almost 2^256 (to be exact: FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141). The public key is also within the same range. However, later due to hash operations (SHA256 and ripemd160), the total possible combinations of final addresses is only 2^160. So, statistically each address on average could have 2^(256-160) = 2^96 possible private keys which is very large number: 79 228 162 514 264 337 593 543 950 336 (roundly 10^29). So, there should be the situation there several DIFFERENT private keys within the bitcoin order lead to the same bitcoin address.

You stated that "A single btc address could not be belongs to two or more private keys", but how is it true if the total possible combinations of bitcoin legacy addresses are 2^96 times less than the total possible combinations of priivate keys?

DaCryptoRaccoon
Hero Member
*****
Offline Offline

Activity: 1208
Merit: 587


OGRaccoon


View Profile
September 19, 2019, 11:19:53 AM
Merited by malevolent (1)
 #9

However i want to find 2 different private keys inside the order leading to the same BTC address
Likely you will not able to find it, and I don't think it will happen even future. A single btc address could not be belongs to two or more private keys. If so, then fund will be stolen from the first address. Because when you will see that you new genarated address contained with fund then likely you will move it to another address. And I don't think blockchain designed like that.

I understand that it is very unlikely. But a BTC address is created from the private key. The total possible private keys are almost 2^256 (to be exact: FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141). The public key is also within the same range. However, later due to hash operations (SHA256 and ripemd160), the total possible combinations of final addresses is only 2^160. So, statistically each address on average could have 2^(256-160) = 2^96 possible private keys which is very large number: 79 228 162 514 264 337 593 543 950 336 (roundly 10^29). So, there should be the situation there several DIFFERENT private keys within the bitcoin order lead to the same bitcoin address.

You stated that "A single btc address could not be belongs to two or more private keys", but how is it true if the total possible combinations of bitcoin legacy addresses are 2^96 times less than the total possible combinations of priivate keys?

This is why brainflayer runs against a bloom filter of ripemd160 hashes instead of the actual main address it hunts for the corresponding PK value in relation to the Ripemd160 hashes.
it's also open source unlike the Large Bitcoin  MALWARE Collider posted above.

https://github.com/ryancdotorg/brainflayer

┏━━━━━━━━━━━━━━━━━┓
┃   💎 Mine Solo with CKPool 💎    ┃
┃    ➤ Hit Blocks on Your Own!      ┃
┃ ███▓▓  ███▓▓  ███▓▓  ███▓▓┃
AdolfinWolf
Legendary
*
Offline Offline

Activity: 1946
Merit: 1427


View Profile
September 19, 2019, 12:53:02 PM
Merited by ABCbits (1)
 #10

And I don't think blockchain designed like that.
Except that it is possible. See the quote above, (or below)

Yes, you can have two keys generate the same address.

There are 2^160 possible addresses, and 2^256 possible private keys, so each address corresponds to roughly 2^(256-160)=2^96 private keys. Any of these will generate the same address and thus be able to spend the money owned by that address. Since 2^160 is so large, however, it would take a near-eternity to find any collisions.

Whether two private keys can generate the same public key is another question. I think the answer is yes, but I am not sure on that. The public key in uncompressed form consists of two 256-bit numbers, which are X and Y coordinates on an elliptic curve. However, the compressed form is just the X coordinate plus a bit, from which you can calculate the whole public key. This means the space is (at most) 2^257. Unless there is a one-to-one mapping due to the mathematical properties of the cryptography used, each compressed public key corresponds to roughly 0.5 private keys (with the same distribution you'd get from picking a random number from 1 to 2^257, 2^256 times), so some private keys will collide, while others will not.

Actually finding any pair of different private keys that generate the same public key or address would be quite difficult. Either it would involve a huge amount of computation and/or luck, or it would be due to finding a serious vulnerability in the algorithm(s) used.

odolvlobo
Legendary
*
Offline Offline

Activity: 4312
Merit: 3214



View Profile
September 19, 2019, 06:28:26 PM
 #11

There are almost 2^256 possible private keys, and every key could be used to generate the BTC address. However the amount of possible BTC addresses is only 2^160 (because of ripemd160 hash function).

Is there any real example of at least 2 (or may be more) DIFFERENT private keys resulting to the same bitcoin address?

Answering your question ... So far there is no known collision.

Furthermore, the probability of a collision ever occurring by chance is extremely low. Imagine that 10 billion transactions, each with a new address, are added to the block chain every year for 1 million years. That's about 253 transactions, which is still very negligible compared to 2160.

Join an anti-signature campaign: Click ignore on the members of signature campaigns.
PGP Fingerprint: 6B6BC26599EC24EF7E29A405EAF050539D0B2925 Signing address: 13GAVJo8YaAuenj6keiEykwxWUZ7jMoSLt
kzv
Legendary
*
Offline Offline

Activity: 1722
Merit: 1285

OpenTrade - Open Source Cryptocurrency Exchange


View Profile WWW
September 20, 2019, 12:50:42 PM
 #12

When you find a collision, you can get your reward in BTC:
SHA256 collision cost 0.27609251 BTC
RIPEMD160 collision cost 0.11476888 BTC
RIPEMD160(SHA256()) collision cost 0.10026873 BTC
SHA256(SHA256()) collision cost 0.10026873 BTC

Read original topic of the bounty https://bitcointalk.org/index.php?topic=293382.msg3142575#msg3142575

OpenTrade - Open Source Cryptocurrency Exchange
MrFreeDragon (OP)
Sr. Member
****
Offline Offline

Activity: 443
Merit: 350


View Profile
September 21, 2019, 11:01:18 AM
 #13

When you find a collision, you can get your reward in BTC:
SHA256 collision cost 0.27609251 BTC
RIPEMD160 collision cost 0.11476888 BTC
RIPEMD160(SHA256()) collision cost 0.10026873 BTC
SHA256(SHA256()) collision cost 0.10026873 BTC

Read original topic of the bounty https://bitcointalk.org/index.php?topic=293382.msg3142575#msg3142575

Thank you for sharing! I wanted to find such collision just for my curiosity, however it also could be paid   Roll Eyes
Can you please explain how did you calculate these bounties for each collision?

MrFreeDragon (OP)
Sr. Member
****
Offline Offline

Activity: 443
Merit: 350


View Profile
September 22, 2019, 03:04:02 AM
 #14


Regarding your original question i must admit I have found such addressess and possess the private key for it, but cannot for various reason share which one and how I came in possession of it.

/KX

This was the exact thing i want to know   Huh If you can not tell everything, can you just say how many private keys do you have to the same address? And also how many addresses do you have with more than one private key?

pooya87
Legendary
*
Offline Offline

Activity: 3444
Merit: 10562



View Profile
September 22, 2019, 04:18:16 AM
 #15

can you just say how many private keys do you have to the same address? And also how many addresses do you have with more than one private key?

we are not "mapping" keys to addresses to have 1:X ratio. we are hashing the public key which returns a random result so there is no fixed ratio. there is a chance of collision because the hash size (160 bits) is smaller than the number of private keys (a little less than 256 bit) but so far nobody has found any collisions and will not find any for a very long time. anybody who claims otherwise without proof is most probably lying.

.
.BLACKJACK ♠ FUN.
█████████
██████████████
████████████
█████████████████
████████████████▄▄
░█████████████▀░▀▀
██████████████████
░██████████████
████████████████
░██████████████
████████████
███████████████░██
██████████
CRYPTO CASINO &
SPORTS BETTING
▄▄███████▄▄
▄███████████████▄
███████████████████
█████████████████████
███████████████████████
█████████████████████████
█████████████████████████
█████████████████████████
███████████████████████
█████████████████████
███████████████████
▀███████████████▀
█████████
.
MrFreeDragon (OP)
Sr. Member
****
Offline Offline

Activity: 443
Merit: 350


View Profile
September 22, 2019, 07:00:15 PM
 #16

can you just say how many private keys do you have to the same address? And also how many addresses do you have with more than one private key?

we are not "mapping" keys to addresses to have 1:X ratio. we are hashing the public key which returns a random result so there is no fixed ratio. there is a chance of collision because the hash size (160 bits) is smaller than the number of private keys (a little less than 256 bit) but so far nobody has found any collisions and will not find any for a very long time. anybody who claims otherwise without proof is most probably lying.

As for the ratio I knoe that this ratio could not be. There just ann average chance that one address could have 2^96 private keys.
I asked "how many" because this guy wrote that he had such keys, but didnot want to give the example and did not say the reason why he cuuld not tell:


Regarding your original question i must admit I have found such addressess and possess the private key for it, but cannot for various reason share which one and how I came in possession of it.

/KX

bartekjagoda
Jr. Member
*
Offline Offline

Activity: 87
Merit: 5


View Profile
September 25, 2019, 06:13:56 PM
 #17

can you just say how many private keys do you have to the same address? And also how many addresses do you have with more than one private key?

we are not "mapping" keys to addresses to have 1:X ratio. we are hashing the public key which returns a random result so there is no fixed ratio. there is a chance of collision because the hash size (160 bits) is smaller than the number of private keys (a little less than 256 bit) but so far nobody has found any collisions and will not find any for a very long time. anybody who claims otherwise without proof is most probably lying.

As for the ratio I knoe that this ratio could not be. There just ann average chance that one address could have 2^96 private keys.
I asked "how many" because this guy wrote that he had such keys, but didnot want to give the example and did not say the reason why he cuuld not tell:


Regarding your original question i must admit I have found such addressess and possess the private key for it, but cannot for various reason share which one and how I came in possession of it.

/KX

And post got deleted.

 Ich liebe Bitcoin
turndealer
Newbie
*
Offline Offline

Activity: 16
Merit: 3


View Profile
October 05, 2019, 10:14:24 AM
 #18

can you just say how many private keys do you have to the same address? And also how many addresses do you have with more than one private key?

we are not "mapping" keys to addresses to have 1:X ratio. we are hashing the public key which returns a random result so there is no fixed ratio. there is a chance of collision because the hash size (160 bits) is smaller than the number of private keys (a little less than 256 bit) but so far nobody has found any collisions and will not find any for a very long time. anybody who claims otherwise without proof is most probably lying.

As for the ratio I knoe that this ratio could not be. There just ann average chance that one address could have 2^96 private keys.
I asked "how many" because this guy wrote that he had such keys, but didnot want to give the example and did not say the reason why he cuuld not tell:


Regarding your original question i must admit I have found such addressess and possess the private key for it, but cannot for various reason share which one and how I came in possession of it.

/KX

Talking about Wif format

Here are some privatekeys Leading to same addresses [Compressed and Uncompressed]

KxqjPLtQqydD8d6eUrpJ7Q1266k8Mw8f5eoyEztY3Kc6jtMsgkXp
cPCirFtGH3KUJ4ZusGdRUiW5iL3Y2PEM9gxSMRM3YSG6Eon9heJj
5JBb5A38fjjeBnngkvRmCsXN6EY4w8jWvckik3hDvYQMnakxLRd

Leads to
1C4LeCvgTFJJjxiuPMGgW26PAqmfEBfSL5 [Compressed]
1DU46StbrH652jBv7dE8DWMg4rTRy2rU5W [Uncompressed]

Thanks
PrivatePerson
Member
**
Offline Offline

Activity: 173
Merit: 12


View Profile
October 05, 2019, 10:46:15 AM
 #19

Privkeys:
KwDiBf89QgGbjEhKnhXJuH7LrciVrZi3qYpCemuaUp7NigjvtJug
L5oLkpV3aqBjhki6LmvChTCV6odsp4SXM6LBVeqHTSj1w9XhwfuR   (outside of bitcoins curve range)
Address:
1Me6EfpwZK5kQziBwBfvLiHjaPGxCKLoJi
BrewMaster
Legendary
*
Offline Offline

Activity: 2114
Merit: 1292


There is trouble abrewing


View Profile
October 05, 2019, 11:17:55 AM
Merited by aliashraf (1)
 #20

Here are some privatekeys Leading to same addresses

there are different ways of representing numbers:
Code:
1
I
one
0x01
00000001
but it doesn't mean we have dozens of number one! we only have 1 value that we use different encodings for it to represent it (numeral, roaman, text, hex, binary). what you did here was only to change the encoding.
and what you did here is just playing with modular arithmetic.

neither one of these have anything to do with this topic: collision.

There is a FOMO brewing...
nc50lc
Legendary
*
Offline Offline

Activity: 2408
Merit: 5604


Self-proclaimed Genius


View Profile
October 05, 2019, 11:51:48 AM
 #21

Here are some privatekeys Leading to same addresses [Compressed and Uncompressed]

KxqjPLtQqydD8d6eUrpJ7Q1266k8Mw8f5eoyEztY3Kc6jtMsgkXp
-snip-
5JBb5A38fjjeBnngkvRmCsXN6EY4w8jWvckik3hDvYQMnakxLRd

Leads to
1C4LeCvgTFJJjxiuPMGgW26PAqmfEBfSL5 [Compressed]
1DU46StbrH652jBv7dE8DWMg4rTRy2rU5W [Uncompressed]
Those "two" WIF private keys aren't different, those are basically the same private key:
305E293B010D29BF3C888B617763A438FEE9054C8CAB66EB12AD078F819D9F7F
There's no collision there.

BTW, if you just base it from their WIF format, both private keys derived different addresses Roll Eyes

█▀▀▀











█▄▄▄
▀▀▀▀▀▀▀▀▀▀▀
e
▄▄▄▄▄▄▄▄▄▄▄
█████████████
████████████▄███
██▐███████▄█████▀
█████████▄████▀
███▐████▄███▀
████▐██████▀
█████▀█████
███████████▄
████████████▄
██▄█████▀█████▄
▄█████████▀█████▀
███████████▀██▀
████▀█████████
▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀
c.h.
▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄
▀▀▀█











▄▄▄█
▄██████▄▄▄
█████████████▄▄
███████████████
███████████████
███████████████
███████████████
███░░█████████
███▌▐█████████
█████████████
███████████▀
██████████▀
████████▀
▀██▀▀
MrFreeDragon (OP)
Sr. Member
****
Offline Offline

Activity: 443
Merit: 350


View Profile
October 08, 2019, 12:04:12 AM
 #22

Privkeys:
KwDiBf89QgGbjEhKnhXJuH7LrciVrZi3qYpCemuaUp7NigjvtJug
L5oLkpV3aqBjhki6LmvChTCV6odsp4SXM6LBVeqHTSj1w9XhwfuR   (outside of bitcoins curve range)
Address:
1Me6EfpwZK5kQziBwBfvLiHjaPGxCKLoJi

Thank you Smiley But this "playing" is known to me as well.
I'm not sure if you understand how these keys were received. I made the same example some weeks ago.

I just add the order to the private key 363d541eb611abee and received the outside private fffffffffffffffffffffffffffffffebaaedce6af48a03bf60fb2ab8647ed2f
But it is not a collision. It just play with a modular mathematics. This works beacuse the private keys are repeating after the order (the order actually is 0 in bitcoin EDCSA math).

I want to find at least two (better more of course) private keys within the bitcoin range and leading to the same btc address.

PS. It looks like you took my own example from another topic and post it here  Huh
Here is my post with the same example: https://bitcointalk.org/index.php?topic=5166284.msg52493665#msg52493665

PrivatePerson
Member
**
Offline Offline

Activity: 173
Merit: 12


View Profile
October 08, 2019, 05:30:15 AM
 #23

PS. It looks like you took my own example from another topic and post it here  Huh

Yes, I did not pay attention to who is the creator of this topic Smiley
DannyHamilton
Legendary
*
Offline Offline

Activity: 3388
Merit: 4653



View Profile
October 08, 2019, 04:40:51 PM
 #24


I want to find at least two (better more of course) private keys within the bitcoin range and leading to the same btc address.


What you are looking for is either one of the following to have occurred:

  • A SHA256 collision (2 different inputs that result in the exact same SHA256 outputs)
  • A RIPEMD160 collision (2 different inputs that result in the exact same RIPEMD160 outputs)

To my knowledge, there is no record of either having ever occurred (in Bitcoin or otherwise).
MrFreeDragon (OP)
Sr. Member
****
Offline Offline

Activity: 443
Merit: 350


View Profile
October 08, 2019, 04:56:41 PM
 #25


I want to find at least two (better more of course) private keys within the bitcoin range and leading to the same btc address.


What you are looking for is either one of the following to have occurred:

  • A SHA256 collision (2 different inputs that result in the exact same SHA256 outputs)
  • A RIPEMD160 collision (2 different inputs that result in the exact same RIPEMD160 outputs)

To my knowledge, there is no record of either having ever occurred (in Bitcoin or otherwise).


Any of these collission will be good as both will lead to the situation where 2 different private keys will result to the same bitcoin address. As ECDSA bitcoin curve guarantees to us that there is only one public key to every private key, so the collision could be only during the public key transormation to the address.
So, you are absolutely right that the collision is in SHA256 or RIPEMD160. But considering the facts that SHA256 transforms 256bit public key (as input) to 256bit output, but RIPEMD160 transforms 256bit to 160bit, so the highly likely the collision is in RIPEMD160 function.

DannyHamilton
Legendary
*
Offline Offline

Activity: 3388
Merit: 4653



View Profile
October 08, 2019, 06:59:34 PM
Merited by aliashraf (1)
 #26

considering the facts that SHA256 transforms 256bit public key (as input) to 256bit output, but RIPEMD160 transforms 256bit to 160bit, so the highly likely the collision is in RIPEMD160 function.

That depends on what you mean by highly likely.

It is much MORE likely that it will occur in the RIPEMD160 transform than in the SHA256 transform, but that's a bit like saying that it is much MORE likely that a completely fair coin will land on heads 160 times in a row than 256 times in a row.  In both cases it is *VERY* unlikely.

Essentially we are talking about the difference between "It isn't going to happen" and "It isn't going to happen".

The exception to this would be if a mathematician were to discover some currently unknown weakness in the algorithm which allows for a practical technique to generate a collision. In that case such a weakness is no more likely to be discovered in SHA256 than in RIPEMD160.

Furthermore, a discovery of an exploitable weakness in either hash would still require the ability to calculate an ECDSA private key from it's public key (currently not possible).  Otherwise, it won't be possible for someone to find the private key needed to cause the collision.
MrFreeDragon (OP)
Sr. Member
****
Offline Offline

Activity: 443
Merit: 350


View Profile
October 08, 2019, 07:22:09 PM
 #27

considering the facts that SHA256 transforms 256bit public key (as input) to 256bit output, but RIPEMD160 transforms 256bit to 160bit, so the highly likely the collision is in RIPEMD160 function.

That depends on what you mean by highly likely.

It is much MORE likely that it will occur in the RIPEMD160 transform than in the SHA256 transform, but that's a bit like saying that it is much MORE likely that a completely fair coin will land on heads 160 times in a row than 256 times in a row.  In both cases it is *VERY* unlikely.

Essentially we are talking about the difference between "It isn't going to happen" and "It isn't going to happen".

I used the incorrect words to descripbe. Of course the probability is highly unlikely, it is actually impossible. And for me as 2^256, so 2^160 are both very high numbers, and the probabilities 1/2^256 and 1/2^160 are actually 0%.

I just had in mind the probable place of collision if such collision is found. Let's say Key1 and Key2 are 2 keys leading to the same Address. So, it is more likely that public keys PubKey1 and PubKey2 are different. Then it is also more likely that SHA256 of PubKey1 and SHA256 of PubKey2 will be different. But the collision is in RIPEMD160 function transforming different SHA256(PubKey1) and SHA256(PubKey2) to the same hash, and then to the sme Address.

nc50lc
Legendary
*
Offline Offline

Activity: 2408
Merit: 5604


Self-proclaimed Genius


View Profile
October 09, 2019, 08:25:09 AM
 #28

I just had in mind the probable place of collision if such collision is found. Let's say Key1 and Key2 are 2 keys leading to the same Address. So, it is more likely that public keys PubKey1 and PubKey2 are different. Then it is also more likely that SHA256 of PubKey1 and SHA256 of PubKey2 will be different. But the collision is in RIPEMD160 function transforming different SHA256(PubKey1) and SHA256(PubKey2) to the same hash, and then to the sme Address.
Indeed, for legacy addresses.
If the RIPEMD160 hash of the SHA256 hash of the private key was the same, the final address will be the same.
Since after hashing the Pub key using SHA256, the result will be hashed using RIPEMD160 and the next few steps will only be based from the second hash's result.

But that will only happen if there will be a RIPEMD160 collision.
And as you know it, its collision resistance is pretty "strong" at 280.

█▀▀▀











█▄▄▄
▀▀▀▀▀▀▀▀▀▀▀
e
▄▄▄▄▄▄▄▄▄▄▄
█████████████
████████████▄███
██▐███████▄█████▀
█████████▄████▀
███▐████▄███▀
████▐██████▀
█████▀█████
███████████▄
████████████▄
██▄█████▀█████▄
▄█████████▀█████▀
███████████▀██▀
████▀█████████
▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀
c.h.
▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄
▀▀▀█











▄▄▄█
▄██████▄▄▄
█████████████▄▄
███████████████
███████████████
███████████████
███████████████
███░░█████████
███▌▐█████████
█████████████
███████████▀
██████████▀
████████▀
▀██▀▀
MrFreeDragon (OP)
Sr. Member
****
Offline Offline

Activity: 443
Merit: 350


View Profile
October 09, 2019, 09:06:47 AM
 #29

But that will only happen if there will be a RIPEMD160 collision.
And as you know it, its collision resistance is pretty "strong" at 280.

So, what is the practice way to find this collision? Is there any better way rather than straight brute force and luck?

nc50lc
Legendary
*
Offline Offline

Activity: 2408
Merit: 5604


Self-proclaimed Genius


View Profile
October 09, 2019, 10:58:42 AM
 #30

So, what is the practice way to find this collision? Is there any better way rather than straight brute force and luck?
For its usage with Bitcoin to generate an address,
I'd say, it's pure luck since you can't pre-define the SHA256 hash of the public key.

█▀▀▀











█▄▄▄
▀▀▀▀▀▀▀▀▀▀▀
e
▄▄▄▄▄▄▄▄▄▄▄
█████████████
████████████▄███
██▐███████▄█████▀
█████████▄████▀
███▐████▄███▀
████▐██████▀
█████▀█████
███████████▄
████████████▄
██▄█████▀█████▄
▄█████████▀█████▀
███████████▀██▀
████▀█████████
▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀
c.h.
▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄
▀▀▀█











▄▄▄█
▄██████▄▄▄
█████████████▄▄
███████████████
███████████████
███████████████
███████████████
███░░█████████
███▌▐█████████
█████████████
███████████▀
██████████▀
████████▀
▀██▀▀
ABCbits
Legendary
*
Offline Offline

Activity: 2870
Merit: 7497


Crypto Swap Exchange


View Profile
October 09, 2019, 06:20:01 PM
Merited by aliashraf (1)
 #31

But that will only happen if there will be a RIPEMD160 collision.
And as you know it, its collision resistance is pretty "strong" at 280.

So, what is the practice way to find this collision? Is there any better way rather than straight brute force and luck?

There aren't any practical / faster way to find collusion, unless you managed to find vulnerability in both RIPEMD160 and SHA256 which can reduce the search space.

█▀▀▀











█▄▄▄
▀▀▀▀▀▀▀▀▀▀▀
e
▄▄▄▄▄▄▄▄▄▄▄
█████████████
████████████▄███
██▐███████▄█████▀
█████████▄████▀
███▐████▄███▀
████▐██████▀
█████▀█████
███████████▄
████████████▄
██▄█████▀█████▄
▄█████████▀█████▀
███████████▀██▀
████▀█████████
▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀
c.h.
▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄
▀▀▀█











▄▄▄█
▄██████▄▄▄
█████████████▄▄
███████████████
███████████████
███████████████
███████████████
███░░█████████
███▌▐█████████
█████████████
███████████▀
██████████▀
████████▀
▀██▀▀
20kevin20
Legendary
*
Offline Offline

Activity: 1134
Merit: 1597


View Profile
October 12, 2019, 04:32:10 AM
 #32

considering the facts that SHA256 transforms 256bit public key (as input) to 256bit output, but RIPEMD160 transforms 256bit to 160bit, so the highly likely the collision is in RIPEMD160 function.

That depends on what you mean by highly likely.

It is much MORE likely that it will occur in the RIPEMD160 transform than in the SHA256 transform, but that's a bit like saying that it is much MORE likely that a completely fair coin will land on heads 160 times in a row than 256 times in a row.  In both cases it is *VERY* unlikely.

Essentially we are talking about the difference between "It isn't going to happen" and "It isn't going to happen".

I used the incorrect words to descripbe. Of course the probability is highly unlikely, it is actually impossible. And for me as 2^256, so 2^160 are both very high numbers, and the probabilities 1/2^256 and 1/2^160 are actually 0%.

I just had in mind the probable place of collision if such collision is found. Let's say Key1 and Key2 are 2 keys leading to the same Address. So, it is more likely that public keys PubKey1 and PubKey2 are different. Then it is also more likely that SHA256 of PubKey1 and SHA256 of PubKey2 will be different. But the collision is in RIPEMD160 function transforming different SHA256(PubKey1) and SHA256(PubKey2) to the same hash, and then to the sme Address.

Although everybody calls it a 0% chance, it's enough for just one man to get the key to a big wallet like Satoshi's without even having the plan to, and that would be disastrous for us. I keep on wondering when something like that would happen. I understand the chances are very close to 0, but what if it happens just ONCE with a huge wallet? Is there any way this could be prevented?
achow101
Moderator
Legendary
*
expert
Offline Offline

Activity: 3388
Merit: 6641


Just writing some code


View Profile WWW
October 12, 2019, 05:26:01 AM
Merited by ABCbits (1)
 #33

Although everybody calls it a 0% chance, it's enough for just one man to get the key to a big wallet like Satoshi's
Satoshi's wallet is not one address or public key. It is tens of thousands of individual keys because he did not reuse them. Being able to find a private key that he used would only let you spend 50 Bitcoin.

I understand the chances are very close to 0
You don't seem to understand how close to 0 it is.

It is literally impossible to have the probability of collision be exactly 0 because that would require an infinite search space which is literally impossible (would require infinite matter and infinite energy which do not exist).

but what if it happens just ONCE with a huge wallet? Is there any way this could be prevented?
There is no way to prevent it because whoever produced the collision would have an equally legitimate claim to the Bitcoin.

It is far more likely that if there were a collision that it was the result of a bad implementation of the RNG and of the crypto library used in general.

20kevin20
Legendary
*
Offline Offline

Activity: 1134
Merit: 1597


View Profile
October 12, 2019, 05:44:14 AM
 #34

Satoshi's wallet is not one address or public key. It is tens of thousands of individual keys because he did not reuse them. Being able to find a private key that he used would only let you spend 50 Bitcoin.

Oh, I get it now and I kinda feel ashamed not to know that yet, lol. I thought there were just a few addresses with tons of coins actually.

You don't seem to understand how close to 0 it is.

It is literally impossible to have the probability of collision be exactly 0 because that would require an infinite search space which is literally impossible (would require infinite matter and infinite energy which do not exist).

Got it, I'm just thinking there might be just 1 collision happening at one point in the future, even with the chances so small. I mean, again, it's VERY close to 0 but there still is that one very little chance of collision, right?

What about LBC? I have never used it before although I did want to, but it seemed kinda sketchy to me. However, I've seen lists of Bitcoin addresses found as collisions with older transactions on them or even still having BTC on them. How does that work, aren't they privkey collisions?
pooya87
Legendary
*
Offline Offline

Activity: 3444
Merit: 10562



View Profile
October 12, 2019, 07:45:43 AM
 #35

What about LBC? I have never used it before although I did want to, but it seemed kinda sketchy to me. However, I've seen lists of Bitcoin addresses found as collisions with older transactions on them or even still having BTC on them. How does that work, aren't they privkey collisions?

you mean "large bitcoin collider"? it has absolutely nothing to do with collision and yes it is very sketchy.
what it does is to loop through private keys from 1 and increment them one by one, on each step get the public key, hash it and compare it with a hashes provided by puzzle and claims the reward if they found a match.
the space they are searching in is minuscule compared to the 256 bit space that normal bitcoin private keys are in.

.
.BLACKJACK ♠ FUN.
█████████
██████████████
████████████
█████████████████
████████████████▄▄
░█████████████▀░▀▀
██████████████████
░██████████████
████████████████
░██████████████
████████████
███████████████░██
██████████
CRYPTO CASINO &
SPORTS BETTING
▄▄███████▄▄
▄███████████████▄
███████████████████
█████████████████████
███████████████████████
█████████████████████████
█████████████████████████
█████████████████████████
███████████████████████
█████████████████████
███████████████████
▀███████████████▀
█████████
.
DannyHamilton
Legendary
*
Offline Offline

Activity: 3388
Merit: 4653



View Profile
October 12, 2019, 08:16:57 AM
Merited by ABCbits (2), amishmanish (1)
 #36

Got it, I'm just thinking there might be just 1 collision happening at one point in the future, even with the chances so small. I mean, again, it's VERY close to 0 but there still is that one very little chance of collision, right?

There are mathematical numbers that are very Very VERY small.  Even though those numbers are not mathematically zero, they can be considered to be zero in the real world.

For example...

You sit in a large room full of air at 23 degrees celsius.  The air is a typical earth atmosphere (a bit more than 14 pounds per square inch) with approximately 78% nitrogen, 21% oxygen, 0.9% argon, 0.04% carbon dioxide, etc.

The oxygen molecules bounce around RANDOMLY in the room. mixed together with all the other molecules in the room.  If we consider EVERY possible arrangement of all those air molecules, each of those arrangements is equally likely as any other.  However, there are many, Many, MANY more possible arrangements that result in enough oxygen being near the air holes in your face to keep you alive than there are arrangements that result in there being no oxygen at all close enough to keep you alive.

So, in a normal room, with a normal amount of air, there is a mathematically NON-ZERO chance that you will unexpectedly, and suddenly die of suffocation for no apparent reason (just because the oxygen randomly happened to end up too far away for you to breath it).

However, in the REAL WORLD, I think any reasonable person would say that there is ZERO CHANCE of that actually happening.

Another example...

There is a non zero possibility that you could be struck by lightning once a year while sitting on a toilet taking a crap every year for 17 consecutive years.  I think any reasonable person would also say that there is ZERO CHANCE of that actually happening as well.


What about LBC? I have never used it before although I did want to, but it seemed kinda sketchy to me.

It's a sketchy scam.


However, I've seen lists of Bitcoin addresses found as collisions with older transactions on them or even still having BTC on them. How does that work, aren't they privkey collisions?

Sort of.  There is a difference between a private key that is actually chosen RANDOMLY, and a private key that is not random at all.

Lets say I choose to use a private key with a value of 1.  The odds that someone else will decide to try the same private key are pretty good.  It is not a randomly chosen number, and it is therefore very likely that someone else will also non-randomly choose that number.

There are a number of private keys that have been chosen (non-randomly) in the past by various people for a variety of reasons. The fact that LBC which also chooses private keys non-randomly happened to try some of those same private keys is about as surprising as the fact that there is more than one person in the world named Peter.
MrFreeDragon (OP)
Sr. Member
****
Offline Offline

Activity: 443
Merit: 350


View Profile
October 12, 2019, 12:31:36 PM
 #37


There are mathematical numbers that are very Very VERY small.  Even though those numbers are not mathematically zero, they can be considered to be zero in the real world.


DannnyHamilton has just made a very good example about the almost zero probability and people's attention to it. He said that if there is a VERY VERY small probability of a positive outcome (like to find a private key with the digital wealth), our brains (people's brains) would like to consider this event to happen on someday in future. However there is the same (or even larger) probability of a negative event (like die from a lighintg storm or spacewar with the aliens), our brains consider such event as never happen.

This is a very interesting psychological trick, how are our brains falsify the real probability of events depending on their outcome (positive or negative)  Wink

In many life situations people do not spend any attention to the the events with 10-20% probability considering them as unlikely things, but in other situations they are ready to spend years of their life for "almost 0%" probability events  Roll Eyes

odolvlobo
Legendary
*
Offline Offline

Activity: 4312
Merit: 3214



View Profile
October 12, 2019, 10:55:21 PM
 #38

You don't seem to understand how close to 0 it is.

It is literally impossible to have the probability of collision be exactly 0 because that would require an infinite search space which is literally impossible (would require infinite matter and infinite energy which do not exist).

Got it, I'm just thinking there might be just 1 collision happening at one point in the future, even with the chances so small. I mean, again, it's VERY close to 0 but there still is that one very little chance of collision, right?

Please watch this: https://www.youtube.com/watch?v=nFTRwD85AQ4

Join an anti-signature campaign: Click ignore on the members of signature campaigns.
PGP Fingerprint: 6B6BC26599EC24EF7E29A405EAF050539D0B2925 Signing address: 13GAVJo8YaAuenj6keiEykwxWUZ7jMoSLt
bigvito19
Full Member
***
Offline Offline

Activity: 706
Merit: 111


View Profile
October 13, 2019, 01:24:43 AM
 #39

Well almost zero is not zero......so may the odds be in your favor  Cool
20kevin20
Legendary
*
Offline Offline

Activity: 1134
Merit: 1597


View Profile
October 13, 2019, 04:16:03 AM
 #40

There are mathematical numbers that are very Very VERY small.  Even though those numbers are not mathematically zero, they can be considered to be zero in the real world.

For example...

You sit in a large room full of air at 23 degrees celsius.  The air is a typical earth atmosphere (a bit more than 14 pounds per square inch) with approximately 78% nitrogen, 21% oxygen, 0.9% argon, 0.04% carbon dioxide, etc.

[...]

There is a non zero possibility that you could be struck by lightning once a year while sitting on a toilet taking a crap every year for 17 consecutive years.  I think any reasonable person would also say that there is ZERO CHANCE of that actually happening as well.

Oh, wow, thanks for the examples. I see, so I always had this fear somebody could randomly generate my private key one day and take my funds, even if I'd be using hardware wallets. Now you clarified that and I get it. Thanks!

It's a sketchy scam.

Well, I wanted to use it just once and even the setup part looked pretty sketchy to me. I had that feeling something's wrong with it. (wanted to use it for educational purposes, no stealing intention)

Looks like I have so much to learn that my questions are actually kinda stupid..
Btckeypuzzle
Newbie
*
Offline Offline

Activity: 5
Merit: 0


View Profile
February 28, 2020, 09:26:41 AM
 #41

Two more related examples:

Bitcoin Address

13TQKnr3psXk7Zw9xi6hsrJcdqKRLidhux

Private Keys WIF 51 characters base58, starts with a '5'

5HpHagT65TZzG1PH3CSu63k8DbpvD8s5ip4nEB3kEsrePng1DKR
5Km2kuu7vtFDPpxywn4u3NLpbr5jKpTB3jsuDU2KYEqf82m2L2c


Bitcoin Address Compressed

12e2Zo4VFe2j4Cs3gru55H8JZ7PZXppHnd

Private Keys WIF Compressed 52 characters base58, starts with a 'K' or 'L':

KwDiBf89QgGbjEhKnhXJuH7LrciVrZi3qYjgd9M7rFU7GKcwKfzu
L5oLkpV3aqBjhki6LmvChTCV6odsp4SXM6FfU2Gppt5kUnQrQ7aw
MrFreeDragon (OP)
Sr. Member
****
Offline Offline

Activity: 443
Merit: 350


View Profile
February 28, 2020, 11:57:09 AM
Merited by o_e_l_e_o (1)
 #42

These arre not related examples.

13TQKnr3psXk7Zw9xi6hsrJcdqKRLidhux

Private Keys WIF 51 characters base58, starts with a '5'

5HpHagT65TZzG1PH3CSu63k8DbpvD8s5ip4nEB3kEsrePng1DKR
5Km2kuu7vtFDPpxywn4u3NLpbr5jKpTB3jsuDU2KYEqf82m2L2c

In this case you just used a decimal number 116 as the private key - first private key is 116 itself, and the 2nd one is 116+order (so out of range), but of course order+k will have the same bitcoin address due to ECDSA specific.

Bitcoin Address Compressed

12e2Zo4VFe2j4Cs3gru55H8JZ7PZXppHnd

Private Keys WIF Compressed 52 characters base58, starts with a 'K' or 'L':

KwDiBf89QgGbjEhKnhXJuH7LrciVrZi3qYjgd9M7rFU7GKcwKfzu
L5oLkpV3aqBjhki6LmvChTCV6odsp4SXM6FfU2Gppt5kUnQrQ7aw

In this example you used decimal number 26 as the private key. So 1st key is 26 itself, and the 2nd one is 26+order. The same thing as in 1st example.

This "playing" with the order is very well known.
I want to find at least two (better more of course) private keys within the bitcoin range and leading to the same btc address. So both private keys should be less than the bitcoin order (0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141)

Btckeypuzzle
Newbie
*
Offline Offline

Activity: 5
Merit: 0


View Profile
February 28, 2020, 02:48:13 PM
Last edit: February 28, 2020, 02:58:45 PM by Btckeypuzzle
 #43

Thank you MrFreeDragon for your reply and efforts.
Your searches are completely clear and logical - I respect.
I got my keys in a completely different way. Just left the range of 2 ^ 256.
There are further private keys 2 ^ 512, 2 ^ 1024 and so on.
I am interested in other questions, for example:
1. These are the private keys of the Wallet Import Format (WIF), as
 ways to encode ECDSA private key? Then why only "one address is one key"
without reservations about diaposane? Do not change the dogma, even if it is out of date?
2. Why they look like "Private Keys WIF 51 characters base58, starts with a '5'"
and "Private Keys WIF Compressed 52 characters base58, starts with a 'K' or 'L'"
and when imported into Electrum-portable, they show the "true" first keys for the address.
It’s like, the first and simple questions in my quest for “the depths of a rabbit hole”.
Sorry for off topic.
MrFreeDragon (OP)
Sr. Member
****
Offline Offline

Activity: 443
Merit: 350


View Profile
February 28, 2020, 08:13:56 PM
Merited by nc50lc (2), o_e_l_e_o (1)
 #44

-snip-
I am interested in other questions, for example:
1. These are the private keys of the Wallet Import Format (WIF), as
 ways to encode ECDSA private key? Then why only "one address is one key"
without reservations about diaposane? Do not change the dogma, even if it is out of date?
2. Why they look like "Private Keys WIF 51 characters base58, starts with a '5'"
and "Private Keys WIF Compressed 52 characters base58, starts with a 'K' or 'L'"
and when imported into Electrum-portable, they show the "true" first keys for the address.
It’s like, the first and simple questions in my quest for “the depths of a rabbit hole”.
Sorry for off topic.

Well, it is actually the basic question.
First of all you should know that any private key is just a number from 1 up to bitcoin order. Greater numbers just repeat the address. order + 1 has the same address as 1.

order = 115792089237316195423570985008687907852837564279074904382605163141518161494337 (in dec).
order = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 (in hex)

The number can be represented in decimal (not widely used), in binary (used by computers), in hex (used by users), or in WIF. Actually it is the same number, but represented in different bases.
Your case: number 26 (decimal), the same as 1A (in hex), or 11010 (in binary).

The private key (number) is used to receive the public key using ECDSA. So your output will be a point with x coordinate and y coordinate. Uncompressed key means that it has both coordinates and prefix 04, but compressed used only x and prefix 02/03 depends on odd/even the y coordinate (google for it, it is due to symmetry of elliptic curve).

Now WIF is a wallt import format, used to import keys to wallet software. This format includes the private key (as hex value) and information about compression (optional byte for compression keys). All this is encoded with base58. Have a look here: https://learnmeabitcoin.com/guide/wif
Converting the private key to WIF with base58 will also make a first sign '5' due to first version byte '80' for uncompressed keys, and will also make a first sign 'K'/'L' due to 1 byte longer (suffix '01') and the same first byte '80'.

Then why only "one address is one key": because for every private key you will have only one and the same public key, for every public key you will have only one address of the same type. However as there are different bitcoin formats, you actually could have different addresses for every type. For every private key you will have 2 legacy addresses (one compressed and one uncompressed - both start with 1), one segwit address (starts with 3) and one segwit address (starts with bc1).


bigvito19
Full Member
***
Offline Offline

Activity: 706
Merit: 111


View Profile
February 28, 2020, 08:40:12 PM
 #45

Y'all do know there is no such things as 2 different private keys going to the same BTC address. That's just like saying 2 different passwords going to the same email account. A BTC collision (Finding a private key to an address with BTC) can still happen.
MrFreeDragon (OP)
Sr. Member
****
Offline Offline

Activity: 443
Merit: 350


View Profile
February 28, 2020, 09:03:55 PM
 #46

Y'all do know there is no such things as 2 different private keys going to the same BTC address. That's just like saying 2 different passwords going to the same email account. A BTC collision (Finding a private key to an address with BTC) can still happen.

I beleive that BTC collision can happen. There a simple logic for it: as there almost 2^256 possible private keys, and for evey private key there is only one legacy compressed address, but the total number of possible legacy addresses is not more than 2^160 ==> there should be a collision (under Dirichlet principle)

Pages: 1 2 3 [All]
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!