Bitcoin Forum
July 24, 2024, 02:16:49 AM *
News: Latest Bitcoin Core release: 27.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: [1]
  Print  
Author Topic: Could a Quantum Computer derive a BIP32 seed from a public key?  (Read 316 times)
chairmember (OP)
Newbie
*
Offline Offline

Activity: 5
Merit: 4


View Profile
November 04, 2018, 11:39:39 PM
Merited by suchmoon (2)
 #1

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?
bones261
Legendary
*
Offline Offline

Activity: 1806
Merit: 1827



View Profile
November 04, 2018, 11:52:29 PM
Last edit: November 05, 2018, 12:14:41 AM by bones261
 #2

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 (OP)
Newbie
*
Offline Offline

Activity: 5
Merit: 4


View Profile
November 05, 2018, 12:34:22 AM
Merited by DarkStar_ (2)
 #3

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
Legendary
*
Offline Offline

Activity: 1806
Merit: 1827



View Profile
November 05, 2018, 01:00:59 AM
 #4

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 (OP)
Newbie
*
Offline Offline

Activity: 5
Merit: 4


View Profile
November 05, 2018, 01:05:52 AM
 #5

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
Legendary
*
Offline Offline

Activity: 1806
Merit: 1827



View Profile
November 05, 2018, 01:23:00 AM
 #6

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
Legendary
*
Offline Offline

Activity: 2086
Merit: 4316

<insert witty quote here>


View Profile
November 05, 2018, 03:14:25 AM
Merited by DarkStar_ (2), bones261 (2)
 #7

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.

█████████████████████████
████▐██▄█████████████████
████▐██████▄▄▄███████████
████▐████▄█████▄▄████████
████▐█████▀▀▀▀▀███▄██████
████▐███▀████████████████
████▐█████████▄█████▌████
████▐██▌█████▀██████▌████
████▐██████████▀████▌████
█████▀███▄█████▄███▀█████
███████▀█████████▀███████
██████████▀███▀██████████
█████████████████████████
.
BC.GAME
▄▄░░░▄▀▀▄████████
▄▄▄
██████████████
█████░░▄▄▄▄████████
▄▄▄▄▄▄▄▄▄██▄██████▄▄▄▄████
▄███▄█▄▄██████████▄████▄████
███████████████████████████▀███
▀████▄██▄██▄░░░░▄████████████
▀▀▀█████▄▄▄███████████▀██
███████████████████▀██
███████████████████▄██
▄███████████████████▄██
█████████████████████▀██
██████████████████████▄
.
..CASINO....SPORTS....RACING..
█░░░░░░█░░░░░░█
▀███▀░░▀███▀░░▀███▀
▀░▀░░░░▀░▀░░░░▀░▀
░░░░░░░░░░░░
▀██████████
░░░░░███░░░░
░░█░░░███▄█░░░
░░██▌░░███░▀░░██▌
░█░██░░███░░░█░██
░█▀▀▀█▌░███░░█▀▀▀█▌
▄█▄░░░██▄███▄█▄░░▄██▄
▄███▄
░░░░▀██▄▀


▄▄████▄▄
▄███▀▀███▄
██████████
▀███▄░▄██▀
▄▄████▄▄░▀█▀▄██▀▄▄████▄▄
▄███▀▀▀████▄▄██▀▄███▀▀███▄
███████▄▄▀▀████▄▄▀▀███████
▀███▄▄███▀░░░▀▀████▄▄▄███▀
▀▀████▀▀████████▀▀████▀▀
bones261
Legendary
*
Offline Offline

Activity: 1806
Merit: 1827



View Profile
November 05, 2018, 04:25:00 AM
Last edit: November 05, 2018, 05:40:39 AM by bones261
 #8

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
Legendary
*
Offline Offline

Activity: 1624
Merit: 2481



View Profile WWW
November 05, 2018, 08:59:01 AM
Merited by suchmoon (4)
 #9

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
Full Member
***
Offline Offline

Activity: 378
Merit: 197



View Profile
November 05, 2018, 12:24:31 PM
 #10

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 Smiley

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.

My Address: 121f7zb2U4g9iM4MiJTDhEzqeZGHzq5wLh
chairmember (OP)
Newbie
*
Offline Offline

Activity: 5
Merit: 4


View Profile
November 05, 2018, 01:53:07 PM
 #11

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
Legendary
*
Offline Offline

Activity: 2086
Merit: 4316

<insert witty quote here>


View Profile
November 05, 2018, 07:50:59 PM
 #12

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. Tongue


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.


█████████████████████████
████▐██▄█████████████████
████▐██████▄▄▄███████████
████▐████▄█████▄▄████████
████▐█████▀▀▀▀▀███▄██████
████▐███▀████████████████
████▐█████████▄█████▌████
████▐██▌█████▀██████▌████
████▐██████████▀████▌████
█████▀███▄█████▄███▀█████
███████▀█████████▀███████
██████████▀███▀██████████
█████████████████████████
.
BC.GAME
▄▄░░░▄▀▀▄████████
▄▄▄
██████████████
█████░░▄▄▄▄████████
▄▄▄▄▄▄▄▄▄██▄██████▄▄▄▄████
▄███▄█▄▄██████████▄████▄████
███████████████████████████▀███
▀████▄██▄██▄░░░░▄████████████
▀▀▀█████▄▄▄███████████▀██
███████████████████▀██
███████████████████▄██
▄███████████████████▄██
█████████████████████▀██
██████████████████████▄
.
..CASINO....SPORTS....RACING..
█░░░░░░█░░░░░░█
▀███▀░░▀███▀░░▀███▀
▀░▀░░░░▀░▀░░░░▀░▀
░░░░░░░░░░░░
▀██████████
░░░░░███░░░░
░░█░░░███▄█░░░
░░██▌░░███░▀░░██▌
░█░██░░███░░░█░██
░█▀▀▀█▌░███░░█▀▀▀█▌
▄█▄░░░██▄███▄█▄░░▄██▄
▄███▄
░░░░▀██▄▀


▄▄████▄▄
▄███▀▀███▄
██████████
▀███▄░▄██▀
▄▄████▄▄░▀█▀▄██▀▄▄████▄▄
▄███▀▀▀████▄▄██▀▄███▀▀███▄
███████▄▄▀▀████▄▄▀▀███████
▀███▄▄███▀░░░▀▀████▄▄▄███▀
▀▀████▀▀████████▀▀████▀▀
Pages: [1]
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!