--- Day changed Fri Feb 19 2016 05:39 < jonasschnelli> gmaxwell: I somewhere read in my IRC history that you where looking for a GIT visualization of the secp256k1 repository? Right? Same style as the bitcoin.git visu? 05:40 < jonasschnelli> Only 2015? 07:21 < gmaxwell> Would be neat, not urgent. It could cover more than 2015. 07:30 < jonasschnelli> Can try it... but, I accidentally lost the command line options I uses for the bitcoin/bitcoin visu. But I think it was not that complicated. Will try, but not today or tomorrow. :9 09:08 < gmaxwell> Cool. Thanks! 09:22 < gmaxwell> So, EM sidechannel attack on libgcrypt https://lwn.net/SubscriberLink/675912/6a17ec8bf48b958e/ In particular, they use a NAF implementation for ECDH and the attacker distinguishes -1 and 1 in the sequence by picking P such that P.y or -P.y has a very small value. It looks like libgcrypt's fix is to just change to a simple double and always add. 09:22 < gmaxwell> TD-Linux: ^ 09:23 < gmaxwell> It isn't clear to me if their sidechannel is exploiting non-constant-operation properties of the underlying field implementation; or if it's a true EM leakage in a fixed ladder, e.g. multiplying with 0 making a different EM signal than non-zero. 09:32 < gmaxwell> wow; the former 09:32 < gmaxwell> this code isn't even _remotely_ constant time. 09:32 < gmaxwell> I'm skeptical that this is fixed at all. 09:33 < gmaxwell> All the field operations are done using very generic multi-precision integer code. E.g. the multiplies are a bignum multiply followed by a divmod for the modular reduction. The divmod is really branchy and resizes numbers as it goes. 09:37 < gmaxwell> in any case, this code is crap. But it did cause me to note that we're not doing even projective blinding in our ECDH code, and we should do that. 09:47 -!- andytoshi [~andytoshi@unaffiliated/andytoshi] has joined #secp256k1 09:48 < andytoshi> hi gmaxwell .. you say we're not doing projective blinding. you mean multiplying by a random z value? 09:55 < gmaxwell> andytoshi: correct. If you look at ecmult_gen, it uses random precomputed initial point.. and that point is randomly scaled via secp256k1_gej_rescale. 09:57 < gmaxwell> for ECDH using an initial point would be costly, but doing random scaling would be very cheap. 09:57 < gmaxwell> And would be sufficient for masking any EM signature that comes from specially chosen values. 10:04 < andytoshi> ok, i'll open an issue for this 10:04 < andytoshi> i guess it's like a one-line change but i need some time to context switch and i'm unsure when i'll have that 10:05 < gmaxwell> well the one line version would let it use some static value in the context. Though ideally it should be a different one on every invocation. 10:06 < gmaxwell> I could do the one line version easily-- it's not urgent in any case.. but I think prudent. 10:07 < andytoshi> oh, i was thinking i could generate a new one on every invocation and not touch the context 10:07 < andytoshi> we have access to a rng right? 10:07 < andytoshi> just call gej_rescale at the top of the function 10:08 < andytoshi> top of ecmult_const 10:08 < gmaxwell> well right at the ge to gej conversion. But yes. 10:08 < gmaxwell> we have sha256, but: it's slow, and right now, ecdh doesn't mutate the context. We have no access to a general RNG. 10:10 < gmaxwell> I think the easiest thing to do is to just use a random value in the context, and don't mutate it inside ecdh; only in secp256k1_context_randomize. 10:10 < andytoshi> sgtm 10:10 < andytoshi> and by random you mean sha256 of some string or something, like the current point blinding 10:11 < andytoshi> in ecmult_gen 10:12 < gmaxwell> andytoshi: we have a function secp256k1_context_randomize which mutates the context to update the random blindin... it takes a 32 byte input that is used to randomize the initial point. 10:12 < andytoshi> thaats right 10:12 < gmaxwell> Same function could update a field element (actually we could just use the x of the random initial point)... AFAIK. 10:13 < gmaxwell> though I don't think making secp256k1_context_randomize generate another field element when ECDH is compiled in would be a big performance hit. 10:13 < andytoshi> i think that's fine 10:14 < andytoshi> the sort of user who cares abotu this is probably not randomizing super often anyway 10:14 < andytoshi> what i'd like to do (and i'd have suggested had you not preemptively said it was slow) was to use sha256(x) of the input point in ecmult_const 10:14 < andytoshi> to randomize on every call 10:15 < andytoshi> oh, i guess that still lets you do chosen point stuff by grinding 10:16 < gmaxwell> andytoshi: yes, but it's probably impratical to get a really strong EM signature from that. And not possible to grind even if there was a only-random-once nonce. 10:16 < gmaxwell> But sha256 is slow, and if our hardware is EM leaky, I'm not super excited about performing more operations on the secret key than strictly needed. 10:18 < andytoshi> ok, here's a proposal 10:19 < gmaxwell> andytoshi: I by "really strong em signature", I mean in the gcrypt attack they're using a point where y=1 (or similar) and so -y is some huge number with most of the bits set. ... you could grind sha256 but you're not going to get values where -y/y have a hamming weight difference or magnitude difference of more than a couple dozen bits. 10:19 < andytoshi> we generate a random-only nonce. in ecmult_const we take the x-coord of the public point and xor with that 10:19 < andytoshi> and scale z by that value 10:19 < andytoshi> yeah, i gotcha. i ran those calcs once. you're right 10:20 < andytoshi> i don't see any need to touch secret keys here, we only screw with the points, and we do so in a way that preserves what point it is (so there's not even a correction step or anything) 10:20 < andytoshi> s/random-only nonce/random-once nonce/ 10:20 < gmaxwell> andytoshi: hm. well Z needs to be a field element, the xor of two field elements may not be one. Add them? 10:20 < andytoshi> yup, that works 10:21 < gmaxwell> well crud... it needs to be a member of the multiplicative group, e.g. non-zero. 10:21 < gmaxwell> Which addition will not uphold (thouh with neglible probablity. --- but in the case where the randomization is a constant because no one ever really randomized, the fault would be reachable) 10:22 < andytoshi> yes 10:22 < andytoshi> but if it's zero in the non-randomized case it's ok 10:22 < andytoshi> or some other value for which there is no point with x = -value 10:23 < andytoshi> so like, we default to sha256("the hash of this is a value x such that y^2 = -x^3 + 7 has no solution in our field") 10:23 < andytoshi> and rerandomize just chooses a random value and assumes we have negligible probability of having trouble 10:23 < andytoshi> and if we *do* get zero on some call to ecmult we just fail the ecdh call 10:24 < gmaxwell> okay, then the randomize would have to check the curve equation. That could be done. 10:24 < andytoshi> oh, yeah, we could do that even, and keep rerandomizing until we get one that doesn't work 10:24 < andytoshi> doesn't allow creating zeros* 10:25 < andytoshi> we throw away 1-2 bits doing that (i'm unsure if it's half the values or 1/3 or 2/3) but not much 10:25 < gmaxwell> it's 1/2. 10:25 < andytoshi> oh, yes, we're solving y for y^2 10:25 -!- Netsplit *.net <-> *.split quits: roasbeef 10:25 -!- Netsplit over, joins: roasbeef 10:25 < gmaxwell> though it would be slow... even though it would never fail more than a couple times. 10:26 < gmaxwell> because it needs the sqrt. 10:26 < andytoshi> yeah, that's a big hit 10:26 < andytoshi> i don't want to discourage people calling _randomize all the time 10:26 < gmaxwell> it could multiply instead of adding. 10:26 < andytoshi> yes, that'd be equivalent 10:27 < andytoshi> though i guess it adds one field op to ecmult_const 10:27 < andytoshi> oh, the scaling is already like 5 :P --- Log closed Fri Feb 19 10:27:21 2016 --- Log opened Fri Feb 19 10:27:42 2016 10:27 -!- kanzure [~kanzure@bryan.fairlystable.org] has joined #secp256k1 10:27 -!- Irssi: #secp256k1: Total of 24 nicks [0 ops, 0 halfops, 0 voices, 24 normal] 10:27 -!- so [~so@unaffiliated/so] has joined #secp256k1 10:27 < gmaxwell> well, it would lose more entropy because e.g what happens when I send you an x which has a low multiplicative order mod P ? 10:28 < andytoshi> ugh, i actually forgot that was possible 10:28 < andytoshi> wait, no, that doesn't matter 10:28 < andytoshi> for random c, c*x is random 10:28 < andytoshi> doesn't matter that c*x^n will eventually wrap around 10:28 -!- Madars [~null@unaffiliated/madars] has joined #secp256k1 10:28 < andytoshi> or c^n*x 10:29 < gmaxwell> oh right. okay. 10:29 < gmaxwell> prime field. 10:29 < andytoshi> yeah 10:30 < andytoshi> i guess, if the randomizer has order 2 or 3 (which is extremely unlikely), then when we scale in jacobian coordinates one of the scaling factors will reduce to 1 10:30 < andytoshi> so there is a small loss there. if we had projective coordinates this wouldn't be a thing 10:30 < gmaxwell> yea, the multiply might not add much (with neglible probablity) but it won't hurt. 10:30 < andytoshi> agreed 10:31 < andytoshi> i need to think a little bit to thing if it adds anything at all tbh 10:31 < andytoshi> because it's known that we're multiplying the constant randomizer by the x-coord, which a chosenpoint attacker knows 10:31 < andytoshi> oh, actually, this is good 10:32 < andytoshi> knowing an algebraic relation in the field is basically useless for knowing relationships between the bits (which is what you need for EM analysis) 10:32 < andytoshi> unless that relation is equality :) 10:33 < gmaxwell> right, well... not useless, but it would certantly require a much more complex analysis. 10:33 < andytoshi> yup 10:34 < andytoshi> so while i think we get almost all the advantage from a constant randomizer, this gives us a bit of a boost and is cheap in terms of code complexity and cycles 10:35 -!- Irssi: Join to #secp256k1 was synced in 513 secs 10:37 < gmaxwell> so could it hurt, e.g. if you make your x=-1modP ? .... no I think not. At least if we assume the EM model is that the attacker is trying to get at least one table entry which has an all zeros or all one word. 10:40 -!- maaku [~quassel@botbot.xen.prgmr.com] has joined #secp256k1 10:40 -!- maaku is now known as Guest44567 10:48 < andytoshi> yeah, i think -1 (or any other specific value) is fine 11:03 -!- wumpus [~quassel@pdpc/supporter/professional/wumpus] has quit [Ping timeout: 276 seconds] 11:14 -!- wumpus [~quassel@pdpc/supporter/professional/wumpus] has joined #secp256k1 12:09 < TD-Linux> gmaxwell, yeah I saw it earlier and that it was more of a timing sidechannel 19:36 -!- andytoshi [~andytoshi@unaffiliated/andytoshi] has quit [Quit: WeeChat 1.4] 19:59 -!- jtimon [~quassel@46.31.134.37.dynamic.jazztel.es] has joined #secp256k1 21:27 -!- andytoshi [~andytoshi@unaffiliated/andytoshi] has joined #secp256k1