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

Bryan Ford <brynosaurus@gmail.com> Wed, 05 July 2017 12:26 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 C450113173E for <cfrg@ietfa.amsl.com>; Wed, 5 Jul 2017 05:26:20 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.698
X-Spam-Level:
X-Spam-Status: No, score=-2.698 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_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 LBD0OJ5384x0 for <cfrg@ietfa.amsl.com>; Wed, 5 Jul 2017 05:26:18 -0700 (PDT)
Received: from mail-wm0-x236.google.com (mail-wm0-x236.google.com [IPv6:2a00:1450:400c:c09::236]) (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 60C34131CC6 for <cfrg@irtf.org>; Wed, 5 Jul 2017 05:26:17 -0700 (PDT)
Received: by mail-wm0-x236.google.com with SMTP id w126so220483112wme.0 for <cfrg@irtf.org>; Wed, 05 Jul 2017 05:26:17 -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=mwnvGsPBHKiwxHkqQU9vnOJU6rT1ABBo4eRs3iflN4Y=; b=FezNIpgSwHO8zVIWCVZBEQSD639KOc1Vwv6VxUDFgqOgfMn5enTnbO64IrDoydOnRf LUAm5NxS6mYvbNCJxVtwGjQypZwEvWMJORs84yULhXK4tDkBoF+TH8rRj7fvz+2nvWmr Pzqm4P1PX0zodLxBXM1Wwx5NN4teZ6I9mheqK5IWNI8WNTwDDC9pMSbfU+NM1ZQzFmzw /vnUEWoWgZ6zrdr7t0OeJBYfZvkovaY6hcF2aD3EqkKJ2b2qK1fdNgs3KzLvAoqs/Ms2 r+Mt9gaJA10aQ7wt9ViVcKndxjtV2ZiSGQPuFGsdaUQhk3NVHvikEsn6QG5p8uxSBxUK 9olg==
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=mwnvGsPBHKiwxHkqQU9vnOJU6rT1ABBo4eRs3iflN4Y=; b=qNdc/ccIyfRKSP2/nDzln53bMM1b4Vl9zHluiwo0/roli65yayPQmlSyIp8ya5ezkp LJBrSVm91Fvrd5aBYPqGJ3DYOcNKPi81Xqq4C3bX39f274SUtvxVnEe0i5cn6Ep84o+d Efnpp3jH/ilRVjUWOozdf3iDKCCE9gAX6aWOIvwxGtl7tTxZsIvQGSZB1L+yThBY6bcx yF8FtEUIe9tzyzoOXIYtHle8vD3t8BMNIOUuM+2hevR5rdMdcJaUlwjKc1SR8V3W9KdR n4KwhG/aO7Pc1V2+o+xiguT/ISXpOManfrGFyklCSwqfGUDY9Juu+GHv7oVDtXTZURhb 3iBQ==
X-Gm-Message-State: AKS2vOyE7RLp7satfnSvJ1Fp8y3vDOSrpnb1T5JSOKMYPHY9RCPb/JK2 HqLL3pUGw8o9uvzYXRI=
X-Received: by 10.80.182.90 with SMTP id c26mr18012347ede.55.1499257575765; Wed, 05 Jul 2017 05:26:15 -0700 (PDT)
Received: from [172.20.10.3] (81.227.197.178.dynamic.wless.zhbmb00p-cgnat.res.cust.swisscom.ch. [178.197.227.81]) by smtp.gmail.com with ESMTPSA id r37sm5639975edd.19.2017.07.05.05.26.13 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 05 Jul 2017 05:26:14 -0700 (PDT)
From: Bryan Ford <brynosaurus@gmail.com>
Message-Id: <A4104495-EE45-4CD2-B4F0-014AC6E74C34@gmail.com>
Content-Type: multipart/signed; boundary="Apple-Mail=_9B18970A-44D2-4314-BBB3-E8F2C5E69443"; protocol="application/pgp-signature"; micalg="pgp-sha256"
Mime-Version: 1.0 (Mac OS X Mail 10.3 \(3273\))
Date: Wed, 05 Jul 2017 14:26:11 +0200
In-Reply-To: <5E91769F-B102-4A49-9ED5-B789D4FED598@gmail.com>
Cc: Philipp Jovanovic <philipp@jovanovic.io>, cfrg@irtf.org
To: Oleg Andreev <oleganza@gmail.com>
References: <8AE29DD0-26FE-4AB6-A4A9-2BB9169BAB13@jovanovic.io> <5E91769F-B102-4A49-9ED5-B789D4FED598@gmail.com>
X-Mailer: Apple Mail (2.3273)
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/lcA-AZj_f7N66RFOD-Y4XrEbgH4>
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 12:26:21 -0000

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 <oleganza@gmail.com> wrote:
> 
> 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

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 committing to the exact set of signers is a good idea.

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.

> 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.

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

> 
> Cheers,
> Oleg.
> 
>> On 2 Jul 2017, at 00:58, Philipp Jovanovic <philipp@jovanovic.io> 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
> 
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg