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

From: Vincent Yu <[email-masked]>
Date: Thu, 13 Mar 2014 17:03:13 -0400

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

This message is used to demonstrate a ring 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

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Thu, 13 Mar 2014 17:11:47 -0400

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

a claim has already been made for public key algorithm ID 22 for EdDSA.

See:

  http://thread.gmane.org/gmane.ietf.openpgp/7419/focus=7421

I think it would be a mistake to force a collision here.

I haven't had a chance to review the meat of the proposal yet, but i
think proposals like are better off starting with an experimental public
key algorithm ID so that the discussion can be about the algorithm
itself and its use within OpenPGP, rather than opening up ID assignment
quibbling.

thanks for the proposal,

	--dkg

---

From: Vincent Yu <[email-masked]>
Date: Thu, 13 Mar 2014 17:25:24 -0400

> itself and its use within OpenPGP, rather than opening up ID assignment

Whoops. Thanks, that's a good point.

It's too late now for me to modify the example I gave in Appendix A, but 
if I create any more examples, I'll use experimental IDs instead of 22 
and 33.

Vincent

---

From: Jon Callas <[email-masked]>
Date: Thu, 13 Mar 2014 15:02:58 -0700

My suggestion is that you write up an I-D, and push it.

My quick read looks like this is a useful thing, and it would be nice to have. Just as Andrey pushed an ECC draft and there have been others, it'd be a great way to go.

As DKG noted, we have a constant collision, but that's not a big deal. That's why we have IANA.

	Jon

---

From: Vincent Yu <[email-masked]>
Date: Thu, 13 Mar 2014 21:28:15 -0400

> As DKG noted, we have a constant collision, but that's not a big deal. That's why we have IANA.

Thanks for your comments. I plan to write up and submit an I-D if no one 
points out egregious problems with the current proposal.

In past threads, there were discussions about supporting non-SHA-1 
fingerprints [1] and including full issuer fingerprints in signatures 
[2]. You forwarded to this list a proposal for a new fingerprint [3]. 
Did anything concrete come out of that proposal or other discussions?

In my proposal, I am using key IDs (i.e., the rightmost 8 octets of 
SHA-1 fingerprints) in a new signature subpacket, but I would like to 
switch to non-SHA-1 fingerprints if there is a standard or consensus 
about how they should be formatted. This is an opportune time to 
introduce such fingerprints since backward compatibility is not a 
relevant consideration.

Comments on this are welcome from everyone.

Vincent

[1]: https://www.ietf.org/mail-archive/web/openpgp/current/msg00253.html
[2]: https://www.ietf.org/mail-archive/web/openpgp/current/msg00405.html
[3]: https://www.ietf.org/mail-archive/web/openpgp/current/msg00259.html

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Thu, 13 Mar 2014 22:26:45 -0400

> introduce such fingerprints since backward compatibility is not a

the OpenPGP fingerprint revision discussions have not yet terminated in
a clear conclusion -- the last stage we reached was was "wait until
SHA-3 has settled down and then reconsider".

You should *not* use keyIDs as distinct identifiers in the subpacket
body of the ring signature design; the use of keyIDs in the traditional
issuer subpacket is a mistake that i hope we don't propagate if/when
OpenPGPv5 ever gets standardized.

Your I-D should have the subpacket body built from either OpenPGPv4
fingerprints, or full public key packets.  the search space for key IDs
is too small to distinguish "bad signature" from "i don't have the
appropriate key" with sufficient confidence, which causes all sorts of
nasty UI edge cases.

	--dkg

---

From: Vincent Yu <[email-masked]>
Date: Thu, 13 Mar 2014 22:39:31 -0400

> appropriate key" with sufficient confidence, which causes all sorts of

Thanks for the info. I will likely follow your suggestion and modify my 
proposal to use V4 fingerprints rather than key IDs.

Vincent

---

From: David Shaw <[email-masked]>
Date: Thu, 13 Mar 2014 22:40:21 -0400

On Mar 13, 2014, at 9:28 PM, Vincent Yu <[email-masked]> wrote:

> Thanks for your comments. I plan to write up and submit an I-D if no one points out egregious problems with the current proposal.
> 
> In past threads, there were discussions about supporting non-SHA-1 fingerprints [1] and including full issuer fingerprints in signatures [2]. You forwarded to this list a proposal for a new fingerprint [3]. Did anything concrete come out of that proposal or other discussions?
> 
> In my proposal, I am using key IDs (i.e., the rightmost 8 octets of SHA-1 fingerprints) in a new signature subpacket, but I would like to switch to non-SHA-1 fingerprints if there is a standard or consensus about how they should be formatted. This is an opportune time to introduce such fingerprints since backward compatibility is not a relevant consideration.

Changing fingerprints raises a lot of complexity that you may not want tied to your I-D.  I suspect that non-SHA-1 fingerprints will not happen without an accompanying V5 key format.

With regards to your I-D, I recommend using the full fingerprint instead of the 64-bit key ID in your sig subpacket.  That is the least ambiguous way to specify a key today, and while it is V4 specific, it can be easily changed if and when the fingerprint changes, just like the revocation key subpacket will need to be.

(Though see https://www.ietf.org/mail-archive/web/openpgp/current/msg00260.html )

David

---

From: Werner Koch <[email-masked]>
Date: Fri, 14 Mar 2014 10:50:14 +0100

Hi,

> following initial values:

Why do we need a new registry?  I can't see a problem in using the
existing public algorithms ids and declare that only certain algorithms
may be used for ring signatures (i.e. exclude the algo for a ring
signature).

I would also suggest to settle for ECC algorithms and not bother with
RSA or DSA anymore.  

>      (1 octet algorithm ID, 8 octet key ID)

Until a v5 public key packet format has been defined, I would strongly
suggest to use the full SHA-1 fingerprint instead of a key id.  Creating
long key id collisions is quite possible and thus would require extra
code for trial verification.

Salam-Shalom,

   Werner

-- 
Die Gedanken sind frei.  Ausnahmen regelt ein Bundesgesetz.

---

From: Vincent Yu <[email-masked]>
Date: Fri, 14 Mar 2014 09:55:02 -0400

On 03/14/2014 05:50 AM, Werner Koch wrote:
> may be used for ring signatures

This is a good point. I was worried that some people might object to 
having DSA keys being used as Schnorr keys, which is what's being done 
in the current proposal. The registry provides a way for a signer to 
state explicitly that this is intended, and provides some 
future-proofing in case a future extension to ring signatures uses DSA 
keys differently.

I anticipated potential objections because it is possible to modify or 
augment the proposal to use DSA keys in ways that more closely resemble 
DSA. The main alternative I considered is to use something like what Ren 
and Harn published in 2008 [RH08]. Their scheme provides a way to use 
ElGamal keys in a ring signature, and I think it can possibly be 
modified and integrated with Abe et al's scheme to use DSA keys directly 
as DSA keys. I didn't do so for the following reasons:

1. This alternative scheme produces signatures that are up to double the 
size of those from the current scheme.

2. Abe et al's scheme is much more widely read and cited (their paper 
has been cited more than 250 times, whereas Ren and Harn's paper has 
been cited less than 20 times). I'd prefer to stick to well-known schemes.

3. I had trouble parsing Ren and Harn's security proofs (but this could 
just be me being stupid).

But this is all beside the point since no one has actually objected so 
far. Looking back at my proposal, it does seem rather silly to have a 
registry that is currently redundant.

I agree with you that it is mostly useless. Unless someone has a better 
idea, I will remove the registry and modify the new signature subpacket 
to hold only the fingerprints of possible signers. This will nicely 
simplify things.

> (i.e. exclude the algo for a ring signature).
>

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 
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 
ECDSA signing key). I think this is an essential feature; otherwise, it 
would be a pain to make sure that all possible signers have the correct 
type of key.

Thus, I think it is important to have a new algorithm ID for ring 
signatures so that signers are free to mix together different types of 
keys in the ring signature. I would also prefer to leave RSA and DSA 
keys in the scheme for the same reason.

What ECC signing algorithms does the current development version of 
GnuPG support?

> code for trial verification.

Okay. dkg and David suggested similarly. I will modify my proposal to 
use full SHA-1 fingerprints.

Thanks!
Vincent

[RH08]
J. Ren and L. Harn (2008).
Generalized ring signatures.
doi:10.1109/TDSC.2008.22
https://v-yu.com/lib/2008_Ren,%20Harn.pdf

---

From: Peter Pentchev <[email-masked]>
Date: Fri, 14 Mar 2014 16:24:47 +0200

On Thu, Mar 13, 2014 at 10:39:31PM -0400, Vincent Yu wrote:
> Thanks for the info. I will likely follow your suggestion and modify
> my proposal to use V4 fingerprints rather than key IDs.

Hm, how exactly would this deal with the existence of multiple signing
subkeys, all associated with the same master public key?  Your current
proposal explicitly allows for that, using the key IDs; I guess there
might be a need to include *both* the fingerprint of the master key
*and* some kind of identification of the subkey actually used for
signing.

G'luck,
Peter

-- 
Peter Pentchev	[email-masked] [email-masked] [email-masked]
PGP key:	http://people.FreeBSD.org/~roam/roam.key.asc
Key fingerprint 2EE7 A7A5 17FC 124C F115  C354 651E EFB0 2527 DF13
I am jealous of the first word in this sentence.

---

From: Vincent Yu <[email-masked]>
Date: Fri, 14 Mar 2014 10:36:23 -0400

> *and* some kind of identification of the subkey actually used for

Isn't there a V4 fingerprint defined for every key, including for each 
subkey? I think it would be okay just to include the fingerprints of all 
possible signing keys, regardless of whether they are primary keys or 
subkeys.

If I've misunderstood something, please let me know.

Thanks,
Vincent

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Fri, 14 Mar 2014 10:37:46 -0400

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?

	--dkg

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Fri, 14 Mar 2014 10:38:37 -0400

> to hold only the fingerprints of possible signers. This will nicely

For extra safety, you could still include the public key's algorithm ID
in the subpacket as a separate one-byte marker, just using the value
from https://tools.ietf.org/html/rfc4880#section-9.1 instead of pulling
the values from a new/duplicate registry.

> keys in the scheme for the same reason.

i still haven't gotten my head around the particular details of the
proposed scheme, but i agree it would be nice for users to be able to
have this feature without requiring their peers to opt into the scheme
by making a new EC key or designating a new usage flag for this purpose.
 Sticking with widespread existing keys and the common "data signing"
