Pages:
Author

Topic: re-use of addresses (Read 5489 times)

sr. member
Activity: 365
Merit: 251
May 11, 2014, 01:15:51 PM
Imagine an alternate universe where NxT suddenly had the same market-cap and usage as bitcoin.  All sorts of problems would start to emerge.  And because NxT isn't a bitcoin clone, it would be a completely new set of problems that we would not be prepared for.
True. On the other hand, the issues around key length and exposing public keys are well-known. If Nxt has problems, it probably isn't there.

Quote
We were forced to take that risk with bitcoin because it was the first, but why would we want to debug another cryptocurrency payment system if it wasn't necessary?
It is necessary if there's to be progress and innovation in the space of core crypto-currency protocols. Bitcoin itself innovates slowly, if at all, because its devs are rightly very conservative. I think coins that are very different to Bitcoin, like Nxt, are more worthy of our time than the clones, even if we're more confident the clones are technically secure.
legendary
Activity: 1162
Merit: 1007
May 11, 2014, 12:16:06 PM
I would never say address re-use should never occur.  Also for a small amount of funds the risk (and potential loss) is minimal.  Sometimes accepting lower security is an acceptable option.  The important part is making an informed decision.
I've been learning about Nxt recently. That protocol always exposes public keys (and reuse addresses). They just didn't think it was worth worrying about at all.

This hints at another reason alt-coins are unappealing.  Bitcoin has been brutally beaten for over 4 years and has grown in spite of this.  The amount of energy spent trying to exploit weaknesses has forced us to recognize what those weaknesses are and begin dealing with them appropriately.

Imagine an alternate universe where NxT suddenly had the same market-cap and usage as bitcoin.  All sorts of problems would start to emerge.  And because NxT isn't a bitcoin clone, it would be a completely new set of problems that we would not be prepared for.  We were forced to take that risk with bitcoin because it was the first, but why would we want to debug another cryptocurrency payment system if it wasn't necessary?
sr. member
Activity: 365
Merit: 251
May 11, 2014, 10:12:18 AM
I would never say address re-use should never occur.  Also for a small amount of funds the risk (and potential loss) is minimal.  Sometimes accepting lower security is an acceptable option.  The important part is making an informed decision.
I've been learning about Nxt recently. That protocol always exposes public keys (and reuse addresses). They just didn't think it was worth worrying about at all.
legendary
Activity: 2506
Merit: 1010
May 09, 2014, 01:32:59 AM
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.

More explanation.
 - http://trilema.com/2014/why-exactly-reusing-bitcoin-addresses-strengthens-bitcoin-user-anonimity

If a hosted (shared) E-Wallet is used (e.g., like at most exchanges) I don't see any relevance to Mircea's argument.  Even when an E-Wallet isn't used, I'm struggling to grasp the benefit from his approach.
legendary
Activity: 1302
Merit: 1004
Core dev leaves me neg feedback #abuse #political
May 08, 2014, 01:21:59 AM
Yes it is off-topic and I apologize.  I am partially to blame
for starting to talk about ssl certs. 

I would also rather talk about Bitcoin addresses and
ECDSA Smiley
legendary
Activity: 1008
Merit: 1001
Let the chips fall where they may.
May 08, 2014, 01:19:31 AM
You really believe under such a system there would be less phishing and spoofing than with using CAs?  CA is a flawed system but given the realities of mass use by non experts it is the least flawed system we have.

To be honest I don't know, but it would be hard to imagine things even more insecure.

I know without CAs, encryption would be fairly ubiquitous. That would make passive surveillance harder; but would not stop phishing. Browsers can limit the scope of spoofing by actually storing certificates and warning the user when they are changed: though after heartbleed, "Certificate Patrol" has been noisy of late.

Incidentally,  many Bitcoin websites use cloudflare. Clouldflare works by performing a man-in-the-middle attack on the websites under "protection". If a hostile government (such as the US) instructs Cloudflare to attack a website; I am not sure they would say "no".

As of this writing, cryptothrift.com shares a cert with the following websites:
Code:
DNS Name: ssl2250.cloudflare.com
DNS Name: cryptothrift.com
DNS Name: *.photodeals.com.au
DNS Name: *.chapmaninstitute.net
DNS Name: *.smsassembly.com
DNS Name: nicabet.com
DNS Name: chapmaninstitute.net
DNS Name: *.eastmon.com.au
DNS Name: *.nicabet.com
DNS Name: miniboxphoto.com
DNS Name: eastmon.com.au
DNS Name: preferredgarcinia.com
DNS Name: *.miniboxphoto.com
DNS Name: fighthub.international
DNS Name: *.fighthub.international
DNS Name: makeupandbeauty.com
DNS Name: *.pcdashboard.net
DNS Name: *.gardenatics.co.uk
DNS Name: *.makeupandbeauty.com
DNS Name: smsassembly.com
DNS Name: *.cryptothrift.com
DNS Name: *.bubblepix.com.au
DNS Name: photodeals.com.au
DNS Name: bubblepix.com.au
DNS Name: pcdashboard.net
DNS Name: *.preferredgarcinia.com
DNS Name: indespensablegarcinia.com
DNS Name: gardenatics.co.uk
DNS Name: *.indespensablegarcinia.com

