00:46:43justanotheruser:justanotheruser is now known as justanotherSJW
01:06:54justanotherSJW:justanotherSJW is now known as justanotheruser
08:05:17sinisalo.freenode.net:topic is: This channel is not about short-term Bitcoin development | http://bitcoin.ninja/ | This channel is logged. | For logs and more information, visit http://bitcoin.ninja
08:05:17sinisalo.freenode.net:Users on #bitcoin-wizards: andy-logbot AaronvanW _ingsoc mapppum oujh pen lclc tromp OX3_ TheSeven iddo altoz phrackage Dr-G2 koshii samson_ jchp atgreen justanotheruser grishnakh__ jaromil comboy wiretapped Ursium devrandom pi07r go1111111 Emcy Eliel Burrito tacotime grubles Sangheili fanquake melvster ryan-c grandmaster2 [Derek] Graet sipa mortale zenojis Adohgg mr_burdell copumpkin andytoshi nickler dgenr8 nsh Transisto HaltingState Graftec starsoccer Luke-Jr
08:05:17sinisalo.freenode.net:Users on #bitcoin-wizards: Krellan_ kanzure spinza mikalv EasyAt BigBitz Starduster phantomcircuit gwillen mappum nuke1989 BrainOverfl0w Dyaheon SDCDev HM_ otoburb realzies Guest95624 postpre nsh- Alanius mkarrer_ CryptOprah_ DoctorBTC btc jgarzik Keefe waxwing smooth quackgyver michagogo warren throughnothing_ Muis artifexd Fistful_of_coins azariah4 Hunger- zibbo tromp_ fierbuq forrestv OneFixt harrow K1773R pigeons cfields [\\\] bobke drawingthesun midnightmagic
08:05:17sinisalo.freenode.net:Users on #bitcoin-wizards: CodeShark Logicwax maaku LarsLarsen1 Anduck zling_____ helo crescendo epscy mmozeiko Guest50253 asoltys berndj-blackout BlueMatt digitalmagus7 sl01 weex Iriez abc56889 espes__ lechuga_ SomeoneWeird bbrittain nanotube rs0 davidlatapie jbenet poggy_ TD-Linux gmaxwell a5m0 tjopper catcow amiller dansmith_btc danneu LaptopZZ_ burcin optimator_ jcorgan [d__d] petertodd UukGoblin wizkid057 kinlo so phedny gribble roasbeef nkuttler @ChanServ
08:05:17sinisalo.freenode.net:Users on #bitcoin-wizards: Apocalyptic lianj wumpus
09:02:12Dr-G2:Dr-G2 is now known as Dr-G
13:42:20wallet42:wallet42 is now known as Guest49541
13:42:21wallet421:wallet421 is now known as wallet42
18:11:12andytoshi:in the short signature scheme http://eprint.iacr.org/2009/028.pdf you have this nonce `s` per signature, which is not secret but must be unique (you just increment a counter) (actually the security proof assumes `s` grows polynomially in the # of sigs)
18:11:41andytoshi:i was able to show that if you reuse `s` even once, there is a linear algebra trick which lets an attacker forge arbitrary messages
18:12:16andytoshi:interestingly this does -not- reveal the secret key, just lets you forge messages with this specific tainted `s` value
18:13:09andytoshi:anyway brent (second author) asked me if i could come up with a tweak to the scheme where you could reuse `s` once, say. ....an interesting academic problem is to do the same for ECDSA. can you come up with a "tweaked ECDSA" where you can reuse k once?
18:16:00gmaxwell:andytoshi: in a bitcoin like system where you promised a pubkey could never be reused, could someone just set s equal to some function of their pubkey, and then you get a general short signature? (haven't looked at the paper yet)
18:17:07gmaxwell:How big are the signatures assuming you don't have to signal s?
18:17:09andytoshi:to make the security proof go through, you'd want it to be some poly-size function (say, first 10 bits of the pk)
18:17:59andytoshi:two curvepoints and a numeric nonce
18:18:18andytoshi:the nonce is an exponent, its size is 256bits or whatever
18:18:29gmaxwell:oh, ha. well thats not shorter than ECDSA, alas.
18:18:48andytoshi:verification involves two pairing ops, it's also much slower :)
18:19:07gmaxwell:oh it's pairing. okay, well there are pairing signature schemes with no nonce at all.
18:19:29andytoshi:this one is secure in the standard model, that's its claim to fame
18:19:42andytoshi:assuming only CDH (!!)
18:20:31andytoshi:efficiency-wise it's not so great, tho it's cool that it's reasonable
18:20:57gmaxwell:weird!... still, I think we should be slightly less confident that CDH holds in paring friendly groups. (simply because there are two paths to attack, e.g. you attack CDH in GT or in the EC group)
18:21:11andytoshi:yeah, that's my intuition too
18:22:04andytoshi:this "doesn't reveal the key" property is neat, it is possible we could also restrict s by other means
18:22:13andytoshi:to get "locally nonreusable sigs"
18:25:44andytoshi:i have put my reused-s attack at https://download.wpsoftware.net/bitcoin/wizardry/ss-standard-model.pdf nb it has not been reviewed at all
18:43:20bsm117532:FWIW that sound a bit like perfect forward secrecy, used in e.g. OTR.
18:45:18Quanttek_:Quanttek_ is now known as Quanttek
18:48:50andytoshi:almost ... like, you might sign your messages with a "session key" s which is just a session counter, then afterward reuse s to repudiate those sigs
18:49:10andytoshi:problem is you'd need a different s for every single message, and would have to repudiate them all :)
18:52:33bsm117532:I need to spend a few days smashing my face against ECDSA.
18:55:28andytoshi:secret key x, message m, per-message nonce k, the sig is (s, r) where s = k^{-1}(H(m) + rx) and r = X(kG)
18:56:10gmaxwell:andytoshi: would be a neat trick if some structure was such that using s+1 repudiated prior s.
18:56:23andytoshi:bsm117532: this use of X(.) literally "x-coord of the point" to jam a curvepoint into an exponent slot basically kills all analytic tools
18:56:53andytoshi:gmaxwell: oooh, i'll think about it
18:57:45bsm117532:I feel like some of the things I want to do, I might be able to think of a way to do on elliptic curves. But need to smash face some more.
18:57:58bsm117532:(e.g. I'm thinking about Fair Exchange an awful lot)
18:58:47andytoshi:bsm117532: it seems to me that most of the cool stuff is group-agnostic, only ECDSA uses any properties of the group element representation that i know of
18:59:15andytoshi:you just assume that certain problem(s) (CDH, DDH, BDH, etc) are hard for your group and work from that
18:59:55andytoshi:but yes, facesmashing is necessary in any case :) good lock
19:00:57bsm117532:I'm amused you posted something about the Standard Model. I've spent my career studying that *other* Standard Model (of particle physics).
19:01:37andytoshi::P i forgot about that one. funny, when i started my math degree i wanted to be a physicist
19:02:01andytoshi:(but only because my school at the time had no crypto program)
19:02:08bsm117532:It's a bit odd to transition to discrete math after a lifetime of complex analysis.
19:02:53bsm117532:But you need any contour integrals, resummation, or infinite series'....I've got you covered. :-P
19:03:20nsh:* nsh smiles
19:03:34andytoshi::P will keep it in mind
19:07:10zooko`:zooko` is now known as zooko
19:11:37bsm117532:Hey speaking of which, can anyone recommend some good textbook exercises in elliptic curves? (Or a good textbook, for that matter...Applied Cryptography is 20 years old at this point)
19:13:13tromp_:there's the more recent Practical Cryptography, but I don't know how well it does on exercises
19:15:37bsm117532:* bsm117532 stomps over to ##crypto
20:10:27melvster:melvster is now known as klaranet
20:38:38fanquake_:fanquake_ is now known as fanquake
21:08:31andytoshi:gmaxwell: there is an obvious(ly inefficient) way to do what you want for an OTR-like scheme --- require each message be signed with both `s` and `s + 1`!
21:11:04andytoshi:you can save at least one pairing op (vs the naive 2 for verifying two sigs) by doing that
21:12:19andytoshi:(and ofc i would want a security proof for this mode of operation before actually suggesting it)
21:19:23gmaxwell:fwiw, if one of the arguments to the pairing is fixed you can save more computation.
21:23:54andytoshi:nope, one of them is totally identical (except the left argument is multiplied by a known point determined by the sigs -- so you can just check the multiplication and not bother with the pairing)
21:24:03andytoshi:and the other pairing has totally different arguments
21:25:29andytoshi:oh, wait, you might not be able to skip that .. i misread the verification eqn
21:26:44andytoshi:shit, there are 3 pairing ops :) but you can indeed skip one
21:28:59andytoshi:hmm, with some precomputation (which has to be done with each public key) i think you can skip it on every sig actually..
21:30:27andytoshi:`u`, `v`, `d`, `g^a` are all part of the public key (`a` is the secret key) ... you compute e(u^M v^r d, g^a) as part of the verification. you precompute U = e(u, g^a), V = e(v, g^a), D = e(d, g^a) then e(u^M v^r d, g^a) is just U^M V^R D
21:31:10andytoshi:i mean, U^M V^r D
21:35:25andytoshi:with regular OTR you reveal the auth key at the end of the session correct? so if you disconnect early can you entrap people by not giving them chance to reveal it?
21:36:50gmaxwell:andytoshi: actually you constantly reveal keys, basically you have a rolling window, and when the far end has acknoweldged you publish the prior auth key in the clear.
21:38:19andytoshi:so on a high level this "reusing s" scheme is simpler (only one auth key) though in practice it'd be way more expensive due to all the pairing ... but same security properties i think?
21:38:29gmaxwell:there is a neat cryptosystem someplace which has the property that given the trapdoor secret there is a efficiently computable private input that makes any ciphertext produce any plaintext. sadly the overhead is huge... but thats really what you want for otr.
21:38:50andytoshi:"deniable encryption"?
21:39:07andytoshi:iirc that was open until program obfuscation ... so still open for those of us with physical machines ;)
21:49:09gmaxwell:hm. Pretty sure someone has a reasonable cryptosystem for that now.
21:51:10andytoshi:http://eprint.iacr.org/2013/684 maybe ... that's the only more recent hit for 'deniable encryption' on iacr
21:51:21andytoshi:from the abstract, looks like it uses a funny hardness assumption but not obfuscation
21:51:33andytoshi:anyway i gotta run, have vector calc to tecah :)
23:17:15gmaxwell:Heads up, the old gmx satoshi account looks like it expired and was handed to some idiot. Said idiot used it to take over the old bitcoin sourceforge. Nothing too important there, but there are a bunch of old download links to it, so some people still use it. Also some mailing lists.
23:18:35gmaxwell:Including the Bitcoin-security lists, ... fortunately valiting the decision to keep most really critical things off that list. In any case, we're trying to get ahold of sourceforge to fix it.
23:22:08Luke-Jr:gmaxwell: can't Gavin just remove Satoshi from the project?
23:22:37gmaxwell:no, 'satoshi' removed everyone else.
23:22:46gmaxwell:Otherwise it would already be fixed.
23:23:03tacotime:yeah; https://bitcointalk.org/index.php?topic=775174.0
23:23:20gmaxwell:(satoshi created the project, I don't think we were able prevent it from recovering it)