usage flag seems like the way to go.

I note that you've specified the ring signature approach as a generic
public key algorithm for arbitrary signature packets, and left
"decisions regarding creation and interpretation" up to the
implementation.  I think a bit more guidance would be helpful in at
least two cases:

signature types: at the moment, i only see this as a useful mechanism
for data signatures (sigtype 0x00 and 0x01) ; i don't see a reasonable
use case here for identity certifications (sigtypes 0x10 through 0x13),
or other signature types currently available:
https://tools.ietf.org/html/rfc4880#section-5.2.1  -- i'm not suggesting
that we need to say these MUST NOT be made as ring signatures, but it
might be worth considering the applicability to the other signature types.

Guidance would also be useful for implementations processing (or
generating) ring signatures that were made by one of a set of keys where
some of those keys appear to be expired or revoked.  (i haven't thought
this use case through in sufficient detail, but i could see
implementations getting tripped up here or behaving in wildly divergent
ways if there is no clear guidance)

	--dkg

---

From: Peter Pentchev <[email-masked]>
Date: Fri, 14 Mar 2014 16:44:15 +0200

On Fri, Mar 14, 2014 at 10:36:23AM -0400, Vincent Yu wrote:
> Isn't there a V4 fingerprint defined for every key, including for
> each subkey? I think it would be okay just to include the
> fingerprints of all possible signing keys, regardless of whether
> they are primary keys or subkeys.
> 

Argh, sorry, stupid of me; of course you're right.  I was a bit misled
by the fact that GnuPG, by default, only outputs the fingerprint of the
primary key when --fingerprint is specified on the command line; I kind
of missed the part where --fingerprint may be given more than once and
it will output the fingerprints of all the subkeys.

G'luck,
Peter

-- 
Peter Pentchev	[email-masked] [email-masked] [email-masked]
PGP key:	http://people.FreeBSD.org/~roam/roam.key.asc
Key fingerprint 2EE7 A7A5 17FC 124C F115  C354 651E EFB0 2527 DF13
If the meanings of 'true' and 'false' were switched, then this sentence wouldn't be false.

---

From: Jon Callas <[email-masked]>
Date: Fri, 14 Mar 2014 09:40:28 -0700

> *and* some kind of identification of the subkey actually used for

Well, today, the KeyID is exactly that -- the identifier for a key. You have to backtrack from the signing key to its owner in your key database. There's nothing to stop me from using the same signing key in multiple masters. Despite any distress that may give, it can't be stopped, so we might as well embrace it.

	Jon

---

From: Werner Koch <[email-masked]>
Date: Fri, 14 Mar 2014 17:46:32 +0100

On Fri, 14 Mar 2014 14:55, [email-masked] 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

Old implementations won't be able to handle ring signatures at all.  To
use existing keys, users can simply use dedicated subkeys.

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

> signatures so that signers are free to mix together different types of

Agreed,

> What ECC signing algorithms does the current development version of

ECDSA.

