Re-usable "Green" addresses carry extra risk: theft vulnerability

[Carlton Banks]

(the developers can confirm this, and they always bring it up when the issue of re-using addresses comes up)




Every time you send from an address, you sign the transaction (using cryptography)

Every time you send from the same address more than once, you're storing a different signature in the blockchain (each signature is unique to each transaction)

The more signatures there are available for an address, it makes it easier to guess valid signatures to spend money from that address (the number of possibilities becomes smaller, the math behind this is proven)



So, "Green" addresses are a security risk, and a major target for the determined cyber-thief. The list has to be public, so this "Green" list will be a ready made set of addresses for thieves to start trying to brute force. You might pay money in one day, then it'll be gone. You might stupidly pay more in, thinking "some mistake here!". That money will disappear too.

Great way to make Bitcoin safer for the new or basic user? The total opposite. Oh well, the red-list will mop up the mess! Great idea guys, good job.

[DeathAndTaxes]

Easier is all relative.

Yes it makes it "easier" in the sense of requiring more energy than available to our solar system to just more energy used by mankind since the dawn of civilization.

The real danger to any address reuse is
a) enables easier tracking of transactions
b) if QC becomes feasible of ECDSA is cryptographically weakened then the pubkey in theory could be attacked.

[Carlton Banks]

Easier is all relative.

Yes it makes it "easier" in the sense of requiring more energy than available to our solar system to just more energy used by mankind since the dawn of civilization.

The real danger to any address reuse is
a) enables easier tracking of transactions
b) if QC becomes feasible of ECDSA is cryptographically weakened then the pubkey in theory could be attacked.

There will be a bigger pool of signatures from re-used addresses available, all in one nicely packaged list. The chances of getting a lucky sig collision increase if you're working with a bigger set of targets.

[DeathAndTaxes]

Yeah once again improved chances go from more energy in the solar system to more energy used by mankind.  It is an academic distinction at best.  Even with a trillion address reuses the computational power needed is far beyond what is considered feasible.

Simple version: if the mean time to a preimage attack is reduced from 10,000 times as long as the life of the universe to 1x as long as the life of the universe most people don't really consider that a realistic security threat.

[Carlton Banks]

Yeah once again improved chances go from more energy in the solar system to more energy used by mankind.  It is an academic distinction at best.  Even with a trillion address reuses the computational power needed is far beyond what is considered feasible.

Simple version: if the mean time to a preimage attack is reduced from 10,000 times as long as the life of the universe to 1x as long as the life of the universe most people don't really consider that a realistic security threat.

What's with the "if"? Are these actually the valid probabilities for sig pre-imaging of the length of the keys we're using in Bitcoin or not?

[DeathAndTaxes]

Yes it actually is massively optimistic.   It would assume a perfect computer something which is trillions of times more energy efficient than anything mankind has even conceived of and construction on a scale that is simply hard to believe even in far future science fiction.   In reality the timespans and energy requirements would be even more asininely long.

[Rupture]

Surely it only becomes easier by a miniscule amount. Besides if this were true, wouldn't satoshidice 50% been cleaned out a long time ago?

[Carlton Banks]

Surely it only becomes easier by a miniscule amount. Besides if this were true, wouldn't satoshidice 50% been cleaned out a long time ago?

It was always warned against as a way of avoiding problems with ECDSA getting cracked or compromised. D&T has added the full probabilistic perspective, but it doesn't undermine the principle.

As I say in the OP, the developers specifically warn that re-using addresses has this security flaw. Imagine a scenario 10 years in the future, where computing and cryptography may have changed, perhaps unrecognisable compared to today. If people happily go along with green listing from 2014, this could be a real problem by 2020+.

[MysteryMiner]

It's like saying that password made from 35 random symbols are insecure because it is easier to brute force than password made from 37 random symbols. In reality I don't think i ever will become a practical security threat.

[Peter R]

In Statistical Mechanics (physics), we have something called The Law of *really* Large Numbers.  This law basically says that if X is a normal number (like 2 or 44 or 193) and Z is a *really* large number, then we can approximate their product as X*Z = Z.

2^256 is not as big as the really large numbers in stat mech, but the rule still basically applies to bitcoin: the probability of brute forcing *any* private key that actually contains funds is essentially unchanged regardless of how many addresses get created or how many times those addresses sign transactions: nil.

[Peter R]

In Statistical Mechanics (physics), we have something called The Law of *really* Large Numbers.  This law basically says that if X is a normal number (like 2 or 44 or 193) and Z is a *really* large number, then we can approximate their product as X*Z = Z.

2^256 is not as big as the really large numbers in stat mech, but the rule still basically applies to bitcoin: the probability of brute forcing *any* private key that actually contains funds is essentially unchanged regardless of how many addresses get created or how many times those addresses sign transactions: nil.

Haha.  The University of Hawaii (c/o Wiki Answers) estimates that you'd have 7500000000000000000 (75 x 10^17) grains if you collected all the sand from all the beaches and deserts and ocean floors in the entire world. 

Imagine checking all the sand piece-by-piece to find a private key that gives you the bitcoin address you are looking for (1 : 2^160 odds).  Is it this hard to do?  NO, it is WAY harder than just checking every piece of sand!  Imagine if every piece of sand you've collected could be broken down into the same huge number of pieces (7500000000000000000 pieces), and now you have to check every single one of those 7500000000000000000 pieces that make up each of the 7500000000000000000 grains of sand in all the world.  Is is this hard to do?  NO, its even harder:

