Is this a safe thing to be doing with ECC addition? (Oracle protocol)
10 messages, 4 to 8 Mar 2014. Started by Edmund Edgar.
Edmund Edgar (3), Alan Reiner (3), Odinn Cyberguerrilla, Joel Joonatan Kaartinen, Adam Back, Natanael
Some people may have seen my service Reality Keys, which can perform a role a bit like an External State Oracle as described previously by Mike Hearn and others. (I like to think of it as a Certificate Authority for propositions, doing for facts what Verisign do for identities.) You register a possible outcome with us, we publish a public key for "yes" and another for "no", and once the outcome happens or fails to happen, we publish the appropriate private key.
A few people have been asking for advice on the best way to use our keys to make m-of-n contracts, where each party locks up their stake in a transaction, then the winner gets their private key from Reality Keys and uses it to release the funds. Peter Todd suggested what seems like a very nice way to do this without needing non-standard transactions or refund transactions. I've had a go at implementing it and it seems to work, but I don't know enough about this to distinguish the ECC bit of it from magic, so I'm wondering if people who do understand it could comment on whether it's a safe thing to be doing.
What I'm trying to do here is to combine the public key of each party with the public key of the outcome they're representing, eg I make a public key with: <alice-pub> + <reality-key-yes-pub> ...and another with: <bob-pub> + <reality-key-no-pub>
That goes into a 1/2 P2SH address (in the simplest possible case), which is spendable by one of Alice or Bob after the outcome occurs with either: <alice-priv> + <reality-key-yes-priv> ...or <bob-priv> + <reality-key-no-priv>
I'm making the transaction with add_pubkeys, then spending it with add_privkeys, both from: https://github.com/vbuterin/pybitcointools/blob/master/pybitcointools/main.py#L173
What's worrying my superstitious mind is that knowing <reality-key-no-pub> before he has to produce <bob-pub>, I'm wondering if there's something Bob could do with <bob-pub> to intentionally weaken the resulting (<bob-pub> + <reality-key-no-pub>) so that he could sign a transaction with it without needing to know <reality-key-no-priv>.
My example script (and specifically the bit that's scaring me) is here: https://github.com/edmundedgar/realitykeys-examples/blob/master/realitykeysdemo.py#L247
PS. I hope I'm not too far off-topic. Peter Todd suggested it might be worth talking about here as it potentially has implications for other protocols. If people prefer to respond at bitcointalk instead, we've been discussing it here: https://bitcointalk.org/index.php?topic=260898.60
Nothing is safe.
Take risks. Engage one trouble at a time.
Perform unexpected actions.
Observe the results.
Rinse and repeat.
Ignore the lions. They too shall pass.
"Do not sleep under a roof. Carry no money or food. Go alone to places frightening to the common brand of men. Become a criminal of purpose. Be put in jail, and extricate yourself by your own wisdom."
-- Miyamoto Musashi (Niten Ichi-ryū)
Quoted text (77 lines)
> Some people may have seen my service Reality Keys, which can perform a > role > a bit like an External State Oracle as described previously by Mike Hearn > and others. (I like to think of it as a Certificate Authority for > propositions, doing for facts what Verisign do for identities.) You > register a possible outcome with us, we publish a public key for "yes" and > another for "no", and once the outcome happens or fails to happen, we > publish the appropriate private key. > > A few people have been asking for advice on the best way to use our keys > to > make m-of-n contracts, where each party locks up their stake in a > transaction, then the winner gets their private key from Reality Keys and > uses it to release the funds. Peter Todd suggested what seems like a very > nice way to do this without needing non-standard transactions or refund > transactions. I've had a go at implementing it and it seems to work, but I > don't know enough about this to distinguish the ECC bit of it from magic, > so I'm wondering if people who do understand it could comment on whether > it's a safe thing to be doing. > > What I'm trying to do here is to combine the public key of each party with > the public key of the outcome they're representing, eg I make a public key > with: > <alice-pub> + <reality-key-yes-pub> > ...and another with: > <bob-pub> + <reality-key-no-pub> > > That goes into a 1/2 P2SH address (in the simplest possible case), which > is > spendable by one of Alice or Bob after the outcome occurs with either: > <alice-priv> + <reality-key-yes-priv> > ...or > <bob-priv> + <reality-key-no-priv> > > I'm making the transaction with add_pubkeys, then spending it with > add_privkeys, both from: > https://github.com/vbuterin/pybitcointools/blob/master/pybitcointools/main.py#L173 > > What's worrying my superstitious mind is that knowing <reality-key-no-pub> > before he has to produce <bob-pub>, I'm wondering if there's something Bob > could do with <bob-pub> to intentionally weaken the resulting (<bob-pub> + > <reality-key-no-pub>) so that he could sign a transaction with it without > needing to know <reality-key-no-priv>. > > My example script (and specifically the bit that's scaring me) is here: > https://github.com/edmundedgar/realitykeys-examples/blob/master/realitykeysdemo.py#L247 > > PS. I hope I'm not too far off-topic. Peter Todd suggested it might be > worth talking about here as it potentially has implications for other > protocols. If people prefer to respond at bitcointalk instead, we've been > discussing it here: > https://bitcointalk.org/index.php?topic=260898.60 > > -- > Edmund Edgar > Founder, Social Minds Inc (KK) > Twitter: @edmundedgar > Linked In: edmundedgar > Skype: edmundedgar > http://www.socialminds.jp > > Reality Keys > @realitykeys > ed@realitykeys•com > https://www.realitykeys.com > ------------------------------------------------------------------------------ > Subversion Kills Productivity. Get off Subversion & Make the Move to > Perforce. > With Perforce, you get hassle-free workflows. Merge that actually works. > Faster operations. Version large binaries. Built-in WAN optimization and > the > freedom to use Git, Perforce or both. Make the move to Perforce. > http://pubads.g.doubleclick.net/gampad/clk?id=122218951&iu=/4140/ostg.clktrk_______________________________________________ > Bitcoin-development mailing list > Bitcoin-development@lists•sourceforge•net > https://lists.sourceforge.net/lists/listinfo/bitcoin-development >
On 4 March 2014 14:07, Odinn Cyberguerrilla <odinn.cyberguerrilla@riseup•net
Quoted text (3 lines)
> wrote: > Nothing is safe. >
This is true. To rephrase, imagine I gave you an ECC public key <ed_pub>, you gave me back a public key <odinn_pub> of your own devising, then I paid some money to the address resulting from add_pubkeys(<ed_pub>,<odinn_pub>) [1]. Can anyone either:
a) Think of a way that Odinn could make an <odinn_pub> such that they could spend the resulting money without having <ed_priv>. b) Opine, somewhat knowledgeably, that this probably wouldn't be an easy thing to do, and they wouldn't be alarmed to see people running software that did this kind of thing.
[1] https://github.com/vbuterin/pybitcointools/blob/master/pybitcointools/main.py#L173
On 03/08/2014 01:55 AM, Edmund Edgar wrote:
Quoted text (19 lines)
> On 4 March 2014 14:07, Odinn Cyberguerrilla > <odinn.cyberguerrilla@riseup•net > <mailto:odinn.cyberguerrilla@riseup.net>> wrote: > > Nothing is safe. > > > This is true. To rephrase, imagine I gave you an ECC public key > <ed_pub>, you gave me back a public key <odinn_pub> of your own > devising, then I paid some money to the address resulting from > add_pubkeys(<ed_pub>,<odinn_pub>) [1]. Can anyone either: > > a) Think of a way that Odinn could make an <odinn_pub> such that they > could spend the resulting money without having <ed_priv>. > b) Opine, somewhat knowledgeably, that this probably wouldn't be an > easy thing to do, and they wouldn't be alarmed to see people running > software that did this kind of thing. > > [1] https://github.com/vbuterin/pybitcointools/blob/master/pybitcointools/main.py#L173
Consider that I see your public key <a_pub> before I create and send you my public key <b_pub>.
I create a new keypair, <c_pub> with <c_priv> which I know (it can be any arbitrary key pair). But I don't give you <c_pub>, I give you <b_pub> = <c_pub> minus <a_pub> (which I can do because I've seen <a_pub> before doing this).
Sure, I don't know the private key for <b_pub>, but it doesn't matter... because what
<b_pub> + <a_pub> = <c_pub> (mine)
You have no way to detect this condition, because you don't know what c_pub/c_priv I created, so you can only detect this after it's too late (after I abuse the private key)
-Alan
On 8 March 2014 17:10, Alan Reiner <etotheipi@gmail•com> wrote:
Quoted text (14 lines)
> I create a new keypair, <c_pub> with <c_priv> which I know (it can be any > arbitrary key pair). But I don't give you <c_pub>, I give you <b_pub> = > <c_pub> minus <a_pub> (which I can do because I've seen <a_pub> before > doing this). > > Sure, I don't know the private key for <b_pub>, but it doesn't matter... > because what > > <b_pub> + <a_pub> = <c_pub> (mine) > > You have no way to detect this condition, because you don't know what > c_pub/c_priv I created, so you can only detect this after it's too late > (after I abuse the private key) >
Thanks Alan and Forrest, that makes sense. So to salvage the situation in the original case, we have to make sure the parties exchange their public keys first, before they're allowed to see the public keys they'll be combining them with.
If both parties insist on seeing a hash of the other party's public key before they'll show their own public key, they can be sure that the public key is not chosen based on the public key they themselves presented.
Although, I have to wonder, why not just use multisig?
- Joel
On 08.03.2014 10:51, Edmund Edgar wrote:
Quoted text (51 lines)
> On 8 March 2014 17:10, Alan Reiner <etotheipi@gmail•com > <mailto:etotheipi@gmail.com>> wrote: > > > I create a new keypair, <c_pub> with <c_priv> which I know (it can > be any arbitrary key pair). But I don't give you <c_pub>, I give > you <b_pub> = <c_pub> minus <a_pub> (which I can do because I've > seen <a_pub> before doing this). > > Sure, I don't know the private key for <b_pub>, but it doesn't > matter... because what > > <b_pub> + <a_pub> = <c_pub> (mine) > > You have no way to detect this condition, because you don't know > what c_pub/c_priv I created, so you can only detect this after > it's too late (after I abuse the private key) > > > Thanks Alan and Forrest, that makes sense. So to salvage the situation > in the original case, we have to make sure the parties exchange their > public keys first, before they're allowed to see the public keys > they'll be combining them with. > > -- > -- > Edmund Edgar > Founder, Social Minds Inc (KK) > Twitter: @edmundedgar > Linked In: edmundedgar > Skype: edmundedgar > http://www.socialminds.jp > > Reality Keys > @realitykeys > ed@realitykeys•com <mailto:ed@realitykeys.com> > https://www.realitykeys.com > > > ------------------------------------------------------------------------------ > Subversion Kills Productivity. Get off Subversion & Make the Move to Perforce. > With Perforce, you get hassle-free workflows. Merge that actually works. > Faster operations. Version large binaries. Built-in WAN optimization and the > freedom to use Git, Perforce or both. Make the move to Perforce. > http://pubads.g.doubleclick.net/gampad/clk?id=122218951&iu=/4140/ostg.clktrk > > > _______________________________________________ > Bitcoin-development mailing list > Bitcoin-development@lists•sourceforge•net > https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Also the other limitation for ECDSA is that there is no known protocol to create a signture with a+b (where keys P=aG, Q=bG, R=P+Q=(a+b)G). without either a sending its private key to b or viceversa (or both to a third party).
With Schnorr sigs you can do it, but the k^-1 term in ECDSA makes a (secure) direct multiparty signature quite difficult.
ps probably only 1 party needs to hash their key
P=aG
H(P) ->
<- Q=bG
P ->
Adam
On Sat, Mar 08, 2014 at 12:37:30PM +0200, Joel Kaartinen wrote:
Quoted text (4 lines)
> If both parties insist on seeing a hash of the other party's public key > before they'll show their own public key, they can be sure that the > public key is not chosen based on the public key they themselves > presented.
You can always use a secure multiparty computation algorithm to do it.
https://en.wikipedia.org/wiki/Secure_multi-party_computation
But those aren't the fastest algorithms in the world, and usually both participants needs to be online at the same time. I guess most people would prefer a two-step algorithm that can be performed asynchronously.
- Sent from my phone Den 8 mar 2014 18:44 skrev "Adam Back" <adam@cypherspace•org>:
Quoted text (41 lines)
> Also the other limitation for ECDSA is that there is no known protocol to > create a signture with a+b (where keys P=aG, Q=bG, R=P+Q=(a+b)G). without > either a sending its private key to b or viceversa (or both to a third > party). > > With Schnorr sigs you can do it, but the k^-1 term in ECDSA makes a > (secure) > direct multiparty signature quite difficult. > > ps probably only 1 party needs to hash their key > > P=aG > H(P) -> > > <- Q=bG > > P -> > > Adam > > On Sat, Mar 08, 2014 at 12:37:30PM +0200, Joel Kaartinen wrote: > > If both parties insist on seeing a hash of the other party's public key > > before they'll show their own public key, they can be sure that the > > public key is not chosen based on the public key they themselves > > presented. > > > ------------------------------------------------------------------------------ > Subversion Kills Productivity. Get off Subversion & Make the Move to > Perforce. > With Perforce, you get hassle-free workflows. Merge that actually works. > Faster operations. Version large binaries. Built-in WAN optimization and > the > freedom to use Git, Perforce or both. Make the move to Perforce. > > http://pubads.g.doubleclick.net/gampad/clk?id=122218951&iu=/4140/ostg.clktrk > _______________________________________________ > Bitcoin-development mailing list > Bitcoin-development@lists•sourceforge•net > https://lists.sourceforge.net/lists/listinfo/bitcoin-development >
Note that one of the reasons why this is insecure is because EC point addition is invertible. EC-scalar multiplication is not, thus why EC Diffie-Hellman is secure even when this timing asymmetry exists.
A good cryptosystem doesn't have strange restrictions, like "your public key can only be public sometimes, but needs to protected like your private key other times." If you have to worry about things like that, you're doing it wrong :) And why we always recommend sticking to well-known, well-studied operations.
-Alan
On 03/08/2014 03:51 AM, Edmund Edgar wrote:
Quoted text (51 lines)
> On 8 March 2014 17:10, Alan Reiner <etotheipi@gmail•com > <mailto:etotheipi@gmail.com>> wrote: > > > I create a new keypair, <c_pub> with <c_priv> which I know (it can > be any arbitrary key pair). But I don't give you <c_pub>, I give > you <b_pub> = <c_pub> minus <a_pub> (which I can do because I've > seen <a_pub> before doing this). > > Sure, I don't know the private key for <b_pub>, but it doesn't > matter... because what > > <b_pub> + <a_pub> = <c_pub> (mine) > > You have no way to detect this condition, because you don't know > what c_pub/c_priv I created, so you can only detect this after > it's too late (after I abuse the private key) > > > Thanks Alan and Forrest, that makes sense. So to salvage the situation > in the original case, we have to make sure the parties exchange their > public keys first, before they're allowed to see the public keys > they'll be combining them with. > > -- > -- > Edmund Edgar > Founder, Social Minds Inc (KK) > Twitter: @edmundedgar > Linked In: edmundedgar > Skype: edmundedgar > http://www.socialminds.jp > > Reality Keys > @realitykeys > ed@realitykeys•com <mailto:ed@realitykeys.com> > https://www.realitykeys.com > > > ------------------------------------------------------------------------------ > Subversion Kills Productivity. Get off Subversion & Make the Move to Perforce. > With Perforce, you get hassle-free workflows. Merge that actually works. > Faster operations. Version large binaries. Built-in WAN optimization and the > freedom to use Git, Perforce or both. Make the move to Perforce. > http://pubads.g.doubleclick.net/gampad/clk?id=122218951&iu=/4140/ostg.clktrk > > > _______________________________________________ > Bitcoin-development mailing list > Bitcoin-development@lists•sourceforge•net > https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Note that one of the reasons why this is insecure is because EC point addition is invertible. EC-scalar multiplication is not, thus why EC Diffie-Hellman is secure even when this asymmetry exists.
A good cryptosystem doesn't have strange restrictions, like "your public key can only be public sometimes, but needs to protected like your private key other times." If you have to worry about things like that, you're doing it wrong :)
-Alan
On 03/08/2014 05:37 AM, Joel Kaartinen wrote:
Quoted text (76 lines)
> If both parties insist on seeing a hash of the other party's public > key before they'll show their own public key, they can be sure that > the public key is not chosen based on the public key they themselves > presented. > > Although, I have to wonder, why not just use multisig? > > - Joel > > On 08.03.2014 10:51, Edmund Edgar wrote: >> On 8 March 2014 17:10, Alan Reiner <etotheipi@gmail•com >> <mailto:etotheipi@gmail.com>> wrote: >> >> >> I create a new keypair, <c_pub> with <c_priv> which I know (it >> can be any arbitrary key pair). But I don't give you <c_pub>, I >> give you <b_pub> = <c_pub> minus <a_pub> (which I can do because >> I've seen <a_pub> before doing this). >> >> Sure, I don't know the private key for <b_pub>, but it doesn't >> matter... because what >> >> <b_pub> + <a_pub> = <c_pub> (mine) >> >> You have no way to detect this condition, because you don't know >> what c_pub/c_priv I created, so you can only detect this after >> it's too late (after I abuse the private key) >> >> >> Thanks Alan and Forrest, that makes sense. So to salvage the >> situation in the original case, we have to make sure the parties >> exchange their public keys first, before they're allowed to see the >> public keys they'll be combining them with. >> >> -- >> -- >> Edmund Edgar >> Founder, Social Minds Inc (KK) >> Twitter: @edmundedgar >> Linked In: edmundedgar >> Skype: edmundedgar >> http://www.socialminds.jp >> >> Reality Keys >> @realitykeys >> ed@realitykeys•com <mailto:ed@realitykeys.com> >> https://www.realitykeys.com >> >> >> ------------------------------------------------------------------------------ >> Subversion Kills Productivity. Get off Subversion & Make the Move to Perforce. >> With Perforce, you get hassle-free workflows. Merge that actually works. >> Faster operations. Version large binaries. Built-in WAN optimization and the >> freedom to use Git, Perforce or both. Make the move to Perforce. >> http://pubads.g.doubleclick.net/gampad/clk?id=122218951&iu=/4140/ostg.clktrk >> >> >> _______________________________________________ >> Bitcoin-development mailing list >> Bitcoin-development@lists•sourceforge•net >> https://lists.sourceforge.net/lists/listinfo/bitcoin-development > > > > ------------------------------------------------------------------------------ > Subversion Kills Productivity. Get off Subversion & Make the Move to Perforce. > With Perforce, you get hassle-free workflows. Merge that actually works. > Faster operations. Version large binaries. Built-in WAN optimization and the > freedom to use Git, Perforce or both. Make the move to Perforce. > http://pubads.g.doubleclick.net/gampad/clk?id=122218951&iu=/4140/ostg.clktrk > > > _______________________________________________ > Bitcoin-development mailing list > Bitcoin-development@lists•sourceforge•net > https://lists.sourceforge.net/lists/listinfo/bitcoin-development