Subject: The last word (hopefully) on back-signatures

From: David Shaw <[email-masked]>
Date: Mon, 12 Jan 2004 14:58:11 -0500

Apologies for the delay in this.  I've had a lot on my plate recently.
In November, I posted two proposals for comment on the "stolen
signature"/back-signatures problem.  Here now is my final proposal
with the various comments taken into account:

First to briefly recap the purpose for this, there is a minor problem
in the current subkey design where a signing subkey can be taken from
an existing key, and bound to the attacker's primary key with a
binding signature issued by the attacker's key.  The attacker cannot
use this stolen key to issue a signature of course, but can claim that
an existing signature was issued by him.

The proposed fix is to add an additional signature into the mix -
currently we have only a binding signature issued by the primary key
on the signing subkey.  I suggest we add a signature (the
"back-signature") issued by the subkey on the primary key.  This
prevents the attack as the attacker cannot issue this signature, and
thus cannot claim ownership of an existing signature.  The
back-signature design seemed to enjoy greater approval than the other,
as well as having the nice detail that it could automatically protect
signatures issued before the back-signature was added.

The specifics (suggestions - I'm not wedded to this particular
language):

1) Define a new type of signature subpacket that consists of a regular
   signature contained in a subpacket.

    Add to section 5.2.3.1 ("Signature Subpacket Specification"):

         32 = embedded signature

    Add a new section to 5.2.3.x:

        5.2.3.26. Embedded Signature

         (1 signature packet body)

         This subpacket contains a complete signature packet body as
	 specified in section 5.2 above.  It is useful when one
	 signature needs to refer to, or be incorporated in, another
	 signature.

2) Define a new signature class (Hal suggested 0x19), that is defined
   as a subkey signature on a primary key.

    Add to section 5.2.1 ("Signature Types"):

       0x19: Primary key Binding Signature

         This signature is a statement by a signing subkey,
         indicating that it is owned by the primary key.  This
	 signature is calculated directly on the primary key itself,
	 and not on any User ID or other packets.

3) At (sub)key generation time (or later, for existing keys) create
   this 0x19 signature and store it as a subpacket on the subkey
   binding signature.  It does not matter whether it is a hashed
   subpacket or not.  The hashing rules for 0x19 are the same as a
   0x18 signature - we hash the primary key, then the subkey, and
   issue a signature from the subkey over this hash.

    In section 5.2.1, add to the description of the 0x18 signature:

        Signing subkeys have an embedded signature subpacket on this
        signature which contains a 0x19 signature by the signing
	subkey on the primary key.

    In section 5.2.4, change the sentence:

        A subkey signature (type 0x18) then hashes the subkey, using
	the same format as the main key (also using 0x99 as the first
	octet).

     to:

        A subkey binding signature (type 0x18), or primary key binding
	signature (0x19) then hashes the subkey, using the same format
	as the main key (also using 0x99 as the first octet).

    In section 10.1, change the sentence:

        Each Subkey packet must be followed by one Signature packet,
	which should be a subkey binding signature issued by the top
	level key.

    to:

        Each Subkey packet must be followed by one Signature packet,
	which should be a subkey binding signature issued by the top
	level key.  For subkeys that can issue signatures, the subkey
	binding signature must contain an embedded signature subpacket
	with a primary key binding signature (0x19) issued by the
	subkey on the top level key.

That should do it.  I've tried to keep the number of changes to a
minimum, so this may seem somewhat terse.  I do think it is sufficient
to explain the proper way to write the additional signature.  I have
code for GnuPG that follows this basic design, and it works well.

David

---

From: Adrian von Bidder <[email-masked]>
Date: Tue, 13 Jan 2004 09:24:43 +0100

On Monday 12 January 2004 20:58, David Shaw wrote:
> I have

Will it be possible to convert existing subkeys? AFAICT, putting the 0x19 
signature in an unhashed packet, this should be relatively painless. (Will 
keyservers properly deal with subkeys with the additional packet suddenly 
appearing?)

cheers
-- vbi

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

---

From: David Shaw <[email-masked]>
Date: Tue, 13 Jan 2004 13:21:12 -0500

On Tue, Jan 13, 2004 at 09:24:43AM +0100, Adrian von Bidder wrote:
Content-Description: signed data
> keyservers properly deal with subkeys with the additional packet suddenly 

Yes, it is possible to convert existing subkeys.  One of the reasons I
advocated using a subpacket was for this ability.  Based on a number
of tests, and a conversation with the author of SKS, I don't see any
problem with updating existing subkeys on the PKSD or SKS servers.  I
haven't looked at the LDAP server yet.

David