Do invalid keys in BIP44 path matter?

j2002ba2

full member

Activity: 206

Merit: 447

Quote from: Coding Enthusiast on July 21, 2020, 12:15:01 AM

Quote from: j2002ba2 on July 20, 2020, 03:37:06 PM

A 256-bit number bigger than n modulo n is at most only 128 bits.

It actually is at most 136 bits (0x014551231950b75fc4402da1732fc9bebe).

This number is 129 bits.

I got the rest wrong though.

The change appeared in the 23 March 2013 revision https://en.bitcoin.it/w/index.php?title=BIP_0032&type=revision&diff=36331&oldid=36142

o_e_l_e_o

legendary

Activity: 2268

Merit: 18711

Quote from: j2002ba2 on July 20, 2020, 03:37:06 PM

If one knows the xpub, then k-par is known, and it is possible to recover the private key.

I don't follow you here. How does one know k_par if they know the xpub? The xpub reveals the public key K_par, not the private key k_par. Further, to calculate the child private key, you still have to add the result of the hash function to the parent private key. Even if you know the result of the hash, you cannot calculate the child private key.

Coding Enthusiast

legendary

Activity: 1040

Merit: 2785

Bitcoin and C♯ Enthusiast

Quote from: j2002ba2 on July 20, 2020, 03:37:06 PM

A 256-bit number bigger than n modulo n is at most only 128 bits.

It actually is at most 136 bits (0x014551231950b75fc4402da1732fc9bebe).

Quote

If one knows the xpub, then k-par is known, and it is possible to recover the private key.

You can't know the parent private key from xpub, you only know the parent public key (capital K) and even then to compute a child private key you still need another private key, even if the next key was only 1G ahead.

P.S. I honestly can't think of any reason why this decision was made.

j2002ba2

full member

Activity: 206

Merit: 447

Quote from: o_e_l_e_o on July 20, 2020, 10:48:38 AM

Follow up question: Why was the decision made that if the left 256 bits are greater than n, to declare the key invalid instead of just using modulo n and proceeding as normal?

When calculating the child key, you add the left 256 bits to the parent key, and use modulo n to ensure a valid key is obtained. Why not just use modulo n at the previous step to ensure the left 256 bits are also valid?

A 256-bit number bigger than n modulo n is at most only 128 bits. If one knows the xpub, then k-par is known, and it is possible to recover the private key. The Summit supercomputer can find it in a week.

ashfame

newbie

Activity: 21

Merit: 15

Not sure why. Perhaps someone else will be able to answer.

o_e_l_e_o

legendary

Activity: 2268

Merit: 18711

Follow up question: Why was the decision made that if the left 256 bits are greater than n, to declare the key invalid instead of just using modulo n and proceeding as normal?

When calculating the child key, you add the left 256 bits to the parent key, and use modulo n to ensure a valid key is obtained. Why not just use modulo n at the previous step to ensure the left 256 bits are also valid?

ashfame

newbie

Activity: 21

Merit: 15

Quote from: Coding Enthusiast on July 14, 2020, 10:07:45 AM

Quote from: ashfame on July 14, 2020, 08:50:48 AM

Follow up ques: If parent key at m/44'/0'/0'/0 is found to be valid, shouldn't I be checking the corresponding parent key of internal chain at m/44'/0'/0'/1 before assuming its safe to use? Otherwise we would have no valid change addresses to send money to.

Each key is checked only when it is generated and wallets usually generate a bunch of them at a time, there is no need to check the ones that may be generated in the future. Keep in mind that chances of finding an invalid key is extremely small since sekp256k1 order is very close to 2²⁵⁶.

If a child key was invalid you simply skip it and get the next one, meaning m/44'/0'/0'/0/0, m/44'/0'/0'/0/1, m/44'/0'/0'/0/2, m/44'/0'/0'/0/4, m/44'/0'/0'/0/5 assuming index=3 gave an invalid key.
But if the parent key (eg the key at depth 1) was invalid you should stop, that would be a very unlikely error and the seed must be changed, meaning stop if m/44'/ was invalid. At least that is what I do in my Bitcoin.Net code.

Yeah, I get that point, but I was asking about internal chains, which I was able to figure out. Thanks for explaining!

Coding Enthusiast

legendary

Activity: 1040

Merit: 2785

Bitcoin and C♯ Enthusiast

Quote from: ashfame on July 14, 2020, 08:50:48 AM

Follow up ques: If parent key at m/44'/0'/0'/0 is found to be valid, shouldn't I be checking the corresponding parent key of internal chain at m/44'/0'/0'/1 before assuming its safe to use? Otherwise we would have no valid change addresses to send money to.

Each key is checked only when it is generated and wallets usually generate a bunch of them at a time, there is no need to check the ones that may be generated in the future. Keep in mind that chances of finding an invalid key is extremely small since sekp256k1 order is very close to 2²⁵⁶.

