Bitcoin Forum

ok, so I understand that you shouldn't re-use an address
because then people will see the public key rather than
the hex-encoded hash, and it weakens the security
from 160 bit to 128 bit...

But, can you receive multiple transactions at the same
address (as long as you dont send) with no security
compromise?

Yes.  There is a second reason for not reusing addresses, and it is to improve privacy.  If you are receiving funds from different sources at the same address you still defeat that element.

It should be pointed out that 128 bit security is still beyond brute force for both current and future classical computing.  The main reason for not exposing the PubKey is if to protect it in case the strength of that key is ever reduced in the future.  This could be due to quantum computing making it possible to implement Shor's algorithm against the key, or ECDSA being weakened through cryptanalysis.  In both instances the effective security of the key will be reduced and known keys could be attacked without warning.

Also note that if you receive multiple transactions at an address, and then only spend some of the outputs, the remaining outputs will be left at an address for which the public key is known. Furthermore, if the wallet you are using does not use an unknown value for generating the signature then the remaining outputs become vulnerable.

So to be safe... when spending... always create a transaction that spends any unused part to one or more of your other Bitcoin addresses  (or new addresses) that have never spent anything.

And when receiving funds from someone, always receive them at a newly generated address, if possible.

Using these rules would achieve greater degrees of security and privacy than if you did allow yourself to reuse addresses.

try to explain it to a legit charity that does not care about privacy at all.
example: donation address to seans outpost

he does not care about privacy AT ALL infact he wants the world to know and use that address for donations, and he 'spends' the inputs manytimes a month. explain the risk and/or chance all their donations can be lost by using the same address.

(without meandering into a privacy concern)

Wait now I'm confused.  Are you talking about output to a change address? I thought the change address would be safe because we are not sending from it.

GreenAddress just wrote a blog post on address re-use:
 - http://blog.greenaddress.it/2014/04/30/reusing-addresses-is-bad-m-kay/

But this view is not universal, apparently:

- http://twitter.com/Mircea_Popescu/status/463072372896333825

and then:
 - http://log.bitcoin-assets.com/?date=04-05-2014#659487

which I read but still have no idea why Mircea would make that claim.

Anybody?

Outputs that are received at a Bitcoin address are individually spent in their entirety. If you are using a wallet with coin control you have the ability to choose which outputs are spent in a transaction, and can therefore make sure that all outputs received at a particular address are spent together in a single transaction. If you are not using coin control, then it is possible that some outputs will be spent separately from others that were received at the same address.

Bitcoin doesn't distinguish between change addresses and receiving addresses. At the protocol level, it's all the same.

I suppose what im still not understanding is this part about the remaining outputs would be left at address where the public key would be known.  Why would it be known?  This change address for the remaining outputs would be a receive only address.

Ok never mind, I think I get it.  You mean the other part of the money NOT in the change address.

Interesting, reusing address analogous to creating history for credit or consumer worthiness.  A mulling point.

all im reading is about privacy so people cant track you and that a public key will become............ public..

so to quote myself as i think the main point people are truly concerned with is losing their coins, so:


the layman wishes to know SECURITY risk not privacy risk

I think you misunderstand. If your public key is known then the security of your address is reduced.   Today assuming the wallet implementation is proper it is reduced by 160 bit to 128 bit security.  It is the public knowledge of the PubKey which reduces the security of the funds.  So public knowledge of the PubKey IS a security not just privacy issue.

Can a known PubKey lead to a loss of funds?  In most cases in may not but
* if Quantum Computing ever advances to a point where it is economical to break a 256 bit PubKey your funds could be stolen.
* if cryptanalysis advances to a point where it becomes possible to brute force a 256 bit PubKey your funds could be stolen.
* if your wallet implementation (or underlying library and/or OS) through deliberate intent or negligence ruses the same k value for the same PubKey your funds could be stolen.

