Bitcoin vulnerability

[tubbyjr]

I've been watching this thread for a bit https://bitcointalk.org/index.php?topic=433522.600 and they may be onto something. Allegedly, with only a bit of searching, collisions have been found of private keys, using public keys. I'm mostly in fiat for now, although I don't think any of us smaller holders need to worry that much .

Here's the site displaying live stats: https://bitcointalk.org/index.php?topic=433522.600

If there is a vulnerability, hopefully developers will look to it real soon, although the ECDSA is an integral part of bitcoin and the blockchain, and I see it as being very difficult to change, without something to revalidate all previous transactions.

[fonzie]

Holy shit, thanks for sharing.!

This will generate a big shitstorm today, you can be sure. We have to change the software and not only flag the duplicated keys, but also submit the randoms used to generate the private key. There are two possibilities to investigate before we point to ECDSA:
1) Our randoms are not random even on different machines due to the lack of entropy on them,
2) the hash of that random number is broken and it generates collisions in private keys from different random numbers.

It all breaks out to - we have to change the software to submit the random numbers we used to generate private keys, even if it means temporary interruption of mining before the server is updated not to accept the triplets without a random.

THIS IS A VERY SERIOUS DISCOVERY AND MIGHT BE WORTH A PRESS RELEASE

ALARM!


ALSO, WHAT IS CAUSING A REALLY BAD HEADACHE

In gh2k's new software you can see the duplicates are not always 0. Now we are completely generating random BTC addresses and obviously it can be observed that many people are getting some rejects.
That again indicates, that we have several people who accidently generate the same private key. This is really ALARMING as people are finding collisions in BTC Addresses. Maybe we need some stats for this at the page.


This might by a major breakthrough in the address space analysis.

Did you just say that with enough power you can access easily other people bitcoins?

Did you just say that with enough power you can access easily other people bitcoins?

That's the whole point of this "science" project. To identify exactly that. Evil even posted a few pages back how to target a specific key!

[runam0k]

LOL @ FUD

Why not quote the parts where a 50BTC reward was offered for proof (breaking any one of 200k addresses)... which they still haven't claimed.

[TERA]

LOL @ FUD

Why not quote the parts where a 50BTC reward was offered for proof (breaking any one of 200k addresses)... which they still haven't claimed.

I think someone who can exploit this vulnerability will suddenly take an interest in more than 50BTC.

[fonzie]

LOL @ FUD

Why not quote the parts where a 50BTC reward was offered for proof (breaking any one of 200k addresses)... which they still haven't claimed.

This problem is quite new, few days/hours old. If somebody couldn´t do it in the last 3 days, it doesn´t mean that it couldn´t happen ever.

[Bitbuy]

Thanks for sharing this; will definitely be looking into this.

[Miz4r]

LOL @ FUD

Why not quote the parts where a 50BTC reward was offered for proof (breaking any one of 200k addresses)... which they still haven't claimed.

I think someone who can exploit this vulnerability will suddenly take an interest in more than 50BTC.

If there actually is a vulnerability here, you can be sure someone within the community will find it and will claim that bounty. So far I'm not worried and I think it's very likely to be a bug within the script they're running for that test.

[TERA]

LOL @ FUD

Why not quote the parts where a 50BTC reward was offered for proof (breaking any one of 200k addresses)... which they still haven't claimed.

I think someone who can exploit this vulnerability will suddenly take an interest in more than 50BTC.

If there actually is a vulnerability here, you can be sure someone within the community will find it and will claim that bounty. So far I'm not worried and I think it's very likely to be a bug within the script they're running for that test.

How do you know that this particular person will have the morality to simply claim the 50 bitcoin bounty rather than using it to access 12 million bitcoins and cash out as many as he can without getting caught.

[zby]

LOL @ FUD

Why not quote the parts where a 50BTC reward was offered for proof (breaking any one of 200k addresses)... which they still haven't claimed.

1. The condition for the reward is harder than the condition for the system failure - there are more than 200k addresses used and it is easier to find a collision in the whole bunch than in the chosen sliver.

2. As someone already said - if you have the means to cause collisions you can gain much more han 50BTC - so the 50BTC is not an incentive to stop doing it if someone knows how to do it.

[Miz4r]

LOL @ FUD

Why not quote the parts where a 50BTC reward was offered for proof (breaking any one of 200k addresses)... which they still haven't claimed.

I think someone who can exploit this vulnerability will suddenly take an interest in more than 50BTC.

