Split private keys

[Forp]

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.

[ben-abuya]

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.

[Forp]

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.   

[tubro]

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

I 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:

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

[ben-abuya]

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.

[Forp]

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. 

[ben-abuya]

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.

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. 

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.

[smartcardguy]

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.

[ben-abuya]

It really depends on how much money you're talking about. Split keys and dead man's switch don't really make sense for a few hundred bucks worth. But if you have $100,000 in bitcoin, do you really want to bet it all on one smartcard? We need to come up with different approaches for different risk profiles. Certainly, making it really simple to securely store $500 is very important.

I think a device like IronKey but with the ability to sign a bitcoin transaction would be great for this. It could be a smartcard too, but not everybody has a smartcard reader these days. I'm looking forward to bitcoin keyboards with a built-in smartcard reader. They could have a hardware override so that the keyboard stops sending input to the computer and is only used for unlocking the smartcard.

[smartcardguy]

I agree regarding risk profiles.

I known the iron key guys, it's a good product and the team they have is good but it's expensive and doesn't support ECC or at least it did not last year and I highly doubt it supports the curve bitcoin uses.

I think it would be possible to get the interesting scenarios to work on a cheap 10 device, initial probably being around 40 due to volume issues, the form factor doesn't need to be a card there are lots of USB dongles.

[Gavin Andresen]

The risk profile I care about is:

User's computer is completely compromised by a root-kit trojan, but they don't know it.

However, the user has access to some other device or service that they have setup in advance to be a "second line of defense" to prevent their entire wallet from being stolen.

[ben-abuya]

The risk profile I care about is:

User's computer is completely compromised by a root-kit trojan, but they don't know it.

However, the user has access to some other device or service that they have setup in advance to be a "second line of defense" to prevent their entire wallet from being stolen.

Right, so by definition they don't have their wallet on the computer. IronKey has built in AES encryption. Imagine a smartcard or usb drive that had built in ECDSA encryption. The device could generate and store private keys and sign bitcoin transactions, but would be designed to never allow access to the private keys. The client just sends the unsigned transaction to the device and gets back the signed transaction.

This still has an weakness though. A rootkit could send the drive a transaction for your entire balance and have it sign it. So you need a screen on the drive that shows the amount and recipient address, and a physical confirm button.

[Forp]

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.

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.

The dead man's switch is a nice idea. 

Regarding script.cpp, I just checked if the opcode is there and not the logic. It looked to me that this is not a threshold scheme but a "you must present two signatures" scheme - so that's why I wrote about "increasing risk of loss". Moreover, wouldn't it also have to be used by the sender of the coins?!

[jimbobway]

The risk profile I care about is:

User's computer is completely compromised by a root-kit trojan, but they don't know it.

However, the user has access to some other device or service that they have setup in advance to be a "second line of defense" to prevent their entire wallet from being stolen.

An encrypted wallet could protect a user completely compromised by a root-kit trojan.  I don't see how cutting and pasting an encrypted wallet over to a service (dropbox) or device (android phone) is any different than splitting keys.

[ben-abuya]

The dead man's switch is a nice idea. 

Thanks, I'm a bit obsessed with that idea

Regarding script.cpp, I just checked if the opcode is there and not the logic. It looked to me that this is not a threshold scheme but a "you must present two signatures" scheme - so that's why I wrote about "increasing risk of loss". Moreover, wouldn't it also have to be used by the sender of the coins?!

I just checked the code again and I'm pretty sure it is a threshold scheme. nSigsCount is the threshold and nKeysCount is the total number of keys. Yes, it would have to be used by the sender of the coins to you. So, either you send yourself transactions like this, or you ask the person paying you to do a transaction like that. This could be as simple as giving them a different version of the bitcoin address that has a few type bits in it and a bunch of concatenated public keys. It would look like a regular address, just longer. You wouldn't even have to specify you want a special transaction, it would be implicit in the address.

An encrypted wallet could protect a user completely compromised by a root-kit trojan.  I don't see how cutting and pasting an encrypted wallet over to a service (dropbox) or device (android phone) is any different than splitting keys.

Not if the rootkit has a keylogger in it. Also, it's better if the attacker doesn't get the encrypted wallet, because then the problem is reduced to how good your pass phrase is.

[smartcardguy]

The risk profile I care about is:

User's computer is completely compromised by a root-kit trojan, but they don't know it.

However, the user has access to some other device or service that they have setup in advance to be a "second line of defense" to prevent their entire wallet from being stolen.

Me too, and this is a likely attack in my opinion.

To protect against this attack one needs the keys to be in a crypto processor of some sort, and the ability to do some flavor of trusted pin presentment.

Though this would mitigate the risks significantly we would also want to have a recovery story in the event of token loss and theft.

[smartcardguy]

The risk profile I care about is:

User's computer is completely compromised by a root-kit trojan, but they don't know it.

However, the user has access to some other device or service that they have setup in advance to be a "second line of defense" to prevent their entire wallet from being stolen.

Right, so by definition they don't have their wallet on the computer. IronKey has built in AES encryption. Imagine a smartcard or usb drive that had built in ECDSA encryption. The device could generate and store private keys and sign bitcoin transactions, but would be designed to never allow access to the private keys. The client just sends the unsigned transaction to the device and gets back the signed transaction.

This still has an weakness though. A rootkit could send the drive a transaction for your entire balance and have it sign it. So you need a screen on the drive that shows the amount and recipient address, and a physical confirm button.

The Ironkey also does RSA, it can be thought of as several devices in one, flash, smart card reader, smart card, all off a single USB bus.

The scenario we discuss here though doesn't require the flash component though it is of course interesting for other reasons.

As for the trusted input problem there are a few solutions, it depends on how deep you want to go to solve it.

To protect against user mode key l loggers in windows you can use the session 0 ui to collect the pin, only kernel malware would get past that.

You could use a secure PED (hard to do in a decentralized system)

You can use graphical pins, random layout (kind of like captchas)

There are a ton, first step IMHO is getting the keys off the host

[ByteCoin]

The risk profile I care about is:
User's computer is completely compromised by a root-kit trojan, but they don't know it.

There are a number of possible solutions to this problem. The best solution from a technical point of view would involve an implementation of the paper I referred to earlier.

I gather that you are willing to make changes to the bitcoin client software to enable users to opt into some scheme whereby they are protected even if their computer is compromised.

If the computer running the bitcoin client is rootkitted then strictly, it's impossible to trust anything the computer displays or limit what it sends or ensure the security of any information you input. Practically, there are limits to the complexity of software which anyone is willing to develop for a rootkit and so some use of the computer may be possible.

Possible solutions are:

1) Facilitating the use of an offline secure computer to hold the private key and generate transactions. In this case the engineering effort goes towards implementing an efficient secure communication probably involving copying alphanumeric strings between the two computers. The user has to have another computer and be able securely to install the client.

2) Facilitating the use of a third-party website the approval of which (indicated by quoting an ECDS) would be required before transactions of the client could succeed. In this case, the unapproved transaction generated by the client is sent to the website, the website displays what the transaction would accomplish in some hard-to-spoof fashion and the user approves of the transaction via some hard-to-brute-force pre-arranged password or other such token. The website then signs and either passes the transaction back or sends the transaction onto the network itself. This is a solution which requires multisignatures to be enabled.

There are other solutions, none of them easy or nice.

It would be helpful if you could come up with some use-cases for the private key splitting. What ideally would you like the user experience to be? What degree of deviation and increased complexity from the normal transaction process do you imagine will be tolerable? Is this solution intended to be suitable for crypto-ignorant non technical users of bitcoin?

ByteCoin

[Gavin Andresen]

Here's a use case I'd like to work:

I tell Bitcoin running on my computer or cell phone to run transactions through a bitcoin security service-- maybe I give it a https:// URL for the service.

I tell the security service "auto-approve small-value transactions, but give me a call for any transactions above $X (or $XY per day)."

The security service sends me something in the mail that I keep safe, but that I can use to recover use of my bitcoins in case the security service goes out of business or disappears or I decide to stop paying for the service.

I get bitcoin addresses either from my bitcoin client (not trustworthy!) and/or from the security service that require both my computer and the security service to sign to spend.  And I have people send bitcoins (or I self-send my own bitcoins) to those addresses.

Spending coins is done as usual-- I type in an amount and an address.  Behind the scenes, magic happens, and if the transaction is greater than $X I get a phone call -- "Press 1 to confirm payment of $X bitcoins to bitcoin address blah, press 2 to cancel."

If I suddenly get random phone calls, I know my computer has been infected.

[weavejester]

This sounds a lot like threshold cryptography combined with distributed key generation.

There have been a few papers written on using RSA to achieve the same result, but I'm unaware of this being done with elliptic curves. However, I'm not a cryptographer.

As a sidenote, splitting a private key in this fashion could be used to construct a simple contract without needing a trusted third party. Two individuals could generate a split private key, and then sign a pure function that would perform some prearranged task; by signing the function, it would be tied to a bitcoin account and essentially act as a fund manager. Bitcoin miners could then run this pure function (passing into it the current block data as an argument) as part of the block chain verification process.