Somehow bitmit.net got a green verified cloudflare cert before they went down.

Quote
my bank has some pretty good online protocols/procedures.

You first have to enter your username separately,
and then you are shown a security image
that you previously picked, like a mushroom or
a banana or something.

and only THEN do you enter your password.
My bank does the same thing. If you mistype your user-name, it asks for your password before presenting you with the "security image" though. I suspect those are mainly "security theatre" to make you think the site is secure.



But this is all off-topic :/

legendary
Activity: 1302
Merit: 1004
Core dev leaves me neg feedback #abuse #political
May 08, 2014, 12:15:56 AM
my bank has some pretty good online protocols/procedures.

You first have to enter your username separately,
and then you are shown a security image
that you previously picked, like a mushroom or
a banana or something.

and only THEN do you enter your password.

Certainly not foolproof (the bank might show
no image at all and user forgets about it),
but this system lets you know you're talking
to the bank website rather than being phished.
donator
Activity: 1218
Merit: 1079
Gerald Davis
May 08, 2014, 12:10:30 AM
How would a customer know the difference between a valid and invalid custom letter head.  As far as driving to the bank to verify all cert changes I never said high security systems were impossible I said "it is a very hard problem to solve on a mass scale and for non tech savy users".  You don't honestly think even 1 in 100,000 users are going to drive to their local bank to verify a long hex signature in the cert matches the one they are getting online do you?

You really believe under such a system there would be less phishing and spoofing than with using CAs?  CA is a flawed system but given the realities of mass use by non experts it is the least flawed system we have.
legendary
Activity: 1008
Merit: 1001
Let the chips fall where they may.
May 07, 2014, 11:18:37 PM

Easy?  So when you get mail from "your bank" how do you know it is from "your bank".  Blind trust?


Custom-printed letter-head essentially. Elections Canada accepts that as proof-of-residence; but not self-printed e-billing statements. If in doubt, there is always the copy at the local branch. Of course that has the same problem. You know a local branch is "real" because they have a large sign that costs some amount of money to make. I have heard that banks traditionally use a lot of stone in their architecture so they you know they can't easily move locations on you.
donator
Activity: 1218
Merit: 1079
Gerald Davis
May 07, 2014, 11:07:44 PM
With a self signed cert say you got a cert claiming to be your bank.  How do you know it was your bank which created it?
Easy, your bank mails out their Certificate hash; and posts a copy of the cert (with hash) in local branches in the case of key rotation.
Easy?  So when you get mail from "your bank" how do you know it is from "your bank".  Blind trust?

Quote
With the CA sytem, you are blindly accepting the "self-signed" CA cert anyway if your browser does not recognize the CA authority your bank is using. I tried calling one of my parents's banks after such a warning. I was told to just trust the HTTP re-direct because the bank actually uses many different certs (and they did not know which signature to read over the phone).

IMO, giving dire warnings for self-signed certs, but not HTTP sites is a design flaw.

I agree and you will get no complaints form me on CA being the weak link but it is a very hard problem to solve on a mass scale and for non tech savy users.
legendary
Activity: 1008
Merit: 1001
Let the chips fall where they may.
May 07, 2014, 10:49:25 PM
With a self signed cert say you got a cert claiming to be your bank.  How do you know it was your bank which created it?
Easy, your bank mails out their Certificate hash; and posts a copy of the cert (with hash) in local branches in the case of key rotation.

With the CA sytem, you are blindly accepting the "self-signed" CA cert anyway if your browser does not recognize the CA authority your bank is using. I tried calling one of my parents's banks after such a warning. I was told to just trust the HTTP re-direct because the bank actually uses many different certs (and they did not know which signature to read over the phone).

IMO, giving dire warnings for self-signed certs, but not HTTP sites is a design flaw.

legendary
Activity: 1302
Merit: 1004
Core dev leaves me neg feedback #abuse #political
May 07, 2014, 09:30:47 PM
#99
So then I was completely wrong, as this is on the order of 2^256.

Are the common implementations using numbers that big?

Well it has to be a 256 bit number.  0x0000000000000000000000000000000000000000000000000000000000000001 is a 256 bit number. Smiley

Are you asking, do the k values generated really have 256 bits of entropy?  That is a very hard thing to prove, which is why I am an advocate of RFC6979 it bypasses that concern entirely by making the k value deterministic.

No, I wasn't asking that to be honest.

It would have been a much smarter question.

I guess I was somehow thinking it might be too big of
a number to calculate the curve point or something.

But I now I see that is the whole point here...

 Tongue

legendary
Activity: 1162
Merit: 1007
May 07, 2014, 09:23:11 PM
#98
So then I was completely wrong, as this is on the order of 2^256.

Correct.  You're more likely to brute force a private key that unlocks a funded bitcoin address (1 in 2^160) than you are to generate the same k value twice with a working RNG (1 in 2^256).

Quote
Are the common implementations using numbers that big?

Yes, which means that repeat-k-value problems are entirely due to bugs.  Bitcoin is forcing us to recognize how poor our computer security really is (and RNGs are not the only culprit by a long shot).  
donator
Activity: 1218
Merit: 1079
Gerald Davis
May 07, 2014, 09:16:44 PM
#97
So then I was completely wrong, as this is on the order of 2^256.

Are the common implementations using numbers that big?

Well it has to be a 256 bit number.  0x0000000000000000000000000000000000000000000000000000000000000001 is a 256 bit number. Smiley

Are you asking, do the k values generated really have 256 bits of entropy?  That is a very hard thing to prove, which is why I am an advocate of RFC6979.  It bypasses that concern entirely by making the k value deterministic.  With RFC6979 and HD wallets you could process a lifetime of bitcoin transactions with just 128 random bits (a small enough amount to generate by rolling dice or flipping coins). Smiley
legendary
Activity: 1302
Merit: 1004
Core dev leaves me neg feedback #abuse #political
May 07, 2014, 08:51:37 PM
#96
So then I was completely wrong, as this is on the order of 2^256.

Are the common implementations using numbers that big?

legendary
Activity: 1162
Merit: 1007
May 07, 2014, 07:10:50 PM
#95
Btw, how big is the space  for k?

Big!

k must be on the interval [1, n-1] where n is the integer order of G (and G is the base point for secp256k1).  n is the big prime number:

n = 115792089237316195423570985008687907852837564279074904382605163141518161494337

or in hex:

n = FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

If you pick a 256-bit unsigned integer at random, it will be a permissible value for k 99.99999999999999999999999999999999999962655% of the time.

This also shows that it is not feasible to "randomly" generate the same k value twice (well, unless your random number generator is broken à la the Android bug but then it wasn't really random).  

legendary
Activity: 1302
Merit: 1004
Core dev leaves me neg feedback #abuse #political
May 07, 2014, 05:49:01 PM
#94

A bitcoin private key, d is (almost) any 256-bit integer (78 digit number).  To find the associated public key, Q, you need to multiply your private key by a special "number" G called the elliptic curve base point:

     Q = d x G

If you know d (private key) and G, it is fairly straight forward to calculate Q (public key).  Now, if G and Q were normal numbers, we could re-arrange this equation to solve for the private key by division:

     d = Q / G

But G and Q are not normal numbers; they are actually the {x, y} coordinates of points on a special type of curve called an elliptic curve.  Points on elliptic curves can be multiplied by normal numbers (like a private key), but it turns out that it is extremely difficult to "divide" two points on an elliptic curve to get a normal number (to solve for the private key, d).  I use quotes around "divide" because we actually call this problem the "elliptic curve discrete logarithm problem" (ECDLP) and not the division problem.

Now the reason the security is 128 bits when the private key is 256 bits is because you don't need to brute force every possible key.  You just need to find the value of d that when multiplied by G gives you Q.  There is a bit of a pattern that you can exploit, so to speak.  The fastest known algorithms that allow one to solve the ECDLP (baby-step giant-step, Pollard's rho, etc.), need O(√n) steps.  Since n = 2^256, √2^256 = 2^128.  So using the most efficient algorithm to solve for d if Q and G are known, it should "only" take around 2^128 steps, as opposed to the 2^256 steps it would take to try every possible key by brute force.

http://en.wikipedia.org/wiki/Elliptic_curve_cryptography#Key_sizes

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?  

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.  



Thanks Peter,
I read the wiki article on ECDSA.  I get idea better now. 

Still miles behind the conversion but at least I see what
is this "k" you guys keep talking about and why we shouldn't
re use addresses for that reason.

wrong RNG or simple collision in the integer space used for K
Is orders of magnitude more feasible than brute forcing a key,
I assume. 

Btw, how big is the space  for k?
full member
Activity: 187
Merit: 109
Converting information into power since 1867
May 07, 2014, 05:32:56 PM
#93
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.
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.

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.

