Subject: [Cfrg] Internet-Draft: Collective Edwards-Curve Digital Signature Algorithm

From: Philipp Jovanovic <[email-masked]>
Date: Sat, 1 Jul 2017 23:58:47 +0200

Hi CFRG,

Here’s a first version of an Internet-Draft on “Collective Edwards-Curve Digital Signature Algorithms” based on Ed25519 and Ed448: https://datatracker.ietf.org/doc/draft-ford-cfrg-cosi/

We plan to give a short presentation on that topic at the next CFRG meeting in Prague.

Any feedback is more than welcome. Thanks!

All the best,
Philipp

---

From: Oleg Andreev <[email-masked]>
Date: Sun, 2 Jul 2017 23:47:28 +0300

Hi,

First of all: nice to see a simpler approach than a full SSSS-based threshold signing scheme!

After a quick glance at the spec, I have two security concerns:

1. It seems unsafe to add public keys directly (A = Sum[A_i]) without multiplying them by their hashes (A = Sum[Hash(A_i)*A_i]). Without that measure, it is possible to have A_j as a linear combination of other public keys. See this discussion for details: https://bitcointalk.org/index.php?topic=1377298.0

2. The signature does not commit to membership bitmask Z. Maybe it could be argued that signature is not malleable (especially with an improvement mentioned above), but to stay on safe side I think committing to the exact set of signers is a good idea.

Additionally, I'd suggest an improvement to the API. Since the scheme is not a SSSS scheme, verifier needs to reconstruct the exact key from the individual keys (4.3.5 Signature Verification). Current spec states that verifier should know the set of these member-keys upfront. It could be more practical to provide them as a part of the signature and commit into the aggregate public key, so the setup process looks as simple as non-aggregate one, or one using SSSS: just sharing a single aggregate public key.

This is how it could be done:

1. Organize all member keys in a merkle tree and compute it's root hash `h`.
2. Compute intermediate aggregate key as `A = Sum[Hash(A_i)*A_i]`.
3. Compute aggregate public key with commitment to the merkle tree: `P = Hash(A || h)*A`.
4. Signature will include:
    1) necessary member keys according to bitmask Z.
    2) merkle proof (necessary intermediate hashes needed to reconstruct the root hash).
    3) intermediate key A.
5. Verifier would reconstruct root hash h', compute `Hash(h' || A)*A` and verify it matches the P. Then it will reconstruct actual verification key `A' = A-T` and proceed with Schnorr protocol.

The member keys part of the signature could be optional, so the keys could be cached in case many signature from the same key are continuously verified.

Cheers,
Oleg.

> On 2 Jul 2017, at 00:58, Philipp Jovanovic <[email-masked]> wrote:
> 
> Hi CFRG,
> 
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg

---

From: Daniel Slamanig <[email-masked]>
Date: Mon, 3 Jul 2017 19:34:15 +0200

Hi Philipp,

looks interesting!

After looking at the protocol I also have some security concerns 
(related to what has been raised by Oleg in a previous mail).

Not committing to Z as well as the actual sum of signers public keys A' 
in the computation of the hash c for the signature seems to be problematic.

It seems to me that committing Z in the signature in plain as well as A' 
does not work given the later application of the signing procedure 
(where till the end of the protocol it is not clear who actually 
participates in the signing but c must be known at the beginning).

Committing to neither of both however seems problematic as it does not 
fix the set of actual signers.