If there actually is a vulnerability here, you can be sure someone within the community will find it and will claim that bounty. So far I'm not worried and I think it's very likely to be a bug within the script they're running for that test.

How do you know that this particular person will have the morality to simply claim the 50 bitcoin bounty rather than using it to access 12 million bitcoins and cash out as many as he can without getting caught.

I assume not only morally void people have the brains and means to find possible exploits. If there is a vulnerability it will probably not be found by just one person who can either decide to do the right thing and claim the 50 BTC bounty or hack multiple addresses (or both). Multiple people will find this exploit if there is one and I think it's quite reasonable to assume that at least one of them will be claiming that bounty.

[cr1776]

This is all FUD. The parameters in the code EK wants you to use are like saying "pick an integer between 2 and 4 and I'll guess it in one guess"  Vs saying "pick an integer between one and a trillion and I'll guess it in 1 guess."

Just like with the android PRNG bug, if you limit the search space you can easily search it. It is self evident. There is a good thread in the tech and dev section which details why it isn't an issue unless you use bad (or limited) code to generate keys.

[Hyena]

This is all FUD. The parameters in the code EK wants you to use are like saying "pick an integer between 2 and 4 and I'll guess it in one guess"  Vs saying "pick an integer between one and a trillion and I'll guess it in 1 guess."

Just like with the android PRNG bug, if you limit the search space you can easily search it. It is self evident. There is a good thread in the tech and dev section which details why it isn't an issue unless you use bad (or limited) code to generate keys.

That's what I suspected. These code newbies don't know shit about PRNGs. Nevertheless, I've lately started to use http://random.org to influence the seed for my random number generators in security critical infrastructure.

[raid_n]

This is all FUD. The parameters in the code EK wants you to use are like saying "pick an integer between 2 and 4 and I'll guess it in one guess"  Vs saying "pick an integer between one and a trillion and I'll guess it in 1 guess."

Just like with the android PRNG bug, if you limit the search space you can easily search it. It is self evident. There is a good thread in the tech and dev section which details why it isn't an issue unless you use bad (or limited) code to generate keys.

Exactly.
For those who don't quite grasp the technology: This "vulnerability" has been and will always be there. Address collision is just very very very very unlikely unless the random number generation of the code is predictable (or you create your own private key from some phrase/input without using some form of salt to modify it).
If you are really paranoid just split your holdings into many wallets that were created with code that provides good random numbers.
In the unlikely event that you are one of the most unlucky beings in the universe and suffer from a collision at least you only lose a fraction.

A 1 second google search threw up this QA : http://bitcoin.stackexchange.com/questions/22/is-it-possible-to-brute-force-bitcoin-address-creation-in-order-to-steal-money

[sgbett]

LOL @ FUD

Why not quote the parts where a 50BTC reward was offered for proof (breaking any one of 200k addresses)... which they still haven't claimed.

I think someone who can exploit this vulnerability will suddenly take an interest in more than 50BTC.

If there actually is a vulnerability here, you can be sure someone within the community will find it and will claim that bounty. So far I'm not worried and I think it's very likely to be a bug within the script they're running for that test.

How do you know that this particular person will have the morality to simply claim the 50 bitcoin bounty rather than using it to access 12 million bitcoins and cash out as many as he can without getting caught.

I assume not only morally void people have the brains and means to find possible exploits. If there is a vulnerability it will probably not be found by just one person who can either decide to do the right thing and claim the 50 BTC bounty or hack multiple addresses (or both). Multiple people will find this exploit if there is one and I think it's quite reasonable to assume that at least one of them will be claiming that bounty.

A rational actor should do exactly as you suggest. The grandparent here is overlooking the fact that by compromising the protocol you compromise the value of any bitcoin obtained by using the exploit.

Whilst this is not a guarantee - criminals iz stoopid after all - it's a fairly 'self healing' process. 50BTC is not to be sniffed at thesedays.

[Opsamk]

Bottom line, bitcoin was designed to be cracked. Price won't change from a collision here and there.

[mgburks77]

This is all FUD. The parameters in the code EK wants you to use are like saying "pick an integer between 2 and 4 and I'll guess it in one guess"  Vs saying "pick an integer between one and a trillion and I'll guess it in 1 guess."

Just like with the android PRNG bug, if you limit the search space you can easily search it. It is self evident. There is a good thread in the tech and dev section which details why it isn't an issue unless you use bad (or limited) code to generate keys.

