Bitcoin Forum
November 21, 2017, 03:55:35 PM *
News: Latest stable version of Bitcoin Core: 0.15.1  [Torrent].
 
   Home   Help Search Donate Login Register  
Pages: [1] 2 »  All
  Print  
Author Topic: Crypto question: Breaking ECDSA for all key-pairs simultaneously?  (Read 4256 times)
Sergio_Demian_Lerner
Hero Member
*****
expert
Offline Offline

Activity: 539


View Profile WWW
September 12, 2012, 03:48:48 AM
 #1

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.
1511279735
Hero Member
*
Offline Offline

Posts: 1511279735

View Profile Personal Message (Offline)

Ignore
1511279735
Reply with quote  #2

1511279735
Report to moderator
1511279735
Hero Member
*
Offline Offline

Posts: 1511279735

View Profile Personal Message (Offline)

Ignore
1511279735
Reply with quote  #2

1511279735
Report to moderator
Join ICO Now Coinlancer is Disrupting the Freelance marketplace!
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1511279735
Hero Member
*
Offline Offline

Posts: 1511279735

View Profile Personal Message (Offline)

Ignore
1511279735
Reply with quote  #2

1511279735
Report to moderator
kjj
Legendary
*
Offline Offline

Activity: 1302



View Profile
September 12, 2012, 04:36:39 AM
 #2

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.

p2pcoin: a USB/CD/PXE p2pool miner - 1N8ZXx2cuMzqBYSK72X4DAy1UdDbZQNPLf - todo
I routinely ignore posters with paid advertising in their sigs.  You should too.
Etlase2
Hero Member
*****
Offline Offline

Activity: 798


View Profile
September 12, 2012, 12:56:30 PM
 #3

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
Legendary
*
Offline Offline

Activity: 1302



View Profile
September 12, 2012, 01:34:53 PM
 #4

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"
    }
  ]

p2pcoin: a USB/CD/PXE p2pool miner - 1N8ZXx2cuMzqBYSK72X4DAy1UdDbZQNPLf - todo
I routinely ignore posters with paid advertising in their sigs.  You should too.
Remember remember the 5th of November
Legendary
*
Offline Offline

Activity: 1582

Reverse engineer from time to time


View Profile
September 12, 2012, 01:46:11 PM
 #5

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

Quote
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

BTC:1AiCRMxgf1ptVQwx6hDuKMu4f7F27QmJC2
Sergio_Demian_Lerner
Hero Member
*****
expert
Offline Offline

Activity: 539


View Profile WWW
September 12, 2012, 03:40:11 PM
 #6

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
Legendary
*
qt
Offline Offline

Activity: 1050


View Profile WWW
September 12, 2012, 03:49:17 PM
 #7

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.

aka sipa, core dev team

Tips and donations: 1KwDYMJMS4xq3ZEWYfdBRwYG2fHwhZsipa
Etlase2
Hero Member
*****
Offline Offline

Activity: 798


View Profile
September 12, 2012, 03:51:13 PM
 #8

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
Legendary
*
Offline Offline

Activity: 1203



View Profile WWW
September 12, 2012, 11:00:17 PM
 #9

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
Legendary
*
Offline Offline

Activity: 1302



View Profile
September 13, 2012, 12:14:05 AM
 #10

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.

p2pcoin: a USB/CD/PXE p2pool miner - 1N8ZXx2cuMzqBYSK72X4DAy1UdDbZQNPLf - todo
I routinely ignore posters with paid advertising in their sigs.  You should too.
Sunny King
Legendary
*
Offline Offline

Activity: 1203



View Profile WWW
September 13, 2012, 02:20:53 AM
 #11

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?  Shocked

Is it even remotely feasible to design ASIC to crake a key?
keystroke
Hero Member
*****
Offline Offline

Activity: 842


advocate of a cryptographic attack on the globe


View Profile
September 13, 2012, 03:39:41 AM
 #12

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?

"The difference between a castle and a prison is only a question of who holds the keys."
Etlase2
Hero Member
*****
Offline Offline

Activity: 798


View Profile
September 13, 2012, 04:23:28 AM
 #13

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
Newbie
*
Offline Offline

Activity: 19



View Profile
September 13, 2012, 03:05:33 PM
 #14

Question was cross-posted on crypto.stackexchange.
keystroke
Hero Member
*****
Offline Offline

Activity: 842


advocate of a cryptographic attack on the globe


View Profile
September 13, 2012, 04:54:54 PM
 #15

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 Cheesy

"The difference between a castle and a prison is only a question of who holds the keys."
keystroke
Hero Member
*****
Offline Offline

Activity: 842


advocate of a cryptographic attack on the globe


View Profile
September 13, 2012, 05:14:18 PM
 #16

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!

"The difference between a castle and a prison is only a question of who holds the keys."
Etlase2
Hero Member
*****
Offline Offline

Activity: 798


View Profile
September 13, 2012, 05:33:42 PM
 #17

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

ByteCoin
Sr. Member
****
expert
Offline Offline

Activity: 416


View Profile
September 13, 2012, 09:26:58 PM
 #18

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
Hero Member
*****
Offline Offline

Activity: 798


View Profile
September 13, 2012, 09:54:07 PM
 #19

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
Hero Member
*****
Offline Offline

Activity: 842


advocate of a cryptographic attack on the globe


View Profile
September 14, 2012, 03:12:44 AM
 #20

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

Neat, thanks Smiley 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!

"The difference between a castle and a prison is only a question of who holds the keys."
Pages: [1] 2 »  All
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!