--- Log opened Thu Jan 09 00:00:03 2020
01:04 -!- ddustin [~ddustin@unaffiliated/ddustin] has joined #secp256k1
01:12 -!- ddustin [~ddustin@unaffiliated/ddustin] has quit [Remote host closed the connection]
01:13 -!- ddustin [~ddustin@unaffiliated/ddustin] has joined #secp256k1
01:17 -!- ddustin [~ddustin@unaffiliated/ddustin] has quit [Ping timeout: 240 seconds]
01:48 -!- jonatack [~jon@2a01:e0a:53c:a200:bb54:3be5:c3d0:9ce5] has quit [Ping timeout: 248 seconds]
03:32 -!- jonatack [~jon@atoulouse-656-1-807-188.w86-221.abo.wanadoo.fr] has joined #secp256k1
03:41 -!- jonatack [~jon@atoulouse-656-1-807-188.w86-221.abo.wanadoo.fr] has quit [Ping timeout: 268 seconds]
03:41 -!- jonatack [~jon@134.19.179.179] has joined #secp256k1
04:16 < real_or_random> lgtm
04:29 < gmaxwell> real_or_random: you indirectly found another non-constant time bug. Gcc with -Os emits an idiv on x86_64 for the prior code's divsion by 2.  (and I'm sure older compilers are much more prone to do that even at other optimization levels)
04:30 < real_or_random> let's just rewrite the thing in asm
04:30 < real_or_random> gimme 3 years
04:31 < sipa> gmaxwell: an idiv with a constant denomimator?
04:31 < gmaxwell> To be fair, the source _said_ division.  You have no idea ... my skin crawls at any / or % that shows up in code and I have to restrain myself about whining about it, since compilers are usually pretty good at elimiating them.... so hurray for my preferences, I now have a new excuse.
04:31 < real_or_random> :D
04:31 < gmaxwell> sipa: it's shorter code, -Os optimize for size.... sooooo.
04:32 < real_or_random> well, but then why doesn't it change >> 1 to /2 with -Os
04:32 < gmaxwell> twenty years ago, compilers seldom converted / into other operations and a div was (and still is) 100x slower than a mul or worse.
04:32 < sipa> gmaxwell: yes, but does it emit a "x / y" or an "x / 2" ?
04:32 < gmaxwell> sipa: idiv with a constant.
04:33 < sipa> is it even variable time in that case? (i suspect the answer is "who knows?")
04:33 < real_or_random> I'm sure we have more of these divisions in the code
04:34 < gmaxwell> (on current x86-- who knows?  I have no idea elsewhere.  but that totally breaks the ability to simply analyize the output for divs)
04:34 < gmaxwell> real_or_random: we didn't at one point, I audited the asm output for them.
04:34 < gmaxwell> (I read every emitted div in the codebase and confimed it wasn't on secret data.
04:34 < gmaxwell> )
04:35 < gmaxwell> I bet it wouldn't be hard to modify valgrind to catch those too.
04:35 < real_or_random> would be cool if you could eliminate all of them ^^
04:35 < gmaxwell> I'm not completely sure that I also checked -Os, I'll have to go look at irc logs to see if I said. It's not unlikely that I did, because I was aware that -Os turns off strength reduction (particularly on arm)
04:36 < real_or_random> or at least in certain files, I guess the scratch space code needs actual divisions for example
04:36 < real_or_random> when dealing with memory
04:37 < gmaxwell> actual divisions are never needed.
04:37 < gmaxwell> esp scratch space just divides with small constants.
04:38 < sipa> i suspect that with -O2 all divisions get turned into muls/shifts
04:38 < real_or_random> ok yes
04:39 < gmaxwell> sipa: constant divisions. Yes, hopefully on current compilers they do.
04:39 < real_or_random> I meant "not divisions by a power of 2"
04:39 < sipa> gmaxwell: right, and hopefully all we have are divisions by constantz
04:39 < real_or_random> but you're right, idiv should not be needed there
04:39 < gmaxwell> real_or_random: you can convert them into multiply+shift if they aren't powers of 2.
04:40 < gmaxwell> (same thing the compiler does)
04:40 < gmaxwell> (or rather, that we hope it does! :) )
04:41 < gmaxwell> it mostly only matters when you have a non-constant divisor, in which case the compiler won't do it. ... or I guess when you really want to be sure your code is constant time.
04:41 < real_or_random> gmaxwell: nice that you mentioned integer promotion. when people talk to me about C, I often ask them how to multiply two uint16_t's
04:43 < gmaxwell> real_or_random: I've seen a lot of bugs introduced by use of unsigned causing surprising promotions. The coders at skype that worked on their silk codec prohibited unsigned except on a case by case basis, where it was actually required.
04:45 < real_or_random> and I guess our code would simply explode when compiled for a target where int has 64 bits
04:46 < gmaxwell> in any case, tomorrow I'll look into seeing if it would be easy to modify valgrind to treat idiv like a branch.
04:46 < gmaxwell> real_or_random: dunno, would be interesting to try. Unfortunately I do not have a cray computer.
04:48 < real_or_random> I would not mind adding "1U * U" everywhere but I can imagine people will yell at me
04:48 < real_or_random> meant "1U * "
04:54 < gmaxwell> oh god, ran into this: https://stackoverflow.com/questions/54438477/why-does-clang-do-this-optimization-trick-only-from-sandy-bridge-onward
04:54 < gmaxwell> see,  the '/' symbol is just cursed.
04:55 -!- jonatack [~jon@134.19.179.179] has quit [Ping timeout: 260 seconds]
04:57 < sipa> ha
04:58 < gmaxwell> "The throughput of "DIV/IDIV r32" varies with thenumber of significant digits in the input EDX:EAX and/or of the quotientof the division for a given size of significant bits in the divisor r32. Thethroughput decreases (increasing numerical value in cycles) with in-creasing number of significant bits in the input EDX:EAX or the outputquotient. The latency of "DIV/IDIV r32" also varies with the
04:58 < gmaxwell> significantbits of the input values. For a given set of input values, the latency isabout the same as the throughput in cycles."
04:58 < gmaxwell> So the intel manual essentially makes no useful promise.
05:12 < gmaxwell> real_or_random: this page has good info on non-constant-time multipliers https://www.bearssl.org/ctmul.html
05:13 < sipa> yeah i think real_or_random found that page after djb's talk at c3
05:52 < real_or_random> I mentioned this here yesterday, I think
06:07 -!- jonatack [~jon@2a01:e0a:53c:a200:bb54:3be5:c3d0:9ce5] has joined #secp256k1
06:14 -!- afk11 [~afk11@gateway/tor-sasl/afk11] has quit [Remote host closed the connection]
06:15 -!- afk11 [~afk11@gateway/tor-sasl/afk11] has joined #secp256k1
07:59 -!- belcher [~belcher@unaffiliated/belcher] has quit [Quit: Leaving]
08:03 -!- belcher [~belcher@unaffiliated/belcher] has joined #secp256k1
09:23 < real_or_random> gmaxwell: I was of course wrong, the msvc issue is about 64x64 multiplications on a 32bit machine (which is not as crazy. but still.)
09:30 < gmaxwell> yeah indeed.
09:50 < gmaxwell> hurrah. I successfully modified valgrind to complain about divs, and can detect that secret div in an Os build on x86_64.
09:53 < gmaxwell> And it's the only one (in an x86_64 -Os GCC 9.2.1 build).
09:54 < gmaxwell> God knows if I got every form of div, but I got every instruction with 'div' in its name that wasn't obviously a SIMD instruction... https://i.pinimg.com/originals/e1/10/e4/e110e4f1a25705c7f23974aac7e1cbc4.jpg
09:57 < gmaxwell> after we merge the valgrind check, I'll reach out to the author of valgrind and see what I can do about making this possible without patching valgrind.
11:17 < gmaxwell> sipa: I have a new verification idea for libsecp256k1. Lets call it "shitty-typestate".
11:17 < gmaxwell> In -D verify builds, every FE and Scalar struct is agumented with an additional boolean "secret".
11:18 < gmaxwell> All functions that are non-constant time add checks that the inputs that they're not constant time in terms of aren't secret.
11:18 < gmaxwell> In non-verify builds all this goes away, so it's zero overhead.
11:25 < sipa> it would be nice as a way to formalize what our expectations & guaranteed are regarding secret data
11:28 < gmaxwell> It would, for example, have discouraged implementing double-nonzero as a wrapper on double-var.
11:28 < gmaxwell> In theory we could also do this for other properties we care about-- like tracking if a point could possibly be infinity.
11:33 < gmaxwell> fun fact, secp256k1_fe_set_b32 is not constant time.
11:39 < sipa> gmaxwell: but it only leaks whether overflow occured,right?
11:41 < gmaxwell> No.
11:41 < gmaxwell> it uses a shortcutting comparison.
11:42 < gmaxwell> and also returns at a different point (though the compiler might fix that in non-DVERIFY builds)
11:42 < gmaxwell>     if (r->n[4] == 0x0FFFFFFFFFFFFULL && (r->n[3] & r->n[2] & r->n[1]) == 0xFFFFFFFFFFFFFULL && r->n[0] >= 0xFFFFEFFFFFC2FULL) {
11:42 < gmaxwell> it's not a leak except in the table randomization function.
11:43 < gmaxwell> I'll fix it to  make it constant time-- it'll probably be faster.
11:43 < gmaxwell> it's just lower on my list, I could use feedback about my proposed way of handling overflow: https://0bin.net/paste/k-f4K7X4tjYcszYV#aBRAenCt9E7O5GLB7oA7TvFvdDy-pcehM1cqOiaUuf5
12:36 < real_or_random> gmaxwell: when I saw your change with nonzero, I thought about typing too. but wouldn't it be nice to have an external tool for this? no idea if this exists but sounds plausible
12:37 < real_or_random> motivated by all these discussions, I really had a look at those weird msvc multiplications, and I think there are four multiplications in the 32bit field code which are affected
12:37 < real_or_random> the scalar code is clean
12:38 < real_or_random> maybe I can have a PR ready tomorrow
13:30 < gmaxwell> 'use asm on msvc' ? :P
14:16 < gmaxwell> real_or_random: I'm sure someone has written a tool... that requires patching a three year old copy of clain, four sub utilities written on ocaml, explodes if your codebase uses int128, and only works in a docker image of the author's system. :P
14:16 < gmaxwell> s/clain/clang/ :P
14:20 < gmaxwell> realisticaly, if you make seperate structs with the same definition, they'll be different types. But I suspect there is no way to do that without creating copying overhead when you do convert... and no good way to capture the relationship that one direction is safe, but not the other. (e.g. you can feed non-secrets to constant time secret inputs)
14:28 < midnight> argh docker
14:28 < midnight> destroying compatibility since 1842
14:29 -!- belcher [~belcher@unaffiliated/belcher] has quit [Quit: Leaving]
14:31 < gmaxwell> real_or_random: the magnitude thing on field elements is already a kind of typestate.
14:37 < gmaxwell> I really like the valgrind test though, because it'll catch the compiler screwing us... and it supports x86_64/x86/arm/ppc/s390/sparc... presumably it'll pick up riscv sooner or later.
14:38 < gmaxwell> and we can run the tests with an unmodified production library.
14:39 < gmaxwell> so you can test if your real code passes...  which is about the best that could possibly be done short of having a hardware setup to record sidechannels.
19:16 -!- jonatack [~jon@2a01:e0a:53c:a200:bb54:3be5:c3d0:9ce5] has quit [Ping timeout: 248 seconds]
19:19 -!- jonatack [~jon@88.124.242.136] has joined #secp256k1
--- Log closed Fri Jan 10 00:00:02 2020