Topic: re-use of addresses - page 2. (Read 5530 times)

By providing a single address, everyone can see the average amount donated per person, and know how many people didn't donate.  Using additional information, it might become possible to make educated guesses about who gave how much.  Now, not only you and the boss, but EVERYONE has information about the donations.

Better would be to print out enough donation addresses so there is one for each employee.  Then cut up the paper so that there is only one address per piece.  Turn then face down so nobody knows what address anybody else gets, and let everyone choose randomly.

Now nobody other than the recipient knows exactly how much each person donated.

Of course, privacy comes at a cost of security.  It is now possible for the person making the collection to lie about the amount that they received, skimming a bit off for themselves.  The group can decide if they want the list of donation addresses to be public or not.

Well, suppose you are collecting donations from co-workers for your boss's birthday present. If you give them all the same address, you see the incoming transactions and the total balance, but you won't know who paid what, so they have some anonymity. If you give a different address to each co-worker, and remember who got which address, then you can tie the amount of each donation to the person who sent it. Then you can inform your boss about who didn't pay for her present. Clearly, your co-workers' anonymity has been compromised in a way that affects (some of) them adversely.

The above makes sense to me, but I can't relate it to Peter Dushenski's article, so he may have been saying something different. Quite a lot of that article makes no sense to me.

That's your choice. In the above scenario, their loss of privacy is to your benefit. If you were running something like Wikileaks, you might get more donations if you did respect your benefactor's privacy.

There's not a lot they can do in the above scenario.

Thanks DeathAndTaxes.  I was interested in only the math itself and just needed the key words "ECDSA Public Key Recovery" to find it.  For interested readers, the algorithm is on page 47 of this PDF: "Given an ECDSA signature (r, s) and EC domain parameters, it is generally possible to determine the public key Q, at least to within a small number of choices."

Very cool indeed.  Perhaps Satoshi didn't know this was possible, or perhaps he was worried about the possibility of more than one choice for Q given the signature (r, s) and the additional logic needed to deal with it.  


EDIT: I see Gavin supported Satoshi's decision to include the public key: https://bitcointalksearch.org/topic/m.94290

Peter,

Which language?  It is in the bitcoin-core (QT) sourecode.  Probably in the bitcoin libs for just about any language now.  In general the concept is called "ECDSA Public Key Recovery".  A very cool property of ECC that doesn't existing in all public key cryptography.  In Bitcoin it is only used in message (not transaction) signing.

Here is the standard.  Key Recovery starts on page 47.

http://www.secg.org/download/aid-780/sec1-v2.pdf

There is one thing i am unsure about.  The PubKey (in the absence of additional information) has to be found by trial and error (generate possible PubKey from sign, verify sig w/ possible key.  if valid then you have found key, if not try next possible key, if no possible key validates sig then sig is invalid). 

When locating the proper key one iterates from i=0 to i=h (domain parameter).  For secp256k1 h = 1 so the only possible i values should be 0 or 1.  Most code I have seen iterates from 0 to 3 I wonder if that is just an oversight.  If I am right then there will never be a recovery using an i of 2 or 3.

For Bitcoin messages the i value is encoded in the message header so only one recovery and verification needs to be done.  It is encoded as a byte as follows.
0x1B = Uncompressed PubKey, First Even Key (i = 0)
0x1C = Uncompressed PubKey, First Odd Key (i = 1)
0x1D = Uncompressed PubKey, Second Even Key (i = 2)  <- impossible for secp256k1?
0x1E = Uncompressed PubKey, Second Odd Key (i = 3) <- impossible for secp256k1?
0x1F = Compressed PubKey, First Even Key (i = 0)
0x20 = Compressed PubKey, First Odd Key (i = 1)
0x21 = Compressed PubKey, Second Even Key (i = 2) <- impossible for secp256k1?
0x22 = Compressed PubKey, Second Odd Key (i = 3) <- impossible for secp256k1?

Thanks Danny, your comment has me quite interested.  The algorithm I coded in Mathematica (for learning purposes) to verify ECDSA is the one from the Wikipedia article here.  This algorithm assumes knowledge of the public key Q (in addition to the signature pair {r, s}) in Step 6:

6.  Calculate the curve point {x, y} = u1 x G + u2 x Q

In fact, the first thing the wiki says about ECDSA verification is "for Bob to authenticate Alice's signature, he must have a copy of her public-key curve point Q."

Can you point me to an algorithm that uses only the signature pair {r, s} and the message, m, to calculate Q?  I can see that if you could calculate Q from {r, s} and m, that you could then hash Q to a bitcoin address and verify this way.  That would have been pretty slick 

It's not, IMO.

If a large number of people are all sending to a single address, that address
becomes conspicuous.  So you are losing a layer of obfuscation there.
In other words, if you were looking at someone's wallet or transactions,
you would more easily be able to spot a well known address, as
well as determine what that address is for.

That's quite simple. Creating a very secure paper wallet requires some efforts. Dealing with multiple paper wallets requires even more efforts. When you deal with multiple paper wallets there is always a risk that you loose a paper wallet and that means that a single paper wallet might be more safe than many wallets.

- http://bitcoinpete.com/2014/05/05/on-reusing-bitcoin-addresses

I still don't get how a dozen people sending to a single address of mine is protecting their privacy better than if I provide one address per transaction.  And I'm more interested in MY privacy than theirs, anyway.  If they want privacy, that's their job to mix or obfuscate -- not mine.

And then further that post reads ...


I don't even.

Actually, the Bitcoin protocol requires you to supply your public key Q, because that's the way Satoshi wrote the program. We all now have to live with it.

If Satoshi hadn't written it that way, it wouldn't be necessary to supply your public key Q to verify the signature.  Given the signature and the message, it's possible to compute the public key. Then by hashing that computed public key, it is possible to verify that the computed public key matches the bitcoin address from the output being spent.

Hah, you too! I have nothing to contribute other than to say that I also wrote my own ECDSA program in Mathematica. Doing this also gave me respect for the serious speed efficiencies that "real" implementations must incorporate (I was using a prime field of only 67 elements).

Referring to the flaw in XP, if you follow the Wikipedia article to the reference to the original paper about this windows RNG, and read it carefully, you will see the weakness lies in being able to predict what random numbers will come next but only if you know the current state of the machine.  And there is no way to know that unless you have access to the machine.

The machine uses entropy from mouse movements, CPU temperature, etc...so this provides more randomness and makes it machine dependent.  The exact temperaturs, mouse movements, etc...all create entropy and a unique state for the machine, and there are too many variables to know what state the machine is in, and even if you had access to it, it wouldn't be trivial.

Are you sure about the bold part ? Any idea how MS used to derive the random number ? I mean how it is machine dependent ?

In the post you quoted, I was trying to explain elliptic curve multiplication and the discrete logarithm problem in a very simple way.  Elliptic curve multiplication is an example of a trapdoor function that is easy to compute in one direction (multiplying the private key (integer) by the elliptic curve base point to get the public key) but infeasible to compute in reverse (finding the private key given the public key and base point).  

When you produce an ECDSA signature for a bitcoin transaction, you sign a 256-bit hash, e, of the message (transaction), m, and get a pair of numbers {r, s}.  But in order for anyone to verify that the signature is correct, you must also tell them your public key Q in addition to r and s (and they must know the message, m, that you signed).

Everyone already knows G because it's a property of the secp256k1 curve.  The act of signing and broadcasting a transaction makes your public key Q known because you need to provide this in order for the network to verify your signature.  Someone could "steal" your funds remaining in the associated bitcoin address if they can solve the problem:

        Q = d x G

for an unknown d.  But like I explained earlier, it is not presently feasible to find d as the fastest known algorithm still takes 2^128 steps.  If the public key is not known, on the other hand, then someone could "steal" your funds if they try on average 2^160 random 256-bit integers until they find a ripeMD160 collision with your bitcoin address.   I say "steal" because 2^128 and 2^160 are really really big numbers and it's not actually feasible to perform a computation with such a huge number of steps.  


I've seen you express interest in elliptic curves in a few threads now.  How I learned about them was reading the wikipedia articles (many, many times), reviewing the comments by DeathAndTaxes, DannyHamilton, GMaxwell and a few others regarding these curves.  But what really made it sink in for me was writing code from scratch to sign and verify ECDSA.  I did this in Mathematica so that I didn't have to worry about integer size or modulus operations.  After I did this, l had new respect for the weird properties of elliptic curves and prime numbers too--it's really interesting stuff.  

Isn't hash function SHA-256 plugged in there somewhere?  where does that fit into this?  And even if you knew "G", wouldn't you still have the hash to contend with? 

Well there are currently no known issues with the PRNG in Windows Vista or later.   That isn't to say there aren't any flaws but I am not aware of any and the cited link references a flaw which only existed in Windows XP and prior.  Even on Windows XP that specific flaw was patched many years ago (assuming users installed security updates).  The Windows PRNG is closed source and that may hide vulnerabilities, bugs, or backdoors but we can't assume most keys are weak.  Even the flaw found in the XP era PRNG requires the attacker to have access to the machine to exploit it.

Really do not want to use the latest 0.9.1 version,
so while I still insist on 0.8.6 before I had to upgrade

Flawed wallet means PRNG weakness and most of today's wallets depend on OS for that. MS PRNG is weak as we already know (http://en.wikipedia.org/wiki/Random_number_generator_attack#Windows_implementation). So u can safely assume most of today's wallet are actually weak because the source is NOT so Random.

Well, I got a address which private key have been exposed,so this address is can't be
used anymore
But,never mind,the amount of address is unlimited. so we are not necessary to worry about the old address.

Thanks everyone! Seems ESCDA is much less secure than I thought but even with all the weaknesses and moore law we are good to reuse addresses for at least 100 years :-)

I don't know of any promising attacks on ECDSA.  In case you mean what reduces the security of a 256 bit ECDSA key to only 128 bit we need to first look at what makes it have any security to begin with. ECC (the underlying cryptography for ECDSA) is based on an assumption that solving the discrete logarithm problem is infeasible.  That is to say that for a large set (like 2^256) the fastest possible solutions require too many steps on average to make any attack effective.   

The most naive attack would be to attempt all possible private keys until you find one which produces the public key you are looking for.  For symmetric algorithms (like AES) this is the only possible solution which is why we measure security relative to symmetric algorithms.   If this naive solution was the only possible solution the security would be 256 bits.   However there are "better" (but not good enough) solutions for this problem.  The fastest of which require O (sqrt{n}) steps where n is the number of elements.  So 2^256 elements means a solution will on average require 2^128 operations which is equal to the number of operations requires to brute force a public key so we say it has 128 bit security. 

However that 128 bit security is based on currently known solutions.  There may be more efficient algorithms that haven't been discovered yet, and in the future someone will develop one which solves the discrete logarithm problems in less than O(sqrt{n}) steps.  If that happens the security of ECC will be reduced to the complexity of the new algorithm as an attacker would use the best tool available.   It is hard to predict if or when this will happen so it remains a potential uncertainty.   Larger key sizes give a higher confidence.  If for example a new algorithm reduced the security to 100 bit we may want to start migrating to a new solution but any real world attack would be uneconomical.   ECC is less extensively studied than integer factorization (like used in RSA).  Breakthroughs in the efficiency of algorithms used to factor prime numbers have occurred in the past and when they did the effective security of RSA keys (which rely on the assumption that factoring large primes will remain infeasible) was reduced.  At one time 768 bit RSA keys were common place now most applications demand at least 2,048 bits to "compensate". Some of that is due to Moore's law but some of that is due to the better algorithms making the problem "easier".