Re: [Bitcoin-development] Is this a safe thing to be doing with ECC addition? (Oracle protocol)

Re: [Bitcoin-development] Is this a safe thing to be doing with ECC addition? (Oracle protocol)

[Edmund Edgar]

[-- Attachment #1: Type: text/plain, Size: 963 bytes --]

On 4 March 2014 14:07, Odinn Cyberguerrilla <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

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

[-- Attachment #2: Type: text/html, Size: 1899 bytes --]

Re: [Bitcoin-development] Is this a safe thing to be doing with ECC addition? (Oracle protocol)

[Alan Reiner]

[-- Attachment #1: Type: text/plain, Size: 1504 bytes --]

On 03/08/2014 01:55 AM, Edmund Edgar wrote:
> 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

[-- Attachment #2: Type: text/html, Size: 3069 bytes --]

Re: [Bitcoin-development] Is this a safe thing to be doing with ECC addition? (Oracle protocol)

[Edmund Edgar]

[-- Attachment #1: Type: text/plain, Size: 1077 bytes --]

On 8 March 2014 17:10, Alan Reiner <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
https://www.realitykeys.com

[-- Attachment #2: Type: text/html, Size: 1963 bytes --]

Re: [Bitcoin-development] Is this a safe thing to be doing with ECC addition? (Oracle protocol)

[Joel Kaartinen]

[-- Attachment #1: Type: text/plain, Size: 2210 bytes --]

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


[-- Attachment #2: Type: text/html, Size: 4695 bytes --]

Re: [Bitcoin-development] Is this a safe thing to be doing with ECC addition? (Oracle protocol)

[Adam Back]

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.

Re: [Bitcoin-development] Is this a safe thing to be doing with ECC addition? (Oracle protocol)

[Natanael]

[-- Attachment #1: Type: text/plain, Size: 1918 bytes --]

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

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

[-- Attachment #2: Type: text/html, Size: 2730 bytes --]

Re: [Bitcoin-development] Is this a safe thing to be doing with ECC addition? (Oracle protocol)

[Alan Reiner]

[-- Attachment #1: Type: text/plain, Size: 3439 bytes --]

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


[-- Attachment #2: Type: text/html, Size: 6905 bytes --]

Re: [Bitcoin-development] Is this a safe thing to be doing with ECC addition? (Oracle protocol)

[Alan Reiner]

[-- Attachment #1: Type: text/plain, Size: 2462 bytes --]

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


[-- Attachment #2: Type: text/html, Size: 4974 bytes --]

[Bitcoin-development] Is this a safe thing to be doing with ECC addition? (Oracle protocol)

[Edmund Edgar]

[-- Attachment #1: Type: text/plain, Size: 2735 bytes --]

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

[-- Attachment #2: Type: text/html, Size: 3805 bytes --]

Re: [Bitcoin-development] Is this a safe thing to be doing with ECC addition? (Oracle protocol)

[Odinn Cyberguerrilla]

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



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