There is no way to quantity the risk of the the first two factors however if it happens and you have funds stored in a know pubkey it will be too late.   The third scenario has already happened multiple times (android OS and bitcon.js).

The hash of the pubkey is a secondary line of defense.  It is like asking why can't I clean a firearm while it is loaded and the safety off.  In theory if you do everything right you could accomplish that without incident but taking that risk serves no purpose and if it doesn't end badly for you, if enough people try it, it will end badly for someone.

It seems my electrum wallet is pretty good about automatically creating new addresses for most transactions.

I was just reviewing my cold storage coins and seems that the main addresses are only used once despite a few transactions in the wallet.

Any Localbitcoin Sellers on here?

Reading this thread made me a bit worried about the auto-generated blockchain wallet attached to our accounts.

Apparently we can change them (+still have access to previous?) but thought it's pretty damn secure at any rate. What do you guys reckon?

I don't re-use addresses but I might as well because I use a wallet (armory) program that can send from any of my addresses.  kind of annoying

Blockchain.info ?  That's an online wallet.  The main risks there are
some hacker steals your password (please set up 2FA!) or
the site itself is hacked or internally compromised.  (Goxxed).

Although I trust Blockchain (Andreas Antonopolous is their chief of security)
infinitely more than Mark Karpeles and Gox, its still an online wallet
and it could happen.

Those things are probably more likely to happen than
you losing your coins because of address re-use.

I think I can quantify this!

with the current hash power for BTC if everyone would mine in a pool to brute force your address  then first the sun will explode and after they will break into your address ... witch will be pointless because we won't have any sun :)

He said cryptoanalysis and quantum computing, not ordinary brute-forcing, but you're right.  ;)

On a side note, will the sun really "explode"  or just burn out?

Cheers J

Assumed it was autogenerated from the blockchain.info with multisig because when you click on the address in "wallet", links to site.

But see what you mean  :)  So do they move our BTC funds when we deposit into:

cold storage wallet<trade request<cold storage to Buyers withdrawal address ?

No you can't.


Which has nothing to do with the points you "quantified".

Nope, Not our SUN! He is too small!

If you are interested you might want to check this article http://www.universetoday.com/107791/will-the-sun-explode/

Enjoy ;)

You can't blame me for my condition!

I have no idea about the internals of blockchain or how
they are handling their cold wallets.

What I would like to know now is
on a technical level, WHY
you can safely re-use a receiving address
but not a sending address?

we are using cryptography to sign
the transaction and verify the
transaction... so why does
the address become known only
on the sending side and not
the receiving side?

Is this a feature of all the altcoins
as well?

ok time to not be subtle

after all whats the point in telling everyone that bitcoin is so great due to funds being secured by 256bit and elliptic curved private keys at the back end of a transaction which never appear on the blockchain, if someone can steal funds from the front end that are only 128bit secured using publicly available data

so my next question:

so everyone should be screaming at 'seans outpost' that he can lose all donations in his address tomorrow?? not next year or 10 years time when quantum computers are around.. but tomorrow.

or is this just a hypothetical future-proofing of a possible risk relating to quantum computers maybe in the future cracking 128bit

 i only ask this in common human understanding so that the laymen of the world who are already gossiping and starting to FUD spread that bitcoin is already broke due to a re-use address vulnerability

1. we just established that its ok to re-use a receive-only address and you stay at 160 bit security.

2. even if an address is re-used for sending and you're down to 128 bits of security, its still
hypothetical weakness.  Quantum computers today cannot compute/factor more than a few bits, and
there is no known weakness to the elliptic curves used in Bitcoin.

This has been asked and answered thee times.   Reusing addresses reduces security.  Period.   The risks can't be quantified as an exact % of losing funds tomorrow or next year, or next decade but the risk is increased, the margin of safety is decreased.

If tomorrow Sean signed a tx using a flawed wallet which used a repeated k value then hacker would probably detected that and exploit it within seconds emptying the wallet.   If addresses were not reused then there would be no risk even if same k value was used.  Likewise we simply do not know if/when cryptanalysis will yield usable exploits againsts ECDSA.  It could be tomorrow or might never happen before you die.   It isn't something that can be definitively quantified.  Hashing the public key is a secondary safety.  You can remove that safety and if the primary safety (the security of ECDSA and the secp256k1 curve) remains intact you are fine.   In other words you are safe until you aren't.

Wow.  I didn't know that scenario existed. 

I guess there are MANY things that could wrong
with a flawed wallet, including weak cryptography,
coins being burned, or something as dumb as
it accidentally deletes your private keys.

The first thing you need to do is remove incorrect concepts like receiving and spending addresses.   There is no such thing.   There are only addresses.   The protocol doesn't even use addresses it converts addresses to the raw PubKeyHash (which is a hash of the Public Key).

When you send funds to a given address you are actually sending it to the PubKeyHash.  The transaction becomes a public record thus the PubKeyHash (and the address can be computed from it) is a known however the Public Key (PubKey) is NOT known.   Look at the output of any transaction  the funds are sent to a PubKeyHash (160 bits).

For example here is a recent tx (pulled at random).   
http://blockchain.info/tx/4c555be716ccf923252ae118f2e9719a7ce6d4fdbf52a8cc03489b330debbd01

Funds were sent to 1Fv1uSsxr8z4hCHi2yhzuLf2sQafJfLbF8

Technically the output is this

a3988fd05be9c9b642503e61ec6bb6ed553ab8a2 is the PubKeyHash which corresponds to address 1Fv1uSsxr8z4hCHi2yhzuLf2sQafJfLbF8.

So the PubKeyHash is known and if you search the blockchain by address you will see this address received funds multiple times.   However the PubKey is unknown.  What is the PubKey for a3988fd05be9c9b642503e61ec6bb6ed553ab8a2?  There is no feasible method of finding out (unless you already know because you have seen the PubKey.

Now if 1Fv1uSsxr8z4hCHi2yhzuLf2sQafJfLbF8 spends some but not all of these outputs then in the input side of the tx, to "prove" the outputs correspond to his keypair the user will provide the PubKey.  The PubKey becomes known when it is spent because it is provided in the input side of the spending transaction.   Until that happens the PubKey is unknown.

If tomorrow there was an exploit which required knowledge of the PubKey this user would not be immediately at risk.


If they were based on Bitcoin or a derivative of Bitcoin then yes.  If they were completely new then it is possible this doesn't apply although I don't know of any.

Thanks for the lesson.  :)

(I was also unaware that there was a separate PubKeyHash.)

Follow-up question:


What if they spent all?  Wouldn't we still need to provide the PubKey as an input?  

Yes but there would no longer be any unspent outputs associated with that keypair.  It is more of an issue if you don't spend all the outputs.

Inputs are just references to specific outputs.

So say your address was assigned the following outputs

1 BTC to Address A
1 BTC to Address A
3 BTC to Address A
5 BTC to Address A
All these outputs would be locked to the PubKeyHash (decoded addresses).   The PubKey is unknown to the public.

Now lets say you wanted to send 0.5 BTC to your friend.  Your wallet may construct a tx with 1 BTC as the input and two outputs 0.5 BTC to your friend and 0.5 BTC in change.

So you are left with
1 BTC to Address A spent
1 BTC to Address A
3 BTC to Address A
5 BTC to Address A
0.5 BTC to Address A (or B depending on wallet behavior) <- your change

The issue is the tx spending the 1 BTC revealed the PubKey for address A however you still have another 9 BTC in other unspent outputs which share the same address, pubkeyhash, and pubkey.   The attacker now knows the PubKey for your other 9 BTC.  This by itself doesn't allow the theft of funds however if there is a flaw/weakness which requires the PubKey to be know, spending 0.5 BTC left 9 BTC in a weakened state.

