--- Log opened Tue May 07 00:00:05 2019 00:20 -!- jtimon [~quassel@181.61.134.37.dynamic.jazztel.es] has joined #secp256k1 00:41 < gmaxwell> andytoshi real_or_random : you might want to head over to https://forums.sifive.com/t/cycle-counts-on-unleashed-board-seem-innaccurate/2266/17 and tell them how to configure the memory usage. 02:25 -!- elichai2 [uid212594@gateway/web/irccloud.com/x-qyucheftvkhqqsim] has joined #secp256k1 02:26 < elichai2> Hey, I'm reading bip schnorr, and if I understand correctly there's another nice upside, 02:26 < elichai2> Which is you don't have to give the preimage of the message in order to successfully verify the signature, because it's hashed again with r and P, am I right? 02:28 -!- midnightmagic [~midnightm@unaffiliated/midnightmagic] has quit [Ping timeout: 264 seconds] 02:30 < real_or_random> I'm not sure if I understand your question 02:31 < gmaxwell> elichai2: yes, it has that property, though bitcoin's ecdsa does too (due to the double hashing) 02:31 < real_or_random> the scheme in bip-schnorr signs messages of size 32 bytes. it does not care what these messages are 02:31 < gmaxwell> real_or_random: right but it's _secure_ to show you an arbritary 32 byte message. 02:32 < real_or_random> can you explain? 02:32 < gmaxwell> elichai2: the cascaded hashes though has some theoretical security reduction. it's done the way its done mostly for performance reasons. 02:32 < elichai2> real_or_random: yeah but in ecdsa there's an assumption that you have the message. 02:32 < elichai2> The way bitcoin solves this is by providing a preimage 02:32 < gmaxwell> elichai2: bitcoin's ecdsa hash is sha256^2 so you could provide only the middle state... 02:32 < elichai2> Regular ecdsa requires the message to be a public knowledge 02:33 < elichai2> gmaxwell: is secp256k1 gets the first hash and hashes again or does it receives it after the double hash? 02:33 < gmaxwell> real_or_random: ecdsa takes a 32 byte input, but if I show you a {m,r,s} tuple, you don't know if it's a real signature or a forgery, because you don't know m was a hash. 02:33 < elichai2> *does 02:34 < gmaxwell> elichai2: it has nothing to do with secp256k1. Almost every use of sha2 in bitcoin is sha2(sha2(x)). 02:34 < gmaxwell> elichai2: including the hashes used for signing w/ ecdsa. 02:34 < real_or_random> gmaxwell: okay, yeah. but I think it's wrong that to claim that ECDSA takes a 32 byte input as the message 02:34 < elichai2> Yeah, but current secp implementations doesn't add another hash so you have to have the preimage 02:35 < elichai2> Btw, if anyone wants to explain why batch verification requires deterministic randomness I couldn't figure it out. Why can't I just aggregate the sigs and pubkey and try to verify? 02:35 < gmaxwell> elichai2: I have no clue what you're talking about. 02:35 < real_or_random> ECDSA internally computes a 32 byte hash of the message, but that's not part of its interfaci 02:36 < elichai2> gmaxwell: I'm talking about bip schnorr batch verification 02:36 < gmaxwell> elichai2: my no idea was regarding your prior comment. 02:37 < real_or_random> elichai2: first of all, it does not require deterministic randomness. real randomness is fine too. it's just easy to screw up, so we suggest to deterministic randomness 02:37 < gmaxwell> real_or_random: yes, you can say that--- but then bitcoin is giving that hash a hash output as the input, which is exactly the property elichai2 thought was new in bit-schnorr. 02:37 < gmaxwell> elichai2: it must be randomized or it is trivial to forge a batch. 02:37 < real_or_random> gmaxwell: indeed 02:37 < gmaxwell> s/bit-schnorr/bip-schnorr/ 02:38 < elichai2> Oh. Hmm if the secp implementation receives a message as a 32 byte hash already then it's your responsibility to make sure you have the preimage and you hash it. Otherwise it's insecure. But in the schnorr implementation this isn't true 02:38 < real_or_random> elichai2: think about how you can play around with s1 and s2 in batch of two signatures 02:39 < elichai2> Hmmm It might be possible to make something similiar to Rouge key attack but a Rouge signature attack? 02:39 < elichai2> By computing a malicious s value 02:40 < gmaxwell> elichai2: exactly. 02:40 < real_or_random> yes, that intuition will give you one possible attack 02:40 < gmaxwell> not even the only possible attack though! 02:40 < gmaxwell> you can just straight up use a rogue key attack too. 02:41 < elichai2> I'll try to create an attack like that to really understand this because I'm still not sure if I understand how randomness solves this 02:42 < gmaxwell> elichai2: the fact that the implementation takes a pre-hashed value is arguably an implementation mistake, it violates our design principles. Probably half the reason it works that way is just inertia, and the other half was because we didn't want to embed a high performance hash in the library. 02:43 < real_or_random> check (e.g.) dan bernstein's paper on eddsa for an explanation why batch verification is secure 02:43 < elichai2> But you still have hmac in there for ecdsa's k value, don't you? 02:43 < elichai2> real_or_random: I'll look for it. Thanks! (djb?) 02:43 < real_or_random> yep 02:44 < elichai2> gmaxwell: and hmac uses sha2 anyway 02:44 < gmaxwell> elichai2: we don't consider signing to be particularly performance critcial. 02:44 < elichai2> Oh 02:44 < gmaxwell> so it doesn't matter that what we have is a naieve implementation. 02:44 < elichai2> OK, understood. Thank you 02:45 < gmaxwell> sha2 in bitcoin core's codebase is many times faster (esp on hardware with SHA-NI) 02:45 < elichai2> (maybe it'll be possible to make it a library by itself and then link secp256k1 to it) 02:45 < gmaxwell> (RFC6979 is kind of a performance joke regardles... you'd need to use a difference nonce function if you cared about speed...) 02:45 < elichai2> I need to dive into secp256k1 code, it's not an easy to read library haha 02:46 < gmaxwell> weird, we've gotten a bunch of complements on it being easy to read. 02:46 < real_or_random> what's easy to read? 02:47 < elichai2> Really? I implemented my own naive not safe implementation so I'll have a reference, by overloading the operators my library looks almost like the algabreic functions themselves 02:47 < real_or_random> maybe we should port core's SHA256 to secp then for schnorr, now that we need it for verification too 02:47 < gmaxwell> elichai2: that kind of coding is virtually impossible to review. 02:48 < gmaxwell> real_or_random: or just let the interface take the hash function as an argument...? 02:48 < elichai2> gmaxwell: yeah, I didn't say that's how secp should work, just why it's harder to read, but I'll try to invest the time to know it better (and get my C better) 02:48 < gmaxwell> elichai2: well you're using a different definition of easy to read than some other people do. 02:48 < elichai2> Is there already a secp PR that I can review the changes that are needed to add schnorr (and musig) 02:49 < gmaxwell> elichai2: the people that complemented it were all people reviewing it for vulnerablities. indirection that hides that actual behavior makes it unreadable for that purpose. 02:49 < real_or_random> hm, yes. possible. but I'm not sure. another possibility to screw up as a user. 02:49 < elichai2> Oh. Yeah, you're right, if you're reviewing it you prefer that everything is explicit 02:49 < gmaxwell> real_or_random: yea, the challenge is that anything faster than what we currently do needs runtime hardware autodetection. 02:49 < gmaxwell> real_or_random: which we could do as part of context creation. 02:50 < real_or_random> I mean... it's always possible to shoot yourself in the foot but I always prefer to make it very hard^^ 02:50 < gmaxwell> real_or_random: but also really getting the best performance out requires vectorized hashing. 02:50 < real_or_random> a related issue is that nickler's PR implements chacha20, which is also already in core (nothing particular wrong about that, but why mantain the same code twice) 02:51 < gmaxwell> well there is essentially nothing to maintain in functions lik that. 02:51 < gmaxwell> like* 02:51 < gmaxwell> And this is the cost of it being a seperate library. 02:51 < elichai2> real_or_random: I agree with you. I think that hardware detection in the context isn't so bad and then you can decide between Intel's NI instructions and AVX2 etc. 02:51 < real_or_random> elichai2: there is a PR here https://github.com/bitcoin-core/secp256k1/pull/558 02:52 < elichai2> Thanks! I'll go read that and djbs paper now :) 02:53 < real_or_random> that's true sure. but having it only once seems still cleaner than having it twice 02:53 < gmaxwell> real_or_random: all the sha2 implementations get a lot more speedup if there are multiple independant things to hash at once... my thinking before is that we'd just address faster hashing in the batch interface and not worry otherwise. 02:53 < gmaxwell> real_or_random: meh, different demands, bitcoin is probably going to end up with AVX chacha shortly after the p2p encryption goes in. 02:54 < real_or_random> and there we could actually think about another hash function even. (not sure if people will like this idea) 02:54 < gmaxwell> for what? the batch rng? 02:56 < real_or_random> yep 02:56 < real_or_random> not for the rng 02:56 < real_or_random> but for the hashing to create the seed 02:56 -!- belcher [~belcher@unaffiliated/belcher] has joined #secp256k1 02:57 < gmaxwell> right, well on hardware with sha-ni, if its used, sha2 is pretty much the fastest general strong hashfunction available. 02:57 < gmaxwell> for the rngs we could ultimately pick the hasher based on the platform. 02:58 < elichai2> Is there any world in which the message will be hashed in sha3/blake2? 02:58 < elichai2> So that bitcoin might slowly move to those? 02:59 < gmaxwell> doubtful, they aren't attractive functions. 02:59 < gmaxwell> esp w/ the increasing deployment of sha-ni, they're both vastly slower than sha256. 03:00 < gmaxwell> SHA3 process was created in part because of concerns that new attacks against sha2 would materialize that simply didn't. 03:00 < gmaxwell> it's good that there are already existing alternatives, at least, but that doesn't make for a real reason to use them. 03:01 < gmaxwell> you see them crop up in altcoins for essentially buzzword marketing reasons, all the better to seperate fools from their money. 03:02 < elichai2> There's one known attack against sha2 that is mitigated in those, being length extension attack, but AFAIK this isn't relevant to bitcoin's use case 03:02 < elichai2> Especially with the double sha2 03:04 < gmaxwell> the length extension issue also doesn't apply to sha384, sha224, sha512/256, or sha512/224, nor does it apply to HMAC-SHA256 which is almost certantly what you should be using when a length extension would matter. 03:05 -!- midnightmagic [~midnightm@unaffiliated/midnightmagic] has joined #secp256k1 03:05 < gmaxwell> blake2 has had a lot less scrutiny, I'd probably happily use it in cases where cryptographic security isn't that critical... except its a lot slower and more power hungry than sha2 w/ hardware support. 03:11 -!- jtimon [~quassel@181.61.134.37.dynamic.jazztel.es] has quit [Ping timeout: 250 seconds] 03:12 < nickler> elichai2: MuSig is merged into secp256k1-zkp here https://github.com/ElementsProject/secp256k1-zkp/tree/secp256k1-zkp/src/modules/musig 03:13 < elichai2> Last question :) I remember in the musig paper that the whole R point is in the message, but in bip schnorr it's just the x(R) 03:13 < elichai2> nickler: thanks! 03:14 < nickler> x(R) implies R because its the R where y is a quadratic residue 03:15 < gmaxwell> I doubt the musig paper ever specifies how R is serialized in any detail, but bip-schnorr only allows one of the two possible points sharing an x. 03:16 < elichai2> Yeah I got that just that it's not using the paper as a reference, and what's the relationship between quadratic residue and point being in the lower or upper side? (and from that being odd or even) 03:16 < elichai2> Does every point have a quadratic residue? It has any sort of relationship to upper/odd? 03:17 < elichai2> gmaxwell: you're right. The paper doesn't talk about serialization 03:17 < gmaxwell> QRness is the natural tiebreaker between the two possible points, since the reason that there are two possiblities is because of two solutions to the square-root. 03:18 < gmaxwell> The fact that even/odd works is basically just a number theory coincidence. 03:21 < elichai2> So it's the more natural name of the same phenomena In the EC? 03:22 < gmaxwell> it's not the same as even/odd. 03:23 < elichai2> For me upper/lower is easiest to visualize, even/odd is only because p is odd 03:24 < gmaxwell> every x value will have two possible y's (in curves of this type), one will be even the other odd. One will be a quadratic residue, the other a quadratic non-residue. the relationship between the two properties is random. 03:25 < gmaxwell> using QR as the tiebreaker allows some speedups because it can be tested for without fully computing Y in some cases. 03:25 < gmaxwell> Also because the SQRT in point decompression naturally returns a QR value. 03:35 < elichai2> makes sense 04:31 -!- arubi [~ese168@gateway/tor-sasl/ese168] has quit [Remote host closed the connection] 04:31 -!- arubi [~ese168@gateway/tor-sasl/ese168] has joined #secp256k1 05:01 -!- jtimon [~quassel@181.61.134.37.dynamic.jazztel.es] has joined #secp256k1 06:53 < sipa> elichai2: the details of what the quadratic residue meams are not even relevant here 06:53 < sipa> elichai2: in our application, you can reconstruct the full R point from its x coordinate 06:53 < sipa> that is all 06:55 < sipa> gmaxwell: fwiw, the qr/nonqr tiebreaker only works because -1 is a nonqr in our field 06:56 < elichai2> sipa: thanks, I read more and I understand now that QR is the "native" square without going over the modulo, just wanted to understand the different semantics 06:59 < sipa> ok! 09:35 -!- jtimon [~quassel@181.61.134.37.dynamic.jazztel.es] has quit [Ping timeout: 250 seconds] 10:07 -!- jtimon [~quassel@181.61.134.37.dynamic.jazztel.es] has joined #secp256k1 12:44 -!- elichai2 [uid212594@gateway/web/irccloud.com/x-qyucheftvkhqqsim] has quit [Quit: Connection closed for inactivity] 13:14 -!- ddustin [~ddustin@unaffiliated/ddustin] has joined #secp256k1 13:15 -!- ddustin [~ddustin@unaffiliated/ddustin] has quit [Read error: Connection reset by peer] 13:15 -!- ddustin [~ddustin@unaffiliated/ddustin] has joined #secp256k1 13:16 -!- ddustin [~ddustin@unaffiliated/ddustin] has quit [Read error: Connection reset by peer] 13:17 -!- ddustin [~ddustin@unaffiliated/ddustin] has joined #secp256k1 13:18 -!- ddustin [~ddustin@unaffiliated/ddustin] has quit [Read error: Connection reset by peer] 13:18 -!- ddustin [~ddustin@unaffiliated/ddustin] has joined #secp256k1 14:40 -!- ddustin [~ddustin@unaffiliated/ddustin] has quit [Remote host closed the connection] 14:41 -!- ddustin [~ddustin@unaffiliated/ddustin] has joined #secp256k1 14:41 -!- ddustin [~ddustin@unaffiliated/ddustin] has quit [Remote host closed the connection] 14:41 -!- ddustin [~ddustin@unaffiliated/ddustin] has joined #secp256k1 14:42 -!- ddustin [~ddustin@unaffiliated/ddustin] has quit [Remote host closed the connection] 14:42 -!- ddustin [~ddustin@unaffiliated/ddustin] has joined #secp256k1 14:43 -!- ddustin [~ddustin@unaffiliated/ddustin] has quit [Remote host closed the connection] 14:43 -!- ddustin [~ddustin@unaffiliated/ddustin] has joined #secp256k1 14:44 -!- ddustin [~ddustin@unaffiliated/ddustin] has quit [Remote host closed the connection] 14:44 -!- ddustin [~ddustin@unaffiliated/ddustin] has joined #secp256k1 14:48 -!- ddustin [~ddustin@unaffiliated/ddustin] has quit [Ping timeout: 246 seconds] 17:00 -!- instagibbs [~instagibb@pool-100-15-135-248.washdc.fios.verizon.net] has quit [Ping timeout: 252 seconds] 18:28 -!- instagibbs [~instagibb@pool-100-15-135-248.washdc.fios.verizon.net] has joined #secp256k1 18:59 -!- jtimon [~quassel@181.61.134.37.dynamic.jazztel.es] has quit [Ping timeout: 268 seconds] 23:04 -!- jtimon [~quassel@181.61.134.37.dynamic.jazztel.es] has joined #secp256k1 23:40 -!- jtimon [~quassel@181.61.134.37.dynamic.jazztel.es] has quit [Ping timeout: 246 seconds] --- Log closed Wed May 08 00:00:06 2019