Bitcoin Forum
October 18, 2017, 05:27:06 PM *
News: Latest stable version of Bitcoin Core: 0.15.0.1  [Torrent]. (New!)
 
   Home   Help Search Donate Login Register  
Pages: [1] 2 3 4 5 6 »  All
  Print  
Author Topic: Why you cannot enter an arbitrary seed in Electrum  (Read 55019 times)
ThomasV
Moderator
Legendary
*
Offline Offline

Activity: 1890



View Profile WWW
March 16, 2013, 09:54:41 PM
 #1

Electrum does not let you use an arbitrary sequence of words as seed. This is because humans are not good at generating really random phrases.

The seed generated by Electrum is a 128-bit random number. It is encoded as a sequence of 12 words, for the purpose of memorization. However, it is important to understand that it has 128-bits of entropy. A phrase generated by a human, or picked from a random book opened at a random page, will in general be much less random, and much more vulnerable to attacks. (and "much more" here means astronomically more).

In this type of attack, time is on the side of the attacker. It is perfectly possible for an attacker to try all the phrases existing in a large database of books, and some variants of those, until they find a wallet. In contrast, it is not possible to do the same with 2^128 random phrases.

As you may have noticed, it is possible to bypass this protection; if you restore your wallet from a hexadecimal string, any string length will be accepted. However, this will only work with hexadecimal inputs. Thus, if you absolutely insist on using an arbitrary phrase as seed, you will need to hex-encode it yourself. Consider this as a protection.

Electrum: the convenience of a web wallet, without the risks
1508347626
Hero Member
*
Offline Offline

Posts: 1508347626

View Profile Personal Message (Offline)

Ignore
1508347626
Reply with quote  #2

1508347626
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1508347626
Hero Member
*
Offline Offline

Posts: 1508347626

View Profile Personal Message (Offline)

Ignore
1508347626
Reply with quote  #2

1508347626
Report to moderator
1508347626
Hero Member
*
Offline Offline

Posts: 1508347626

View Profile Personal Message (Offline)

Ignore
1508347626
Reply with quote  #2

1508347626
Report to moderator
1508347626
Hero Member
*
Offline Offline

Posts: 1508347626

View Profile Personal Message (Offline)

Ignore
1508347626
Reply with quote  #2

1508347626
Report to moderator
btcven
Hero Member
*****
Offline Offline

Activity: 717


Bitcoin Venezuela


View Profile WWW
March 16, 2013, 11:55:43 PM
 #2

This is a good post to go to the http://electrum.org FAQs and Tutorials

Admin: rdymac (PGP) | contacto@bitcoinvenezuela.com | @cafebitcoin | Electrum, lightweight bitcoin client
If I've been helpful tip me a coffee! Cheesy1rdymachKZpA9pTYHYHMYZjfjnoBW6B3k Bitrated user: rdymac.
theymos
Administrator
Legendary
*
Offline Offline

Activity: 2814


View Profile
March 18, 2013, 05:02:46 PM
 #3

I agree that it is important to have a random, unguessable passphrase, but 12 random words with 128 bits of entropy is overkill. My passphrase utility allows you to safely use 6 random words.

1NXYoJ5xU91Jp83XfVMHwwTUyZFK64BoAD
ThomasV
Moderator
Legendary
*
Offline Offline

Activity: 1890



View Profile WWW
March 19, 2013, 09:10:16 AM
 #4

I agree that it is important to have a random, unguessable passphrase, but 12 random words with 128 bits of entropy is overkill. My passphrase utility allows you to safely use 6 random words.

We are not talking about an encryption passphrase here. We are talking about the entropy of Bitcoin addresses used by the client.
For this, 128 bits is not overkill. Bitcoin BIP 32 recommends to use at least 128 bits for this: https://en.bitcoin.it/wiki/BIP_0032
As an additional safety measure, Electrum adds a little bit of key stretching to generate the master key (100000 iterations of sha256, which is equivalent to adding a few extra bits of entropy to the seed)


Electrum: the convenience of a web wallet, without the risks
etotheipi
Legendary
*
Offline Offline

Activity: 1428


Core Armory Developer


