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.
Starduster_ has quit
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.
rusty
gmaxwell: isn't that almost an inevitable consquence of any authenticated email scheme though?
BlueMatt
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
gmaxwell
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.
Guest73382 has quit
BlueMatt
and allow an intermediary server to modify it
gmaxwell
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.
askmike joined the channel
BlueMatt
to be fair, in court, "look, heres a screenshot of gmail!" is pretty much as good as dkim
lechuga_
lol
gmaxwell
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.
BlueMatt
yea, was just gonna say that
gmaxwell
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.
BlueMatt
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")
gmaxwell
in any case, "in before some POS system starts using gmail as a timestamper to prevent nothing at stake". :P
BlueMatt
naa, just use gmail dkim signatures/proof of number of gmail accounts as a measure for stake :)
gmaxwell
yea, you could do that too.
BlueMatt
to be fair, it would actually work pretty well until google decided to walk all over it
gmaxwell
Also, proof of spam. E.g. send a letter to president@whitehouse.gov that includes at least 5 offensive words to get your payment.
BlueMatt
security of google/of mass-gmail-registration is generally pretty good
heh
gmaxwell
Actually, given strong enough script we can create trutless (well cept for google) contract to nag congress people with form letters.
BlueMatt
heh
gmaxwell
probably all kinds of crazy vote buying and other fun things we can do.
BlueMatt
proof of offer to bribe?
fanquake_ joined the channel
gmaxwell
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.
BlueMatt
heh, indeed
gmaxwell
BlueMatt: well lots of systems send side effects in email, ... invoices, thanks for participating in our survey.
BlueMatt
yea, absolutely
Starduster joined the channel
gmaxwell
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)
BlueMatt
yupyup
nsh
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]
SubCreative joined the channel
fanquake has quit
fanquake_ is now known as fanquake
NewLiberty_ joined the channel
Sub|afk has quit
gmaxwell
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.
NewLiberty has quit
fanquake has quit
arowser1 joined the channel
arowser has quit
Dr-G2 has quit
sl01
gmaxwell: how much actual work would it take to create a document hash collision w sha256 ?
2**128 ?
NewLiberty_ has quit
Transisto joined the channel
askmike has quit
Transisto has quit
rusty
gmaxwell: seems a little paranoid, but OK, you're suggesting you commit the document, then blockhash-where-document-committed || document in some later block?
adam3us joined the channel
atgreen joined the channel
belcher has quit
webdeli_ has quit
atgreen has quit
nsh
gmaxwell, neat
Transisto joined the channel
samson_ has quit
samson_ joined the channel
webdeli joined the channel
NewLiberty joined the channel
gmaxwell
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.
phantomcircuit
and likely wouldn't be an issue in bitcoin anyways
gmaxwell
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.
webdeli_ joined the channel
phantomcircuit
gmaxwell, how would you use collisions for dos?
webdeli has quit
gmaxwell
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.
phantomcircuit
ah right
askmike joined the channel
gmaxwell
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.
rusty
gmaxwell: s/identify blocks/identify txs/?
askmike has quit
go1111111 has quit
gmaxwell
rusty: for the attacks I'm describing above its sufficient to solve it at a block level. (since a block includes the transactions)
midnightmagic
how would one determine if a p2sh was duplicated until an actual spend happens
gmaxwell
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.
op_null joined the channel
go1111111 joined the channel
go1111111 has quit
freewil joined the channel
Burrito has quit
rusty
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.