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

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

  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?

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)

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.

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.

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

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.

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

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.

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.  

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.

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.

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

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.

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.

So he'll only receive & never send ?

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.

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

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!

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