Split private keys

[Gavin Andresen]

So I've been thinking a lot about wallet security; Matt's password patch is a good first step, but maybe we can at least build in some infrastructure for a better solution.

We really need a solution where transactions are generated on one device and then verified on a second device, so malware must compromise both devices (e.g. computer and mobile phone, or web wallet and mobile phone) to steal coins.

gmaxwell from IRC thinks it can be done without multiple signatures (just with the standard transaction we have now), and staring at the ECDSA math on this wikipedia page I think he's right.  I believe he was inspired by ByteCoin's observation that you can create a vanity public key generating service that is secure-- the service can generate the public key but not know the private key.

I'm mostly writing this to convince myself it could work and to give ByteCoin and Hal and gmaxwell and anybody else who knows a whole lot more crypto than me a chance to poke holes in it. And then point me to a FIPS standard that has it all figured out already...

So:  generating an ECDSA keypair means choosing a private key d_A, then calculating the public key Q_A = d_AG (where G is a fixed point on the elliptic curve).

The key generation can be split; have device 1 choose d_A1 and device 2 choose d_A2.  Device 1 then sends Q_A1 to Device 2, and it can calculate Q_A1d_A2 = Q_A1*A2.  Or in english, Device 1 finds a public key on the curve.  Then Device 2 uses its part of the private key to do a bunch more elliptic curve multiplies to find the composite public key without ever knowing Device 1's public key.

So great, neither Device 1 or 2 needs to ever have both parts of the private key on them to generate the shared public key.

Now lets say Device 1 wants to spend a TxOut that is one of these split keys.  The key bit of the signature generation algorithm (see the Wikipedia page: http://en.wikipedia.org/wiki/Elliptic_Curve_DSA#Signature_generation_algorithm ) is:
...
4. Calculate s = k^-1(z+rd_A)(mod n)
...
That can be rewritten as:

Calculate s = k^-1(z+rd_A1d_A2)(mod n)

And now I'm stuck.  Can that equation be refactored so that Device 1 can compute part of the signature, send its partial result to Device 2, and have Device 2 complete the signature (without Device 2 being able to figure out 1's part of the private key?)?

[passerby]

Gavin, not being a coder I might be treading way out of my depth here, but why go to all that length and deal with potential disastrous interactions between whatever happens in the mobile device and whatever happens on desktop (problem, bluetooth ? ), the results of which will amount to unhappy users and blame and whatnot, and not, say, implement HSM/smartcard support?

While I understand that the question of "dedicated hardware cryptographic devices vs. smartphones" is at least tangential to your post, methinks it is worthwhile to suggest that the developers look into the issue of whether capabilities of modern smartcard/HSMs are relevant to the goals of protecting wallets and can be used to implement a decent solution - IIRC there are "open source" smartcard solutions and affordable usb HSMs, and they aren't murderously expensive, and something tells me that it is not unlikely that dedicated cryptographic devices will offer more straightforward ways of securing wallet material than the (seemingly?   ) exotic approach you have outlined.

Anyone who has >2 000$ worth of coins in his wallet should be able to buy a motherloving smart card reader with the card, or a token, whatever class of hardware security devices you, the developers, will find easier/more practical to support.

[ByteCoin]

...
gmaxwell from IRC thinks it can be done without multiple signatures
...
Can that equation be refactored so that Device 1 can compute part of the signature, send its partial result to Device 2, and have Device 2 complete the signature (without Device 2 being able to figure out 1's part of the private key?)?

I presume it's also not acceptable for device 1 to be able to figure out device 2's part of the private key after viewing the completed signature.

I've looked into this already for a very similar application and initially I was hopeful too.

k is a random number provided by the first signer with the intention of preventing the recovery of the private key d by simple algebra. The second signer would need to incorporate their own random number into the "k" portion of the equation in order to prevent the first signer from deducing their d_B by analogous manipulation. However there doesn't seem to be a way of making a signature that behaves like ECDSA without revealing secret information.

Now it's Hal's chance to shine by showing how it's done!

You can probably create a multiparty signature but it would have to be verified by a different algorithm to the standard ECDSA and hence would be entering worryingly novel crypto territory. The benefit over multiparty signatures implemented in the script would be small.

I don't know much about secure multiparty computation but there may be a solution down that avenue but it would be a bit like using a sledgehammer to crack a nut.

ByteCoin

[cschmitz]

Generally i think the practice by people in the long run will have to involve a checking and a savings wallet, where best practice should be leaving no more than 500$ worth in the checking wallet.
That way, a wallet with more usability can be held, for mobile devices, "simple" password security and such. On the other side, due to the nature of bitcoin, a secure savings wallet should be promoted, using physically external security features such as a mobile auth app or a smartcard.
Once the development for such a second tier of defense is there, usage of such should be heavily promoted by bitcoin.org, after all users need to be protected from their own stupidity.

[Forp]

Calculate s = k^-1(z+rd_A1d_A2)(mod n)

And now I'm stuck.  Can that equation be refactored so that Device 1 can compute part of the signature, send its partial result to Device 2, and have Device 2 complete the signature (without Device 2 being able to figure out 1's part of the private key?)?

If you allow two communications between the devices, couldn't it be done as follows:

Device 2 calculates d^-1₂z and sends this to Device 1.

Device 1 then calculates k^-1(d^-1₂z + d₁r) and sends to Device 2.

Device 2 multiplies by d₂ and has the result.

[gim]

(subscribing, and doubtful about injecting cryptonovelties strait into Bitcoin)

[Mike Hearn]

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.

[Forp]

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.

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.

Maybe better to discuss this on the mailing list?

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.

[Gavin Andresen]

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.

[ene]

Since you aren't a cryptographer, why not just implement transactions with multiple signatures?

[kjj]

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.

[Forp]

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.

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?

[kjj]

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.

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.

[Gavin Andresen]

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:

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.

[Oldminer]

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.

[CydeWeys]

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.

[Gavin Andresen]

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.

[ByteCoin]

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

[Gavin Andresen]

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.

[Forp]

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