--- Log opened Fri Sep 27 00:00:19 2013
18:12 < gmaxwell> so, I've come up with a way of exploiting ECDSA on the basis of controlling the generator.
18:13 < gmaxwell> basically, if you select G to be some multiple of someones public key, then you can forge signatures as being from that public key, without ever knowing the private key.
18:14 < gmaxwell> I don't think this is a problem for us, since of course all our pubkeys would be generated after the generator was fixed. :)
18:14 < gmaxwell> But there you go.
18:17 < sipa> so, say there is a secret private key x
18:17 < sipa> then you choose G to be n times ... what?
18:18 < sipa> G = n * (x * G) ...
18:18 < sipa> ok, so n has to be 1/x
18:19 < sipa> how can you do that without knowing x?
18:20 < gmaxwell> sipa: no no, say there is an existing public key P.  (forget how it was generated). I can pick the generator as P*X  for some X and then sign messages as P even though I do not know P's discrete log.
18:21 < gmaxwell> (perhaps P is some nothing up my sleeve number)
18:23 < sipa> but P = G * p
18:24 < sipa> (whether you know p or not)
18:24 < sipa> i'm just saying that the notion of a public key sounds meaningless without having the generator
18:25 < gmaxwell> Right it's not really a 'public key' anymore. It's just an "apparent public key"
18:26 < gmaxwell> for example. Say bitcoin was stupid and send "expired coins" to a pubkey of SHA256("expired").  I could pick G so that I could spend those coins.
18:27 < sipa> ok, say you have P
18:28 < sipa> a valid point on the curve
18:28 < sipa> now you choose G to be n*P
18:28 < sipa> then by definition, P's corresponding private key becomes 1/n
18:29 < sipa> or in other words, by choosing G, you're choosing P's private key
18:29 < sipa> ... of course you're able to spends coins using it, then
18:30 < gmaxwell> Yea, did we really know this before?  At least before figuring this out, I thought the only thing you could do by controlling G is forge the signature of a single message.
18:31 < sipa> right
18:31 < sipa> no, i actually never realized that
18:32 < sipa> the realization is that if you're choosing G in terms of an existing public key (however generated), that public key's private key becomes apparent
18:33 < sipa> so, we should actually demand that the generator point has some property that makes it unlikely to be the multiple of something known
18:33 < sipa> why isn't G something like (0x333333333333...33333, <whatever needer>)
18:35 < gmaxwell> or just (1,whatever) + (whatever,1) ?
18:35 < sipa> right
18:35 < sipa> SO
18:35 < gmaxwell> yea, I have no idea. Its irritating. I won't disclose how much time I've spent thinking about this purely because I can't see why the generator isn't some obvious value— or at least chosen for performance.
18:35 < sipa> satoshi works for certicom
18:37 < gmaxwell> yea, I can't figure out any attack for this which is at all interesting. We have no nothing up my sleeve pubkeys in bitcoin. We never use pubkeys from other systems as our pubkeys, etc.
18:38 < sipa> right
18:39 < sipa> all it can do is make an apparent nothing-up-my-sleeve number in fact not be a black hole
18:39 < sipa> but that's all it could be in bitcoin: a proven black hole
18:39 < gmaxwell> if 1bitcoineaterdontspend were really a pubkey (if we even had addresses for pubkeys) then I could have made it so those coins were spendable.
18:40 < sipa> yup
18:40 < sipa> for one single address
--- Log closed Sat Sep 28 00:00:22 2013