Pages:
Author

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

HCP
legendary
Activity: 2086
Merit: 4361
November 18, 2021, 01:08:18 AM
#27
My paranoid thought experiment relies on the fact that the words for the Electrum passphrase are fixed and known.
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...

Code:
540360087662636962890625
vs
5444517870735015415413993718908291383296
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. Wink
legendary
Activity: 2268
Merit: 18711
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.
You cannot have an index of 2256, as the limit for each index is 232. 0 through 231 - 1 is used for unhardened indices, and 231 through 232 - 1 is used for hardened indices. Using the ' symbol to denote a hardened index is essentially code for whatever number you pick plus 231.

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 (232)255 private keys, which is a number many orders of magnitude larger than the number of possible private keys.
copper member
Activity: 1652
Merit: 1901
Amazon Prime Member #7
The first five addresses I would generate would be:
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.
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.
legendary
Activity: 2268
Merit: 18711
The first five addresses I would generate would be:
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.
jr. member
Activity: 32
Merit: 37
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.
copper member
Activity: 1652
Merit: 1901
Amazon Prime Member #7
Say for example, I have a seed of:
Code:
eager assist dutch group deny wealth gown disorder goddess inmate same scrap

The first five addresses I would generate would be:
Code:
path, address
m/84'/0'/14'/4/0,bc1qx3kaxwcuxzsu2ur94453nvfglp8eka9a5fqwpj
m/84'/0'/14'/4/1,bc1q6dmxds943wd8u7r7enr2uyfffgcrfn78gsx7sj
m/84'/0'/14'/4/2,bc1q7v8x5980vvfpx96zp6y2j4jhn8jn2hmuyp90dy
m/84'/0'/14'/4/3,bc1q48935lt9v8ghqmpfmycrpwp0a7wk3jt5tf7mx6
m/84'/0'/14'/4/4,bc1qfvs9arztcgzj7tp8krrw8nq85gfte92cld8u98

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.
legendary
Activity: 2730
Merit: 7065
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".
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.   
legendary
Activity: 2268
Merit: 18711
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.
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.

While large amounts of computing power might be needed, this attack would work against airgapped wallets as well as those on-line.
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.

Is this a feasible (if computationally expensive) attack
No.
jr. member
Activity: 32
Merit: 37
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.
legendary
Activity: 2268
Merit: 18711
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 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.
legendary
Activity: 2730
Merit: 7065
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.     
copper member
Activity: 1652
Merit: 1901
Amazon Prime Member #7
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.

But how would people know their computer OS is capable of generating secure random number? Most people simply assume the OS is secure and some of them only know about it after such vulnerability is disclosed.
I was hinting at things such as malware that would prevent the OS from generating a secure random number.
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).

While it's possible, it's not practical when the malware could simply copy wallet file, steal password using keylogger or read private key from RAM when the wallet opened by user. Are there any known malware which specifically mess with system cryptographic secure PRNG?
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.
legendary
Activity: 3500
Merit: 6320
Crypto Swap Exchange
But how would people know their computer OS is capable of generating secure random number? Most people simply assume the OS is secure and some of them only know about it after such vulnerability is disclosed.

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
copper member
Activity: 1652
Merit: 1901
Amazon Prime Member #7
The 12 words are 128 bits of entropy, which is considered more then enough.
Obviously more words would make it more secure.

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).
legendary
Activity: 3234
Merit: 5637
Blackjack.fun-Free Raffle-Join&Win $50🎲
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).

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 Smiley
legendary
Activity: 2268
Merit: 18711
128 or 256?
128.

Isn't that any integer between 1 and 2256 (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 2128.
Correct.

What I am missing here?
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.)
legendary
Activity: 2380
Merit: 5213
The security of a bitcoin private key is 128 bits.
128 or 256?

Isn't that any integer between 1 and 2256 (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 2128.

What I am missing here?
legendary
Activity: 2268
Merit: 18711
Should users be encouraged to add some random words to reduce these (admittedly minuscule) risk?
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.
legendary
Activity: 2352
Merit: 6089
bitcoindata.science
November 08, 2021, 06:55:57 AM
#9
Imagine if you could see atoms that are in the entire universe. Now imagine if you randomly selected one atom out of the whole set. The chances of someone else also selecting the same atom is the same chance of someone else finding your seed phrase if chosen randomly.

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:
Code:
 word word word word word word word word word word word word

Some of those repeated word lists passes the checksum. This is why you should always use a decent software to generate your wallet.
legendary
Activity: 2870
Merit: 7490
Crypto Swap Exchange
November 08, 2021, 06:42:02 AM
#8
Should users be encouraged to add some random words to reduce these (admittedly minuscule) risk?

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.

The 12 words are 128 bits of entropy, which is considered more then enough.

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