I have worked on systems that utilize key splitting in the past, though not with ECC.
I like key splitting but thought it might be worthwhile to play devils advocate and see where it takes us.
Usability of these systems are typically poor (complex and failure prone) but the nature of the systems that use this approach it's not been a problem, for Bitcoin I think it can be.
If the goal is to protect the key from compromise we might want to enumerate the threats we hope to mitigate, for example if it's the Trojan cases then the code that can steal one key could likely steal all keys.
Process and privlige separation helps address the key compromise cases, this can be done in a few ways for a software only solution you can imagine an authenticated service and a LPC or maybe one where crypto happens on a phone vs on the pc.
Another more common design pattern would be to move crypto to a smart card and have cards clone the crypto to a backup card to deal with the loss issue.
Topic: Split private keys - page 4. (Read 17309 times)
Thank you for pointing this out. I checked this in the code. With the exception of script.cpp and script.h it is not used. Especially, it si not part of the GUI.
Guess we should make it available ASAP.
Still it is only part of the solution. It increases the risc of loss. Now you should not lose TWO things. Before that, you whould not lose ONE thing.
Guess we should make it available ASAP.
Still it is only part of the solution. It increases the risc of loss. Now you should not lose TWO things. Before that, you whould not lose ONE thing.
Well script.cpp is the core. It's completely integrated into bitcoin, it's just not in the default GUI. Before putting it into the GUI I'd add support to the RPC. I don't understand why this increases the risk of loss. If you only need 2 out of 5 keys, you can lose three of them and still be able to access your account. You can even do 1 out of 5 if you're worried about that and less worried about theft.
Ok. Then replace "secure device" in my sentence by "usb drives/smartcards/whatever".
There is a thing which holds your key. This thing gets broken - you lose your money. You copy this thing - you increase your risc of having it stolen and you have to redo the copy every time you generate new keys.
The solution I am contemplating takes care of BOTH aspects.
You cannot be compromised so easily, because you need more than one device to access your money.
You do not increase your risk of loss, because you "things" are replaceable.
With the suggest form of secret sharing you get both advantages for one price.
There is a thing which holds your key. This thing gets broken - you lose your money. You copy this thing - you increase your risc of having it stolen and you have to redo the copy every time you generate new keys.
The solution I am contemplating takes care of BOTH aspects.
You cannot be compromised so easily, because you need more than one device to access your money.
You do not increase your risk of loss, because you "things" are replaceable.
With the suggest form of secret sharing you get both advantages for one price.
Well there's always a tradeoff between loss and theft. If you're worried about loss but not theft you'd want 1 out of n where n is big. If you're worried about theft and not loss you'd want n out of n. You're usually worried about both so you compromise and choose m out of n somewhere in the middle.
I think a complimentary technique is to use a dead man's switch, so that in the case of loss Bitcoin will transfer your funds to another account after say 30 days. This is also already built into bitcoin scripting. That way you can focus less on loss and more about theft in your crypto protocol.
See here: https://en.bitcoin.it/wiki/Contracts (CHECKMULTISIGVERIFY)
Thank you for pointing this out. I checked this in the code. With the exception of script.cpp and script.h it is not used. Especially, it si not part of the GUI.
Guess we should make it available ASAP.
Still it is only part of the solution. It increases the risc of loss. Now you should not lose TWO things. Before that, you whould not lose ONE thing.
Imagine you lose the secure device. Or drop it. Or your cat pees on it. Your son runs his bike over it. There goes the access to all your bitcoins. 
The secure device holds no data, it's just used to generate keys and write them to the usb drives/smarcards/whatever. It's also used to sign transactions based on the keys on the usb drives/smartcards. If it gets lost, stolen or broken, you just get a new one.
Ok. Then replace "secure device" in my sentence by "usb drives/smartcards/whatever".
There is a thing which holds your key. This thing gets broken - you lose your money. You copy this thing - you increase your risc of having it stolen and you have to redo the copy every time you generate new keys.
The solution I am contemplating takes care of BOTH aspects.
You cannot be compromised so easily, because you need more than one device to access your money.
You do not increase your risk of loss, because you "things" are replaceable.
With the suggest form of secret sharing you get both advantages for one price.
Is this multiple signature feature for m of n or is it rather for 2 of 2. What I saw in the code was rather a 2 of 2 kind of scheme - and I did nto check if it is really turned on or just in the code but disabled.
See here: https://en.bitcoin.it/wiki/Contracts (CHECKMULTISIGVERIFY)
Getting the coins to a new address with keys is certainly possible and fun for the freak, for the John Doe user it is a no-go. Just compare: This new fine leather wallet is secure. You just have to move your coins into a different one every other day!
Agreed, just have to make sure that key renewal really is a lot more convenient.
Imagine you lose the secure device. Or drop it. Or your cat pees on it. Your son runs his bike over it. There goes the access to all your bitcoins.
The secure device holds no data, it's just used to generate keys and write them to the usb drives/smarcards/whatever. It's also used to sign transactions based on the keys on the usb drives/smartcards. If it gets lost, stolen or broken, you just get a new one.
I have found an article Two-Party Generation of DSA Signatures by Philip D. Mackenzie and Michael K. Reiter which looks very promising.
Very interesting paper.
And the method is patented or patent pending
http://www.freepatentsonline.com/20030059041.pdfI think this article http://www.paulgraham.com/softwarepatents.html gives good reasoning on why it is safe for us (and pretty much everyone) to ignore patents:
Quote
(...) no one will sue you for patent infringement till you have money, and once you have money, people will sue you whether they have grounds to or not. So I advise fatalism. Don't waste your time worrying about patent infringement. You're probably violating a patent every time you tie your shoelaces. At the start, at least, just worry about making something great and getting lots of users. If you grow to the point where anyone considers you worth attacking, you're doing well.
How would proactive sharing work in the context of bitcoin? Who decides that shares are renewed? It will be interesting to see if there are established open source tools that give us threshold, proactive sharing and verifiability.
I am trying to work that out right now.
The idea is, that the account holder also has access to a majority of devices holding the shares. So, the account holder would press the "redistribute secret" button on all the devices he has access to, and the devices would generate and distribute new shares using a suitable protocol. Those devices which are not present at that moment, would not get their new share, and their old share would, from that moment on, be useless.
It is probably easier (but less secure) to have a single trusted device redistribute the secret.
To my knowledge there are no open source tools which do that. So it would be a matter of implementing and having it subjected to peer and community reviewing. The good part is, that it does not affect Bitcoin at all and would be a seperate piece of software, using the RPC API of bitcoin.
I understand that Bitcoin already supports an m of n scheme for signatures. Any individual key can easily be verified in the usual way and a renewal can be accomplished by getting keys together and transferring to a new address with new keys.
Is this multiple signature feature for m of n or is it rather for 2 of 2. What I saw in the code was rather a 2 of 2 kind of scheme - and I did nto check if it is really turned on or just in the code but disabled.
Getting the coins to a new address with keys is certainly possible and fun for the freak, for the John Doe user it is a no-go. Just compare: This new fine leather wallet is secure. You just have to move your coins into a different one every other day!
I don't know if pluggable pc's are the best solution. I wouldn't want the keys being read on any machine that was connected to the net. I think the best safe solution is to create an unsigned transaction on your regular computer, write it to a usb drive, sign it on a secure device that has no connectivity but can show the amount sent and address sent to, and then send it via the regular computer. The secure device would also not have any persistent storage. Keys would be stored on additional usb drives.
I agreed with that until yesterday.
Imagine you lose the secure device. Or drop it. Or your cat pees on it. Your son runs his bike over it. There goes the access to all your bitcoins.
Cryptographical idea: We do not want private key splitting, we want more. We want a threshold scheme with proactive sharing (and, if possible, verifiability). This means:
I agree that the threshold scheme is important. How would proactive sharing work in the context of bitcoin? Who decides that shares are renewed? It will be interesting to see if there are established open source tools that give us threshold, proactive sharing and verifiability. However, proactive sharing and verifiability are slightly less important with Bitcoin. I understand that Bitcoin already supports an m of n scheme for signatures. Any individual key can easily be verified in the usual way and a renewal can be accomplished by getting keys together and transferring to a new address with new keys. The cryptographic version sounds more elegant, though.
I don't know if pluggable pc's are the best solution. I wouldn't want the keys being read on any machine that was connected to the net. I think the best safe solution is to create an unsigned transaction on your regular computer, write it to a usb drive, sign it on a secure device that has no connectivity but can show the amount sent and address sent to, and then send it via the regular computer. The secure device would also not have any persistent storage. Keys would be stored on additional usb drives.
Gavin, I looked at the papers Bytecoin cited, to see if it is worth effort implementing this.
Especially the first paper is very intersting. I agree that it should be possible to adapt the two zero knowledge proof parts from the Paillier crypto system (for which the paper gives a solution) to elliptic. Moreover, it probably involves quite a bit of thinking and implementing; it's not really as straight forward as it may seem.
Therefore, I spent a few hours analyzing the situation. I think that splitting private keys in the form you describe in your first post is the right direction but not really what we want. Let me first outline some problems I see with your approach and then provide an amendment to your thoughts.
Risk of loss: Suppose, we lose one of the two devices. Then we have lost our money, since we no longer can form the requested signature. Thus, while we gain more security against attackers, the burden on backup gets higher: We now have to backup two devices and we should do this after every generation of new keys. Lose your laptop, drop you mobile on the floor: Your money is gone. Two devices - double risk.
Burden of key-splitting: Every time we generate a new key, the two devices must synchronize, for the scheme to work. So: When generating a new bitcoin address, I need a new PAIR of private keys, which requires an activity on both devices. If you only have one device with you on generation time, you have got bad luck.
Usability: Looks like I always have to have both devices on me when using Bitcoin. Sometimes I will not. So I might end up having some small cash on some addresses which are only on one device. Or the other. And only the addresses with the big money are secured by secret splitting. Which may lead to user confusion and a hassle when trying to get the devices synchronized.
Mobility: Right now, BTC is a desktop application. It will become a mobile application. Fine. So will i need two mobile devices in that scheme, when I am having my beer in bitcoin bar? One could be a mobile phone. And the second? Smartcard? USB token? Second phone? How useful are two devices for a mobile solution?
Currently, I see two ways out of most problems: A cryptographical one (using a different crypto scheme) and an operational one.
Cryptographical idea: We do not want private key splitting, we want more. We want a threshold scheme with proactive sharing (and, if possible, verifiability). This means:
Threshold: We split keys not into two but into a larger number. For example: Five. (Desktop PC at work, desktop PC at home, mobile phone, smart card, USB token). We impose a threshold. For example: Two devices together can produce a valid signature. This solves the backup issue. Lose one device, you still have four left. I think, this threshold concept if a major improvement of the backup situation.
We have to modify the life-cycle of the keys, of course, to solve the other issues mentioned above. No small pools any longer, but 1.000 keys or more which are generated at the beginning. So we do not have to distribute fresh key shares so often.
Proactive sharing comes into the game, when we lose one of the devices. In this case, we want to disable the keys as fast as possible (before the attacker manages to steal a second of our devices). Proactive secret sharing allows us to redistribute the shares in such a manner, that compromised shares lose their value for the attacker.
Verifiability comes into the game, when one of devices is not lost but compromised or defective. It allows the other sharing participants to check if a sharing participant lies about his share (but, of course, without learning anything about the share).
For elliptic crypto and DSA, there exist threshold based signature schemes. I am currently researching, if there are proactive schemes (I assume, yes) or verifiable schemes (I do not know).
This concept should work without touching anything on Bitcoin crypto - we only add a wallet client.
Organizational idea: We do not split at the wallet private key level, but at the level of the user.
Our wallet is handled by a secure and trustworthy organization or node. We tell that organization or node using secret splitting schemes as outlined above, when they are supposed to use the wallet keys on our behalf. The node might be a pluggable PC such as openplug.org running out of my home (with a backup of the keys stored somewhere). The activating devices then are a smartcard to be put into any card reader and a mobile phone. These two devices would not have to use Bitcoin elliptic crypto but just ANY existing key sharing scheme (which is much easier to do). Again, Bitcoin client does not have to be modified.
The advantage here is: When I lose one of the devices, I do not lose my bitcoins. Not only the attacker has no advantage, I have no damage in case of a loss. It is easy to get a new mobile and place it in synch with the second device and the trusted node.
Those who do not want to buy a pluggable PC can delegate this to an authority they trust. (I admit, this is not completely satisfactory. So, rather, have your own pluggable PC).
Would be great to get a bit of feedback on these thoughts.
Thanx.
Especially the first paper is very intersting. I agree that it should be possible to adapt the two zero knowledge proof parts from the Paillier crypto system (for which the paper gives a solution) to elliptic. Moreover, it probably involves quite a bit of thinking and implementing; it's not really as straight forward as it may seem.
Therefore, I spent a few hours analyzing the situation. I think that splitting private keys in the form you describe in your first post is the right direction but not really what we want. Let me first outline some problems I see with your approach and then provide an amendment to your thoughts.
Risk of loss: Suppose, we lose one of the two devices. Then we have lost our money, since we no longer can form the requested signature. Thus, while we gain more security against attackers, the burden on backup gets higher: We now have to backup two devices and we should do this after every generation of new keys. Lose your laptop, drop you mobile on the floor: Your money is gone. Two devices - double risk.
Burden of key-splitting: Every time we generate a new key, the two devices must synchronize, for the scheme to work. So: When generating a new bitcoin address, I need a new PAIR of private keys, which requires an activity on both devices. If you only have one device with you on generation time, you have got bad luck.
Usability: Looks like I always have to have both devices on me when using Bitcoin. Sometimes I will not. So I might end up having some small cash on some addresses which are only on one device. Or the other. And only the addresses with the big money are secured by secret splitting. Which may lead to user confusion and a hassle when trying to get the devices synchronized.
Mobility: Right now, BTC is a desktop application. It will become a mobile application. Fine. So will i need two mobile devices in that scheme, when I am having my beer in bitcoin bar? One could be a mobile phone. And the second? Smartcard? USB token? Second phone? How useful are two devices for a mobile solution?
Currently, I see two ways out of most problems: A cryptographical one (using a different crypto scheme) and an operational one.
Cryptographical idea: We do not want private key splitting, we want more. We want a threshold scheme with proactive sharing (and, if possible, verifiability). This means:
Threshold: We split keys not into two but into a larger number. For example: Five. (Desktop PC at work, desktop PC at home, mobile phone, smart card, USB token). We impose a threshold. For example: Two devices together can produce a valid signature. This solves the backup issue. Lose one device, you still have four left. I think, this threshold concept if a major improvement of the backup situation.
We have to modify the life-cycle of the keys, of course, to solve the other issues mentioned above. No small pools any longer, but 1.000 keys or more which are generated at the beginning. So we do not have to distribute fresh key shares so often.
Proactive sharing comes into the game, when we lose one of the devices. In this case, we want to disable the keys as fast as possible (before the attacker manages to steal a second of our devices). Proactive secret sharing allows us to redistribute the shares in such a manner, that compromised shares lose their value for the attacker.
Verifiability comes into the game, when one of devices is not lost but compromised or defective. It allows the other sharing participants to check if a sharing participant lies about his share (but, of course, without learning anything about the share).
For elliptic crypto and DSA, there exist threshold based signature schemes. I am currently researching, if there are proactive schemes (I assume, yes) or verifiable schemes (I do not know).
This concept should work without touching anything on Bitcoin crypto - we only add a wallet client.
Organizational idea: We do not split at the wallet private key level, but at the level of the user.
Our wallet is handled by a secure and trustworthy organization or node. We tell that organization or node using secret splitting schemes as outlined above, when they are supposed to use the wallet keys on our behalf. The node might be a pluggable PC such as openplug.org running out of my home (with a backup of the keys stored somewhere). The activating devices then are a smartcard to be put into any card reader and a mobile phone. These two devices would not have to use Bitcoin elliptic crypto but just ANY existing key sharing scheme (which is much easier to do). Again, Bitcoin client does not have to be modified.
The advantage here is: When I lose one of the devices, I do not lose my bitcoins. Not only the attacker has no advantage, I have no damage in case of a loss. It is easy to get a new mobile and place it in synch with the second device and the trusted node.
Those who do not want to buy a pluggable PC can delegate this to an authority they trust. (I admit, this is not completely satisfactory. So, rather, have your own pluggable PC).
Would be great to get a bit of feedback on these thoughts.
Thanx.
I have found an article Two-Party Generation of DSA Signatures by Philip D. Mackenzie and Michael K. Reiter which looks very promising.
Very interesting paper.
And the method is patented or patent pending
http://www.freepatentsonline.com/20030059041.pdf
At first glance, adapting the scheme to ECDSA should not be troublesome but implementing it is likely to involve a substantial amount of work. It is, however, vastly simpler than trying to do it using a generic MPC scheme.
Zero-knowledge proofs... ummm....Nice to know it can be done securely. I'll leave it to the professionals to actually do it.
I have found an article Two-Party Generation of DSA Signatures by Philip D. Mackenzie and Michael K. Reiter which looks very promising.
At first glance, adapting the scheme to ECDSA should not be troublesome but implementing it is likely to involve a substantial amount of work. It is, however, vastly simpler than trying to do it using a generic MPC scheme.
This should be exactly what you need Gavin.
Everyone else should note that implementing this would not involve any changes to the Bitcoin system.
It's also worth reading Secure Distributed Key Generation for Discrete-Log Based Cryptosystems by Rosario Gennaro, Stanis law Jarecki , Hugo Krawczyk and Tal Rabin
ByteCoin
At first glance, adapting the scheme to ECDSA should not be troublesome but implementing it is likely to involve a substantial amount of work. It is, however, vastly simpler than trying to do it using a generic MPC scheme.
This should be exactly what you need Gavin.
Everyone else should note that implementing this would not involve any changes to the Bitcoin system.
It's also worth reading Secure Distributed Key Generation for Discrete-Log Based Cryptosystems by Rosario Gennaro, Stanis law Jarecki , Hugo Krawczyk and Tal Rabin
ByteCoin
RE: pulling the wallet private key encryption ASAP: Agreed 100%
I wanted to start discussing split keys now because if we need a new standard transaction type then it is best to do that in stages-- let clients relay, and miners include in blocks, the new transaction type. Then once most of the network will accept the new transactions, people can actually start USING them.
I wanted to start discussing split keys now because if we need a new standard transaction type then it is best to do that in stages-- let clients relay, and miners include in blocks, the new transaction type. Then once most of the network will accept the new transactions, people can actually start USING them.
Two-factor authentication on multiple devices is fine for down the line, but we really need a good solution to encrypt the private components of our ECDSA keypairs right now. I would implement that PULL as soon as possible (with appropriate modifications) and then move onto additional changes. Hashing the private keys with a good algorithm will make the standard attack vector of "look for a wallet.dat, send it home" much harder. The attacker will have to install some kind of keylogger or memory logger and then wait for the next time the user needs to decrypt the private component of the wallet to sign a transaction. Plus, odds are decent the user may discover their infection in the interim before they ever decrypt their wallet.dat.
As an anecdote, I consider myself a pretty savvy PC user. Still, back when I was using Windows as a primary OS, I did get a virus once from a shady torrent. Within a day I immediately realized things were off and completely re-formatted my PC. Now, pretending that Bitcoin existed back then, encryption of the private key component would've been the difference between me losing all of my bitcoins and not.
As an anecdote, I consider myself a pretty savvy PC user. Still, back when I was using Windows as a primary OS, I did get a virus once from a shady torrent. Within a day I immediately realized things were off and completely re-formatted my PC. Now, pretending that Bitcoin existed back then, encryption of the private key component would've been the difference between me losing all of my bitcoins and not.
Paypal used to (dont know if they still do) give out a free RSA fob with each new account. I think they later started charging for them but the price was miniscal. WoW I believe uses the same system.
Since you aren't a cryptographer, why not just implement transactions with multiple signatures?
Because sending to a multiple-signature-required address requires a new standard transaction type, a new type of bitcoin address, and a protocol for Device 1 <-> Device 2 communication. More code means more possibility of bugs, so I was hoping there is a simpler solution.And as I said in the original post, I wanted to start discussion:
Quote
and then point me to a FIPS standard that has it all figured out already...
If the answer is "multiple signatures" then so be it.
I see a portable dedicated device with very limited communications ability. Just a serial port will do, which probably means serial over USB or serial over bluetooth. It will also have a SD card socket for wallet backups.
I think this could help with the retail problem too; no reason why you couldn't plug it into a potentially hostile terminal.
I think this could help with the retail problem too; no reason why you couldn't plug it into a potentially hostile terminal.
How will you ensure, that the 2.00 BTC which the hostile terminal shows you are about to pay isn't 450.00 BTC. Ie: How do you plan to deal with the hostile display issue? Will your device have its own screen?
Yes, it will have a display. I guess I didn't mention that, but it is absolutely essential.
It can either show the address, and ask for an amount. Or it can show the address and amount, and ask for a Yes/No.
I see a portable dedicated device with very limited communications ability. Just a serial port will do, which probably means serial over USB or serial over bluetooth. It will also have a SD card socket for wallet backups.
I think this could help with the retail problem too; no reason why you couldn't plug it into a potentially hostile terminal.
I think this could help with the retail problem too; no reason why you couldn't plug it into a potentially hostile terminal.
How will you ensure, that the 2.00 BTC which the hostile terminal shows you are about to pay isn't 450.00 BTC. Ie: How do you plan to deal with the hostile display issue? Will your device have its own screen?
I've been thinking about wallet security too. I think a second device is a good idea, but I see it working in a different way.
I see a portable dedicated device with very limited communications ability. Just a serial port will do, which probably means serial over USB or serial over bluetooth. It will also have a SD card socket for wallet backups.
The device will generate the key pairs, and store them. The private key never leaves the device, except on the SD card backup, which could be encrypted.
I think it only needs 3 hooks into the PC client software.
1) It needs to be able to push public keys to the client.
2) It needs to be able to ask for (and receive) balance updates from the client.
3) It needs to be able to accept an address from the client, and generate a complete transaction to that address using an amount entered on a keypad. (Or possibly accept an address and amount, then only ask for confirmation.)
I think this could help with the retail problem too; no reason why you couldn't plug it into a potentially hostile terminal.
I'm thinking Arduino. It should already have all of the crypto libraries necessary, plus hookups for serial, USB, BT, and SD cards. Probably going to order some hardware this week to get started.
I see a portable dedicated device with very limited communications ability. Just a serial port will do, which probably means serial over USB or serial over bluetooth. It will also have a SD card socket for wallet backups.
The device will generate the key pairs, and store them. The private key never leaves the device, except on the SD card backup, which could be encrypted.
I think it only needs 3 hooks into the PC client software.
1) It needs to be able to push public keys to the client.
2) It needs to be able to ask for (and receive) balance updates from the client.
3) It needs to be able to accept an address from the client, and generate a complete transaction to that address using an amount entered on a keypad. (Or possibly accept an address and amount, then only ask for confirmation.)
I think this could help with the retail problem too; no reason why you couldn't plug it into a potentially hostile terminal.
I'm thinking Arduino. It should already have all of the crypto libraries necessary, plus hookups for serial, USB, BT, and SD cards. Probably going to order some hardware this week to get started.
Since you aren't a cryptographer, why not just implement transactions with multiple signatures?
FYI: I posted this here on the forums because I see the mailing list as being for nuts-and-bolts "lets talk about exactly how to get XYZ done."
And I see these forums as a better place for brainstorming and pie-in-the-sky maybe-it-will-work-maybe-it-won't discussions.
Also, equations don't look pretty in plain-text emails.
And I see these forums as a better place for brainstorming and pie-in-the-sky maybe-it-will-work-maybe-it-won't discussions.
Also, equations don't look pretty in plain-text emails.
Jump to: