Topic: Elliptic curve math question - page 2. (Read 14040 times)

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

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.

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.

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.

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.

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.

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.

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.

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

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.

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.

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.

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

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

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


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.

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


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.

In summary there are two possible ways this can be done.  In both systems you need both private keys to spend the money.  In one system you would add the two private keys together to get the private key needed to spend/transfer the funds, in the second system you would muliply the two keys together in order to get the final private key needed to spend the funds.  I believe either system will work and that the addition is slightly easier.

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.

Agree.  

Agree.  However, there is nothing in the proposed two key system that requires that any public key be kept secret.  All three public keys a*G, b*G and (a+b)*G are, at all times, publicly available keys.  Knowing all three public keys give you no new information.  Anyone can use point addition or point subtraction to calculate any one of the three from the other two but that is pointless (grin) since all three are public keys anyway.

Agreed. This would work.  And you have just created a shared key that only Alice and Bob can know, yes.  But since this shared key is going to be a public key why does it need to be a shared secret?

Agreed.  This would work.  However the proposed point addition system will also work just as well.  

True.

Agree with the general statement.  However what is being discussed here assumes the key pair is going to be used one time for a specific purpose.

There is nothing in the proposed point addition scenario that requires any of the points (pubic keys) to be held as secrets.  Where did you get that idea?  

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?

Me too.

Finally had some time to look at this, and I'm not impressed with the talk of point-addition:   as ByteCoin suggested, there is not a "robust" way to use point addition to secure anything.  Point addition on a given curve (where everyone knows the parameters, like secp256k1) is easily invertible.  Point subtraction is only slightly slower than point addition.  

Additionally, it is very unwise to rely on any method that requires keeping public keys secret.  This goes against the grain of cryptography, and creates a headache for those of us client developers that justifiably leave public keys unencrypted in wallets.  You can argue that some special CONOPS (concept of operations) designed for this application will help, but it's just not good cryptography.  Don't do it.

Going back to casascius' original idea:  you CAN use Diffie-Hellman shared-secret techniques to SECURELY create a shared key.  If Alice has (a, a*G) and Bob has (b, b*G), then by publicly broadcasting their public keys, Alice and Bob can both compute the elliptic curve point (a*b*G) and no one else can.   This gives us two options (in general):

(1)  (A and B)  Alice and Bob create the point (a*b*G) from each others' public keys, and use the result as a new public key.  They calculate the address hash and put it in the TxOut field of a transaction.  Then when the money needs to be spent, Alice or Bob can send the other one their private key, and then the combined private key can be computed and used to sign the inputs.  This is perfect for casascius application, but not many other applications (see below).  

(2)  (A or B)  Alice and Bob create the public key as above, and then use the x component (or combination of x and y components) to derive a new private key.  This private key can be converted to public-key/address that can be included on a transaction, and then Alice or Bob can sign for that transaction.  This isn't relevant for casascius' application, but it is cryptographically secure, and has plenty of other useful applications.

The problem with (1), in general, is that it's a terrible idea to create a crypto process that relies on exchange of private keys.  While a wallet/app will attempt to use a different private key for every transaction, there's a possibility that things go wrong -- someone else sends that private key money, a bug in their client (or someone manipulates their client)  to reuse private keys, multiple clients using the same wallet don't realize the key has been used, etc.  And a problem like this would go unnoticed by the user until someone has already exploited it.  This is in the same vein as requiring public keys to be kept private -- private keys should never have to be made public.  

Except for casascius' application:  his CONOPS already involves exchanging private keys and his software is specialized to do this correctly.  For general multi-signature protocols over the internet with untrusted parties (1) should never be used.  (2) could be used cryptographically-responsibly to replace 1-of-2 multi-sig transaction types, but that's for some other application.

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

hmmmmm.

Right, and it designed to be impossible to go directly from the public key address back to the original public key (the public key address is a fancy sha256 hash of the public key - see the above mentioned paper for the details).