--- Log opened Thu Apr 09 00:00:48 2020
00:27 -!- jonatack [~jon@2a01:e0a:53c:a200:bb54:3be5:c3d0:9ce5] has quit [Ping timeout: 265 seconds]
00:29 -!- jonatack [~jon@213.152.161.229] has joined #secp256k1
00:29 -!- jonatack [~jon@213.152.161.229] has quit [Client Quit]
00:38 -!- jonatack [~jon@213.152.161.229] has joined #secp256k1
04:04 -!- Chris_Stewart_5 [~Chris_Ste@unaffiliated/chris-stewart-5/x-3612383] has joined #secp256k1
06:17 -!- sipa [~pw@gateway/tor-sasl/sipa1024] has quit [Remote host closed the connection]
06:17 -!- afk11` [~afk11@gateway/tor-sasl/afk11] has quit [Remote host closed the connection]
06:18 -!- afk11` [~afk11@gateway/tor-sasl/afk11] has joined #secp256k1
06:33 -!- sipa [~pw@gateway/tor-sasl/sipa1024] has joined #secp256k1
06:34 -!- afk11` [~afk11@gateway/tor-sasl/afk11] has quit [Remote host closed the connection]
06:35 -!- afk11` [~afk11@gateway/tor-sasl/afk11] has joined #secp256k1
07:29 -!- ddustin [~ddustin@unaffiliated/ddustin] has quit [Remote host closed the connection]
07:29 -!- ddustin [~ddustin@unaffiliated/ddustin] has joined #secp256k1
10:02 -!- ddustin [~ddustin@unaffiliated/ddustin] has quit [Remote host closed the connection]
10:03 -!- ddustin [~ddustin@unaffiliated/ddustin] has joined #secp256k1
10:16 -!- ddustin [~ddustin@unaffiliated/ddustin] has quit [Remote host closed the connection]
10:16 -!- ddustin [~ddustin@unaffiliated/ddustin] has joined #secp256k1
10:20 -!- belcher [~belcher@unaffiliated/belcher] has joined #secp256k1
11:16 < elichai2> I don't really want to open it. but I would like to hear thoughts/opinions if anyone here has any :) I think generally Schnorr should get the full message as an input and not just the hash of the message.
11:16 < elichai2> for a couple of reasons: A. Otherwise I don't think the scheme can be considered "chosen-prefix resistant" because all you need is a collision on the hash of the message, not on `e`. B. it's more natural to hash the message instead of the hash of the message, and it avoids rare weird interactions between doing multiple hashes. C. because that's what ed25519 does and what most descriptions of schnorr imply.
11:17 < sipa> in theory that is absolutely true
11:17 < sipa> but in bitcoin, the distinction is meaningless
11:18 < sipa> inherently, our messages are hashes (even if they're not hashes directly, the messages contain hashes - all transactions are indirectly hashes of their entire history)
11:19 < sipa> and indeed, we lose the chosen-prefix resistance property
11:19 < sipa> but that's ok, Bitcoin is already way more fundamentally broken if SHA256 is not collision-resistant
11:21 -!- ddustin_ [~ddustin@unaffiliated/ddustin] has joined #secp256k1
11:22 -!- ddustin [~ddustin@unaffiliated/ddustin] has quit [Ping timeout: 246 seconds]
11:22 < elichai2> hmm so you're saying because we already have tons of hash of hashes (double SHA256, inputs, and the way sighashes works) then it doesn't really matter yet another hash just for the sake of simplicity(and profiting from bitcoin's faster sha256 impl)
11:23 < sipa> also it would mean losing the ability to precompute parts of the hash
11:23 < sipa> it's worth pointing out this tradeoff in the BIP, though
11:25 -!- roconnor [~roconnor@host-45-78-205-127.dyn.295.ca] has joined #secp256k1
11:26 < roconnor> Was it this chosen-prefix property that was important for the security proof in the, what was it, generic group model?
11:28 < sipa> i think it's actually random prefix preimage resistance
11:28 < sipa> and random prefix second preimage resistance
11:28 < sipa> which together are sufficient to prove Schnorr's security in GGM
11:28 < sipa> however, collision resistance implies both of these properties
11:28 < sipa> and we're already relying on collision resistant
11:30 < roconnor> Hmmm.  I'm a little behind on the details of this topic.  Are you willing to explain what it would mean for the scheme to be "chosen-prefix resistant"?
11:30 < sipa> i think elichai2 just misspoke
11:31 < sipa> http://www.neven.org/papers/schnorr.pdf
11:32 < sipa> section 4 defines what random-prefix (second-)preimage resistance means
11:33 < roconnor> oh this paper is about GGM.
11:33 < sipa> yes; the alternative is ROM+DL, and ROM implies All The Things(tm) you want for a hash
11:34 < roconnor> I guess the thing that confuses me about elichai2's comment is that we do hash "the message" it is just that the message is limited to 256-bits by our scheme.
11:34 < elichai2> sipa: yep. you're right
11:34 < roconnor> So I'm not quite following the issue raised.
11:35 < sipa> roconnor: right, but if you think about there being a "real message" m, and the scheme being sG=R+H(R||P||H(m)), which is arguably what we're doing, the rpp+rpsp+GGM security proof no longer holds
11:35 < elichai2> roconnor: right. so all these properties are required for the H that creates e. `e = H(R|P|M)` but if `M` is actually `H(M)` then now this second H actually assume collision resistance
11:36 < roconnor> oh really, the proof no longer holds?  I'm surprised, but I didn't really read the proof.
11:37 < sipa> clearly if H is not collision resistant, the scheme cannot be strongly unforgeable
11:38 < sipa> as in that model an attacker can ask an honest signer for any signature on any message, and he wins if he can produce any valid signature that wasn't exactly produced by the honest signer
11:40 < roconnor> Given that our message in our API is limited to 256 bits, it certainly behoves the uses to use a collision resistant hash should they wish to stuff a larger message into the 256 bits.
11:41 < sipa> FWIW, this is rpp: adversary first chooses a hash (and optionally some internal state), is then given a random prefix p, and then the adversary wins if he can come up with a message m such that H(p||m)=h
11:41 -!- ddustin_ [~ddustin@unaffiliated/ddustin] has quit [Remote host closed the connection]
11:42 -!- ddustin [~ddustin@unaffiliated/ddustin] has joined #secp256k1
11:42 < roconnor> In our form of schnorr I guess the adversary is limited to a message of length 256 bits.
11:42 < sipa> and rpsp is this: adversary first chooses a message m, is then given a random prefix p, and then the adversary wins if he can come up with another message m' such that H(p||m) == H(p||m')
11:42 < roconnor> well there are some pubkeys involved, so a few more bits I guess.
11:43 < sipa> if you think of our scheme as simply restricted to 256-bit messages, all existing results hold... but that's kind of a weird abstraction of reality
11:44 < sipa> my point is that this doesn't matter: we're already working in a world where H is assumed to be collision-resistant, so we don't care about the fact that our scheme might also be security under slightly weaker assumptions
11:45 < roconnor> when you wrote sG=R+H1(R||P||H2(m)) the fact that H1=H2 is not mandated by our API.
11:45 < sipa> true
11:47 < elichai2> roconnor: but you can't just look at the API. technically our ECDSA API doesn't mandate that `msg32` will be a hash. But ECDSA actually *does* mandate it and is broken if it's not a hash
11:48 < elichai2> (altough the comment does say it's a `the 32-byte message hash being verified` and bip-schnorr doesn't say that `m` is a hashed message)
11:49 < elichai2> the comment == the comment in the header above ECDSA signing.
11:50 < roconnor> Let's see, in the rpp, the attacker choses h, then is given R and must find m such that H(R||m) = h.  In our application the property would be that the attacher chooses h ad is given R and must find P and m such that H(R||P||H2(m)) = h.  But given that H is SHA256, then this property still assumed to hold no matter how broken H2 is.
11:51 < roconnor> H2 could be the constant 0 function and it would still hold.
11:52 < roconnor> Ah rpsp is the problematic one.
11:55 < sipa> also something i always have to remind myself of: this is existential unforgeability under chosen-message attack: generate a random private x with public key P, give the adversary P, and an oracle that can sign any message with x; the adversary wins if he can come up with a message m and sig s such that (P,m,s) is a valid key-message-sig triplet, without ever having queried the oracle with input m
11:56 < sipa> so if the inner hash is not collision resistant, the adversary trivially wins here
11:59 < sipa> the standard ROM/DL proof for Schnorr proves something even stronger, namely strong unforgeability, which is the same, except the adversary wins if s was not the output of the signing oracle for input m (which adds what we call non-malleability; the adversary here would also win if he can mutate an existing signature without breaking it)
12:03 < roconnor> I see sipa's earlier point now.  if the message is the root of any sort of merkle root structure then all the hashes used in that construction also have to be collision resistant, even if we allowed an API with an arbitrary long message.
12:04 < roconnor> Since putting hashes into the signed message is so common, there is little point in making the full message part of the API if people are just going to fill that message with hash values anyways.
12:04 < roconnor> I mean, I'm just restating what sipa said.
12:05 < sipa> right, exactly
12:05 < sipa> it's a neat bonus point to have a signature scheme that technically relies on slightly less than collision resistance
12:05 < sipa> and if you can avoid giving up that property at no cost, sure
12:11 < roconnor> elichai2: I guess the ECDSA thing is a bit different.  if the message is not a hash, then it is just broken AFAICT.  But in schnorr the 256-bit "message" can be freely set without being broken if your message is truely only 256-bit and you wish to use it this way.
12:11 < sipa> roconnor: that is my understanding too
12:11 < roconnor> elichai2: your point about the dangerous of that ECDSA api is well taken though.
12:12 < sipa> yeah, i think i wrote that before knowing how critical the message being a hash was for security
12:29 -!- jonatack [~jon@213.152.161.229] has quit [Ping timeout: 256 seconds]
12:31 -!- jonatack [~jon@37.164.104.82] has joined #secp256k1
12:31 -!- jonatack [~jon@37.164.104.82] has quit [Client Quit]
12:32 -!- jonatack [~jon@37.164.104.82] has joined #secp256k1
13:20 -!- ddustin [~ddustin@unaffiliated/ddustin] has quit [Remote host closed the connection]
13:21 -!- ddustin [~ddustin@unaffiliated/ddustin] has joined #secp256k1
14:24 -!- Chris_Stewart_5 [~Chris_Ste@unaffiliated/chris-stewart-5/x-3612383] has quit [Ping timeout: 264 seconds]
16:59 -!- ddustin [~ddustin@unaffiliated/ddustin] has quit [Remote host closed the connection]
17:01 -!- ddustin [~ddustin@unaffiliated/ddustin] has joined #secp256k1
17:05 -!- ddustin [~ddustin@unaffiliated/ddustin] has quit [Ping timeout: 265 seconds]
17:11 -!- ddustin [~ddustin@unaffiliated/ddustin] has joined #secp256k1
18:26 -!- ddustin [~ddustin@unaffiliated/ddustin] has quit [Ping timeout: 260 seconds]
18:49 -!- ddustin [~ddustin@unaffiliated/ddustin] has joined #secp256k1
19:27 -!- belcher [~belcher@unaffiliated/belcher] has quit [Quit: Leaving]
23:00 -!- ddustin [~ddustin@unaffiliated/ddustin] has quit [Ping timeout: 246 seconds]
--- Log closed Fri Apr 10 00:00:48 2020