--- Log opened Mon Jan 27 00:00:23 2020
02:00 -!- belcher [~belcher@unaffiliated/belcher] has joined #secp256k1
03:09 -!- jonatack [~jon@2a01:e0a:53c:a200:bb54:3be5:c3d0:9ce5] has quit [Ping timeout: 272 seconds]
03:35 -!- jonatack [~jon@54.76.13.109.rev.sfr.net] has joined #secp256k1
03:40 -!- jonatack [~jon@54.76.13.109.rev.sfr.net] has quit [Ping timeout: 268 seconds]
03:40 -!- jonatack [~jon@213.152.162.154] has joined #secp256k1
06:08 -!- jonatack [~jon@213.152.162.154] has quit [Ping timeout: 265 seconds]
07:13 -!- roconnor [~roconnor@host-104-157-187-25.dyn.295.ca] has joined #secp256k1
10:40 -!- jonatack [~jon@88.124.242.136] has joined #secp256k1
10:44 -!- jonatack [~jon@88.124.242.136] has quit [Ping timeout: 240 seconds]
10:44 -!- jonatack [~jon@2a01:e0a:53c:a200:bb54:3be5:c3d0:9ce5] has joined #secp256k1
15:35 < elichai2> sipa: it looks like all ed25519 implementations do this https://docs.rs/ed25519-dalek/0.9.1/src/ed25519_dalek/ed25519.rs.html#574-597 https://ed25519.cr.yp.to/python/ed25519.py and more
15:35 < elichai2> (checked already 4 different implementations including supercop)
15:38 < sipa> elichai2: cool, thanks
16:31 < gmaxwell> elichai2: do what?
16:32 < gmaxwell> Take the public key as an argument?
16:32 < sipa> gmaxwell: i suspect he's referring to https://github.com/bitcoin-core/secp256k1/pull/558#discussion_r371533366
16:33 < gmaxwell> yeah, well you have an additional complication of the sign flipping.
16:33 < elichai2> gmaxwell: yes.
16:35 < elichai2> I'm talking about the problem of untrusted pubkey used to generate 2 equations with 2 variables
16:35 < sipa> it'd be nice to have a proof that signing-with-untrusted-pubkey (where this untrusted pubkey is fed to the nonce derivation function) was secure
16:36 < gmaxwell> but it's not really a problem in ed25519 because the only thing it does with the public key is stuffs it into the e hash, and presumably it stuffs the same data into the nonce hash?  (if it doesn't they're pants on head stupid and should be shot)
16:36 < sipa> then we could just standardize that, and have an API that implement that modified signing algorithm; getting the flip bit wrong will just result in invalid signatures
16:36 < gmaxwell> in bip-schnorr you have the added problem in that you can get it to sign with -1*x if you lie to it.
16:37 < sipa> gmaxwell: pretty sure ed25519 nonce derivation is fixed by the protocol, and does not include the public key
16:37 < gmaxwell> okay the ed25519 people should be shot, it's an input to e and not an input to their nonce function
16:38 < gmaxwell> (I just checked)
16:38 < gmaxwell> I would make a singificant bet that this is exploitable in some software/protocol.
16:38 < gmaxwell> it's like sibling of msft not making the generator (an implicit) part of the pubkey.
16:39 < gmaxwell> at least it's fixable without breaking compatibility for them.
16:39 < gmaxwell> in our case, the flipping x based on the PK value is problematic.
16:40 < gmaxwell> Because there is no computationally efficient fix.
16:40 < gmaxwell> (that handled PK being untrusted)
16:41 < gmaxwell> it's a non-issue if keygen were changed so that x never needs to be flipped, but I understand the reasons you didn't want to do that.
16:41 < sipa> feeding the negation bit to the nonce derivation function fixes it, no?
16:41 < gmaxwell> maybe the solution is to have a secp256k1_secret_key object that has x and a flipping flag?
16:41 < gmaxwell> hm!
16:41 < sipa> (we have no proof that that fixes it, but i think that fixes the known attack)
16:41 < gmaxwell> okay, yes it does.
16:42 < sipa> this is my dilemma
16:42 < gmaxwell> the public key should be fed in too. any input to e (except the nonce itself) should be.
16:42 < gmaxwell> what ed25519 is doing is dangerous and wrong.
16:42 < sipa> if we had a proof, we'd just standardize an alternative signing with known public key, which feeds that data into the nonce derivation function
16:43 < sipa> but we don't, so i'm worried about doing that
16:43 < gmaxwell> well we already have a problem with proof techniques used for this, because apparently no one has noticed the exploitable ed25519 interfaces before.
16:44 < sipa> my preference right now is to not have any standardized signing algorithm with known pubkey, because we don't know if it can be done securely at all, if the pubkey is untrusted
16:44 < sipa> and if we find a proof for that, add one
16:45 < sipa> (which would then be distinct from the normal signing-with-just-privkey one)
16:45 < gmaxwell> sipa: ignore for a minute that QR keys are required by the verifier.
16:46 < sipa> sure
16:46 < gmaxwell> e is a random oracle. If pubkey,sign are inputs to e and either k is random or k also has pubkey,sign... then having you sign with these is equiviently to me having you sign different unrelated messages with x and -x.
16:47 < gmaxwell> which I don't think looks frighteningly different from signing chosen messages with two distinct armory HD wallet keys. (or tor onion HSv3 derrived keys)
16:48 < gmaxwell> the latter of which I believe there is a security proof for.
16:49 < gmaxwell> I think, in fact, you can make a black box reduction if a -x/x breaker to make a tor HSv3 breaker.
16:49 < sipa> gmaxwell: the concern isn't just lying about the sign
16:50 < sipa> you could lie about the public key entirely, though i certainly believe that is unexploitable... having a proof that actually incorporates this would be nice
16:50 < sipa> i mean... the claimed pubkey goes directly into the signature hash, no way that someone is going to make that signature pass if the pubkey is wrong
16:51 < gmaxwell> but lying about the public key entirely is like not lying about the public key having extra random data that goes into the message.  They're isomorphic because random oracle.
16:52 < gmaxwell> (IF and ONLY IF pubkey goes into the nonce function, of course, otherwise it's trivially exploitable like in the ed25519 implementations)
17:43 -!- belcher [~belcher@unaffiliated/belcher] has quit [Quit: Leaving]
19:10 < roconnor> I've only half been paying attention to this thread, but if the pubkeys got an oddness tiebreaker, wouldn't that slow down verification, because we'd have to do a full field normalization of the recovered y coordinate in the lift_x function?
19:12 < roconnor> Though perhaps that price is too small to even bring up.
19:12 < sipa> roconnor: yes, an additiinal multiplication and normalization
19:13 < sipa> but also you lose the need to compute a jacobi symbol
19:14 < gmaxwell> huh? there is no jacobi needed for the pubkey in verrification.
19:14 < gmaxwell> the value that comes out of the sqrt is the right one.
19:15 < gmaxwell> roconnor: you're right but I think it's too small to worry about. /me checks
19:15 < gmaxwell> (the relevant ratio is the ratio of the normalize_var to the sqrt)
19:18 < gmaxwell> hmph there is no benchmark for field_normalize_var right now, lol
19:20 < gmaxwell> roconnor: the normalize_var is 0.09% of the time the sqrt takes here, so thats the best case speedup. It's pretty small.
19:21 < gmaxwell> the reason there are multiple normalize functions isn't because normalization is expensive, but rather because there are a whole bunch of them in an ecmult.
19:26 < sipa> oh, nvm, i'm confusing signing with verification
19:29 < roconnor> ok
19:35 < sipa> yeah, it adds a normalization + optional negation to verification
19:35 < gmaxwell> negation isn't needed in this case, since the 'sign' would be fixed.
19:39 < sipa> P is used in the verification algorithm, so its full X/Y coordinates need to be down
19:39 < sipa> *known
19:39 < sipa> if its Y coord is wrong, it needs to be flipped
19:39 < gmaxwell> sipa: I think the standard nonce function really needs to be changed to include the pubkey. It should also be changed to include the jacobi flag.
19:40 < gmaxwell> sipa: oh right if oddness is the tiebreaker.
19:40 < gmaxwell> redoing math
19:41 < gmaxwell> ... no field negate in the benchmark either.
19:41 < sipa> gmaxwell: do you think that's really necessary in case the signing algo takes in a private keys only?
19:42 < sipa> i agree that if we specify a signing algo with privkey+pubkey, we should...
19:42 < gmaxwell> sipa: I think that it's harmless in that case, adding almost no cost (plz arrange so it can be precomputed and midstate cached)...  and it helps avoid being broken like apparently every ed25519 implementation out there.
19:43 < sipa> it's really annoying that privkey + pubkey + negation flag is >64 bytes
19:46 < sipa> i guess, not really
19:46 < gmaxwell> at least that could be precomputed if you care about the highest possible performance. (at least if you zero extend to a multiple of 64)
19:46 < sipa> oh, it's not increasing the number of sha256 compression calls!
19:47 < gmaxwell> ah, sure enough, if you don't pad anything it fits.
19:59 < gmaxwell> heh..  if nonce function is H(p || m || flag || x) and  the challenge hash were H(p || m || r),  they could share computation. (not worth it, r first is better, but I thought it was a cute observation)
20:07 < gmaxwell> the nonce generation function really should have G commited to into it, too.  Say you had two programs, One that signed over G and the other that signed over H.  I ask you to sign the same message in both... k is the same in each case because G is not an input to the nonce function. But the image of k in the EC group is not the same, and your key is leaked.
20:07 < gmaxwell> you could wave this away saying that the G is a property of the 'system' and that if G changed the tag should change...
20:08 < sipa> the adding G will increase the number of compression calls
20:09 < gmaxwell> no, because it can be entirely precomputed as part of the tag.
20:10 < gmaxwell> already you pad up the tag for that reason.
20:10 < gmaxwell> just put it inside the tag.  H(bip-schnorr||G) || H(bip-schnorr||G)
20:14 < gmaxwell> what are people calling derandomized nonces that take a random input?
20:18 < sipa> synthetic nonces
20:18 < sipa> is the term trevor introduced i think
20:19 < gmaxwell> thanks.
20:28 < gmaxwell> Does this post sound reasonable (for modern crypto curves list)  https://0bin.net/paste/axO1c1wbTm5XaxFT#9Z0k6Z2X0yvDzPkBa62RR5a95KXp3Nu7kQ32MJ1gu53
20:44 < gmaxwell> sipa: including the generator is maybe generally overkill but we do have people in bitcoin land using alternative generators a bit.
20:44 < gmaxwell> of course, even if it was included, some genius will manage to use the wrong nonce function anyways. :)
20:44 < gmaxwell> but including it is a way to document the fact that you can't just switch it around without security considerations.
20:51 < roconnor> obviously the bip-schnorr tag should be the Merkle-root of a Simplicity program that implements the verifier. :P
20:59 < sipa> roconnor: or the signer?
20:59 < sipa> using the same tag for distinct but individually valid signers may be a problem
21:18 < gmaxwell> really the tag needs to be distinct if e is distinct.
21:18 < gmaxwell> otherwise I think it doesn't matter too much.
21:28 < gmaxwell> if no one thinks that post is awful, I'm going to send it.
21:55 < sipa> are we absolutely sure the implementations are vulnerable?
21:59 < gmaxwell> I'm absolutely sure DJB's python one is and ed25519 donna.
21:59 < gmaxwell> (and trevor's pseudocode)
21:59 < gmaxwell> If I'm somehow mistaken, I'm sure I'll get yelled at. :)
22:00 < gmaxwell> I'm not quite sure I should call it a vulnerablity. It's not a vulnerablity until its embedded in an implementation that accepts an incorrect pubkey.
22:00 < gmaxwell> It's a fragility.
22:00 < sipa> yeah
22:01 < gmaxwell> "Ed25519 / EdDSA key leakage due to fragility in recommended nonce procedure" is my revised subject line.
22:12 < sipa> sounds fair
22:14 < gmaxwell> After thinking more about fault attacks, damn, it really makes me want to always use a synthetic nonce, cycle counter or something in its input.
22:15 < gmaxwell> it would be exceptually easy to track nonce generation vs challenge generation based on timing and or power consumption then drop out the power (or blast with RF) to corrupt the challenge hash.
22:16 < gmaxwell> I hope hardware wallets verify their signatures before outputting them.
22:17 < gmaxwell> the thing I don't think I previously realized is that the fault doesn't have to be at all controlled.. ANY fault durring the challenge hash will work, so long as the processor doesn't crash completely.
22:21 < gmaxwell> aside, this kind of nonce reuse vuln works across different groups. if I can get you to use rfc6979 as specified to sign using the same key in P256 and some secp256k1 thing, I also can recover your key... even though the group orders are different. (we're hardened in libsecp256k1 by the 'algo' input)
22:25 < sipa> yup, with fault injection in the keygen you don't even need to know what the fault was
22:25 < sipa> eh, nonce derivation
22:28 < gmaxwell> yeah, hitting either the kG ecmult step (which is the longest in terms of cpu time) OR the challenge hash is sufficient.
22:41 -!- BlueMatt [~BlueMatt@unaffiliated/bluematt] has quit [Ping timeout: 260 seconds]
22:42 -!- BlueMatt [~BlueMatt@unaffiliated/bluematt] has joined #secp256k1
23:44 < sipa>  gmaxwell: so you get the weird (but harmless) effect that signing with key x and -x, which have the same public key, will give distinct signatures
23:45 < gmaxwell> seems harmless to me.
23:46 < gmaxwell> after all 'synthetic nonces'.
23:51 < sipa> yeah
--- Log closed Tue Jan 28 00:00:22 2020