View Profile WWW
March 19, 2013, 02:34:49 PM
 #5

Electrum does not let you use an arbitrary sequence of words as seed. This is because humans are not good at generating really random phrases.

The seed generated by Electrum is a 128-bit random number. It is encoded as a sequence of 12 words, for the purpose of memorization. However, it is important to understand that it has 128-bits of entropy. A phrase generated by a human, or picked from a random book opened at a random page, will in general be much less random, and much more vulnerable to attacks. (and "much more" here means astronomically more).

In this type of attack, time is on the side of the attacker. It is perfectly possible for an attacker to try all the phrases existing in a large database of books, and some variants of those, until they find a wallet. In contrast, it is not possible to do the same with 2^128 random phrases.

As you may have noticed, it is possible to bypass this protection; if you restore your wallet from a hexadecimal string, any string length will be accepted. However, this will only work with hexadecimal inputs. Thus, if you absolutely insist on using an arbitrary phrase as seed, you will need to hex-encode it yourself. Consider this as a protection.

I approve of this message.  This is why Armory uses a different alphabet, and uses checksums.  Of course checksums are there for checking that data was entered correctly, but it also requires users to manually compute the checksums if they want to enter their own data.  It's a nice protection from people just cramming "aaaaaaaaa..." into the wallet recovery screen.

Of course, Armory uses waaaay more than 128 bits of entropy, but I'll be bringing it down to 128 or 160 in the next release -- I was thinking 160 because I wanted to give a little margin in case your system does not have a high-quality entropy pool at creation time.  This because I totally agree with ThomasV -- 128 bits is a nice, unbreakable value.  Maybe in 1000 years when we have Dyson spheres around a few different stars for the purpose of collecting energy to break my wallet, they might break 128 bits.  

Founder and CEO of Armory Technologies, Inc.
Armory Bitcoin Wallet: Bringing cold storage to the average user!
Only use Armory software signed by the Armory Offline Signing Key (0x98832223)

Please donate to the Armory project by clicking here!    (or donate directly via 1QBDLYTDFHHZAABYSKGKPWKLSXZWCCJQBX -- yes, it's a real address!)
btcven
Hero Member
*****
Offline Offline

Activity: 717


Bitcoin Venezuela


View Profile WWW
March 19, 2013, 10:30:05 PM
 #6

"Can someone with the list of words from the Electrum code get an electrum user's seed trough brute force? How can it be avoided?"

Admin: rdymac (PGP) | contacto@bitcoinvenezuela.com | @cafebitcoin | Electrum, lightweight bitcoin client
If I've been helpful tip me a coffee! Cheesy1rdymachKZpA9pTYHYHMYZjfjnoBW6B3k Bitrated user: rdymac.
ThomasV
Moderator
Legendary
*
Offline Offline

Activity: 1890



View Profile WWW
March 19, 2013, 10:51:53 PM
 #7

"Can someone with the list of words from the Electrum code get an electrum user's seed trough brute force? How can it be avoided?"

The list of words used by Electrum is public; everyone can read it: https://github.com/spesmilo/electrum/blob/master/lib/mnemonic.py
The security of your seed does not reside in a secret algorithm; Electrum is open source, anyone can see how it works.
Security is based on the length of your seed: your seed is safe because it is long enough to make brute force attacks impossible.


Electrum: the convenience of a web wallet, without the risks
btcven
Hero Member
*****
Offline Offline

Activity: 717


Bitcoin Venezuela


View Profile WWW
March 21, 2013, 01:38:03 AM
 #8


Talking about security, guessing and entropy; what are your thoughts about this http://www.nilsschneider.net/2013/01/28/recovering-bitcoin-private-keys.html ?

Admin: rdymac (PGP) | contacto@bitcoinvenezuela.com | @cafebitcoin | Electrum, lightweight bitcoin client
If I've been helpful tip me a coffee! Cheesy1rdymachKZpA9pTYHYHMYZjfjnoBW6B3k Bitrated user: rdymac.
etotheipi
Legendary
*
Offline Offline

Activity: 1428


Core Armory Developer


View Profile WWW
March 21, 2013, 01:42:10 AM
 #9


This is the most basic rule of ECDSA -- use a different random number for each signature.  I'd say that this should be a very difficult mistake to make, but apparently Playstation 3 also had some under-qualified developers in this regard.  

It's nothing new.  It's just the risk of "rolling your own" when dealing with crypto algorithms -- you don't understand the importance of each step, or have any guarantee you did it right.

Even when you think you did it right, you're probably open to things like timing attacks -- where someone gets your system to sign a whole bunch of stuff and collects statistics on the time it took -- which reveals information about the private key.  Proper implementations avoid this.

Founder and CEO of Armory Technologies, Inc.
Armory Bitcoin Wallet: Bringing cold storage to the average user!
Only use Armory software signed by the Armory Offline Signing Key (0x98832223)

Please donate to the Armory project by clicking here!    (or donate directly via 1QBDLYTDFHHZAABYSKGKPWKLSXZWCCJQBX -- yes, it's a real address!)
btcven
Hero Member
*****
Offline Offline

Activity: 717


Bitcoin Venezuela


View Profile WWW
March 21, 2013, 01:49:41 AM
 #10


This is the most basic rule of ECDSA -- use a different random number for each signature.  I'd say that this should be a very difficult mistake to make, but apparently Playstation 3 also had some under-qualified developers in this regard.  

It's nothing new.  It's just the risk of "rolling your own" when dealing with crypto algorithms -- you don't understand the importance of each step, or have any guarantee you did it right.

Even when you think you did it right, you're probably open to things like timing attacks -- where someone gets your system to sign a whole bunch of stuff and collects statistics on the time it took -- which reveals information about the private key.  Proper implementations avoid this.

You answered my question even before I could refresh the page! Good to see it can be avoided taking the right minds to work. It seems that there are still people that don't get it is money what they are playing with.

Admin: rdymac (PGP) | contacto@bitcoinvenezuela.com | @cafebitcoin | Electrum, lightweight bitcoin client
If I've been helpful tip me a coffee! Cheesy1rdymachKZpA9pTYHYHMYZjfjnoBW6B3k Bitrated user: rdymac.
DigitalHermit
Full Member
***
Offline Offline

Activity: 150


Thank you! Thank you! ...


View Profile
March 28, 2013, 12:27:25 PM
 #11

I know a 128-bit seed is good enough to defeat brute force attacks, but then wouldn't it be even better to support a 256-bit seed? Any thoughts on allowing that option?
Abdussamad
Legendary
*
Offline Offline

Activity: 1526



View Profile WWW
April 18, 2013, 11:31:57 PM
 #12

I understand that the seed in number form is 128bits of entropy. But is the mnemonic 128 bits too? 12 words out of 1600 are 128bits of entropy? Just curious.

RoxxR
Full Member
***
Offline Offline

Activity: 178


View Profile
April 19, 2013, 08:38:45 AM
 #13

I understand that the seed in number form is 128bits of entropy. But is the mnemonic 128 bits too? 12 words out of 1600 are 128bits of entropy? Just curious.

Yes. As long as they are *randomly* chosen.
xanatos
Jr. Member
*
Offline Offline

Activity: 41


View Profile
April 22, 2013, 10:17:18 AM
 #14

Quote
Of course, Armory uses waaaay more than 128 bits of entropy, but I'll be bringing it down to 128 or 160 in the next release -- I was thinking 160 because I wanted to give a little margin in case your system does not have a high-quality entropy pool at creation time.  This because I totally agree with ThomasV -- 128 bits is a nice, unbreakable value.  Maybe in 1000 years when we have Dyson spheres around a few different stars for the purpose of collecting energy to break my wallet, they might break 128 bits.  

I hope you where exaggerating. 128 bits encryption could be breaked "routinely" in 100 years. Armchair explanation: DES at 56 bits can be breaked "routinely" by NSA/CIA ecc. If Moore's Law is sustainable the number of transistors in a chip will double every 1.5 years. Let's say that every doubling in number of transistors double the speed (because, in the end, cracking a code is a highly parallelizable task, so doubling the number of processors WILL double the speed). So each 1.5 years the number of bits that can be cracked "routinely" is raised by 1 (double speed = +1 bits, because +1 bit doubles the keyspace)... So 72 * 1.5 = 108 years... But note that DES was cracked "routinely" some years ago.

(read for example here. http://en.wikipedia.org/wiki/EFF_DES_cracker , in 1998 EFF brute-force cracked DES in 56 hours for 250,000$. So if Moore Law is sustainable, in 2106 AES128 could be cracked in 56 hours, but note that some years before a resolute cracker with some million $ and a month of time could probably crack it)
Tungsten
Member
**
Offline Offline

Activity: 73



View Profile WWW
April 23, 2013, 08:24:26 PM
 #15

Well, technically you can:
  • Run electrum with parameter: -w fun.bin (to generate new custom wallet named fun.bin)
  • Select [Restore]
  • Enter word "god" 12 times Smiley (or any combination of words from electrum dictionary)
  • You got your own fully functional, funny-seeded and hence very insecure, likely to be cracked by someone wallet Smiley

Gleb

• 188888888qZ5Mv4u5C2Bve6eyVJBFR5EEj • Get personalized bitcoin address like that at http://vanitycoin.com/
Tuxavant
Hero Member
*****
Offline Offline

Activity: 784

Bitcoin Mayor of Las Vegas


View Profile WWW
April 30, 2013, 04:33:47 PM
 #16

Whoops, I was under the impression assumed that Electrum was using RFC 1751 for translating bits to words...

http://tools.ietf.org/html/rfc1751

Can I ask what the reason for not using it and going with a poetry frequency list instead?

Tuxavant
Hero Member
*****
Offline Offline

Activity: 784

Bitcoin Mayor of Las Vegas


View Profile WWW
May 16, 2013, 12:24:01 PM
 #17

From Thomas...

Quote
The main reason is that the encoding method used in RFC1751 collides with patent US5892470 A.
My personal opinion is of course that this patent is ridiculous and should never have been granted.
However, I did not want to take any risk, because if the site hosting the source code (github, gitorious)
receives a cease and desist letter, they will remove the project rather than hire a lawyer to defend the
case. And if someone decided to target Bitcoin software in general, this patent gives them a reason to
attack Electrum.
 
In order to circumvent that patent, I used a different encoding algorithm and a different dictionary.
Of course I could have changed only the encoding algorithm and kept the same dictionary, but that
would have been a terrible idea, because it means Electrum would have generated RFC 1751 valid
passphrases, but decodes these phrases differently. This would definitely have been considered as a bug.
 
Another reason not to use the same dictionary as in the RFC is that it contains mostly short words,
which are not good for long-term memorization. People often believe that short words are easier to
remember, because they confuse short-term and long-term memory. STM and LTM are separate functions,
that are performed in anatomically distinct parts of the brain (hippocampus and cortex, respectively).
It is true that sequences of short words are easier to store and recall in short term memory (Baddeley
et al 1975), but that does not make them good candidates for long term memory storage. In order
to store a list of words in long term memory, these words must be both familiar and salient (not too
common and with some semantic or emotional load). Another good thing that boosts memory is to
have words from different categories (eg verbs and nouns), as explained in this paper:
http://csjarchive.cogsci.rpi.edu/proceedings/2008/pdfs/p2183.pdf
 
This is why I used words from a poetry list found on Wikimedia; this list contained words that were both
familiar and salient. Starting from this list, I first removed words that I found too short or too common,
and verbs that were conjugated with different tenses. (I also removed nsfw words such as "fuck" and "shit",
although I realize I forgot a few of them). After that, I still had more words than needed, so I ran an
optimization algorithm, in order to select the subset with maximal average Hamming distance between words.
 
cheers
 
Thomas

minerpumpkin
Hero Member
*****
Offline Offline

Activity: 672


A pumpkin mines 27 hours a night


View Profile
January 14, 2014, 10:19:07 AM
 #18

What are your thoughts on this: http://www.sendspace.com/file/68tgbd
You have to roll your own seed. 5 dice for each word = 60 rolls, if a roll is invalid (i.e. under certain circumstances not applicable), roll again. IMO this should lead to a truly random seed, which can't be compromised by faulty or limited random number generators implementations. It's a bit cumbersome, but for long-term storage a decent decision.

Any downsides or potential risks I don't see?

██████████████████████████████████████████████
██████████████████████████████████████████████
█████                                    █████
█████                                    █████
█████                                    █████
█████           ▄█▄        ▄█▄           █████
█████          ████████████████          █████
█████           ▀████████████▀           █████
█████           ████▀    ▀████           █████
█████           ████▄    ▄████           █████
█████           ▄████████████▄           █████
█████          ████████████████          █████
█████           ▀█▀        ▀█▀           █████
█████                                    █████
█████                                    █████
█████                                    █████
██████████████████████████████████████████████
██████████████████████████████████████████████
▄██████████████████████████▄
██                        ██
██                        ██
██                        ██
██             ▄█▀███████████
██              ▀▀▀▀▀▀▀▀▀▀██▀
██                        ██
██                        ██
██▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄██
 ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀

▄██████████████████████████▄
██                        ██
██                        ██
██                        ██
██                        ██
████████████████████████████
██                        ██
██                        ██
██▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄██
 ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀
▄██████████████████████████▄
██                 ▄███▀  ██
██             ▄▄██▀▀  ▄█ ██
██     ▄    ▄███▀▀  ▄███  ██
██    ██▄▄██▀▀   ▄█████   ██
██   ████▀▀  ▄▄██▀▀ ▀█    ██
██  █▀▀   ▄▄██▀           ██
██    ▄▄███▀              ██
██▄▄▄████▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄██
 ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀

▄██████████████████████████▄
██                        ██
██  ████▄  ▄▄▄▄▄▄▄▄▄▄▄▄   ██
██     ▀█▄ ▀▀▀▀▀▀▀▀▀██    ██
██      ██         ██     ██
██       ███████████      ██
██        ▄▄     ▄▄       ██
██       ▀██▀   ▀██▀      ██
██▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄██
 ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀
▄██████████████████████████▄
██                       ▄██
██                     █████
██         ▄         ███▀ ██
██       ▄███     ▄███▀   ██
██   ▄▄███▀▀███▄████▀     ██
██▄▄███▀     ▀███▀        ██
████▀                     ██
██▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄██
 ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀

▄███████████▄  ██████████████
█           █  █            █
█           █  █            █
█           █  █            █
█           █  █            █
█           █  █            █
█           █  █            █
█           █  █            █
██████▀██████  ██████▀███████
 ▀▀▀▀▀▀▀▀▀▀▀   ▀▀▀▀▀▀▀▀▀▀▀▀▀▀
manicminer
Sr. Member
****
Offline Offline

Activity: 302



View Profile
January 23, 2014, 03:22:38 PM
 #19

What are your thoughts on this: http://www.sendspace.com/file/68tgbd
You have to roll your own seed. 5 dice for each word = 60 rolls, if a roll is invalid (i.e. under certain circumstances not applicable), roll again. IMO this should lead to a truly random seed, which can't be compromised by faulty or limited random number generators implementations. It's a bit cumbersome, but for long-term storage a decent decision.

Any downsides or potential risks I don't see?

This method is well known as Diceware - http://world.std.com/~reinhold/diceware.html

Good question! How Diceware (5 words with dice, dictionary size of 7776) compares to Electrum (12 words, from a dictionary of 1600) for practical purposes; to use as your master password?
manicminer
Sr. Member
****
Offline Offline

Activity: 302



View Profile
January 23, 2014, 03:26:43 PM
 #20

As you may have noticed, it is possible to bypass this protection; if you restore your wallet from a hexadecimal string, any string length will be accepted. However, this will only work with hexadecimal inputs. Thus, if you absolutely insist on using an arbitrary phrase as seed, you will need to hex-encode it yourself. Consider this as a protection.
I am not a cryptographer (what are some good sources to learn some very basic concepts? Maybe one good article for noobs), so this is a basic question: let's say I used my own passphrase and I am happy with it, my passphrase is (obviously)

the quick brown fox jumps over the lazy dog

then how do I hex-encode it to become an Electrum seed?

and just for fun, can I also convert it for Electrum style 12 words?
Pages: [1] 2 3 4 5 6 »  All
  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!