Topic: Split private keys - page 4. (Read 17136 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.


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. 

See here: https://en.bitcoin.it/wiki/Contracts (CHECKMULTISIGVERIFY)


Agreed, just have to make sure that key renewal really is a lot more convenient.


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

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.


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

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.

Very interesting paper.

And the method is patented or patent pending  http://www.freepatentsonline.com/20030059041.pdf

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

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.

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.

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.

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:If the answer is "multiple signatures" then so be it.

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.

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.

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.

Agree, that one should not change crypto light-heartedly. 

I understood the original suggestion as an additional option and possibility to be offered, just for testing.

Moreover: In my contribution yesterday late at night I demonstrated how the two devices can do a joint signature with both of their keys. However, I did a short security review and found a flaw in the scheme. My suggestion requires a communication from device 2 to device 1 and then another communication from device 1 to device 2. The second communication must be trusted otherwise the private key of device two can be compromised. Since Gavins idea was to split trust between two devices, this does not work:

Device 2 sends $d_2^{-1}z$ to device 1. This is secure, since $z$ is random. Device 1 generates $k^{-1}(d_2^{-1} z+d_1 r)$
 and sends to device 2. Device 2 then multiplies by $d_2$ and publishes the result.

Therefore anyone who is able to snoop into the second inter-device communication is able to reconstruct $d_2$. So the obvious attack vector is to compromise device 1 and the job then is done.


Why? Personally, I prefer it to be discussed in the forum, where there is better access, where there is generally better visability of the topic and more contribution by others and more transparency of the process.

Maybe better to discuss this on the mailing list?

Anything that involves significant changes to the crypto seems like a bad idea. Even if the equations are sound, it will be harder to convince others of the systems soundness.

Two-sig transactions are far easier to implement and prove correct. Given that the requisite mobile support doesn't exist yet, concerns about upgrade time don't seem like a big deal to me.