(75 10^17) x (75 10^17) ~= 2^125  << 2^160 !!

Not going to happen.

[Carlton Banks]

In Statistical Mechanics (physics), we have something called The Law of *really* Large Numbers.  This law basically says that if X is a normal number (like 2 or 44 or 193) and Z is a *really* large number, then we can approximate their product as X*Z = Z.

2^256 is not as big as the really large numbers in stat mech, but the rule still basically applies to bitcoin: the probability of brute forcing *any* private key that actually contains funds is essentially unchanged regardless of how many addresses get created or how many times those addresses sign transactions: nil.

Just to clarify, this vulnerability does not involve computing private keys corresponding to a re-used public key, it is purely the synthesizing of valid signatures for an individual public key.

[MysteryMiner]

In Statistical Mechanics (physics), we have something called The Law of *really* Large Numbers.  This law basically says that if X is a normal number (like 2 or 44 or 193) and Z is a *really* large number, then we can approximate their product as X*Z = Z.

2^256 is not as big as the really large numbers in stat mech, but the rule still basically applies to bitcoin: the probability of brute forcing *any* private key that actually contains funds is essentially unchanged regardless of how many addresses get created or how many times those addresses sign transactions: nil.

Just to clarify, this vulnerability does not involve computing private keys corresponding to a re-used public key, it is purely the synthesizing of valid signatures for an individual public key.

In theory it should be just as hard as calculating the private key. Or the digital signature algorithm is seriously flawed...

[Peter R]

In Statistical Mechanics (physics), we have something called The Law of *really* Large Numbers.  This law basically says that if X is a normal number (like 2 or 44 or 193) and Z is a *really* large number, then we can approximate their product as X*Z = Z.

2^256 is not as big as the really large numbers in stat mech, but the rule still basically applies to bitcoin: the probability of brute forcing *any* private key that actually contains funds is essentially unchanged regardless of how many addresses get created or how many times those addresses sign transactions: nil.

Just to clarify, this vulnerability does not involve computing private keys corresponding to a re-used public key, it is purely the synthesizing of valid signatures for an individual public key.

I see the distinction you are making Carlton Banks.  It is my understanding that no one has found any "short cuts" that reduce the entropy of bitcoin's secp256k1 ECDSA regardless of the number of signatures made public, so long as the nonce values are chosen truly at random when calculating the signatures (otherwise we get the Andriod RNG problem).  This is despite a diligent and ongoing search by top cryptographers across the globe.  

Someone above my pay grade would have to confirm....

[gmaxwell]

I see the distinction you are making Carlton Banks.  It is my understanding that no one has found any "short cuts" that reduce the entropy of bitcoin's secp256k1 ECDSA regardless of the number of signatures made public, so long as the nonce values are chosen truly at random when calculating the signatures (otherwise we get the Andrion RNG problem).  This is despite a diligent and ongoing search by top cryptographers across the globe.  

In general DSA is pretty lame— there are attacks on DSA with reduced computation compared to solving the DLP given multiple signatures with nonces that happen to have certain properties relative to each other. The cases where the attacks are made possible are themselves unlikely enough that its not a practical concern, but its not correct to say that ECDSA is as strong as ECDLP as far as we know. Instead we know its not, but not concerningly so.

(Schnorr signatures are better in almost any way you can pick— better security proofs, ability to do efficient multisignature, etc. but their creator patented them and so pretty much no one has used them except academics.)

I don't consider increased cryptographic risk from pubkey reuse or disclosure of the pubkey (keep in mind: until you spend using a key the first time the public doesn't even know the EC pubkey you're using, they know its hash!) against real, hypothetical, or quantum attacks to be a major consideration. ... but I suppose you could say that it's just one more reason to not reuse addresses.

[Peter R]

I see the distinction you are making Carlton Banks.  It is my understanding that no one has found any "short cuts" that reduce the entropy of bitcoin's secp256k1 ECDSA regardless of the number of signatures made public, so long as the nonce values are chosen truly at random when calculating the signatures (otherwise we get the Andrion RNG problem).  This is despite a diligent and ongoing search by top cryptographers across the globe.  

In general DSA is pretty lame— there are attacks on DSA with reduced computation compared to solving the DLP given multiple signatures with nonces that happen to have certain properties relative to each other. The cases where the attacks are made possible are themselves unlikely enough that its not a practical concern, but its not correct to say that ECDSA is as strong as ECDLP as far as we know. Instead we know its not, but not concerningly so.

(Schnorr signatures are better in almost any way you can pick— better security proofs, ability to do efficient multisignature, etc. but their creator patented them and so pretty much no one has used them except academics.)

I don't consider increased cryptographic risk from pubkey reuse or disclosure of the pubkey (keep in mind: until you spend using a key the first time the public doesn't even know the EC pubkey you're using, they know its hash!) against real, hypothetical, or quantum attacks to be a major consideration. ... but I suppose you could say that it's just one more reason to not reuse addresses.

Thanks for the info gmaxwell.  I see my request for someone above my pay grade to help answer this worked out

Is it possible to put some hard numbers to this?  Let's say I've made 2^10 signatures with my private key using truly random nonce values.  Can we say anything definitive about the loss of entropy?  The entropy is obviously now equal to or less than 256 bits, but is it 246 bits, 255 bits, or 200 bits now?