[openpgp] Ring signatures and subkeys

[Vincent Yu <[e-mail]>]

Thank you for your comments, dkg and Werner. Both of you brought up good 
points about the use of subkeys with ring signatures, so I am starting a 
new thread to discuss them.

At its heart, a ring signature knows very little about the nature of the 
keys that are fed to it. It knows nothing about the relation between 
primary keys and subkeys. It also knows nothing about the ring signing 
capabilities of its possible signers. Given that ring signatures are 
unable to take such considerations into account, I think it would be a 
mistake to try to encode or to enforce which subkeys can be used for 
ring signatures.

To be more concrete, when a recipient of ring signature can dictate 
which subkey must be used for ring signatures, there are certain attacks 
on non-transferability that the recipient can execute against senders.

Suppose that Alice has been talking to Bob, and has been using ring 
signatures to provide non-transferable authenticity. Bob expects to 
receive from Alice some juicy message that he wants to share with Eve, 
and he wants to prove to Eve that Alice signed the message. He can 
attack Alice's non-transferability as follows: cooperate with Eve to 
create a bait by having Eve create a subkey that Bob claims as his new 
subkey (key binding signatures can be computed both ways without 
requiring Eve to reveal her bait's private key). Bob deploys this bait 
by getting its public key into Alice's keyring. This can be done in many 
ways; for instance, if Alice synchronizes regularly with key servers, 
then Bob can inconspicuously put the bait on a key server. If Alice's 
software creates new ring signatures to Bob using only the bait, then 
Bob can prove to Eve that Alice signed the new messages (because Eve 
knows that Bob does not have the bait's private key). Among all this, 
Alice never realizes that Bob has destroyed the non-transferability of 
her ring signatures.

The attack outlined above is a specific instance of a class of attacks 
that exploit the fact that users can have public subkeys for which they 
provably do not possess the private key. My biggest worry about such 
attacks is that they are incredibly easy to execute in the current 
framework with key server synchronization being good practice, and the 
typical victim might never realize that the attack has occurred.

On 03/14/2014 10:37 AM, Daniel Kahn Gillmor wrote:
> Vincent's original spec says:
>
>>> It is common for an OpenPGP key bundle to contain multiple keys that
>>> are capable of producing signatures. For instance, this is the case
>>> when the primary certification key and a subkey both have their signing
>>> flags set (see Section 5.2.3.21 of RFC 4880). When a user wishes to
>>> create a ring signature that includes a key ID in a bundle that
>>> contains other keys capable of signing, it would make sense to include
>>> all signing-capable keys in the ring signature.
>
> But I'm not convinced by this last conclusion.  Why include all the
> signing-capable keys?  I have a primary signing-capable key and a subkey
> that is also signing-capable.  When i sign this message, i will only
> sign it with one of them.  What is the rationale for including all the
> keys?  It seems like it just makes the signature creation take longer,
> and i don't see the benefit.  presumably the signing keys are likely to
> be all controlled by the same person, right?

You are right that my recommendation there results in signatures that 
are potentially larger and take more time to generate and verify.

I intended that to be a recommendation for a safer default that can be 
overridden by users who know what they are doing. The main alternative 
default that I considered is to use either the newest or the oldest 
signing subkey, which falls too easily to the outlined attack.

However, I now realize that even with my recommendation in place, the 
attack is still easy if Bob's primary certification key does not have 
the signing flag set: he simply needs to revoke all signing-capable 
subkeys and execute the attack as before. With this in mind, I 
tentatively suggest that ring signatures should (again, as an 
overridable default) include the primary certification key, even if its 
signing flag is not set. All primary keys are intrinsically 
signing-capable, so there should be no issue implementing this. I'm 
unsure about this and would be interested in everyone's comments.

On 03/14/2014 12:46 PM, Werner Koch wrote:
> On Fri, 14 Mar 2014 14:55, [e-mail] said:
>
>> A major consideration in the proposed scheme is to make sure that it
>> is separable; i.e., that different types of existing keys can be used
>> together without a dedicated setup. In the current scheme, signers are
>
> Old implementations won't be able to handle ring signatures at all.  To
> use existing keys, users can simply use dedicated subkeys.
>
>> able to produce a ring signature without any cooperation or setup from
>> the other possible signers (as long as they each have an RSA, DSA, or
>
> You better need some setup from the other possible signers: They should
> be able to create ring signatures.  If you look at a ring signature and
> you can figure out that only key has been created with a software
> version capable of handling ring signatures it would be easy to single
> out who actually did the signature.  Unfortunately we can't completely
> hide all hints on the software version used.  For example analyzing
> signed mails from mailing list archives should allow to guess which
> software version is used.

I think there is a large security / usability trade-off here. On the one 
hand, the non-transferability "guarantee" of a ring signature is indeed 
much greater if everyone involved had a dedicated key for which they 
explicitly claim to have ring signing capabilities. On the other hand, 
that requires significant setup on both ends and I don't see it becoming 
general practice. When a protocol requires cooperation from both sides, 
it's hard for it to gain any ground at all, especially when the 
alternative (basic signing) is already well-established. But when it 
requires only one side to cooperate, users who want it can use it 
whenever they want.

My hope is that one day creating a ring signature requires no more from 
Alice than updating to the latest version of GnuPG and running:

     gpg2 --clearsign --ring-signature --recipient Bob

Bob will not be able to verify the signature if he does not have an 
implementation that supports ring signatures, but at the very least 
Alice can still create a ring signature without requiring Bob to set 
things up.

Vincent