But as long as there is no mathematical proof that such attack is impossible, I do not feel entirely comfortable with deterministic keys
You might have bigger problems then since ecdsa is also only assumed to be secure.Electrum is a brain wallet.
Topic: [ANNOUNCE] Electrum - Lightweight Bitcoin Client - page 48. (Read 274562 times)
Electrum is a brain wallet.
But as long as there is no mathematical proof that such attack is impossible, I do not feel entirely comfortable with deterministic keys
You might have bigger problems then since ecdsa is also only assumed to be secure.
But as long as there is no mathematical proof that such attack is impossible, I do not feel entirely comfortable with deterministic keys
You might have bigger problems then since ecdsa is also only assumed to be secure.I think he's referring to Elliptic Curve Digital Signature Algorithm, not the Electrum server at ecdsa.org. Bitcoin keypairs, including deterministic keys, are created with ECDSA. Like most public key cryptosystems, it is never impossible to carry out an attack; it is only extremely impractical. That's (probably) why vuce is saying ECDSA is only assumed to be secure. If you need complete mathematical certainty of impossibility, there's bigger problems than just deterministic wallets.
But as long as there is no mathematical proof that such attack is impossible, I do not feel entirely comfortable with deterministic keys
You might have bigger problems then since ecdsa is also only assumed to be secure.
I know that it's not easy, I'm concerned that it's possible. It takes government level cryptologists to reverse a twice used one-time-pad, but it can be done. And deterministic wallets are not standard at all. As far as I know, Electrum & Brainwallet are the only two examples of it in use in Bitcoin, and Brainwallet seems to use Electrum code to do it, so the methods are identical.
The amazing benefits and security of type-2 determinstic wallets has been discussed at length in several previous threads.
In fact, Electrum is not alone: Armory also chose to use deterministic wallets, and MultiBit and Bitcoin-Qt both plan to implement them as well.
I'm concerned about a particular attack vector. If you happen to have a link to show me, that would be helpful, but I am already aware of the several advantages of deterministic wallets. I would like to see one of the crypto-geeks (better than I) assess this particular risk. I can't really do it because I'm not very good at looking at the code and knowing what I'm looking at.
Here is what seems to be the mother of deterministic wallet threads which was initiated by gmaxwell https://bitcointalksearch.org/topic/deterministic-wallets-19137
Further along the thread JoelKatz gave a reply which touched your concern.
Excuse me if I'm being a noob, but as I understand this system, it's basically generating many keys in a deterministic way from a single backed-up seed. Doesn't this make it possible for anyone with multiple public keys generated from the same seed to do some sort of correlation attack and discover the seed?
No. Because it's the secret keys that are correlated and an attacker would only have the public keys.Even if he did have some secret keys, it wouldn't matter. This attack would be possible in theory but impossible in practice because the scheme is specifically designed to make it impractical. (It's not particularly hard to do that. Both schemes proposed use well-known methods to prevent this even if an attacker had some private keys somehow.)
Of course, if the seed gets out, all future keys are compromised.
He made another relevant comment.
I am wondering the same thing: if the wallet is deterministic and you publish several public keys shouldn't it be possible to calculate the original private key? Especially regarding merchants, restaurants and such who most likely will publish a lot of keys. The more keys published the easier it should get to find the private key!
Or am I missing something?
No, you are correct. But it doesn't matter. Here "easier" means that if you dedicated every computer on the planet to breaking a key, it might take a few dozen centuries rather than a few hundred centuries. In fact, the system is so strong, even if you released the master public key, allowing an attacker to generate as many related public keys as he wanted, it would still be impossible (for practical purposes) for him to compromise a single private key. (In fact, this scheme was originally developed with the idea of using it exactly that way.)Or am I missing something?
This is the interesting thing about public key cryptography. Attacks are always possible. Every conceivable compromise is doable in principle. So you can't just check if an attack is theoretically possible, you have to ask if it is practical.
At the end of the thread iddo even demonstrated the soundness of the crypto behind deterministic wallets.
I'd like to add to this thread the simple explanation why the crypto behind deterministic wallets is sound, i.e. why it's safe to assume that an attacker who only looks at public data (that's sent over the bitcoin network and stored in the blockchain) doesn't have an advantage if the participants use deterministic wallets instead of the regular random-independent wallets. As discussed here, obviously if an attacker obtains the master private key and random seed then he can generate new keys, unlike the case of random-independent wallets, but the focus here is about an attack without access to the secret data.
Since with type-2 deterministic wallet the public keys are generated independently of the master private key, using key homomorphism, it's enough to say why signing transactions with pseudorandom private keys and revealing the signatures is safe from related-key attacks. The only assumption needed is that PRFs (pseudorandom functions) exist, which is a more conservative assumption than PKE exists. In other words it should be safer to assume that sha256 is pseudorandom than that elliptic curves give public-key encryption, though admittedly elliptic curves are used in bitcoin just for digital signatures and not PKE.
So assuming that the hash function h(x)=hash(type|seed|x) is a PRF, a PPT (probabilistic poly time) adversary who's given r_i=h(i) for i=1,2,...,n=poly(security parameter) cannot distinguish them from R_i that are truly random. Now suppose (sk_i,pk_i)=keygen(r_i) and the signatures sgn_i=sign_sk_i(msg_i) are published along with the msg_i, and a PPT adversary A1 can sign a new msg' so that verify_pk_j(msg',sgn_j) is true for some j<=n with a non-negligible advantage compared to the case where the keys were generated with keygen(R_i) randomly. This means that there exists another PPT adversary A2 who can distinguish between pseudorandom r_i=h(i) and random R_i sequences with non-negligible probability, simply by taking his input sequence t_i and creating (sk_i,pk_i)=keygen(t_i) and signing sgn_i=sign_sk_i(msg_i), and then simulating A1 by giving it the msg_i and sgn_i signatures and testing whether A1 successfully signs some new msg''. Therefore A2 is a PPT distinguisher and the hash function isn't a PRF, QED by contradiction.
That's a generic argument why pseudorandom keys are safe from related-key attacks, it has nothing to do with bitcoin wallets. However, in the context of bitcoin the optimal behavior of signing only once with each key is also true for deterministic wallets, meaning that an adversary has less than 10 minutes on average to try to attack, under the (even more conservative) assumption that the address hash is a one-way function.
Since with type-2 deterministic wallet the public keys are generated independently of the master private key, using key homomorphism, it's enough to say why signing transactions with pseudorandom private keys and revealing the signatures is safe from related-key attacks. The only assumption needed is that PRFs (pseudorandom functions) exist, which is a more conservative assumption than PKE exists. In other words it should be safer to assume that sha256 is pseudorandom than that elliptic curves give public-key encryption, though admittedly elliptic curves are used in bitcoin just for digital signatures and not PKE.
So assuming that the hash function h(x)=hash(type|seed|x) is a PRF, a PPT (probabilistic poly time) adversary who's given r_i=h(i) for i=1,2,...,n=poly(security parameter) cannot distinguish them from R_i that are truly random. Now suppose (sk_i,pk_i)=keygen(r_i) and the signatures sgn_i=sign_sk_i(msg_i) are published along with the msg_i, and a PPT adversary A1 can sign a new msg' so that verify_pk_j(msg',sgn_j) is true for some j<=n with a non-negligible advantage compared to the case where the keys were generated with keygen(R_i) randomly. This means that there exists another PPT adversary A2 who can distinguish between pseudorandom r_i=h(i) and random R_i sequences with non-negligible probability, simply by taking his input sequence t_i and creating (sk_i,pk_i)=keygen(t_i) and signing sgn_i=sign_sk_i(msg_i), and then simulating A1 by giving it the msg_i and sgn_i signatures and testing whether A1 successfully signs some new msg''. Therefore A2 is a PPT distinguisher and the hash function isn't a PRF, QED by contradiction.
That's a generic argument why pseudorandom keys are safe from related-key attacks, it has nothing to do with bitcoin wallets. However, in the context of bitcoin the optimal behavior of signing only once with each key is also true for deterministic wallets, meaning that an adversary has less than 10 minutes on average to try to attack, under the (even more conservative) assumption that the address hash is a one-way function.
tl;dr
It's theoretically possible to crack the seed from related-keys attack, but practically impossible to carry out.
I know that it's not easy, I'm concerned that it's possible. It takes government level cryptologists to reverse a twice used one-time-pad, but it can be done. And deterministic wallets are not standard at all. As far as I know, Electrum & Brainwallet are the only two examples of it in use in Bitcoin, and Brainwallet seems to use Electrum code to do it, so the methods are identical.
The amazing benefits and security of type-2 determinstic wallets has been discussed at length in several previous threads.
In fact, Electrum is not alone: Armory also chose to use deterministic wallets, and MultiBit and Bitcoin-Qt both plan to implement them as well.
I'm concerned about a particular attack vector. If you happen to have a link to show me, that would be helpful, but I am already aware of the several advantages of deterministic wallets. I would like to see one of the crypto-geeks (better than I) assess this particular risk. I can't really do it because I'm not very good at looking at the code and knowing what I'm looking at.
I just installed Electrum on my 64-bit linux mint 11.04, as per the instructions on the website, and I get the following error when trying to run it:
Traceback (most recent call last):
File "/usr/local/bin/electrum", line 23, in
from electrum.util import print_error
ImportError: No module named util
*Edit: Nevermind I did sudo pip uninstall electrum, them installed it again and all is well.
Traceback (most recent call last):
File "/usr/local/bin/electrum", line 23, in
from electrum.util import print_error
ImportError: No module named util
*Edit: Nevermind I did sudo pip uninstall electrum, them installed it again and all is well.
I have a question concerning the method of deterministic keypair generation that the Electrum client uses. My understanding is that a 128 bit random number is created for the 'seed', and that all followup keypairs are derived from this number. The number is represented outside of the client as a set of twelve English words. While I can see this as pretty slick, I thought of a potential problem. In cryptography, the Vernam Cipher or the one-time pad is considered an unbreakable code without the key; however it's called a one-time pad because if the key is reused even once, it's possible for a crytographer to derive the original key from the two encrypted codes, so long as he knows that they belong together. While I would doubt that taking two bitcoin addresses produced by the same Electrum client can be used to reproduce the seed, a large number of them known to come from the same user (and thus the same client) potentially could be used to reproduce the seed of that user, thus laying open that user's entire balance to theft. What algo does Electrum use to produce the keypairs, specificly? And is it known to be hardened against this kind of attack? I don't wish to diparage Electrum, but this potential attack vector with deterministic wallets honestly concerns me, and I don't see this addressed elsewhere.
I think it uses key stretching to make such a thing infeasible.
Code:
def stretch_key(self, seed):
oldseed = seed
for i in range(100000):
seed = hashlib.sha256(seed + oldseed).digest()
return string_to_number(seed)
oldseed = seed
for i in range(100000):
seed = hashlib.sha256(seed + oldseed).digest()
return string_to_number(seed)
Although best to ask ThomasV or gmaxwell. Deterministic wallets are pretty standard, so I'm not so sure it's totally easy to guess someone's seed.
I know that it's not easy, I'm concerned that it's possible. It takes government level cryptologists to reverse a twice used one-time-pad, but it can be done. And deterministic wallets are not standard at all. As far as I know, Electrum & Brainwallet are the only two examples of it in use in Bitcoin, and Brainwallet seems to use Electrum code to do it, so the methods are identical.
The amazing benefits and security of type-2 determinstic wallets has been discussed at length in several previous threads.
In fact, Electrum is not alone: Armory also chose to use deterministic wallets, and MultiBit and Bitcoin-Qt both plan to implement them as well.
I would feel more than comfortable with using deterministic keys for the vast majority of daily transactions, I'm more concerned about the possibility that this might eventually lay someone open to a large theft when the user believed that deterministic keys are as secure as individually created keys, and they most certainly are not. More than likely they are far more secure than most people will ever realisticly need, since real security is a scale between convience and safety.
But as long as there is no mathematical proof that such attack is impossible, I do not feel entirely comfortable with deterministic keys
You might have bigger problems then since ecdsa is also only assumed to be secure.
I fully share MoonShadow's concern, even though I am also not a crypto-expert.
But as long as there is no mathematical proof that such attack is impossible, I do not feel entirely comfortable with deterministic keys, and honestly I would not put the majority of my Bitcoin savings to deterministic keys. Another concern about deterministic keys, by the way, is raised here. Personally, I think you cannot be paranoid enough about this.
But at the same time I would not be too paranoid about using deterministic keys for my daily business (just like I do carry around my pocket wallet every day, taking the risk of loosing it, which would cost me a few 10s or 100s of EUROs, but I would not loose my life time savings).
Fortunately, Electrum supports the feature of importing keys (b.t.w. - is it supported by the GUI already?)
So, to be on the safe side, I would do the following:
- Generate some keys with the Bitcoin.org client and extract the keys, and then
- Import them to my Electrum client
Now I would use both kinds of keys - imported keys and "deterministic Electrum keys generated from seed" - in the same wallet.
Since Electrum has a nice GUI with the "flag" column, I can easily see which keys are my (potentially safer) imported keys, and how many funds are currently residing on my (potentially unsafer) deterministic keys.
I would make sure that the vast majority of my savings is always on my imported keys!
For normal transactions in daily life, I would use the deterministic keys for convenience.
This way, I have my keys and my security under control, while still enjoying the comfort of not having the need for regular backups - a one-time-backup (of seed and imported keys) is all I need.
From this practice, one could even derive a new Electrum client feature request:
The possibility to let the client do the job in the background that always at least [90%] (user configurable value) of my wallet's balance are associated to the imported keys! And maybe further more, there could be the feature that if I have e.g. 10 imported "savings" keys, that Electrum makes sure by background control that the savings on my imported keys are evenly distributed between them, e.g. by specifying that one single key (amongst the [10] imported keys) is not allowed to carry more than [20%] (=2*1/[10] in this example) of the total amount of imported key savings (again, the "2" could be a user configurable parameter).
Whenever there is a transaction for my wallet (i.e. I send or receive bitcoins), Electrum would check in background whether the conditions described above are still met. If not, the client would autonomously calculate what transaction(s) it has to trigger from one wallet address to another, such that the condition is met again. Then, there could be a pop-up window informing the user about this extra "internal" transaction, and by confirming with "ok" button the user allows the client to perform this transaction to keep his wallet "in good shape".
One could argue that this increased amount of "wallet internal transactions" would sacrifice anonymity to some extend (that's why the original BTC client always generates new changes addresses upon each BTC transmission etc.), but I would accept that if it improved the safety of my savings.
BTW: Another thing: GUI support for offline wallets (like in Armory) would be really nice, it would make the use of safe offline-wallets much more comfortable for the average user.
But as long as there is no mathematical proof that such attack is impossible, I do not feel entirely comfortable with deterministic keys, and honestly I would not put the majority of my Bitcoin savings to deterministic keys. Another concern about deterministic keys, by the way, is raised here. Personally, I think you cannot be paranoid enough about this.
But at the same time I would not be too paranoid about using deterministic keys for my daily business (just like I do carry around my pocket wallet every day, taking the risk of loosing it, which would cost me a few 10s or 100s of EUROs, but I would not loose my life time savings).
Fortunately, Electrum supports the feature of importing keys (b.t.w. - is it supported by the GUI already?)
So, to be on the safe side, I would do the following:
- Generate some keys with the Bitcoin.org client and extract the keys, and then
- Import them to my Electrum client
Now I would use both kinds of keys - imported keys and "deterministic Electrum keys generated from seed" - in the same wallet.
Since Electrum has a nice GUI with the "flag" column, I can easily see which keys are my (potentially safer) imported keys, and how many funds are currently residing on my (potentially unsafer) deterministic keys.
I would make sure that the vast majority of my savings is always on my imported keys!
For normal transactions in daily life, I would use the deterministic keys for convenience.
This way, I have my keys and my security under control, while still enjoying the comfort of not having the need for regular backups - a one-time-backup (of seed and imported keys) is all I need.
From this practice, one could even derive a new Electrum client feature request:
The possibility to let the client do the job in the background that always at least [90%] (user configurable value) of my wallet's balance are associated to the imported keys! And maybe further more, there could be the feature that if I have e.g. 10 imported "savings" keys, that Electrum makes sure by background control that the savings on my imported keys are evenly distributed between them, e.g. by specifying that one single key (amongst the [10] imported keys) is not allowed to carry more than [20%] (=2*1/[10] in this example) of the total amount of imported key savings (again, the "2" could be a user configurable parameter).
Whenever there is a transaction for my wallet (i.e. I send or receive bitcoins), Electrum would check in background whether the conditions described above are still met. If not, the client would autonomously calculate what transaction(s) it has to trigger from one wallet address to another, such that the condition is met again. Then, there could be a pop-up window informing the user about this extra "internal" transaction, and by confirming with "ok" button the user allows the client to perform this transaction to keep his wallet "in good shape".
One could argue that this increased amount of "wallet internal transactions" would sacrifice anonymity to some extend (that's why the original BTC client always generates new changes addresses upon each BTC transmission etc.), but I would accept that if it improved the safety of my savings.
BTW: Another thing: GUI support for offline wallets (like in Armory) would be really nice, it would make the use of safe offline-wallets much more comfortable for the average user.
I have a question concerning the method of deterministic keypair generation that the Electrum client uses. My understanding is that a 128 bit random number is created for the 'seed', and that all followup keypairs are derived from this number. The number is represented outside of the client as a set of twelve English words. While I can see this as pretty slick, I thought of a potential problem. In cryptography, the Vernam Cipher or the one-time pad is considered an unbreakable code without the key; however it's called a one-time pad because if the key is reused even once, it's possible for a crytographer to derive the original key from the two encrypted codes, so long as he knows that they belong together. While I would doubt that taking two bitcoin addresses produced by the same Electrum client can be used to reproduce the seed, a large number of them known to come from the same user (and thus the same client) potentially could be used to reproduce the seed of that user, thus laying open that user's entire balance to theft. What algo does Electrum use to produce the keypairs, specificly? And is it known to be hardened against this kind of attack? I don't wish to diparage Electrum, but this potential attack vector with deterministic wallets honestly concerns me, and I don't see this addressed elsewhere.
I think it uses key stretching to make such a thing infeasible.
Code:
def stretch_key(self, seed):
oldseed = seed
for i in range(100000):
seed = hashlib.sha256(seed + oldseed).digest()
return string_to_number(seed)
oldseed = seed
for i in range(100000):
seed = hashlib.sha256(seed + oldseed).digest()
return string_to_number(seed)
Although best to ask ThomasV or gmaxwell. Deterministic wallets are pretty standard, so I'm not so sure it's totally easy to guess someone's seed.
I know that it's not easy, I'm concerned that it's possible. It takes government level cryptologists to reverse a twice used one-time-pad, but it can be done. And deterministic wallets are not standard at all. As far as I know, Electrum & Brainwallet are the only two examples of it in use in Bitcoin, and Brainwallet seems to use Electrum code to do it, so the methods are identical.
I have a question concerning the method of deterministic keypair generation that the Electrum client uses. My understanding is that a 128 bit random number is created for the 'seed', and that all followup keypairs are derived from this number. The number is represented outside of the client as a set of twelve English words. While I can see this as pretty slick, I thought of a potential problem. In cryptography, the Vernam Cipher or the one-time pad is considered an unbreakable code without the key; however it's called a one-time pad because if the key is reused even once, it's possible for a crytographer to derive the original key from the two encrypted codes, so long as he knows that they belong together. While I would doubt that taking two bitcoin addresses produced by the same Electrum client can be used to reproduce the seed, a large number of them known to come from the same user (and thus the same client) potentially could be used to reproduce the seed of that user, thus laying open that user's entire balance to theft. What algo does Electrum use to produce the keypairs, specificly? And is it known to be hardened against this kind of attack? I don't wish to diparage Electrum, but this potential attack vector with deterministic wallets honestly concerns me, and I don't see this addressed elsewhere.
I think it uses key stretching to make such a thing infeasible.
Code:
def stretch_key(self, seed):
oldseed = seed
for i in range(100000):
seed = hashlib.sha256(seed + oldseed).digest()
return string_to_number(seed)
oldseed = seed
for i in range(100000):
seed = hashlib.sha256(seed + oldseed).digest()
return string_to_number(seed)
Although best to ask ThomasV or gmaxwell. Deterministic wallets are pretty standard, so I'm not so sure it's totally easy to guess someone's seed.
I have a question concerning the method of deterministic keypair generation that the Electrum client uses. My understanding is that a 128 bit random number is created for the 'seed', and that all followup keypairs are derived from this number. The number is represented outside of the client as a set of twelve English words. While I can see this as pretty slick, I thought of a potential problem. In cryptography, the Vernam Cipher or the one-time pad is considered an unbreakable code without the key; however it's called a one-time pad because if the key is reused even once, it's possible for a crytographer to derive the original key from the two encrypted codes, so long as he knows that they belong together. While I would doubt that taking two bitcoin addresses produced by the same Electrum client can be used to reproduce the seed, a large number of them known to come from the same user (and thus the same client) potentially could be used to reproduce the seed of that user, thus laying open that user's entire balance to theft. What algo does Electrum use to produce the keypairs, specificly? And is it known to be hardened against this kind of attack? I don't wish to diparage Electrum, but this potential attack vector with deterministic wallets honestly concerns me, and I don't see this addressed elsewhere.
Hey Flatfly! I see your hosting is back up! That is great!
What is the status on the 0.61 build that includes that nifty new gui?
What is the status on the 0.61 build that includes that nifty new gui?
You should discuss this server-client stuff here: https://bitcointalksearch.org/topic/electrum-server-discussion-thread-85475
There are ways to generate Electrum keypairs from seed without the Electrum client. If you're worried, download the HTML from brainwallet.org and keep it in a safe place--it does the job ("Chains" option near the top). Run if offline or with a fake/empty wallet if you need to verify it.
The rest of my post is about making the wallet act as a decentralised seed for downloading the client. Or at least every (or some) wallets act as torrent seed on on I2PSnark - (http://www.ghacks.net/2007/06/06/anonymous-bittorrent-with-i2psnark/). So the ability to obtain an electrum client is taken away from central servers.
How do you update it and ensure that all the versions are consistent? You can run your own server, too.That's what I thought
Maybe some kind of gpg-keyring 
The rest of my post is about making the wallet act as a decentralised seed for downloading the client. Or at least every (or some) wallets act as torrent seed on on I2PSnark - (http://www.ghacks.net/2007/06/06/anonymous-bittorrent-with-i2psnark/). So the ability to obtain an electrum client is taken away from central servers.
How do you update it and ensure that all the versions are consistent? You can run your own server, too. Jump to: