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

Daniel Slamanig <daniel.slamanig@tugraz.at> Mon, 03 July 2017 17:34 UTC

Return-Path: <daniel.slamanig@tugraz.at>
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 B1ADA129B77 for <cfrg@ietfa.amsl.com>; Mon, 3 Jul 2017 10:34:27 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -4.301
X-Spam-Level:
X-Spam-Status: No, score=-4.301 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, RCVD_IN_DNSWL_MED=-2.3, RP_MATCHES_RCVD=-0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=tugraz.at
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 H50S3-dt8bKd for <cfrg@ietfa.amsl.com>; Mon, 3 Jul 2017 10:34:24 -0700 (PDT)
Received: from mailrelay.tugraz.at (mailrelay.tugraz.at [129.27.2.202]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 982AA131668 for <cfrg@irtf.org>; Mon, 3 Jul 2017 10:34:22 -0700 (PDT)
Received: from [10.27.152.210] (nat-hiding.iaik.tugraz.at [129.27.152.126]) (authenticated bits=0) by mailrelay3.tugraz.at (8.14.9/8.14.9) with ESMTP id v63HYGA9009014 (version=TLSv1/SSLv3 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NO); Mon, 3 Jul 2017 19:34:16 +0200
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=tugraz.at; s=mailrelay; t=1499103260; bh=NiX2sI6wEg5N4l7+0uLeinJcYc/jcKwle1CTrdRvVXw=; h=Subject:To:References:Cc:From:Date:In-Reply-To; b=FjitOLg9m9Dtrx4lbqyRPYFNPbn/WBR5mWNRG7jpv3HMGk9AB3bDHlNSX0yl+aFnn +HEL9WUEdTtp1Ei4q1sQFT7l3L29lgxaoSF4sHiaocnITzEkY6JscqeyunklqLEyq7 TEWfCcsiJ2Ik2kuBqUtoBICPCZqNyNqu03TwuAw8=
To: Philipp Jovanovic <philipp@jovanovic.io>
References: <8AE29DD0-26FE-4AB6-A4A9-2BB9169BAB13@jovanovic.io>
Cc: cfrg@irtf.org
From: Daniel Slamanig <daniel.slamanig@tugraz.at>
Message-ID: <11cc5d3f-ecf9-2fd0-825c-c8b441bd2813@tugraz.at>
Date: Mon, 3 Jul 2017 19:34:15 +0200
User-Agent: Mozilla/5.0 (Windows NT 6.3; WOW64; rv:52.0) Gecko/20100101 Thunderbird/52.2.1
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
X-TUG-Backscatter-control: lAa1Aa+Pa1hp/miybLoRww
X-Spam-Scanner: SpamAssassin 3.003001
X-Spam-Score-relay: -1.7
X-Scanned-By: MIMEDefang 2.74
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/DUK4gB7HRIM8JwBEDguFgb8rukk>
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: Mon, 03 Jul 2017 17:34:28 -0000

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
http://www.iaik.tugraz.at