4

In this post by an Ethereum engineer taken from the Ethereum wiki about brute-forcing private keys, he writes:

"Public keys are sized so that, absent a breakthrough in solving the discrete logarithm problem, brute force is impractical for any conceivable amount of computing power. With 2^128 possible combinations, and if we assume a modern computer can compute, say, a billion per second (which is a massive overestimate), it would take a million such computers ~5e15 years to brute force your key. If we assume computing power improves by another million fold, it'd take this massive cluster 'only' about 5 billion years."

However, according to this question, a private key is 256 bits long. In this case, why is the quote referring to 2^128 instead of 2^256?

mcansado
  • 841
  • 8
  • 25
  • 2^128 is the size of the brute-force search for collisions on 256 bits due to the birthday paradox. So maybe there is a link. But then you only have to find a collision between 160-bits addresses, so 2^80 operations, which is a lot less... – Distic Sep 06 '17 at 16:27
  • My math might be off, but when I changed the number to 2^80 keeping the rest of the parameters the same, it would only take 38 years. – liquidki Jan 29 '18 at 15:08

1 Answers1

2

Disclaimer: Not my domain of expertise.

Ethereum uses elliptic curve cryptography (ECC) for security. One can perform naïve brute force testing of a 256 bit key by testing all 2^256 combinations. However, similar to how it's unnecessary to test every number between 2 and n - 1 to test if n is prime (worst-case high-school method is O(n^0.5), but even better algorithms exist), ECC can be broken by solving the relevant elliptic curve discrete log problem more efficiently.

The best known algorithms for solving the elliptic curve discrete log problem operate in worst case O(n^0.5); (2^256)^0.5 yields 2^128 steps for brute forcing a 256-bit key. Hence, at most 2^128 trials are required to break a 256-bit key used for Ethereum. Note that this is unrelated to the birthday paradox, which pertains to collisions; the fact that both happen to be square root of n is pure coincidence.

lungj
  • 6,680
  • 2
  • 17
  • 45