[openpgp] Proposal for a separable ring signature scheme compatible with RSA, DSA, and ECDSA keys

[Vincent Yu <[e-mail]>]

I propose an extension to RFC 4880 to add support for ring signatures 
based on a separable scheme published by Abe et al. in 2002 [AOS04].

The following additions to RFC 4880 are proposed:

1. A new public-key algorithm, ID 22, for ring signatures.

2. A new signature subpacket, ID 33, which lists the key-specific 
algorithm IDs (see below) and key IDs of the possible signers of a ring 
signature.

3. A new registry of ring signature key-specific algorithm IDs with the 
following initial values:

     ID   Algorithm
     --   ---------
     1  - RSA signing
     2  - Schnorr signing
     3  - EC-Schnorr signing


1. Overview
===========

Ring signatures allow a signer to specify a set of possible signers 
without revealing who actually signed the message. The proposed scheme 
is compatible with existing RSA, DSA, and ECDSA keys. Furthermore, it is 
unconditionally signer-ambiguous: even if the private keys of all 
possible signers of a message are revealed, it remains impossible to 
determine which private key was used to sign the message.

The current OpenPGP specification lacks a straightforward way for Alice 
to send Bob an authenticated message that can only be verified by Bob. 
Right now, if such a signature is desired, the best that Alice can do is 
to send Bob a signed-then-encrypted message. Unfortunately, this means 
that Bob can show others the decrypted signature to prove to others that 
Alice signed the message. This ability of Bob to transfer Alice's 
signature to others is often undesirable from Alice's point of view.

Ring signatures provide an easy way for Alice to authenticate a message 
to Bob without concomitantly giving Bob the ability to transfer her 
signature. Alice simply creates a ring signature that specifies Alice 
and Bob as the possible signers of a message. Upon receipt of the 
message and ring signature, Bob is assured that the message is signed by 
Alice, but he cannot prove to others that Alice signed the message 
because Bob could have created the ring signature himself.

The scenario outlined above is typical of two-party email 
communications: when we communicate with someone by email, we often wish 
ensure the authenticity and privacy of our messages. Thus we sign and 
encrypt messages. However, we do not usually intend to grant our 
recipient the ability to authenticate our private messages to others. 
For such communications, I suggest that using ring signatures with 
encryption is an option that better reflects our intentions.

The proposed scheme closely follows Abe et al's scheme [AOS04], with 
small modifications made to better integrate with the current OpenPGP 
specification. Where possible, the notation and variable names in the 
following sections are the same as those in their paper.

Compatibility with DSA and ECDSA keys is achieved by using them as 
Schnorr and EC-Schnorr keys in the ring signature generation algorithm 
in Section 3. For now, I ignore ECDSA keys in following sections because 
I have not yet gone through the process of creating a ring signature 
using an ECDSA key to make sure that I comprehend RFC 6637. However, I 
believe that there are no issues with using ECDSA keys in a way 
analogous to the way that DSA keys are used in the proposed scheme.


2. Ring signature packet format
===============================

To create a ring signature, a V4 signature packet MUST be used, and V3 
signature packets MUST NOT be used. The public-key algorithm field MUST 
have the value 22 (0x16), which is a new algorithm type for ring signatures.

A signature subpacket of type 33 (0x21) MUST be present in the hashed 
subpacket data, and it SHOULD be placed ahead of any other hashed 
subpacket. This new subpacket type holds a list of pairs of key-specific 
algorithm ID and key ID of possible signers. The subpacket body is 
formed as the concatenation of the following 9-octet pairs:

     (1 octet algorithm ID, 8 octet key ID)

Each key ID is a possible signer of the ring signature, and the 
prepended algorithm ID specifies how the public key is used in the ring 
signature generation algorithm presented in Section 3. Currently, RSA 
keys MUST have a prepended algorithm ID value of 1 (indicating that they 
are to be used as RSA keys) and DSA keys MUST have a prepended algorithm 
ID value of 2 (indicating that they are to be used as Schnorr keys).

The 9-octet pairs SHOULD be ordered such that their key IDs appear in 
big-endian ascending order.

To illustrate the format of the subpacket body, suppose that we wish to 
create a ring signature with three possible signers, with two DSA key IDs:

     F2AD85AC1E42B367
     4F0540D577F95F95

And an RSA key ID:

     6B1947C7B5BAA022

The correct subpacket body here would be (spaces are inserted for 
readability only):

     02 4F0540D577F95F95  01 6B1947C7B5BAA022  02 F2AD85AC1E42B367

Once the hashed subpacket data has been prepared (it would be normal to 
include a signature creation time subpacket), a hash of the message to 
be signed is produced as specified in Section 5.2.4 of RFC 4880.

The algorithm-specific fields of a ring signature packet form a 
concatenated list of MPIs that are generated as prescribed in Section 3.


3. Ring signature generation
============================

The ring signature generation algorithm takes the hashed message and 
prepends a single octet containing the hash algorithm ID (identified in 
Section 9.4 of RFC 4880) of the hash function used (this is done to 
prevent length-extension shenanigans with hash functions based on the 
Merkle–Damgård construction). That is, given the hashed message m, we 
define:

     hm = hash_algorithm_id || m

To generate a ring signature, the actual signer must have available to 
them the public keys of all the possible signers, as well as the private 
key of one of the public keys.

Label the public keys from 1 to n in the same order as in the ring 
signature key-specific IDs and key IDs subpacket. Let k be the label of 
the public key for which the signer has the private key (so k is one of 
the integers from 1 to n).

For each public key, given its label i, use the following variable names 
for the unsigned integers that form the key material (the names are the 
same as those used in Section 5.5.2 of RFC 4880):

     if RSA(i):     (n_i, e_i)
     if Schnorr(i): (p_i, q_i, g_i, y_i)

For the private key (same as Section 5.5.3 of RFC 4880):

     if RSA(k):     (d_k, p_k, q_k, u_k)
     if Schnorr(k): (x_k)

Define the functions Random(n), MPI(n), and Hash() as follows.

Random(n) returns a uniformly random integer from 0 to n-1 inclusive.

MPI(n) returns a string of octets that is the unique MPI representation 
of the unsigned integer n, as defined in Section 3.2 of RFC 4880.

Hash() is the same hash function as that used to hash the message.

Now evaluate the following to generate the ring signature.

Initialize the ring signature:

     if RSA(k):
         r   = Random(n_k)
         a_k = r
     if Schnorr(k):
         r   = Random(q_k)
         a_k = g_k**r mod p_k

     c_(k+1) = Hash(hm || MPI(a_k))

For i = k+1, ..., n, 1, ..., k-1:

     if RSA(i):
         s_i = Random(n_i)
         a_i = (c_i + s_i**e_i) mod n_i
     if Schnorr(i):
         s_i = Random(q_i)
         a_i = (g_i**s_i * y_i**c_i) mod p_i

     c_(i+1) = Hash(hm || MPI(a_i))

Close the ring signature:

     if RSA(k):
         s_k = (r - c_k)**d_k mod n_k
     if Schnorr(k):
         s_k = (r - x_k*c_k) mod q_k

The ring signature output is a concatenated list of n+1 MPIs:

     MPI(c_1) || MPI(s_1) || MPI(s_2) || ... || MPI(s_n)

Note that in the degenerate case where n=1, the middle loop is skipped 
and the resulting signature is simply a randomized RSA signature or a 
standard Schnorr signature.


4. Ring signature verification
==============================

Given a message and a ring signature packet, the signature can be 
verified by following the same steps as in the signature generation to 
hash the message, then prepending the hash algorithm ID to get hm, then 
finally evaluating the following loop.

For i = 1, ..., n:

     if RSA(i):
         a_i = (c_i + s_i**e_i) mod n_i
     if Schnorr(i):
         a_i = (g_i**s_i * y_i**c_i) mod p_i

     c_(i+1) = Hash(hm || MPI(a_i))

