--- Day changed Sun Sep 27 2015
00:49 -!- adam3us [~Adium@host-92-19-14-134.as13285.net] has joined #secp256k1
01:12 <@gmaxwell> sipa: ...  so, secp256k1_ec_pubkey_parse  with a null pointer for the string. Assuming the illegal argument callback has been no-opped. ... right now we do not zero-initilize the pubkey output. I think we should. Thoughts?
01:13 <@gmaxwell> uh by right now I mean in my codebase... IIRC master has no argument checks on that entrypoint at all.
01:30 <@sipa> oh!
01:30 <@sipa> i think we should fix that
02:11 -!- adam3us [~Adium@host-92-19-14-134.as13285.net] has quit [Quit: Leaving.]
03:52 -!- GAit [~GAit@2-230-161-158.ip202.fastwebnet.it] has joined #secp256k1
04:10 <@gmaxwell> sipa: fixed locally... almost done with a set of ec_parse tests.
04:10 <@gmaxwell> but I need to sleep.
04:31 <@sipa> gmaxwell: uh, i think we should make changes to what parse accepts, to be better specified, and split up lax vs strict der
06:08 -!- jtimon [~quassel@160.28.134.37.dynamic.jazztel.es] has joined #secp256k1
07:00 <@sipa> assumption: given a point A for which you don't know the private key, you can't choose X and y such that A + H(X)*X == y*G
07:01 <@sipa> gmaxwell, andytoshi: correct? ^
07:15 <@sipa> if so, a solution to the multisigning problem where one can choose their public key to cancel out other's keys is solved by using the sum H(A)*a + H(B)*b + ... of the keys, instead of a simple sum
07:18 <@sipa> takes 2^128 i think... you can build tables of H(X)*X and of A+y*G independently and do a collision search
07:18 <@sipa> work
07:55 <@sipa> gmaxwell: for trhe zero initialization, perhaps it is best to memset the output to zero before doing any other checks?
07:55 <@sipa> gmaxwell: that removes the e special case necessaity, and removes a conditional
08:43 -!- GAit [~GAit@2-230-161-158.ip202.fastwebnet.it] has quit [Quit: Leaving.]
08:53 -!- btcdrak [uid115429@gateway/web/irccloud.com/x-mmesabtwospzgqsy] has quit [Quit: Connection closed for inactivity]
08:59 < andytoshi> sipa: your assupmption is correct, and H(X) could even be attacker-chosen. the DL has an additive factor of DL_G(A) which nobody knows
09:00 < andytoshi> ah, i see, but you need H(X) to be publically known
09:00 <@sipa> indeed
09:01 < andytoshi> and in your "A + H(X)*X == y*G" example it's X that represnts the PK that the attacker is choosing
09:03 < andytoshi> ok, understood. i think you're correct, this is 2^128 hard. it's a bit tricky to think about, i'd like some sort of reduction argument, but i don't think it'd be too difficult to come up with
09:34 <@sipa> if this works, it's sort of surprising
09:34 <@sipa> all that is required to avoid an attack is a simple transformatiin of participants' keys
09:38 < andytoshi> well, the idea is that if you change your own key you change the transformation
09:38 < andytoshi> so it's a standard "require secret knowledge to go back in time" application of a random oracle
09:52 -!- btcdrak [uid115429@gateway/web/irccloud.com/x-rzzyaepmeojtyosm] has joined #secp256k1
10:12 < Apocalyptic> andytoshi, since the curve is of prime order, if you consider H as a random oracle then the function that maps X to H(X)*X is itself a random oracle too (if you exclude X=0 of course), so choosing such X and y is as hard as computing a DLOG for A + random_point or just A, I think
10:12 < Apocalyptic> (I have no idea of the context, I assume H is a cryptographic hash function, if not disregard)
10:47 <@gmaxwell> sipa: thats what I did-- memset the output after only doing the nullness check of the buffer.
11:21 <@gmaxwell> sipa: strange that your cancellation if is possible!
11:22 <@gmaxwell> sipa: it looks right to me, then again I didn't catch that the nonce signing wasn't helpful before. (/me shame)
11:28 -!- GAit [~GAit@2-230-161-158.ip202.fastwebnet.it] has joined #secp256k1
11:52 -!- adam3us [~Adium@host-92-19-14-134.as13285.net] has joined #secp256k1
12:00 -!- GAit [~GAit@2-230-161-158.ip202.fastwebnet.it] has quit [Quit: Leaving.]
12:30 -!- GAit [~GAit@2-230-161-158.ip202.fastwebnet.it] has joined #secp256k1
12:32 -!- adam3us [~Adium@host-92-19-14-134.as13285.net] has quit [Quit: Leaving.]
12:43 -!- adam3us [~Adium@host-92-19-14-134.as13285.net] has joined #secp256k1
12:51 -!- adam3us [~Adium@host-92-19-14-134.as13285.net] has quit [Quit: Leaving.]
13:07 <@sipa> Apocalyptic: H is a cryptographic hash function, indeed
15:41 -!- GAit [~GAit@2-230-161-158.ip202.fastwebnet.it] has quit [Quit: Leaving.]
17:00 <@sipa> gmaxwell: would you hate me for rewriting ec_pubkey_parse completely?
17:01 <@gmaxwell> sipa: hah. no. does the new one pass those tests?
17:01 <@gmaxwell> I'm actually wondering if it's possible to make another implementation that does which is distinguishable from the current one. :P
17:02 <@sipa> well i would make it accept much more
17:02 <@sipa> ideally, everything i know that openssl accepts
17:02 <@gmaxwell> pubkey parse? what more does openssl accept for pubkeys?
17:02 <@gmaxwell> oh you mean not making it check the curve equation.
17:03 <@sipa> no no no
17:03  * sipa points to bip66 vulnerability disclosure
17:03 <@sipa> i want to disconnect parsing from validation
17:06 <@gmaxwell> For pubkeys there is virtually no parsing, "parsing" is basically a length check and that the first byte is 2/3 and length 33 or 4/6/7 and length 65.
17:06 <@sipa> oh
17:06 <@sipa> i mean signature parsing!
17:06 <@sipa> nvm!
17:06 <@gmaxwell> yea, I haven't touched signature parsing yet!
17:07 <@gmaxwell> Also because I know you were thinking of changing it, also because I don't look forward to actually specifying what the darn thing does.
17:07 <@gmaxwell> I do like that the pubkey parsing does point validity testing, because it means if you verify many times with the same pubkey you can avoid it.
17:12 <@sipa> yeah, i don't think that pubkey parse can be changed much without changing intented semantics
17:12 <@sipa> it's fully specified, i think
17:13 <@gmaxwell> Right, I think the PR I posted fully tests its behavior, including error conditions. Excepting those involving ctx and very large length for obvious reasons.
17:14 <@gmaxwell> Some of the tests are kind of idiotic considering the actual implementation. E.g. it exhaustively tests all 1 and 2 byte inputs. But they're fast.
17:20 <@gmaxwell> sipa: in any case, only harm a signature parser rewrite would cause me is a few cpu months fuzzing the old one. :P  no biggie.
17:21 <@gmaxwell> I really really don't look forward to writing an exact behavior test for the current one. :(
17:28 <@gmaxwell> andytoshi: [random number theory] so for our field,  if x is not square,  -x is.  Our powering ladder sqrt computes sqrt(-x) when x is not square. This surprised me.
17:28 <@sipa> woa!
17:30 <@gmaxwell> (I noticed this when I was creating test vectors for pubkey parsing. For points not on the curve I extracted what the power laddering produced in order to make points with y that would verify if you checked y using a sqrt from x^3+7 and didn't check that the input was square)...
17:31 < andytoshi> gmaxwell: interesting... if i had known the first half of that i would've guessed the sceond
17:32 < andytoshi> i wonder how useful "either x or -x is square" is
17:33 < andytoshi> like can we do the dettman co-x stuff using *both* x and -x, and avoid needing to check if the x value is a square?
17:33 < andytoshi> not co-x, x-only
17:34 <@gmaxwell> Note, I do not have a proof for this property. But I verified it on many millions of values.
17:34 < andytoshi> oh, ok, i'll work on proving it
17:34 <@gmaxwell> (also, though I didn't mention it above is x is square -x is not. Just to be clear, except for 0 of course)
17:35 < andytoshi> yeah, that's easy, cuz -1 does not have a square root
17:35 < andytoshi> oh, actually if you multiply a non-square by anything else non-square you'll get a square cuz the legendre symbols will multiply
17:35 < andytoshi> so there you go, multiplying by -1 makes a non-square a square and vice-versa
17:36 <@gmaxwell> As far as usefulness, I think it immediately results in a fast uniform hash onto points.
17:37 <@gmaxwell> otherwise, I dunno. surprised me in any case.
17:37 < andytoshi> hash onto [0, 2^256], discard if it's larger than p, use this as x, derive the point of whichever of {x, -x} gives you one, and that's the hash?
17:39 < andytoshi> also if you do a detmann xo shared secret with both x and -x then hash the concatenation of the results, this blocks low-order attacks while allowing every x value to work. it might also be faster than doing a const-time legendre check on x
17:39 <@gmaxwell> Well it's x^3 + 7 which must be square, so not quite that trivial.
17:39 <@gmaxwell> oh lol. amusing.
17:39 < andytoshi> oh right
17:40 <@gmaxwell> the trick you just described would still work, I think.  but I think it won't be faster than the check.
17:40 < andytoshi> i bet i can find an x for which neither x^3 + 7 or -x^3 + 7 is a square
17:41 < andytoshi> it definitely won't be faster than the check if we do the check properly. if we do it with the const-time sqrt i think it's comparable
17:41 <@gmaxwell> you really mean you can find a number which the one that is square -7 doesn't have a cube root.
17:42 < andytoshi> oh, yes, oops
17:44 <@gmaxwell> in any case it was neat to me that it seems the sqrt is 'complete'  in that it gives a correct result for every value, just ignores the sign.
17:48 <@gmaxwell> andytoshi: yea the property of the legendre symbols multplying had me thinking a secure batch legendre symbol was possible for a while.
17:49 <@gmaxwell> e.g. by randomly cutting the batches and checking their composites, but when I worked out the math, to be secure it was just as slow as non-batch.
17:52 < andytoshi> that's a good intuition
18:05 <@gmaxwell> andytoshi: on the subject of random intuition, based on the above I guessed that eactly one of x, x*beta, and x*beta^2 would have a cube root.  And this appears to be true.
18:12 <@gmaxwell> (really I expected it to work for anything that didn't have a cuberoot, I just knew beta didn't)
18:13 < andytoshi> gmaxwell: so 1/3 of everything has a cube root (since each cube has three things that cube to it, which are multiples of beta of each other). call this set S. then S*beta will be disjoint and of the same size, and S*beta^2 will be disjoint from the other two (each element is clearly not in S as it has no cube root; then it's not in beta*S because the element divided by beta also has no cube root)
18:13 <@gmaxwell> yea, 2 works fine.
18:13 < andytoshi> so we've partitioned the whole field into these 3 equal-size cells which can be mapped into each other by multiplication by beta
18:14 < andytoshi> yup, my argument applies to everything without a cube root
18:14 <@gmaxwell> right.
18:17 < andytoshi> i think this argument implies, if you have any element with -no- cube root your field has to have order 1 mod 3. so like mod 11 i bet everything has a cube root
18:18 < andytoshi> yup
18:18 < andytoshi> more generally if your field fails to be 1 mod n, every element has an nth root
18:20 < andytoshi> this is wrong, our field is 3 mod 4 but like anything without a square root obviously has no fourth root
18:24 <@gmaxwell> yes, I was just trying to extend your earlier description to 6th roots, and multiplying by an arbritary non-member is not enough.
18:40 <@gmaxwell> andytoshi: it holds but only for primes.
18:41 < andytoshi> if you choose some element which has no cube root or square root does it work?
18:41 < andytoshi> for 6?
18:41 <@gmaxwell> andytoshi: no.
18:41 <@gmaxwell> but works fine for 7th roots.
18:42 < andytoshi> hmmm, that surprises me
18:56 < andytoshi> can an element have a cube root and square root but no sixth root?
18:56 <@sipa> take the square root, divide it by the cube root
18:57 <@sipa> and you get x^(1/2-1/3) = x^(1/6)
18:57 < andytoshi> oh, nice!
18:57 <@sipa> also
18:57 <@sipa> moon is almost totally eclipsed
18:58 <@sipa> not sure if it's visible over there
18:58 < andytoshi> we're checking
18:59 < andytoshi> but then im quite confused by gmaxwell's claim that i can't skip through six cells of a partition with a sixth-rootless element
18:59 < andytoshi> we think it's behind clouds
19:00 <@sipa> totally clear sky here, and 4am
19:00 <@sipa> pretty nice
19:00 <@sipa> i can see the red shadow already :)
19:01 < andytoshi> 7pm in mountain view, it's beautiful out but half the sky is clouded over
19:02 <@gmaxwell> andytoshi: well I tried and failed, perhaps I typoed. Trying 13441 roots. :P
19:03 < andytoshi> i have some ideas about the structure of this problem but im on a phone and can't checj
19:33 -!- btcdrak [uid115429@gateway/web/irccloud.com/x-rzzyaepmeojtyosm] has quit [Quit: Connection closed for inactivity]
20:02 -!- btcdrak [uid115429@gateway/web/irccloud.com/x-oyioezokfvhpxtpg] has joined #secp256k1
22:09 -!- jtimon [~quassel@160.28.134.37.dynamic.jazztel.es] has quit [Ping timeout: 256 seconds]
22:27 <@gmaxwell> sipa: can we make VERIFY_CHECK not side effect preserving (e.g. goes away completely when VERIFY is not defined)
22:31 <@gmaxwell> As is, it result in random bits of pointless code being emitted in non-optimized builds that irritate my coverage analysis.
22:33 <@gmaxwell> hm why isn't secp256k1_ecdsa_sig_recover in modules/recovery/ ?
22:54 < andytoshi> +1 gmaxwell re VERIFY_CHECK
23:24 <@gmaxwell> Coverage results for master+parsetests+making VERIFY_CHECK side effect free and totally disabling it: https://people.xiph.org/~greg/secp256k1.rpt3/