Could a Quantum Computer derive a BIP32 seed from a public key?

[chairmember]

I've read that a QC could break ECDSA to derive a public key from a private key.

Could it also derive a BIP 32 seed from the public key?

[1715410389]

1715410389

[1715410389]

1715410389

[1715410389]

1715410389

[bones261]

Bip 32 uses HMAC-SHA512 as the algorithm.  I think that it would be much easier for a quantum computer to attempt to crack an individual private key than to attempt to crack the BIP32 seed. Quite frankly, I think we are quite far off from quantum computers becoming powerful enough to make password/private key hacking trivial due to quantum decoherence.

[chairmember]

Bip 32 uses HMAC-SHA512 as the algorithm.  I think that it would be much easier for a quantum computer to attempt to crack an individual private key than to attempt to crack the BIP32 seed. Quite frankly, I think we are quite far off from quantum computers becoming powerful enough to make password/private key hacking trivial due to quantum decoherence.

What about Ledger hardware wallet addresses that use BIP49?

For example, these 4 addresses were derived from the same seed on a Ledger:

(1) 38yp4KEzHXuQzPqXosDrqR6k7m82vtTWN4 -> sent a transaction and exposed public key
(2) 3HdkVwrSuDcVhpcHRBfpxdyEWDgFhEo3T9
(3) 3GPmyepu9DpGYKMUgF4XV2kNhnWjZEEbJb
(4) 3D6Ka9zE1Ku2nu43h5YSET8M1tewm7AUGH

Could a QC use the exposed public key from (1) to compromise addresses (2), (3), and (4) ?

Assuming a QC is invented in the future that can break ECDSA.

[bones261]

What about Ledger hardware wallet addresses that use BIP49?

For example, these 4 addresses were derived from the same seed on a Ledger:

(1) 38yp4KEzHXuQzPqXosDrqR6k7m82vtTWN4 -> sent a transaction and exposed public key
(2) 3HdkVwrSuDcVhpcHRBfpxdyEWDgFhEo3T9
(3) 3GPmyepu9DpGYKMUgF4XV2kNhnWjZEEbJb
(4) 3D6Ka9zE1Ku2nu43h5YSET8M1tewm7AUGH

Could a QC use the exposed public key from (1) to compromise addresses (2), (3), and (4) ?

Assuming a QC is invented in the future that can break ECDSA.

Do you mean BIP39? Bip49 is what allows for segwit address to be embedded in a P2SH. Either way, the HMAC-SHA512 is used as the random function, and I really do not think it will be a trivial task, even for a QC that could break ECDSA.

[chairmember]

What about Ledger hardware wallet addresses that use BIP49?

For example, these 4 addresses were derived from the same seed on a Ledger:

(1) 38yp4KEzHXuQzPqXosDrqR6k7m82vtTWN4 -> sent a transaction and exposed public key
(2) 3HdkVwrSuDcVhpcHRBfpxdyEWDgFhEo3T9
(3) 3GPmyepu9DpGYKMUgF4XV2kNhnWjZEEbJb
(4) 3D6Ka9zE1Ku2nu43h5YSET8M1tewm7AUGH

Could a QC use the exposed public key from (1) to compromise addresses (2), (3), and (4) ?

Assuming a QC is invented in the future that can break ECDSA.

Do you mean BIP39? Bip49 is what allows for segwit address to be embedded in a P2SH. Either way, the HMAC-SHA512 is used as the random function, and I really do not think it will be a trivial task, even for a QC that could break ECDSA.

Yes, I meant BIP39

[bones261]

Actually, since there are only 1024 possible words in BIP39/BIP32, it would be a much easier operation for the QC to just brute force the seed phrase than to try to work backwards from an exposed public key. However, if you use a passphrase on top of the mnemonic, this will probably confound the effort.

[HCP]

Theoretically, if you have the master public (aka xpub) and one private key from that chain, you can derive all private keys from THAT chain...

So, in this theoretical discussion, if a QC was developed that enabled you to take a public key and crack the private key... and you also had the relevant xpub... you could derive all the private keys. Asssuming that your addresses (2), (3) and (4) were from the same "account"... as Ledger uses BIP44 which uses hardened key derivation down to the "account" level (m/44'/0'/0'...)

Actually, since there are only 1024 possible words in BIP39/BIP32

It's 2048 words... not that that really matters for the OPs question.

[bones261]

Well, that sucks. So I guess the only way to secure my xpub key for my Trezor is to only view my balance on an air-gapped computer, correct? Hopefully, they don't come up with an affordable way run and maintain a  quantum computer capable of breaking traditional algos anytime soon.

[bob123]

Well, that sucks. So I guess the only way to secure my xpub key for my Trezor is to only view my balance on an air-gapped computer, correct?

Not necessarily, but if you want to be absolutely sure that noone gets your xpub, then yes.
However, only the xpub is not enough to steal funds, it does 'only' destroy your privacy.

Hopefully, they don't come up with an affordable way run and maintain a  quantum computer capable of breaking traditional algos anytime soon.

Quantum computers aren't some kind of 'magic machines'.

They are comparable to normal computers, just that they don't work with bits (0 and 1) but with qubits (which basically just is a computer with more than 2 states).
They can not magically crack cryptography.

First there needs to be a prototype which can be run in a stable state. Then it needs to be further developed, because high end server are way more powerfull than a small quantum computer prototype (which doesn't exist yet).

Further someone would need to invent an innovative algorithm (for a quantum computer) which is capable of solving mathematical problems noone had ever an approach yet.


You really don't need to hope that they don't come up with an affordable way to run such a machine.
And not to mention the need of a proper algorithm to crack keys.

[aplistir]

I've read that a QC could break ECDSA to derive a public key from a private key.

Could it also derive a BIP 32 seed from the public key?

LOL, You do not need a QC to be able to get a public key FROM a private key. I can do it on my computer and it takes less than a second

But seriously speaking.
It is impossible to get the BIB39 seed from a single public key QC or not. Seed generates many keys and public key is just one of them. You could get the private key to that public key, but there is no route to the seed. Single public key just does not hold enough information in it.
Maybe it could be possible if you had the master public key and a big quantum computer.

But remember it is also a question of which addresses will be attacked first, if there ever will be a big enough QC.

There are many addresses with more than 100000BTC in them, whose public keys are published. So if you have much less in your wallet, that would not make you a very interesting target.

[chairmember]

https://np.reddit.com/r/ledgerwallet/comments/7fjc3v/security_of_ledger_wallets_hierarchical/

For long-term QC-resistant storage on a BIP 32 or BIP 39 seed, it sounds like it's best to store in an unused address and don't expose the seed's master public key.

If I understand correctly, it's impossible for a QC to reverse engineer a seed like this:

exposed public key -> master public key -> seed

Thanks for the help

[HCP]

But remember it is also a question of which addresses will be attacked first, if there ever will be a big enough QC.

There are many addresses with more than 100000BTC in them, whose public keys are published. So if you have much less in your wallet, that would not make you a very interesting target.

The number of BTC is pretty much irrelevant... if some a computer/method were ever created and/or found to be viable... Crypto would essentially become worthless overnight.

If I understand correctly, it's impossible for a QC to reverse engineer a seed like this:

exposed public key -> master public key -> seed

It is technically possible to go from "exposed master pub key + one priv key" -> ALL priv keys (relating to that xpub)... and you don't even need a QC... but as I understand it, you'll never be able to work back to the seed.