Elliptic curve math question

[mndrix]

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.

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.

[ByteCoin]

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

[Meni Rosenfeld]

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.

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

[casascius]

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.

[etotheipi]

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.

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

[casascius]

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.

[BurtW]

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

Why are you trying to muliply points?

[etotheipi]

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.

[BurtW]

Mike,

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

Code:

A has private key a and sends public key a*G to B [scalar mult]
B has private key b and calculates new public key b*(a*G) from public key a*G [scalar mult]

Ending private key is b*a (simple modulo multiplication)
  But not known to either A or B, only knowable by someone once they have both a and b
Ending public key is b*a*G

[casascius]

Mike,

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

Code:

A has private key a and sends public key a*G to B [scalar mult]
B has private key b and calculates new public key b*(a*G) from public key a*G [scalar mult]

Ending private key is b*a (simple modulo multiplication)
  But not known to either A or B, only knowable by someone once they have both a and b
Ending public key is b*a*G

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

[casascius]

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.

[koin]

This text file contains the pubkeys for all the privkeys on the page.

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?

[pc]

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.

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.

[pointbiz]

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.

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.

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.