Elliptic curve math question

[etotheipi]

I agree that your proposal would also work for the coin application.  But since your only objection to the proposed point addition method is based on the incorrect assumption that it requires that one or more of the public keys be kept secret do you now agree that the proposed point addition system will also work?

That's embarassing, I rushed through the thread and totally misunderstood the proposed solution.   My apologies.

You're right it doesn't require keeping public keys secret, but it doesn't change my objection to it.   As Mike Hearn suggested, it's a mistake to not use "established" techniques for any cryptographic protocol.  Is point addition an established technique for a secure system (I'm not familiar with it, but maybe it is)?   Just because an insecurity isn't obvious doesn't mean it's not there.  There's all sorts of creative math that has been used to break crypto schemes, and the only way to "be sure" is to use established techniques.

And the fact is there is already an established scheme:  which is using point multiplication as described multiple times before.  Diffie-Hellman shared-secret techniques have been established as secure, and if you have ECC-math module on your system, you can use it just as easily.  There's no reason to risk using point-addition when there's a widely-accepted alternative that gets you the same thing.  (In fact, the point multiplication adds a little bit of extra anonymity, since the tx with point addition can be identified with anyone having both public keys.  The multiplication tx can only be identified by someone with one of the private keys.)

Publishing private keys or other secrets after a transaction is a standard part of some sound cryptographic protocols.  For example, Off-the-record messaging protocol publishes secret MAC keys as soon as those keys have expired (allowing deniable authentication).  Similarly, a Bitcoin contract for trading across chains publishes a secret to finalize the transaction.
...
All cryptographic protocols can be ruined by things going wrong.  A bad Bitcoin implementation might accidentally broadcast private keys on IRC.  That doesn't mean the Bitcoin protocol is flawed.

The examples you speak of are protocols where your keys are expected to be revealed at the end of the exchange.  But, up to this point in Bitcoin, people reuse private keys all the time with the assumption they remain private.  Removing that assumption changes the security model for application developers and users.  As an app developer, I don't want to have to deal with simultaneously maintaining a set of private keys are okay to reuse, and a set of keys that are a guaranteed fail if I re-use them.  Sure, it can be done, but it's extra complexity in security-sensitive software.

[BurtW]

After thinking about it a bit there is a pretty big difference between the two systems when extrapolated to 3 or more parties.

The point addition system can be done in parallel.

Assume five parties all publish their public keys to each other (and the world).  These five public keys are a*G, b*G, c*G, d*G and e*G where a, b, c, d, and e are the five private keys.
Now all five parties immediately have eveything they need to calculate the shared public key = a*G + b*G + c*G + d*G + e*G = (a + b + c + d + e)*G

In the other proposed system the calculation of the shared public key cannot be done in parallel, each party must calculate the next point from the previous point

Code:

A sends a*G to B         B calculates b*a*G
B sends b*a*G to C       C calculates c*b*a*G
C sends c*b*a*G to D     D calculates d*c*b*a*G
D sends d*c*b*a*G to E   E calculates e*d*c*b*a*G

This is perfect for where this is what you want:  for each party to have to send the result of their calculation on to the next party and for the final party to be the only one to know the final public key.  However for our use case we do not need or want this.

I am still looking for a citation regarding the use of point addition.  Will let you know when I find it.

[BurtW]

As an app developer, I don't want to have to deal with simultaneously maintaining a set of private keys are okay to reuse, and a set of keys that are a guaranteed fail if I re-use them.  Sure, it can be done, but it's extra complexity in security-sensitive software

Mt. Gox already does this.  If you import a private key into your Mt. Gox account they immediately move all BTC from it and will never re-use it.  However, they do have a nice sweep feature.  If you turn it on then they will automatically sweep any coins sent to that address off it into your account.  So if the private key has been or ever is compromised and someone is foolish enough to send it BTC then they get automatically claimed.

I have imported many private keys into my Mt. Gox account - especially every publicly available private key found on this forum and on the wiki - in the hopes that someone will send it some coins on a whim, then they will be mine all mine <insert maniacal laughter here>

[Meni Rosenfeld]

Is point addition an established technique for a secure system (I'm not familiar with it, but maybe it is)?   Just because an insecurity isn't obvious doesn't mean it's not there.

It seems trivial to prove that if ECDSA is secure then so is the addition scheme (though of course this has to be vetted by someone who is actually experienced with these things): Suppose that given A and (A+B)*G we can deduce A+B. Now let's say we have some arbitrary public key C*G. Generate a random A. C = A + (C-A) so by assumption we can find C.

And the fact is there is already an established scheme

There is an established scheme for an application which is not identical to this. There's no reason we shouldn't make use of known primitives to create new applications. Again, I agree that the uninitiated could miss something even when the recombination seems trivial - so we should ask someone about it, but not wait for someone to write a paper about such trivialities.

P.S. -- I am very interested in ways that an (A and B) transaction could be created using "responsible" cryptography, but so far no one has suggested a way.  Such as a way for Alice to only compute the combined private key with her own private key and Bob's signature (or vice versa)...

This is in the works (assuming you meant "compute the combined signature").

[BurtW]

It seems trivial to prove that if ECDSA is secure then so is the addition scheme (though of course this has to be vetted by someone who is actually experienced with these things): Suppose that given A and (A+B)*G we can deduce A+B. Now let's say we have some arbitrary public key C*G. Generate a random A. C = A + (C-A) so by assumption we can find C.

This is basically what I was thinking and was going to write up basically the same proof but then thought - well that would just be bwagner again saying that I think it is secure which I have already done numerous times.

What we need is a known "expert" to say it.

[etotheipi]

I suppose I could've gotten out pencil and paper and done exactly what you did, instead of ranting about it.  Your proof looks valid, using a typical proving method:  if this was insecure, so would ECDSA, so it must be at least as secure as other ECDSA operations.

But I still don't know why you wouldn't use the DHSS method, since it is established, and you don't need convince someone "I'm pretty sure this proof is correct."  Anyone can look up DHSS and see that it is an accepted method for doing what you are trying to do.  It's no harder to apply than point addition and even has a little bit of extra anonymity.

-Eto

[pc]

I think the question is the reversibility of EC addition. And I know almost nothing about EC crypto, so perhaps the terms are what's confusing me, but if Alice and Bob each have a private key (PrivA and PrivB), tell each other their public key (PubA and PubB, and they create a combined public key (PubA+PubB) and send coins to it, is it possible for Bob to subtract Alice's public key from Bob's to get the difference, and then apply that some difference to his private key to get Alice's private key and take the coins without Alice's consent? (PrivA=(PrivB-(PubB-PubA)) or something?)

It seems that all of EC crypto is based on many of these operations being irreversible, so I guess I'm just asking if the point addition being talked about fits in that category.

[BurtW]

is it possible for Bob to subtract Alice's public key from Bob's to get the difference, and then apply that some difference to his private key to get Alice's private key and take the coins without Alice's consent? (PrivA=(PrivB-(PubB-PubA)) or something?)

No.  You cannot mix public key addition/subtraction and private key addition/subtraction, they are two totally different things.  Public key addition is the defined addition operation on the eliptical group - it is a fairly complex operation and unlike regular addition.  You are adding two points from the elliptical group to get a third point.  Private key addition is the simple modulo addition defined for the finite field.  Apples and oranges.

[mndrix]

But I still don't know why you wouldn't use the DHSS method...

For casascius' original question, I agree that Diffie-Hellman is the best solution.  However, some of the other protocols described above need onlookers to calculate the same public key as Alice and Bob without knowing either party's private key.  As far as I can tell, DH won't work for those protocols, but EC addition will.

[BurtW]

After much thought I agree that we should abandon the point addition system and use the serial point creation system instead.  Here is why:

This is the proposed point addition system as used by Mike, who is assumed to be trustworthy
The customer creates public key C and private key c where C = c*G
Mike creates public key M and private key m where M = m*G
The customer sends public key C to Mike and Mike creates the final public key F = C + M = c*G + m*G = (c + m)*G
Mike transfers the BTC to the key pair F = (c + m)*G and ships the product to the customer along with the public key M and the private key m (under the hologram)
The customer can verify that C + M = F and also verify that the BTC are stored on F, all is well.
When the time comes the customer can claim the BTC using c + m

But what about Mike’s evil twin brother Ekim?
Again, the customer creates public key C and private key c where C = c*G
Ekim creates public key E and private key e where E = e*G
The customer sends public key C to Ekim but instead of creating the correct public key F = C + E, Ekim instead creates a pseudo public key P where C + P = E, in other words P = E - C
Ekim now transfers the BTC to the key pair he created E = e*G and ships the product to the customer along with the fake public key P and nothing under the hologram
Since the pseudo public key P was created as P = E – C the customer will be able to verify that C + P = E and also be able to verify that the BTC are stored on E, so the customer thinks that all is well!
When the time comes the customer looks under the hologram and discovers there is no key (or a bogus key) and they have been ripped off.  Ekim can move the BTC from E at any time since he knows e.

Now let’s try the same scenario using the serial point creation system
The customer creates public key C and private key c where C = c*G
Mike creates public key M and private key m where M = m*G
The customer sends public key C to Mike and Mike creates the final public key F = m*C = m*c*G
Mike transfers the BTC to the key pair F = m*c*G and ships the product to the customer along with the public key M and the private key m (under the hologram)
The customer can verify that F = c*M = c*m*G and also verify that the BTC are stored on F, all is well.
When the time comes the customer can claim the BTC using c*m

But what about Mike’s evil twin brother Ekim?
Again, the customer creates public key C and private key c where C = c*G
Ekim creates public key E and private key e where E = e*G
The customer sends public key C to Ekim.  Now in order to pull the same scam Ekim would want to be able to pass off his personal key pair E = e*G as the final keys and load the BTC on to E for later recovery.
In order to do that he needs to have the pseudo public key necessary to fool the customer.
The customer is going to attempt to verify the pseudo key P by calculating E = c*P
But there is no way that Ekim can calculate P because Ekim does not know c.

Ekim will have to turn over a new leaf and be more like his brother Mike.

EDIT:  Note that this is not a cryptographic weakness in the point addition method - it is a fraud vector that does not exist in the point "multiplication" system.

[Meni Rosenfeld]

This is the proposed point addition system as used by Mike, who is assumed to be trustworthy
The customer creates public key C and private key c where C = c*G
Mike creates public key M and private key m where M = m*G
The customer sends public key C to Mike and Mike creates the final public key F = C + M = c*G + m*G = (c + m)*G
Mike transfers the BTC to the key pair F = (c + m)*G and ships the product to the customer along with the public key M and the private key m (under the hologram)
The customer can verify that C + M = F and also verify that the BTC are stored on F, all is well.
When the time comes the customer can claim the BTC using c + m

I don't think that's the proposal. I thought the point with casascius coins is that you can pay with them, with the active ingredient being that the private key is hidden but with Mike's seal that it is valid. If redeeming a coin requires the private key of the customer who originally ordered the coin, he can't pay with it to another party.

My interpretation of the proposal is: Mike generates a key m and has a business partner who generates a key b. The partner creates a "mini-coin" with b hidden and B exposed, so that b can only be found if the minicoin is evidently opened. Mike embeds the minicoin in his own coin with m hidden and M+B exposed. To redeem the coin it needs to be opened completely to expose m and b and thus m+b. This way, the bitcoins can only be stolen if either:

1. Mike and the partner collude, which is assumed to be unlikely, or
2. Mike opens minicoins before embedding them and scrapes b, which can be detected by sampling Mike's coins and verifying that the minicoin is intact.

Note that sampling needs to be done anyway to verify that coins indeed contain the promised private key. Mike will also need to sample the minicoins of his partner before he commits to embedding them in a coin sealed by himself.

This can be extended to multiple partners each submitting their own minicoin, all of them being embedded in a single coin by Mike.

[BurtW]

Yes, there are two proposals floating around.  In one scenario the customer generates a key pair so the customer is certain that they, and only they, have half the puzzle.  The other proposal is for Mike to do half and some other trusted entity to do the other half and the customer does nothing until redemption time.  Both are being discussed and I think both are valid use cases.

The fraud vector outlined above applies to both use cases and the use of the serial key creation sytem instead of the point addition system eliminates this fraud vector in both use cases.

[etotheipi]

Wow, nice work bwagner!  It sounds like the flaw has to do with the fact that point addition is easily invertible, allowing someone to "invert" your public key before using it.   They would have to have your private key (or solve a discrete log problem) in order to do the same thing in DHSS.

[BurtW]

Yes, and I have to admit that my thought process was inspired by the following question so some of the credit goes to pc for asking the "stupid" question.  I answered the question but it got me to thinking...

I think the question is the reversibility of EC addition. And I know almost nothing about EC crypto, so perhaps the terms are what's confusing me, but if Alice and Bob each have a private key (PrivA and PrivB), tell each other their public key (PubA and PubB, and they create a combined public key (PubA+PubB) and send coins to it, is it possible for Bob to subtract Alice's public key from Bob's to get the difference, and then apply that some difference to his private key to get Alice's private key and take the coins without Alice's consent? (PrivA=(PrivB-(PubB-PubA)) or something?)

It seems that all of EC crypto is based on many of these operations being irreversible, so I guess I'm just asking if the point addition being talked about fits in that category.

[casascius]

I don't have any significant efforts invested into addition that cannot be easily switched to multiplication, so this should not be a problem with respect to my coins.

I expect that to create two-part physical bitcoins, I would simply take private key circles out of my secure repurposed Nutella jar, use the series 1 hologram which covers it entirely, calculate the composite bitcoin address, and laser the resulting address on the outside of the hologram.  That's time consuming, but not unreasonable for the gold coin since there won't be that many of them.

[BurtW]

EDIT:  I guess this is an answer to a question that disappeared while I was answering it!  O well I will leave it here for anyone who has the same question.

The argument is subtle.  First we are not talkikng about Mike, we are talking about Ekim - and he is out to rip off the customer (being Mike's evil twin brother).

On purpose he is funding the key E (which he totally controls with the private key e).  He is planning to take the BTC back at a later time.

The plan is to lie and tell the customer that his key E is the final combined key.

To do this he calculates P = E - C and lies and tells the customer that P is his public part of the two part key chain being used to secure the BTC.  Liar - he does not even know the private key for P (and can't)!

So everything is set up.  Ekim ships the item to the customer claiming that P is his public key and claims to have put the corresponding private key p under the hologram.  He has not since he does not even know p.  He also lies and says that E is the final combined key.

The customer gets the item and the two public keys P and E.  The customer is sophisticated and careful so they check everything out.

First they check to make sure the BTC they ordered are on the combined key.  He looks in the block chain for key E and yes the BTC are there.

Next he wants to make sure that the public keys add up so he calculated C + P and yes it does equal E!

So the customer is happy and thinks everything is ok - but it is not.  Ekim controls the BTC and the customer has no way to get the BTC.

[casascius]

I deleted it because I realized I had misunderstood.

You are right.

[mndrix]

But what about Mike’s evil twin brother Ekim?
Again, the customer creates public key C and private key c where C = c*G
Ekim creates public key E and private key e where E = e*G
The customer sends public key C to Ekim but instead of creating the correct public key F = C + E, Ekim instead creates a pseudo public key P where C + P = E, in other words P = E - C
Ekim now transfers the BTC to the key pair he created E = e*G and ships the product to the customer along with the fake public key P and nothing under the hologram
Since the pseudo public key P was created as P = E – C the customer will be able to verify that C + P = E and also be able to verify that the BTC are stored on E, so the customer thinks that all is well!
When the time comes the customer looks under the hologram and discovers there is no key (or a bogus key) and they have been ripped off.  Ekim can move the BTC from E at any time since he knows e.

Academic observation: In this scenario, the customer is safe if Ekim commits to E before C is revealed (by publishing a hash of E, for example).

[BurtW]

I did think of this and thought of it this way:  If both parites send their public keys to each other at the start of the protocol and they "cross in the mail" then the system is secure because there is now agreement on which two keys are to be added together to create the final public key.

I guess there may be a way to ensure this "crossing in the mail" but what if Ekim is very clever and so on...

[casascius]

I did think of this and thought of it this way:  If both parites send their public keys to each other at the start of the protocol and they "cross in the mail" then the system is secure because there is now agreement on which two keys are to be added together to create the final public key.

I guess there may be a way to ensure this "crossing in the mail" but what if Ekim is very clever and so on...

They can cross in the mail by the two sending each other the hashes of their pre-generated public keys, sharing them only after both have confirmed receipt of the hashes.