A. Antonopoulos’ Take on Seed Splitting and Bruteforcing

[Pmalek]

I was watching this video of Andreas explaining the dangers of splitting your seed into several parts. He was answering a question from someone who wanted to know about the safety of splitting the seed into three different locations. Any two of those locations would contain all the words and would be enough to recreate the mnemonic.

A)   Words 1-8 and 9-16
B)   Words 1-8 and 17-24
C)   Words 9-16 and 17-24

Andreas explains that it’s a bad idea and suggests using Shamir's Secret Sharing scheme to those who want to split up their seed words for whatever reason.

A 24-word recovery phrase contains 256 bits of entropy. That’s impossible to brute-force with today’s technology. In the proposed method of spitting represented above, there are 16 out of 24 words in each location. 8 words are missing. AA explains how the last word of the phrase is the checksum, and since only one word fits in that position, it can be brute-forced much easier than the rest.

Location A doesn’t contain the checksum, and you will be required to brute-force 7 of the missing words + the checksum. AA says that it decreases the entropy to 80 bits that need to be brute-forced. I don’t have any knowledge about brute-forcing, but Andreas says that’s an exponential. It’s not going to take one-third of the time (since you only need to crack 1/3 of the seed). It’s much less than that. According to the explanation under the video, it’s 2^176 times easier to brute-force those 80 bits of entropy. He goes on to mention that this could be easily done in the next decade with the appropriate hardware, especially if the checksum is known.   

Did he set the bar too low, or could this be “easily brute-forced in the next decade”? 2^176 times quicker to brute-force doesn’t tell me much about a timeframe, so with the most powerful possible hardware, how long would such a process take approximately?


The video about this topic can be watched here:
https://www.youtube.com/watch?v=p5nSibpfHYE&list=PLPQwGV1aLnTuN6kdNWlElfr2tzigB9Nnj&index=35

[vjudeu]

how long would such a process take approximately?

There are blocks with SHA-256 hashes starting with 80 zero bits. Current block reward is 6.25 BTC plus fees. Imagine there is some seed with more coins than block reward. Then, it may be more profitable to break that seed than to mine the next block. For the same reason, 80-bit *.onion addresses were discarded, because bruteforcing such name may be more profitable than mining next block. If we consider SHA-256 as a safe and one-directional hash function, where people are really doing 2^80 operations to mine it, then we can assume 2^80 security is not enough and that in some cases attacking may be more profitable than mining.

So how long it would take? Around 10 minutes for the whole network per seed. Of course ECDSA operations are more complicated than hashing, but if we look at transaction puzzle, then we can see that 2^63 key with only address known was taken and 2^115 key with public key known was also taken. So, it will take some time to break it, but attacks only get better and in the future when attacking will be more profitable than mining, then you will see such attacks if that kind of seeds will be used and if many coins will be accumulated there.

[Coding Enthusiast]

There are blocks with SHA-256 hashes starting with 80 zero bits.
So how long it would take? Around 10 minutes for the whole network per seed. Of course ECDSA operations are more complicated than hashing,

These two are not comparable. To mine a bitcoin block there is only 3 SHA256 block compressions while to brute force a BIP39 mnemonic in most optimized scenario it takes 1 SHA256 block compression, 4,101 SHA512 block compressions + 4 SHA512 block compressions per path index + 1 EC point multiplication per non-hardened path index.
For a path like m/44'/0'/0'/0/0 this is 4,121 SHA512 blocks which is 1373 times more than what miners compute and we are ignoring the EC point multiplication. If we assume the data could be extrapolated, it should at least take 10 days to 2 weeks not 10 minutes.

Another issue is whether we can actually build an ASIC that does all the operations needed to brute force a BIP39 mnemonic and more importantly if it can operate as efficiently as a simple SHA256 ASIC that repeatedly runs a much simpler algorithm.

but if we look at transaction puzzle, then we can see that 2^63 key with only address known was taken and 2^115 key with public key known was also taken.

That's another bad comparison. The "puzzle" is a puzzle and in that search one starts searching in a small private key space and only computes the corresponding public keys. When the corresponding public key is known certain "tricks" could be used to speed it up because of ECC characteristics.
In brute forcing an entropy on the other hand even if the child public key were known it still wouldn't give any edge to brute forcing.

For the same reason, 80-bit *.onion addresses were discarded,

Not exactly. Version 2 onion addresses were truncated (80-bit) encoding of 160-bit SHA1 hashes. SHA1 has been considered weak and broken for many years and cutting that hash by half makes it even easier to attack.
Version 3 also doesn't use a hash anymore it is encoding the actual ed25519 key.