EdDSA (Bernstein et al's Schnorr variant) will likely be added soon.

Shalom-Salam,

   Werner

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Fri, 14 Mar 2014 13:26:44 -0400

> software version is used.

I'm not sure i agree with this line of reasoning.  older keys can be
imported into newer software (i've done that multiple times).  if the
goal here is simply cryptographic non-repudiability, Alice's peer is
presumably trying to prove to a third-party judge that the peer didn't
make the signature, therefore Alice did.  But the peer cannot prove that
their key material has never been used with a different implementation
-- they can only assert that claim; but they could just as well assert
that they didn't make the signature in the first place.  Why should the
judge believe one claim over the other?

Put another way, i can produce a ring signature over a set of very
reasonable text that claims to be *from* a peer's public key and/or a
throwaway key, and introduce that as a piece of correspondence -- i
could even do this with the body of a message that the peer actually did
send to me, thereby "demonstrating" that the peer is capable of making
ring signatures.

it doesn't make sense to rely on non-cryptographic signals (e.g. typical
OpenPGP implemnetation version information, etc) to rule out possible
cryptographic signers.

	--dkg

---

From: Werner Koch <[email-masked]>
Date: Fri, 14 Mar 2014 18:37:39 +0100

> imported into newer software (i've done that multiple times).  if the

It is all about probability.

> goal here is simply cryptographic non-repudiability, Alice's peer is

There is no such thing as mechanically created non-reputability.  But
why make it too easy.

> OpenPGP implemnetation version information, etc) to rule out possible

I case we are speaking about this: The whole point of criminial
investigations is to collect lots of evidence from _different sources_
to prove or disprove a claim.

Salam-Shalom,

   Werner

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Fri, 14 Mar 2014 14:00:19 -0400

> to prove or disprove a claim.

sure, i'm not claiming that cryptographic deniability is a particularly
useful feature in the courts.  Even with the extra limits you're
proposing, i'm not convinced it has much utility, though.  I've written
about this here (slightly different context, but much of the reasoning
applies):

  https://www.debian-administration.org/users/dkg/weblog/104

Do you think that saying "ring signatures are limited to these
new-fangled keys" would make the arguments for deniability stronger?

if so, why does making the specification *possible* to use with older
keys make them any weaker?  That is, if the spec makes it possible to
work with multiple key types, two users exchanging ring signatures with
ECC keys will be no worse off than if the spec constrains its users to
only allow ECC keys.  But a user corresponding with someone who still
uses an RSA key has *no way* to make a ring signature under the
constrained proposal, thereby removing what little argument they could
have made otherwise.  Why not leave the proposal open to those users?

So perhaps some guidance is suggested, along the lines of "Due to the
novelty of this scheme within OpenPGP as of this writing, making a ring
signature over multiple ECC keys offers more plausible deniability than
a ring signature covering an ECC key and any other form of public key"

Is there another argument for constraining ring signatures to ECC keys,
though?  for example, arguments by implementation simplicity,
efficiency, or mathematical clarity might be a good reason to constrain
the spec to new key types.

	--dkg

---

From: Werner Koch <[email-masked]>
Date: Fri, 14 Mar 2014 19:47:08 +0100

> new-fangled keys" would make the arguments for deniability stronger?

No.

> a ring signature covering an ECC key and any other form of public key"

Well, by only allowing only the use of ECC keys, we would do the same
without having to write this down.

> though?  for example, arguments by implementation simplicity,

Implementation simplicity is always a valid argument.  To take this further I
would even suggest to make the use of EdDSA a MUST and and all other
algos a MAY.

Shalom-Salam,

   Werner

---

From: Vincent Yu <[email-masked]>
Date: Fri, 14 Mar 2014 18:30:51 -0400

> EdDSA (Bernstein et al's Schnorr variant) will likely be added soon.

Thanks.

Are there any other signature algorithms or schemes that are likely to 
appear within the next few years in either OpenPGP or GnuPG?

Right now, my understanding is that RSA, DSA, ECDSA, and EdDSA are the 
only signing keys / algorithms. Is this correct?

I only have specifications for RSA and DSA keys in the current proposal, 
but I think there is no issue augmenting the proposal to support ECDSA 
and EdDSA keys. If there other types of signing keys that are likely to 
appear, I would like to take a look to see whether they can be included 
successfully in the proposed ring signature scheme.

Vincent

---

From: Vincent Yu <[email-masked]>
Date: Fri, 14 Mar 2014 19:42:27 -0400

> the values from a new/duplicate registry.

I think I will simply remove the one-byte marker; it just seems like a 
bad idea for me to have added it in the first place. It doesn't seem to 
provide any security or practical benefit, since each public key already 
has a well-defined algorithm associated with it. If the verifier lacks 
one of the public keys, knowing the algorithm ID is not going to help 
them in any way.

> might be worth considering the applicability to the other signature types.

Yes, it sounds like a good idea to provide a bit more guidance for 
implementers. I agree that signatures of binary documents (0x00) and 
canonical text documents (0x01) are the intended targets of ring 
signatures, and I also don't see reasonable usage scenarios for other 
signature types. Perhaps I should add a short recommendation to fail all 
ring signatures with types other than 0x00 and 0x01. If the implementer 
thinks they have a genuine use for ring signatures with other types, 
they are still free to create them, but they should not expect other 
implementations to verify them.

> ways if there is no clear guidance)

I think a good general recommendation here would be to look at each 
public key individually and output the same warnings and errors that 
would be output if this were a standard signature. Are there significant 
issues that you see with this?

Vincent

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Sat, 15 Mar 2014 01:03:36 -0400

> issues that you see with this?

i'm just imagining a troubling use case in terms of UI (maybe it isn't
an issue):

 Alice and Bob have keys; Alice decides she wants to frame Bob.  Alice
makes a ring signature with her key and with Bob's key at time T over a
document that is particularly terrible.  She then sets her computer's
clock back to time T-1 and expires or revokes her own key.

Carol comes along and checks the signature on the terrible document.
her OpenPGP implementation says "this signature was made by either Alice
or Bob, but Alice's key was expired/revoked"

If Carol is naive, the implication she might take away from such a UI is
that Alice couldn't have made the signature, therefore it must have been
Bob that said the terrible thing.

I don't know how to clarify the UI to avoid giving that impression.

	--dkg

---

From: Vincent Yu <[email-masked]>
Date: Sat, 15 Mar 2014 01:26:34 -0400

> I don't know how to clarify the UI to avoid giving that impression.

Hm. Yes, scenarios like that sound like they can confuse the typical 
user and possibly lead to incorrect conclusions. It seems like it would 
be prudent for implementations to issue conspicuous errors when any 
aspect of a ring signature fails to verify, and to warn the user against 
drawing any conclusion other than the fact that the ring signature did 
not verify correctly.

But at the end of the day, the security of the scheme and the behavior 
of the implementation don't matter if users misuse them... A possibly 
more important thing to do is to provide easy-to-read references that 
users can look up. If ring signatures ever get implemented in GnuPG (or 
elsewhere), we should take care to write up clear and concise 
explanations for end users. (This is a difficult task.)

Vincent

---

From: Ben Laurie <[email-masked]>
Date: Sat, 15 Mar 2014 09:54:45 +0000

> It is all about probability.

So if I want to deny that I'm the one that made a ring signature, I
make sure I only use the new s/w for ring signatures. Then probability
says its not me, according to you.

---

From: Jon Callas <[email-masked]>
Date: Sat, 15 Mar 2014 10:47:10 -0700

> I don't know how to clarify the UI to avoid giving that impression.

I confess that I don't see it as an issue.

There's part of me that wants to say ironically, "Well, I guess we shouldn't do it, then!" But I don't want to be dismissive of your point.

But I would also say that a lot of what you're saying is just hard to do -- like revocation. Revocation doesn't work and *can't* work the way one might naively expect it. The situation you describe exists today in a slightly mutated form. Here's an example:

Bob is a politician and wants to repudiate a previous position he used to have, so he sets his clock back, revokes his own key and then claims that all the signatures made after that date come from his computer having been hacked back in the day.

It's really the same problem, just with a one-person variety. It boils down to the fact that revocation doesn't really work, beyond trivial cases.

Now on the other hand, ages ago, we discussed ring signatures, and a use case that I wanted to do was to make it so that whenever Alice sends Bob a signed email or other casual message, she would (could?) sign it with a ring signature of her key and Bob's. Bob knows that he didn't sign it so he knows that Alice did. 

Of course, it's one of those things that are cool, and yet it's hard to say what it actually does to improve anything.

	Jon

---

From: Nicholas Cole <[email-masked]>
Date: Sat, 15 Mar 2014 20:33:25 +0000

On Saturday, 15 March 2014, Jon Callas <[email-masked]> wrote:

> On Mar 14, 2014, at 10:03 PM, Daniel Kahn Gillmor <[email-masked]<javascript:;>>
> wrote:
>
> There's part of me that wants to say ironically, "Well, I guess we
> shouldn't do it, then!" But I don't want to be dismissive of your point.
>
> But I would also say that a lot of what you're saying is just hard to do
> -- like revocation. Revocation doesn't work and *can't* work the way one
> might naively expect it. The situation you describe exists today in a
> slightly mutated form. Here's an example:
>
> Bob is a politician and wants to repudiate a previous position he used to
> have, so he sets his clock back, revokes his own key and then claims that
> all the signatures made after that date come from his computer having been
> hacked back in the day.

That is an interesting 'attack' on your own key. Never rely on the date of
a revocakation signature is obvious when you think about it.  It does make
you wonder if signature packets like this should have dates at all.  They
make everything much more complicated in some ways...

It's really the same problem, just with a one-person variety. It boils down
> to the fact that revocation doesn't really work, beyond trivial cases.
>
> Now on the other hand, ages ago, we discussed ring signatures, and a use
> case that I wanted to do was to make it so that whenever Alice sends Bob a
> signed email or other casual message, she would (could?) sign it with a
> ring signature of her key and Bob's. Bob knows that he didn't sign it so he
> knows that Alice did.
>
> Of course, it's one of those things that are cool, and yet it's hard to
> say what it actually does to improve anything.
>

It also breaks the metaphor of a 'signature' too: the signatures we
currently have work in a very similar way to the ideal real-world
signature. This type of signature doesn't: it is a signature only specific
people can verify, or rather, a signature that could have been made by any
one of a number of people. The problem might then become proving you were
*not* the person who made it, rather than the person who did, and proving a
negative is impossible. I think for that reason I'm not sure would welcome
it being added to gpg.  "Yes, that is a signature that I could have made,
but I didn't" is not an easy position...

N.

---

From: Nicholas Cole <[email-masked]>
Date: Sat, 15 Mar 2014 20:40:27 +0000

On Sat, Mar 15, 2014 at 8:33 PM, Nicholas Cole <[email-masked]> wrote:
> That is an interesting 'attack' on your own key. Never rely on the date of a
> revocakation signature is obvious when you think about it.  It does make you
> wonder if signature packets like this should have dates at all.  They make
> everything much more complicated in some ways...
>
>
>> It's really the same problem, just with a one-person variety. It boils
>> down to the fact that revocation doesn't really work, beyond trivial cases.
>>
>> signed email or other casual message, she would (could?) sign it with a ring
>> signature of her key and Bob's. Bob knows that he didn't sign it so he knows
>> that Alice did.
>>
> currently have work in a very similar way to the ideal real-world signature.
> This type of signature doesn't: it is a signature only specific people can
> verify, or rather, a signature that could have been made by any one of a
> number of people. The problem might then become proving you were *not* the
> person who made it, rather than the person who did, and proving a negative
> is impossible. I think for that reason I'm not sure would welcome it being
> added to gpg.  "Yes, that is a signature that I could have made, but I
> didn't" is not an easy position...

And thinking about it even further, it compounds a problem that
someone (was it you, Jon?) has written about in the past.  Even though
we all know that key UIDs can be signed by complete strangers, users
are *often* disconcerted by this fact (which is why there is a
no-modifier flag, even if keyservers have never respected it and even
if it would make the use of OpenPGP even more complicated).  Still, a
naive user of an OpenPGP program may draw incorrect inferences about
social relationships from UID signatures.  Imagine the outcry of users
if they discovered that documents were in the wild that 'might' have
been signed by them...

N.

---

From: Vincent Yu <[email-masked]>
Date: Sat, 15 Mar 2014 17:40:32 -0400

> if they discovered that documents were in the wild that 'might' have

This reminds me that I used the name "signer-ambiguous signature" in 
some of the early drafts of my proposal. This name concisely describes 
the most important property of ring signatures. Now that I think about 
it, that is a much better name than "ring signature" for implementations 
to present to their end users.