On the other hand if you didn't re-use addresses each of those outputs would be a different Address:
1 BTC to Address A spent
1 BTC to Address B
3 BTC to Address C
5 BTC to Address D
0.5 BTC to Address E <- your change

The PubKey for Address A has been revealed however there are no unspent outputs associated with A.  You don't really need to think about it, this is the default behavior of most clients (including bitcoin-core).  Just request a new address whenever someone needs to send you funds.

Yes, I understand.

In a nutshell, I believe the answer to my question is:
the transaction is signed once with the public key
of the sender (which is then visible), and
the protocol requires nothing further to create those
outputs and send them along.

well no he can keep clearing that address.

Not if he wants to maintain highest level 160-bit security!  That's what we just got done discussing.
But i guess it doesn't matter since he wouldn't have that much at any given time if it kept clearing.

It's only tomorrow if his wallet is flawed. Since these issues are well-known by wallet authors, his wallet is probably fine. In which case, he has 128-bit security and that is pretty good. He can mitigate the risk by transferring funds out frequently, and by monitoring the news for developments in quantum computing. He probably figures his expected loss from reusing addresses is more than compensated by the donations he gets from having a fixed, published address.

Yes u only reveal a part of the key when u use it to create a transaction

Simple solution: Stealth Addresses.
In this context, "Stealth" is a misnomer. Stealth addresses can be used to receive bitcoins in a "stealthy" manner, but they are also perfect for organisations like charities that are interested in the exact opposite of stealth - high public exposure for one particular donation address. With stealth, they can publish one address publicly but never actually receive any coins with it, thus maintaining all the privacy and security advantages of not re-using addresses.


By the way, it's not at all true that legit charities don't care about financial privacy.
They care about their own privacy: no one needs to know where they send their donated coins. If they want to be transparent (and they should), they will publish a full report detailing their expenses, but they don't necessarily want the money to be easy to track.  
They should also care about the privacy of the people who donate to them: I'm not sure you'd want the government to know that you donated to wikileaks. Of course it's your job to worry about your financial privacy; personally, I always mix before donating. But it sure would make things easier if the charities I donate to would use stealth addresses.

how long until stealth features part of core and stable?

Agreed.  There is also the security aspect to consider.  Say some Bitcoin millionaire decided to drop a ten thousand BTC into Sean's wallet.  That information will be instantly and globally available, even to bad actors.  For that kind of money someone may decide to engage in some rubber-hose cryptanalysis (aka $5 wrench analysis http://xkcd.com/538/ ).  The idea that literally the entire planet needs to know every detail of your finances to provide accountability is a naive implementation of a good concept.

In the future, instead of "security by wesson" , my house will say "security by multisig"  :)

