re-use of addresses

[jonald_fyookball]

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.  

[1714622568]

1714622568

[1714622568]

1714622568

[1714622568]

1714622568

[DeathAndTaxes]

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.

[jonald_fyookball]

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

[DeathAndTaxes]

Or if you want something from a government.

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

Digital Signature Verification
≥ 112 bits of security strength:
DSA: |p| ≥ 2048 and |q| ≥ 224
RSA: |n| ≥ 2048
EC: |n| ≥ 224

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.

[DeathAndTaxes]

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

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

[jonald_fyookball]

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

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.

[DeathAndTaxes]

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.

[Valle]

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.

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)

[jonald_fyookball]

So if you go to a website claiming to be your bank and enter sensitive financial information how do you know it is actually your bank?  It gets worse when you consider that the internet is a relay system 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 the hacker.

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

SSL isn't just about encryption it is also about authentication.  Eve pretending to be Bob and presenting a cert so Alice will use it to encrypt the sensitive information thinking that makes it secure is the problem CA are attempting to solve.  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" who has the private key.  How good of a job they do is debatable

  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?

[Peter R]

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?

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.  For 256 bit ECDSA keys used in Bitcoin that means 128 bit security.  I don't know why Satoshi chose a 160 bit PubKeyHash as a 128 bit one would be sufficient and would result in shorter addresses.

As a side note sometimes people ask why ECC, why not RSA? To achieve 128 bit security using RSA would require a 3,072 bit public key and that would mean very large transactions.

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.

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

[DeathAndTaxes]

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)

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

[Valle]

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

[innocent93]

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.

[BitCoinDream]

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

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.

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.

[TinyBBC]

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

[DeathAndTaxes]

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

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

[jonald_fyookball]

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?

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.  For 256 bit ECDSA keys used in Bitcoin that means 128 bit security.  I don't know why Satoshi chose a 160 bit PubKeyHash as a 128 bit one would be sufficient and would result in shorter addresses.

As a side note sometimes people ask why ECC, why not RSA? To achieve 128 bit security using RSA would require a 3,072 bit public key and that would mean very large transactions.

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.

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

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? 

[Peter R]

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.  

[BitCoinDream]

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

Well 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 the flaw was patched (assuming users installed security updates).  The 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.

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

[jonald_fyookball]

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

Well 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 the flaw was patched (assuming users installed security updates).  The 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.

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.