[Pmalek]

If we assume the data could be extrapolated, it should at least take 10 days to 2 weeks not 10 minutes.

That's still quicker than what I assumed it would be. I wish I had better technical knowledge on the topic to not sound like a noob and respond in a more professional manner, but I don't. How important is knowing the checksum compared to not knowing it in that estimate of yours?   

Another issue is whether we can actually build an ASIC that does all the operations needed to brute force a BIP39 mnemonic...

Is there optimism that such technology couldn't eventually be developed?

[ranochigo]

Shamir's Secret Snakeoil : https://en.bitcoin.it/wiki/Shamir_Secret_Snakeoil#Examples_of_Shamir_Secret_Snakeoil.

Our current mining ASICs are incredibly specialized in the sense that they are very good at hashing block headers and incrementing the nonces but nothing else. There is a reason why ASICboost has made certain ASICs faster than those without. I agree, the network hashrate and cracking BIP39 seeds cannot scale to the same level.

Is there optimism that such technology couldn't eventually be developed?

Thought I'll address this as well: It can be developed, for sure. It isn't particularly difficult. The problem is not how hard is it to be developed, but how big is the market for it. Would there be any point in the future where people are able to get partial seeds readily? Scrypt was ASIC resistant as well, but it didn't take too long for an ASIC for it to be developed... Just that it was quite memory intensive. The costs of the R&D into the mining ASICs that we've seen today is subsidized by the huge market for it.

I'm not so sure if I agree on it from a cost-benefit POV. Sure, it might weaken the security but does it mean that it'll get exponentially easier and cheaper in the future to do so? For one, you need to compromise the partial seeds first and you also need to invest time and money into cracking it. Wouldn't it be more worth to just go out and buy some Bitcoins instead of cracking some partial seeds. Not that SSS is fundamentally flawed, but if you're asking me to choose between something that is foolproof and infeasible enough to crack or something that is difficult to implement and difficult to crack, I'll choose the former.

[Coding Enthusiast]

How important is knowing the checksum compared to not knowing it in that estimate of yours?

Very important because for each checksum that fails all the HMACSHA512 computation and the EC multiplication that comes next will not be skipped. For example for a 12-word mnemonic we only have to fully check 6% of the permutations on average.

Even with skipping this much by using checksum the algorithm is still very slow. For example for my recovery project I've been squeezing every ounce of performance that I could and I still can not reach half a million checks/second while at the same time recovering a WIF (which is essentially a double SHA256 similar to mining, ie. 2 blocks instead of 3) despite complexity of Base58 encoding goes as high as 60 million checks/second.

Is there optimism that such technology couldn't eventually be developed?

There is not enough incentive. We are talking about breaking a mnemonic that we know most of it, like a paper backup that was torn in half. How many cases of this is found out there anyways and how much bitcoin they've got locked up?

[Pmalek]

The problem is not how hard is it to be developed, but how big is the market for it.

If the technology can be used for evil and can do bad things, there will be a market for it.

Wouldn't it be more worth to just go out and buy some Bitcoins instead of cracking some partial seeds.

Don't look at it in that way. Look at it from the point of view of someone who doesn't like the benefits that Bitcoin offers. Be it a government, a political party, or the banking elite. If bans and regulations don't deliver the expected results, let's try to hit the security of Bitcoin and show everyone how useless it it. Think about it in that way, for example. 

[ranochigo]

If the technology can be used for evil and can do bad things, there will be a market for it.

Don't look at it in that way. Look at it from the point of view of someone who doesn't like the benefits that Bitcoin offers. Be it a government, a political party, or the banking elite. If bans and regulations don't deliver the expected results, let's try to hit the security of Bitcoin and show everyone how useless it it. Think about it in that way, for example.  

This doesn't impact Bitcoin. The security that the 12 word or 24 seeds provide isn't the issue here. The issue here is how many words can be exposed before it becomes vulnerable to an adversary, which doesn't concern Bitcoin's security at all. The entropy that our seeds provide >128bits isn't vulnerable to any attacks, ASICs or not, at least it isn't feasible in the near or the far future.

The market for this ONLY exists if there is an abundance of seeds out there, which are partially exposed. Since we are concerned about the cost/benefits of developing such an ASIC, would it be reasonable to assume that in the future, there exists billions of dollars worth of partially exposed seeds? Probably not. No one really cares if you can bruteforce partial seeds anyways, because the negligence of the user is at place here, not how we designed BIP39 to be. It doesn't undermine the security of our implementation, and cracking a seed that is securely generated and stored is far, far, far more expensive (both in terms of the monetary and the resources required) and also improbable than any rewards you'd possibly get.

