--- Log opened Tue Jan 07 00:01:02 2020
01:33 -!- belcher [~belcher@unaffiliated/belcher] has joined #secp256k1
02:18 -!- jonatack [~jon@2a01:e0a:53c:a200:bb54:3be5:c3d0:9ce5] has quit [Ping timeout: 248 seconds]
04:39 -!- jonatack [~jon@213.152.161.170] has joined #secp256k1
06:37 -!- jonatack [~jon@213.152.161.170] has quit [Read error: Connection reset by peer]
06:41 -!- jonatack [~jon@54.76.13.109.rev.sfr.net] has joined #secp256k1
07:17 -!- jonatack [~jon@54.76.13.109.rev.sfr.net] has quit [Ping timeout: 265 seconds]
10:44 -!- jonatack [~jon@2a01:e0a:53c:a200:bb54:3be5:c3d0:9ce5] has joined #secp256k1
11:50 < gmaxwell> fwiw, this new chosen prefix collision on sha1 is essentialy a total break on a signatures using sha1 that don't put R first.
11:51 < gmaxwell> and not a break on ones that do (also assuming they don't pre-hash the message w/ sha1, of course)
11:53 < sipa> yup
11:54 < gmaxwell> sounds like their demo involves getting forged pgp wot certifications by exploiting this fact.
11:54 -!- ddustin [~ddustin@unaffiliated/ddustin] has joined #secp256k1
11:55 < gmaxwell> I ask you to certify a key as being mine, but I've generated the signing request in a way that your signature applies to a signing request for another key which has, say, Satoshi's name on it..  and then I can impersonate him.
12:00 -!- ddustin [~ddustin@unaffiliated/ddustin] has quit [Remote host closed the connection]
12:00 -!- ddustin [~ddustin@unaffiliated/ddustin] has joined #secp256k1
12:04 -!- ddustin [~ddustin@unaffiliated/ddustin] has quit [Ping timeout: 240 seconds]
12:26 < midnight> another reason for the sks replacement to ignore all third-party sigs  i guess
13:16 < elichai2> gmaxwell: if you get to checking the ecdh code i'd love to hear what methods you plan on using to check for timing attacks(aka secret independence) I have some ideas on how it can be done, but i'm curious if you have a set of checks you do or something like that
13:26 < gmaxwell> in the past I used valgrind to identify data dependant braches on secret data, and TSC counting with a realtime scheduled process on a core with nothing else allowed to run on it.  (then I introduced vulnerabilities and made sure that the instrumentation caught them).
13:26 < gmaxwell> What I _really_ want is a #@$# cpu emulator that can record a transcript of the memory accesses... but my attempts to get that working in the past were unsuccessful.
13:28 < gmaxwell> E.g. you instrument the emulator so a special instruction starts tracing, and another one stops it. At the end of a trace the emulator spits out the number of cycles executed and a hash of the addresses of every memory access (and if it was a read or write).   Running that multiple times with different secret keys should give the same result.
13:28 < gmaxwell> I'd love to have something like that in a CI test.
13:29 < gmaxwell> The problem I had is that the riscv emulators I could get working didn't simulate memory... and I got lost trying to modify x86 emulators because they were so complicated.
13:30 < gmaxwell> (x86 or arm would be ideal, since those are major targets for us... and it would be really good to discover non-constant timeness injected by the compiler)
13:31 < elichai2> yeah I thougt about valgrind. that's a cool idea, I'm also curious cause I saw nickler talk about some tools that somehow check that
13:32 < elichai2> a cpu emulator is sadly quite a lot of work, but even then, what do you pass it? random value?edge cases? and compare they all took the same cycles?
13:34 < gmaxwell> yea, the obvious thing to test are edges cases and random values-- you know how the code is designed, which suggests edge cases. :)
13:35 < gmaxwell> Min value, max value, are obvious natural test cases.  For ecdh that plus a bunch of random values is probably pretty good.  The best way to find edge cases is to go and inject vulnerablities and make sure the tests are sufficient to find them!
13:35 < sipa> iirc there are tools specifically for testing constant time behavior
13:35 < gmaxwell> e.g. go make a cmov into an array access. Or swap the constant time negation with a variable time one.
13:35 < sipa> ctverif
13:36 < sipa> (looks like it's javascript..., so i'm confused now)
13:36 < sipa> but uses clang as a backend
13:37 < gmaxwell> Never used it.  I think an instrumented emulator would be strictly better, but... we use the tools we can.
13:40 < gmaxwell> https://bellard.org/tinyemu/ this looks promising.
13:41 < sipa> ah, that's the guy that got the linux kernel to run in a browser
13:42 < gmaxwell> yes, and also tinyc and Bellard's formula (random access into hex pi...).
13:43 < gmaxwell> this emulator is enough to run a linux system, so getting libsecp256k1 working in it should be trivial.
13:43 < sipa> yup
13:44 -!- echonaut [~echonaut@46.101.192.134] has quit [Remote host closed the connection]
13:44 < sipa> it already contains a sha256 implementation even
13:45 -!- echonaut [~echonaut@46.101.192.134] has joined #secp256k1
13:46 < gmaxwell> my ideal CT testing idea would require: get it so you can run a compile riscv binary with it (maybe that requires making a little linux boot image, lol).  Then extending it by adding two instructions (presumably riscv has a user defined instruction area), one that starts tracing, the other that stops it and sticks the hash of the trace into registers.  Then we just make a little test harness that
13:46 < gmaxwell> traces with different secret keys and verifies the results are constant.
13:46 < gmaxwell> The cool thing about using an emulator is that it should be robust against bitrot... we don't need to keep updating our patched emulator.
13:46 < sipa> that sounds like an awesome project
13:47 < gmaxwell> unlike these monststosities that try to static analyize constant timeness from LLVM IR.   The primary limit is that they'll never find extremely rare non-constant timeness, like being non-constant time when an add turns out to be a double.
13:47 < gmaxwell> But that kind of 'vulnerablity' is also a lot less likely to result in a pratical attack.
13:50 < gmaxwell> in _theory_ valgrind would be perfectly capable of doing all this too, but I looked into it before and it seemed really complicated to modify. It doesn't help that damn near every x86 instruction can access memory.
14:11 -!- echonaut [~echonaut@46.101.192.134] has quit [Remote host closed the connection]
14:15 -!- echonaut [~echonaut@46.101.192.134] has joined #secp256k1
15:34 < real_or_random> oh yes, this would be awesome stuff
15:34 < real_or_random> by the way, there is ctgrind which is a modification of valgrind. but I'm not sure how far that goes, I never used it
16:32 < gmaxwell> I ~think~ it just does the 'do branches depend on secret data'-- which you can just do using the valgrind macros now. I've never seen something that captures memory traces.  in terms of stuff to modify to accomplish this, RR would also be an excellent candidate.
16:32 < gmaxwell> actually Roc (whom I used to work for) now has a company selling some debugging-as-a-service based on RR... they might take doing some RR trace comparison thing as a contract job.
16:34 < sipa> RR?
16:35 < gmaxwell> https://en.wikipedia.org/wiki/Rr_(debugging)
16:37 < sipa> ah
16:45 < gmaxwell> hm maybe not, because how rr records only state and non-determinstic effects.
16:48 < gmaxwell> real_or_random: I just read the ctgrind source, and indeed _all_ it does is creates a poison and unpoison call which are functionally equal to VALGRIND_MAKE_MEM_UNDEFINED and VALGRIND_CHECK_MEM_IS_DEFINED.  (Perhaps those didn't exist back when it was written).
16:53 < gmaxwell> (oh well unpoison isn't equivilent to check, you simply ... write to the data to unpoison it. :P)
19:46 -!- belcher [~belcher@unaffiliated/belcher] has quit [Ping timeout: 260 seconds]
21:44 -!- sipa [~pw@gateway/tor-sasl/sipa1024] has quit [Remote host closed the connection]
21:49 -!- sipa [~pw@gateway/tor-sasl/sipa1024] has joined #secp256k1
23:32 -!- luke-jr [~luke-jr@unaffiliated/luke-jr] has quit [Ping timeout: 265 seconds]
--- Log closed Wed Jan 08 00:00:01 2020