01:15:35gmaxwell:So. Uh. Heres a bit of fodder for things with potentially unexpected consequences. Following a comment in private conversation with op_null about unrelated stuff; I thought I should go look to see what DKIM puts under signature. DKIM is DomainKeys Identified Mail an IETF standard for email that authenticates a messages origin (e.g. from address) to prevent spam.
01:16:47gmaxwell:So i turns out that many of the message headers (from/to/id/etc.) are almost always under the signature. The sender also has a timestamp under the signature. And the hash of some portion of the body; the usage I'm looking at puts the whole body under the signature.
01:17:28gmaxwell:This means that if you send email using DKIM you're making your message cryptographically non-reputable.
01:18:10gmaxwell:Because DKIM just uses keys in DNS there isn't a strong PKI to verify the keys; so there are limits on how strong the evidence is.
01:18:51rusty:gmaxwell: isn't that almost an inevitable consquence of any authenticated email scheme though?
01:19:12BlueMatt:depends on what your goals are
01:19:43BlueMatt:you might just sign from/to/date, that way you can only prove an email was sent, not its contents
01:19:48gmaxwell:rusty: It's not.. I mean if your goal is just antispam, having a nonce, timestamp, and from domain under the signature is adequate. Which is what I'd stupidly asumed DKIM did.
01:19:54BlueMatt:and allow an intermediary server to modify it
01:20:17gmaxwell:E.g. you say ig are good for 3 days, you remember the nonces, you don't allow nonce replay for three days.. etc.
01:21:50gmaxwell:It's been much to our (-wizard-ish folks) annoyance that with SSL there is actually no way to get the server to sign data. So I don't mean to say that it's entirely a bad thing DKIM works this way; but it means that sending emails might have somewhat more consequences than people assume.
01:22:31BlueMatt:to be fair, in court, "look, heres a screenshot of gmail!" is pretty much as good as dkim
01:22:46gmaxwell:Though only somewhat; because we take trivially forged documents as strong evidence way to easily... so the addition of a signature that actually makes it into strong evidence is unlikely to caue harm; even if it came as a shock.
01:22:54gmaxwell:BlueMatt: yes ^ exactly.
01:24:30gmaxwell:Not just in court, but also in public opinion. Though this may change over time; most legal scholars I've talked to agree that our standards for evidence are insane... but we have them because historically better evidence was impossible; and a court that has to constantly go "sorry, can't decide" is not socially useful.
01:24:50BlueMatt:yea, was just gonna say that
01:25:13gmaxwell:So the existance of the possiblity of stronger evidence will change the standards, given enough time... and then creating stronger evidence than we expected could be harmful to people.
01:25:54BlueMatt:well, ultimately it will create the same level of evidence people consider unsigned email to be today...the only difference will be that people who run their own mailservers and fix this bug now get a free pass
01:26:09BlueMatt:(or the court just says "nope, sorry, you cant get a free pass like that")
01:26:22gmaxwell:in any case, "in before some POS system starts using gmail as a timestamper to prevent nothing at stake". :P
01:27:03BlueMatt:naa, just use gmail dkim signatures/proof of number of gmail accounts as a measure for stake :)
01:27:17gmaxwell:yea, you could do that too.
01:27:37BlueMatt:to be fair, it would actually work pretty well until google decided to walk all over it
01:27:48gmaxwell:Also, proof of spam. E.g. send a letter to president@whitehouse.gov that includes at least 5 offensive words to get your payment.
01:27:52BlueMatt:security of google/of mass-gmail-registration is generally pretty good
01:28:15gmaxwell:Actually, given strong enough script we can create trutless (well cept for google) contract to nag congress people with form letters.
01:28:59gmaxwell:probably all kinds of crazy vote buying and other fun things we can do.
01:29:15BlueMatt:proof of offer to bribe?
01:29:30gmaxwell:Oh, trustless escrows. E.g. you pay me bitcoin conditional on me presenting an amazon.com dkim email invoice that has your address in the shipto.
01:29:46BlueMatt:heh, indeed
01:29:54gmaxwell:BlueMatt: well lots of systems send side effects in email, ... invoices, thanks for participating in our survey.
01:30:06BlueMatt:yea, absolutely
01:30:22gmaxwell:the pki part isn't a problem if you can just specify the key in advance in the contract (as I did in these examples)
01:31:09nsh: pfm: Perhaps the most worrying thing I've seen this week is the standard of data/evidence integrity that is used across the EU. In nearly every EU country when a forensics specialist presents evidence to the court, he or she must show proof that the evidence has not been tampered with in the form of some type of checksum. So that checksum must match when the device was seized to that which is presented to the court. The generally accepted st
01:31:10nsh:andard is CRC. Given you can get a CRC collision in less than 5 minutes, you can already see some arising problems and I am amazed it has never been challenged
01:31:11nsh: seems like more technical experts are desperately needed in the legal system
01:31:13nsh:-- OFTC#nottor [edited for vertical brevity]
01:32:18fanquake_:fanquake_ is now known as fanquake
01:36:26gmaxwell:oh seperately. I think I have a scheme for blockchain document timestamping that removes collision attacks, if anyone cares. E.g. you could do sqrt(|H()|) work and grind out two documents with the same hash, then commit the value, and then later pick which one(s) you reveal. An interactive protocol where you commit to the document, then the verifier gives you a challenge and you commit to challenge||document and both commitments ...
01:36:32gmaxwell:... must pass, removes that attack (I think!) and (if so), we can make that non-interactive by using the blockchain to provide the challenge.
01:47:52sl01:gmaxwell: how much actual work would it take to create a document hash collision w sha256 ?
01:48:40sl01:2**128 ?
02:11:21rusty:gmaxwell: seems a little paranoid, but OK, you're suggesting you commit the document, then blockhash-where-document-committed || document in some later block?
02:28:33nsh:gmaxwell, neat
02:54:55gmaxwell:sl01: 2^128 assuming the function was perfect. But, for example: it's trivial to compute chosen prefix collisions for MD5, and yet producing a second preimage is infeasable; due to cryptographic weakneses.
02:55:34gmaxwell:The MD structure used by sha256 is inherently weak against some attacks to produce collisions, though in the case of sha256 it appears to not (currently) be exploitable.
02:57:03phantomcircuit:and likely wouldn't be an issue in bitcoin anyways
02:57:28gmaxwell:so given that it already happened with MD5 and to a lesser extent for sha1 (no one has demonstrated it against sha1, but it should only have complexity ~2^62 or so) ... It's quite plausable that sha256 could someday be found to be pratically collision weak while still being second preimage strong. If it's worth fixing that, I dunno. For schnorr signatures an analogus protection can be done for basically free. In this case it's not ...
02:57:34gmaxwell:... free.
02:58:13gmaxwell:phantomcircuit: yea, bitcoin under normal use mostly doesn't care about collisions (or rather, they result in DOS attacks, but generally not worse). But a timestamping scheme might be made very vulnerable by them.
02:59:51phantomcircuit:gmaxwell, how would you use collisions for dos?
03:04:03gmaxwell:phantomcircuit: e.g. make two txn with the same hash. one valid, one invalid. get the valid one mined, relay to people copies of the block with the invalid one. Oops they're all now rejecting that block.
03:04:46phantomcircuit:ah right
03:05:11gmaxwell:or worse, make two valid transactions but with different scriptpubkeys in the txouts. Get one mined, relay variations of the block to random nodes. Later spend one and the network forks.
03:05:29gmaxwell:these things are fixable with pure p2p protcol changes, I think.
03:06:09gmaxwell:E.g. you identify blocks with an alternative second hash... and so you'd learn both of them. And you have some rule that the lower second hash value is the block you use when there are two valid blocks with the same id.
03:07:01rusty:gmaxwell: s/identify blocks/identify txs/?
03:13:13gmaxwell:rusty: for the attacks I'm describing above its sufficient to solve it at a block level. (since a block includes the transactions)
03:13:15midnightmagic:how would one determine if a p2sh was duplicated until an actual spend happens
03:14:38gmaxwell:midnightmagic: you can't. Though I believe you can use the same protocol I described to harden p2sh against 2^80 collisions... most of the time you don't care what someone elses scriptPubKey is, .... but for protocols where you do (e.g. "I'll pay to this because I trust I am a signer) you have at best 2^80 security today.
03:16:20gmaxwell:To harden you could have someone commit the script they're going to use, exactly. Then you give them a nonce, and the script they really use is NONCE OP_DROP and then there is no 2^80 attack. (or even without the overhead, e.g. if you're providing one of the pubkeys, you provide it in that order.
03:16:46gmaxwell:mostly I don't worry about 2^80 attacks, esp ones against interactive protocols.
03:41:00rusty:gmaxwell: ok, so I've hacked up a simulator for a fountain server, using an exponential series of blocks to xor. Seems promising; want to make sure results are real though.
04:02:34freewil:freewil has left #bitcoin-wizards
06:53:35lclc_bnc:lclc_bnc is now known as lclc
08:54:34lclc:lclc is now known as lclc_bnc
09:00:50lclc_bnc:lclc_bnc is now known as lclc
09:05:14sinisalo.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
09:05:14sinisalo.freenode.net:Users on #bitcoin-wizards: andy-logbot nuke1989 soundx cbeams go1111111 askmike Flyer33 Luke-Jr d4de Baz___ freewil RoboTeddy gues bosma TheSeven atgreen coiner adlai devrandom NewLiberty samson_ Transisto adam3us arowser1 SubCreative Starduster spinza Anduck Shiftos PRab prodatalab warptangent bitbumper nubbins` roconnor tacotime c0rw|away maaku_ hashtagg_ rfreeman_w null_radix grandmaster Meeh waxwing Nightwolf jgarzik mortale koshii hollandais berndj epscy dgenr8
09:05:14sinisalo.freenode.net:Users on #bitcoin-wizards: zibbo tromp Emcy mkarrer jaekwon_ Graftec fenn postpre ryanxcharles iddo Hunger- HaltingState luny SDCDev Pan0ram1x jaekwon lclc K1773R s1w Eliel_ kanzure bobke LaptopZZ isis btcdrak sneak harrigan michagogo hguux_ gavinandresen JonTitor ebfull phantomcircuit sl01 Cory Grishnakh sipa DoctorBTC Alanius jbenet HM dansmith_btc artifexd btc__ kumavis mappum Muis azariah4 nanotube orw MRL-Relay fluffypony PaulCapestany BlueMatt a5m0 kgk LarsLarsen
09:05:14sinisalo.freenode.net:Users on #bitcoin-wizards: gazab AdrianG yoleaux gwillen livegnik BananaLotus Myagui @ChanServ burcin coutts wizkid057 Dyaheon bbrittain NikolaiToryzin forrestv nickler mr_burdell Logicwax tromp_ Krellan poggy pi07r_ comboy mmozeiko lnovy Taek optimator_ [\\\] Apocalyptic throughnothing petertodd crescendo CryptOprah cfields-away Fistful_of_Coins gmaxwell kinlo ahmed_ so [d__d] espes BigBitz otoburb wumpus EasyAt starsoccer jaromil helo Keefe Iriez huseby phedny
09:05:14sinisalo.freenode.net:Users on #bitcoin-wizards: midnightmagic nsh coryfields andytoshi BrainOverfl0w warren lechuga_ harrow roasbeef ryan-c [Tristan] TD-Linux catcow danneu amiller smooth Graet gribble asoltys pigeons
10:17:53gmaxwell:andytoshi: Can I talk you into another crypto review? https://github.com/bitcoin/secp256k1/pull/123 the last commit there (the other is just the branch it's based on) is the code. A description of what we're doing is in the comments.
10:21:31gmaxwell:(anyone who is not andytoshi whom wants to review modular algebra is also free to review. :) )
10:25:33nsh:* nsh imagines self standing on diving board above a empty swimming pool peppered with sharp pointy number theory
11:09:35op_null:hello hearn.
12:35:29sipa:andytoshi: just added a small derivation about why the simplification is correct; may help reviewing
15:12:33lclc:lclc is now known as lclc_bnc
16:10:50Adlai`:Adlai` is now known as adlai
20:42:26c0rw|away:c0rw|away is now known as c0rw1n
21:21:28DougieBot5000_:DougieBot5000_ is now known as DougieBot5000
21:35:10NikolaiToryzin_:NikolaiToryzin_ is now known as NikolaiToryzin
22:38:48kanzure_:kanzure_ is now known as kanzure
22:51:09Dizzle__:Dizzle__ is now known as Dizzle
23:05:08therealnanotube:therealnanotube is now known as nanotube
23:37:06amiller:new snarks paper: https://eprint.iacr.org/2014/976.pdf
23:37:08amiller:Geppetto, the successor to pinocchio
23:57:36c0rw1n:c0rw1n is now known as c0rw|sleep