Crack seed phrases with brute force?

[krogothmanhattan]

Since we are talking about Brute force...take a look at this stamp I designed back in 2017. Its loaded with 0.02BTC and the public key and the BIP38 encrypted key have been exposed online for almost 7 years now...BTC is still on it! The password is over a 100 symbols long...i just punched on the keyboard randomly.    https://www.crypto-stamps.com/

  



   One other thing I also do is, I place a non encrypted Bitcoin private key and load it with $10 in BTC....if my computer were ever exposed to any malware sweeping BTC, this would be swept and I would be alerted. Although its not guaranteeing you a clean computer, its a nice alarm so to speak when swept.

[1714582141]

1714582141

[1714582141]

1714582141

[BlackHatCoiner]

Although its not guaranteeing you a clean computer, its a nice alarm so to speak when swept.

It's not guaranteeing you anything. A wallet being emptied does not tell you what's wrong, which software is responsible, when the malware was installed etc. A smart thief wouldn't trade their unknown access with $10, and I strongly recommend you to not expect hackers to be dumb. They may wait until you deposit a decent amount of money, or perhaps valuable files.

Prevention over cure. You should just be aware of your computer's security, and friendly suggestion; don't rely on security through obscurity.

[LoyceV]

the BIP39 encrypted key have been exposed online for almost 7 years now...

It's BIP38, not BIP39. I know, because I've made the same mistake in the past....

The password is over a 100 symbols long...

Given that $1000 was not enough to crack just 6 characters in 2 years (even after giving hints), this doesn't really prove anything. It's probably easier to "guess" the private key itself than guessing your 100 characters.

[pooya87]

The password is over a 100 symbols long...i just punched on the keyboard randomly.   

The only thing a 100 char long password used for BIP38 does for you is to make your work entering it in the future for decryption a nightmare, more so when it is random!

It does not provide you with the security you think it does because in BIP38 algorithm the password is fed into scrypt KDF to derive a 32 byte key which means when you use a bigger than 32 byte password to derive a 32 byte key, your security still depends on the 32 byte size not the much bigger password (eg. 100 byte).

Theoretically to brute force your password, one would just skip the first step (ie to derive a key using scrypt that needs to iterate 100 bytes) and just brute forces the 32 byte derived key.
Realistically since 32 bytes is 256 bit and impossible to brute force, this is impossible to pull off.

[krogothmanhattan]

Although its not guaranteeing you a clean computer, its a nice alarm so to speak when swept.

It's not guaranteeing you anything. A wallet being emptied does not tell you what's wrong, which software is responsible, when the malware was installed etc. A smart thief wouldn't trade their unknown access with $10, and I strongly recommend you to not expect hackers to be dumb. They may wait until you deposit a decent amount of money, or perhaps valuable files.

Prevention over cure. You should just be aware of your computer's security, and friendly suggestion; don't rely on security through obscurity.

   Nobody said it was guaranteeing you anything but its something to bait em with. And yes there are dumb malware that will sweep anything with btc on it. And of course who said I would deposit more! Jeees!

The password is over a 100 symbols long...i just punched on the keyboard randomly.    

The only thing a 100 char long password used for BIP38 does for you is to make your work entering it in the future for decryption a nightmare, more so when it is random!

It does not provide you with the security you think it does because in BIP38 algorithm the password is fed into scrypt KDF to derive a 32 byte key which means when you use a bigger than 32 byte password to derive a 32 byte key, your security still depends on the 32 byte size not the much bigger password (eg. 100 byte).

Theoretically to brute force your password, one would just skip the first step (ie to derive a key using scrypt that needs to iterate 100 bytes) and just brute forces the 32 byte derived key.
Realistically since 32 bytes is 256 bit and impossible to brute force, this is impossible to pull off.

    Exactly....impossible to pull off.....thats how good BIP38 is with a good passpword!

the BIP39 encrypted key have been exposed online for almost 7 years now...

It's BIP38, not BIP39. I know, because I've made the same mistake in the past....

The password is over a 100 symbols long...

Given that $1000 was not enough to crack just 6 characters in 2 years (even after giving hints), this doesn't really prove anything. It's probably easier to "guess" the private key itself than guessing your 100 characters.

   Let em try...that stamp will stay there forever then. Crypto encryprion da best!
 

[Lakai01]

It's BIP38, not BIP39. I know, because I've made the same mistake in the past....
[...]

Count me in 
"At that time" I stumbled across this very good Medium article by Tara Annison, which describes on a (in my opinion) pleasant technical level what is actually happening here and why BIP38 is used in the first place: Encrypted Private Keys — An outline of BIP38.

[NotATether]

I don't think you need to check the checksum while you are are brute-forcing a seed. Because the checksum is deterministic and will always hash to the same value given a particular input.

That's going to save a lot of time and let you search faster, since computing a checksum is particularly expensive and can only be optimized so much.

