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

Bryan Ford <brynosaurus@gmail.com> Tue, 11 July 2017 10:29 UTC

Return-Path: <brynosaurus@gmail.com>
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 E3AE2127180 for <cfrg@ietfa.amsl.com>; Tue, 11 Jul 2017 03:29:12 -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 p4C7kz7BKTJe for <cfrg@ietfa.amsl.com>; Tue, 11 Jul 2017 03:29:09 -0700 (PDT)
Received: from mail-wr0-x22b.google.com (mail-wr0-x22b.google.com [IPv6:2a00:1450:400c:c0c::22b]) (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 37931126BF3 for <cfrg@irtf.org>; Tue, 11 Jul 2017 03:29:09 -0700 (PDT)
Received: by mail-wr0-x22b.google.com with SMTP id r103so177163248wrb.0 for <cfrg@irtf.org>; Tue, 11 Jul 2017 03:29:09 -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=hLuXhCzKolEQJ9MHcVVkQgaMYT7HDH+7lhH2CnDPDXw=; b=Q52+X0MO2fICPPkLAm4Ykty2kjFHZEqMoJnQw4yaHtDO3NbKLORwtAnYbXxHEsWIHU 9GfS/xhs+//ESWJENX5+dCYnN44FUmuJx2hEeNxXm4kvp7hNQgs9TiI1JOL5C7cjuAcj pkwVPLs19t4QLBZhrpxOeUcHNFEqqVjzwgeUjxPCzYU5KIrF/fQT+wQRCni0abABeaPR +n5su7O6HIAVRVcDqaaoiSjx92FKJbgg8rYu69YhTbvyu1zoU5LCMNzcPEQZjAkekvew wUNSUWwCjoS3t8960tX2t7Hu4QESNSdZiK1t58uEZpan18lZM2PLSVbk//4v4R36ljmT /Z2A==
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=hLuXhCzKolEQJ9MHcVVkQgaMYT7HDH+7lhH2CnDPDXw=; b=KGcNotF9XjZq7SI6xciwDtLGJgOzAv3KkROPXCHgRFbCqV26Us3f4nDdsI62DlVrgG w8ARAQ/ryGh8THFUNWu+42hUssUT2AHD6J84y4GILXk9E+Gb++oiWct7rcHYpzXva9MW /MoOPLyvAuQz8GHnXWZXJDU4Ird8ZCbzp51BjxNx4+LcktPCXWxm1oXO8Y0KFHDBNCGN 7xIo9mmLG2s/wzT+RAtauBeHsyJnoiuR3eOyGCEedXNKnl5sJlHkSITf0dlQ8KDyJ8I7 4vgPuPhxw8qQNV/G9j11ZDy2k3AUnGUhAk/6ovHFhKkX7lOR+DrUPG3tY2SiPTDG/cQ+ MzIw==
X-Gm-Message-State: AIVw111TIxwq0XXUAS7sY2mX9Ypc5EUuNTU71qYlrCBVt/mCMv62/CaC CAHkILvwcZB9mXpw24g=
X-Received: by 10.80.183.98 with SMTP id g89mr2002621ede.105.1499768947538; Tue, 11 Jul 2017 03:29:07 -0700 (PDT)
Received: from [172.20.10.2] (78.227.197.178.dynamic.wless.zhbmb00p-cgnat.res.cust.swisscom.ch. [178.197.227.78]) by smtp.gmail.com with ESMTPSA id h18sm777749eda.46.2017.07.11.03.29.04 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 11 Jul 2017 03:29:04 -0700 (PDT)
From: Bryan Ford <brynosaurus@gmail.com>
Message-Id: <870B4583-2FF4-4B5F-A19C-5D39FA81559B@gmail.com>
Content-Type: multipart/signed; boundary="Apple-Mail=_4D1010BB-2068-406E-BB75-7089D31ED14A"; protocol="application/pgp-signature"; micalg=pgp-sha256
Mime-Version: 1.0 (Mac OS X Mail 10.3 $$3273$$)
Date: Tue, 11 Jul 2017 12:29:02 +0200
Cc: Philipp Jovanovic <philipp@jovanovic.io>, cfrg@irtf.org
To: Daniel Slamanig <daniel.slamanig@tugraz.at>
References: <8AE29DD0-26FE-4AB6-A4A9-2BB9169BAB13@jovanovic.io> <11cc5d3f-ecf9-2fd0-825c-c8b441bd2813@tugraz.at> <A423CB6E-D649-4320-BB76-2E3783D6AFE0@gmail.com> <1e0faffa-370c-bf81-4973-55bfd36de510@tugraz.at>
X-Mailer: Apple Mail (2.3273)
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/qzQ2Fw1QgexmBs1tePhgCPYL-YA>
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 <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Tue, 11 Jul 2017 10:29:13 -0000

Hi Daniel, sorry about the slow followup…

> On Jul 6, 2017, at 10:34 AM, Daniel Slamanig <daniel.slamanig@tugraz.at> 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

> Thanks and cheers,
> Daniel
>
> On 05.07.2017 15:11, Bryan Ford wrote:
>> 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).
>> 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 <mailto:daniel.slamanig@tugraz.at> <mailto:daniel.slamanig@tugraz.at <mailto: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=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
>>>
>>> On 01.07.2017 23:58, Philipp Jovanovic wrote:
>>>> 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/ <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 <mailto:Cfrg@irtf.org> <mailto:Cfrg@irtf.org <mailto:Cfrg@irtf.org>>
>>>> https://www.irtf.org/mailman/listinfo/cfrg <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 <http://www.iaik.tugraz.at/>
>>>
>>> _______________________________________________
>>> Cfrg mailing list
>>> Cfrg@irtf.org <mailto:Cfrg@irtf.org>
>>> https://www.irtf.org/mailman/listinfo/cfrg <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 <http://www.iaik.tugraz.at/>