Re: Back-signatures, part II

At 12:58 AM 10/29/2003 -0500, David Shaw wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> On Tue, Oct 28, 2003 at 08:18:50PM -0800, Trevor Perrin wrote:
> >
> > At 05:23 PM 10/28/2003 -0500, David Shaw wrote:
> >
> > >I just checked over my notes about back-signatures, and there was a
> > >second proposal to solve the same problem.  For completeness, here is
> > >the other proposal.
> > >
> > >To repeat the problem: it is possible for an attacker to take a
> > >signing subkey from a victim's key and attach this signing subkey to
> > >the attacker's own key.  The attacker does this by issuing a new
> > >binding signature on the subkey from his own primary key.  The end
> > >result is that a signature issued by this signing subkey may be
> > >claimed to be from either the attacker or the victim.
> >
> > Does this attack also work if the attacker issues a subkey binding
> > signature on the victim's *primary* key, so as to claim signatures issued
> > by this primary key?
>
> You mean take the victim's primary signing key, transform it into a
> signing subkey and bind it to the attacker's primary key?  Yes, the
> attack would still work, but either of the proposed fixes still
> prevents it.
[...]

I think you're right.


> > I don't want to re-confuse an issue you've just clarified, but here's a
> > generalization of the second proposal that might be worth considering:
> >
> > You could include in *every* signature a subpacket that contains a hash of
> > *all* enclosing context.  By "enclosing context" I mean the key packet for
> > the primary key, along with its self-signatures, and the key packet for 
> the
> > subkey as well (if the signing key is a subkey) along with the subkey
> > binding signature.
> >
> > This would protect against the above attack, and some other manipulations,
> > such as:
> >
> >  - A naive user re-uses the same subkey under 2 different primary
> > keys.  Signatures performed by the subkey can't be confined to being under
> > one or the other primary key.  This problem can be easily avoided: just
> > don't re-use keys, but that caveat would be unnecessary if signatures
> > committed to their enclosing context.
>
> I don't see this as a problem, actually.  So what if a user uses the
> same subkey under two different primaries?  The user controls the
> subkey, and so can issue valid back-signatures (or fingerprint
> subpackets).  The owner of a subkey can do what they like with it.
The problem arises when the user signs a document with the subkey, and 
wants this signature to be under one of his particular primaries.  Say he 
has Work and Personal primary keys.  He signs something and wants to 
indicate that it's under his Work primary key.
He could include the Signer's User ID in the signature, but what if both 
primaries have the same User ID?
If every signature committed to all previous context, then the verifier 
could always recognize that this signature was performed under a particular 
primary key, so there wouldn't be ambiguous cases like this.


> >  - Attacker generates a key that verifies a signature issued by someone
> > else [1], then puts this key on a key server where a victim finds it, and
> > assumes that since it verifies the signature correctly, it must belong to
> > the originator of the message.  There's caveats that make this attack 
> hard,
> > and not very useful [1].  Still, it could be avoided entirely if the key
> > used to create a signature was hashed as input to the signature.
>
> Hmm.  I think I see where you are going with this, but isn't this sort
> of the same problem as the "stolen primary that is kept as a primary"
> above?  I can steal a primary key and add a user ID and bribe someone
> to sign it (since I can't sign it myself of course).  Just because
> I've constructed a key that can verify a signature doesn't mean that I
> issued that signature.
You're right, and as long as users keep that in mind, they're safe.

But there's the rub.  It's unintuitive that you can generate a key that 
verifies someone else's signature.  And when things are unintuitive, 
there's room for users to screw up.
I.e.: a user who receives a signed message through some secure channel (say 
someone hands them a message on a floppy disk), might then retrieve a key 
through an *un*secure channel, and attempt to validate the key by verifying 
the message with it.
You can say: the user screwed up, we can't help him.  But if the signature 
covered the public key that produced it, then the user's naive assumption 
would be correct, and his behavior would be safe.
The issuer key ID subpacket makes an attack hard, though, because the 
attacker would have to try ~ 2^64 trial keys that verify the signature, 
before discovering one that *also* has the right issuer key ID.  But if the 
signature covered the public key with a full hash, an attack would be even 
harder.

>   Or forget computer trickery at all: I can just
> get myself a fake ID that says I am "Trevor Perrin" ;)
The trickery I'm envisioning is where a naive verifier tries to validate a 
key by using it to verify a message that was received over some secure channel.


> >  - Attacker fiddles the timestamp in someone's primary-key packet, so that
> > the key still verifies the signature correctly, but the sender appears to
> > have a different fingerprint than he really does.
>
> This would break all signatures on the key, including the
> self-signatures.  I think that would give the attack away.
That's true.  As long as primary keys have self-signatures, and verifiers 
are required to check them before doing anything else with the key, that 
stops this.

Basically, I just like the idea of having signatures cover all relevant 
context.  So I was trying to find some trickery that would justify doing 
this.  The trickery isn't very good, but there's trickier people than me 
out there..
So I dunno, I'm not sure how to balance the costs and benefits here, I just 
wanted to toss this out.
Trevor