"Signer-ambiguity" was coined by Rivest et al. to describe ring 
signatures in their seminal paper in 2001, so it's well-connected to the 
concept of ring signatures in the literature.

Unless there are severe objections, I will modify the proposal to use 
the phrase "signer-ambiguous signature" to refer generally to the 
signatures produced by the scheme, and use "ring signature" only as 
technical term for the specific scheme that was chosen to provide 
signer-ambiguity.

Vincent

---

From: Nicholas Cole <[email-masked]>
Date: Sat, 15 Mar 2014 22:02:21 +0000

On Saturday, 15 March 2014, Vincent Yu <[email-masked]> wrote:

>>>> ring
> This reminds me that I used the name "signer-ambiguous signature" in some
> of the early drafts of my proposal. This name concisely describes the most
> important property of ring signatures. Now that I think about it, that is a
> much better name than "ring signature" for implementations to present to
> their end users.
>
> "Signer-ambiguity" was coined by Rivest et al. to describe ring signatures
> in their seminal paper in 2001, so it's well-connected to the concept of
> ring signatures in the literature.
>
> Unless there are severe objections, I will modify the proposal to use the
> phrase "signer-ambiguous signature" to refer generally to the signatures
> produced by the scheme, and use "ring signature" only as technical term for
> the specific scheme that was chosen to provide signer-ambiguity.

I think that is a better name.  It gets away from the idea that there is a
'ring' of people who have authorized each other to make signatures.  But
still, I think that this proposal will bring more problems than benefits.
 Signatures will appear that 'might' have been made by all kinds of people
on all kinds of documents.  User interfaces will struggle to help users to
make good decisions as a result.  I can't help feeling that this kind of
signature belongs in very specific applications, and not in general purpose
tools. But I could be wrong.

N.

---

From: Vincent Yu <[email-masked]>
Date: Sat, 15 Mar 2014 22:28:14 -0400

On 03/15/2014 06:02 PM, Nicholas Cole wrote:
>
>
> On Saturday, 15 March 2014, Vincent Yu <[email-masked] <mailto:[email-masked]>>
> wrote:
>     some of the early drafts of my proposal. This name concisely
>     describes the most important property of ring signatures. Now that I
>     think about it, that is a much better name than "ring signature" for
>     implementations to present to their end users.
>
>     signatures in their seminal paper in 2001, so it's well-connected to
>     the concept of ring signatures in the literature.
>
>     Unless there are severe objections, I will modify the proposal to
>     use the phrase "signer-ambiguous signature" to refer generally to
>     the signatures produced by the scheme, and use "ring signature" only
>     as technical term for the specific scheme that was chosen to provide
>     signer-ambiguity.
>
>
> I think that is a better name.  It gets away from the idea that there is
> a 'ring' of people who have authorized each other to make signatures.
>   But still, I think that this proposal will bring more problems than
> benefits.  Signatures will appear that 'might' have been made by all
> kinds of people on all kinds of documents.  User interfaces will
> struggle to help users to make good decisions as a result.  I can't help
> feeling that this kind of signature belongs in very specific
> applications, and not in general purpose tools. But I could be wrong.

I share your concerns, but on the whole, I think it is a net positive to 
offer signers the option to create signer-ambiguous signatures. Let me 
go into more detail.

Within benign use cases, there are two sides to signer-ambiguous 
signatures: the recipient's side and the signer's side.

The recipient would generally prefer to receive standard signatures 
rather than signer-ambiguous signatures because standard signatures 
offer stronger guarantees and grant them the power to prove to others 
what they received. However, recipients would prefer to receive 
signer-ambiguous signatures rather than no signature. So from the 
recipient's perspective, signer-ambiguous signatures can be bad or good, 
depending on whether the alternative is a standard signature or no 
signature.

However, signer-ambiguous signatures are designed with the signer in 
mind. The signer would find signer-ambiguous signatures useful in 
situations where they wish to ensure authenticity without granting 
recipients the power to transfer their signatures (here, I am 
considering only two-party communications; there are potentially other 
applications of signer-ambiguous signatures). Signer-ambiguous 
signatures are always good from the signer's perspective, because they 
provide an extra option that they may choose to use.

Within malicious use cases, there is the attacker's side. At the end of 
the day, a new signature type will indeed create a potential attack 
vector, and it is hard to predict exactly what types of attack will 
become possible because the details will depend on the interactions 
between users and implementations.

It seems to me that your worries fall mainly within scenarios with an 
attacker. Without an attacker, there is little reason to worry about 
verifier confusion because the goals of signers coincide with those of 
recipients: signatures are a way for signers to provide a guarantee to 
recipients. If it turns out that recipients get excessively confused 
over signer-ambiguous signatures, then signers will simply decide not to 
use them. In the long run, signers will adapt and use signer-ambiguous 
signatures only when they judge that the benefits outweigh the potential 
confusion.

So we need only worry about the potential for verifier confusion in 
scenarios with an attacker. Here, I think implementations have a good 
response available if attacks grow rampant: they simply refuse to verify 
signer-ambiguous signatures. Without the cooperation of implementations, 
attackers can do no harm.

