--- Log opened Wed Jan 08 00:00:01 2020 01:18 -!- sipa [~pw@gateway/tor-sasl/sipa1024] has quit [Ping timeout: 240 seconds] 01:20 -!- sipa [~pw@gateway/tor-sasl/sipa1024] has joined #secp256k1 02:52 -!- belcher [~belcher@unaffiliated/belcher] has joined #secp256k1 02:55 -!- jonatack [~jon@2a01:e0a:53c:a200:bb54:3be5:c3d0:9ce5] has quit [Ping timeout: 260 seconds] 03:54 -!- luke-jr [~luke-jr@unaffiliated/luke-jr] has joined #secp256k1 04:07 < gmaxwell> sipa: fun fact, ... signing and keygen in libsecp256k1 are not actually constant time with respect to the private key. 04:13 < gmaxwell> https://github.com/bitcoin-core/secp256k1/pull/708 04:18 -!- jonatack [~jon@213.152.162.94] has joined #secp256k1 04:33 < sipa> gmaxwell: without looking, i expect it is not constant time in whether or not it is a valid private key 04:34 < elichai2> it seems to be complaining about `!overflow && !secp256k1_scalar_is_zero(&sec)` is `secp256k1_scalar_is_zero` not constant time maybe? 04:37 < nickler> nice! fwiw autogen.sh fails rn 04:38 < gmaxwell> nickler: oops forgot to check in the am file... 04:39 < gmaxwell> elichai2: it's constant time, but then it branches on the result -- which isn't. 04:40 < gmaxwell> elichai2: the errors there are not real problems, we don't actually care if it's constant time if your private key turns out to be invalid. 04:40 < gmaxwell> but they gum up the test. 04:40 < elichai2> gmaxwell: even though the results aren't "unintialized values"? 04:40 < gmaxwell> elichai2: the _result_ of the test is tainted. 04:40 < elichai2> (the result is still techinaclly UB because it's based on uninit) 04:41 < gmaxwell> which is exactly why this tool works. 04:41 < elichai2> gmaxwell: didn't know that valgrind also complains about "tainted" variables 04:41 < gmaxwell> elichai2: if it didn't it mostly wouldn't be useful. 04:41 < sipa> gmaxwell: for most public API functions we have, we can permit variable time based on the *output* (as the output in correct operation is properly blinded, being dependent on it never leaks anything) 04:42 < sipa> this is something that nickler or real_or_random observed a few days ago 04:42 < gmaxwell> yeah, so one option to work around the S retry is to insert a valgrind macro into secp256k1.c that marks the signature as untainted. 04:42 < gmaxwell> the s _overflow_ is a real 'leak', just a totally irrelevant one. 04:42 < sipa> gmaxwell: but for example for ECDH, the output is secret too 04:43 < gmaxwell> nickler: I force pushed an update with the macro included. 04:47 < gmaxwell> sipa: Would you find it objectionable to add a VALGRIND_MAKE_MEM_DEFINED() on the result of the secp256k1_scalar_is_zero test in the signing loop? (if the code is compiled with valgrind) ... and also make it so that keygen and signing still runs with an overflowing key, but returns an error and cmovs zeros into the output if there is overflow? 04:48 < sipa> gmaxwell: i wish there was a more systematic way 04:49 < sipa> because it's actually overriding a correct observation that that result is not constant in the input 04:50 < gmaxwell> Marking a "cryptographically scrubbed" value as clean isn't particularly bad. At first I was concerned about reducing the sensitivity to errors in normal use, but then I realized it could just be applied to the output of the test. 04:51 < gmaxwell> If you look at my test, it actually marks the output (outside of libsecp256k1) as clean, then runs the serialize functions on them. In the case of the ecdh test, I wouldn't mark the output as clean before running the serialize. 04:52 < gmaxwell> If I did add the VALGRIND_MAKE_MEM_DEFINED I'd make a wrapper macro that makes the intent clear. some ... UNTAINT... 04:52 < elichai2> can we do it in a seperate file instead of in the code? (like msan/asan supression files) 04:52 < gmaxwell> elichai2: I think thats less good. 04:52 < gmaxwell> (I mention that on the PR) 04:54 < gmaxwell> in addition to the reasons I gave there, if I were a third party and saw this project shipping a valgrind suppression file I would be inclined to not use this software, without even bothering to look to see what it was. :) 04:54 < elichai2> the upside of the file is that we could name it in a way that you need to *explictly include it* and it won't be used with default valgrind runs 04:54 < gmaxwell> elichai2: it's still a maintance burden. 04:55 < elichai2> and adding `VALGRIND_MAKE_MEM_DEFINED` isn't? 04:55 < elichai2> (ie the file can be named `constant_time_checkes.supp` or even remove the `.supp` altogether) 04:55 < gmaxwell> How is it? it's a single line of code (+if macro) that has no interaction with anything else. 04:56 < gmaxwell> And the issues its reporting are _real_ non-constant time behavior. 04:56 < elichai2> you need another macro so it will only be enabled for the constant time checks and not for the "normal tests" 04:57 < elichai2> so that needs to be part of the build system too 04:57 < gmaxwell> They're just not particularly interesting. (I mean, I could probably construct some awful crazy offlable usage which is made vulnerable by the overflow test) 04:57 < elichai2> they are interesting if you want to check for actual uninit usage IMHO 04:57 < gmaxwell> elichai2: no, it doesn't. It just needs to be there only if the valgrind headers are on the system. It's inert when not run in valgrind. 04:58 < gmaxwell> (and if we wanted we could make the scrubbing conditional on a variable in ctx) 04:58 < sipa> gmaxwell: it should be compile-time chosen, no? 04:58 < sipa> production binaries shouldn't get the overhead of having these 04:58 < gmaxwell> Why? I think running the constant time tests on special binaries is both unnecessary and less good. 04:59 < gmaxwell> sipa: IIRC the valgrind macros do something basically costless. 04:59 * gmaxwell looks 05:00 < gmaxwell> it loads a value into a register and does xchgl %%ebx,%%ebx with the value. 05:02 < gmaxwell> https://github.com/pmem/pmdk/blob/master/src/common/valgrind/valgrind.h#L269 05:03 < gmaxwell> so it'll output like six instructions. 05:04 < gmaxwell> Having to compile a seperate binary means that the test isn't actually run on the production binary, -- so if there is some non-constanttimeness introduced by compiler behavior or configuration optiosn, it won't get caught. 05:05 < gmaxwell> If you were ./configure --disable-valgrind (or the headers weren't on your system so it was auto-disabled) then it wouldn't be emitted either. 05:06 < gmaxwell> to be clear, I'm only suggesting doing that on the _output_ of the crypto. Overflow I would still recommend handling by making the software constant time. 05:22 -!- ddustin [~ddustin@unaffiliated/ddustin] has joined #secp256k1 05:23 < gmaxwell> uh. secp256k1_ecmult_const appears to have real constant time bugs, FWIW. 05:29 < sipa> uh! 05:31 < gmaxwell> okay, one of them doesn't appear to be real, but I think it's dangerous code and should be changed. secp256k1_gej_double_var is _almost_ constant time. except for the input being an infinity. ecdh uses it, but in a case where the input can never be an infinity. 05:31 < gmaxwell> but there really shouldn't be a constant time function just acting as an "i know best" wrapper on a variable time one-- if someone changes the doubling algo they very likely would miss this fact. 05:32 < gmaxwell> instead, I think double_var should be turned into a wrapper for double_nonzero, instead of the other way around. 05:35 < gmaxwell> The several other ones are valgrind saying ECMULT_CONST_TABLE_GET_GE is not constant time in the secret. Because it's a macro, the report doesn't give a good line number, and the function is complicated... so I haven't checked it out fully yet. 05:39 < sipa> gmaxwell: seems reasonable 05:41 < real_or_random> related: I spent some hours at 36c3 looking into non-constant time multiplication after bernstein and lange brought reminded me of that issue in their talk. 05:42 < gmaxwell> real_or_random: stupid old arm devices. Did you know the original trezor is one of those cpus? 05:42 < real_or_random> here's a nice table: https://www.bearssl.org/ctmul.html 05:42 < real_or_random> yep! 05:42 < gmaxwell> thats the sort of thing where the countermeasure could be tested by a cpu simulator... just make it's multiplies follow the rules you're trying to deal with. 05:42 < real_or_random> and there are a few interesting things, e.g., MSVC on 32 bit calls into the runtime library for every 32 x 32 -> 64 multiplication 05:43 < gmaxwell> sipa: okay, the issue in ecdh looks real enough to me. 05:43 < gmaxwell> int abs_n = (n) * (((n) > 0) * 2 - 1); 05:43 < gmaxwell> N is a secret, n>0 branches on it. 05:43 < real_or_random> and the called function is not constant-time, which has lead to real key extraction vulnerabilities in some EC implementations 05:43 < gmaxwell> real_or_random: what?! !! CRAZY. 05:44 < real_or_random> https://research.kudelskisecurity.com/2017/01/16/when-constant-time-source-may-not-save-you/ read this... this was admittedly a particularly unlucky interaction with that windows function but yeah 05:45 < gmaxwell> sipa: do you have a better fix than ORing log2(n_bits) shifts? 05:45 < elichai2> gmaxwell: is `n` signed or unsigned? 05:46 < elichai2> probably signed heh 05:46 < real_or_random> another thing we should look at in our code. that's kind of sad. I feel I could create 10 issues / day in secp. and solve 1 per week or so >.> 05:47 < gmaxwell> real_or_random: I think that compiler+platform should just get blacklisted. I don't think it's worth it to try to fix widening multiplies being non-constant time. 05:48 < gmaxwell> oh derp the test is > 0 not != 0. 05:49 < real_or_random> not sure yet. my first impression is that all our 32x32 to 64 muls are of a type that is actually constant-time. but I haven't verified this 05:49 < real_or_random> and blacklisting MSVC sounds pretty tbh. 05:49 < gmaxwell> casting it then checking the MSB? 05:50 < elichai2> gmaxwell: i'm not quite sure if it works on signed too but I think `return (x^((x^(x-y))&(y^(x-y))))>>31;` can check in constant time if it's less then. so replace x with 0 05:50 < elichai2> I have it written down, i'll find where it's from in a sec 05:50 < real_or_random> s/pretty/pretty bad 05:51 < gmaxwell> real_or_random: well I did mean for only 32-bit. :) 05:51 < elichai2> gmaxwell: here: https://github.com/veorq/cryptocoding#compare-secret-strings-in-constant-time that's the source of this black magic 05:51 < gmaxwell> thanks for clarifying, I thought you ment petty. :) 05:52 < gmaxwell> I'm pretty sure that expression simplfies in this case to (y>>31)&1 05:52 < sipa> is y>>31 well-defined on a signed 32-bit int? 05:52 < gmaxwell> or to be more clear ((unsigned)y>>31)&1 05:52 < gmaxwell> sipa: no, but you can always cast to unsigned. 05:53 < sipa> ah, yes, it does sign-extension 05:53 < gmaxwell> okay then no cast even needed, I guess. 05:54 < elichai2> https://godbolt.org/z/Hh5CgR 05:55 < elichai2> it seems to do more than shift and AND 05:55 < gmaxwell> well the compiler isn't necessarilly all that smart. 05:56 < elichai2> if it was non of these tricks would work :) 05:59 < gmaxwell> usually the branch is slower than even a bunch of constant time magic. :P 06:02 < gmaxwell> (unless the branch predictor is very successful) 06:17 < gmaxwell> interesting, valgrind appears to have caught the compiler turning clearly constant time code into non-constant time code. 06:17 < gmaxwell> pretty cool 06:42 -!- jonatack [~jon@213.152.162.94] has quit [Ping timeout: 268 seconds] 06:43 -!- jonatack [~jon@109.202.107.147] has joined #secp256k1 07:04 -!- ddustin [~ddustin@unaffiliated/ddustin] has quit [Remote host closed the connection] 07:27 -!- jonatack [~jon@109.202.107.147] has quit [Ping timeout: 260 seconds] 08:26 -!- jonatack [~jon@2a01:e0a:53c:a200:bb54:3be5:c3d0:9ce5] has joined #secp256k1 09:28 -!- meshcollider [meshcollid@gateway/shell/ircnow/x-yykaxgczrolqfbhm] has quit [Ping timeout: 248 seconds] 10:22 -!- roconnor [~roconnor@host-104-157-187-25.dyn.295.ca] has joined #secp256k1 11:00 -!- meshcollider [meshcollid@209.141.50.204] has joined #secp256k1 15:53 < gmaxwell> andytoshi: sipa: This is how I propose handling the overflow/zero on the secret key: https://0bin.net/paste/k-f4K7X4tjYcszYV#aBRAenCt9E7O5GLB7oA7TvFvdDy-pcehM1cqOiaUuf5 15:54 < gmaxwell> with that patch (and the PR I have open), ecdh is completely clean in the constat time checker. 15:54 < gmaxwell> If you think thats agreeable, I'll go ahead and give the same treatment to keygen and signing. 15:55 < gmaxwell> Then the only remaining issue will be the signing retry loop, and I'll make a proposed patch for that after the key handling is fixed. 15:56 < gmaxwell> real_or_random: nickler: ^ 16:29 -!- luke-jr [~luke-jr@unaffiliated/luke-jr] has quit [Ping timeout: 260 seconds] 16:34 -!- luke-jr [~luke-jr@unaffiliated/luke-jr] has joined #secp256k1 18:18 -!- jonatack [~jon@2a01:e0a:53c:a200:bb54:3be5:c3d0:9ce5] has quit [Ping timeout: 252 seconds] 22:39 -!- roconnor [~roconnor@host-104-157-187-25.dyn.295.ca] has quit [Quit: Konversation terminated!] 23:46 -!- jonatack [~jon@2a01:e0a:53c:a200:bb54:3be5:c3d0:9ce5] has joined #secp256k1 --- Log closed Thu Jan 09 00:00:03 2020