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

Thomas Garcia <tgarcia.3141@gmail.com> Wed, 05 July 2017 13:27 UTC

Return-Path: <tgarcia.3141@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 90F53132A19 for <cfrg@ietfa.amsl.com>; Wed, 5 Jul 2017 06:27:07 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.448
X-Spam-Level:
X-Spam-Status: No, score=-2.448 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_ENVFROM_END_DIGIT=0.25, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_LOW=-0.7, 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 X1arLZakUaiv for <cfrg@ietfa.amsl.com>; Wed, 5 Jul 2017 06:27:03 -0700 (PDT)
Received: from mail-lf0-x229.google.com (mail-lf0-x229.google.com [IPv6:2a00:1450:4010:c07::229]) (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 3B2E6132A13 for <cfrg@irtf.org>; Wed, 5 Jul 2017 06:27:03 -0700 (PDT)
Received: by mail-lf0-x229.google.com with SMTP id t72so24793950lff.1 for <cfrg@irtf.org>; Wed, 05 Jul 2017 06:27:03 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=UKfnMuwHUZ/RgEvUOOGlINc1+jwLRDMAn5UQdl/D17s=; b=RQrqZDZipeNNA421oDvOPmrkuimuILR8SqbMcxEt+Wrp45xev9oiv0TbsC8AHJ2MUR Ys6zVKdJS7jCikBG6dyzp4RBl0RtTw3MJhGx/mYqfsw4A+LDJYAt3KjNfJ9cfZ31ssmx iSiy0LT0+DTw47mnbF8vK+XQ8ZU/2wRJ9V6iLUo5yqsFrr+a7YZePYxRpEuPzGR0ioXG kmffynVavkmAn2rdfJmoN5p5hO6zfzZ9ajThz/tVWRmLgWKPkGuOKxbbP4XJTk+WZzON 9RFp9RXEJ3tNm/lthZpXBKwMIbd+oGKLze/NuB45Ny61TQOCpA4sBCvzrR2ddSdva+2g 3iIg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=UKfnMuwHUZ/RgEvUOOGlINc1+jwLRDMAn5UQdl/D17s=; b=GVq+boCzeQlVy/cnIdFMOIia2waEuchfUa8m5fVceoXDi5VMHMWnK5QUcMKJN7DM/k Q6juWLdjG8u1l32B0MtZf9adQNoo1uchGC8lR6wKaVW7asStCC9vlMD0abfYhojCx7oL oWVgBAT9JHzikewCAtNMr48yhiZ45OPRtP1tw2GKMvMrzUpOhZTRrW1DX+whCg7lVGCZ bU3oBZJf0SYv0QO65dgKkOIPEhtYVNLRq6IVMGEDeYiJGWWlwXvSYbEUXIdNPQSjKWW9 JhU6HhjZCxR6CDwWFN1I4UA3c1fEU6363cq+AJWdQWcnNyqwCwU2ajh1fMoZeEXjkb0G eAQA==
X-Gm-Message-State: AKS2vOzyv7Fjfn6081YP8uRg5n6FDcikuzstv4c/ecA3blIfkhuxIGgE Qi7HA3JLhQlhOppP/z4MP6Cc0w7YWA==
X-Received: by 10.46.71.72 with SMTP id u69mr13290752lja.16.1499261221388; Wed, 05 Jul 2017 06:27:01 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.25.22.211 with HTTP; Wed, 5 Jul 2017 06:27:00 -0700 (PDT)
In-Reply-To: <A423CB6E-D649-4320-BB76-2E3783D6AFE0@gmail.com>
References: <8AE29DD0-26FE-4AB6-A4A9-2BB9169BAB13@jovanovic.io> <11cc5d3f-ecf9-2fd0-825c-c8b441bd2813@tugraz.at> <A423CB6E-D649-4320-BB76-2E3783D6AFE0@gmail.com>
From: Thomas Garcia <tgarcia.3141@gmail.com>
Date: Wed, 5 Jul 2017 14:27:00 +0100
Message-ID: <CAFTSWve-J9pKVAaCJ=F==ZP_6=f2QMR2chD+J0T7vF6SNb95Ow@mail.gmail.com>
To: Bryan Ford <brynosaurus@gmail.com>
Cc: Daniel Slamanig <daniel.slamanig@tugraz.at>, cfrg@irtf.org
Content-Type: multipart/alternative; boundary="001a11411b8486ca1c055391f431"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/QTz9IEbcKURvqQoxI7hrfCaz3Rk>
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: Wed, 05 Jul 2017 13:27:07 -0000

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 <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 “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).
>
> 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=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/
> 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 <+43%20316%208735509>
> 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
>
>