Subject: Back-signatures, part II

From: David Shaw <[email-masked]>
Date: Tue, 28 Oct 2003 17:23:56 -0500

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.

Second proposed solution: on all signatures issued by a signing
subkey, include a copy of the fingerprint of the primary key that
"owns" this subkey.  An attacker cannot issue signatures from the
stolen subkey at all, so is foiled.

The details:

1) Define a new type of signature subpacket that consists of a
   fingerprint.

2) Include it on all subkey signatures as a hashed subpacket.  (It
   must be hashed to be effective).

Comments:

1) Unlike the subkey-signs-primary key solution, old signatures issued
   before this back-signature protection became available are NOT
   automatically protected.

2) Like the other solution, this does not require generating a new
   subkey.

3) Like the other solution, this uses a signature subpacket so there
   should be no backward compatibility problems.

4) This is simpler than the other solution in several ways (less code
   to do it, for one, does not require the key to be modified and
   redistributed, for two).

5) This is likely to be faster than the other solution, as it only
   requires two signature verifications (the data in question plus the
   subkey binding signature) rather than three (the data in question,
   the subkey binding signature, and the back-signature).

6) It will no longer be possible to issue a v3 signature from a
   signing subkey.  I don't see this as a major problem since the
   older programs that don't understand v4 signatures don't
   understand signatures from signing subkeys anyway.

Comparing the two proposals seems to be a wash.  Back-signatures are a
bit slower, but protect existing signatures.  Including a fingerprint
is a bit faster, but does not protect existing signatures.

Perhaps speed and simplicity should win out here.  Speaking as someone
who regularly uses a signing subkey, I don't particularly care if my
old signatures are protected or not.  I obviously can't speak for
everyone using a signing subkey though.

Again, comments welcome.

David

---

From: Michael Young <[email-masked]>
Date: Tue, 28 Oct 2003 22:34:17 -0500

I don't feel all that strongly about this -- in fact, I don't
consider the problem all that serious in the first place -- but
I do find the properties of the cross-signature subpacket
solution more attractive.

If I did care about someone claiming my signatures as their own, I
think I would care about old signatures as well.  Under the
per-message scheme, if I cared about old signatures, I'd have to find
all of those signatures *and the associated documents* in order to
reissue them, and then I'd have to deal with disseminating them.

User agents that keep a "key ring" will likely verify a
cross-signature only once, at the same time that they verify the
subkey binding signature.  It need not be a per-message cost.  The
same is true for the storage and transmission of the extra material.
Yes, the cost is higher for a one-time verification... I can
live with that.

Also, note that the specification already provides a "signer userId"
subpacket that could be used to nearly the same effect as a "signer
primary fingerprint" subpacket.  As I recall, the very first proposal
was to recommend/require the use of the existing "signer userId"
subpacket.

I would have no objection to defining both mechanisms, to account for
differing user needs.  If I were forced to choose only one, I'd
take cross-signatures, as it adds more value beyond what we have now.

---

From: Trevor Perrin <[email-masked]>
Date: Tue, 28 Oct 2003 20:18:50 -0800

>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?

>stolen subkey at all, so is foiled.

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.

  - 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.

  - 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.

These aren't a big deal, but it just seems a good principle, in general, 
for signatures to cover as much context as is needed to properly interpret 
them.

Trevor

[1] sci.crypt thread: Choosing key to verify someone else's sig?

---

From: Trevor Perrin <[email-masked]>
Date: Tue, 28 Oct 2003 20:34:55 -0800

At 10:34 PM 10/28/2003 -0500, Michael Young wrote:
[...]
>primary fingerprint" subpacket.

I think that would prevent the version of this where the attacker tries to 
convince the verifier that the signed message came from his *name*.

It wouldn't prevent the version where the attacker tries to convince the 
verifier that the signed message came from his *key*, which is what using a 
key fingerprint adds.

Trevor

---

From: David Shaw <[email-masked]>
Date: Wed, 29 Oct 2003 00:02:47 -0500

> solution more attractive.

I think I do as well.  I like that it handles old signatures, and I'm
not yet convinced that the include-the-fingerprint covers all of the
attacks that the back-signature does.

> was to recommend/require the use of the existing "signer userId"

Nearly the same effect, yes, but ultimately a different problem.

David

---

From: David Shaw <[email-masked]>
Date: Wed, 29 Oct 2003 00:58:33 -0500

> signature on the victim's *primary* key, so as to claim signatures issued 

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.

The back-signature fix prevents this flavor of the attack since the
attacker still could not use the stolen key (be it primary or subkey),
to issue the back-signature.

The include-the-fingerprint fix prevents this flavor of the attack as
well.  Since the key is a primary, existing signatures from the key
would not contain the fingerprint subpacket at all, and would
therefore be suspect.

There are four basic permutations of this attack:

1) Attacker steals a subkey and keeps it as a subkey.  Either fix
   works here.

2) Attacker steals a primary and makes it into a subkey.  Either fix
   works here.

3) Attacker steals a subkey and makes it into a primary.  Neither fix
   is relevant here since the attacker would be unable to bind a user
   ID to such a primary key.  Without a bound user ID, it would be
   difficult at best to get such a key trusted.

4) Attacker steals a primary and keeps it as a primary.  Neither fix
   is relevant here either, for the same reason as #3.

> 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.

> 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.  Or forget computer trickery at all: I can just
get myself a fake ID that says I am "Trevor Perrin" ;)

> 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.

David

---

From: Trevor Perrin <[email-masked]>
Date: Tue, 28 Oct 2003 22:59:31 -0800

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

>-----BEGIN PGP SIGNED MESSAGE-----
>Hash: SHA1
>
[...]

I think you're right.

>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.

>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

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.

>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

---

From: David Shaw <[email-masked]>
Date: Wed, 29 Oct 2003 15:13:06 -0500

On Tue, Oct 28, 2003 at 10:59:31PM -0800, Trevor Perrin wrote:

> >> 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.
> >

A user can "legally" use the same subkey under two different
primaries.  I think this is more of a feature request than an attack.

The include-the-primary-fingerprint fix for the original attack has a
side effect that gives the information you want here, but I still
don't think this is an attack on the system.

> signature covered the public key with a full hash, an attack would be even 

Note that most implementations do not store the issuer key ID in the
hashed portion of the signature.  The issuer ID is thus not part of
the signature.

David

---

From: Trevor Perrin <[email-masked]>
Date: Wed, 29 Oct 2003 13:33:23 -0800

At 03:13 PM 10/29/2003 -0500, David Shaw wrote:

>primaries.

yeah, but if he does this, a verifier might assume that the signature was 
intended under one primary key, when it was really intended under another.

>   I think this is more of a feature request than an attack.

It's only an attack if a bad guy can choose which primary key the signature 
appears to be under, in a way that tricks the verifier into treating the 
signature incorrectly.

I believe signing subkeys are rare, re-use of signing subkeys is rarer, and 
re-using them in such a way that an attacker
can do this trick, and accomplish something, is pretty unlikely.

I'm just trying to point out ways in which signatures can be placed in 
different contexts than what the signer intended.  I view that as the 
commonality that links these things together - if every signature had a 
subpacket that contained a hash of:
  - the key used to perform the signature
  - the primary key (if the signing key is a subkey)
  - any self-signatures on the primary key, and the binding signature on 
the subkey,

then I'd feel re-assured that every signature was bound to all relevant 
context, and no manipulations such as
  - splicing someone else's key under your primary key, to claim their 
signatures
  - fiddling with which primary key a signature appears to be under
  - presenting a different key that happens to verify a signature
would be possible.

The one manipulation that *would* still be possible is presenting someone 
else's key under your primary key, when there's no signature by the 
victimized key present to give the lie to this.  For that, some sort of 
additional back-signature is unavoidable.

But these approaches could be combined - if the back-signature contains the 
sort of subpacket I'm talking about, that's enough to make it a back-signature.

So I guess I'm saying *every* signature should be a back-signature, in that 
it covers the relevant primary key and sub-keys.  But you could also add an 
extra back-signature just when sub-keys are present.

