Concerns regarding deterministic wallet

[DivineOmega]

I asked the following in the #electrum IRC channel on Freenode recently, but sadly got not response.

<DivineOmega> Hi all. I'm considering using Electrum to store a large number of Bitcoins, but the deterministic wallet concerns me a bit.
<DivineOmega> I'm under the impression the completely random address generation of Bitcoin-QT is more secure, as a potentially attacker would need to guess every private key to spend your entire wallet.
<DivineOmega> While with Electrum only one secret (the seed) is required to spend the entire wallet
<DivineOmega> Am I correct here or am I completely missing something?
<DivineOmega> I really want to use Electrum, as I have an old netbook with very little storage that is struggling to hold the entire blockchain (< 900 MB remaining) and struggling dealing with Bitcoin-QT's IO requirements.
<DivineOmega> I really want to know if my concerns regarding deterministic wallets are valid.
<DivineOmega> Also, I suppose I should ask if Electrum can be used without a deterministic wallet?

What are everyone's thoughts?

[1714990314]

1714990314

[1714990314]

1714990314

[1714990314]

1714990314

[1714990314]

1714990314

[1714990314]

1714990314

[DeathAndTaxes]

Nobody tries to "guess" a private key.  Brute forcing private keys is for all intents and purposes infeasible.  256bit is a large number (likely a quadrillion, quadrillion times times larger than you "think" it is).

These numbers have nothing to do with the technology of the devices; they are the maximums that thermodynamics will allow. And they strongly imply that brute-force attacks against 256-bit keys will be infeasible until computers are built from something other than matter and occupy something other than space.

http://www.schneier.com/blog/archives/2009/09/the_doghouse_cr.html

Unless you are worried about attackers building computers from something other than matter and existing in something other than space the attack vector isn't to "guess" your private key/seed it is to GAIN ACCESS to your private key/seed.


Your coins will be stolen if the attacker GAINS ACCESS TO the private keys.  For unencypted wallets this means access to the wallet file.  For encyrpted wallets this means the wallet file and the passphrase.  If the passphrase is weak the attacker may be able to brute force it.  There is no likely scenario where an attacker would gain access to only some but not all of the random private keys but would gain access to the seed and thus all private keys.

Deterministic or random once the attacker has the decrypted wallet file, you should assume your funds will be lost.  It is your job to ensure the attacker never gains access to the wallet (deterministic or random).

Now if you employ a second wallet (say offline "cold storage") it should use keys which are unrelated to the first wallet.  This applies regardless of if you use a random or deterministic wallet.

[Pieter Wuille]

If an attacker needs to guess a key, there is nothing to worry about. The keyspace is way too large for that.

If an attacker has access to your wallet/backup/passphrase/... in a way that grants him access to one of the keys, he very likely has access to all keys.

There is one small security difference between deterministic and randomly-generated wallet keys: if someone manages to copy the keys from the second, he cannot wait (long) before stealing, as the coins tend to move to newer addresses (i.e., it becomes "unstolen" over time).

Also, there are plans to implement deterministic wallets for the reference client too, as the advantages for backup safety far outweigh the security risks.

[etotheipi]

If an attacker needs to guess a key, there is nothing to worry about. The keyspace is way too large for that.

If an attacker has access to your wallet/backup/passphrase/... in a way that grants him access to one of the keys, he very likely has access to all keys.

There is one small security difference between deterministic and randomly-generated wallet keys: if someone manages to copy the keys from the second, he cannot wait (long) before stealing, as the coins tend to move to newer addresses (i.e., it becomes "unstolen" over time).

Also, there are plans to implement deterministic wallets for the reference client too, as the advantages for backup safety far outweigh the security risks.

Also, I would argue that that even the "unstealing" aspect of random wallets is irrelevant.  If someone has access to your unencrypted wallet, they can fill your keypool with more addresses than you'd ever use, then copy your private keys.

Therefore, there really isn't a downside to deterministic wallets.  The upside is phenomenal, though. Armory users rave about being able to do one-time backups and never have to worry about it again.  It also makes securing your backup easier, since it doesn't have to be easily replaceable.  Secure it hardc0re, once.  Then leave it alone for the next 3 years until you need it.

[DeathAndTaxes]

Also, there are plans to implement deterministic wallets for the reference client too, as the advantages for backup safety far outweigh the security risks.

This is a very good point.  A non trivial number of coins have been collectively lost over the years due to the "gotchas" inherent in a RBOK (random bunch of keys) wallet.

Just some examples:
a) failing to make a backup
b) failing to keep backup current and exhausting the keypool
c) forgetting or losing passphrase and not having a paper backup
d) encrypting a wallet and not making a new backup (encrypting results in keypool being flushed and old backups out of date)

[DivineOmega]

Nobody tries to "guess" a private key.  Brute forcing private keys is for all intents and purposes infeasible.  256bit is a large number (likely a quadrillion to the quadrillionth times larger than you "think" it is).

