Topic: Crack seed phrases with brute force? (Read 667 times)

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.

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.

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

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.

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.

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?

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.

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.

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:


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:


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

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.

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.

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.

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.

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.

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.

   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!


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


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

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.

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

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.

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.

Got it! I have been reading a lot lately. Not that I understood all of it, but I'm digesting in bit by bit.

Hey, that's a good idea. I actually never though it like that. It might be worth the try. I'll try to keep that in mind.

I never knew that. All I though was those words were selected randomly to complete 2048 word list. Who knew they were something like a disguise of large numbers.

Why not have a seed with a passphrase.

 

    MNEMONIC SEED = WALLET A

    MNEMONIC SEED AND PASSPHRASE= WALLET B

 

    Wallet A would be the bitcoin addresses that would show if ever brute forced.

    I would place a few Sats in it so in case Wallet A is ever brute forced open and swept

    then I would have ample enough time to remove any BTC from wallet B...HOPEFULLY.

 

     The question is, Wallet B is a hidden wallet...so even if someone stole your seed they

   will not be aware of Wallet B.

Yes.

For a simple explanation of how seed phrases and passphrases are combined in your wallet, take a look at the following links:
https://github.com/bitcoinbook/bitcoinbook/blob/develop/ch05.asciidoc#from-mnemonic-to-seed
https://learnmeabitcoin.com/technical/mnemonic#mnemonic-to-seed

If you want a more complex explanation of how PBKDF2 works and the role of the salt in the calculation, then see here:
https://datatracker.ietf.org/doc/html/rfc2898#section-5.2

Think about it this way, why can't we brute force a base58 encoded private key aka a WIF? After all each character in a WIF is selected from a list of only 58 characters which is smaller than 2048! That's because we don't select chars from the 58 char long list, base58 is just an encoding and the security comes from the size of the data or the entropy it is encoding.
BIP39 is exactly the same. We don't select works from a small list of 2048 words, we are encoding a much bigger data/entropy that is not possible to brute force.

Checksums in most algorithms including BIP39 are there to ensure data integrity not validation. In other words it ensures that the words you entered don't contain a mistake like wrong word or wrong order.

Additionally, to differentiate the two and for others to better understand of the term "encrypt":

• With encryption, the original data can be recreated from the secret and the encrypted data.
• PBKDF2 functions like HMAC, however is a "one-way" function, there's no going back from 'seed' to 'seed phrase'.

By salt did you meant this?

As pointed out by BHC above, these calculations are for unscrambling known words. While this is possible for a 12 word seed phrase, unscrambling a 24 word seed phrase even when you know all 24 words is impossible. Brute forcing a 24 word seed phrase from scratch is several trillion trillion trillion trillion times harder than that.

Passphrases do not encrypt seed phrases. They are used as a salt in the HMAC-SHA512 function which turns your seed phrase in to your master keys.

It's a pretty close example for the maximum combinations that a 2048 words can do but that images is mostly used to explain the Bitcoin private key range of 256bits.
My post is mostly about the reason for having only 2048 words.

Just two posts above yours.
I think I did a pretty good explanation and example to make 2^11 which represents each word understandable even for beginners.

Was it because of the last possible number is 2047, Yes?
If you count "00000000000" in which is counted, that'll be a total of 2048 words.

Let me illustrate this answer

They are 2048, because that is 2^11. This means that for every 11 bits you can represent a word. Say that a seed phrase is 128 bits long, which is 12 words long. If you extend these 128 bits to something divisible by 11 (i.e., 132 which is the point of 4 bits checksum), you can represent any seed in a sequence of 132 / 11 = 12 words.

As the video demonstrates, there are just not that many resources to begin with. But, note that the 128-bit security is much less than the 256-bit.

Saw that video. Man, that's a lot of numbers. Not just lots, a lot!!! I imagine there is no word in this world to quantify this amount of numbers. I get it. Basically the point is that, it will take forever. 

So those seed phrase are not real numbers, I mean, of course, they are in human readable form but in computer sight, they are in bits. Wait a second are you talking about these stream of bits.

Well, I just watched the video preferred by the BlackHatCoiner and it was really awesome and convincing, although, I am getting used to forget things, but I did knew about bits before. Just your statement reminds me of it. Thanks for it.

Overall, I am also having similar thoughts, and wanted to ask about it, but did not had the time to search about it on my own, but due to this thread, I don't have to spend time. But nobody gave the answer to the question of why the number of words are limited to 2048, or anyone have already gave!

This is where your assumption takes the wrong path. It doesn't matter that the words are not random, the words are only used as a human readable interpretation of a very large random number. So, the number is random, and you use common words to avoid mistakes writing it down.

My take on brute-forcing: try it!

Here's the small answer  

Because the entropy (plus checksum) where the mnemonic seed is based from is sorted per 11-bits, each of those 11-bit part corresponds to a word.
Then the reason for "2048" is because that is the limit that an 11-bit number can do, from 00000000000 (0 in decimal) to 11111111111 (2047 in decimal)

If your whole point is if someone can guess your seed phrase then it's possible so if you are afraid about your wallet you can manually add an extra word/passphrase on BIP39 wallet to encrypt your seed phrase even if they know your seed phrase they can't still able to access your wallet without the extra word/passphrase.

If you want to scale security, forget about words and seed phrases. A seed phrase is an encoding of a 256 bit entropy. That means there can be 2^256 different seeds. Here's a great video that demonstrates how big that is: https://piped.video/watch?v=S9JGmA5_unY.

Nobody is going to randomly brute force seed phrases, unless they're nuts. In fact, a private key can be cracked more easily as the public key cryptography used in Bitcoin provides 128 bit security.

Note that he's talking about brute forcing by knowing which words are used but not the order of them. If you don't know the 24 used words, then you'll have to choose among 2048, which raises the time exponentially.

Moved...


I know it's not wise to choose our own seed words. Just like today, I was also curious about choosing my own seed words. That why I created a thread in the past and got that answer. Can we choose our own seed words?

The checksum isn't the last word.
In a 12 word seed phrase, the checksum is the last 4 bits and in a 24 word seed phrase, the checksum is the last 8 bits.

A 12 word BIP39 seed phrase provides 128 bits of security and is secure enough.


It's possible to pick random words from the BIP39 wordlist and have a valid seed phrase, but it's not possible that the seed phrase has been already generated by someone else before.
As I said, a 12 word BIP39 seed phrase provides enough entropy.

Take note that it's not a secure way to generate a seed phrase by selecting words. The correct way is to generate a random entropy and then encode that to a seed phrase.

Move thread to bitcoin support Board.


Here is o_e_l_e_o explanation on the topic, this means for 24 words we will probably be looking at billions of years to come.


Because it doesn’t matter as long it is a 12 word seed phrase the entropy will remain 128 bits and 256 bits if it is a 24 word seed phrase and the entropy is actually what determines the security or randomness of the word not how many they seems to be. Here is also a thread explained by o_e_l_e_o on it

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.