>hashed portion of the signature.  The issuer ID is thus not part of

In the odd case I'm considering, the verifier gets the signed message 
through some secure channel - someone hands him a signed message on a 
floppy disk, for example.  So even though the issuer key ID isn't part of 
the signature, an attacker who's trying to make a fake key that verifies 
the message, still has to match the issuer key ID.

So that provides some measure of protection, but if the signing key was 
hashed as an input to the signature, that would provide even more.

Trevor

---

From: David Shaw <[email-masked]>
Date: Wed, 29 Oct 2003 17:04:15 -0500

> appears to be under, in a way that tricks the verifier into treating the 

The user intentionally chose to use the same subkey in two places.
The user intentionally issued the signature.  The user shouldn't be
surprised that either copy of the same key can verify that signature.
If a user wants to be unambiguous as to which hat he was wearing when
he issued the signature, he shouldn't use the same key everywhere.

This is somewhat similar to a situation where a user has two user IDs
on his key: "user at evilcompany.com" and "user at
anonymouswhistleblowers.com".  If the user sends out whistleblower
information and signs it with that key, he shouldn't be surprised when
he is fired...

David

---

From: Michael Young <[email-masked]>
Date: Wed, 29 Oct 2003 17:08:51 -0500

Trevor Perrin wrote:
 >> Also, note that the specification already provides a "signer
 >> userId" subpacket that could be used to nearly the same effect as
 >> a "signer primary fingerprint" subpacket.
 >
 > I think that would prevent the version of this where the attacker
 > tries  to convince the verifier that the signed message came from
 > his *name*.

In practice, I think it's far more interesting to claim that a
particular real-world identity signed a document than a particular
primary key.  But I understand the difference -- that's why I said
"nearly".

Trevor Perrin wrote (in another message):
 > 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 add yet another impediment to rewriting self-signatures
(or binding signatures).  To permit rewriting, you'd have to keep
all past versions (and try each one at verification time) or copy
that material into the signature.

Very little of this "context" is relevant for most uses.  For special
needs, we have notation packets to carry arbitrary additional
context.

---

From: Trevor Perrin <[email-masked]>
Date: Wed, 29 Oct 2003 15:17:33 -0800

>he issued the signature, he shouldn't use the same key everywhere.

Yeah, this is easily avoided if you just don't re-use keys.

It would also be avoided if the signature is calculated over the hat the 
user was wearing, when he issued the signature.  Then you can re-use keys 
without fear that a verifying party will be confused or tricked about which 
copy of the key you signed with.

>information and signs it with that key, he shouldn't be surprised when

Anonymity throws a different spin on things.

The case I was thinking of, where key re-use might occur, is in something 
like a smartcard, or a delegated signing server.  This might have limited 
key storage, or it might not be able to generate new keys (not enough 
power, or not enough randomness).  If different users share the device, 
they each might want to certify the device's subkey as belonging under 
their own primary key.

The device would want to make sure each of it's signatures are attributable 
to the right primary key.  If every signature is a back-signature, this is 
accomplished.

Trevor

---

From: Trevor Perrin <[email-masked]>
Date: Wed, 29 Oct 2003 15:44:46 -0800

>that material into the signature.

Good point - you'd only want to include context that won't get invalidated 
by re-issued signatures.  So I guess we could change the proposal to only 
cover key packets, not signature packets, without losing too much:

Proposal:  Include in every signature a hashed subpacket that contains a 
hash of the relevant key packets.  The relevant key packets are the primary 
key packet if the signing key is a primary key, or the primary key *and* 
subkey packets if the signing key is a subkey.

This stops these 3 manipulations:
  - issuing a subkey signature to someone else's key, and claiming their 
signatures
  - changing the primary key that a signature performed by a re-used subkey 
belongs under
  - an attacker generating a new key that verifies someone else's signature

Trevor

---

From: Adrian von Bidder <[email-masked]>
Date: Thu, 30 Oct 2003 09:25:52 +0100

[no cc:s please]
On Thursday 30 October 2003 00:17, Trevor Perrin wrote:

