#bitcoin-wizards

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.

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.

This means that if you send email using DKIM you're making your message cryptographically non-reputable.

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.

gmaxwell: isn't that almost an inevitable consquence of any authenticated email scheme though?

depends on what your goals are

you might just sign from/to/date, that way you can only prove an email was sent, not its contents

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.

and allow an intermediary server to modify it

E.g. you say ig are good for 3 days, you remember the nonces, you don't allow nonce replay for three days.. etc.

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.

to be fair, in court, "look, heres a screenshot of gmail!" is pretty much as good as dkim

lol

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.

BlueMatt: yes ^ exactly.

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.

yea, was just gonna say that

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.

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

(or the court just says "nope, sorry, you cant get a free pass like that")

in any case, "in before some POS system starts using gmail as a timestamper to prevent nothing at stake". :P

naa, just use gmail dkim signatures/proof of number of gmail accounts as a measure for stake :)

yea, you could do that too.

to be fair, it would actually work pretty well until google decided to walk all over it

Also, proof of spam. E.g. send a letter to president@whitehouse.gov that includes at least 5 offensive words to get your payment.

security of google/of mass-gmail-registration is generally pretty good

heh

Actually, given strong enough script we can create trutless (well cept for google) contract to nag congress people with form letters.

heh

probably all kinds of crazy vote buying and other fun things we can do.

proof of offer to bribe?

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.

heh, indeed

BlueMatt: well lots of systems send side effects in email, ... invoices, thanks for participating in our survey.

yea, absolutely

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)

yupyup

apropos:

--

<TheCthulhu> 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

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

<pfm> seems like more technical experts are desperately needed in the legal system

-- OFTC#nottor [edited for vertical brevity]

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 ...

... must pass, removes that attack (I think!) and (if so), we can make that non-interactive by using the blockchain to provide the challenge.

gmaxwell: how much actual work would it take to create a document hash collision w sha256 ?

2**128 ?

gmaxwell: seems a little paranoid, but OK, you're suggesting you commit the document, then blockhash-where-document-committed || document in some later block?

gmaxwell, neat

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.

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.

and likely wouldn't be an issue in bitcoin anyways

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 ...

... free.

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.

gmaxwell, how would you use collisions for dos?

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.

ah right

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.

these things are fixable with pure p2p protcol changes, I think.

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.

gmaxwell: s/identify blocks/identify txs/?

rusty: for the attacks I'm describing above its sufficient to solve it at a block level. (since a block includes the transactions)

how would one determine if a p2sh was duplicated until an actual spend happens

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.

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 <what they told you> 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.

mostly I don't worry about 2^80 attacks, esp ones against interactive protocols.

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.