That is the worst case scenario. However, I consider it unlikely that 
attacks using signer-ambiguous signatures will ever become common enough 
to outweigh the benefits to signers. Perhaps our intuitions differ here.

The main point I wish to reemphasize is that signers are free not to 
create signer-ambiguous signatures if they think that the potential for 
confusion outweighs the benefits. Their goals are aligned with those of 
recipients.

Vincent

---

From: [email-masked]
Date: Sat, 15 Mar 2014 23:29:51 -0400

On 03/15/2014 at 1:47 PM, "Jon Callas" <[email-masked]> wrote:

>It's really the same problem, just with a one-person variety. It 
>boils down to the fact that revocation doesn't really work, beyond 
>trivial cases.
>
>Now on the other hand, ages ago, we discussed ring signatures, and 
>a use case that I wanted to do was to make it so that whenever 
>Alice sends Bob a signed email or other casual message, she would 
>(could?) sign it with a ring signature of her key and Bob's. Bob 
>knows that he didn't sign it so he knows that Alice did. 

But isn't it obvious that the key revocation is a scam, when the time of the revocation and the time of its receipt by a key-server, are too far apart?
(anything more than an hour should be suspicious.)

The only plausibility Alice may have, is that she couldn't get online soon enough after she revoked her key,
and this is discoverable if she went online for any other reason.

If there were some way to make the revocation process not be complete until received and verified by a keyserver,
and then listed as revoked as of the keyserver's receipt time,
then it might do away with the 'change the clock and revoke scam' and make revocation more workable.

vedaal

---

From: Falcon Darkstar Momot <[email-masked]>
Date: Sat, 15 Mar 2014 21:12:05 -0700

> then it might do away with the 'change the clock and revoke scam' and make revocation more workable.

Even assuming there were protocol support for this (please correct me if
in fact there is), you've also made a great leap in deciding to
effectively trust keyservers as timestamping authorities.

Keep in mind that this would require changes to the keyserver software;
SKS does not have any mechanism I am aware of to make such an assertion.

Bear also in mind when thinking about these two points that the
lamentable policy of refusing to ever purge data (save once) including
key vandalism, fraudulent keys, and similar abuse is traditionally
justified by a lack of time to implement support (or by revocation
persistence which is a separate issue) even for that.

Moreover, most public keyservers are run by volunteers on an at-will
basis, and synchronize with varying speeds.  Virtually anyone may
operate them and there is no standard or process for protecting their
security either individually or as a network.  Shall each of them keep
their own different timestamp for each piece of data?  Or shall they
trust each other's assertions as to timestamping?  Shall new keyservers
trust existing timestamps and is this different from the synchronization
process?

How shall you decide to trust timestamp data, and which copy of it to
trust, with respect to edge cases where a timestamp to be verified falls
within the delta between any two keyservers' receipt of the timestamped
information?  What happens when conflicting timestamps are asserted
between keyservers?

When a timestamp on data from a timestamping keyserver differs from the
timestamp in the signed packet (ie. revocation), what else will be
trusted?  Will the revocation be discarded as fraudulent?  If it is, can
you assume the key is compromised?  If validation succeeds (drift within
the threshold), will the timestamper's timestamp, or the timestamp in
the data be used?

Why is an hour the proper threshold for clock drift?  Is it even
appropriate to specify maximum drift in the standard?

What about keys which are exchanged without a mediating keyserver?  How
will the protocol work when data is not available?  How will existing
data without associated timestamps be treated?  What about offline
verification?

Does any problem arise if that data is arbitrarily timestamped with the
current time as of a keyserver software update?  What happens when
timestamp-less data is received during inter-keyserver synchronization?

There are other questions that need to be answered as well for such a
proposal to work.  However, in the signer-agnostic signatures draft this
surprisingly complex new logic would be pollution (and totally eclipse
the intent of the draft); perhaps you should consider making a proposal
of your own if you can answer those questions well.  The lack of a
useful mechanism for this and other timestamping is indeed a deficiency
and there would be some value in developing an appropriate scheme.