As DeathAndTaxes pointed out, the security level is reduced from 160 bits to 128 bits when the public key is known.  This is fact.  Inspecting the 30 richest bitcoin addresses (http://bitinfocharts.com/top-100-richest-bitcoin-addresses.html), I found 9 with publicly known public-keys, representing a total of 419,308 BTC.  The individuals and groups that control these address are obviously confident with 128-bit security and (IMO) the extremely-small risk of compromising secp256k1 by crypto-analysis or by breakthroughs in quantum computing.




I'll probably be torn to shreds for this comment, but it is my opinion that no one will ever lose a single satoshi due to a security weakness at the protocol level.  The vastly more real threats in my opinion are user and developer error.  User errors include losing keys due to theft, malware, damaged paper wallets, forgetfulness, trusting incompetent of unscrupulous third-parties, etc.  Developer errors centre around leaking private keys, for example due to reuse of the per-message secret number k while producing an ECDSA signature, or generating bitcoin addresses that don't actually correspond to a known private key.

What are you talking about?  How do you weaken the stregnth of the security by exposing the public key.  Asymmetric cryptography is built around the notion that you must expose the public key.  Doing so is a key (pun intended) part of the process.  You assume NO security around the public key and protect the private key.


Also keep in mind that is 128 Bit keys become weak, then there is a bigger problem than Bitcoin wallets.

I most agree with your assessment with the exception of "never".  Never is a very long time and I believe Bitcoin will need to be extended to more secure cryptographic primitives on a long enough timeline.  Not sure about you, but if we get to a place where known pubKeys are considered cryptographically weak and developers are implementing a transition to addresses based on stronger cryptography I would much rather wait that out holding value in unknown PubKeys.

Still I would point out that known public key and leaking private key are not mutually exclusive.   The most notable developer error involves repeat k values.  Repeat k values can only apply in an address reuse scenario.  If your wallet has a flaw which leads to a repeat k value you are insulated from that risk by not reusing addresses.   That is why I likened the PubKeyHash as a secondary safety.  Sure if the primary security system is flawless against all current and future threats then there is no need for a second safety.  I have never needed my backup chute when skydiving, and statistically I probably never will, that doesn't mean I jump with one chute though. :)

It's been explained a couple times already:

    -  the security level is reduced from 160 bits to 128 bits.  
    -  finding the discrete logarithm of a random elliptic curve element with respect to a publicly known base point must remain infeasible.  

Please read.  I said explicitly that 128 bits of security is beyond brute force for both current and all conceivable future classical computing.   However that doesn't mean that ECDSA will always have 128 bit security (emphasis to the portion you quoted and ignored).

What is the strength of a 256 bit ECDSA public key if the same k value is used for multiple transactions? 0 bits
What is the strength of a 256 bit ECSDA public key in the safe of a QC implementing Shor's algorithm? Potentially very low
What is the strenght of a 256 bit ECSA public key if weaknesses are exposed which reduce the effective security of the cipher?  <128 bits (how low depends on how severe the flaw)

So while 128 bit strength is beyond brute force there is no guarantee that both today and in the future that secp256k1 will have 128 bit security.  History is full of ciphers which have degraded security.  Some degraded to a point of only academic curiosity (say 112 bits is degraded but there is no economical attack) and some degraded to a point where attacks became trivial.

Most notably in the face of flawed k value selection (Android RNG, bitcoin.js, etc) re-used addresses had an effective security of 0 bits while addresses which were not re-used (pubkey remained unknown) had 160 bits of security.

Same wallet, same set of keys, same implementation and the security varied from 0 bits to 160 bits based solely on if the key had be re-used.  Yes I would call that a reduction in security.

"Never" was purposely provocative.  I do agree with your assessment that given enough time bitcoin will need to be extended to more secure cryptographic primitives.  But I think that any weaknesses will emerge very slowly such that by the time it is feasible to attack one of those 9 rich addresses, the funds will be protected by better security.  


It is a fact that repeat k-value problems can only apply in address re-use scenarios, so I agree that address re-use introduces a new risk.  You've suggested deterministic k-values in the past [as per T. Pornin, “Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA),” from Request for Comments: 6979, ISSN: 2070-1721, August 2013] and hopefully we see a push in this direction.  

But here's why I like address re-use sometimes: when someone asks me for help getting set up with bitcoin, I normally create a laminated paper wallet for them (and a TrueCrypt back-up).  But I can see it in their eyes that they don't trust the paper wallet.  So what I invariably do is (a) send the paper wallet 0.1 BTC, (b) produce a signature using the paper wallet to spend that 0.1 BTC, (c) broadcast the TX to the network (their public key is now known), and (d) prove to them that this particular paper wallet works when they see the transaction confirmed.  We then load the paper wallet with additional funds.  

I know that this is not optimally secure, but the new user is actually more confident because they've already witnessed that this particular key works.  It seems people understand that the key can't "break" in the future because it's just a number, but how do you explain to someone that the key didn't come "broken" if you never test it?  I know you can sign some text and verify the ECDSA signature locally, but this only convinces me because I understand how bitcoin works.  It is not at all convincing to my mom, for instance.  

Good point Peter.  that's a lot of coins for the "taking" :)

Agreed.  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.  At BitSimple we do allow address reuse on "deposit addresses" <gasp>.  There is no way to technically prohibit a user from depositing more than once.  If we ask them not to, some users will still do.  However we do periodically sweep deposit addresses and prevent reuse in the primary wallet.

I reuse my address all the time, but after reading this, i will consider retiring my main receiving address.

I believe brute forcing an address takes time. So, I assume it would still be safe to reuse an address over a short period of time. My address do not have much anyway.

There is no risk of brute forcing an address.  PubKeys with 128 bit security are beyond brute force for both current and future classical computing.  The laws of physics protect the PubKey from brute force attacks, the PubKeyHash provides a secondary line of defense against other potential attacks (quantum computing, cryptanalysis of ECDSA, flawed k value generation, etc).  It is still a good idea to no reuse addresses but the possibility of someone by brute force generating the same private key is essentially for all practical purposes zero.

When i said coins for the "taking" (in quotes), I was being facetious. 
(If they can't take the 419,308 coins, they won't be coming after yours.)

Why all the really interesting threads only get a few hundred views? Topic: re-use of addresses  (Read 726 times)

while the ponzies get thousands of thousands views ???

This is really one interesting topic! And you can actually learn something from it!

I can see the long tech discussions in the whole thread where the outcome is Dont use an address twice. Now just think how bad impact it will have on an average person in terms of use. It is like asking him to create a new email ID for every mail communication. I wonder, if an wallet can solve this problem ? Like the person will only provide a certain unique identity for send/receive and rest will be managed internally that he does not need to bother. Please note, the average Joe is more bothered about ease of use rather than security. And if the security is breached, he'll be the first to yell at us saying Bitcoin protocol is broken and we are all scammer.

Please think about it...

Those unique identifiers are called addresses. :)  Addresses are more like order numbers than email addresses.   Wallets do manage this internally for users.   They can request a new address, the wallet keeps track of all the private keys and when the user wants to spend funds he just says how much and the wallet finds the set of unspent outputs corresponding to those multiple addresses that have sufficient value for the transaction.

