Return-Path: X-Original-To: cfrg@ietfa.amsl.com Delivered-To: cfrg@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id A22FF131D71 for ; Wed, 5 Jul 2017 09:29:38 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -1.998 X-Spam-Level: X-Spam-Status: No, score=-1.998 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id lf5tjaHn0m-U for ; Wed, 5 Jul 2017 09:29:35 -0700 (PDT) Received: from mail-wr0-x235.google.com (mail-wr0-x235.google.com [IPv6:2a00:1450:400c:c0c::235]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id DB28E131D4E for ; Wed, 5 Jul 2017 09:29:34 -0700 (PDT) Received: by mail-wr0-x235.google.com with SMTP id k67so265319095wrc.2 for ; Wed, 05 Jul 2017 09:29:34 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:message-id:mime-version:subject:date:in-reply-to:cc:to :references; bh=0nF05oLs9wB2XszEY29JO2CHdwTe/2lz56sZecOQ0Uc=; b=U9/piQ9M11GLE8bJhll7AhSpRQOZOQwK0gLp526EthlOGAoEApftJ2YHvbwgy6ZKe+ Ww5SeCiRLqu3mf55ut44JckE/2iywlbE3rPBw6qp0F76oCJpYxddBS7sRBOCe4yd+K/Q YoKOtFdkkv+63AfjTFBJHW4Qz+gP6U4+4xal6ri3he/5N8rwN7TMEKjXnQhmCtzBsMCg SGftIUGpDIOT/H0gdVqprS6GLhzHo3qhUqBtKhPHPkTJJqLZ0nRcbZB5bwbzA8U5FBNq a6aW0Xbi7wRPO0uef4VWPfInzN3ymPJhj0BbncEUlVIkkchyLu/q63RIyyWKf0t0WoTq ShLg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:message-id:mime-version:subject:date :in-reply-to:cc:to:references; bh=0nF05oLs9wB2XszEY29JO2CHdwTe/2lz56sZecOQ0Uc=; b=UV7RCYfb4dOzYl6u//97RGahBpz8gVgha//AwYkNKrcvOmm/Sgm2ofDK3armEwqZiM +jWHKfqnHUq+BdJRI/Pr4K0HccRuD6tWbfK1u09Wpk19i/cJvZ9VnAKgv9oOho0PoMym yb3o6A5PZbvF+GVpM54NmFjdnrFe+R7mzhlZ1rR+zd9anlfgXuvVIHZzypvRbWR/CESX UEeEiq6JzUywqRAmgHvS/t81NQfmqJ/PzaQYPurAuxWsZsYK9b3ZYQoCZkEqYQvfphu0 dafkdIbcd3N9Bdo4CUtOij3VdZ3TMDHAqba64k7v9kxIsf+AZ2T4U4OhDd3oWq8c5hpC uSNQ== X-Gm-Message-State: AKS2vOxNMv8dGs+KoSjwgxXwfOoMFT8fWMVvGN4vtRwORVPG8aDRL+Hz ecAHaDnZTjEb/g== X-Received: by 10.223.145.227 with SMTP id 90mr39896772wri.171.1499272173395; Wed, 05 Jul 2017 09:29:33 -0700 (PDT) Received: from [192.168.1.28] (83-103-13-156.ip.fastwebnet.it. [83.103.13.156]) by smtp.gmail.com with ESMTPSA id 79sm12600055wrc.34.2017.07.05.09.29.25 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 05 Jul 2017 09:29:26 -0700 (PDT) From: Bryan Ford Message-Id: Content-Type: multipart/signed; boundary="Apple-Mail=_821CAADD-B3B5-40A3-BF93-B12AD20EDA74"; protocol="application/pgp-signature"; micalg=pgp-sha256 Mime-Version: 1.0 (Mac OS X Mail 10.3 \(3273\)) Date: Wed, 5 Jul 2017 18:29:23 +0200 In-Reply-To: Cc: Daniel Slamanig , cfrg@irtf.org To: Thomas Garcia References: <8AE29DD0-26FE-4AB6-A4A9-2BB9169BAB13@jovanovic.io> <11cc5d3f-ecf9-2fd0-825c-c8b441bd2813@tugraz.at> X-Mailer: Apple Mail (2.3273) Archived-At: Subject: Re: [Cfrg] Internet-Draft: Collective Edwards-Curve Digital Signature Algorithm X-BeenThere: cfrg@irtf.org X-Mailman-Version: 2.1.22 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 05 Jul 2017 16:29:39 -0000 --Apple-Mail=_821CAADD-B3B5-40A3-BF93-B12AD20EDA74 Content-Type: multipart/alternative; boundary="Apple-Mail=_B73CB522-DE56-4B30-967E-A4ECA65EE493" --Apple-Mail=_B73CB522-DE56-4B30-967E-A4ECA65EE493 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset=utf-8 Hi Thomas, > On Jul 5, 2017, at 3:27 PM, Thomas Garcia = wrote: >=20 > 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. 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 =3D SHA512(R || A || M) independently = based on that R, ensuring that the responses they produced are only good = for a particular message M they=E2=80=99ve 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=E2=80=99ll 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)=3DSHA512(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=E2=80=99s not clear that there=E2=80= =99s 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=E2=80=99t be an issue = in practice. Cheers Bryan > Thomas G. >=20 > On Wed, Jul 5, 2017 at 2:11 PM, Bryan Ford > wrote: > Hi Daniel, thanks for your thoughts on the commitment-to-the-bitmask = issue. >=20 > Your proposal of using a chameleon hash, to allow the leader to = =E2=80=9Cadjust=E2=80=9D 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=E2=80=99t that still make the final collective signature = malleable for the leader (or for anyone the leader=E2=80=99s 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. >=20 > 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 =E2=80=9Ccommitted=E2=80=9D participants remaining present in = the =E2=80=9Cresponse=E2=80=9D 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. >=20 > 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 = =E2=80=9Cleader-malleability=E2=80=9D 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=E2=80=99t had = a chance to compare them deeply yet. >=20 > But at any rate, the higher-level tradeoff here to consider is whether = it=E2=80=99s 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 =E2=80=9Cspecial=E2=80=9D trust in the leader than = we might like). >=20 > Again, further thoughts on this and other topics are most welcome. >=20 > Thanks > Bryan >=20 >> On Jul 3, 2017, at 7:34 PM, Daniel Slamanig = > wrote: >>=20 >> Hi Philipp, >>=20 >> looks interesting! >>=20 >> After looking at the protocol I also have some security concerns = (related to what has been raised by Oleg in a previous mail). >>=20 >> 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. >>=20 >> 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). >>=20 >> Committing to neither of both however seems problematic as it does = not fix the set of actual signers. >>=20 >> 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. >>=20 >> The leader could choose chameleon hash parameters sk_ch=3Dy for = random y and pk_ch=3D(P,Y=3DyP) and add pk_ch and chameleon hash = CH(Z'):=3Dh(Z')P+u'Y for randomly chosen u' to the computation of c, = i.e., set c=3DH(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':=3D0. 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)=3DCH(Z') by solving h(Z')+u'y =3D 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. >>=20 >> Also, A is committed in the signature, but not the concrete A'=3D\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^*=3Da^*A_j. And then given a = collective signature (R,s,Z) where A_j participated, the signer can = update s to s^* =3D 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. >>=20 >> 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=3DH(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. >>=20 >> 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. >>=20 >> 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=3D\sum R_i instead of R=3D[r]B which would = mean that they would send their r_i's (hope they will not do so). >>=20 >> 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? >>=20 >> Cheers, >> Daniel >>=20 >>=20 >> [1] Hugo Krawczyk, Tal Rabin: Chameleon Signatures. NDSS 2000 >>=20 >> On 01.07.2017 23:58, Philipp Jovanovic wrote: >>> Hi CFRG, >>> Here=E2=80=99s a first version of an Internet-Draft on =E2=80=9CCollec= tive Edwards-Curve Digital Signature Algorithms=E2=80=9D 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 >>> _______________________________________________ >>> Cfrg mailing list >>> Cfrg@irtf.org >>> https://www.irtf.org/mailman/listinfo/cfrg = >>=20 >>=20 >> -- >> 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 >>=20 >> _______________________________________________ >> Cfrg mailing list >> Cfrg@irtf.org >> https://www.irtf.org/mailman/listinfo/cfrg = >=20 >=20 > _______________________________________________ > Cfrg mailing list > Cfrg@irtf.org > https://www.irtf.org/mailman/listinfo/cfrg = >=20 >=20 --Apple-Mail=_B73CB522-DE56-4B30-967E-A4ECA65EE493 Content-Transfer-Encoding: quoted-printable Content-Type: text/html; charset=utf-8 Hi Thomas,

On Jul 5, 2017, at 3:27 PM, = Thomas Garcia <tgarcia.3141@gmail.com> wrote:

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.

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 =3D = SHA512(R || A || M) independently based on that R, ensuring that the = responses they produced are only good for a particular message M = they=E2=80=99ve 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=E2=80=99ll 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)=3DSHA512(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=E2=80=99s not clear that there=E2=80= =99s 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=E2=80=99t be an issue = in practice.

Cheers
Bryan

Thomas G.

On Wed, = Jul 5, 2017 at 2:11 PM, Bryan Ford <brynosaurus@gmail.com> wrote:
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 =E2=80=9Cadjust=E2=80=9D 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=E2=80=99t that still make the final collective = signature malleable for the leader (or for anyone the leader=E2=80=99s = 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 = =E2=80=9Ccommitted=E2=80=9D participants remaining present in the = =E2=80=9Cresponse=E2=80=9D 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 =E2=80=9Cleader-malleability=E2=80=9D = 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=E2=80=99t had a chance to compare them = deeply yet.  

But at any rate, the higher-level tradeoff here to consider = is whether it=E2=80=99s 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 =E2=80=9Cspecial=E2=80=9D 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 <daniel.slamanig@tugraz.at> 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=3Dy for random y and = pk_ch=3D(P,Y=3DyP) and add pk_ch and chameleon hash CH(Z'):=3Dh(Z')P+u'Y = for randomly chosen u' to the computation of c, i.e., set = c=3DH(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':=3D0. 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)=3DCH(Z') = by solving h(Z')+u'y =3D 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'=3D\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^*=3Da^*A_j. And = then given a collective signature (R,s,Z) where A_j participated, the = signer can update s to s^* =3D 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=3DH(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=3D\sum = R_i instead of R=3D[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

On 01.07.2017 23:58, Philipp Jovanovic wrote:
Hi CFRG,
Here=E2=80=99s a first version of an Internet-Draft on = =E2=80=9CCollective Edwards-Curve Digital Signature Algorithms=E2=80=9D = 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
_______________________________________________
Cfrg mailing list
Cfrg@irtf.org
https://www.irtf.org/mailman/listinfo/cfrg

--
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
_______________________________________________
Cfrg mailing list
Cfrg@irtf.org
https://www.irtf.org/mailman/listinfo/cfrg


_______________________________________________
Cfrg mailing list
Cfrg@irtf.org
https://www.irtf.org/mailman/listinfo/cfrg



= --Apple-Mail=_B73CB522-DE56-4B30-967E-A4ECA65EE493-- --Apple-Mail=_821CAADD-B3B5-40A3-BF93-B12AD20EDA74 Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename=signature.asc Content-Type: application/pgp-signature; name=signature.asc Content-Description: Message signed with OpenPGP -----BEGIN PGP SIGNATURE----- iQIcBAEBCAAGBQJZXRPkAAoJEGt1rlrP7+d/LJgQAIKccHkpUYtcbN+3IlP40uBC DZt2+l9DzHcp1VOfaN7d7OL+aLTRkEhOdIWj/12RBuLbd1s8FRCp8IjSm96eYnPz mA9EDd0maLxdBOnXco6QROwOEC14rgDk18bCD2BsbXZt1m1FTby5cSHPpHNqyihP r8SZcVL5CL6D1vr1SZx15Hh8UjEaSy+PT0CriXBYXuohwVx8Bj7hp2IqMcgDtQeu b8WWuW7Y+lCcb77VguB1YRndK936pQ76Xm4/nWjirViYoa22w8fRlBvIbf1kq799 qGzwRYHARCeGihMCJ7PbNl3cdkLnUISx2kbJIQ8f8N2qRT846LoWqr6EOPrDd1gU zdbrKKX+jJEoHsufEtzGQaGw8A8kewhQYNBEjNQ8/QT6sTkKU7r7ukJM2OvDY6g6 hBnQG259fGVlczQ4Ys7M/0w3l53B+pZ5OTJ6GDxWjqiPTU+lPsCWw68G1lp/31k1 n2HN3sgoMkMHUN/IiRD/HqIYcf9LVcnvZUTx0O/DhYKCWMUsAgwPWu99PlCLHYtx vFFU++wmMcQe4xxVXOAbn3nGY4hBsxRMRgSDBk0+IJhjbUqDa5SftCr7dIXfjYiE vXopD8skA8m9qzcEseWMh6ha0B9jlG2Kz1b8v51BvQaT8RyOCJHGbqwHh8djeoZ4 r1GcdV7sx7zhZ/eGJOr6 =wuak -----END PGP SIGNATURE----- --Apple-Mail=_821CAADD-B3B5-40A3-BF93-B12AD20EDA74--