|
Title: Are the 12 worded seeds really secure from Brute force? Post by: adaseb on December 15, 2016, 11:12:41 AM I found the dictionary file that Electrum uses to make the 12 worded seeds.
https://github.com/spesmilo/electrum/blob/master/lib/wordlist/english.txt At first I assumed that it used a 30000-60000 word dictionary but instead its 2048 words. So with 12 words there are a possible 2048^12= 5.4445178707350154154139937189083e+39 combinations. However can't someone design some SHA256 like ASIC which is capable of hashing 10TH/s to look for wallets with balances on them? With 10TH/s it would take 544451787073501541541399371.89083 seconds to hash each and every possible commbination. However lets say there are already 1,000,000 seeds with some type of balance in them. That would reduce the collision to 544451787073501541541.39937189083 seconds. Say someone builds like one thousand of these 10TH/s ASICs so it would take instead 544451787073501541.54139937189083 seconds to find one valid seed with a balance. So if they hashed for an entire year it would take 17264452913 years to find that one seed. So if my math is correct, it seems its next to impossible to brute force any Electrum keys. Title: Re: Are the 12 worded seeds really secure from Brute force? Post by: Abdussamad on December 15, 2016, 01:11:38 PM your math probably isn't correct because it is supposed to take until the heat death of the universe even if you use all the computers in the world non-stop ::). you're using just 1000 asics in your example.
part of that seed mnemonic is actually a checksum so you have to discount that. once you remove the checksum you find it's a 124bit seed. so 2^124 possibilities. Title: Re: Are the 12 worded seeds really secure from Brute force? Post by: BooToo on December 15, 2016, 06:47:47 PM Yes clearly, the seed is secure from brut force, at least for a human life, which is long enough in most of cases, (very few peoples need to stock or to spend money after the last day on earth, and for thoses concerned by "heaven", it seems, according to most of it's coming back visitors, that's there is no special need of any currency there ;D )
Title: Re: Are the 12 worded seeds really secure from Brute force? Post by: RodeoX on December 15, 2016, 06:56:36 PM your math probably isn't correct because it is supposed to take until the heat death of the universe even if you use all the computers in the world non-stop ::). you're using just 1000 asics in your example. I thought that time frame was to discover a collision in a bitcoin address? Electrum is much weaker than that because they are using a list of words to create a password. However it is still a large number of possibilities to test. part of that seed mnemonic is actually a checksum so you have to discount that. once you remove the checksum you find it's a 124bit seed. so 2^124 possibilities. This is why a good password should never be a word at all. With something like 60-80k English words in common use it is a relatively small task to test those possibilities. That is a dictionary attack. If instead you used a PW like: %74Fkg#!jkF6l it will require trying every possibility for all characters. That is brute forcing. Title: Re: Are the 12 worded seeds really secure from Brute force? Post by: xhomerx10 on December 15, 2016, 07:05:21 PM Yes clearly, the seed is secure from brut force, at least for a human life, which is long enough in most of cases, (very few peoples need to stock or to spend money after the last day on earth, and for thoses concerned by "heaven", it seems, according to most of it's coming back visitors, that's there is no special need of any currency there ;D ) For those concerned by heaven, faith is the currency of the Kingdom of God and it is a requirement. Not so sure you can "brute force" it though even if given an eternity. Title: Re: Are the 12 worded seeds really secure from Brute force? Post by: btchris on December 15, 2016, 07:26:43 PM Given enough private-key entropy, the weakest link in securing Bitcoin funds is the secp256k1 curve used to sign transactions and generate public keys from private ones, which takes on the order of 2^128 operations to break. Using more than 128 bits of entropy does not help at all. While it's true that Electrum uses slightly less entropy as Abdussamad mentions above (124 bits), practically speaking this is still in the same ball park.
Claiming that Electrum is much weaker than that because they are using a list of words to create a password is flat-out wrong.Title: Re: Are the 12 worded seeds really secure from Brute force? Post by: btchris on December 15, 2016, 08:07:20 PM adaseb,
Your math is more or less within the right order of magnitude, but is missing a few things. First, you need SHA512, not SHA256. Next, for each seed you try, you need to check its "checksum" with HMAC-SHA512, so that's 2x SHA512's, not one. 1 in 256 of the seeds you try will pass the checksum step above, and with these you'll need to run PBKDF2-HMAC-SHA512 with 2048 iterations (and each iteration requires 2x SHA512's) to get the xprv. This means on average, you'll need another 16x SHA512's per seed tried (so your initial estimate was 18x too small). Once you have a potential xprv, you still need to check if it's in use. This means deriving a bunch of private keys from the xprv (let's say we derive 30ish keys on both the internal and external chains, using both BIP32 and BIP44 style paths). Now we're looking at 120+ EC operations per seed which passes the checksum step (on average 1 EC operation for every 2 seeds you initially try). There is also another HMAC-SHA512, SHA256, and RIPEMD operation per address that's generated. Finally, we need a whole bunch of CAM (https://en.wikipedia.org/wiki/Content-addressable_memory)s to look up (in parallel) these addresses in the UTXO set (which has about 43M entries today). I'm not sure how big CAMs get these days, but I can say that a 43M-entry cam is at least 10x or 20x bigger than anything commonly used in networking gear. We can shift some things around a bit (generate fewer private keys/addresses, but search in the every-address-every-used set which is 10x bigger), but it remains a daunting task. Of course, if we have this theoretical hardware mentioned above that can do silly-fast EC operations, it makes a lot more sense to just choose a public key visible on the blockchain which has a large UTXO value and attack it directly (which would take only on the order of 2^128 EC operations). In any case, it seems pretty likely it would take longer than current the age of the universe to succeed--personally I'm not that patient. So yes, "12 worded seeds [are] really secure from Brute force". :) Title: Re: Are the 12 worded seeds really secure from Brute force? Post by: RodeoX on December 15, 2016, 08:10:55 PM Claiming that Actually the way I wrote that is wrong. What I mean is that the pass phrase is weaker than a private key. Electrum is much weaker than that because they are using a list of words to create a password is flat-out wrong.Title: Re: Are the 12 worded seeds really secure from Brute force? Post by: btchris on December 15, 2016, 08:31:59 PM Actually the way I wrote that is wrong. What I mean is that the pass phrase is weaker than a private key. Maybe I'm not understanding you correctly. Surely a human-created pass phrase is very likely to be weaker than a randomly-generated private key, but a sufficiently long randomly-generated pass phrase (such as a seed created by Electrum, assuming a non-broken OS) is not any weaker than any private key. In other words, for a 256-bit EC curve, a seed with 128 bits of entropy which generates a private key with just as much entropy is as strong as a private key with more than 128 bits of entropy since the weakest link is the curve itself (reversing an exponentiation takes on the order of "just" 2^128 EC operations even when the private key has more than 128 bits of entropy). Title: Re: Are the 12 worded seeds really secure from Brute force? Post by: zxcykuaile on December 22, 2016, 10:47:09 AM adaseb, Your math is more or less within the right order of magnitude, but is missing a few things. First, you need SHA512, not SHA256. Next, for each seed you try, you need to check its "checksum" with HMAC-SHA512, so that's 2x SHA512's, not one. 1 in 256 of the seeds you try will pass the checksum step above, and with these you'll need to run PBKDF2-HMAC-SHA512 with 2048 iterations (and each iteration requires 2x SHA512's) to get the xprv. This means on average, you'll need another 16x SHA512's per seed tried (so your initial estimate was 18x too small). Once you have a potential xprv, you still need to check if it's in use. This means deriving a bunch of private keys from the xprv (let's say we derive 30ish keys on both the internal and external chains, using both BIP32 and BIP44 style paths). Now we're looking at 120+ EC operations per seed which passes the checksum step (on average 1 EC operation for every 2 seeds you initially try). There is also another HMAC-SHA512, SHA256, and RIPEMD operation per address that's generated. Finally, we need a whole bunch of CAM (https://en.wikipedia.org/wiki/Content-addressable_memory)s to look up (in parallel) these addresses in the UTXO set (which has about 43M entries today). I'm not sure how big CAMs get these days, but I can say that a 43M-entry cam is at least 10x or 20x bigger than anything commonly used in networking gear. We can shift some things around a bit (generate fewer private keys/addresses, but search in the every-address-every-used set which is 10x bigger), but it remains a daunting task. Of course, if we have this theoretical hardware mentioned above that can do silly-fast EC operations, it makes a lot more sense to just choose a public key visible on the blockchain which has a large UTXO value and attack it directly (which would take only on the order of 2^128 EC operations). In any case, it seems pretty likely it would take longer than current the age of the universe to succeed--personally I'm not that patient. So yes, "12 worded seeds [are] really secure from Brute force". :) Your Explanation is excellent. And I still have one question. Since it has a very little chance to have the same seed, I think it could be used for one UUID variant? Do you have any idea about it? Title: Re: Are the 12 worded seeds really secure from Brute force? Post by: btchris on December 24, 2016, 12:15:36 AM Since it has a very little chance to have the same seed, I think it could be used for one UUID variant? Do you have any idea about it? Do you mean a seed could be used as an alternative for a UUID? I suppose, they both "encode" 128 bits of data minus a checksum (for seeds) or a small header (for UUIDs), except that UUIDs are designed more to be convenient for machines, whereas seeds are for humans. Actually, the "Random UUID probability of duplicates" on Wikipedia (https://en.wikipedia.org/wiki/Universally_unique_identifier#Random_UUID_probability_of_duplicates) is quite relevant for seeds too. Title: Re: Are the 12 worded seeds really secure from Brute force? Post by: jonald_fyookball on December 31, 2016, 04:11:03 AM i'm not sure if this PBKDF2 that was mentioned
is for the new code and replaces this --> but when I was looking at the old version of electrum, it was using a 100,000 round concatenation style key stretching algo, meaning you need 100,000 times as many operations, effectively increasing 128 bit security to beyond 144 bits. Title: Re: Are the 12 worded seeds really secure from Brute force? Post by: Abdussamad on December 31, 2016, 05:13:35 PM i'm not sure if this PBKDF2 that was mentioned is for the new code and replaces this --> but when I was looking at the old version of electrum, it was using a 100,000 round concatenation style key stretching algo, meaning you need 100,000 times as many operations, effectively increasing 128 bit security to beyond 144 bits. Hi Jonald. Good to see you here after a long time. The PBKDF2 thing was introduced with version 2.0: https://github.com/spesmilo/electrum/blob/9285a7198ee1f19571d10453db1b708fc6306e9a/lib/mnemonic.py#L127 This approach was originally proposed by the bip39 standard. Title: Re: Are the 12 worded seeds really secure from Brute force? Post by: jonald_fyookball on January 03, 2017, 02:56:46 AM i'm not sure if this PBKDF2 that was mentioned is for the new code and replaces this --> but when I was looking at the old version of electrum, it was using a 100,000 round concatenation style key stretching algo, meaning you need 100,000 times as many operations, effectively increasing 128 bit security to beyond 144 bits. Hi Jonald. Good to see you here after a long time. The PBKDF2 thing was introduced with version 2.0: https://github.com/spesmilo/electrum/blob/9285a7198ee1f19571d10453db1b708fc6306e9a/lib/mnemonic.py#L127 This approach was originally proposed by the bip39 standard. Thank you my friend. I got bored of the forum but its cool to post once in a while... It's a good time for Bitcoin! Title: Re: Are the 12 worded seeds really secure from Brute force? Post by: btcpepa04 on October 18, 2017, 08:34:08 PM I try to brute force electrum wallet i find some wallet with simple seed like
1_"1b" i find in this wallet 0.7 BTC 2_"above above above above above above above above above above above above " I FIND 1mBTC 3_"ghost ghost ghost ghost" I find in this seeds 0.72 mBTC My priv8 mind to brute force Looool ;D Try my methode Title: Re: Are the 12 worded seeds really secure from Brute force? Post by: userpike0 on March 18, 2018, 06:37:43 PM What if you have 10 of the 12 words in their proper order so you just need the last 2 words in the correct order?
Title: Re: Are the 12 worded seeds really secure from Brute force? Post by: bob123 on March 18, 2018, 06:49:33 PM What if you have 10 of the 12 words in their proper order so you just need the last 2 words in the correct order? With 10 out of 12 words you reduce the possible (theoretical amount of) combinations to 20482 = 4.194.304 Checking this amount is definetely possible in a short amount of time. Considering that the last word 'contains' a checksum, the actual amount of combinations is lower than 4.194.304, making it even easier to bruteforce them. With 10 words exposed you should definetely regard your seed as compromised and switch as soon as possible. Title: Re: Are the 12 worded seeds really secure from Brute force? Post by: userpike0 on March 20, 2018, 08:50:08 PM Well actually, what had happened was.. I somehow only copied 10 of the 12 words down to multiple back ups.. so now I am researching ways to brute force my key to a mobile wallet app.. and of course I don't speak/write code so I can't just produce a cracker. Any suggestions?
Title: Re: Are the 12 worded seeds really secure from Brute force? Post by: bob123 on March 22, 2018, 06:40:17 PM I somehow only copied 10 of the 12 words down to multiple back ups.. so now I am researching ways to brute force my key to a mobile wallet app.. and of course I don't speak/write code so I can't just produce a cracker. Any suggestions? You can bruteforce your seed with btcrecover (https://github.com/gurnec/btcrecover/blob/master/docs/Seedrecover_Quick_Start_Guide.md (https://github.com/gurnec/btcrecover/blob/master/docs/Seedrecover_Quick_Start_Guide.md)). There is a small guide published. It is important to know which wallet you have used with your seed. Depending on the wallet you probably have to set the correct derivation path manually. But it is definetely possible to creack your seed within a short timeframe. But do not disclose your 10 words to anyone! Feel free to ask further questions if you need any help with running the script. Title: Re: Are the 12 worded seeds really secure from Brute force? Post by: userpike0 on May 25, 2018, 03:19:52 AM I have it running now but the only problem I see is that I need it for BCH, not BTC so I wonder if it will work. I tried to put in the new style BCH address but it gave an error. I found the "legacy" address for the BCH address so I used that and it ran. One thing I had to do was add 2 more words to my seed to make the program run. I guess it won't fill in the blanks. lol I'll report back when its finished.
Title: Re: Are the 12 worded seeds really secure from Brute force? Post by: HCP on May 25, 2018, 07:44:24 AM I have it running now but the only problem I see is that I need it for BCH, not BTC so I wonder if it will work. I tried to put in the new style BCH address but it gave an error. I found the "legacy" address for the BCH address so I used that and it ran. One thing I had to do was add 2 more words to my seed to make the program run. I guess it won't fill in the blanks. lol I'll report back when its finished. You shouldn't need to add in 2 words... it should detect that your seed is short and add words as required. The only issue is that by default, I think seedrecover may only look for ONE completely incorrect word :-\Which wallet was your seed from? You might find that the "seedrecover" script will fail to find your correct seed, as it is setup for BTC and ETH... so the derivation path it defaults to is the BIP44 derivation path for BTC which is m/44'/0'/0'/0... unfortunately, you most likely need to use the derivation path: m/44'/145'/0'/0 to find your BCH address. :-\ You can try running it using the --bip32-path parameter to force it to the BCH derivation like this: Code: ./seedrecover.py --bip32-path "m/44'/145'/0'/0/" If you find that it doesn't search for 2 incorrect words, you may or may not also need to add the following argument: --big-typos 2 It will likely generate MILLIONS AND MILLIONS of possible combinations if you use --big-typos 2... as I don't think you can specify where the missing words are. It'll test ALL combinations. I have another possible solution. It's a custom python script that I hacked together that lets you specify the location of missing words like this: Code: python find_missing_seed_word.py sketch hockey elbow property symptom peanut genre bubble popular inherit x x It isn't terribly difficult to use, but it doesn't automatically search the output for possible addresses. It just generates 100 addresses for each valid seed that it can find... and you can then search the files looking for a matching address. Title: Re: Are the 12 worded seeds really secure from Brute force? Post by: Cobalt9317 on June 02, 2018, 12:30:27 AM In short 12 words seeds is unhackable, unbreakable, uncrackable and you can also add a custom words on your seed.
But a password for a privatekey is crackable in practice/theory. Title: Re: Are the 12 worded seeds really secure from Brute force? Post by: adaseb on June 04, 2018, 07:36:21 AM In short 12 words seeds is unhackable, unbreakable, uncrackable and you can also add a custom words on your seed. But a password for a privatekey is crackable in practice/theory. If the password is short then yes, but if its a very long password then most attackers would probably give up. Either way, most people get their BTC stolen because they not only use a weak password but they usually keep their 12 worded seeds written down somewhere on their computer or leave it in their email or cloud storage. Even though there is a warning when you create a BTC electrum wallet to never have those words stored digitally. Title: Re: Are the 12 worded seeds really secure from Brute force? Post by: userpike0 on June 04, 2018, 10:05:19 PM I have it running now but the only problem I see is that I need it for BCH, not BTC so I wonder if it will work. I tried to put in the new style BCH address but it gave an error. I found the "legacy" address for the BCH address so I used that and it ran. One thing I had to do was add 2 more words to my seed to make the program run. I guess it won't fill in the blanks. lol I'll report back when its finished. You shouldn't need to add in 2 words... it should detect that your seed is short and add words as required. The only issue is that by default, I think seedrecover may only look for ONE completely incorrect word :-\Which wallet was your seed from? You might find that the "seedrecover" script will fail to find your correct seed, as it is setup for BTC and ETH... so the derivation path it defaults to is the BIP44 derivation path for BTC which is m/44'/0'/0'/0... unfortunately, you most likely need to use the derivation path: m/44'/145'/0'/0 to find your BCH address. :-\ You can try running it using the --bip32-path parameter to force it to the BCH derivation like this: Code: ./seedrecover.py --bip32-path "m/44'/145'/0'/0/" If you find that it doesn't search for 2 incorrect words, you may or may not also need to add the following argument: --big-typos 2 It will likely generate MILLIONS AND MILLIONS of possible combinations if you use --big-typos 2... as I don't think you can specify where the missing words are. It'll test ALL combinations. I have another possible solution. It's a custom python script that I hacked together that lets you specify the location of missing words like this: Code: python find_missing_seed_word.py sketch hockey elbow property symptom peanut genre bubble popular inherit x x It isn't terribly difficult to use, but it doesn't automatically search the output for possible addresses. It just generates 100 addresses for each valid seed that it can find... and you can then search the files looking for a matching address. Title: Re: Are the 12 worded seeds really secure from Brute force? Post by: userpike0 on June 08, 2018, 02:27:06 AM no go. Even after I put that command in it still asks for which standard and wallet type etc. I have contacted Guarda to ask them what standard they use for the 12 word seed key that is generated before you can use their wallet. I tried the --big-typos 2 also and the cmd window would just close.
There seems to be a checksum checker for the seeds in btcrecover, maybe it could be modified to produce all the 12 word seed keys with correct checksums that would use the partial seed key inputted into the app So ideally it would produce every possible 12 word seed key with a correct checksum only utilizing in my instance the 10 words I gave it to use. Title: Re: Are the 12 worded seeds really secure from Brute force? Post by: HCP on June 08, 2018, 03:29:42 AM So ideally it would produce every possible 12 word seed key with a correct checksum only utilizing in my instance the 10 words I gave it to use. That's pretty much what my script does... it simply checks every combination of words and when it finds valid ones, outputs a text file with 100 receive addresses and 100 change addresses and their private keys... So you end up with hundreds of files like this: https://pastebin.com/WeBPkxjNThis way, you can simply do a search in each file looking for a known address: Code: find . -name "keys_*.txt" | xargs grep 1BdvycQtKNAt89r6nUPtekb45NsR1YTy3o gives: Code: ./keys_7.txt:1BdvycQtKNAt89r6nUPtekb45NsR1YTy3o It isn't anywhere near as polished or user-friendly as the btcrecover and seedrecover scripts... and you'd need to edit the source code to set the derivation path if you want to change it... and it'll probably take quite a while to check all the combinations of 2 missing words and output hundreds of files... but it *should* work. Source code is here: https://pastebin.com/3veBTLFg You run it by passing the "known" seed words... and use an "x" for missing word(s): Code: python find_missing_seed_word.py sketch hockey elbow property symptom peanut genre bubble popular inherit x x Code: python find_missing_seed_word.py sketch hockey elbow x symptom peanut genre bubble popular inherit x adult NOTES: - This script will NOT work if you don't know the position of the missing words - There will probably be some Python library dependencies (like "bitcoin") that you might need to install... use pip - if anyone wants to use this with a derivation path (it is currently set to m/44'/145'/0' for BCH)... you need to change the lines 466-469: Code: #m/44'/145'/0'/0 - Receive For instance, if you wanted to use BTC (m/44'/0'/0') you would need to change to: Quote #m/44'/0'/0'/0 - Receive xprvReceive = bitcoin.bip32_ckd(bitcoin.bip32_ckd(bitcoin.bip32_ckd(bitcoin.bip32_ckd(xprv, 44 + 2**31), 2**31), 2**31), 0) #m/44'/0'/0'/1 - Change xprvChange = bitcoin.bip32_ckd(bitcoin.bip32_ckd(bitcoin.bip32_ckd(bitcoin.bip32_ckd(xprv, 44 + 2**31), 2**31), 2**31), 1) |