Cryptographic Signatures
 

Cryptographic Signatures

A cryptographic signature is supposed to have the following properties:

  1. The signature can't be transferred to another message.

  2. The message can't be changed without this being detected.

  3. The signer cannot deny signing a message after doing so.

This - especially the last point - is quite a lot! Let's look at these one at a time:

  Non-Transferrable

A signature can't be transferred to another message. This is usually done by letting the signature process include a hash of the message. The hash function is furthermore assumed to not hash any pair of interesting messages to the same hash value. Of course, a message with a lot of dead space - regions where you can manipulate bits freely without affecting the appearance of a message, such as an embedded uncompressed truecolor image in a document - may be altered and the alteration compensated with changes in this dead space.

  Guarantees Integrity

This is again related to the hash function. It is assumed that it would take too long to find another message with the same hash value to be feasible.

  Non-Repudiation

"Non-Repudiation" means that a participant in a transaction can't claim that they didn't authorize the transaction once the transaction has been finalized. That is, once we've both signed the contract, you can't back out of the deal by claiming that you never signed.

This is a very difficult thing to prove absolutely. Normally, the signature involves the use of the signer's private key. Since is it assumed that only the signer has access to the key, the presence of the key means that the signer was involved. Thus, the reasoning goes, the signer can't deny having signed the message.

However, let's look at where things can go wrong:

  1. Someone else has the key: Maybe someone stole the private key and managed to break the passphrase. Given that people choose passwords that they can remember and not neccessarily secure ones, this is quite feasible. Add an email worm that scans the drive for public-key keychains and you're good to go.

  2. Signing program signs wrong message: Suppose the message is HTML formatted, as too much email is today. The sender's program has a problem with displaying certain elements - the result being that the're simply not shown on the screen. Alternatively, the program could have some internal bug that messes up the message as it is signed.

  3. Coercion: "Rubber hose cryptanalysis" - gun to head of signer. Makes signature legally invalid.

These two points pretty much removes any absolutes from the guarantee of digital signatures. But does it matter? Let's look at how a much more primitive signing happens.

  Non-Repudiation of Ink Signatures

A couple of weeks ago I signed a $22.5M deal. Given that "high value transactions" in some crypto tutorials are $1500, I think this one qualifies. What really happened? Well, the four signers (me and three others) went to a lawyer's office, and with our counsel and their present, we initialized ever page of the contract (~40 pages and ten copies) and the schedules (~60 pages and ten copies). We then signed the contract in two places. I am told that these signing ceremonies can take two days for large transactions ($1B and upwards).

Given the ease with which an ink signature - not to mention my initials - can be forged, what provides non-repudiation of this?

Well, you have the lawyers present. You have a paper trail of negotiation emails and witnesses to phone conversations. In short, you have a whole lot more than just the signature. Should this go to court, we have witnesses that can testify as to who were present, what the execution copy of the contract contained, that everyone signed volutarily.

I would submit that a functioning legal system, where judges can impose sentences on people breaking contracts, is the only real guarantee we have for non-repudiation. Because digital signatures can only ever be one of many pieces of evidence in a disagreement.