Topic: Concerns regarding deterministic wallet (Read 5717 times)

Thanks for the great explanation! I should have realized the clients would do something like this; I use 1Password which does the same with its master password. I still don't think the very occasional security transfer of wallets would hurt, just to easy my paranoia.

You are correct.  They only have to attack your passphrase.  However, Bitcoin-Qt and Armory both use "key-stretching" which is guaranteed to slow down key guessing by a couple orders of magnitude. 

Bitcoin-Qt uses the simplest version -- the password is hashed 25,000+ times to get the encryption key (the exact number is chosen based on your system's speed).  This means that you either try to brute force the encryption key directly (impossible), or you try guessing the passphrase but requires hashing each guess 25,000+ times.  This dramatically slows down an attacker.  But, GPU acceleration is feasible on this, because hashing is so cheap in terms of RAM and simplicity.

Armory uses something more advanced, related to scrypt.  The password isn't just hashed N times, each hash is saved into a lookup table which is then used for another N lookup operations.  This means that they not only have to do the sequential hashing, but each thread that is guessing passwords needs to have N*64 bytes of dedicated RAM to store the lookup table, and that lookup table is specific to the passphrase being guessed (so threads can't share it).  This makes it pretty much useless to apply GPUs, since much of their speed advantage is due to having only a couple kB fast memory per thread, not megabytes.

Armory also tests your system speed to set the parameters to about 0.25sec.  If you use a single CPU on a completely randomized 6-character password, it would take about 500 years for 50% chance to find the password.  Obviously, attackers may have multiple systems/cores to parallelize this, but they have to use CPUs, because of what's mentioned above.  Therefore, if you use approximately 8 characters of real entropy, it's pretty much useless for someone to try, even if they have extraordinary resources.

Of course, people use weak passphrases.  But there's only so much you can do to protect people from themselves...

If someone were to get access to your encrypted wallet file, they would only have to attack your passphrase, correct? Some people could easily have weak passphrases, and then you could get access to the private keys. If deterministic wallets were periodically moved to a new deterministic wallet with a new random seed, this would help to mitigate the threat of offline atttacks.

i think i did see one example of veyr similar address from a determnisitc wallet, lead to being able to get a private key

Plus a lot of other powerful features like watching wallet can be put on webserver allowing site to "know" when deposits are made without exposing the seed or private keys.  This can be done using qt client by setting keypool to zero, generating a large number of keypairs and then exporting only the public keys to the webserver.  However it is "clunky".

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

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.

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.

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

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.

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?

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

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.

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.

 

Will be a long time before the next milestone.

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.

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

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.   

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.

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?