4
$\begingroup$

Given the following two preconditions:

  1. It is almost impossible to reconstruct a bitcoin private key if an attacker only has one half of the private key as well as the public key.
  2. It is almost impossible to reconstruct a bitcoin private key if an attacker has an SHA512 hash of the private key as well as the public key.

I searched on the internet and I am almost sure that these two preconditions are valid as it would be very cost intensive if not impossible to realize these calculations.

By private key I mean the string representation as a 52-digit hexadecimal number. One half of the private key would be the first 1 to 26 characters of this string. You can find the sourcecode that generates this key here:

https://github.com/pointbiz/bitaddress.org/tree/master/src

Or you can generate these addresses here:

https://www.bitaddress.org

Now to my question: If we assume an attacker has all of the following four pieces of data:

  1. One half of the private key.
  2. The public key.
  3. An SHA512 hash of the private key.
  4. An SHA512 hash of the public key.

How could an attacker could combine these information parts to successfully recover the private key? Could an attacker improve a brute-force-attack or any other attack to recover the private key given the information above? Can you please give me background information that support your answer? How long would it take to recover the keys and on what type of hardware? Would it be economically feasible?

$\endgroup$
3
  • 1
    $\begingroup$ [edited by moderator to match the revised Q] I am not sure if your assumption is true that it would be possible to find the whole private key. Can you please compare with the comments of Crypto L Plate in this question. Are you sure? If so, why? $\endgroup$
    – Ohumeronen
    Feb 14 at 15:17
  • $\begingroup$ The question now is answerable and on-topic, because "One half of the public key" that was present up to rev3 is removed, and it's now clear that the public key is known. That's such a standard hypothesis that I removed it from the title. Please leave it in the body of the question. But precondition 1 is now false, and that answer starts to explains why. $\endgroup$
    – fgrieu
    Feb 14 at 16:25
  • $\begingroup$ The present question is hopefully not making a confusion between "public key" and "address". The later is often expressed as a 34-character Base58 string starting with the digit 1. It encodes a 20-byte hash of the public key. One (of several) payment conventions is to an address, allowing the public key to remain secret until the private key is put to use to spent what's been received, in whole or part. Then the public key necessarily gets public: it's used to verify a message/signature pair (and can be recovered from two such pairs matching the key, using ECDSA public key recovery). $\endgroup$
    – fgrieu
    Feb 15 at 11:48

1 Answer 1

6
$\begingroup$

We must first wonder if the preconditions hold, in particular 1; that is:

In Bitcoin, given half the 52-character private key in WIF format, is it possible to reconstruct the whole private key?

The WIF format conveys the nearly random 32-byte ECDSA private key $d$ for curve secp256k1, fixed data and a checksum (the first 4 bytes of the SHA256d(*) hash of the first 34 bytes), formatted as:

    80h   [32-byte private key]   01h   [4-byte checksum]

That 38-byte bytestring is encoded as 52 characters per Base58 which in this context reduces to the usual positional numeral system with base 58 instead of 10 for decimal, and "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz" instead of "0123456789". Everything is big-endian.

The first 26 characters of the WIF-encoded private key therefore discloses an integer $d_\min$ such that $d_\min\le d<d_\max$ with $d_\max-d_\min=\Delta\lesssim\left\lceil58^{26}/2^{40}\right\rceil+1\approx2^{112.31}$. In particular, we know the value of the first 143 bits out of 256 of the key (or sometime two possible values for this bitstring). That's >56% for the private key's entropy.

These $\Delta\approx2^{112.31}$ possible $d$ are too many to try by brute force, to find which matches the known public key $Q$ per $Q=[d]\,G$ (where $G$ is the conventional generator of secp256k1). That's even though testing one more $d$ and comparing requires significantly less work than a point addition (because we can do without a modular inversion).

But there are much better methods! Baby-Step/Giant-Step is a theoretical algorithm that does the job in an average $1.5\sqrt\Delta$ point additions. Pollard's rho is a practical variations that require feasibly little memory, and has variants efficiently distributed on multiple CPUs (or GPUs, FPGAs, ASICs), using not much more work. We are talking $2^{58}$ point additions. It's still not easy, but clearly feasible. For reference, the current Bitcoin hash rate is about $2^{69}$ SHA256d(*) per second.

The original author of the answer does not have the motivation to detail the algorithm or the monetary cost to carry one attack, and makes the question a community wiki.


In that related question, it's assumed 75% rather than 50% of the WIF-format key is known, which dramatically reduces the cost of an attack if the public key is available. That's as stated in the most upvoted comment, which includes links to papers discussing adaptation to any missing segment of the private key. However that question's OP considers that attackers know the address (that is a hash of the public key) rather than the public key, contrary to the present question.


Assumption 2 is correct: If we knew the SHA-512 hash of the private key rather than half of the WIF-encoded private key, the task of finding the private key would be computationally hopeless. That's because SHA-512 is preimage-resistant, and is so unrelated to secp256k1 that it's knowledge can't be combined with knowledge of the public key. The hash does not disclose entropy in the structured way of partial disclosure.


Among the 4 pieces of data listed in the end of question, the hashes (3 and 4) are of little help: 4 can be readily recomputed from the public key 2, thus it's only practical use is ensuring that no error crept in the public key. And while 3 could similarly be used to check a conjectured private key, so can the public key, at cost only marginally higher.


(*) SHA256d is two SHA-256 chained.

$\endgroup$
1
  • $\begingroup$ Thank you for your time and effort, giving me such an elaborate response and for improving the post. $\endgroup$
    – Ohumeronen
    Feb 14 at 22:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.