[Pmalek]

This doesn't impact Bitcoin. The security that the 12 word or 24 seeds provide isn't the issue here. The issue here is how many words can be exposed before it becomes vulnerable to an adversary, which doesn't concern Bitcoin's security at all.

How much time will be required to crack the remaining words with X amount of words exposed, exactly. But why do you say that such a technology wouldn't negatively impact Bitcoin in its current state? If it becomes possible to crack 8 words tomorrow, in two years time it might be possible to crack 12. Once 12 becomes brute-foreable, could 15-16 be penetrable in 10 years? Cracking a part is just the testing phase to the ultimate goal of cracking it all. 

It doesn't undermine the security of our implementation, and cracking a seed that is securely generated and stored is far, far, far more expensive (both in terms of the monetary and the resources required) and also improbable than any rewards you'd possibly get.

Forget the monetary rewards and just focus on someone wanting the death of Bitcoin. Death in its current state unless it can adjust to an algorithm strong enough to withstand the new attack technology. I suppose that shouldn't be difficult considering that the interests of everyone involved with Bitcoin is in jeopardy. 

[ranochigo]

How much time will be required to crack the remaining words with X amount of words exposed, exactly.

Depends. Resources needed is immense.

But why do you say that such a technology wouldn't negatively impact Bitcoin in its current state? If it becomes possible to crack 8 words tomorrow, in two years time it might be possible to crack 12. Once 12 becomes brute-foreable, could 15-16 be penetrable in 10 years? Cracking a part is just the testing phase to the ultimate goal of cracking it all.  

Because the difficulty of cracking them becomes exponentially harder. Exhausting 80 bits of search space is 2.8147498e+14 times easier than going through the search space of 128bits. Currently, the entire Bitcoin network calculates ~ 80+ bits within a short period of time, but if you were to go to 128bits, that would go to billions of years (~8.43e+10 year). The search space is gigantic and I believe that we've talked about how big 128 bits of entropy is, many many times and how infeasible it would for anyone to even try to exhaust the search space. There is a reason why the topic was centered about partial cracking and not fully compromising Bitcoin seeds.

As a disclaimer, the hashrate of Bitcoin network cannot be approximated to be the same. Reason being, the ASICs that we have operates by a simple principle; where you only take data to double hash them, check the hash and then increment or change the parameters. The same cannot be said for an ASIC that would be made specifically for cracking BIP39 seeds. Even if it does, if it takes billions of dollars of equipment, not including R&D together with the electrical consumption of a country. All that just to crack a few dollars worth of nearly fully exposed BIP39 seeds. It's far cheaper, easier and impactful to just execute a 51% attack, don't you think?

Forget the monetary rewards and just focus on someone wanting the death of Bitcoin. Death in its current state unless it can adjust to an algorithm strong enough to withstand the new attack technology. I suppose that shouldn't be difficult considering that the interests of everyone involved with Bitcoin is in jeopardy.  

BIP39 is a way to get the mnemonic to generate BIP32 seeds. BIP32 seeds are used to generate master keys to generate Bitcoin address. Are we talking about cracking Bitcoin addresses or are we talking about the possibility of cracking a standard for generating Bitcoin addresses? We aren't talking about cracking individual addresses in the first place and even if we are, it is practically impossible.

[o_e_l_e_o]

It comes back to the same argument that we see often repeated regarding quantum computers.