Accept the signature if and only if the computed c_1 (i.e., c_(n+1)) is 
identical to the input c_1.


5. Notes for implementers
=========================

As outlined in the overview in Section 1, an intended use of ring 
signatures is to provide non-transferable authenticity in two-party 
communications. Ring signatures can be used for other purposes (see 
[RST06]). This proposal does not give a strict prescription for the 
usage of ring signatures, and decisions regarding the creation and 
interpretation of ring signatures is left to the implementation.

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. This is illustrated in Appendix A.


6. Summary
==========

In this message, I proposed an extension to RFC 4880 that adds support 
for ring signatures and provided specifications for the packet format 
and signature generation algorithm.

I would like to hear your comments on this proposal.

Vincent


Selected references
===================

For readers unfamiliar with ring signatures, I recommend first reading 
[RST06], then Sections 1–3 of [BSS02], then finally [AOS04].

[AOS04]
M. Abe, M. Ohkubo, and K. Suzuki (2004).
1-out-of-n signatures from a variety of keys.
https://v-yu.com/lib/2004_Abe,%20Ohkubo,%20Suzuki.pdf
This is a newer version of an earlier conference paper that was 
published at ASIACRYPT 2002.

[BSS02]
E. Bresson, J. Stern, and M. Szydlo (2002).
Threshold ring signatures and applications to ad-hoc groups.
https://www.di.ens.fr/~bresson/papers/BreSteSzy02_full.pdf
This is the full version of an extended abstract that was published at 
CRYPTO 2002.

[RST06]
R. L. Rivest, A. Shamir, and Y. Tauman (2006).
How to leak a secret: Theory and applications of ring signatures.
doi:10.1007/11685654_7
https://v-yu.com/lib/2006_Rivest,%20Shamir,%20Tauman.pdf
This is an updated version of an earlier conference paper that was 
published at ASIACRYPT 2001.


Appendix A. Example of a ring signature following the current proposal
======================================================================

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

This message is used to demonstrate a ring signature.
-----BEGIN PGP SIGNATURE-----

wsBFBAEWCAAjHCECTwVA1Xf5X5UBaxlHx7W6oCIC8q2FrB5Cs2cFAlLW2wcAAD9a
AP0Ra1gFBVBxgoeOxaTcujSOAMbgf6HLF4N1bb0OLHcseACdFcWeQO4kUeSaMuRh
qbmi6hzbZ64D+gImlNxP3/gKNF5QP445LZfjvVULr+H3WCZylP4GhEnieMas+X+s
XUDMAQSKL/O7qO+i1/k85yDWLod3Fv8ki3n4QF8N/wlzhuRHpT6Z4f0lZcdlA0be
DCa2bRBa3rriUt/yTtKVjpRKfHOkV+FLdWvWoYIs9mBTvgJ6MwfgKz4HAOC4Eo8+
MqWNgrr7Y8/byd8wQSmx3mTDHScc7oOP
=0Hrj
-----END PGP SIGNATURE-----

To demonstrate the proposed specification and to eliminate ambiguity, I 
have prepared the cleartext ring signature above. The signed message 
complies with the cleartext signature framework in Section 7 of RFC 
4880. The base64-encoded data contains a ring signature packet that 
follows the current proposal. Three key IDs are identified as the 
possible signers:

     4F0540D577F95F95 - Werner's DSA signing subkey.
     6B1947C7B5BAA022 - RSA signing key that I created for this occasion.
     F2AD85AC1E42B367 - Werner's DSA primary key.

Werner's public keys are available at:

     http://werner.eifelkommune.de/mykey.asc

The private key for 6B1947C7B5BAA022 is provided in Appendix B. This 
private key was used to create the ring signature.

The value of r used in the ring signature generation algorithm can be 
recovered from the signature, but let me provide it here anyway for your 
convenience in case you wish to reproduce an exact copy of the ring 
signature:

     r = 0x5202a86b534ac6e7680c3db32f1b409a8529d1e8d51baf648e9f0d
         9fc35bd8bc6b8327636666511566a5bd54a1f2c01d376ae6a38af39c
         bb3682a89604299c32c3843709124c4dd25a08c2a8ba8c8ad215337c
         951ed330444bccb04d4d74b75e3f0e6c04e168d2d93c903fddabc89d
         884082022fcc01eaa2be9e3b14ae909732