So he'll only receive & never send ?

I don't think you read that carefully.

the outcome was:  don't use an address twice but if you do, it probably won't matter as long as its not a flawed wallet.  That being said, many wallets do automatically give you new addresses.

When he sends the only address which needs to be provided is the receivers.  The wallet internally (just like you asked) figures out which of the unspent outputs to reference in the new transaction.  From the users point it is just send X to Y.

Private key is 256 bit. Public key is 256 bit too. Hash of public key is 160 bit. How revealing of public key (256 bit) reduce strength to 128 bit? It's reduced to 256 bit ECDSA. I fail to see the 128 bit strength :-)

The bit strength of a key refers to the equivalent strength of a symmetric key of that length.  The key strength is only equal to the length of the key for uncompromised symmetric ciphers (and usually hashing algorithms).  For public key cryptography, the bit strength will always be less than the key size.  For ECDSA it is 1/2 the key length if the algorithm is uncompromised.   That means the 256 bit ECDSA keys used in Bitcoin have 128 bit security.  As algorithms are weakened through cryptanalysis the effective security sometimes drops below the initial spec.


I don't know why Satoshi chose a 160 bit PubKeyHash to pair with a 256 bit PubKey (128 bit effective security).  It probably would have made more sense to either use 128 bit PubKeyHash and 256 bit ECDSA (same security and shorter addresses) or 160 bit PubKeyHash and 320 bit ECDSA (higher key security for same size addresses).  As a side note sometimes people ask why was ECDSA chosen instead of RSA? To achieve 128 bit security using RSA would require a 3,072 bit public key and that would mean very large transactions.  It gets even worse if higher security keys are needed in the future.  For ECDSA the security is linear and thus double security (256 bit) could be achieved with double the key size (512 bit) but for RSA to achieve 256 bit security would require a 15,384 bit key.

