1
$\begingroup$

Bitcoin's mini private key format works by brute forcing random data to produce a secret so that when appending ? and then hashing with sha256 it will produce a hash that starts with 0x00. This way the user knows the secret is well formed and can proceed to hash it without appending ? to produce their private key.

This technique could be extended to include useful data in the hash "header", up to 2 bytes could be brute forced in a second or two.

However it seems that this scheme is reducing entropy of the secret i.e. if the attacker knows that a key is not valid by using a cheap sha256 hash, she will skip the expensive private to public key calculations. When the hash header is 1 byte around 99.6% of the random candidate keys were rejected, for 2 bytes it was 99.9983282%.

So does this scheme reduces the entropy of initial secret? If so how much?

$\endgroup$
0
3
$\begingroup$

From the linked page, a minikey is a 30-character string over the base58 alphabet with the first byte fixed to 'S', so effectively 29 characters. This gives a space of $log_2(58^{29}) \approx 169.88$ bits. Assuming that SHA is a random function, the probability of the hash starting with an 0-byte after appending a ? is 1/256, so this check loses 8 bits of entropy giving just over 161 bits of security.

$\endgroup$
2
  • $\begingroup$ Good analysis. Do you know any other scheme that uses a similar technique? $\endgroup$ Aug 20 '15 at 13:27
  • $\begingroup$ No obvious examples come to mind - perhaps the entropy of credit card numbers, bearing in mind the checksum? There's point compression on Elliptic Curves, it doesn't lose entropy since it's only getting rid of redundancy but it does demonstrate that you can send only "part of the point" and have someone else recompute the rest. $\endgroup$
    – user2552
    Aug 20 '15 at 15:14
1
$\begingroup$

There's really two things to consider here:

  • Entropy. Assuming that the hash function in question maps exactly the same number $2^{n-k}$ of bit strings of length $n$ to each hash output of length $k\leq n$, then fixing $l\leq k$ bits of the hash reduces the set of possible choices for the input from $\{0,1\}^n$ to some subset $S\subseteq\{0,1\}^n$ of cardinality $2^{n-l}$. Clearly, restricting the choice of the secret to that subset preserves uniform randomness, hence the entropy is $n-l$ bits instead of the full $n$ bits of an arbitrary uniformly random bit string of length $n$.
  • Computation. As you said, hashes are typically easier to compute than keypairs. However, if you can brute-force $l$ bits of the hash to obtain a key of such a format, then "they" can shoulder that additional computation as well! In other words: If making the computation easier by a factor that you can manage to perform weakens your confidence in the system by a significant amount, then the security level was flawed in the first place.
$\endgroup$
2
  • $\begingroup$ Isn't the computation avoided just a loss of entropy? $\endgroup$ Aug 20 '15 at 13:17
  • 1
    $\begingroup$ @JohnL.Jegutanis No. The point is: The entropy of the secret is lowered, but there is no way to efficiently compute the set of possible secrets, other than brute force (assuming the hash function is secure). Therefore, a brute-forcer still has to enumerate (potentially) all the $n$-bit strings, even though the entropy is lower than $n$ bits! In that sense, the only difference to the case without any restrictions on the hash is that the hash allows you to rule out many possibilities easier than by computing and comparing the corresponding public key. $\endgroup$
    – yyyyyyy
    Aug 20 '15 at 13:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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