The following is an overview of the signature structure in hex:

C2 C045
New packet format holding a signature packet with data length 261.

04 01 16 08
V4 signature of canonical text document using a ring signature with SHA256.

0023
Length of hashed subpacket data: 35 octets.

1C 21 02 4F0540D577F95F95 01 6B1947C7B5BAA022 02 F2AD85AC1E42B367
28-octet hashed subpacket containing the ring signature key-specific 
algorithm IDs and key IDs.

05 02 52D6DB07
5-octet hashed subpacket containing the signature creation time.

0000
Length of unhashed subpacket data: 0 octets.

3F5A
2-octet field containing the leftmost 16 bits of the hashed message.

The remaining packet data is a concatenated list of four MPIs that form 
the ring signature, generated as prescribed in Section 3.


Appendix B. Private key for 6B1947C7B5BAA022
============================================

The following private key was used in the ring signature generation 
algorithm to create the ring signature displayed in Appendix A.

pub  1024R/6B1947C7B5BAA022  created: 2014-01-15  expires: never usage: SC
      Key fingerprint = 2AA7 1619 35F1 2D1D 2BA6  78B2 6B19 47C7 B5BA A022
uid                          This key is for testing only
-----BEGIN PGP PRIVATE KEY BLOCK-----
Version: GnuPG v2.0.20 (GNU/Linux)

lQHYBFLWxR8BBADVrNPuPADyr9Do3Ev4nObRWh8T8hM32A4+tI+lKxkiT7FPHnAy
HDGrsrA2nLYgKM0ulunWRMNKnNRVM9NcK9QNDXMvAE7xaIimGMislBQYVwoKQp6m
pa4uoddGBh1y/1E9QqL5FXO5cEuXsKYAmOvpZlkoM1+dil8qFE2aCxk7bQARAQAB
AAP/RYBaywHfeRDxDd0iJPK8LVp4A1/ZGm//aiwHET1shnmPfeGzssjy6xtLL+hX
YSyEWOQjmVtyfmF2u2QJGtDyvtf1mVAOzqMxIEdQYcYkKGgEUUwwwkylhj9h3A2Q
Ir95OFGZWiAqAvDwUhOZIsyU9hrSwqqZj7B33GJFqbQ0Oc0CAOXN7yVeI+C7WOPE
Maodt9nJaBVj4k943ltDZhfIKql8T8/eUsRQuR+NQYeiE2T1QM+E1SKh0fjy9wyg
f9CwETMCAO4INsS1ziq+3GMvVwMcSIp0MnwtZRMv4v4+tlme+rBC6QTjUxAhGj5t
JGg3mO0EHNQpdrp27/3Y2Sngt9/cwN8B+QEXEvYKpxBtPyDdyXVkS+cB2elS8yGF
qXdgUMb3ix5q6eWN/SlCXnU7AO5jEGwI3FR7vJPcCfoouAjaLZmY9RydbrQcVGhp
cyBrZXkgaXMgZm9yIHRlc3Rpbmcgb25seYi4BBMBAgAiBQJS1sUfAhsDBgsJCAcD
AgYVCAIJCgsEFgIDAQIeAQIXgAAKCRBrGUfHtbqgImOdBACwhoADhwKIZBh8wnDT
UGK6R2Dww9nwhUSMXXBWWPgxWDAIIbeh8HRiumeaHC/9B9apG1mKuJ6UVjho5bK/
RzST92eB0v7Yu+Xrhgq89KTGaA43I501jol+WbjxpaFmj4rWhUPWOkxq7PTAOCyW
T/FZ0tYoeBwVWMOlui2PlQyj1g==
=88Gm
-----END PGP PRIVATE KEY BLOCK-----