This has of course been discussed before to some extent (at least
https://www.ietf.org/mail-archive/web/openpgp/current/msg07136.html).

--Falcon Darkstar Momot

---

From: Nicholas Cole <[email-masked]>
Date: Sun, 16 Mar 2014 10:15:28 +0000

On Sunday, 16 March 2014, Vincent Yu <[email-masked]> wrote:

> offer signers the option to create signer-ambiguous signatures. Let me go
> into more detail.
>
> The recipient would generally prefer to receive standard signatures rather
> than signer-ambiguous signatures because standard signatures offer stronger
> guarantees and grant them the power to prove to others what they received.
> However, recipients would prefer to receive signer-ambiguous signatures
> rather than no signature. So from the recipient's perspective,
> signer-ambiguous signatures can be bad or good, depending on whether the
> alternative is a standard signature or no signature.
>
> However, signer-ambiguous signatures are designed with the signer in mind.
> The signer would find signer-ambiguous signatures useful in situations
> where they wish to ensure authenticity without granting recipients the
> power to transfer their signatures (here, I am considering only two-party
> communications; there are potentially other applications of
> signer-ambiguous signatures). Signer-ambiguous signatures are always good
> from the signer's perspective, because they provide an extra option that
> they may choose to use.
>
> the day, a new signature type will indeed create a potential attack vector,
> and it is hard to predict exactly what types of attack will become possible
> because the details will depend on the interactions between users and
> implementations.
>
> recipients. If it turns out that recipients get excessively confused over
> signer-ambiguous signatures, then signers will simply decide not to use
> them. In the long run, signers will adapt and use signer-ambiguous
> attacks using signer-ambiguous signatures will ever become common enough to
> outweigh the benefits to signers. Perhaps our intuitions differ here.
>

I understand the two use-cases you outline, and why from a signer's point
of view the scheme can make sense.  But the original paper that introduced
this scheme was called, "How to leak a secret". This is a scheme
deliberately designed to throw suspicion on to others, so I don't think I'm
being too pedantic in insisting on thinking about attackers. The scheme was
originally designed so that a staffer in a political organization could
leak data to a third party but create doubt about who had done it.

I suppose you could argue that we just have to hope that such tools would
be used responsibly, or even that such signatures could be created with key
material that is already available.

I suppose I just get uneasy about a signature scheme that is designed to
deliberately throw suspicion on to third parties.

Have there been any attacks on the scheme?

---

From: ianG <[email-masked]>
Date: Sun, 16 Mar 2014 11:55:46 +0000

> Now on the other hand, ages ago, we discussed ring signatures, and a use case that I wanted to do was to make it so that whenever Alice sends Bob a signed email or other casual message, she would (…

Which might be a nice property, but if it goes further it might be
problematic.  Where I'm thinking is experiences with the oddly-named
OTR, which raises questions on two counts.

Firstly, it isn't OTR because it is a protocol, not a record-keeping or
securing agent [0].

The protocol instead claims something that we might call "deniability"
as in "plausible deniability."

Which leads to fubar #2.  "Plausible deniability" might work in the
movies, but it doesn't work in court, being precisely the place were we
might want to be able to claim something didn't happen.  Unfortunately,
deniability is also the weapon the courts are most used to, and they
test for exactly this [1].  In short words, that's their game, and
they're daring you to try it...

Fubar #3 is that because of the claim of off-the-record and ability to
plausibly deny, the presence of the product itself can be evidence
against the victim.  If for example one were to "plausibly deny" a
record or transcript of a chat session, you're already damned by having
used the product.

> Of course, it's one of those things that are cool, and yet it's hard to say what it actually does to improve anything.

Which all is really sad, because other than that, the OTR protocol and
system has really filled a gap and been quite successful.  With the fall
of skype, it's about the only game out there for widespread secure chat.
 It's just the name and claims that run into unforeseen consequences.

Drifting more OT somewhat, what I think is far more useful is
disappearing messages.  I believe that Snapchat was on the money,
because it disappeared the messages & photos, which was much closer to
what the user needed.  Snapchat is a $16bn lesson to the cryptography
industry.

Anyway, I'm out west of Tahiti by now...

iang

[0] The name is less of relevance here, so in footnotes:  The record is
kept or not kept by the app.   It might be that this latter is useful
but what is not useful is advertising a property such as "off the
record" that the protocol cannot provide, and has no way of knowing if
the app provides it or not.

[1] For the exact same reason, non-repudiation is a concept that the
courts reject in general and in concept.  Oops.

---

From: Jon Callas <[email-masked]>
Date: Sun, 16 Mar 2014 13:47:10 -0700

> if they discovered that documents were in the wild that 'might' have

Yes, I'm probably the person. I created the no-modify and other properties of 2440 and 4880 precisely because it was something that I saw as a barrier to OpenPGP adoption and a personal peeve of mine. (Also, at an IETF meeting that happened to be on April First, I did an April Fools OpenPGP presentation where I presented the anti-identity signature, whereby if enough people over a threshold signed an anti-identity signature, you'd lose your identity and they could give it to someone else. That was also an expression of my peeve in this space.)

	Jon

---

From: Werner Koch <[email-masked]>
Date: Mon, 17 Mar 2014 08:23:50 +0100

> appear within the next few years in either OpenPGP or GnuPG?

We can't predicts the future.

> only signing keys / algorithms. Is this correct?

RSA and DSA are specified by RFC-4880.  ECDSA is specified by RFC-6637.
EdDSA ist not yet specified for OpenPGP (and unfortunately the work on
an RFC to describe this algo and other new curves has been deferred).

Shalom-Salam,

   Werner

---

From: Werner Koch <[email-masked]>
Date: Mon, 17 Mar 2014 08:25:42 +0100

> says its not me, according to you.

Right, you would decrease the probability that you created it.

Salam-Shalom,

   Werner

---

From: Ben Laurie <[email-masked]>
Date: Mon, 17 Mar 2014 07:43:42 +0000

> Right, you would decrease the probability that you created it.

Clearly not.

---

From: Werner Koch <[email-masked]>
Date: Mon, 17 Mar 2014 11:15:34 +0100

>> Right, you would decrease the probability that you created it.

I concur and you then disagree?

Salam-Shalom,

   Werner

---

From: Ben Laurie <[email-masked]>
Date: Mon, 17 Mar 2014 10:53:10 +0000

> I concur and you then disagree?

The probability I created it is 100%, right? That's exactly my point.

However, you propose a calculation that makes it _less_ likely that I
created than others did. Clearly this calculation is wrong.