If a child key was invalid you simply skip it and get the next one, meaning m/44'/0'/0'/0/0, m/44'/0'/0'/0/1, m/44'/0'/0'/0/2, m/44'/0'/0'/0/4, m/44'/0'/0'/0/5 assuming index=3 gave an invalid key.
But if the parent key (eg the key at depth 1) was invalid you should stop, that would be a very unlikely error and the seed must be changed, meaning stop if m/44'/ was invalid. At least that is what I do in my Bitcoin.Net code.

ashfame

newbie

Activity: 21

Merit: 15

Quote from: Coding Enthusiast on July 13, 2020, 09:57:59 PM

It could potentially cause problems if we ignore validity (being in range) of the parent derived keys because even though BIP-32 may look like any other Key Derivation Function but it is more than a simple KDF. For instance each non-hardened child key is derived using the parent's public key which means that parent key must have been in range to be used in EC multiplication.

BIP-44 is not relevant here but since you mentioned it, lets take the path used in this BIP:
m / 44' / 0' / 0' / 0 / 0
The bold one is the child keys used in creating addresses.
You won't notice the problem in first 3 depths since they are all hardened but the last one is not. If the parent key at m/44'/0'/0'/0 returned a key that is outside of curve range you can't derive the child key at m / 44'/0'/0'/0/0 anymore.
So the standard has to enforce this validity check on each step.

oh, that's great to know, exactly what I wanted to learn

Follow up ques: If parent key at m/44'/0'/0'/0 is found to be valid, shouldn't I be checking the corresponding parent key of internal chain at m/44'/0'/0'/1 before assuming its safe to use? Otherwise we would have no valid change addresses to send money to.

Coding Enthusiast

legendary

Activity: 1040

Merit: 2785

Bitcoin and C♯ Enthusiast

It could potentially cause problems if we ignore validity (being in range) of the parent derived keys because even though BIP-32 may look like any other Key Derivation Function but it is more than a simple KDF. For instance each non-hardened child key is derived using the parent's public key which means that parent key must have been in range to be used in EC multiplication.

BIP-44 is not relevant here but since you mentioned it, lets take the path used in this BIP:
m / 44' / 0' / 0' / 0 / 0
The bold one is the child keys used in creating addresses.
You won't notice the problem in first 3 depths since they are all hardened but the last one is not. If the parent key at m/44'/0'/0'/0 returned a key that is outside of curve range you can't derive the child key at m / 44'/0'/0'/0/0 anymore.
So the standard has to enforce this validity check on each step.

ashfame

newbie

Activity: 21

Merit: 15

Quote from: odolvlobo on July 13, 2020, 04:32:32 PM

Quote from: ashfame on July 13, 2020, 01:00:36 PM

I understand not all ~~private keys~~ 256-bit numbers are usable as private keys as they fall outside of Secp256k1 ...

FTFY

According to BIP-32, which is really what you are asking about:

Quote from: https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki

In case parse256(I_L) ≥ n or k_i = 0, the resulting key is invalid, and one should proceed with the next value for i. (Note: this has probability lower than 1 in 2¹²⁷ .)

Thanks! Your correction is definitely precise.

About the line you quoted from BIP32, I am familiar with that, but how does it matter unless the child in question is of depth=3 in BIP32? What happens when such a case occurs in depth<3? Are we supposed to ignore it by standard or there is actual merit to it that child generated under that branch would be all invalid keys only? I think its the former, but not sure.

Skipping the account itself (depth=1) or wallet chains (depth=2) when that particular child falls outside of the acceptable private number range, sounds silly. So that's essentially where I am looking to get more clarity.

odolvlobo

legendary

Activity: 4466

Merit: 3391

Quote from: ashfame on July 13, 2020, 01:00:36 PM

I understand not all ~~private keys~~ 256-bit numbers are usable as private keys as they fall outside of Secp256k1 ...

FTFY

According to BIP-32, which is really what you are asking about:

Quote from: https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki

In case parse256(I_L) ≥ n or k_i = 0, the resulting key is invalid, and one should proceed with the next value for i. (Note: this has probability lower than 1 in 2¹²⁷ .)

ashfame

newbie

Activity: 21

Merit: 15

Reposting the question from BitcoinSE, since didn't get a response there:

I understand not all private keys are usable as they fall outside of Secp256k1, but do they really matter when the master node or path being derived in BIP44 generates a private key which isn't usable as those nodes (keys at that node) are not supposed to hold funds?

Or is it just the actual address (external/internal chain of addresses under an account) that matters as those are the ones supposed to hold funds?

Or hitting a private key outside of Secp256k1 somehow translate into child keys being outside of Secp256k1 as well?

Topic: Do invalid keys in BIP44 path matter? (Read 245 times)