Topic: Split private keys - page 5. (Read 17309 times)

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.

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

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.

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.

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

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.

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?)?