These numbers have nothing to do with the technology of the devices; they are the maximums that thermodynamics will allow. And they strongly imply that brute-force attacks against 256-bit keys will be infeasible until computers are built from something other than matter and occupy something other than space.

http://www.schneier.com/blog/archives/2009/09/the_doghouse_cr.html

Unless you are worried about attackers building computers from something other than matter and existing in something other than space the attack vector isn't to "guess" your private key/seed it is to GAIN ACCESS to your private key/seed.

...

Thanks for your detailed response.

Electrum seeds are 128 bit (http://electrum.org/seed.html), which makes them easier to brute force. If one is successfully brute forced, this surely yields a larger 'reward' for a the attacker than just brute forcing private keys directly, as it allows the attacker the reconstruct all private keys in the seeded deterministic wallet.

Assuming I'm correct here, why would the decision to make the seed for an algorithm that generates multiple private keys only 128 bit, while the private keys themselves are 256 bit?

[etotheipi]

Thanks for your detailed response.

Electrum seeds are 128 bit (http://electrum.org/seed.html), which makes them easier to brute force. If one is successfully brute forced, this surely yields a larger 'reward' for a the attacker than just brute forcing private keys directly, as it allows the attacker the reconstruct all private keys in the seeded deterministic wallet.

Assuming I'm correct here, why would the decision for to make the seed for an algorithm that generates multiple private keys only 128 bit, while the private keys themselves are 256 bit?

128 bits is more than sufficient.  There's a reason it was chosen.

Consider that the entire bitcoin network, over the course of the last 4.5 years, has "only" produced about 2⁶⁹ hashes.  You'd have to do about 500 quintillion times that amount of work to have a 50% chance to brute-force a single 128-bit seed.  It's just not feasible.

[DeathAndTaxes]

I am unsure of the reason my guess is that 128 bit seed makes printing or memorizing an paper backup easier.  Would be nice if the wallet had a user defined seed size.

Still I would have no concerns about a 128bit random key.  The effective key strength of 256 bit ECDSA keypairs (the difficulty in finding a private key given a 256 bit ECDSA public key) is 128 bits.

128 bits while not "beyond the thermodynamic limit" is considers but pretty much all cryptographic experts to be beyond what is feasible to brute force (and yes that includes the effect of Moore's law in our lifetime).  AES-128 has been designated sufficient to safeguard classified material by NIST.  NIST sets cryptography standards for US agencies.


Yes the private keys (for actual bitcoin addresses) are always 256 bits. That is part of the protocol spec and thus not a decision for client developer.  However as indicated above ECDSA 256 bit only has 128 bits of preimage resistance anyways.   

[Pieter Wuille]

Consider that the entire bitcoin network, over the course of the last 4.5 years, has "only" produced about 2⁶⁹ hashes.

Tomorrow we're crossing 2⁷⁰, by the way

[DivineOmega]

Thanks for your detailed response.

Electrum seeds are 128 bit (http://electrum.org/seed.html), which makes them easier to brute force. If one is successfully brute forced, this surely yields a larger 'reward' for a the attacker than just brute forcing private keys directly, as it allows the attacker the reconstruct all private keys in the seeded deterministic wallet.

Assuming I'm correct here, why would the decision for to make the seed for an algorithm that generates multiple private keys only 128 bit, while the private keys themselves are 256 bit?

128 bits is more than sufficient.  There's a reason it was chosen.

Consider that the entire bitcoin network, over the course of the last 4.5 years, has "only" produced about 2⁶⁹ hashes.  You'd have to do about 500 quintillion times that amount of work to have a 50% chance to brute-force a single 128-bit seed.  It's just not feasible.

If that is indeed the case, then perhaps I am just being overly paranoid. Maybe it is the simplification of Electrum's seed (specifically its representations as only a few words) that makes it seem that it could be much more easily brute forced than these calculations suggest.

[DeathAndTaxes]

Consider that the entire bitcoin network, over the course of the last 4.5 years, has "only" produced about 2⁶⁹ hashes.

Tomorrow we're crossing 2⁷⁰, by the way

Will be a long time before the next milestone.

[DeathAndTaxes]

If that is indeed the case, then perhaps I am just being overly paranoid. Maybe it is the simplification of Electrum's seed (specifically its representations as only a few words) that makes it seem that it could be much more easily brute forced than these calculations suggest.

Think of the words as larger numbers.

Imagine a combination lock (like on a bike) with digits 0 to 9. 
How many possible combinations are there if the lock has two digits?  10^2 = 100. 
How many possible combinations are there if the lock has three digits?  10^3 = 1,000.
How many possible combinations are there if the lock has four digits?  10^4 = 10,000.
How many possible combinations are there if the lock has five digits?  10^5 = 100,000.

128 bit = 2^128 ~= 10^38

So you could write a random key as 128 binary digits or 38 decimal digits.  Either one is just as strong.
However you notice the larger the numerator (10 vs 2) the smaller the exponent needed for equivalent security (38 vs 128).

So what is we used a much larger number .... we would need less digits.  Right? 

Electrum's words are a set of 1626.  If you prefer think of them as numbers

1= hello
2= dog
....
1626 = xray
(note this isn't actual word list)

1626^12 ~= 10^38

128 bit = 2^128 = 10^38 = 1626^12 = x^y (where there are an infinite number of x & y values possible)

How you choose to represent it doesn't change the entropy of the value anymore than representing 123 as the words "one hundred and twenty three" makes it any more or less secure of a 3 digit decimal combination.

 

[niniyo]

Nobody tries to "guess" a private key.  Brute forcing private keys is for all intents and purposes infeasible.  256bit is a large number (likely a quadrillion to the quadrillionth times larger than you "think" it is).

It's way way smaller than that.  Accordingly to wolfram alpha, (10^15)^(10^15) is more than 10 quadrillion decimal digits long.  You couldn't write that number on paper if you spent your whole lifetime trying.  2^256 can be written with only 76 decimal digits, so I could write that down on paper in less than a minute.

[DeathAndTaxes]

Sorry typo was trying to say a quadrillion quadrillion (i.e 10^15 * 10^15).  Still the point is that 2^256 is "big".  Deceptively big since for example we have 64 bit computers and some people even have 32 bit dollars (~$4.3 billion USD) so at a "common sense" level it doesn't seem like the jump to 128 bit or 256 is "that much more".

[DivineOmega]

Also, there are plans to implement deterministic wallets for the reference client too, as the advantages for backup safety far outweigh the security risks.

That's very encouraging. Do you have a rough time-scale for this and/or knowledge of what priority this is for Bitcoin-QT's development?

[DublinBrian]

<DivineOmega> Hi all. I'm considering using Electrum to store a large number of Bitcoins, but the deterministic wallet concerns me a bit.
<DivineOmega> I'm under the impression the completely random address generation of Bitcoin-QT is more secure, as a potentially attacker would need to guess every private key to spend your entire wallet.
<DivineOmega> While with Electrum only one secret (the seed) is required to spend the entire wallet
<DivineOmega> Am I correct here or am I completely missing something?
<DivineOmega> I really want to use Electrum, as I have an old netbook with very little storage that is struggling to hold the entire blockchain (< 900 MB remaining) and struggling dealing with Bitcoin-QT's IO requirements.
<DivineOmega> I really want to know if my concerns regarding deterministic wallets are valid.
<DivineOmega> Also, I suppose I should ask if Electrum can be used without a deterministic wallet?

You can use Electrum without any risk even if your seed is captured by a hacker. The seed doesnt give access to imported keys.

Generate some new keys using the javascript available on bitaddress.org and then import them into Electrum.

[yokosan]

Consider that the entire bitcoin network, over the course of the last 4.5 years, has "only" produced about 2⁶⁹ hashes.

Tomorrow we're crossing 2⁷⁰, by the way

Will be a long time before the next milestone.

I'm guessing 2.5 years accounting for an ever increasing userbase.

[zomnut]

<DivineOmega> Hi all. I'm considering using Electrum to store a large number of Bitcoins, but the deterministic wallet concerns me a bit.
<DivineOmega> I'm under the impression the completely random address generation of Bitcoin-QT is more secure, as a potentially attacker would need to guess every private key to spend your entire wallet.
<DivineOmega> While with Electrum only one secret (the seed) is required to spend the entire wallet
<DivineOmega> Am I correct here or am I completely missing something?
<DivineOmega> I really want to use Electrum, as I have an old netbook with very little storage that is struggling to hold the entire blockchain (< 900 MB remaining) and struggling dealing with Bitcoin-QT's IO requirements.
<DivineOmega> I really want to know if my concerns regarding deterministic wallets are valid.
<DivineOmega> Also, I suppose I should ask if Electrum can be used without a deterministic wallet?

You can use Electrum without any risk even if your seed is captured by a hacker. The seed doesnt give access to imported keys.

Generate some new keys using the javascript available on bitaddress.org and then import them into Electrum.

Importing keys into Electrum eliminates the concerns regarding a deterministic wallet by eliminating the deterministic wallet. You lose any benefit the deterministic wallet could offer and are left with a "random address" wallet.

[iddo]

Would be nice if the wallet had a user defined seed size.

Yes it would be nice, with BIP32 the seed size should be between 128 bits and 512 bits. More than 512 bits of entropy wouldn't make sense, because the seed derives the privkey+chaincode of the root node, which are 256+256=512 bits.


An additional secuirty advantage of deterministic wallets that wasn't mentioned here is that the user can generate new receiving addresses without providing his AES passphrase to decrypt/encrypt his wallet, by using type-2 key homomorphism. This means that the user would need to decrypt his privkeys only when he wishes to spend coins.

[etotheipi]

An additional secuirty advantage of deterministic wallets that wasn't mentioned here is that the user can generate new receiving addresses without providing his AES passphrase to decrypt/encrypt his wallet, by using type-2 key homomorphism. This means that the user would need to decrypt his privkeys only when he wishes to spend coins.

That's exactly how Armory wallets work, right now.