--- Day changed Fri Oct 09 2015
00:59 -!- fkhan [weechat@gateway/vpn/mullvad/x-joobpgnlmpudepcs] has quit [Ping timeout: 260 seconds]
01:12 -!- fkhan [weechat@gateway/vpn/mullvad/x-vacljtpvaggeezem] has joined #secp256k1
01:37 -!- fkhan [weechat@gateway/vpn/mullvad/x-vacljtpvaggeezem] has quit [Read error: Connection reset by peer]
01:50 -!- fkhan [weechat@gateway/vpn/mullvad/x-nkcvzzclrfrwxaja] has joined #secp256k1
01:58 -!- fkhan [weechat@gateway/vpn/mullvad/x-nkcvzzclrfrwxaja] has quit [Ping timeout: 250 seconds]
02:10 -!- fkhan [weechat@gateway/vpn/mullvad/x-fxiglncanzmhhyrn] has joined #secp256k1
02:19 -!- fkhan [weechat@gateway/vpn/mullvad/x-fxiglncanzmhhyrn] has quit [Ping timeout: 246 seconds]
02:34 -!- fkhan [weechat@gateway/vpn/mullvad/x-mpprkhildpqvupda] has joined #secp256k1
03:44 -!- fkhan [weechat@gateway/vpn/mullvad/x-mpprkhildpqvupda] has quit [Read error: Connection reset by peer]
03:59 -!- fkhan [weechat@gateway/vpn/mullvad/x-wfahfojopamrfjgb] has joined #secp256k1
05:23 < jonasschnelli> Is secp256k1_context_t thread save?
05:24 < sipa> read the fine header file :)
05:24 < sipa> it has comments about that
05:24 < jonasschnelli> sipa: Yes. Good advice. :) thanks
05:25 < sipa> if you don't modify them (don't call randomize), you need no locking
05:25 < sipa> if you do call randomize, it needs a write lock, and all other operations require a read lock
05:26 < jonasschnelli> okay. Thanks!
05:56 -!- fkhan [weechat@gateway/vpn/mullvad/x-wfahfojopamrfjgb] has quit [Ping timeout: 255 seconds]
06:13 -!- fkhan [weechat@gateway/vpn/mullvad/x-vcenufzxfztexmxt] has joined #secp256k1
07:07 < jonasschnelli> valgrind reports source/destination overlap in secp256k1_gej_neg (only clang)
07:08 < jonasschnelli> https://travis-ci.org/jonasschnelli/libbtc/jobs/84510520#L461
09:19 <@gmaxwell> jonasschnelli: Hm. sounds like a clang bug. There is no memcpy in secp256k1_gej_neg, just struct assignments, and I am reasonably sure there is no problem in assigning a struct member to itself via another pointer..
09:20 <@gmaxwell> thats ... kinda scarry!
09:20 < sipa> gmaxwell: could be that due to inlining, the analysis is done on a specific instance where it is provably assigning to itself
09:21 <@gmaxwell> sipa: no.
09:21 <@gmaxwell> sipa: this is runtime checking, and clang is generating memcpys there when there are none in the code.
09:21 <@gmaxwell> jonasschnelli: http://valgrind.10908.n7.nabble.com/memcpy-x-x-n-is-not-OK-clang-llvm-vs-memcheck-td44514.html
09:22 < sipa> oh!
09:22 < jonasschnelli> hmm...
09:24 < jonasschnelli> okay. Sounds reasonable. So it's a bug which is unfix till today?
09:24 < jonasschnelli> https://llvm.org/bugs/show_bug.cgi?id=11763
09:24 <@gmaxwell> And thats mildly scarry because memcpy is not allowed to overlap, and glibc has even shipped versions where some kinds of overlap would cause doom.  Though the specific kind of overlap clang is generating is where it's a no-op... which I think is more likely to be safe.
09:25 < sipa> is it possible that the compiler is using a memcpy for assignment because it knows it is safe?
09:25 <@gmaxwell> I think it's fine so long as glibc's memcopy is safe for the no-op case. But C doesn't require this, and I dunno if glibc ever promised it would be.
09:25 < sipa> i don't think that's generally possible to prove though...
09:25 <@gmaxwell> sipa: kinda! thats what it's doing, except "knows" requires reasoning about libc's behavior; which isn't provided by the compiler.
09:28 <@gmaxwell> Usually the reason overlapping memcpy is not safe is because memcpy is free to run backwards or to use large (e.g. simd register) sized copy chunks.
09:28 <@gmaxwell> though both of those should be safe for the no-op case.
11:32 -!- fkhan [weechat@gateway/vpn/mullvad/x-vcenufzxfztexmxt] has quit [Read error: Connection reset by peer]
11:47 -!- fkhan [weechat@gateway/vpn/mullvad/x-cihgqsvpfdzxmtjy] has joined #secp256k1
12:45 -!- fkhan [weechat@gateway/vpn/mullvad/x-cihgqsvpfdzxmtjy] has quit [Read error: Connection reset by peer]
13:00 -!- fkhan [weechat@gateway/vpn/mullvad/x-cdzfoyypnealqplb] has joined #secp256k1
14:27 < midnightmagic> "I don't think it's really worth warning about, considering I don't know of any real-world implementation where it doesn't work.  If you think it is worth warning about, though, we could change our code generation for the -faddress-sanitizer case."
14:27 < midnightmagic> gah
14:28 < midnightmagic> Patrick J. LoPresti is my new hero
14:30 < midnightmagic> You know, this is *exactly* why the cowboy approach LLVM takes needs a reality check. With "performance", with "licencing". Brutal.
14:31 < sipa> ?
14:36 <@andytoshi> sipa: that's a quote from the LLVM devs on the above bug report
14:36 <@andytoshi> Patrick J. LoPresti is rightly pointing out that they are generating code which has UB, and they're saying "idgaf works for me"
14:50 <@gmaxwell> andytoshi: It's not UB when a compiler does it.
14:50 <@gmaxwell> Except ... the fact that libc and the compiler aren't the same thing is not really something that the C standard was expecting.
14:52 <@gmaxwell> I think LLVM should just specify that it can only be used with libc memcopy that works in place like that. And make sure this is known and agreed to by any libc it works with, and is unit tested by all of them.  And at that point, it would be 99% okay.
14:52 <@gmaxwell> Cowboy mode of "seems fine to me" is ... a little horrifying, but certantly not the first time I've seen that from llvm.
14:54 <@gmaxwell> FWIW, ... things like this are why I do want some amount of init-time self testing.
14:54 <@gmaxwell> I do not think we should trust compilers as much as we do.
14:54 <@gmaxwell> :P
14:54 <@andytoshi> ok, you've finally convinced me of that :)
14:55 <@andytoshi> to be honest i've always thought this was overly paranoid..
14:57 <@gmaxwell> we should at least be fast about it...
15:10 < kanzure> if testing everything takes too long, then you could choose different random sample of things to test each time
15:11 < kanzure> or use fancy self-timing to limit init-time self testing to prioritize which tests get executed during initialization
15:13 <@gmaxwell> kanzure: non-determinstic behavior is a little ugly. And timing usually involves less-portable code.
15:13 <@gmaxwell> I'd rather just find a minimal set of tests that have the greatest test power.  Might just be as simple as signing and verifying, maybe with some carefully selected values.
15:14 < kanzure> signing and verifying some self-referential hash of some kind :-)
15:14 < kanzure> (although would distract readers from its actual purpose, oops)
15:43 <@gmaxwell> sipa: you've managed to overwrite your placeholder master branch at https://github.com/sipa/secp256k1/
15:45 < sipa> ugh
16:39 <@gmaxwell> sipa: your new strict parser will accept a signature that a BIP66 strictder check rejects.
16:42 <@gmaxwell> len: 8 lax: 1 strict: 1 strictder: 0 lax_rt: 0 strict_rt: 0 openssl: 1 openssl_rt: 0 openssl_sv: 1
16:42 <@gmaxwell> openssl_sv means that R and S are <= 256 bits.
16:49 < sipa> example?
16:49 < sipa> can you show me the actual signature?
16:50 <@gmaxwell> sure!
16:51 < sipa> also, i may have changed things that aren't pushed yet
16:51 <@gmaxwell> echo echo MAYCAZ8CAQA= | base64 -d  > x
16:52 < sipa> two echos?
16:52 <@gmaxwell> skip the first.
16:52 <@gmaxwell> (sorry, was typing it in IRC then figured it better to actually test the command...)
16:53 < sipa> it has a negative R
16:53 <@gmaxwell> Hm. So the BIP66 test catches that case.
16:53 < sipa> what commit are you using?
16:53 < sipa> of my parser
16:54 <@gmaxwell> a9e1d35f8726a635418a9adc2c31c9bc666eead4
16:54 < sipa> oh, yes, of course it accepts it
16:54 < sipa> it's valid DER!
16:55 <@gmaxwell> If it's intentional that strict is more permissive than BIP66, okay, I can weaken the 'strictder' invariant I'm using.
16:55 < sipa> the signature in it is invalid
17:00 <@gmaxwell> hm. removed the if (s[4]&0x80)return 0; / if (s[6+nLenR] & 0x80) return 0;  checks and now have a signature with OpenSSL can't round trip which passes strictder. :-/
17:01 <@gmaxwell> oh, makes sense, openssl must be ignoring the negative in the parse, duh
17:09 <@gmaxwell> sipa: hm. so I have this test... if the strict parser passes, memcmp(&sig_strict, &sig_lax, sizeof(sig_lax)) == 0  and this is failing for me.
17:09 < sipa> that's not going to work
17:10 < sipa> that's only true if R and S are both in range
17:12 < sipa> and not negative, specifically
17:12 <@gmaxwell> sipa: why are they not decoding to the same 'parsed but will not verify' state?
17:12 < sipa> because the BER parser forgives negative values, but the DER one won't
17:12 < sipa> even though both 'parse' correctly, one parser to a valid sig, and the other to an invalid one
17:14 <@gmaxwell> ugh.
17:14 < sipa> i have all the rules implemented in my code
17:14 < sipa> but eh... it just found an unexpected bug too :)
17:14 <@gmaxwell> it's just a lot of mental state.
17:15 <@gmaxwell> And means I need to add a 'wont_verify' test.
17:15 < sipa> i have 4 states: 1) unparseable 2) parseable invalid 3) parseable valid 4) roundtrips
17:16 < sipa> for each of the 3 parsers
17:16 < sipa> and there are dozen boolean expressions that relate them :)
17:16 <@gmaxwell> Yea, okay, you and I have implemented the same thing; I'm sure yours is better. :P
17:16 <@gmaxwell> Though my introduces a 4th 'parser' (the BIP66 test).
17:17 < sipa> well, maybe not... things that surprise you may need double checking
17:17 <@gmaxwell> I don't think my work is redundant in any case.
17:18 < sipa> 3080021700427f0000000000000001000000000000f8ffffffffff1f021e0000880000f8ffffffff07000000f8ffffff1f000000000000000000000000000000
17:18 < sipa> that's a signature that openssl accepts, but my ber parser doesn't
17:19 < sipa> which is odd, because i'm not even introducing errors yet...
17:21 <@gmaxwell> okay, my 40 some vector test set created by whitebox fuzzing the old code now passes my current set of boolean conditions.
17:22 < sipa> ok, i don't understand why openssl accepts that
17:26  * sipa rereads ASN.1
17:33 <@gmaxwell> I feel like I need a boolean logic simplifier program to manage all these conditions.
17:34 <@gmaxwell> Now that I have conditions for forced failure, and parse result being identical, and two different strictder intensities.
17:35 <@gmaxwell> after a few seconds with the new harness the test also found me a 'lax fails, openssl parses'
17:36 < sipa> yeah
17:36 <@gmaxwell> 00000000  30 06 02 00 1f 02 01 00                           |0.......|
17:37 <@gmaxwell> if you wanted a shorter example.
17:38 < sipa> hmm, to what does that roundtrip?
17:38 <@gmaxwell> in base64  MAYCAB8CAQA=
17:38 <@gmaxwell> that one is a
17:38 <@gmaxwell> len: 8 lax: 0 strict: 0 strictder: 0 lax_rt: 0 strict_rt: 0 openssl: 1 openssl_rt: 0 openssl_sv: 1
17:39 < sipa> so i cannot comprehend what openssl is making of that
17:39 < sipa> R is not an integer
17:40 < sipa> maybe it just disregards the data type, and knows it is something primitive, and just assumes it is an integer?
17:44 <@gmaxwell> I guess I could print what openssl reencodes it to. one sec.
17:47 <@gmaxwell> 30 06 02 01 00 02 01 00
17:47 <@gmaxwell> so a zero? I wonder if it always decodes to a zero in that case?
17:49 <@gmaxwell> no.
17:49 < sipa> ok?
17:50 <@gmaxwell> 30 08 02 01 19 1f 02 02  08 02 01 14 00 f0 f7 02 00 02 02 00 f0  rencodes to 30 07 02 01 19 02 02 08 02
17:51 < sipa> it... skips the 1f?
17:51 <@gmaxwell> yea, like if it doesn't get the type it just ignores it?
17:55 < midnightmagic> Occasionally I think this sort of thing should be recorded somewhere, even just in note form.
17:56 < sipa> gmaxwell: can you test which byte values you can replace that 1f with to get the same result?
17:57 <@gmaxwell> sipa: sure.
18:03 <@gmaxwell> ... okay, back to the drawing board, 1f is the only value that works there.
18:04 < sipa> yup, and it's even valid BER
18:04 <@gmaxwell> (by works I mean, makes openssl parse)
18:04 < sipa> that 1f just means that the data type number doesn't fit in a single byte, and another follows
18:06 < sipa> BER actually specifies that this is only allowed for type numbers above 30, while the type number is 2 in this case
18:06 < sipa> but i guess it's an easy think to make non-strict
18:08 <@gmaxwell> why would BER apply that over 30 but not over 254 and make the continuation byte be 255?
18:08 < sipa> because only the lower 5 bits of that byte are the type number
18:09 < sipa> there are 3 flag bytes first :)
18:09 < sipa> *bits
18:09 <@gmaxwell> [evil][negative][imaginary] ?
18:10 < sipa> [class][class][constructed]
18:10 < sipa> oh, no
18:10 < sipa> yes
18:11 < sipa> and the 4 class types are universial, application, context-specific, and private
18:12 <@gmaxwell> does openssl require the class to be universal?
18:13 < sipa> i think it checks that the type and the class correspond to what it expects
18:14 < sipa> so anything but 02, 1f 02, 1f 80 02, 1f 80 80 02, ... won't work
18:14 <@gmaxwell> what a weird encoding scheme.
18:15 < sipa> i think it's vastly superior to JSONx
18:15 <@gmaxwell> oh I see. the idea is that if you wanted to code type 31 you'd code 1f 1f.
18:15 <@gmaxwell> yea, thats not so bad.
18:16 <@gmaxwell> I was confused for a minute that it was even possible to put a 1 byte type after 1f.
18:16 < sipa> it uses base128 encoding for the following bytes, with the high bit indicating whether more bytes follow
18:16 <@gmaxwell> 1f 80 02  and not 1f ff 02 ?
18:16 <@gmaxwell> oh got it.
18:16 < sipa> 01 ff 02 would be type 7f 02
18:16 <@gmaxwell> (I was thinking more like 1f ff 02 00 but I see.) yea, thats reasonable.
18:17 <@gmaxwell> so the only redundancy arises from not subtracting 31 first.
18:18 <@gmaxwell> (when extension is used.)
18:22 <@gmaxwell> uh strict parsed this: MIEzAoEKExF/JCIA/TCBEwKBIwL/fywiAF39AOkAEEAAPAeAAAAAgAAAgiIiIhAiIuMefykx
18:23 <@gmaxwell> it's 54 bytes long, but the second byte is 0x81?
18:23 <@gmaxwell> or is the high bit there used for something special too?
18:24 < sipa> looks correct to me
18:24 < sipa> yes :p
18:24 <@gmaxwell> even in DER? okay.
18:24 < sipa> oh!
18:25 < sipa> no, DER shouldn't accept that
18:25 < sipa> but I think I've added that test later
18:25 < sipa> not pushed yet
18:26 <@gmaxwell> okay.  I am correct in believing that if strict passes the result either should be a forced failure or Beyond BIP66 strict der, right?
18:29 < sipa> i think so
18:31 < sipa> so: it should be possible to prefix any valid signature with 0x3F
18:31 < sipa> and remain valid
18:31 <@gmaxwell> so... the reason I'm asking is ... unless the invariant I just stated is true, the strict parser is not enough to prevent malleable valid signatures.
18:32 < sipa> it can also be guaranteed failure
18:32 < sipa> for example have r==0, in the signature
18:33 <@gmaxwell> OK. We should do that and document that.
18:33 < sipa> but i guess you can call that forced failure
18:33 <@gmaxwell> Well right now my 'forced failure' test is making sure the sig memory is all zeros, because thats what the code appeared to do, e.g. for oversized R/S.
18:34 < sipa> if you change 'forced failure' to either R or S is zero, you're good
18:34 < sipa> i think you can put it stronger: if the strict parser succeeds, the result is either forced failure, or roundtrip
18:35 < sipa> what is your 'Beyond' precisely?
18:35 <@gmaxwell> BIP66 plus also checking the size of R and S, right now. But actually I am also checking if strict passes it's forced failure or a round trip.
18:36 < sipa> it should be either forced failure, or roundtrip + BIP66
18:37 < sipa> (where forced failure means either R or S is zero)
18:38 <@gmaxwell> (I like having the BIP66++ test too so that I'm not just testing libsecp256k1 against itself... the simple tester gives another 'outside' view)
18:50 < sipa> wtf
18:50 < sipa> openssl parses 308002810105029100000000000000000000000000010204090000320000000000000000
18:50 < sipa> that has a 16909321-byte R value
19:00 < sipa> sense... this makes none
19:10 <@gmaxwell> what does it seralize as?
19:15 < sipa> oh, test code is broken
20:01 < sipa> gmaxwell: pushed my new code to laxder
20:01 < sipa> it still finds various unexpected discrepancies with openssl...
20:36 <@gmaxwell> sipa: You seem to have regressed.
20:37 <@gmaxwell> sipa: e.g. sAgCAjASAgICYg==  parses with strict, and isn't forced failure but does not round trip and isn't strictder.
20:44 <@gmaxwell> sipa: oh thats with weird typecoding handling ... and not responding to it by force failure. ::sigh::