Topic: Risk Of Losing Bitcoins Through Seed Creation (Read 359 times)

This is quite a common concern for a lot of people who don't understand the sheer vastness of the "keyspace" being generated by this "fixed and known" list.

People will quite happily secure their online banking or whatever with a 10-12 character password... if you use UPPERCASE + lowercase + numbers... that's 26+26+10 = 62 possible characters... then we can throw in the 33 ASCII printable "symbol" characters like ~!@#$%^&*()_+ etc... and all up it would be 62+33 = 95 characters in your "fixed and known list".

So, a 12 character password using this list would be: 95 * 95 * 95 * 95 * 95 * 95 * 95 * 95 * 95 * 95 * 95 * 95 = 540360087662636962890625 possibilities.

The 2048 word list that Electrum uses means that your "alphabet" has 2048 characters... so that means your 12 word seed is effectively a "12 character password where the alphabet has 2048 characters" in it. Giving up this many different seeds: 2048 * 2048 * 2048 * 2048 * 2048 * 2048 * 2048 * 2048 * 2048 * 2048 * 2048 * 2048 = 5444517870735015415413993718908291383296 possibilities...

monospaced to illustrate the difference in length of the 2 numbers.

If you're not worried about someone hacking your 12 character password, you don't need to be worried about someone hacking your 12 word seed.

You cannot have an index of 2²⁵⁶, as the limit for each index is 2³². 0 through 2³¹ - 1 is used for unhardened indices, and 2³¹ through 2³² - 1 is used for hardened indices. Using the ' symbol to denote a hardened index is essentially code for whatever number you pick plus 2³¹.

You can, however, have up to 255 additional levels to your derivation path beyond m, which means that theoretically any seed phrase can produce a maximum of (2³²)²⁵⁵ private keys, which is a number many orders of magnitude larger than the number of possible private keys.

Electrum is open source, and as such, you could change the default derivation paths routes for the change index. So you would specify /84'/0'/14' as the derivation path after changing the index for receiving/change addresses. While the implementation may be non-standard, the resulting addresses are standard, as are any transactions sent from those addresses (all else being normal).

The point of my post was that given a high enough index range, such as m/84'/0'/14'/0 through m/84'/0'/14'/2^256 you will have collisions with address that other people have generated, however it is not possible to generate that many addresses.

Except Electrum would never use those derivation paths, since if you are following BIP44, the change value will only ever be 0 for external chain or 1 for internal chain, and never 4. Since Electrum automatically adds /0/x on to the end of your specified derivation path for receiving addresses and /1/x for change addresses, then the closest you could come would be to specify m/84'/0'/14'/4, which would give your first address at m/84'/0'/14'/4/0/0 - bc1qgz9qy5wnj2a5wq2gd5yu4ld5ud6l364flxzjzz.

You could obviously still derive those addresses externally if you wanted and import the private keys individually in to Electrum, but they do not follow the BIP44 standard.

Thanks to all for the illuminating comments.

I'll shut up and stop worrying about theoretical issues and I'll follow o_e_l_e_o's advice:
The weakest part of bitcoin is almost always the user. Rather than worrying about the impossible (someone breaking 128 bits of security), worry about all the other ways you are risking your coins instead.

Say for example, I have a seed of:

The first five addresses I would generate would be:

You can get a high-level overview of how the above addresses are created by looking at this post from Greg Maxwell in 2011.

At a high level, when you "generate" an address in electrum, you are passing a derivative of your seed, and additional data into a hash function, the output of which is the private key of your "generated" address. The additional data passed through the hash function changes in a predictable way, such that it is trivial to calculate the "additional data" based on the number of addresses already generated.

Generating one additional address via electrum, is the same as generating one additional private key. I refer you to the image previously posted by bitmover. If you were to continue generating addresses with your seed, you would eventually generate every potential private key. However, it is not possible to generate every private key because the sun does not contain enough energy.

I don't mind if someone inquires and even questions the security of the network unless I can feel a malicious tone or agenda. With OP, I am not feeling one. His first sentence might be leaning in that direction, but I still look at it as someone asking how possible is a scenario where a user keeps creating new Electrum seeds and wallets until he finds a collision.

It would have been much worse if he had claimed that Bitcoin/Electrum is unsafe because it's easy to find someone else's seed, and he supported his claims with false data, stats, etc. Here, it still seems like OP is looking for some clarification.   

If someone knows your 12 words, it is trivial for them to generate your private keys and addresses.
If someone does not know your 12 words, it is impossible for them to generate your private keys and addresses.

Even if you used every piece of computing hardware in the world for this task, and consumed every single joule of electricity in the world to run it all, you would not find a collision.

No.

My paranoid thought experiment relies on the fact that the words for the Electrum passphrase are fixed and known.

By default, the 12 words from 2048 do offer a huge combination. As has been pointed out, the risk of accidental duplication is small.

However, if my understanding is correct, in my thought experiment it is easily possible to generate the private keys and addresses that would be created by a real Electrum wallet using the 12 words. A large number of addresses that would result from these keys could be generated relatively easily.

In the attack, the blockchain could be scanned for one of these addresses, and finding any one would confirm that there exists (or existed) a valid wallet with potentially unspent coins. The wallet funds could then be stolen by generating new spends and sent to addresses owned by the attacker.

While large amounts of computing power might be needed, this attack would work against airgapped wallets as well as those on-line.

Is this a feasible (if computationally expensive) attack, or have I misunderstood?

Adding more words would make the computation exponentially more expensive.

