On signatures, enforcement and authentication

[Robert J. Hansen]

First: This is not legal advice.  I am not a lawyer.  Consult a lawyer
in your jurisdiction if you have specific questions.  This is the
rantings of a semi-informed layman.

One of the big elephants in the room when talking about digital
signatures is that we conflate several different things under the name
"digital signature."  The two major ones are *enforceable promises* and
*message authentication*.  These two things are quite distinct.

=====

A digital signature by itself means absolutely nothing.  What's
important is that as a society we have decided we will enforce the
solemnized promises made by our members: slightly less important, that
we have a legal framework to enforce these solemnized promises: and
utterly unimportant, the form in which these solemnized promises
manifest.  There have been successful lawsuits seeking to enforce
financial instruments that have been scrawled in Magic Marker on a
watermelon.  Whether the solemnization is a sworn oath before a notary
public, ink on a page, marker on a watermelon or bits on a hard drive is
really quite insignificant.

For a promise to be enforceable, it must be (a) made (b) unambiguously
(c) by parties able to make enforceable promises (d) and with mutual
benefit.  If I promise you that I'll give you a ride to the supermarket,
that's not an enforceable promise.  If I promise you that I'll give you
a ride to the supermarket and you promise to buy me a Diet Coke while
you're there, that's suddenly become an enforceable promise: we are both
mutually on the hook if we fail to live up to our obligations.

We have social mechanisms in place to support these four requirements.
Yesterday I signed a contract involving a large sum of money, but the
other party refused to simply accept my signature.  I had to go to a
notary public and present two forms of identification before signing the
document in the presence of the notary.  The other party to the contract
required this so that if we went to court I would have a very hard time
saying, "Your Honor, I never signed that contract."

We have other social, cultural and legal things, too -- a detailed list
would go on for literally dozens, if not hundreds, of pages.  The
important thing is that there are *basically* four requirements for an
enforceable promise, and we have a large number of tools to support this.

So, what's the relevance of this to SHA-1 and MD5?

Let me present to you an enforceable MD5 signature.  You and I agree to
a sale of stock.  We want to do it completely electronically without any
paper records.  Neither of us trusts the other, and we're stuck using
PGP 2.6 with its whole slew of problems: MD5, V3 keys and more.

I send you a list of notary publics that I trust.  You choose your own
notary public from that list and visit the notary.  I've already sent a
copy of the document I wish for you to sign to that notary.  The notary
checks your ID, tells you to read the document, and if you wish to
assent to it to electronically sign the document in his presence.  You
do so.  The notary retains a copy of the contract, your digital
signature, a photocopy of your ID and so forth.  On my end, I do the
same thing with a notary chosen from a list of ones that *you* trust.

The notary I trust sends me your signed assent to the agreement, the
notary you trust sends you my signed assent to the agreement.  Now if
either of us wants to break that agreement, how do we do this?  The
notaries will confirm that we read the agreement in their presences and
signed the documents.  Maybe you'll be able to argue that it wasn't you
who signed, but an impostor armed with fake ID.  Maybe you'll be able to
claim the contract was ambiguously worded and should be interpreted in
your favor.  Maybe you can claim you were deranged and should not be
held responsible for your choices.  Maybe you can... etc.

But none of those methods of repudiation have anything to do with
cryptography or the weaknesses of MD5.  And none of those methods of
repudiation would be foreclosed or impossible if you were to use OpenPGP
with SHA256-based signatures.

=====

The preceding is, of course, completely irrelevant when you're trying to
verify the signature on a software package.  Here there's no desire to
enforce a promise.  All that you're trying to do is to ensure the
provenance of a message, and that's where things like MD5 and SHA-1
weaknesses become very, very troubling.  No argument there whatsoever.
In the preceding example, the digital signature is phenomenally robust
because there are trusted parties mediating the entire thing and human
judgment is exercised throughout the process.  In a
verify-the-provenance situation, though, usually it's a completely
automated process without either trusted mediators or human judgment.

The important takeaway is this --

"Digital signature" is a phrase that covers an awful lot of ground.  In
some contexts digital signatures don't need any kind of collision
resistance: just typing in "I agree to the terms of the above" would
both be sufficient and enforceable.  In other contexts you need as much
collision resistance as possible.

Ray Lee once said, "Every truth has a context."  I'm not sure *every*
truth has a context, but declaring certain hash functions as insecure
for use in digital signatures is definitely context-sensitive.  I think
it would be good if we were to keep that in mind when talking about
digital signatures -- it's possible for two people to be using the same
words but have two completely different use cases in mind, and in the
process have two completely different conversations.