This could be circumvented by allowing an honest leader to adapt the 
commitment to the final Z (and A') after it knows the signers without 
modifying the initially computed c using a chameleon hash (trapdoor 
commitment). I use P as a generator below, omit the brackets [a]P 
notation for scalar multiplication and write it from the perspective of 
the leader, i.e., the signer that initiates the protocol.

The leader could choose chameleon hash parameters sk_ch=y for random y 
and pk_ch=(P,Y=yP) and add pk_ch and chameleon hash CH(Z'):=h(Z')P+u'Y 
for randomly chosen u' to the computation of c, i.e., set 
c=H(R||A||pk_ch||CH(Z')||S), where h() is a collision resistant hash 
function (this is just the standard way of constructing a chameleon hash 
from DL for arbitrary message spaces as propsed in [1]). If Z' is not 
yet known one simply sets Z' to some fixed string at the beginning, 
e.g., Z':=0. At the end of the protocol, when the leader knows the exact 
signers, it can update Z' to the final value Z and use sk_ch to compute 
a collision in the chameleon hash, i.e., such that CH(Z)=CH(Z') by 
solving h(Z')+u'y = h(Z)+uy for u. He then adds u and Z as well as pk_ch 
to the signature, i.e., sets it as (R,s,u,Z,pk_ch) and discards sk_ch 
and u'. If Z is known beforehand, one simply computes the chameleon hash 
once and does not need to compute a collision. Clearly, the use of a 
chameleon hash allows to simply adapt to the actual set of signers 
representing Z without modifying c (with the knowledge of sk_ch - but it 
does not work without the knowledge of sk_ch). This would resolve the 
issue with the unknown Z at the time of signing.

Also, A is committed in the signature, but not the concrete A'=\sum A_i 
of keys used for computing the signature (I guess also due to the reason 
that one does not know the correct set of signers when computing the 
hash c). That can be problematic in a rogue key scenario in the current 
protocol, i.e., when not all signers need to prove knowledge of the 
secret key when they register their public keys but their public keys 
could be functions of other public keys (guess this could be a problem 
here). For instance, a malicious A^* could just take some key from A, 
say A_j, and compute and publish A^*=a^*A_j. And then given a collective 
signature (R,s,Z) where A_j participated, the signer can update s to s^* 
= s+a^*c as well as Z^* to exclude A_j and include A^* (as Z is not 
committed in the signature generation) and the signature (R,s^*,Z^*) 
will be a valid signature that certifies that A^* participated in 
signing - although he didn't.

If Z is committed as proposed above and it is checked during the 
verification, then this should no longer work. One could also adapt the 
hash c=H(R||pk_ch||CH(Z'||A)||S) to include a chameleon hash to 
CH(Z||A'), where A' is the real set of signers that participated in the 
signature generation and is adapted before finalizing the signature when 
known as above.

I hope that what I proposed is not just complete nonsense :) Also it 
produces quite a bit of an overhead. There may also be easier ways to 
avoid the issues.

Some editorial issues: the message to be signed is sometimes called a 
satement S and later then message msg. S could be confusing as part of 
the signature is s and your semantic is that scalars are lowercase and 
points are uppercase. Also in 4.2 "Signature Generation" steps 2 and 3 
are confusing as I guess that in the protocol all the signer compute 
their own [r_i]B values and R=\sum R_i instead of R=[r]B which would 
mean that they would send their r_i's (hope they will not do so).

Also I find it somewhat confusing that the bitmask Z identifies the 
non-signers with a bit set to 1. Why not identifying the signers with a 
bit set to 1?

Cheers,
Daniel

[1] Hugo Krawczyk, Tal Rabin: Chameleon Signatures. NDSS 2000

--
Dr. Daniel Slamanig
Institute for Applied Information Processing and Communications
Graz University of Technology
Inffeldgasse 16a, 8010 Graz, Austria.
Phone: +43 316 873 5509
http://www.iaik.tugraz.at

---

From: Bryan Ford <[email-masked]>
Date: Wed, 5 Jul 2017 12:28:14 +0200

Thanks everyone for your great comments so far on our collective signing draft.  More detailed responses to follow soon.

In the meantime, I just wanted to announce that we’ve moved the “source” for this Internet-Draft to this public GitHub repo:

	https://github.com/dedis/doc/tree/master/cosi <https://github.com/dedis/doc/tree/master/cosi>

…and we’re happy to take patch requests there for concrete textual fixes or suggestions anyone might like to propose.  However, let’s keep the main discussion here on the CFRG list.

Thanks
Bryan

> On Jul 1, 2017, at 11:58 PM, Philipp Jovanovic <[email-masked]> wrote:
> 
> Hi CFRG,
>

---

From: Bryan Ford <[email-masked]>
Date: Wed, 5 Jul 2017 14:26:11 +0200

Hi Oleg,

Thanks so much for your extremely constructive feedback.  Responding to your points inline...

> On Jul 2, 2017, at 10:47 PM, Oleg Andreev <[email-masked]> wrote:
> 

Definitely, we’d like to consider incorporating delinearization schemes like this if/when the WG adopts collective signing in some form as a working group item.  We’ve added an Issue on the GitHub repo holding the internet-draft specifically for this (https://github.com/dedis/doc/issues/1 <https://github.com/dedis/doc/issues/1>).

I seem to remember that this topic was already brought up on this list months (years?) ago in the Ed25519/Ed448 discussion leading up to RFC 8032, but delinearization mechanisms weren’t adopted at that point - perhaps in part simply because collective/aggregate signing wasn’t the focus of that work item.  I don’t remember all the details though - if anyone else has a clearer memory of exactly when that discussion occurred and can find pointers to the relevant parts of the CFRG mailing list archive, that would be great.

> 2. The signature does not commit to membership bitmask Z. Maybe it could be argued that signature is not malleable (especially with an improvement mentioned above), but to stay on safe side I think…

Indeed, we’ve considered this question, and included it as a specific “point for discussion” in section 9.2 of our initial Internet-Draft.  We also added an Issue to the draft’s GitHub repo to expand this list of discussion points and move it to an earlier, more prominent location in the draft (see https://github.com/dedis/doc/issues/2 <https://github.com/dedis/doc/issues/2>).

The clear potential benefit of including the bitmask in the hash is to strengthen the non-malleability of the collective signature.  Suppose, for example, I’m a member of a collective signing group and participated in creating a particular collective signature S, for which my bit in the bit mask is 1.  With the current (simple) formulation, I could take this signature S, and remove my “share" of it (which I can do because I know both my private key and my share of the private Schnorr commit) to produce a new “reduced” signature S’ without my share and with my bit in the bit mask set to 0.  The resulting modified signature S’ will be equally valid, just with one fewer cosigners represented (i.e., me).

From one perspective, this “attack” arguably shouldn’t be a problem in most cases because the new signature still correctly attests that all the (remaining) signers indeed signed the message, and if I try to disclaim ever having signed it at all, anyone who knows the original full signature S can just exhibit that as proof.  Any signature almost by definition can’t be taken as a claim that someone else *didn’t* sign a message - because they could have signed the same message in a completely separate, unrelated signing process.  Both the original signature S and the reduced signature S’ will need to be checked by any verifier against some policy anyway (e.g., a t-of-n threshold or a more complex policy), so my reduction S’ will at best make it less likely to satisfy whatever verification policy might be applied to it.

Nevertheless, there have certainly been instances in which unexpected or poorly-understood signature malleability properties have created security problems in practical systems using malleable signing schemes, so from a purist perspective of “any malleability is probably bad and should be eliminated”, it might be best to have the hash cover the bit mask purely out of an abundance of caution.

However, there’s another potential practical cost to enforcing this non-malleability: I believe it conflicts with any provisions we might want to make collective signing protocols “restart-proof” and prevent DoS attacks.  This is another issue to be discussed - for details see https://github.com/dedis/doc/issues/2 <https://github.com/dedis/doc/issues/2> and section IV.D of our CoSi paper (http://dedis.cs.yale.edu/dissent/papers/witness-abs).

In brief, any Schnorr collective signing protocol fundamentally must have two phases, “commit/challenge” and “response”.  If the commits and challenge depend on the exact bit mask of participating cosigners, then if any of those cosigners appeared to be online during the commit phase but then go offline (perhaps maliciously, deliberately at the “worst possible moment”) between the commit/challenge and response phases, then the only way for the protocol to complete is to restart from scratch without the “failed” cosigner.  If there are F colluding malicious cosigners in the group, then they can go offline one-by-one in this way, forcing up to F successive restarts, before the honest members of the cosigning group can successfully create a valid collective signature. This is of course a limited and potentially tolerable DoS attack, “only” O(N) in the group size, but still a consideration.

We have considered collective signing protocol variations that would eliminate this DoS vulnerability, by enabling the leader to continue the collective-signing process without restarting, even if only a subset of the cosigners present in the commit phase remain participants in the response phase.  Again, see section IV.D of our CoSi paper for details (http://dedis.cs.yale.edu/dissent/papers/witness-abs).  Of course such provisions add complexity to the protocol, and we’re not at all certain whether they’re worth the trouble, or if it’s better just to require restarts and tolerate the (limited) DoS vulnerability that restarting on cosigner failure creates.  So this is one of the particular “balance” issues I’d like to see discussed further in this group.

> The member keys part of the signature could be optional, so the keys could be cached in case many signature from the same key are continuously verified.

Yes, I think something along these lines is a good alternative to consider - in fact we suggested more-or-less exactly this approach in Section IV.B of our CoSi paper (http://dedis.cs.yale.edu/dissent/papers/witness-abs).

The upside of this variation is that verifiers need to know only the hash of the root of the Merkle “key tree” in order to verify collective signatures.  The downsides are (a) more complex signing and verification protocols needing Merkle trees and the like, (b) collective signatures themselves are no longer constant-size for a given cosigning group size, and (c) collective signatures may have much larger worst-case size due to the need to include one or more Merkle proofs for missing or present public keys - up to N/2 Merkle proofs in the worst case.  Again, these are important tradeoffs to be discussed.

Backing up for the moment, I think our first step is to establish whether there’s a critical-mass of interest within CFRG to adopt collective signing in some form as a working group item.  We offer our Internet-Draft as a starting point, but only a starting point, for such an effort if approved, and are happy to evolve it as needed as WG consensus hopefully emerges eventually around the above and other important design issues and tradeoffs that will need to be discussed.  I’m already happy to see that there seems to be significant interest, at least, based on the responses so far.

Thanks
Bryan

---

From: Bryan Ford <[email-masked]>
Date: Wed, 5 Jul 2017 15:11:36 +0200

Hi Daniel, thanks for your thoughts on the commitment-to-the-bitmask issue.

Your proposal of using a chameleon hash, to allow the leader to “adjust” the bit mask after the commit c has been established, is an interesting idea. However, if I understand it correctly, if the leader holds the trapdoor key for the chameleon hash, wouldn’t that still make the final collective signature malleable for the leader (or for anyone the leader’s trapdoor key might leak to)?  The CoSi protocol as currently defined is intended to ensure that the leader has no special privilege or trust with respect to other cosigners: i.e., the leader is merely an ordinary participant, but is simply the one who for whatever reason decides to initiate the cosigning operation.  Giving the leader special powers - e.g., making the signature malleable to the leader but not to others - would break this principle and need to be extremely carefully considered I think.

To follow up on my last message to Oleg, again I suggest reading section IV of our CoSi paper from IEEE S&P last year (http://dedis.cs.yale.edu/dissent/papers/witness-abs <http://dedis.cs.yale.edu/dissent/papers/witness-abs>), as it discusses several related issues, especially the potential desire to allow the leader to complete a collective signing procedure even with only a subset of “committed” participants remaining present in the “response” phase.  In particular, the leader can form all the individual Schnorr commits into a Merkle tree, and make the real commit c be the root of that Merkle tree.  In this way, the leader is committing not so much to a particular collective Schnorr commit but rather to *all possible* Schnorr commits that can be composed from any subset of the individual Schnorr commits within that Merkle tree.  This way, if some of the participants whose commits are present in that Merkle tree remain available during the response phase but others drop out, the leader can still use the commit c and form a correct and verifiable collective signature against the particular subset of Schnorr commits from nodes that remained available throughout the process, without restarting.

I guess this approach does, in a slightly different way, make the resulting collective signatures slightly malleable to the leader: from a given set of commit-time and response-time information, the leader could put together distinct collective signatures representing different subsets of response-time participants.  Some form of “leader-malleability” of this kind seems unavoidably essential to enabling the leader to complete a collective signing round in the presence of partial failures without restarting.  Perhaps the same limited leader-malleability is more-or-less the same property your suggestion of using chameleon hashes has, although I haven’t had a chance to compare them deeply yet.

But at any rate, the higher-level tradeoff here to consider is whether it’s better to (a) enforce strict non-malleability of collective signatures (by anyone, leader included), at the cost of O(N)-round DoS attack vulnerability during signing due to the need to restart partially failed rounds, or (b) provide some limited form of limited leader-malleability in order to support restart-free operation and avoid DoS attacks during signing, at the cost of a more complex protocol (and perhaps slightly more “special” trust in the leader than we might like).

Again, further thoughts on this and other topics are most welcome.

Thanks
Bryan

> On Jul 3, 2017, at 7:34 PM, Daniel Slamanig <[email-masked]> wrote:
> 
> Hi Philipp,
> 
> looks interesting!
> 
> After looking at the protocol I also have some security concerns (related to what has been raised by Oleg in a previous mail).
> 
> Not committing to Z as well as the actual sum of signers public keys A' in the computation of the hash c for the signature seems to be problematic.
> 
> It seems to me that committing Z in the signature in plain as well as A' does not work given the later application of the signing procedure (where till the end of the protocol it is not clear who actually participates in the signing but c must be known at the beginning).
> 
> Committing to neither of both however seems problematic as it does not fix the set of actual signers.
> 
> This could be circumvented by allowing an honest leader to adapt the commitment to the final Z (and A') after it knows the signers without modifying the initially computed c using a chameleon hash (trapdoor commitment). I use P as a generator below, omit the brackets [a]P notation for scalar multiplication and write it from the perspective of the leader, i.e., the signer that initiates the protocol.
> 
> The leader could choose chameleon hash parameters sk_ch=y for random y and pk_ch=(P,Y=yP) and add pk_ch and chameleon hash CH(Z'):=h(Z')P+u'Y for randomly chosen u' to the computation of c, i.e., set c=H(R||A||pk_ch||CH(Z')||S), where h() is a collision resistant hash function (this is just the standard way of constructing a chameleon hash from DL for arbitrary message spaces as propsed in [1]). If Z' is not yet known one simply sets Z' to some fixed string at the beginning, e.g., Z':=0. At the end of the protocol, when the leader knows the exact signers, it can update Z' to the final value Z and use sk_ch to compute a collision in the chameleon hash, i.e., such that CH(Z)=CH(Z') by solving h(Z')+u'y = h(Z)+uy for u. He then adds u and Z as well as pk_ch to the signature, i.e., sets it as (R,s,u,Z,pk_ch) and discards sk_ch and u'. If Z is known beforehand, one simply computes the chameleon hash once and does not need to compute a collision. Clearly, the use of a chameleon hash allows to simply adapt to the actual set of signers representing Z without modifying c (with the knowledge of sk_ch - but it does not work without the knowledge of sk_ch). This would resolve the issue with the unknown Z at the time of signing.
> 
> Also, A is committed in the signature, but not the concrete A'=\sum A_i of keys used for computing the signature (I guess also due to the reason that one does not know the correct set of signers when computing the hash c). That can be problematic in a rogue key scenario in the current protocol, i.e., when not all signers need to prove knowledge of the secret key when they register their public keys but their public keys could be functions of other public keys (guess this could be a problem here). For instance, a malicious A^* could just take some key from A, say A_j, and compute and publish A^*=a^*A_j. And then given a collective signature (R,s,Z) where A_j participated, the signer can update s to s^* = s+a^*c as well as Z^* to exclude A_j and include A^* (as Z is not committed in the signature generation) and the signature (R,s^*,Z^*) will be a valid signature that certifies that A^* participated in signing - although he didn't.
> 
> If Z is committed as proposed above and it is checked during the verification, then this should no longer work. One could also adapt the hash c=H(R||pk_ch||CH(Z'||A)||S) to include a chameleon hash to CH(Z||A'), where A' is the real set of signers that participated in the signature generation and is adapted before finalizing the signature when known as above.
> 
> I hope that what I proposed is not just complete nonsense :) Also it produces quite a bit of an overhead. There may also be easier ways to avoid the issues.
> 
> Some editorial issues: the message to be signed is sometimes called a satement S and later then message msg. S could be confusing as part of the signature is s and your semantic is that scalars are lowercase and points are uppercase. Also in 4.2 "Signature Generation" steps 2 and 3 are confusing as I guess that in the protocol all the signer compute their own [r_i]B values and R=\sum R_i instead of R=[r]B which would mean that they would send their r_i's (hope they will not do so).
> 
> Also I find it somewhat confusing that the bitmask Z identifies the non-signers with a bit set to 1. Why not identifying the signers with a bit set to 1?
> 
> Cheers,
> Daniel
> 
>

---

From: Thomas Garcia <[email-masked]>
Date: Wed, 5 Jul 2017 14:27:00 +0100

Hello,
I have a number of comments regarding the draft.
1. In the described protocol the leader, after receiving commitments from
the participants and calculating the challenge c, sends that challenge to
the participants. The participants then do not verify that c was indeed
calculated using the message that they intended to sign, allowing the
leader to procure signatures for arbitrary messages. A stage of
verification of c should be added to the protocol.
2. EdDSA is designed to withstand collision attacks against the hash
function used in the signature. On the other hand, the protocol suggested
is susceptible to such attacks. A hostile leader and participant, together,
could wait for all other participants to select their commitments. They
could then choose a commitment such that
SHA512(R||A||msg)=SHA512(R'||A||msg'), providing them with a signature of
msg'. This would of course have to be done in real-time, and given the
strength of SHA512 is in no way practical. This kind of attack would be
difficult to avoid without substantial modifications to the scheme, but
this does not seem to be a significant threat.

Thomas G.

On Wed, Jul 5, 2017 at 2:11 PM, Bryan Ford <[email-masked]> wrote:

> Your proposal of using a chameleon hash, to allow the leader to “adjust”
> the bit mask after the commit c has been established, is an interesting
> idea. However, if I understand it correctly, if the leader holds the
> trapdoor key for the chameleon hash, wouldn’t that still make the final
> collective signature malleable for the leader (or for anyone the leader’s
> trapdoor key might leak to)?  The CoSi protocol as currently defined is
> intended to ensure that the leader has no special privilege or trust with
> respect to other cosigners: i.e., the leader is merely an ordinary
> participant, but is simply the one who for whatever reason decides to
> initiate the cosigning operation.  Giving the leader special powers - e.g.,
> making the signature malleable to the leader but not to others - would
> break this principle and need to be extremely carefully considered I think.
>
> To follow up on my last message to Oleg, again I suggest reading section
> IV of our CoSi paper from IEEE S&P last year (http://dedis.cs.yale.edu/
> dissent/papers/witness-abs), as it discusses several related issues,
> especially the potential desire to allow the leader to complete a
> collective signing procedure even with only a subset of “committed”
> participants remaining present in the “response” phase.  In particular, the
> leader can form all the individual Schnorr commits into a Merkle tree, and
> make the real commit c be the root of that Merkle tree.  In this way, the
> leader is committing not so much to a particular collective Schnorr commit
> but rather to *all possible* Schnorr commits that can be composed from any
> subset of the individual Schnorr commits within that Merkle tree.  This
> way, if some of the participants whose commits are present in that Merkle
> tree remain available during the response phase but others drop out, the
> leader can still use the commit c and form a correct and verifiable
> collective signature against the particular subset of Schnorr commits from
> nodes that remained available throughout the process, without restarting.
>
> I guess this approach does, in a slightly different way, make the
> resulting collective signatures slightly malleable to the leader: from a
> given set of commit-time and response-time information, the leader could
> put together distinct collective signatures representing different subsets
> of response-time participants.  Some form of “leader-malleability” of this
> kind seems unavoidably essential to enabling the leader to complete a
> collective signing round in the presence of partial failures without
> restarting.  Perhaps the same limited leader-malleability is more-or-less
> the same property your suggestion of using chameleon hashes has, although I
> haven’t had a chance to compare them deeply yet.
>
> But at any rate, the higher-level tradeoff here to consider is whether
> it’s better to (a) enforce strict non-malleability of collective signatures
> (by anyone, leader included), at the cost of O(N)-round DoS attack
> vulnerability during signing due to the need to restart partially failed
> rounds, or (b) provide some limited form of limited leader-malleability in
> order to support restart-free operation and avoid DoS attacks during
> signing, at the cost of a more complex protocol (and perhaps slightly more
> “special” trust in the leader than we might like).
>
> After looking at the protocol I also have some security concerns (related
> to what has been raised by Oleg in a previous mail).
>
> Not committing to Z as well as the actual sum of signers public keys A' in
> the computation of the hash c for the signature seems to be problematic.
>
> does not work given the later application of the signing procedure (where
> till the end of the protocol it is not clear who actually participates in
> the signing but c must be known at the beginning).
>
> commitment). I use P as a generator below, omit the brackets [a]P notation
> for scalar multiplication and write it from the perspective of the leader,
> i.e., the signer that initiates the protocol.
>
> The leader could choose chameleon hash parameters sk_ch=y for random y and
> pk_ch=(P,Y=yP) and add pk_ch and chameleon hash CH(Z'):=h(Z')P+u'Y for
> randomly chosen u' to the computation of c, i.e., set
> from DL for arbitrary message spaces as propsed in [1]). If Z' is not yet
> known one simply sets Z' to some fixed string at the beginning, e.g.,
> Z':=0. At the end of the protocol, when the leader knows the exact signers,
> it can update Z' to the final value Z and use sk_ch to compute a collision
> in the chameleon hash, i.e., such that CH(Z)=CH(Z') by solving h(Z')+u'y =
> h(Z)+uy for u. He then adds u and Z as well as pk_ch to the signature,
> i.e., sets it as (R,s,u,Z,pk_ch) and discards sk_ch and u'. If Z is known
> beforehand, one simply computes the chameleon hash once and does not need
> to compute a collision. Clearly, the use of a chameleon hash allows to
> simply adapt to the actual set of signers representing Z without modifying
> c (with the knowledge of sk_ch - but it does not work without the knowledge
> of sk_ch). This would resolve the issue with the unknown Z at the time of
> signing.
>
> Also, A is committed in the signature, but not the concrete A'=\sum A_i of
> keys used for computing the signature (I guess also due to the reason that
> one does not know the correct set of signers when computing the hash c).
> That can be problematic in a rogue key scenario in the current protocol,
> i.e., when not all signers need to prove knowledge of the secret key when
> they register their public keys but their public keys could be functions of
> other public keys (guess this could be a problem here). For instance, a
> malicious A^* could just take some key from A, say A_j, and compute and
> publish A^*=a^*A_j. And then given a collective signature (R,s,Z) where A_j
> participated, the signer can update s to s^* = s+a^*c as well as Z^* to
> exclude A_j and include A^* (as Z is not committed in the signature
> generation) and the signature (R,s^*,Z^*) will be a valid signature that
> certifies that A^* participated in signing - although he didn't.
>
> hash c=H(R||pk_ch||CH(Z'||A)||S) to include a chameleon hash to CH(Z||A'),
> where A' is the real set of signers that participated in the signature
> generation and is adapted before finalizing the signature when known as
> above.
>
> produces quite a bit of an overhead. There may also be easier ways to avoid
> the issues.
>
> satement S and later then message msg. S could be confusing as part of the
> signature is s and your semantic is that scalars are lowercase and points
> are uppercase. Also in 4.2 "Signature Generation" steps 2 and 3 are
> confusing as I guess that in the protocol all the signer compute their own
> [r_i]B values and R=\sum R_i instead of R=[r]B which would mean that they
> would send their r_i's (hope they will not do so).
>
> non-signers with a bit set to 1. Why not identifying the signers with a bit
> set to 1?
>
> Cheers,
> Daniel
>
>
> Here’s a first version of an Internet-Draft on “Collective Edwards-Curve
> Digital Signature Algorithms” based on Ed25519 and Ed448:
> https://datatracker.ietf.org/doc/draft-ford-cfrg-cosi/
> Phone: +43 316 873 5509 <+43%20316%208735509>

---

From: Bryan Ford <[email-masked]>
Date: Wed, 5 Jul 2017 18:29:23 +0200

Hi Thomas,

> On Jul 5, 2017, at 3:27 PM, Thomas Garcia <[email-masked]> wrote:
> 
> Hello,
> 1. In the described protocol the leader, after receiving commitments from the participants and calculating the challenge c, sends that challenge to the participants. The participants then do not verify that c was indeed calculated using the message that they intended to sign, allowing the leader to procure signatures for arbitrary messages. A stage of verification of c should be added to the protocol.

Oops, looks like that was an unfortunate omission that snuck into the first draft somehow.  Indeed, the cosigners definitely must not simply trust the leader to compute c correctly.  What section 5.1.3 should say is that the leader sends out the aggregate commitment R, which all participants use to compute c = SHA512(R || A || M) independently based on that R, ensuring that the responses they produced are only good for a particular message M they’ve seen and approved.  (And the hash might of course be further extended to cover additional information, such as the bit mask, depending on the outcome of other orthogonal discussions raised by others.)  We’ll make sure that fix gets into the next version of the spec - thanks for pointing out the bug.

> 2. EdDSA is designed to withstand collision attacks against the hash function used in the signature. On the other hand, the protocol suggested is susceptible to such attacks. A hostile leader and participant, together, could wait for all other participants to select their commitments. They could then choose a commitment such that SHA512(R||A||msg)=SHA512(R'||A||msg'), providing them with a signature of msg'. This would of course have to be done in real-time, and given the strength of SHA512 is in no way practical. This kind of attack would be difficult to avoid without substantial modifications to the scheme, but this does not seem to be a significant threat.

Nice observation, thanks.  Agreed, it’s not clear that there’s a straightforward way to protect against such attacks in the event the hash function has collision weaknesses - but hopefully SHA512 will be strong enough for long enough that this shouldn’t be an issue in practice.

Cheers
Bryan

> Thomas G.
> 
> On Wed, Jul 5, 2017 at 2:11 PM, Bryan Ford <[email-masked] <mailto:[email-masked]>> wrote:
>> On Jul 3, 2017, at 7:34 PM, Daniel Slamanig <[email-masked] <mailto:[email-masked]>> wrote:
>> 
>> Hi Philipp,
>> 
>> looks interesting!
>> 
>>> Here’s a first version of an Internet-Draft on “Collective Edwards-Curve Digital Signature Algorithms” based on Ed25519 and Ed448: https://datatracker.ietf.org/doc/draft-ford-cfrg-cosi/ <https://datatracker.ietf.org/doc/draft-ford-cfrg-cosi/>
>>> [email-masked] <mailto:[email-masked]>
>>> https://www.irtf.org/mailman/listinfo/cfrg <https://www.irtf.org/mailman/listinfo/cfrg>
>> 
>> 
>> --
>> Dr. Daniel Slamanig
>> Phone: +43 316 873 5509 <tel:+43%20316%208735509>
>> http://www.iaik.tugraz.at <http://www.iaik.tugraz.at/>
>> 
>> [email-masked] <mailto:[email-masked]>
>> https://www.irtf.org/mailman/listinfo/cfrg <https://www.irtf.org/mailman/listinfo/cfrg>
> 
> 
> [email-masked] <mailto:[email-masked]>
> https://www.irtf.org/mailman/listinfo/cfrg <https://www.irtf.org/mailman/listinfo/cfrg>
> 
>

---

From: Daniel Slamanig <[email-masked]>
Date: Thu, 6 Jul 2017 10:34:36 +0200

Hi Bryan,

thank you very much for your detailed comments. I have to admit that I 
was not aware of the S&P paper before reading the draft and so I 
somewhat missed the big picture and simply "analyzed" the collective 
signing as described in the draft without specific context.

You are correct in that with a chameleon hash (CH) the leader needs to 
be somehow trusted (it however does not seem to me that the leader has 
more power than producing invalid signatures by messing up with the CH - 
which would work in any case - but I guess one needs to evaluate that in 
a bit more details). Moreover, in such a CH approach the leader must be 
involved in the final step of the signature generation. It seems to me 
that this is not the case in your approach as everyone could complete 
the multi-signature. Clearly, the CH approach is much more susceptible 
to DoS attacks.

Another observation regarding committing to the bitmask Z. If you do not 
commit to the bitmask Z, then users could cooperate in setting up their 
public keys, lets say A_i and A_j cooperate. Then one of them could take 
part in the signing, but in the end one could use the attack with the 
rogue keys outlined in my initial mail so that A_j can claim that he 
took part in the signing process although A_i actually took part. As far 
as I see not even using a delinearization scheme would help here. 
Nevertheless, it seems to me that this is not a valid attack vector when 
I look at the paper (but as you do not formally specify a security model 
for your approach in the paper this is hard to tell). Note that such an 
attack would even work if users have to register the public keys and 
prove that they know the secret key corresponding to the public key, 
e.g., via a (NI)ZK proof of the secret key - which I have seen is 
mentioned in the paper, but not discussed in the draft. Summing up, 
without commiting to Z in the signature, you would trivially not be able 
to achieve strong EUF-CMA security of the multi-signature due to the 
malleability, but as far as I see standard EUF-CMA should still hold 
(which seems sufficient for your application).

Thanks and cheers,
Daniel

On 05.07.2017 15:11, Bryan Ford wrote:
> collective signature malleable for the leader (or for anyone the 
> leader’s trapdoor key might leak to)?  The CoSi protocol as currently 
> defined is intended to ensure that the leader has no special privilege 
> or trust with respect to other cosigners: i.e., the leader is merely an 
> ordinary participant, but is simply the one who for whatever reason 
> decides to initiate the cosigning operation.  Giving the leader special 
> powers - e.g., making the signature malleable to the leader but not to 
> others - would break this principle and need to be extremely carefully 
> considered I think.
> 
> IV of our CoSi paper from IEEE S&P last year 
> (http://dedis.cs.yale.edu/dissent/papers/witness-abs), as it discusses 
> several related issues, especially the potential desire to allow the 
> leader to complete a collective signing procedure even with only a 
> subset of “committed” participants remaining present in the “response” 
> phase.  In particular, the leader can form all the individual Schnorr 
> commits into a Merkle tree, and make the real commit c be the root of 
> that Merkle tree.  In this way, the leader is committing not so much to 
> a particular collective Schnorr commit but rather to *all possible* 
> Schnorr commits that can be composed from any subset of the individual 
> Schnorr commits within that Merkle tree.  This way, if some of the 
> participants whose commits are present in that Merkle tree remain 
> available during the response phase but others drop out, the leader can 
> still use the commit c and form a correct and verifiable collective 
> signature against the particular subset of Schnorr commits from nodes 
> that remained available throughout the process, without restarting.
> 
> put together distinct collective signatures representing different 
> subsets of response-time participants.  Some form of 
> “leader-malleability” of this kind seems unavoidably essential to 
> enabling the leader to complete a collective signing round in the 
> presence of partial failures without restarting.  Perhaps the same 
> limited leader-malleability is more-or-less the same property your 
> suggestion of using chameleon hashes has, although I haven’t had a 
> chance to compare them deeply yet.
> 
> it’s better to (a) enforce strict non-malleability of collective 
> signatures (by anyone, leader included), at the cost of O(N)-round DoS 
> attack vulnerability during signing due to the need to restart partially 
> failed rounds, or (b) provide some limited form of limited 
> leader-malleability in order to support restart-free operation and avoid 
> DoS attacks during signing, at the cost of a more complex protocol (and 
> perhaps slightly more “special” trust in the leader than we might like).
> 
>> On Jul 3, 2017, at 7:34 PM, Daniel Slamanig <[email-masked] 
>> <mailto:[email-masked]>> wrote:
>>
>> Hi Philipp,
>>
>> looks interesting!
>>
>> Not committing to Z as well as the actual sum of signers public keys 
>> A' in the computation of the hash c for the signature seems to be 
>> problematic.
>>
>> It seems to me that committing Z in the signature in plain as well as 
>> A' does not work given the later application of the signing procedure 
>> notation for scalar multiplication and write it from the perspective 
>> of the leader, i.e., the signer that initiates the protocol.
>>
>> function (this is just the standard way of constructing a chameleon 
>> hash from DL for arbitrary message spaces as propsed in [1]). If Z' is 
>> not yet known one simply sets Z' to some fixed string at the 
>> beginning, e.g., Z':=0. At the end of the protocol, when the leader 
>> knows the exact signers, it can update Z' to the final value Z and use 
>> sk_ch to compute a collision in the chameleon hash, i.e., such that 
>> CH(Z)=CH(Z') by solving h(Z')+u'y = h(Z)+uy for u. He then adds u and 
>> Z as well as pk_ch to the signature, i.e., sets it as (R,s,u,Z,pk_ch) 
>> and discards sk_ch and u'. If Z is known beforehand, one simply 
>> computes the chameleon hash once and does not need to compute a 
>> collision. Clearly, the use of a chameleon hash allows to simply adapt 
>> to the actual set of signers representing Z without modifying c (with 
>> the knowledge of sk_ch - but it does not work without the knowledge of 
>> sk_ch). This would resolve the issue with the unknown Z at the time of 
>> signing.
>>
>> Also, A is committed in the signature, but not the concrete A'=\sum 
>> A_i of keys used for computing the signature (I guess also due to the 
>> reason that one does not know the correct set of signers when 
>> computing the hash c). That can be problematic in a rogue key scenario 
>> in the current protocol, i.e., when not all signers need to prove 
>> knowledge of the secret key when they register their public keys but 
>> their public keys could be functions of other public keys (guess this 
>> could be a problem here). For instance, a malicious A^* could just 
>> take some key from A, say A_j, and compute and publish A^*=a^*A_j. And 
>> then given a collective signature (R,s,Z) where A_j participated, the 
>> signer can update s to s^* = s+a^*c as well as Z^* to exclude A_j and 
>> include A^* (as Z is not committed in the signature generation) and 
>> the signature (R,s^*,Z^*) will be a valid signature that certifies 
>> that A^* participated in signing - although he didn't.
>>
>> verification, then this should no longer work. One could also adapt 
>> the hash c=H(R||pk_ch||CH(Z'||A)||S) to include a chameleon hash to 
>> CH(Z||A'), where A' is the real set of signers that participated in 
>> the signature generation and is adapted before finalizing the 
>> signature when known as above.
>>
>> non-signers with a bit set to 1. Why not identifying the signers with 
>> a bit set to 1?
>>
>> Cheers,
>> Daniel
>>
>>
>>> Here’s a first version of an Internet-Draft on “Collective 
>>> Edwards-Curve Digital Signature Algorithms” based on Ed25519 and 
>>> Ed448: https://datatracker.ietf.org/doc/draft-ford-cfrg-cosi/

---

From: Bryan Ford <[email-masked]>
Date: Tue, 11 Jul 2017 12:29:02 +0200

Hi Daniel, sorry about the slow followup…

> On Jul 6, 2017, at 10:34 AM, Daniel Slamanig <[email-masked]> wrote:
> Another observation regarding committing to the bitmask Z. If you do not commit to the bitmask Z, then users could cooperate in setting up their public keys, lets say A_i and A_j cooperate. Then one of them could take part in the signing, but in the end one could use the attack with the rogue keys outlined in my initial mail so that A_j can claim that he took part in the signing process although A_i actually took part. As far as I see not even using a delinearization scheme would help here. Nevertheless, it seems to me that this is not a valid attack vector when I look at the paper (but as you do not formally specify a security model for your approach in the paper this is hard to tell).

Correct - when two users A_i and A_j collude in such fashion, we just count both of them as “malicious” in our threat model.  In practice, if two nodes want to collude in this way, there are easier attacks that have nothing to do with collective signing but would work equally well with the “base-case” approach of collecting a bunch of individual signatures.  For example, A_i simply uses A_j’s private key (which A_j shares with A_i because they’re colluding) to pretend to be A_j and sign on A_j’s behalf, individually or collectively.  Or vice versa.

> Note that such an attack would even work if users have to register the public keys and prove that they know the secret key corresponding to the public key, e.g., via a (NI)ZK proof of the secret key - which I have seen is mentioned in the paper, but not discussed in the draft. Summing up, without commiting to Z in the signature, you would trivially not be able to achieve strong EUF-CMA security of the multi-signature due to the malleability, but as far as I see standard EUF-CMA should still hold (which seems sufficient for your application).

Agreed.  The critical question is then whether to prioritize strict non-malleability, or to allow just enough malleability to allow for stronger protection against DoS attacks.  The tradeoff is subtle and the ideal balance is not clear to me at least.

Cheers
Bryan

>> To follow up on my last message to Oleg, again I suggest reading section IV of our CoSi paper from IEEE S&P last year (http://dedis.cs.yale.edu/dissent/papers/witness-abs), as it discusses several related issues, especially the potential desire to allow the leader to complete a collective signing procedure even with only a subset of “committed” participants remaining present in the “response” phase.  In particular, the leader can form all the individual Schnorr commits into a Merkle tree, and make the real commit c be the root of that Merkle tree.  In this way, the leader is committing not so much to a particular collective Schnorr commit but rather to *all possible* Schnorr commits that can be composed from any subset of the individual Schnorr commits within that Merkle tree.  This way, if some of the participants whose commits are present in that Merkle tree remain available during the response phase but others drop out, the leader can still use the commit c and form a correct and verifiable collective signature against the particular subset of Schnorr commits from nodes that remained available throughout the process, without restarting.
>>> On Jul 3, 2017, at 7:34 PM, Daniel Slamanig <[email-masked] <mailto:[email-masked]> <mailto:[email-masked] <mailto:[email-masked]>>> wrote:
>>> 
>>> Hi Philipp,
>>> 
>>> looks interesting!
>>> 
>>>> [email-masked] <mailto:[email-masked]> <mailto:[email-masked] <mailto:[email-masked]>>