Bitcoin Forum
May 26, 2018, 01:13:32 AM
 News: Latest stable version of Bitcoin Core: 0.16.0  [Torrent]. (New!)
 Home Help Search Donate Login Register
 Pages: [1] 2  All
 Author Topic: Are the 12 worded seeds really secure from Brute force?  (Read 1322 times)
Legendary

Offline

Activity: 1610
Merit: 1045

 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.

 .FORTUNE.JACK. ▄▄███████▄▄   ▄████▀▀ ▄ ██████▄  ████ ▄▄███ ████████ █████▌▐███▌ ▀▄ ▀████████████▄██▀▀▀▀▄█████████████▀▄▄▄▄█████████████████▄▄▄▄ ██████████████ ██████▌ ███▀█████████  ███████▄▀▄█████████   ▀█████▀▀████████▀      ▀▀███████▀▀          █         █ ...FortuneJack.com                                              ...THE BIGGEST BITCOIN GAMBLING SITE │ ▄▄█████████▄▄    ▄█████████████████▄  ▄█████████████████████▄ ▄███████████▀███████████▄▄██████████▀   ▀██████████▄█████████▀       ▀█████████████████           ████████████████▄   ▄ ▄   ▄████████▀██████████▀   ▀██████████▀ ▀███████████████████████▀  ▀█████████████████████▀    ▀█████████████████▀       ▀▀█████████▀▀ #JACKMATEWIN 1 BTC │ ▄█████████████████████████▄████████████████████████████████████████████████████████████████▀█████▀█████████████████▀░░▀░░░░░▀░░▀█████████████▌░░░░░░░░░░░░░▐████████████░░░░██░░░██░░░░███████████▌░░░░▀▀░░░▀▀░░░░▐███████████▄░░▄▄▄░░░▄▄▄░░▄██████████████▄▄███████▄▄██████████████████████████████████████████████████████████████▀█████████████████████████▀ │
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1527297212
Hero Member

Offline

Posts: 1527297212

Ignore
 1527297212

1527297212
 Report to moderator
1527297212
Hero Member

Offline

Posts: 1527297212

Ignore
 1527297212

1527297212
 Report to moderator
Legendary

Offline

Activity: 1736
Merit: 1029

 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.

BooToo
Newbie

Offline

Activity: 21
Merit: 0

 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  )
RodeoX
Legendary

Offline

Activity: 2632
Merit: 1039

The revolution will be monetized!

 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.

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.

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.

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.

The gospel according to Satoshi - https://bitcoin.org/bitcoin.pdf

Free bitcoin in AFRICA - https://bitcointalk.org/index.php?topic=2710325.msg27720734
xhomerx10
Legendary

Offline

Activity: 1666
Merit: 1183

 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  )

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.

 HOWEYCOINS ▮      Excitement and         ⭐  ● TWITTER  ● FACEBOOK   ⭐         ▮    guaranteed returns             ⚪    ●TELEGRAM    ⚪                        ▮  of the travel industry    ⭐  ●Ann Thread ●Instagram   ⭐ ✅    U.S.Sec    ➡️✅  approved!  ➡️ PRE-ICO ENDS JULY 1

btchris
Hero Member

Offline

Activity: 672
Merit: 501

a.k.a. gurnec on GitHub

 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.
btchris
Hero Member

Offline

Activity: 672
Merit: 501

a.k.a. gurnec on GitHub

 December 15, 2016, 08:07:20 PM

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 CAMs 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".
RodeoX
Legendary

Offline

Activity: 2632
Merit: 1039

The revolution will be monetized!

 December 15, 2016, 08:10:55 PM

Claiming that
Electrum is much weaker than that because they are using a list of words to create a password
is flat-out wrong.
Actually the way I wrote that is wrong. What I mean is that the pass phrase is weaker than a private key.

The gospel according to Satoshi - https://bitcoin.org/bitcoin.pdf

Free bitcoin in AFRICA - https://bitcointalk.org/index.php?topic=2710325.msg27720734
btchris
Hero Member

Offline

Activity: 672
Merit: 501

a.k.a. gurnec on GitHub

 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).
zxcykuaile
Newbie

Offline

Activity: 1
Merit: 0

 December 22, 2016, 10:47:09 AM

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 CAMs 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?
btchris
Hero Member

Offline

Activity: 672
Merit: 501

a.k.a. gurnec on GitHub

 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 is quite relevant for seeds too.
jonald_fyookball
Legendary

Offline

Activity: 1288
Merit: 1002

Core dev leaves me neg feedback #abuse #political

 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.

Legendary

Offline

Activity: 1736
Merit: 1029

 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.

jonald_fyookball
Legendary

Offline

Activity: 1288
Merit: 1002

Core dev leaves me neg feedback #abuse #political

 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!

btcpepa04
Member

Offline

Activity: 98
Merit: 10

★Jetwin.com★

 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
Try my methode

userpike0
Newbie

Offline

Activity: 21
Merit: 0

 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?
bob123
Sr. Member

Offline

Activity: 574
Merit: 419

 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.

 ░░░░░▄▄██████▄▄░░▄████▀▀▀▀▀▀████▄░███▀░░░░░░░░░░▀█▀████░░░▄██████▄▄░░░██░░░░░█████████░░░░██▌░░░░█████████████████░░░░█████████████████░░░░░███████████████████▄░░▀██████▀░░░████▀█▄▄░░░░░░░░░░▄███░░▀████▄▄▄▄▄▄████▀░░░░░▀▀██████▀▀ .ChipMixer.{ MIXING REINVENTED FOR YOUR PRIVACY #.ChipMixer. ░░░░░▄▄██████▄▄░░▄████▀▀▀▀▀▀████▄░███▀░░░░░░░░░░▀█▀████░░░▄██████▄▄░░░██░░░░░█████████░░░░██▌░░░░█████████████████░░░░█████████████████░░░░░███████████████████▄░░▀██████▀░░░████▀█▄▄░░░░░░░░░░▄███░░▀████▄▄▄▄▄▄████▀░░░░░▀▀██████▀▀
userpike0
Newbie

Offline

Activity: 21
Merit: 0

 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?
bob123
Sr. Member

Offline

Activity: 574
Merit: 419

 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).
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.

 ░░░░░▄▄██████▄▄░░▄████▀▀▀▀▀▀████▄░███▀░░░░░░░░░░▀█▀████░░░▄██████▄▄░░░██░░░░░█████████░░░░██▌░░░░█████████████████░░░░█████████████████░░░░░███████████████████▄░░▀██████▀░░░████▀█▄▄░░░░░░░░░░▄███░░▀████▄▄▄▄▄▄████▀░░░░░▀▀██████▀▀ .ChipMixer.{ MIXING REINVENTED FOR YOUR PRIVACY #.ChipMixer. ░░░░░▄▄██████▄▄░░▄████▀▀▀▀▀▀████▄░███▀░░░░░░░░░░▀█▀████░░░▄██████▄▄░░░██░░░░░█████████░░░░██▌░░░░█████████████████░░░░█████████████████░░░░░███████████████████▄░░▀██████▀░░░████▀█▄▄░░░░░░░░░░▄███░░▀████▄▄▄▄▄▄████▀░░░░░▀▀██████▀▀
userpike0
Newbie

Offline

Activity: 21
Merit: 0

 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.
 Pages: [1] 2  All