I always find it amusing just how many threads we see popping up along these lines, of people wondering "What if someone guesses my seed phrase" or "What if someone generates the same private key as me". The 128 bit security provided by your seed phrase and private keys is probably the strongest part of your entire security set up for most users. They go around splashing their KYC data and their addresses all over the place, advertising to the entire world who they are and how much bitcoin they own. They keep their coins in web wallets or software wallets on their daily use computers, which are running outdated version of bad OSs filled with vulnerabilities, have installed hundreds of pieces of unnecessary software, and which they use to visit all manner of websites and download a variety of questionable things. They use 2FA linked to their email address, the email address which has the same password as every online account they own, which also happens to have been leaked months ago but they didn't even realize. They keep their seed phrase backed up in the cloud, but that's ok because they've used some outdated and non-open source ZIP software to add a (weak) password to it. And as they do all this, they worry about the one thing in their set up which is orders upon orders of magnitude more secure than literally every other part of their set up.

The weakest part of bitcoin is almost always the user. Rather than worrying about the impossible (someone breaking 128 bits of security), worry about all the other ways you are risking your coins instead.

You could fall out of an airplane in midflight, be hit by another airplane on your way down, land face first, and still survive. Theoretically, there is a miniscule chance of that happening. Remember that Russian paraglider who crashed, fell, and got a tree branch stuck in his shoulder that probably saved his life?

Sorry for making such a ridiculous comparison, but my point is that the chances for both these scenarios from happening are so small that they are not worth worrying about.     

I was hinting at things such as malware that would prevent the OS from generating a secure random number.
If the malware is targeting users who are going to be generating private keys on offline computers that will never touch the internet in the future, stealing information is not going to do very much because it would have no way of transmitting the stolen information.

My guess is that any malware that targets PRNG is going to be state-sponsored whose targets are embassy employees and spies, so their communications can be intercepted and decrypted.

Drifting a bit from the original thought but don't we kind of have the same issue with hardware wallets. We hope that the ATECC608A or the Infineon secure elements are not vulnerable. But in the end we still have to have some trust someplace.
Is it easier to hack / find vulnerabilities in an OS then a chip. 100% yes. But you can also more or less code around them. If some of the hardware encryption devices are found with issues, it's a bigger deal.

-Dave

The difference between the chance of a single 12-word seed being made twice and the chance of a single 24-word seed being made twice is approximately ~2.93 * 10^-39. Although technically about a bitcoin private key, and not an electrum seed, the image that bitmover posted nicely illustrates the risk of a collusion.

---

It is important to make sure that your computer is capable of generating random numbers. In 2013, for example a flaw in Android devices prevented them from generating cryptographically random numbers, which resulted in the risk of malicious actors being able to steal any coin stored on Android devices. The above did not ever affect electrum.

Today, most computers and mobile devices can generate cryptographically random numbers. However, if your device is infected with malware, the malware may cause your computer to generate numbers in a predictable manner, which could lead to a hacker stealing your money, even if you generated the seed on an offline computer (that was infected with malware).

Nicely said, and I think it sums up what matters in all doubts about how safe the seed is and the way it is generated. I think that these things are not completely clear to a large number of users, and they are very important if someone has doubts as an OP. When I made my first wallet I didn't have any doubts like this because MultiBit didn't have a seed, but later I had the same doubts as an OP until I learned that seed is just a simple presentation of something much more complicated and not as simple as it seems at first glance.

However, it is quite logical that people feel safer if the seed has 24 words and a passphrase, and if it helps a person sleep more peacefully, it is good that such things exist

128.

Correct.

That a length of 256 bits does not equate to 256 bits of security.

The best known attack against a private key is not random brute force (which would indeed equate to around 256 bits of security), but rather attempting to solve the ECDLP, which provides 128 bits of security.

This can be seen in Standards for Efficient Cryptography. SEC 2: Recommended Elliptic Curve Domain Parameters. (Table at the bottom of page 4.)

128 or 256?

Isn't that any integer between 1 and 2²⁵⁶ (or any 64 character number in hexadecimal format) can be turned into a valid private key?
I know the exact number is a little smaller due to secp256k1 ECDSA standard, but the number of valid private keys should be much bigger than 2¹²⁸.

What I am missing here?

I think everyone should be using passphrases, since they are the best way to provide plausible deniability to your wallets, and also provide extra security should an attacker discover your seed phrase back up. However, they do absolutely nothing to prevent someone from brute forcing or stumbling across one of your private keys (which is already so rare as to essentially be impossible before the the death of the sun).

The security of a bitcoin private key is 128 bits. It doesn't matter if you add an entire paragraph or 10,000 random characters to your seed phrase - your private keys will still have a security of 128 bits. Further, given the way in which private keys are generated from a seed phrase, there is just as much chance as a completely different seed phrase generating an address which is the same as an address from your wallet, with or without an additional passphrase. In fact, I would say this is more likely, since many wallets will generate a single seed phrase, but then generate 20+ addresses from that single seed phrase, meaning that there are 20x as many chances of an address being duplicated than of a seed phrase being duplicated.

This image illustrates this idea.



source

The chances of a "hacker" to generate a seed that was used before is virtually zero. The only risk would be if you generate the seed by yourself or bad software, seeds with poor randomness. For example, a seed with 12 words like this:

Some of those repeated word lists passes the checksum. This is why you should always use a decent software to generate your wallet.

There's good reason to add random words passphrase (Electrum call it "Extend with custom words") after 12/24 words sequence, but avoiding possibility of duplicate generated seed isn't one of them.


To be more specific, Electrum use cryptographic secure PRNG which provided by the OS (for example, /dev/urandom for linux) through function os.urandom.