Monday, August 16

May you live in (cryptographically) interesting times

Eric Rescorla has a post on the consequences of rumored and actual breaks in commonly used cryptographic hash functions. Since this stuff is being reported as of August 16th, I guess it's what you call breaking news, yes?

Anyway, EKR's post says that since the breaks are in collision-resistance, rather than preimage-resistance, it doesn't have a major impact on security protocols. I don't think so.

Hash functions with weak collision-resistance would be a very bad thing for non-repudiation in signature applications.

This has been described before in motivating the so-called birthday attack* in digital signature applications. That is, you as the originator of a signed message could generate two messages: the first a commitment that you'd like the recipient to rely upon and the second that you'd later claim you'd actually said instead which commits to you to something less than the first.

The birthday attack assumes that collision are hard and that you need to pre-compute a large collection of, for instance, good/bad contract pairs. If collisions are easy, you have a more realistic prospect of coming-up with a plausible pair of good/evil offers.


[*] The commonly-cited countermeasure for the birthday attack is for the counter-party to non-materially modify the offered message before signing. This ignores the fact that there are applications requiring non-repudiation that aren't two-party contracts.

10 comments:

Anonymous said...

It's actually more complicated than that. Consider the following case: the attacker (the attesting party) generates two messages X and X'. He signs X and sends it to the victim (the relying party). When the victim then tries to hold the X, the attacker says "Hah! I really committed to X'". But think about the social implications: as long as collisions are easy but preimages are hard, ONLY the attesting/signing party can generate collisions, so the very existence of a collision demonstrates that it's the attacker and not the relying party who is up to no good.

In order for this attack to work correctly, the attacker has to generate a good/evil pair that he gets the victim to sign, not the other way around. But it's easy for the victim to defeat this attack simply by adding very small amounts of unpredictability to the message before he signs it . There doesn't have to be much and it probably doesn't have to be very random--just enough to make it difficult to come up with a precomputed collision pair.

Not of course, that any of this is that important, because it's not how signatures are really used. Consider that people regard a faxed contract as binding, even though cut and paste attacks are easy. Indeed, often the contract is only signed on the last page and the other pages can be swapped at will.

Anonymous said...

Oh, yeah. The previous post was by me... Stinking Blogger....

-Ekr

AMS said...

"...so the very existence of a collision demonstrates that it's the attacker and not the relying party who is up to no good."
Absolutely true. Still, as a matter of what might work in court as a proof of non-repudiability, the production of a signed X' would conclusively demonstrate that the posession of a signed X didn't prove anything. So, if you want non-repudiation that is plausible in court, don't use hash functions that aren't collision-resistant.

By-the-by, I doubt the "the party who could have done it easier by N orders of magnitude is the one who done it" expert opinion, although utterly convincing to a computer scientist, would hold up well under cross.

Anonymous said...

Hmm...

"By-the-by, I doubt the "the party who could have done it easier by N orders of magnitude is the one who done it" expert opinion, although utterly convincing to a computer scientist, would hold up well under cross."

Doesn't this argument pretty much invalidate the whole basis of digital signatures, which, after all, are supported by the claim that it's vastly easier for the party with the private key to generate the signature than for someone who only has the public key?

-Ekr

AMS said...

Fair point, but I don't think the two arguments would sound equivalent. I don't think anybody would say "vastly easier" for generating signatures, they'd say "virtually impossible for anyone else".

In the hash case, the jury has been shown the pair X and X' by the defense. The plaintiff's expert has to claim that producing this pair is "virtually impossible for anyone but the defendent" -- hard to accept when the jury has seen the pair and it seems so obvious that they are similar texts and the algorithm has been animated for the jury, producing the same hash result.

Anonymous said...

Well, perhaps, but conveniently that's what Baudet is for. I would argue that the jury shouldn't even be allowed to hear the testimony you propose.

AMS said...

OK, I'll bite: What's "Baudet". Some precedent I've never heard of?

Anonymous said...

"Baudet"=my brain-dead spoonerism on Daubert v. Merrell Dow
See here

AMS said...

Oh. In that case, my read on Daubert is that such expert testimony ("the showing of signed X proves nothing given also a X' matching the hash") is clearly admissible on the grounds of scientific method.

Anonymous said...

Well, what you just said is interpretive, and basically false. I'm no lawyer but it's not admissible under my understanding of Daubert.

1. The relying party is in possession of the pair (X,Y) where sig(X) = Y.

2. The attesting party is in possession of the pair (X', Y) where sig(X').

3. Only the attesting party could have generated Y.

4. Given X' the relying party could not have generated X (assuming that finding 2nd preimages is still infeasible).

So, the attesting party must either claim that he signed document (X') given him by the relying party or it must be the case that the attesting party provided the relying party with (X,Y).


In any case, as I said before, all of this is pretty much irrelevant, because it's not how signatures are used in the real world.