| 00:46:43 | justanotheruser: | justanotheruser is now known as justanotherSJW |
| 01:06:54 | justanotherSJW: | justanotherSJW is now known as justanotheruser |
| 08:05:17 | sinisalo.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:17 | sinisalo.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:17 | sinisalo.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:17 | sinisalo.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:17 | sinisalo.freenode.net: | Users on #bitcoin-wizards: Apocalyptic lianj wumpus |
| 09:02:12 | Dr-G2: | Dr-G2 is now known as Dr-G |
| 13:42:20 | wallet42: | wallet42 is now known as Guest49541 |
| 13:42:21 | wallet421: | wallet421 is now known as wallet42 |
| 18:11:12 | andytoshi: | 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:41 | andytoshi: | 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:16 | andytoshi: | interestingly this does -not- reveal the secret key, just lets you forge messages with this specific tainted `s` value |
| 18:13:09 | andytoshi: | 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:00 | gmaxwell: | 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:16:47 | andytoshi: | yes. |
| 18:17:07 | gmaxwell: | How big are the signatures assuming you don't have to signal s? |
| 18:17:09 | andytoshi: | 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:59 | andytoshi: | two curvepoints and a numeric nonce |
| 18:18:18 | andytoshi: | the nonce is an exponent, its size is 256bits or whatever |
| 18:18:29 | gmaxwell: | oh, ha. well thats not shorter than ECDSA, alas. |
| 18:18:48 | andytoshi: | verification involves two pairing ops, it's also much slower :) |
| 18:19:07 | gmaxwell: | oh it's pairing. okay, well there are pairing signature schemes with no nonce at all. |
| 18:19:29 | andytoshi: | this one is secure in the standard model, that's its claim to fame |
| 18:19:42 | andytoshi: | assuming only CDH (!!) |
| 18:20:31 | andytoshi: | efficiency-wise it's not so great, tho it's cool that it's reasonable |
| 18:20:57 | gmaxwell: | 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:11 | andytoshi: | yeah, that's my intuition too |
| 18:22:04 | andytoshi: | this "doesn't reveal the key" property is neat, it is possible we could also restrict s by other means |
| 18:22:13 | andytoshi: | to get "locally nonreusable sigs" |
| 18:25:44 | andytoshi: | 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:20 | bsm117532: | FWIW that sound a bit like perfect forward secrecy, used in e.g. OTR. |
| 18:45:18 | Quanttek_: | Quanttek_ is now known as Quanttek |
| 18:48:50 | andytoshi: | 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:10 | andytoshi: | problem is you'd need a different s for every single message, and would have to repudiate them all :) |
| 18:52:33 | bsm117532: | I need to spend a few days smashing my face against ECDSA. |
| 18:55:28 | andytoshi: | 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:10 | gmaxwell: | andytoshi: would be a neat trick if some structure was such that using s+1 repudiated prior s. |
| 18:56:23 | andytoshi: | 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:53 | andytoshi: | gmaxwell: oooh, i'll think about it |
| 18:57:45 | bsm117532: | 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:58 | bsm117532: | (e.g. I'm thinking about Fair Exchange an awful lot) |
| 18:58:47 | andytoshi: | 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:15 | andytoshi: | you just assume that certain problem(s) (CDH, DDH, BDH, etc) are hard for your group and work from that |
| 18:59:55 | andytoshi: | but yes, facesmashing is necessary in any case :) good lock |
| 19:00:57 | bsm117532: | 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:37 | andytoshi: | :P i forgot about that one. funny, when i started my math degree i wanted to be a physicist |
| 19:02:01 | andytoshi: | (but only because my school at the time had no crypto program) |
| 19:02:08 | bsm117532: | It's a bit odd to transition to discrete math after a lifetime of complex analysis. |
| 19:02:53 | bsm117532: | But you need any contour integrals, resummation, or infinite series'....I've got you covered. :-P |
| 19:03:20 | nsh: | * nsh smiles |
| 19:03:34 | andytoshi: | :P will keep it in mind |
| 19:07:10 | zooko`: | zooko` is now known as zooko |
| 19:11:37 | bsm117532: | 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:13 | tromp_: | there's the more recent Practical Cryptography, but I don't know how well it does on exercises |
| 19:15:37 | bsm117532: | * bsm117532 stomps over to ##crypto |
| 20:10:27 | melvster: | melvster is now known as klaranet |
| 20:38:38 | fanquake_: | fanquake_ is now known as fanquake |
| 21:08:31 | andytoshi: | 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:04 | andytoshi: | you can save at least one pairing op (vs the naive 2 for verifying two sigs) by doing that |
| 21:11:13 | andytoshi: | s/2/4/ |
| 21:12:19 | andytoshi: | (and ofc i would want a security proof for this mode of operation before actually suggesting it) |
| 21:19:23 | gmaxwell: | fwiw, if one of the arguments to the pairing is fixed you can save more computation. |
| 21:23:54 | andytoshi: | 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:03 | andytoshi: | and the other pairing has totally different arguments |
| 21:25:29 | andytoshi: | oh, wait, you might not be able to skip that .. i misread the verification eqn |
| 21:26:44 | andytoshi: | shit, there are 3 pairing ops :) but you can indeed skip one |
| 21:28:59 | andytoshi: | 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:27 | andytoshi: | `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:10 | andytoshi: | i mean, U^M V^r D |
| 21:35:25 | andytoshi: | 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:50 | gmaxwell: | 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:37:32 | andytoshi: | gotcha |
| 21:38:19 | andytoshi: | 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:29 | gmaxwell: | 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:50 | andytoshi: | "deniable encryption"? |
| 21:39:07 | andytoshi: | iirc that was open until program obfuscation ... so still open for those of us with physical machines ;) |
| 21:39:41 | andytoshi: | http://eprint.iacr.org/2013/454 |
| 21:49:09 | gmaxwell: | hm. Pretty sure someone has a reasonable cryptosystem for that now. |
| 21:51:10 | andytoshi: | http://eprint.iacr.org/2013/684 maybe ... that's the only more recent hit for 'deniable encryption' on iacr |
| 21:51:21 | andytoshi: | from the abstract, looks like it uses a funny hardness assumption but not obfuscation |
| 21:51:33 | andytoshi: | anyway i gotta run, have vector calc to tecah :) |
| 23:17:15 | gmaxwell: | 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:35 | gmaxwell: | 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:08 | Luke-Jr: | gmaxwell: can't Gavin just remove Satoshi from the project? |
| 23:22:37 | gmaxwell: | no, 'satoshi' removed everyone else. |
| 23:22:46 | gmaxwell: | Otherwise it would already be fixed. |
| 23:23:01 | Luke-Jr: | ugh |
| 23:23:03 | tacotime: | yeah; https://bitcointalk.org/index.php?topic=775174.0 |
| 23:23:20 | gmaxwell: | (satoshi created the project, I don't think we were able prevent it from recovering it) |