--- Day changed Fri Aug 24 2018
02:49 -!- newtmewt [~newtmewt@190-199-199-26.dyn.dsl.cantv.net] has joined #secp256k1     
02:52 -!- newtmewt [~newtmewt@190-199-199-26.dyn.dsl.cantv.net] has quit [Remote host closed the connection]     
05:24 -!- ken2812221 [~ken281222@110.50.144.85] has joined #secp256k1     
08:49 -!- sipa [~pw@gateway/tor-sasl/sipa1024] has joined #secp256k1     
10:15 <@gmaxwell> sipa: so it bothers me a little bit that the key derrivation for BIP151 is non-contributory, but I can't find any way to exploit it for secp256k1, though it would be exploitable for other curves.
10:16 < sipa> non-contributory?
10:16 <@gmaxwell> By non-contributory, I mean that in theory one party could cancel out the other parties choice of keys. If points of low order existed, for example, you connect to me but pick as your ephemeral key a point of low order... Then our session key is one of just a couple values (the low order).
10:16 <@gmaxwell> That then gets turned into an attack when some later protocol component (e.g. auth) signs the session id.
10:17 < sipa> points of low order? points not on the curve?
10:17 <@gmaxwell> Contributory would be something like. H(seckey_a*G || seckey_b*G || seckey_a*seckey_b*G).
10:18 <@gmaxwell> sipa: e.g. curve25519 has point of low order that satisify the curve equation, due to the cofactor.
10:18 < sipa> sure; but we have a prime ordered group, so all points have the same order?
10:19 < sipa> apart from infinity
10:19 <@gmaxwell> Right.
10:20 <@gmaxwell> But is there any other way that after seeing your P I can pick a secret key to get the shared secret to be a few values?
10:22 < sipa> so assume that instead of a few values, it was one value
10:23 < sipa> and a function f exists, where f(P) for point P with unknown DL, results a value such that f(P)*P = C, where C is a constant but still with unknown DL?
10:24 <@gmaxwell> Yes.
10:24 < sipa> in that case f(G)/f(P) is the DL of P.
10:24 <@gmaxwell> Great. OKAY. I feel better now.
10:27 < sipa> :)     
10:27 < andytoshi> crucially, we are using the fact that all multiplications are automorphisms when we jump from "f(G)*G = f(P)*P" to "f(G)/f(P)*G = P"
10:28 < andytoshi> to be clear
10:28 < andytoshi> i really like this arcgument
10:30 < sipa> so weakened i think you can state "if an algorithm f exists that finds multipliers for group elements that maps them in a small set, then f(G)/f(P) has a nonnegligable chance of being the DL of P"
10:31 < andytoshi> no, in the non-prime-group setting you can't really say anything at all. you certainly can't extract discrete logs with this sort of attack
10:31 < sipa> oh, i was assuming a prime group to be clear
10:31 <@gmaxwell> Unrelated, I'm concerned that the use of the "message sequence number" as nonce in BIP151 will make AVX ineffective. The current protocol spec requires each side keep a counter of protocol messages sent, and chacha20 runs with that counter as the nonce.  IIRC AVX chacha works by running 8 copies of chacha in parallel, so it'll generate 512 bytes of stream at once.  mean( (msg_size%512)/msg_size ) is no
10:31 <@gmaxwell> t small for our protocol.
10:32 < sipa> well if you need less than 512 bytes, don't use the AVX version?
10:33 < sipa> or rather, if you need less than 256 bytes, use SSE instead
10:34 < sipa> andytoshi: ah yes, i was assuming that the set of discrete logs form a field
10:35 < sipa> which is only true when they're prime sized
10:37 <@gmaxwell> sipa: yes, but why is the protocol restarting chacha20 at all, the whole advantage of a stream cipher is that you can compute it independantly of your data.
10:37 < sipa> gmaxwell: chacha20 at its core is a function that maps 256 bits to 512 bits
10:37 < sipa> there is basically nothing shared across multiple runs
10:38 < sipa> sorry, 512 bits to 512 bits
10:38 < sipa> the input 512 bits consist of the private key, the iv, the counter, and some static values
10:38 <@gmaxwell> I know how it works. :)
10:38 < sipa> i don't understand your concern then
10:39 <@gmaxwell> My concern is that the our design is unusual use of a stream cipher, that restarts the stream for each message. ... which would be fine, except it will hurt the performance.
10:40 < sipa> what do you mean by 'restart' ?
10:40 < sipa> chacha has no restarting, as it has no state
10:41 < sipa> you can see chacha as a 2-dimensional stream cipher i guess, and one dimension used as packet number and the other is the position within the packet
10:41 < sipa> but changing one isn't more efficient than changing the other
10:42 < sipa> oh!     
10:42 < sipa> i think i see what you mean
10:42 <@gmaxwell> To get maximum performance on a platform with 256bit SIMD you need to compute 8 chacha20s at a time. With ordinary stream cipher usage this is trivial. With "2-d stream cipher" you lose output.
10:42 < sipa> if it were 1-dimensional, you could precompute stuff for the next packet?
10:42 <@gmaxwell> yes.
10:42 < sipa> right
10:42 < sipa> that's interesting
10:43 <@gmaxwell> and almost all (by count, at least) of our packets are small.
10:43 < sipa> i wonder if it's worth changing the design for though... it's already so ridiculously cheap
10:44 <@gmaxwell> Well I assume that for many cheap messages the chacha20/poly1305 costs will be most of the processing time.
10:44 <@gmaxwell> its certantly not the limiting factor in performance for us right now, but we should fix that. :P
10:44 < sipa> i doubt that :)
10:44 < sipa> maybe ping.
10:45 <@gmaxwell> tx inv for an already has transaction is our most common p2p message.
10:45 < sipa> but iirc it's 3 cycles/byte or so with a naive implementation
10:45 <@gmaxwell> FWIW, https://eprint.iacr.org/2013/759.pdf
10:47 < sipa> it's only a 2x factor with avx2?
10:47 < sipa> :)     
10:47 <@gmaxwell> over SSE2
10:47 <@gmaxwell> they also show 5.59cycles/byte for 64 byte messages.
10:50 <@gmaxwell> I don't know if it matters, but the decision to foreclose the optimization should be a conscious one, rather than an accident.
10:53 <@gmaxwell> interesting, okay, so the 128-bit SIMD chacha still works on one chacha block at a time.
10:54 <@gmaxwell> so 256 does 2 of them.
10:55 < sipa> and avx512 does 4 simultaneously
10:55 < sipa> makes sense
10:57 <@gmaxwell> uhh... we use a seperate chacha20 run for lengths...
10:57 < sipa> those can be precomputed ahead, though
10:57 < sipa> no?     
11:05 <@gmaxwell> yes, but we only get 4 bytes of output from each chacha run.
11:05 <@gmaxwell> so the chacha for the lengths would have an effective speed of 89 cycles per byte.
12:08 -!- deusexbeer [~deusexbee@080-250-076-215-dynamic-pool-adsl.wbt.ru] has quit [Quit: Konversation terminated!]     
14:33 -!- andytoshi [~apoelstra@unaffiliated/andytoshi] has quit [Ping timeout: 272 seconds]     
15:19 -!- meshcollider_ [uid246294@gateway/web/irccloud.com/x-gydxecdiidffgcuo] has joined #secp256k1     
15:23 -!- andytoshi [~apoelstra@wpsoftware.net] has joined #secp256k1     
15:23 -!- andytoshi [~apoelstra@wpsoftware.net] has quit [Changing host]     
15:23 -!- andytoshi [~apoelstra@unaffiliated/andytoshi] has joined #secp256k1     
15:47 -!- deusexbeer [~deusexbee@080-250-076-215-dynamic-pool-adsl.wbt.ru] has joined #secp256k1     
15:58 -!- deusexbeer [~deusexbee@080-250-076-215-dynamic-pool-adsl.wbt.ru] has quit [Quit: Konversation terminated!]     
15:59 -!- deusexbeer [~deusexbee@080-250-076-215-dynamic-pool-adsl.wbt.ru] has joined #secp256k1     
16:38 -!- moved [~moved@71-14-128-159.dhcp.ftwo.tx.charter.com] has joined #secp256k1     
16:42 -!- moved [~moved@71-14-128-159.dhcp.ftwo.tx.charter.com] has quit [K-Lined]     
17:33 -!- savoir-faire7 [~savoir-fa@93-173-65-10.bb.netvision.net.il] has joined #secp256k1     
17:37 -!- savoir-faire7 [~savoir-fa@93-173-65-10.bb.netvision.net.il] has quit [Remote host closed the connection]     
17:41 -!- kg12 [~kg@p2697084-ipngn22301marunouchi.tokyo.ocn.ne.jp] has joined #secp256k1     
17:42 -!- kg12 [~kg@p2697084-ipngn22301marunouchi.tokyo.ocn.ne.jp] has quit [Remote host closed the connection]     
17:59 -!- meshcollider_ [uid246294@gateway/web/irccloud.com/x-gydxecdiidffgcuo] has quit [Quit: Connection closed for inactivity]     
22:01 <@gmaxwell> sipa: esp after reading this, https://blog.cr.yp.to/20170723-random.html    I wish there was a chacha20/poly1305 mode that used this approch, then we wouldn't need key rotation at all.
22:53 -!- maaku [~maaku@173.234.25.100] has quit [Quit: ZNC - https://znc.in]     
22:54 -!- maaku [~maaku@173.234.25.100] has joined #secp256k1