Bitcoin Forum
December 17, 2017, 08:32:09 PM *
News: Latest stable version of Bitcoin Core: 0.15.1  [Torrent].
 
   Home   Help Search Donate Login Register  
Pages: [1]
  Print  
Author Topic: Are the 12 worded seeds really secure from Brute force?  (Read 1167 times)
adaseb
Legendary
*
Offline Offline

Activity: 1442



View Profile
December 15, 2016, 11:12:41 AM
 #1

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.

FORTUNEJACK.COM[
                            
5 BTC WELCOME PACK FOR 1ST 5 DEPOSITS
FREE 1,000 mBTC daily for LuckyJack winners
[
          
]
1513542729
Hero Member
*
Offline Offline

Posts: 1513542729

View Profile Personal Message (Offline)

Ignore
1513542729
Reply with quote  #2

1513542729
Report to moderator
1513542729
Hero Member
*
Offline Offline

Posts: 1513542729

View Profile Personal Message (Offline)

Ignore
1513542729
Reply with quote  #2

1513542729
Report to moderator
1513542729
Hero Member
*
Offline Offline

Posts: 1513542729

View Profile Personal Message (Offline)

Ignore
1513542729
Reply with quote  #2

1513542729
Report to moderator
"Apparently, so I am told, there exist "people" who prefer to wipe sitting down. From the front. Initial research indicates it could be up to half the population." -- benjamindees
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1513542729
Hero Member
*
Offline Offline

Posts: 1513542729

View Profile Personal Message (Offline)

Ignore
1513542729
Reply with quote  #2

1513542729
Report to moderator
1513542729
Hero Member
*
Offline Offline

Posts: 1513542729

View Profile Personal Message (Offline)

Ignore
1513542729
Reply with quote  #2

1513542729
Report to moderator
Abdussamad
Legendary
*
Offline Offline

Activity: 1582



View Profile WWW
December 15, 2016, 01:11:38 PM
 #2

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  Roll Eyes. 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 Offline

Activity: 21


View Profile
December 15, 2016, 06:47:47 PM
 #3

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  Grin )
RodeoX
Legendary
*
Offline Offline

Activity: 2478


The revolution will be monetized!


View Profile
December 15, 2016, 06:56:36 PM
 #4

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  Roll Eyes. 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 ICELAND - https://bitcointalk.org/index.php?topic=1610684
xhomerx10
Legendary
*
Offline Offline

Activity: 1498



View Profile
December 15, 2016, 07:05:21 PM
 #5

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

 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.


Don't let sidehack fade away...【ツ】Buy him a burger!   1BURGERAXHH6Yi6LRybRJK7ybEm5m5HwTr
btchris
Hero Member
*****
Offline Offline

Activity: 672

a.k.a. gurnec on GitHub


View Profile WWW
December 15, 2016, 07:26:43 PM
 #6

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 Offline

Activity: 672

a.k.a. gurnec on GitHub


View Profile WWW
December 15, 2016, 08:07:20 PM
 #7

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 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". Smiley
RodeoX
Legendary
*
Offline Offline

Activity: 2478


The revolution will be monetized!


View Profile
December 15, 2016, 08:10:55 PM
 #8

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 ICELAND - https://bitcointalk.org/index.php?topic=1610684
btchris
Hero Member
*****
Offline Offline

Activity: 672

a.k.a. gurnec on GitHub


View Profile WWW
December 15, 2016, 08:31:59 PM
 #9

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 Offline

Activity: 1


View Profile
December 22, 2016, 10:47:09 AM
 #10

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 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". Smiley


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 Offline

Activity: 672

a.k.a. gurnec on GitHub


View Profile WWW
December 24, 2016, 12:15:36 AM
 #11

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 Offline

Activity: 1260


Core dev leaves me neg feedback #abuse #political


View Profile
December 31, 2016, 04:11:03 AM
 #12

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.

Abdussamad
Legendary
*
Offline Offline

Activity: 1582



View Profile WWW
December 31, 2016, 05:13:35 PM
 #13

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 Offline

Activity: 1260


Core dev leaves me neg feedback #abuse #political


View Profile
January 03, 2017, 02:56:46 AM
 #14

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 Offline

Activity: 70

★Jetwin.com★


View Profile
October 18, 2017, 08:34:08 PM
 #15

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

Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!