[Enigmail] On signatures

[Robert J. Hansen]

So far a lot of people have been hotly contesting my claim that you
cannot conclude anything from a bad (syntactically incorrect) signature.

I'm going to prove that you can't.  If you want to change my mind,
you're going to have to show a flaw in my logic--a logical fallacy, a
chain of reasoning that does not hold, whatever.  Simply saying "I
disagree" will not cut it.  Crypto is math.  In math, you need to be
able to prove your assertions.

=====

Signed data--whether on a key or on a message--consists of two parts:
the message and the signature.  The signature is purely a function of
the message and a certificate; it does not encompass itself.  All
signatures are made according to the rules of a signature algorithm.

For a signature S made with certificate C and signature algorithm Sa on
data D, it is syntactically meaningful if and only if Sa(C, D) = S.  In
the case of an OpenPGP message, D is H(m), where H is a hash algorithm
and m is the original message.  Thus, you can say "an OpenPGP signature
S is meaningful if and only if Sa(C, H(m)) = S."

This sort of syntactic examination is easy to automate.  If this
sentence is true for a piece of signed data, then we can begin to
concern ourselves with semantic examination.  Let's not go there yet.
The concerns people are raising seem to be "a bad signature tells you
the message was tampered, what are you talking about?"--so let's just
talk about bad (syntactically invalid) signatures.


Sa(C, H(m)) = S


The only way a signature can be bad is if this equation fails to hold:
that is to say,


Sa(C, H(m)) != S


Clearly, there are at least six different things that can cause a
message to go haywire.  Each will be discussed in turn.


1.  YOU'RE USING THE WRONG SIGNATURE ALGORITHM.

This is actually a lot more common than you might think.  For instance,
if I use DSA2 and send a message to someone who is using GnuPG 1.4.0,
GnuPG will flag the signature as bad due to my DSA2 key being
incompatible with the DSA1 signature algorithm GnuPG 1.4.0 is using.

So: one conclusion you can draw from a syntactically invalid signature
is "I'm using the wrong algorithm."  The signature (S) is good; it's the
algorithm used (Sa) that's wrong.  If this is the case, the failure to
verify is no evidence the message was tampered with in transit.


2.  YOU'RE USING A CORRUPT OR INCORRECT CERTIFICATE.

Certificates are stored in a file on your PC.  Files get corrupted.  We
all know this.  I've had my own keyrings get corrupted four times in the
last decade.  It is a rare, but by no means impossible, occurrence.  The
signature (S) is good; it's the certificate (C) that's wrong.  If this
is the case, the failure to verify is no evidence the message was
tampered with in transit.


3.  YOU'RE USING THE WRONG HASH.

This one is pretty unlikely, unless you're using PGP/MIME.  PGP/MIME has
an unfortunate tendency to misreport what hash is used by the message
body.  If your application trusts the PGP/MIME header, you can quite
easily use the wrong hash.  If this is the case, the failure to verify
is no evidence the message was tampered with in transit.


4.  THE MESSAGE HAS BEEN ALTERED.

If the message gets altered, H(m) gets altered--very probably, at any
rate, better than one in 2**160--and the signature fails.  If this is
the case, the failure to verify is direct evidence the message was
tampered with in transit.  However, in order to prove this is the case,
you first have to prove the message was altered.  That bears some
repetition: if you want to prove the bad signature means the message was
altered, you first have to prove the message was altered, and you can't
introduce the bad signature as evidence the message was altered.  That's
a logical fallacy called /petitio principii/, or assuming the /a priori/
validity of the proposition in question.


5.  EQUALITY DOESN'T MEAN EQUALS.

For this to happen, a stray cosmic ray will have to flip a bit in your
computer.  For just an instant, true becomes false and false becomes
true.  It's unlikely, but possible, and phenomenally difficult to prove
one way or another.  By and large this one can be discounted due to the
phenomenal odds against it.


6.  THE SIGNATURE ITSELF HAS BEEN ALTERED.

If you're going to posit the message may have been altered in transit,
you also need to posit the signature may have been altered in transit.
After all, they're sent as a single chunk of signed data (usually) over
the same communication channel (usually).  If the signature has been
altered, the odds are overwhelmingly good the signature check will fail.
 If this is the case, the failure to verify is no evidence the message
was tampered with in transit.




... There are six elements in that mathematical equation that tell us
whether a signature is good or bad.  Any of the six elements can fail.
One of those six elements is phenomenally unlikely.  The others are all
within the realm of possibility.

If you want to assert that a bad signature means the message has been
tampered with, there are three ways to go about it.


1.  YOU CAN PROVE THE MESSAGE HAS BEEN ALTERED WITHOUT USING THE SIG.

If you can prove the message has been altered, then it is overwhelmingly
likely the bad signature is the direct cause of the bad message.
However, to prevent /petitio principii/, you cannot use the signature to
prove the message has been altered.


2.  YOU CAN ELIMINATE POSSIBILITIES 1-3 AND 6.

If you can eliminate possibilities 1-3 and 6, all of which are
reasonably probable, and we can agree that possibility 5 is phenomenally
improbable, then we can conclude from Holmes' Law that possibility 4 is
overwhelmingly probable.  (Holmes' Law: "Once you have eliminated the
impossible, whatever remains, however improbable, must be the truth.")


3.  YOU CAN SIMPLY DECLARE #4 TO BE THE CASE.

If you elect this, then you are projecting either your own ignorance or
your own emotional desires onto the data, rather than deducing facts
from the data.  This is not reasoning, this is cargo-cultism, and it
will not be taken seriously by anyone who understands mathematics.




... If anyone can spot a logical flaw in this argument, please, correct
me.  However, that said, I don't think there are logical flaws in this
argument, and I think it goes to show that you cannot arbitrarily
declare "a bad signature means the message was tampered with in transit".

By itself, a bad signature tells you absolutely nothing about whether a
message was tampered with in transit.  By itself, a bad signature
possesses absolutely no informational value.  When we have data that's
totally lacking in information, we call that 'noise', and we aim to
reduce the amount of noise in our communications--including in our user
interfaces.