0
$\begingroup$

There are a lot of questions in these forums regarding the recovery of private keys.

But I'm here to postulate on something unique to a specific piece of research that I looked into recently.

The paper is located here: https://eprint.iacr.org/2019/023.pdf

We all know that repeated nonce values render an ECDSA key insecure. But this particular piece of research indicates this is "not the only type of bias that can render an ECDSA key insecure". They state that there are many different types of "non-uniformities in the ECDSA signature nonces that can reveal the private key, given sufficiently many signatures."

This paper implies that these keys can be found without nonce re-use; so a public key could follow the correct secp256k1 construction yet still provide have its private key recovered (which is what the researchers did in this study).

Few Questions / Theories That I Have

The researchers were careful not to give the exact specifics of how they were unable to uncover the private keys due to ethical concerns.

But they did leave a few clues.

In specific, they stated:

Additional Information: Hidden number problem algorithm was used to "discover the long-term ECDSA signature key" when used with nonces that are "shorter than expected". The values they gave here were 64 bits, 110 bits, 128 bits, and 160 bits. Based on that information, I'm guessing that they're referring to the means by which a Bitcoin hierarchical deterministic key is manifested since they draw from a source of entropy that frequently is 128-bits on the spot

Specification can be found here for reference = https://github.com/bitcoin/bips/blob/master/bip-0039.mediawiki

Curious About Key Derivation

The specification is never super clear on exactly how this is done but, the workflow is:

  • Entropy bits are gathered (128 / 160 / 192 / 224 / 256) ; usually 128 bits are chosen

  • These entropy bits are first converted into a binary (0's and 1's). Then the final 4 bits of the binary. This binary is then hashed using SHA256 and the first 4-bits are appended to the value that we derived from the entropy (128 bits ; now 132 bits).

  • They map these bits all to various English dictionary words to derive a mnemonic phrase from them. There are 2048 possible words in the "official" dictionary. In total, there will be 12 words.

  • The mapping process is done by taking the 132 bit string we created above and dividing it by 11. This creates an array of 12 strings of equal length. Each one of those is what gets mapped to the dictionary words, resulting in 12 words for the user.

Here's the Part Where I Get Confused and Curious

Once those 12 words have been plucked, they are then piped into a PBKDF2 KDF.

What makes me curious here is that the actual UTF-8 encoding of the words are what get piped into the PBKDF2.

I mentioned earlier that the entropy bits are mapped to these words, but the lengths, in specific, are not mapped.

So I generated a 12-word mnemonic phrase for the hell of it to see what my result would be and it generated: "call sausage lyrics vintage click salt guard absent entry anger chaos vapor"

These words amount to 75 characters

I tried another randomly generated string (after generating 128-bits of entropy, then appending the 4-bits), and that gave me: wrong legal wing fiction primary install razor wool wrong just snake wish

character-count = 73 Bit-total = 584

Appears That the Word Count Total Amounts 32-Bits

Doing the math here, if we remove the spaces from the first string we end up with a length of 64, but the second string only gives us 62 characters (which is interesting).

The specification (or implementations), indicate that every 3 words is supposed to represent 32-bits of entropy; hence, 12-words should be 128-bits of entropy.

But if there is not uniformity in the total number of characters produced (with or without spaces), I'm not seeing how this could possibly be the case. This is especially interesting when considering the fact that the characters are supposed to be ASCII / UTF-8 NKFD.

Wouldn't this imply that the binary (plus the checksum) is not being encoded properly by the library perhaps? Either way - I'll move forward from here.

PBKDF - HMAC512 Construction

Where I begin to get fascinated is with the HMAC construction.

There is no password given "" (blank string used instead). And the salt is "mnemonic" (like the word mnemonic literally). And the 'key' is the mnemonic phrase itself.

I'm not sure what this is iterating over (i.e., the input that is supposed to be piped into this function), since this is used to generate the private key itself (master private key).

Curious Concerns Centered Around the HMAC Construction

I've read that if the key-length (password) is longer than the block size, then the HMAC will actually create pseudo-collisions based on the fact that the prefix will essentially become unchanged [if there is a fixed that is smaller than the password (key); which is made longer than the input] (where two different inputs can hash to the same result) = PBKDF2-HMAC-SHA512

This was demonstrated here within this article = https://mathiasbynens.be/notes/pbkdf2-hmac (author also provides the requisite nodejs & Python scripts that correspond with such a collision).

I mention this because the flaw in implementation could be the fact that the words are separated by spaces from the mnemonic - this would push the input >64 bytes; there are also instances in which I received mnemonics that were above bytes (64) even after removing the spaces.

Please Review the Research

It truly is the key to assisting with what the researchers found.

I'm certain that there are at least a few cryptographers on here that are able to help me decipher exactly what these researchers were able to uncover.

Thank you!

$\endgroup$
7
  • 1
    $\begingroup$ The attack against ECDSA with biased nonces is quite old (Bleichenbacher 2000), the currently best method you can find in ia.cr/2020/1540. The point of using a key derivation function is simply to convert (enough) entropy you have in form of a non-uniform distribution (ASCII strings of various lengths) into a uniform distribution with about the same entropy ("uniform" prevents the attack). Finding such a collision you mention costs a lot of effort and is unlikely to happen by chance, and therefore doesn't matter in this case. $\endgroup$
    – j.p.
    Mar 6 at 8:23
  • $\begingroup$ Hey @j.p. ; sorry but your comment completely fails to answer this question. I urge you to either re-read or retract. Thank you! $\endgroup$
    – librehash
    Mar 18 at 21:31
  • $\begingroup$ Do you understand Bleichenbacher's attack like described in ia.cr/2020/615 or the lattice based variant like described in ia.cr/2013/346? (The flaw you mentioned is really irrelevant for the Breitner/Heninger paper.) $\endgroup$
    – j.p.
    Mar 18 at 21:55
  • $\begingroup$ @j.p I'm reading what you're saying, but your response is not addressing what I'm writing. I'm not mystified at the fact that such an attack can be possible. I'm trying to figure what it is in Bitcoin's approach to generating these addresses that have made them as uniquely vulnerable as the research suggests* $\endgroup$
    – librehash
    Mar 24 at 16:07
  • $\begingroup$ So do I understand you correctly in assuming that you just want to know which programming/conceptional errors made the attacks possible? (You seem to assume that the vulnerable signatures were generated the way you describe. I do not think so, as they would not be vulnerable unless there is a major SW-bug overwriting the random by fixed data. The attacks described in section 5.2 of ia.cr/2019/023 work without additional knowledge (like what's the prefix/suffix) on the signatures.) $\endgroup$
    – j.p.
    Mar 25 at 7:11

Your Answer

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

Browse other questions tagged or ask your own question.