[o_e_l_e_o]

I don't think you need to check the checksum while you are are brute-forcing a seed. Because the checksum is deterministic and will always hash to the same value given a particular input.

That's going to save a lot of time and let you search faster, since computing a checksum is particularly expensive and can only be optimized so much.

On the contrary - calculating the checksum speeds things up exponentially.

If you are brute forcing a seed phrase, the only way to check you have the correct combination is to derive either a master key or an address from that seed phrase to check against a known value you already posses. To do this requires, at a minimum, 2048 rounds of HMAC-SHA512 and further rounds of HMAC-SHA512 alongside elliptic curve multiplication to work down the derivation path to reach a master key. If you want an address, then add in three SHA256s, one RIPEMD160, and a Base58 conversion as well.

Conversely, calculating the checksum is very fast and requires only a single SHA256.

If you are brute forcing 12 words, then only 1 in 16 seed phrases on average will have a valid checksum. For 24 words, it's only 1 in 256. That means that for either 93.75% or 99.6% of all seed phrases you can exclude them after performing a single SHA256, instead of having to perform the much more computational expensive derivation process as above.

[Casdinyard]

Everyone knows that the words that are used for seed phrases are not random. The BIP39 wordlist (2048 words) is used for creating seedphrases, and they hold a specific meaning. The last seed word generates a checksum, which validates the data. Also, the wordlist isn't infinite, meaning we have a certain parameter.

My question is, Is it possible to crack a seedphrase with brute force? Suppose you have a lot of computing power. Like having a super or quantum computer.

I am not talking about recovering a lost wallet or missing seed words. I know there are many Python based tools, like btcrecover, that can perform this task. If one had the original seed (wrong order) or a part of the seed, like 10 out of 12 words or 21 out of 24 words, one might be able to successfully recover the wallet.

What I am referring to is taking completely random words from BIP39, run some tools and algorithms, and try to make a valid existing seed (Having balance or no balance isn't important).

I know this might be a stupid question, and a lot of you might be wondering why I wanted to know this. The thing is, I saw a bunch of videos on YouTube and Facebook where some tools were trying to bruteforce seeds. They were using thousands of combinations of seeds (I forgot to save the video link). I understand, it might be fake. But is there any technical explanation for my question?

Another small question, why does BIP39 has only 2048 words? What's the reason? Is it related to any maths or equations?

I am not a hacker, cracker, or anything like that, but a curious person who wants to learn new things. If this topic already exists, please give me the reference link. I want to know more.

Possible? yes, probable? Nope.

seedphrases are programmatically generated in such a way that it wouldn't matter if you have the strongest or the fastest computing machine on the planet; as long as it's not a quantum computer running on cubits. there's no chance in hell that people could just brute force their way into your seed phrases since it's randomized without any definitive pattern that would be discerned by the common human being brain. Even more, the longer your seed phrase is, the harder it would be to crack it since there's like thousands if not hundreds of thousands of words in the english lexicon, with trillions of combinations depending on how many words you can generate.

So yeah, don't worry about it getting brute forced or anything. You're good to go.

[hosseinimr93]

Even more, the longer your seed phrase is, the harder it would be to crack it since there's like thousands if not hundreds of thousands of words in the english lexicon, with trillions of combinations depending on how many words you can generate.

A 12 word BIP39 seed phrase is secure enough and since it provides the same security as a private key, you don't really increase your security with increasing the number of words to more than 12.
Also note that the BIP39 wordlist contains 2048 words and it's not that there are hundreds of thousands words used for generating a seed phrase.

[o_e_l_e_o]

as long as it's not a quantum computer running on cubits

Further to hosseinimr93's corrections above, if someone did have a quantum computer of sufficient size and stability (which is a very distant threat), the most effective way to use that would be to attack the ECDLP of coins with known public keys, and not to attempt to brute force seed phrases from scratch.

[Lakai01]

as long as it's not a quantum computer running on cubits

Further to hosseinimr93's corrections above, if someone did have a quantum computer of sufficient size and stability (which is a very distant threat), the most effective way to use that would be to attack the ECDLP of coins with known public keys, and not to attempt to brute force seed phrases from scratch.

Thanks for the food for thought, I was interested in the details of how this could work. In my opinion, the following statement sums it up quite well:

Anyone with a sufficiently large quantum computer could theoretically derive the private key from a known public key and thus, falsify any digital signature. This scenario seems to be the most realistic and vulnerable one. It basically boils down to the unveiling of public keys (a quantum computer could then theoretically “calculate” the private keys), which can occur in different scenarios

Source

However, the article also points out that the solution to this is also quite simple ... avoid address reuse so that the Public Key doesn't get exposed at all:

It is only exposed when the owner initiates a transaction. The majority of coins have been held in this form of address. This means that the public key is unknown, and a quantum computer cannot calculate the private key if funds have never been moved from a P2PKH address. Today, most Bitcoin wallets are programmed to avoid address re-use as much as possible. Always using fresh addresses is already the suggested best practice in Bitcoin, but this is not always followed.

Any address that has Bitcoin and for which the public key has been revealed is potentially insecure in the presence of a quantum computer

What's your opinion about this? Is it really that easy?

[NotATether]

However, the article also points out that the solution to this is also quite simple ... avoid address reuse so that the Public Key doesn't get exposed at all:

It's a bit more nuanced than that.

Your bitcoin public key is only revealed when you make an outgoing transaction, so that means even if you are receiving multiple incoming transactions to the same address, your public key is still hidden until you make the first outgoing transaction.

So, when you make a transaction from an address, you have to make sure you send the rest of the money (i.e. UTXOs belonging to that address) inside it to a different address.

[o_e_l_e_o]

What's your opinion about this? Is it really that easy?

No, it isn't, and keeping your public keys private only provides a false sense of security.

There are dozens of reasons your public key is already exposed. Wallet software generally does not treat public keys as sensitive information and keep them secured like it does with private keys. If you've ever signed a transaction, your public key is exposed. If you've ever signed a message, your public key is exposed. If you've ever used any wallet except Bitcoin Core, then your extended public key (and therefore all your public keys, even those of addresses you haven't used yet) is exposed. If you use taproot, or descriptors, or share xpubs, or create multi-sigs, or a bunch of other things, then your public keys are exposed.

