Crypto question: Breaking ECDSA for all key-pairs simultaneously?

[Sergio_Demian_Lerner]

Is there a method to break an ECC curve for all key-pairs (Q,d) such that (Q=d*G) faster than breaking every single key-pair? Is there any memory trade-off that helps such attack?

If so, then, as Bitcoin grows, the monetary incentive for an attack to the curve will increase over time. An attacker that could break the whole curve at once could steal all the money.

If not, then there is nothing to worry about since the use of unique addresses and the slicing of payments of high value into low value payments can reduce the incentive to a minimum.

Obviously this is not a problem we should worry in the nearby future, but maybe we should in 30 years.

Best regards,
 Sergio.

[kjj]

In the unlikely event that secp256k1 is ever totally broken, there is still the hashing problem to deal with.

As in, even if someone can find the private key for every possible public key, most public keys aren't known, only the RIPEMD160(SHA256(public_key)) is in the blockchain, unless you re-use addresses, which everyone has been warned not to do.

[Etlase2]

30 years is a pretty long time frame, and bitcoin's ECC is only 128-bit security which crypto experts predict is only good until 2020 or so. Any attack that involves speeding up key breaking will probably be thwarted to some degree by adding another 32 bits.

As in, even if someone can find the private key for every possible public key, most public keys aren't known, only the RIPEMD160(SHA256(public_key)) is in the blockchain, unless you re-use addresses, which everyone has been warned not to do.

I may be mistaken, but I remember reading that coinbase transactions are, by default, sent to a public key and not a hash. So if those early coins are indeed lost, they will eventually be found by someone else.

[kjj]

Maybe before, but right now a typical txout in a generate looks like:

Code:

  "out":[
    {
      "value":"50.24250000",
      "scriptPubKey":"OP_DUP OP_HASH160 740ecaf436d5867903c722d783fc994c25a29b15 OP_EQUALVERIFY OP_CHECKSIG"
    }
  ]

[Remember remember the 5th of November]

Well, there are 115,792,089,237,316,195,423,570,985,008,687,907,852,837,564,279,074,904,382,605,163,141,518,161,494,337 private keys according to the wiki article(not full 2^256 because of secp256k1).

And this number is pronounced as

one hundred fifteen quattuorvigintillion, seven hundred ninety-two trevigintillion, eighty-nine duovigintillion, two hundred thirty-seven unvigintillion, three hundred sixteen vigintillion, one hundred ninety-five novemdecillion, four hundred twenty-three octodecillion, five hundred seventy septendecillion, nine hundred eighty-five sexdecillion, eight quindecillion, six hundred eighty-seven quattuordecillion, nine hundred seven tredecillion, eight hundred fifty-two duodecillion, eight hundred thirty-seven undecillion, five hundred sixty-four decillion, two hundred seventy-nine nonillion, seventy-four octillion, nine hundred four septillion, three hundred eighty-two sextillion, six hundred five quintillion, one hundred sixty-three quadrillion, one hundred forty-one trillion, five hundred eighteen billion, one hundred sixty-one million, four hundred ninety-four thousand, three hundred thirty-seven

[Sergio_Demian_Lerner]

I understand your concerns regarding RIPEMD160, but that is another problem, unrelated to my question.

My question is, in other words: Can discrete log finding algorithms be modified to break many/all key pairs at a price not much higher than breaking a single pair.

I've read baby-step giant-step algorithm for solving the discrete log and it uses a pre-computed table that can be reused to break following keys, but I don't know how the cost of building the table relates to the total cost of the algorithm. If building the table is 99% of the required time, then one can break 100 keys at the price of one.

I don't see how Pollard's rho algorithm for logarithms can be optimized to break many key-pairs at the price of one.

I've been thinking about the idea of adding an optional 160-bit ECC curve to Bitcoin signatures in order to allow low-value payments to use half of CPU resources. I don't mind if individual keys are broken (since the cost of the attack will be orders of magnitude higher than the payoff). But I's a problem if all key-pairs can be broken at the same time.

[Pieter Wuille]

I believe that as long as no k value in the ECDSA process signing is reused, having multiple signatures to observe should not make it easier to break the security. If that were possible, it would constitute a weakness in the algorithm.

I'm not cryptographer though.

[Etlase2]

I've been thinking about the idea of adding an optional 160-bit ECC curve to Bitcoin signatures in order to allow low-value payments to use half of CPU resources. I don't mind if individual keys are broken (since the cost of the attack will be orders of magnitude higher than the payoff). But I's a problem if all key-pairs can be broken at the same time.

I have actually thought about this idea for the cryptocurrency proposed in my sig. But, now that the optimizations of ECC that have come to light (especially Ed25519), and batch optimizations that don't exist currently in the bitcoin code, I don't think CPU time will really be much of an issue in the future. The bandwidth savings of using a 160-bit curve might be more significant though if a cryptocurrency were to be popular in poorer countries. Could save potentially 8-24 bytes per transaction, which might be significant. Hard to say. I don't know whether 160-bit curves can be batched with 256-bit curves though and that might present a problem where it is slower to process the 160-bit curves if there are not that many.

[Sunny King]

Maybe before, but right now a typical txout in a generate looks like:

Code:

  "out":[
    {
      "value":"50.24250000",
      "scriptPubKey":"OP_DUP OP_HASH160 740ecaf436d5867903c722d783fc994c25a29b15 OP_EQUALVERIFY OP_CHECKSIG"
    }
  ]

Hmm. I checked latest bitcoin code looks like it is still paying to public key. Are you sure this coinbase output is generated by bitcoind not some pool's modification?

[kjj]

Maybe before, but right now a typical txout in a generate looks like:

Code:

  "out":[
    {
      "value":"50.24250000",
      "scriptPubKey":"OP_DUP OP_HASH160 740ecaf436d5867903c722d783fc994c25a29b15 OP_EQUALVERIFY OP_CHECKSIG"
    }
  ]

Hmm. I checked latest bitcoin code looks like it is still paying to public key. Are you sure this coinbase output is generated by bitcoind not some pool's modification?

Yup, blocks generated entirely inside the standard client do indeed push a key and OP_CHECKSIG.

But, I don't think that many blocks end up in the chain using the standard client's CPU mining capability or getwork RPC calls.  Maybe I'm wrong about that, but none of the random blocks that I clicked on in blockexplorer a while back were built using just the key and OP_CHECKSIG.

And of course, as soon as I type this out, I click on a block from Slush, and sure enough, it is using key + OP_CHECKSIG.  So maybe it isn't quite as rare as I thought.

Maybe I'll turn my spare GPUs to cracking ECDSA when I convert to ASICs.

[Sunny King]

Maybe I'll turn my spare GPUs to cracking ECDSA when I convert to ASICs.

You must be joking right? If it's remotely feasible for a world ranked super computer to crack a key surely bitcoin would have already upgraded? 

Is it even remotely feasible to design ASIC to crake a key?

[keystroke]

In the unlikely event that secp256k1 is ever totally broken, there is still the hashing problem to deal with.

As in, even if someone can find the private key for every possible public key, most public keys aren't known, only the RIPEMD160(SHA256(public_key)) is in the blockchain, unless you re-use addresses, which everyone has been warned not to do.

I always thought address reuse was mainly to protect privacy somewhat - would you mind explaining this more? How does address re-use let the public key be known?

[Etlase2]

Maybe I'll turn my spare GPUs to cracking ECDSA when I convert to ASICs.

GPUs are no good at point multiplication from what I was able to discover on the very limited amount of data on the subject a few months back. Parallelization is not a performance enhancement.

I always thought address reuse was mainly to protect privacy somewhat - would you mind explaining this more? How does address re-use let the public key be known?

It is about privacy, for the most part. When you send a transaction with an address that is only known to the network as a hash, you must give your public key, or your public key will be derived from the signature. Then the network knows the public key for that address. But as RIPEMD160 is "160 bits of security" vs. the effective 128-bits of security of a 256-bit elliptic curve, it is 32 bits more secure in a sense, but not really against a brute-force attack as it just adds another step of first converting private keys into public keys (a relatively slow operation compared to hashing) then hashing (very fast) to see if it matches the hash. But since a RIPEMD160 hash is not necessarily just a hash of a public key (could be scripts or something else to throw it off, or one of several signature algorithms in the future), the address space being larger does make it somewhat more secure under some circumstances.

[CodesInChaos]

Question was cross-posted on crypto.stackexchange.

[keystroke]

Maybe I'll turn my spare GPUs to cracking ECDSA when I convert to ASICs.

GPUs are no good at point multiplication from what I was able to discover on the very limited amount of data on the subject a few months back. Parallelization is not a performance enhancement.

I always thought address reuse was mainly to protect privacy somewhat - would you mind explaining this more? How does address re-use let the public key be known?

It is about privacy, for the most part. When you send a transaction with an address that is only known to the network as a hash, you must give your public key, or your public key will be derived from the signature. Then the network knows the public key for that address. But as RIPEMD160 is "160 bits of security" vs. the effective 128-bits of security of a 256-bit elliptic curve, it is 32 bits more secure in a sense, but not really against a brute-force attack as it just adds another step of first converting private keys into public keys (a relatively slow operation compared to hashing) then hashing (very fast) to see if it matches the hash. But since a RIPEMD160 hash is not necessarily just a hash of a public key (could be scripts or something else to throw it off, or one of several signature algorithms in the future), the address space being larger does make it somewhat more secure under some circumstances.

Thanks Etlase2! Where is the best place to read about these internals? I am going to study https://en.bitcoin.it/wiki/Transactions but is anywhere else good? Besides the source code

[keystroke]

Maybe I'll turn my spare GPUs to cracking ECDSA when I convert to ASICs.

GPUs are no good at point multiplication from what I was able to discover on the very limited amount of data on the subject a few months back. Parallelization is not a performance enhancement.

I always thought address reuse was mainly to protect privacy somewhat - would you mind explaining this more? How does address re-use let the public key be known?

It is about privacy, for the most part. When you send a transaction with an address that is only known to the network as a hash, you must give your public key, or your public key will be derived from the signature. Then the network knows the public key for that address. But as RIPEMD160 is "160 bits of security" vs. the effective 128-bits of security of a 256-bit elliptic curve, it is 32 bits more secure in a sense, but not really against a brute-force attack as it just adds another step of first converting private keys into public keys (a relatively slow operation compared to hashing) then hashing (very fast) to see if it matches the hash. But since a RIPEMD160 hash is not necessarily just a hash of a public key (could be scripts or something else to throw it off, or one of several signature algorithms in the future), the address space being larger does make it somewhat more secure under some circumstances.

Ok cool, I read about this some more and I want to make sure I am starting to understand it. Please correct me if I am wrong. So the idea is that receiving multiple times to one address would not be bad, because in that case only the hash is published. But the problem comes in if you spend coins from that address (in which case 100% of them are sent, some to the receiver, and some back to you as change in a new address), and THEN you again receive coins to the address which you received from. In this case you now have BTC "in an address" which has a public key published to the block chain. Is that right?

Thanks!

[Etlase2]

In this case you now have BTC "in an address" which has a public key published to the block chain. Is that right?

That's right. As far as the best place to learn, I think I learned pretty much everything from reading these boards. 

[ByteCoin]

Is there a method to break an ECC curve for all key-pairs (Q,d) such that (Q=d*G) faster than breaking every single key-pair? Is there any memory trade-off that helps such attack?

All known serious algorithms for computing what have become known as "discrete logarithms" on elliptic curve over fields of prime order have a very extensive precomputation step, which, when completed allows arbitrary solutions to be computed quickly.

30 years is a pretty long time frame, and bitcoin's ECC is only 128-bit security which crypto experts predict is only good until 2020 or so.

Please provide a citation for this "fact". There is an attempt underway to calculate discrete logs on a 130-bit elliptic curve over a prime order field. Without some massive algorithmic improvements we're not going to have any chance of attacking 256-bit curves in eight years. I seem to recall that there is some speculation that humankind will never be able to count up to 2^128 let alone perform an attack with such a work factor.

ByteCoin

[Etlase2]

Please provide a citation for this "fact". There is an attempt underway to calculate discrete logs on a 130-bit elliptic curve over a prime order field. Without some massive algorithmic improvements we're not going to have any chance of attacking 256-bit curves in eight years. I seem to recall that there is some speculation that humankind will never be able to count up to 2^128 let alone perform an attack with such a work factor.

ByteCoin

I read a paper on it, though I checked my saved documents and it doesn't appear that I had saved it and I don't remember the author. It was also written more in the sense about symmetric cryptography and how long do you need your data to be secure and such, and backing it up with information regarding moore's law and other factors. 128bit might have been 2030 too, I'm just going from memory which is why I said "or so." 256-bit security is the magical number that would be impossible to count to, though 128 is still pretty significant. But DSAs and SHAs are more prone to vulnerabilities than symmetric cryptography, so how long 128 bits will be secure remains to be seen.

[keystroke]

In this case you now have BTC "in an address" which has a public key published to the block chain. Is that right?

That's right. As far as the best place to learn, I think I learned pretty much everything from reading these boards. 

Neat, thanks Yea these boards are great! So would there be a disadvantage from then sending *all* coins in a wallet to a new address? That would clean things up so to speak. Could there be any disadvantages you could think of? One could possibly be that if someone sent coins to one address, and then saw it sent as an input along with other inputs in a transaction, they would be able to tie the owner to the other addresses (if they knew who s/he was), right?

Thanks!