Can you give any links what proves the point please? I can understand that hashing to 160 bit means that there are many ECDSA 256bits what corresponds to an address, but saying that real security of ECDSA is 340282366920938463463374607431768211456 times lower than it's key size sounds... strange.

Funny I just posted in another thread just now... I too would like to know more about ECC. If there are any good videos for beginners , please let us know.  :)

https://en.wikipedia.org/wiki/Key_size#Asymmetric_algorithm_key_lengths

If you think that is strange as pointed out it takes 3,072 bit RSA key to achieve the same security.

Also note that in 2010 a 768 bit RSA key was broken by brute force.   
http://www.theregister.co.uk/2010/01/07/rsa_768_broken/

There isn't sufficient energy in our solar system to do that to a symmetric 256 bit key in the lifetime of our sun yet it was done for a 768 bit RSA key in a few years.  Why?  It takes far less operations to brute force a RSA key than its key length would suggest and as such a 768 bit RSA key isn't the equivalent of a 768 bit symmetric key but closer to a 64 bit symmetric key.   For SSL no CA will issue a 1,024 bit RSA key anymore due to the fact that it only has 80 bit key strength and thus is on the edge of what a dedicated (think NSA) attacker could brute force.

Never really thought about it before, but now I see "that's why those SSL certs are so darn long."

Or if you want something from a government.

http://csrc.nist.gov/publications/nistpubs/800-131A/sp800-131A.pdf


NIST sets the (US) requirements for systems that are involved in classified material. For Digital Signature applications that require 112 bits strength an ECC curve which is 224 bits or larger is required.

They would be shorter if CA issued certs using ECC although so far the switch by CA to ECC has been very slow.

What's the point of even having a CA?  Even if a site is self-signing , that's who you're giving your info to anyway.  Instead of browsers checking authority, I would think they should be checking the strength of the encryption directly.

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?  By definition a self signed cert could be created by anyone.  While the info can't be snooped by a third party it doesn't do you much good if the attacker IS the entity you are communicating with.   It gets worse when you consider that the internet is a relay network and anyone between you and your bank your provide you a cert so you happily encrypt your sensitive information using a key that can be decrypted by them.

You <-----> Hacker <------> Financial Site

SSL isn't just about encryption it is also about authentication.  The goal is to provide assurance that when you receive a cert indicating it was issued to "Trusted Bank USA" that it actually IS "Trusted Bank USA" and not the guy running a MITM attack at your local starbucks.  How good of a job, CAs do is debatable but that is the goal.

Thanks, that's very interesting!

Do you know most "promising" attack on the ECDSA? (I'll try to google it for now by myself ;-) but maybe you know something interesting about)

  If you mistyped the domain, or a browser virus redirected you, a CA issued cert to the rouge domain wouldn't raise any warnings.  Are you saying a CA won't issue certs for misspelling domains etc?

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
http://en.wikipedia.org/wiki/Elliptic_Curve_DSA

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".

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 :-)

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.

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.

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

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.

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 (http://en.wikipedia.org/wiki/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 (http://en.wikipedia.org/wiki/Elliptic_Curve_DSA) 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.  

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

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.

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).

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.

- 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.

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.

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.

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 (http://en.wikipedia.org/wiki/Elliptic_Curve_DSA#Signature_verification_algorithm).  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  :)

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 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 (http://www.secg.org/download/aid-780/sec1-v2.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://bitcointalk.org/index.php?topic=6430.msg94290#msg94290

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.

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.

I had updated my post but forgot to click submit.  I see you found the SEC spec.


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.


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.

Yes. That's information about the community.

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.

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.

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  :)




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  ;D



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?).

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?

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).  

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. :)

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). :)

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).


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).  

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...

 :P

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.

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


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.

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.

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.

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.

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) (http://www.cloudflare.com/network-map) 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:

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

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 :/

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 :)

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.

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?

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.

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.