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

Vincent Yu <v@v-yu.com> Thu, 13 March 2014 21:03 UTC

Return-Path: <v@v-yu.com>

X-Original-To: openpgp@ietfa.amsl.com

Delivered-To: openpgp@ietfa.amsl.com

Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com
(Postfix) with ESMTP id 12BE61A075E for <openpgp@ietfa.amsl.com>;
Thu, 13 Mar 2014 14:03:27 -0700 (PDT)

X-Virus-Scanned: amavisd-new at amsl.com

X-Spam-Flag: NO

X-Spam-Score: 0.998

X-Spam-Level:

X-Spam-Status: No,
score=0.998 tagged_above=-999 required=5 tests=[BAYES_00=-1.9,
J_CHICKENPOX_42=0.6, MANGLED_TIME=2.3, RCVD_IN_DNSWL_NONE=-0.0001,
SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=no

Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com
[127.0.0.1]) (amavisd-new, port 10024) with ESMTP id tYzVvcWm1Cfv for
<openpgp@ietfa.amsl.com>; Thu, 13 Mar 2014 14:03:23 -0700 (PDT)

Received: from smtp2.hushmail.com (smtp2.hushmail.com [65.39.178.134]) by
ietfa.amsl.com (Postfix) with ESMTP id 246AD1A09E8 for <openpgp@ietf.org>;
Thu, 13 Mar 2014 14:03:22 -0700 (PDT)

Received: from smtp2.hushmail.com (localhost [127.0.0.1]) by
smtp2.hushmail.com (Postfix) with SMTP id 5EC6EA020F for <openpgp@ietf.org>;
Thu, 13 Mar 2014 21:03:16 +0000 (UTC)

Received: from smtp.hushmail.com (w5.hushmail.com [65.39.178.80]) (using
TLSv1.2 with cipher DHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client
certificate requested) by smtp2.hushmail.com (Postfix) with ESMTPS for
<openpgp@ietf.org>; Thu, 13 Mar 2014 21:03:16 +0000 (UTC)

Message-ID: <80674820640dbeb5ae81f81c67d87541@smtp.hushmail.com>

Date: Thu, 13 Mar 2014 17:03:13 -0400

From: Vincent Yu <v@v-yu.com>

User-Agent: Mozilla/5.0 (X11; Linux x86_64;
rv:24.0) Gecko/20100101 Thunderbird/24.3.0

MIME-Version: 1.0

To: openpgp@ietf.org

X-Enigmail-Version: 1.6

OpenPGP: id=d28d7c4078b3742a; url=https://v-yu.com/pubkeys/openpgp.asc

Content-Type: multipart/signed; micalg=pgp-sha512;
protocol="application/pgp-signature";
boundary="WWhgD7eSLjLc8NQ8uhxgD44Du9v1hbCRx"

Archived-At: http://mailarchive.ietf.org/arch/msg/openpgp/PZzHYqcGmYyOl2TDauDJeVEcukM

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

X-BeenThere: openpgp@ietf.org

X-Mailman-Version: 2.1.15

Precedence: list

List-Id: "Ongoing discussion of OpenPGP issues." <openpgp.ietf.org>

List-Unsubscribe: <https://www.ietf.org/mailman/options/openpgp>,
<mailto:openpgp-request@ietf.org?subject=unsubscribe>

List-Archive: <http://www.ietf.org/mail-archive/web/openpgp/>

List-Post: <mailto:openpgp@ietf.org>

List-Help: <mailto:openpgp-request@ietf.org?subject=help>

List-Subscribe: <https://www.ietf.org/mailman/listinfo/openpgp>,
<mailto:openpgp-request@ietf.org?subject=subscribe>

X-List-Received-Date: Thu, 13 Mar 2014 21:03:27 -0000

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

- [openpgp] Proposal for a separable ring signatu... Vincent Yu
- Re: [openpgp] Proposal for a separable ring sig... Daniel Kahn Gillmor
- Re: [openpgp] Proposal for a separable ring sig... Vincent Yu
- Re: [openpgp] Proposal for a separable ring sig... Jon Callas
- [openpgp] Non-SHA-1 fingerprints in signatures ... Vincent Yu
- Re: [openpgp] Non-SHA-1 fingerprints in signatu... Daniel Kahn Gillmor
- Re: [openpgp] Non-SHA-1 fingerprints in signatu... Vincent Yu
- Re: [openpgp] Non-SHA-1 fingerprints in signatu... David Shaw
- Re: [openpgp] Proposal for a separable ring sig... Werner Koch
- Re: [openpgp] Proposal for a separable ring sig... Vincent Yu
- Re: [openpgp] Non-SHA-1 fingerprints in signatu... Peter Pentchev
- Re: [openpgp] Non-SHA-1 fingerprints in signatu... Vincent Yu
- Re: [openpgp] Non-SHA-1 fingerprints in signatu... Daniel Kahn Gillmor
- Re: [openpgp] Proposal for a separable ring sig... Daniel Kahn Gillmor
- Re: [openpgp] Non-SHA-1 fingerprints in signatu... Peter Pentchev
- Re: [openpgp] Non-SHA-1 fingerprints in signatu... Jon Callas
- Re: [openpgp] Proposal for a separable ring sig... Werner Koch
- Re: [openpgp] Proposal for a separable ring sig... Daniel Kahn Gillmor
- Re: [openpgp] Proposal for a separable ring sig... Werner Koch
- Re: [openpgp] Proposal for a separable ring sig... Daniel Kahn Gillmor
- Re: [openpgp] Proposal for a separable ring sig... Werner Koch
- Re: [openpgp] Proposal for a separable ring sig... Vincent Yu
- Re: [openpgp] Proposal for a separable ring sig... Vincent Yu
- Re: [openpgp] Proposal for a separable ring sig... Daniel Kahn Gillmor
- Re: [openpgp] Proposal for a separable ring sig... Vincent Yu
- Re: [openpgp] Proposal for a separable ring sig... Ben Laurie
- Re: [openpgp] Proposal for a separable ring sig... Jon Callas
- Re: [openpgp] Proposal for a separable ring sig... Nicholas Cole
- Re: [openpgp] Proposal for a separable ring sig... Nicholas Cole
- Re: [openpgp] Proposal for a separable ring sig... Vincent Yu
- Re: [openpgp] Proposal for a separable ring sig... Nicholas Cole
- Re: [openpgp] Proposal for a separable ring sig... Vincent Yu
- Re: [openpgp] Proposal for a separable ring sig... vedaal
- Re: [openpgp] Proposal for a separable ring sig... Falcon Darkstar Momot
- Re: [openpgp] Proposal for a separable ring sig... Nicholas Cole
- Re: [openpgp] Proposal for a separable ring sig... ianG
- Re: [openpgp] Proposal for a separable ring sig... Jon Callas
- Re: [openpgp] Proposal for a separable ring sig... Werner Koch
- Re: [openpgp] Proposal for a separable ring sig... Werner Koch
- Re: [openpgp] Proposal for a separable ring sig... Ben Laurie
- Re: [openpgp] Proposal for a separable ring sig... Werner Koch
- Re: [openpgp] Proposal for a separable ring sig... Ben Laurie