Topic: Elliptic curve math question (Read 14040 times)

We are discussing degrees of security or probability of encountering an attack. The easier an attack is the more likely it will occur.

Sorry... in other words Casascius is "raising the stakes".

To be properly paranoid you could take the list of public keys from Casascius along with the private keys you generated on the pwned machine using the bitaddress-like service and re-run them through the bitaddress-like service on a different computer to double check the calculation of the combined bitcoin address.

I think this novel idea can significantly increase the security of paper wallets against malware, especially once bitcoin goes mainstream.

Well, if it's really filthy rooted pwned, with an attack that is aware of bitcoins and how this system/site works, the malware could just replace the real pubkeys/addresses on the paper wallet that's being generated so that instead of corresponding to the combo of private keys, just corresponds to a private key the attacker controls. It'll stop a generic packet or key logger or the like, but if you really can't trust your computation device, then I don't see how you can trust that your output is right.

to make sure that i understand this better, please clarify this.  re-running the bitaddress-like service against the same text file will create different bitcoin addresses, right?  i.e., the output of the bitaddress-like service is non-deterministic?

So here's how that might work.

• I sell a "half paper wallet" on my website.
• Each half paper wallet has 7 QR coded private keys, they are individual stickers.  Each sticker has a short ID code (maybe 8 characters) that ensures they place the right sticker on the right place on their final paper wallet.  The ID code is based on the hash of the pubkey, but isn't a bitcoin address (to avoid confusion).
• The product also shows a URL, example, casascius.com/pw/9F281BCA398D.txt.  There is one URL per sheet sold.  This text file contains the pubkeys for all the privkeys on the page.
• A service, conceptually similar to BitAddress.org, will http get that file (or offer a place to paste it, if network access is disallowed), and use the pubkeys to construct the paper wallet.  Each address on the paper wallet will have a spot to place my stickers.  It will recompute the same ID numbers from the pubkeys, so the user can assure themselves they are putting their stickers in the right place

The end result?  Pretty much bulletproof paper wallet.  Nobody can steal the funds!  Not even if I decide to be a crook, or if they produce their paper wallet on a filthy rooted pwned machine.

This makes sense, and is what I was looking for.  Thanks!

I wanted to experimentally create a service where I am "B" and mail out stickers to stick on paper wallets produced by (or printed from website) A.  My sticker would have a second private key and the combined Bitcoin address.

Or perhaps even better, where I am "A", and someone uses a website to print their paper wallet "B", and sticks my stickers on their page.  (That way, I'm not responsible for calculating the final Bitcoin address, which would be a potential scam vector.)

Mike,

The two party scheme I think you are working on should be:

You can add points together--that is the core operations of ECC math.  Scalar multiplication is just an extension of that.  If you have point P, then 5*P is just P+P+P+P+P.  There is no such thing as point-to-point mulitplication.

There is no defined multiply operation on the eliptical curve group (hence group).

Why are you trying to muliply points?

OK, so random question... how do you multiply a point by a point?

I understand multiplying a point by a scalar value... but I have no concept of multiplying two points together, neither does BouncyCastle offer any function in its "point" class that multiplies the point by another point.

What am I misunderstanding?  Thanks in advance.

It doesn't hurt, but I'm not sure how much it helps.  The multiplication scheme (DHSS) is used all the time with with pre-published, persistent identities/keys on the internet, all the time.  I think the point here, was, that DHSS is established and you can feel comfortable using it in the ways prescribed by NIST, etc (which doesn't recommend any precautions with respect to public key exchange).  If someone was smart enough to find a mathematical hole in DHSS based on public key exchange, then they're smart enough to realize that there are much more profitable targets to be exploited around the globe than a $3,000 casascius gold bar...

Just thinking about the attack vector, realizing that E and C could be reversed.  A customer could use the same scheme to acquire an intact Casascius coin with no funds, if I were to offer to have done a two-key coin, and had acquiesced to a request to provide my intended public key first.  Having that happen would be non-amusing, so, I suppose I am appreciative to have been made aware of it before ever having produced any.

I suppose that if I offer a two-party key scheme, I might do well not only to use multiplication, but to insist on a mutual commitment of public keys via exchanging hashes first, so that neither party has the opportunity to base their public key on the one they received.

This isn't a problem with generating a public key from adding two other public keys, but rather with some specific applications. I for one thought we were talking about making casascius coins - if they're not manufactured according to spec all bets are off, which is why they need to be sampled anyway, which would detect attacks like the one described.

(I don't disagree with your main point though.)

The recently explained security flaw resulting from adding public key points to derive a common public key is the one I had in mind in my original post.

A number of forum members seemed to have convinced themselves of the security of the scheme and I hope that this episode encourages people to be less confident and more cautious about "novel" cryptographic constructions.

I believe it's possible to recover the security of the scheme without resorting to a two-round system in which the hashes are published and then the public keys revealed. This is achieved as follows:

1) The participants publish the hashes (or equivalently addresses) of public keys for which signatures have been seen in the block chain.
2) The software scans the signatures in the block chain for the relevant public keys and the combined public key is formed by addition.

This scheme is secure against the attack outlined (in a somewhat garbled fashion) in this post because Ekim is unable to create signatures with the key he broadcasts (P in the post's terminology).

ByteCoin

Yup.  A slight optimization allows the first party that receives a public key hash to immediately respond with his own public key, without awaiting confirmation.  Because publishing a public key is contingent on receiving a hash, it can be viewed as confirmation and commitment in one.

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.

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

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

I deleted it because I realized I had misunderstood.

You are right.

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.

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.