Topic: Why you cannot enter an arbitrary seed in Electrum - page 5. (Read 65082 times)

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.

The randomness ("entropy") of one word, chosen at random from a list of 1600, is simply 1600, and the number of bits in 1600 is 10.644 because 2^10.644=1600.  So in a string of words chosen at random from a list of 1600, each word contributes 10.644 bits of randomness (entropy).  To get 128 bits of entropy you need 128/10.644=12 words.  1600 is a pretty short list, which is why electrum makes such long seeds.
Diceware uses a longer list of 7776 words.  Log2 (7776)=12.925;  128/12.925=9.9.  10 words in diceware would give 129 bits of entropy.
I generated a spreadsheet with about 55,000 words by collecting scrabble lists and pasting them into excel.  More entropy there.  By using random numbers to select words, I can generate a strong passphrase which is short enough that I have some chance of remembering it.  The scrabble list also has some real oddball words.  Makes for a memorable passphrase.  The extremely commonplace vocabulary words in the electrum and diceware lists generate very bland phrases that are not memorable at all, besides just being very long.
Electrum should have gone with a much bigger word list.

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

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.

Diceware 5 words bit strength:

>>> log(7776**5,2)
64.624

Electrum 12 words bit strength:

>>> log(1626**12,2)
128.005

Diceware 5 words bit strength:

>>> log(7776**5,2)
64.624

Electrum 12 words bit strength:

>>> log(1626**12,2)
128.005

What this means: Diceware 5 words is no longer secure. With dictionary size 7776, use at least 7 or 8 words for critical/financial stuff.

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?

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?

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.

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?

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

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

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.

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

Armory