I already said this on this thread but I'll say it again: Stealth addresses. A lot simpler than cutting up pieces of paper, and achieves the same result  Smiley



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.

There may be a way around this problem, using Gregory Maxwell's Merkle tree-based auditing technique:

1. After receiving the donations to various addresses, the donation collector creates a Merkle tree: every leaf contains hash(address to which coins were donated, sum donated); every node contains hash(child 1, child 2) and the total sum of the donations contained in the children.
2. The donation collector creates a separate file for every donator, which includes the branch of the tree relevant to that donator (the path from the donation address to the root).
3. Since even the collector doesn't know who donated to which address (and therefore who should get each file), she encrypts each of these files with the public key of the address from which the donation came, and publishes all the encrypted files.  
4. Each donator decrypts the relevant file and verifies her inclusion in the root.
5. The donation collector publishes a receipt, proving that she bought the boss a gift which cost at least as much as the sum of the root.

This way, nobody knows who donated what, everybody knows the total sum donated, only the donation collector knows how many people donated and the distribution of the donation sums, and everybody knows that the collector didn't steal.

It's a bit complicated for such an obscure use case, but I just love how smart cryptography can solve everything  Grin



EDIT: Now that I think about it, maybe it's not such an obscure use case. We already discussed on this thread the advantages of stealth addresses for charities. Think about a charity that wants to initiate a limited-time fundraiser for a specific cause. It publishes a stealth address for donations. Every donation ends up in a different address, thus distancing donators from each other as well as from the charity. This increases privacy for the charity and for its donators, but lowers transparency.
To regain transparency, the charity uses the above auditing technique as soon as the fundraiser is over. It then produces evidence that it spent a sum of money at least as large as the root sum towards advancing the cause.
This could also be useful for things like crowdfunding campaigns on the bitcoin-only version of Kickstarter (does that exist yet?).
sr. member
Activity: 365
Merit: 251
May 07, 2014, 04:34:35 PM
#92
By providing a single address, everyone can see the average amount donated per person, and know how many people didn't donate.
Yes. That's information about the community.

Quote
Using additional information, it might become possible to make educated guesses about who gave how much.
Well, yes. You could go around and ask them, or you could guess that those who knew the boss longest would give more. That's not much Bitcoin can do about additional information.

Quote
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.
Sure, there are ways to use multiple addresses. You could just choose to not remember who got which address. If all this is happening through email, then it becomes harder for the co-workers to directly verify.

In general, when someone gives you a custom address online, you have to figure they can tie it to you (or whatever conversation you are involved in). Usually that's a good thing. When ordering a pizza, you want the payment to be tied to the delivery address.
donator
Activity: 1218
Merit: 1079
Gerald Davis
May 07, 2014, 03:44:56 PM
#91
I had updated my post but forgot to click submit.  I see you found the SEC spec.

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.  

I think the bolded part is more likely.  Satoshi also seemed unaware of the advantages of compressed keys as well.  A lot about the early code would suggest that Satoshi was a genius "big picture thinker" but cryptography may not have been his strongest suit.  None of this should be taken as criticism, it is amazing that Bitcoin worked effectively and securely from day 0, it is just an observation.

As I indicated above I believe (unless I am misreading the spec) that there are only two possible j values (0,1) for secp256k1 and thus two possible pubkey Q. The "j" can be encoded in the transaction making it unnecessary to try all permutations of j.  Bitcoin does this for signed messages by putting a flag byte in the header.  Even if the pubkey is recovered since Bitcoin supports both

Explicit PubKey = 34 (or 64) bytes per output.
Recovered PubKey (w/ hint) = 1 byte (and one recovery required) per output.
Recovered PubKey (no hint) = 0 bytes (and 1.5 recoveries on average) per output.

Quote
I see Gavin supported Satoshi's decision to include the public key.

He did at the time but I still wonder about that (and my guess is it wasn't a decision).  At the current rate the network is creating about 20 million transactions annually.  The average number of inputs per transaction is 2.4.  Even assuming 100% of them are compressed pubkeys that is still 34 bytes per PubKey or ~ 1.6 GB per year.  At the 1MB block limit the blockchain would increase by about 52 GB per year.  PubKeys would make up about a quarter of that if average number of inputs and outputs per transaction remain the same.  Computing power is the resource least likely to be a bottleneck (we are talking about tens of thousands of ECDSA validations per core per second).  It is far more likely as transaction volume grows and full nodes support more SPV nodes that bandwidth will be the first real world bottleneck. 

If necessary Bitcoin could be extended to support a new version of addresses that requires compressed keys, drops redundant DER encoding, and uses PubKey recovery to reduce the size of the average tx by 25%. It shouldn't be any more difficult than adding support for P2SH was unless I am missing something major.
Pages:
Jump to: