2
$\begingroup$

NOTE: This question cannot be posted to Bitcoin SE because it will not render there due to the mathematical notation. Since the mathematical notation is part of the question, this is the more appropriate forum to post on, with tag 'cryptocurrency'.

I wonder how secure it is to split up a printed Bitcoin private key into parts and keep the parts in separate secure physical locations, such as safe deposit boxes, like the Winklevoss twins.

I am considering a standard Base58Check encoded compressed WIF-format Bitcoin private key of length 52, starting with a K or L.

Imagine it was cut up into 4 pieces and 3 were found. To guess the last 13 base58 characters by brute force would require $58^{13}$ operations, taking time :

$$t = t_0 \left(\frac{\Delta t}{C}\right) \hspace{1em} \mbox{(years)} $$

where $t_0 \simeq 2.7$ million, $\Delta t =$ time per operation (per single core) in nanoseconds, and $C =$ number of cores running in parallel, where each operation requires :

  1. form the full 52 char key
  2. base58 decode it to 38 byte binary string
  3. check the checksum in the last 4 bytes equals first 4 bytes of the double SHA256 hash of the first 34 bytes
  4. if yes for step 3) verify private key maps to desired bitcoin address

To guess k more characters than that would take :

$$t = t_0 \left(\frac{\Delta t}{C}\right) \cdot 58^k \hspace{1em} \mbox{(years)} $$

Thus for splitting into 2 pieces ($k = 13$), guessing one half of the key would take :

$$t = 2.2 \times 10^{29} \times \left( \frac{\Delta t}{C} \right) \hspace{1em} \mbox{years} $$

However how low a $\Delta t$ could be achieved in practice ? And what kind of a value could $C$ realistically have, the number of cores that could be marshalled?

In particular I wondered whether splitting into 2 pieces is absolutely secure. And how long into the future it would be before that was no longer the case.

$\endgroup$
5
  • 4
    $\begingroup$ I would strongly suspect that if you're missing $n$ key bits and know the full public key, you can brute-force the remaining ones in time $2^{n/2}$ using algorithms like baby-step-giant-step. This paper should discuss attacks if any continuous (?) sub-range of private key bits are unknown (slides here, pdf). $\endgroup$
    – SEJPM
    Mar 21, 2021 at 19:18
  • 2
    $\begingroup$ You're looking for a secret-sharing scheme. Don't split up a private key (in asymmetric cryptography) or you'll risk giving away sufficient information to reconstruct it in its entirety. Although I don't know how Bitcoin in particular works, with many private keys, knowing only half is sufficient to reconstruct the rest. $\endgroup$
    – forest
    Mar 22, 2021 at 1:00
  • $\begingroup$ Bitcoin uses the secp256k1 elliptic curve, as described here and here. A Bitcoin private key is 32 bytes, and a Bitcoin public key comprises 64 bytes - representing a point (x, y) on the elliptic curve over Fp, with x, y each 32 bytes. The only information revealed about the public key K in Bitcoin is a 20-byte RIPEMD160(SHA256(K)) hash of K (Mastering Bitcoin 2nd Ed, Antonopolous, p65). I am thus wondering if it is ..... $\endgroup$ Mar 22, 2021 at 16:06
  • $\begingroup$ ...... the case at the present state of knowledge that only a brute force attack would be available on a continuous partial private key? In a typical scenario it would take about 170,000 years to brute force a right half of a standard WIF format private key assuming 1 million CPU cores running in parallel, and each performing 1 million brute force attempts per nanosecond. How long into the future could it be before that scenario becomes feasible? $\endgroup$ Mar 22, 2021 at 16:06
  • $\begingroup$ Related question, differing mostly by assuming that the public key (rather than the hash of the public key, known as address) is available, and that 50% rather than 75% of the WIF-formated private key is disclosed. $\endgroup$
    – fgrieu
    Feb 14 at 17:32

1 Answer 1

0
$\begingroup$

This answer, and the question, assume that the public key is not available to the attacker. This is unusual in cryptography, but a possibility in Bitcoin, where the hash of the public key (known as address) is enough for a so-called Pay-to-Public-Key-Hash.

To guess the last 13 base58 characters by brute force would require $58^{13}$ operations

Yes, but there's educated brute force.

The "standard Base58Check encoded compressed WIF-format Bitcoin private key" is a 52-characters string encoding per Base58 of the nearly random 32-byte ECDSA private key $d$ for curve secp256k1, plus two fixed bytes and a checksum (the first 4 bytes of the SHA256d(*) hash of the first 34 bytes), arranged as:

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

In this context Base58 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 $52-k$ characters of the WIF-encoded private key disclose an integer $d_\min$ such that $d_\min\le d<d_\max$ with $d_\max-d_\min\lesssim\Delta_k=\left\lceil58^k/2^{40}\right\rceil+1$.

If we lack the right $k=13$ characters, we have narrowed $d$ to an interval of width $\Delta_k\approx2^{36.2}$ candidates. We can test one candidate by deriving the public key, hashing it and comparing to the 20-byte known hash (the decoded address). The expected cost is dominated by $2^{35.2}$ point additions (when we move to the public key of the next candidate by adding $G$), SHA-256 and RIPEMD-160. This is feasible with a single PC. I throw in $\Delta t<1\,\text{ms}$ without justification.

Things are more difficult for other segments. For $k$ unknown characters in the center, it's possible to leverage the known 01h to reduce to $58^k/2^8$ candidates, a saving by a factor of 256 compared to what the question considers. And (as pointed in the question) it's possible to leverage the checksum to screen out all but one candidate in about $2^{32}$ with only two SHA-256 per candidate, which is an appreciable saving.

There's a large further saving possible if the missing characters are on the left. That's evidently at least by a factor of 26 since the left character is K or L, but it gets much better, perhaps 392.


How Secure Is Splitting A Bitcoin Private Key?

Not much, as shown in this answer. And it gets MUCH worse if the public key is known, as shown in this other answer.


(*) SHA256d is two SHA-256 chained.

$\endgroup$

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.