Even if you generate and store your personal public keys on an airgapped device and 100% private, your coins won't be worth anything if a quantum computer can steal the 10 million or more bitcoin with exposed public keys. Public keys are meant to be public. The security of bitcoin against quantum computers will come from forking to a quantum resistant algorithm.

[Lakai01]

[...]
Even if you generate and store your personal public keys on an airgapped device and 100% private, your coins won't be worth anything if a quantum computer can steal the 10 million or more bitcoin with exposed public keys. Public keys are meant to be public. The security of bitcoin against quantum computers will come from forking to a quantum resistant algorithm.

Thank you very much for the explanation oeleo!

Regarding the highlighted part of your statement:
What makes me a bit perplexed is that you hardly hear anything around the forks towards quantum computing resistance. Especially since people like Sundar Pichai (Alphabet CEO) assume that quantum computers will break current encryption "within the next 3 years". Algorithms such as SHA3 would already exist ...

Without wanting to annoy you too much with my questions ... How do you see this topic? Is the danger of quantum computers overestimated or is the developer community aware of the danger and already working on it without scaring the community too much?

[o_e_l_e_o]

What makes me a bit perplexed is that you hardly hear anything around the forks towards quantum computing resistance.

There is discussion happening in various places, for example this thread from last year on the Bitcoin Dev Mailing List: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-April/020209.html

Especially since people like Sundar Pichai (Alphabet CEO) assume that quantum computers will break current encryption "within the next 3 years".

That's a very nebulous statement. "Current encryption" is a massive category, some of which can already be broken even with conventional computing, some of which will be secure for decades to come. I do not think bitcoin will be vulnerable to quantum computers for many more years yet.

Is the danger of quantum computers overestimated or is the developer community aware of the danger and already working on it without scaring the community too much?

I don't think the danger per se is overstated - at some point I do expect ECDLP will be broken by quantum computing. I think the timeline is very overstated, and as above, don't think this is going to happen for years yet. Forking to a quantum resistant algorithm now, when the actual threat is probably still decades away, would be a mistake. Whichever algorithm we picked today would at best be very outdated, slow, and inefficient by the time it was necessary, and at worst be insecure.

[Lakai01]

[...]
Forking to a quantum resistant algorithm now, when the actual threat is probably still decades away, would be a mistake. Whichever algorithm we picked today would at best be very outdated, slow, and inefficient by the time it was necessary, and at worst be insecure.

Thank you again for your explanations.
What currently "reassures" me somewhat about this topic is the fact that we would have completely different problems if encryptions such as SHA256 could be broken. Bitcoin is probably a relatively minor concern compared to the impact on the financial sector or the internet in general.

Nonetheless, it's a very exciting topic (especially from a technical point of view) and one that I will definitely be looking into in more depth.

[o_e_l_e_o]

What currently "reassures" me somewhat about this topic is the fact that we would have completely different problems if encryptions such as SHA256 could be broken.

Your statement here isn't quite correct. Firstly, hashing is not the same as encryption, and SHA256 does not encrypt data. Encryption is reversible with the correct key, allowing you to decrypt to the original message; hashing is a one way function, often with a much smaller output than input (meaning data has been lost and therefore cannot be reversed).

Further, SHA256 isn't particularly susceptible to quantum computers. As far as bitcoin goes, the most quantum susceptible part is the elliptic curve multiplication which turns a private key in to a public key.

But yes. If elliptic curve multiplication can be broken, then much of the encryption used across the internet and around the world will be similarly broken.