If (and it's an enormous if) we ever reach a point where we can crack 128 bits of security, we are not going to reach it overnight. It will take decades, if not centuries, of constant progress towards that goal, and everyone who is actively using bitcoin will have decades to move to more secure seed phrases, private keys, and addresses. Further, if someone can crack 128 bits of security on a whim, then we have much bigger problems than partially exposed seed phrases being cracked.

I'm not a fan of splitting seed phrases in the method outlined in OP, and I'm also not a fan of SSSS. If you want to have multiple back ups which need to be compromised to access your coins, then either go for a seed phrase with an additional passphrase of minimum 128 bits security, or use a multi-sig wallet.

[NotATether]

Forget the monetary rewards and just focus on someone wanting the death of Bitcoin. Death in its current state unless it can adjust to an algorithm strong enough to withstand the new attack technology. I suppose that shouldn't be difficult considering that the interests of everyone involved with Bitcoin is in jeopardy.  

You forgot the easy $5000-dollar solution of governments (cause let's be honest, these are the only people who can and want to remotely do such a thing) just banning miners from operating in their country like China did. They don't need to do any specialized brute-forcing or "false mining" and there probably aren't enough miners produced every year to make this remotely feasible anyway.

[Pmalek]

...just banning miners from operating in their country like China did.

I don't believe it will come to a worldwide Bitcoin mining ban in the future. The Chinese government lives according to its own rules. I don't see that being reproduced in many other places, especially not in the West. What could happen is that we could see a stronger opposition of the use of fossil fuels, which would impact Bitcoin mining. But switching to other sources of energy production is something we will have to face sooner or later anyways. 

[dkbit98]

Splitting seed words is a terrible idea, but Shamir's Secret Sharing is also bad compared to Multisig solution, it has single point of failure and it can be used only with Trezor Model T as far as I know.
I think that trying to brute force multisig setup would be nearly impossible, if done correctly.

If they attempt to attack Bitcoin's security, brute-force will be last thing they'll do since usually they don't have part of the seed words. I would worry about malicious wallet software, weak RNG or hardware wallet with weak transparency instead.

I also think that brute-force attack is not going to happen any time soon, but I know some people are having wet dreams about quantum computers that could potentially brute-force everything and not just Bitcoin.
Look how much money China spent to ban Bitcoin mining - zero yuans, they just banned it and force is the language of all government parasites, no need to spend money on attacking Bitcoin.

But switching to other sources of energy production is something we will have to face sooner or later anyways.  

It doesn't mater what we use as energy source if all of them are owned by same corporations and families.
Imagine if someone would to invent energy source that would be totally free and you wouldn't have to pay anything to use it... would those big corporations allow that... I don't think so.

[SquirrelJulietGarden]

In a livestream for Crypto security Passwords and Authentication
AA said that people should not complicate the back up procedure because when they lose one part of the complicated procedure, of the back up, they will lose the wallet.

I don't understand the very advanced points in Bruteforcing but I will take the advice from AA in his previous livestream.

[ranochigo]

In a livestream for Crypto security Passwords and Authentication
AA said that people should not complicate the back up procedure because when they lose one part of the complicated procedure, of the back up, they will lose the wallet.

I don't understand the very advanced points in Bruteforcing but I will take the advice from AA in his previous livestream.

Could you point out the timestamp for which this is mentioned? The livestream is far too long and I can't find anything related to this when doing a quick scrub of the timeline.

The alternative to the scheme which is much simpler still gives sufficient redundancy if several pieces are lost, just like in Multisig where you have redundancy in terms of the signers which are not cooperative. Common seed splitting schemes are easily implemented and reproduced without the need for any complicated code.

[HCP]

AA explains how the last word of the phrase is the checksum, and since only one word fits in that position, it can be brute-forced much easier than the rest.

That's actually incorrect. For a 24 word seed there are actually 8 words that will be a "valid" checksum... not just one, because 3 bits out of the last 11 are actually entropy, not checksum.

It's "worse" for a 12 word seed... as only 4 bits of 11 are checksum... so 7 bits of entropy... so you're looking at 128 words that would be a valid checksum.


Of course... that doesn't really change the fact that it is still much easier to bruteforce this as it's only 8 words (128 words in the case of 12 word seed) instead of 2048... but it isn't quite as simple as "stop when we find the first word that makes a valid checksum", you'd still need to check the others.

[Pmalek]

AA said that people should not complicate the back up procedure because when they lose one part of the complicated procedure, of the back up, they will lose the wallet.

Andreas also explains if someone where to find a part of Shamir's share and if that part is less than the quorum, it's like not having any information about the seed at all. That's the complete opposite of knowing 8 or 16 words as explained in the example in OP. And if one part of the SSSS share is lost, the data would still be recoverable.

[NotATether]

Fortunately, Quantum computer isn't magic which can brute force everything instantly. Besides, i doubt attacking Bitcoin will be top priority if government have one.

But breaking elliptic curves and RSA security will be.

Notice that the NSA are the first organization who get access to a particular new advancement in technology such as computers and most of the time they are using it for national security purposes i.e. they are trying to break encryption schemes, so everything from the NIST-issued P-*** curves to commercial sizes of RSA keys and SEC2 and curve25519 curves are at risk, basically anything that is used by businesses, rival governments, etc.

[pooya87]

~rival governments, etc.

Some governments actually use their own standardized cryptography. For example China has its own cryptography standards that includes hash algorithms, asymmetric cryptography, block ciphers, etc. I suppose they also have their own non-public algorithms to use for top secret stuff.