Exactly.
For those who don't quite grasp the technology: This "vulnerability" has been and will always be there. Address collision is just very very very very unlikely unless the random number generation of the code is predictable (or you create your own private key from some phrase/input without using some form of salt to modify it).
If you are really paranoid just split your holdings into many wallets that were created with code that provides good random numbers.
In the unlikely event that you are one of the most unlucky beings in the universe and suffer from a collision at least you only lose a fraction.

A 1 second google search threw up this QA : http://bitcoin.stackexchange.com/questions/22/is-it-possible-to-brute-force-bitcoin-address-creation-in-order-to-steal-money

These collisions are unavoidable due to the nature of multiple access electronic networks?

[xalex]

This is all FUD. The parameters in the code EK wants you to use are like saying "pick an integer between 2 and 4 and I'll guess it in one guess"  Vs saying "pick an integer between one and a trillion and I'll guess it in 1 guess."

Just like with the android PRNG bug, if you limit the search space you can easily search it. It is self evident. There is a good thread in the tech and dev section which details why it isn't an issue unless you use bad (or limited) code to generate keys.

That's what I suspected. These code newbies don't know shit about PRNGs. Nevertheless, I've lately started to use http://random.org to influence the seed for my random number generators in security critical infrastructure.

I looked at the code and i agree.

Python is used, specifically the random.randrange() function. No secure seed is given, so it defaults to time.time(), this basically is the timestamp in full seconds.
Result:
This function alone will yield in 2592000 (4 weeks of seconds) possibilities in stead of 2^256.
1.000.000 of these calculations per second (1Mhs) results in a collision roughly every 2.6 seconds. And this is with just one process running.

No worries here.

-Alex
Security specialist

[raid_n]

These collisions are unavoidable due to the nature of multiple access electronic networks?

No, those collisions are unavoidable because of the way you generate your private/public key.
There is no authority issuing you address 1,2,3,....n with the corresponding key. You yourself ( well more likely your software although you could run the algorithm on paper or in your head) are creating the pairings.
Now the address space to choose from is very large, in fact you could give each atom on this planet its own address if you wanted and still have more than enough left [edit] While the private key is 2^256 bit which would fit the approximate 2^166 bits needed to address each atom the corresponding public address derived ( 2^160) does not quite cover it [/edit]

So simply choosing a random number for generating this will be sufficient. This way there does not need to be any authority that creates them and hence knows the private key.

On the other hand if everyone comes and chooses a number between 1 and say 1 million then you are reducing your previous large address space to that of effectively 1 million
In a sense this also happens if your (pseudo) random  number generator becomes predictable. Say you use the current time as an input to generate a random number.
If i know the day you created that random number and the algorithm were to only rely on the current time and nothing else to generate random numbers I can try through the very limited time-space of that day to try and figure out what "random number" you used.

In fact I believe the NSA compromised a standard method on random number generation so that it would produce predictable results and allow them to take advantage of that

[edit]

here is the description of how the address is derived: https://en.bitcoin.it/wiki/Technical_background_of_version_1_Bitcoin_addresses
The RIPEMD-160 hashing step reduces the possible address space to 2^160 bits
[/edit]

[mgburks77]

These collisions are unavoidable due to the nature of multiple access electronic networks?

No, those collisions are unavoidable because of the way you generate your private/public key.
There is no authority issuing you address 1,2,3,....n with the corresponding key. You yourself ( well more likely your software although you could run the algorithm on paper or in your head) are creating the pairings.
Now the address space to choose from is very large, in fact you could give each atom on this planet its own address if you wanted and still have more than enough left [edit] While the private key is 2^256 bit which would fit the approximate 2^166 bits needed to address each atom the corresponding public address derived ( 2^160) does not quite cover it [/edit]

So simply choosing a random number for generating this will be sufficient. This way there does not need to be any authority that creates them and hence knows the private key.

On the other hand if everyone comes and chooses a number between 1 and say 1 million then you are reducing your previous large address space to that of effectively 1 million
In a sense this also happens if your (pseudo) random  number generator becomes predictable. Say you use the current time as an input to generate a random number.
If i know the day you created that random number and the algorithm were to only rely on the current time and nothing else to generate random numbers I can try through the very limited time-space of that day to try and figure out what "random number" you used.

In fact I believe the NSA compromised a standard method on random number generation so that it would produce predictable results and allow them to take advantage of that

[edit]

here is the description of how the address is derived: https://en.bitcoin.it/wiki/Technical_background_of_version_1_Bitcoin_addresses
The RIPEMD-160 hashing step reduces the possible address space to 2^160 bits
[/edit]

Thank you!

[poppys]

Put all your btc in dogecoin.