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.