Topic: A. Antonopoulos’ Take on Seed Splitting and Bruteforcing - page 2. (Read 726 times)

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.

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.

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.

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.

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. 

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.

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.

Depends. Resources needed is immense.
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?

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.

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. 

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. 

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.

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. 

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.

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?

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.

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.

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?   

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

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.

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.

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.

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.

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