[subkey signatures - embedding the primary to avoid misattribution]

> to the right primary key.  If every signature is a back-signature, this is

The hash of the primary would be over the public key? So the holder of the 
secret subkey can make his subkey signature appear to come from whatever 
primary he wants, he doesn't need the secret (primary) key.

So, in your scenario, sharing the secret subkey will effectively mean that 
each can make signatures that will verify with the other's primary.

Or do I misunderstand someting here?

cheers
-- vbi

-- 
featured product: vim - http://vim.org

---

From: Trevor Perrin <[email-masked]>
Date: Thu, 30 Oct 2003 10:37:18 -0800

At 09:25 AM 10/30/2003 +0100, Adrian von Bidder wrote:
 >> The device would want to make sure each of it's signatures are
 >>attributable to the right primary key.  If every signature is a
 >>back-signature, this is accomplished.
 >
 >The hash of the primary would be over the public key? So the holder of
 >the secret subkey can make his subkey signature appear to come from
 >whatever primary he wants, he doesn't need the secret (primary) key.

He can make his subkey signature appear to come under any of the primary 
keys that have trusted him (i.e. any of the primary keys that have issued 
him a subkey binding signature).

 >
 >So, in your scenario, sharing the secret subkey will effectively mean
 >that each can make signatures that will verify with the other's primary.

In my scenario, a bunch of different primary key holders trust a single 
subkey holder to perform signatures on their behalf.  The subkey holder 
wants to make sure that each signature is attributed to the proper primary key.

Maybe this is a use case that subkeys aren't intended to support.  But if 
every signature covered the primary key and subkey it was produced under, 
this would work.

Trevor

---

From: David Shaw <[email-masked]>
Date: Thu, 30 Oct 2003 15:20:16 -0500

On Thu, Oct 30, 2003 at 10:37:18AM -0800, Trevor Perrin wrote:

> In my scenario, a bunch of different primary key holders trust a
> single subkey holder to perform signatures on their behalf.  The
> subkey holder wants to make sure that each signature is attributed
> to the proper primary key.

I'm having trouble seeing the lack of this ability as a problem, much
less a problem that needs a fix.

It's always possible to come up with a (perhaps convoluted) situation
where any feature would be useful, and with all due respect, I think
this scenario crosses the convolution line.

Sharing signature keys is generally not a good idea.  Note in the
example that if the trusted subkey holder stops being trusted, he can
issue signatures in the name of any of the users.  Plus if any of the
keyholders has a key compromise, all keyholders must re-key.

If and when such a situation develops, I'd support a supplemental RFC
to specify the necessary signature subpacket.  Until the proposed
scenario becomes more concrete, anything we can do about it in 2440bis
is apt to be incorrect in some detail.  In the meantime, I'm content
to say if a user really wants to share keys, he can use a signature
notation to include whatever additional information he lines.  I don't
think this needs to be in 2440bis.

David

---

From: Trevor Perrin <[email-masked]>
Date: Thu, 30 Oct 2003 14:03:43 -0800

>this scenario crosses the convolution line.

Fair enough.  The more useful scenario I was thinking of is where a single 
primary key is held by a server, which issues short-lived subkeys to 
different users, so they don't have to bother keeping a primary key secure.

But in that case, I think the "Signer's User ID" subpacket is sufficient to 
differentiate things.

Trevor

---

From: Michael Young <[email-masked]>
Date: Fri, 31 Oct 2003 11:12:39 -0500

>to the proper primary key.

I'd love to have a better framework for publicly expressing trust
relationships, but I really don't think this was one of the intended
uses of subkeys.  [Given where the RFC stands, I think that trust
expresion would best be addressed by a new, adjunct RFC.]

---

From: Trevor Perrin <[email-masked]>
Date: Fri, 31 Oct 2003 09:50:27 -0800

At 11:12 AM 10/31/2003 -0500, Michael Young wrote:
>Content-Transfer-Encoding: 7bit
>
>

Sure, no problem - I was just thinking we could slay these things with the 
same stone, but in retrospect it seems like it only confuses an issue that 
David had done a good job clarifying..

Trevor