Subject: Re: [Trans] Long-term: scalable collective signing (of certs, log-heads, and/or SCTs)

From: Eran Messeri <[email-masked]>
Date: Wed, 30 Sep 2015 14:02:15 +0100

On Sun, Jul 12, 2015 at 3:28 PM, Bryan Ford <[email-masked]> wrote:

> Hi TRANS folks,
>
> My group at Yale (and shortly to be at EPFL) has been working on
> techniques to make threshold/multi-signature techniques scale efficiently,
> a goal partly motivated by the CA security problem, and whose solution may
> be relevant and complementary to CT.  Basically, our protocol allows a
> “authority server” of any kind to propose publicly a message to be signed,
> and any number of “witness” nodes get the opportunity to inspect and
> approve or object, in the former case contributing a share of the final
> signature, ensuring that nothing gets signed without being widely witnessed
> and approved.  For example, in testbed experiments we’ve demonstrated ~4000
> participants collectively computing a single signature in 1.5-3 seconds
> including wide-area-equivalent round-trip times.  I envision this
> capability might be useful to the TRANS group’s goals in various ways:
>
> 1. In the long term - most ambitious but perhaps least realistically
> deployable - security-conscious CAs could in the future move toward a
> collective-signing model for issuing actual certs.  For example, root CAs
> could gradually deprecate the issuance of delegated authority to sub-CAs,
> instead bringing these sub-CAs into a collective run by the root, such that
> any CA in the group can propose certificates but all have the opportunity
> to inspect before the cert receives a valid (collective) signature.  Of
> course there would be many practical challenges here; I’m under no illusion
> that this approach would be viable for the near-term but may be worth
> thinking about on a “long-term roadmap.”
>
> 2. A more near-term possibility is to consider collective signing for SCTs
> in CT.  This would be easier to deploy incrementally since CT isn’t yet
> “set in stone”, but it would still present challenges, such as the
> possibility of delaying SCT signatures (even if by only a few seconds), to
> which there may be objections.
>
As I pointed out in-person, you and your group could implement this
suggestion right now:
* Base a CT log server on the open-source version that would go out and
seek collective signatures from a group of monitors (which could be based
on open-source monitor code).
* Put the obtained multi-signature into the SCT's extension field (you'd
have to propose an extensions format for this field as it's currently not
defined).
* Contribute code to Chromium that, in the presence of this extension,
would verify the multi-signature in addition to the "regular" signature.

All of that is feasible to implement and does not require the workgroup's
agreement.
Until there's running code proving such a deployment is feasible
(particularly finding willing parties to run the independent monitors and
issuing SCTs within an acceptable timeframe) I don't see how the discussion
around this idea being a viable alternative to  gossip can progress.

>
> 3. A still more near-term possibility is to consider enhancing CT
> log-servers to support collective signing of log-heads.  Witness/monitor
> servers would then be able to join the signing collective of log servers
> they monitor, not just passively checking but actively contributing to the
> signature of each log-head signature.  Anyone (particularly clients) could
> then check offline that a log-head was not only signed by the log server
> operator but also witnessed and verified by any number of monitor servers
> with a single signature check.
>

> Regardless of approach, I think the most important potential opportunity
> here is to address the privacy problem that CT’s gossip mechanism creates
> for clients.  Currently clients have no way to check the SCTs they see
> unless they’re willing to reveal their browsing history to a “trusted
> monitor”, which is unfortunate for users desiring privacy and reluctant to
> trust any single “trusted authority".  With either options #2 or #3 above,
> a client could verify that an SCT was signed (#2) or a cert was logged and
> widely witnessed (#3) with a single signature-check requiring no
> communication or browsing-history disclosure to any server.
>
> At the moment I just want to bring this information to the group and
> solicit feedback or discussion for anyone interested; I’m not making any
> particular proposal at the moment.  If collective signing support provides
> to be of interest at some point, it could certainly be added as a
> later-stage CT extension.  The main (and only that I know of now)
> consideration I suggest the group might want to consider in the near term
> is whether the CT spec should perhaps include support for at least one
> Schnorr-type signature scheme (e.g., Ed25519) rather than just RSA and
> ECDSA, since scalable multisignatures work readily in Schnorr schemes but
> are not so easy or scalable in RSA or ECDSA.
>
> We did a short presentation recently at HotPETS on this topic, and I would
> be happy to do a brief presentation on this at the TRANS meeting if there’s
> time and interest.  More details of this ongoing work-in-progress are
> available in the following preprint and slide-deck:
>
>         Decentralizing Authorities into Scalable Strongest-Link Cothorities
>         Preprint: http://arxiv.org/abs/1503.08768
>         Slides:
> http://dedis.cs.yale.edu/dissent/pres/150610-nist-cothorities.pdf
>
> Our prototype code (in Go) is also online and I’d be happy to share it,
> but it’s not yet in a particularly clean, well-documented, or usable state
> yet.  We’ll be working on that over the coming months but am happy to work
> with anyone deeply interested enough to want to dive into the code
> earlier.  And in any case, I’ll be at IETF 93 for the whole week and happy
> to discuss further with anyone interested.
>
> Thanks
> Bryan
>
>
>
> _______________________________________________
> Trans mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/trans
>
>

---

From: Katriel Cohn-Gordon <[email-masked]>
Date: Wed, 30 Sep 2015 14:35:58 +0100

​Note that ARPKI <http://dl.acm.org/citation.cfm?id=2660298> (among other
academic CT variants) similarly has no need for gossip; roughly, monitors
sign that they have seen a cert and then clients just verify the
signatures. Multisignatures sound like an elegant way to achieve that; are
they more efficient than *n* individual signatures for smallish cothorities
e.g. size <10?

I've never quite understood why CT mandates gossip instead of having
monitors sign that they have seen an STH. Perhaps this is a good
opportunity to clarify that point?

> around this idea being a viable altern
> ​​
> ative to  gossip can progress.
>

​This seems to be a chicken-and-egg problem, since Google is the motivating
force behind CT. I don't see why independent monitors would want to try out
alternatives just in case someone at Google decides that maybe they'll be
used.

Katriel

---

From: Eran Messeri <[email-masked]>
Date: Wed, 30 Sep 2015 15:01:11 +0100

On Wed, Sep 30, 2015 at 2:35 PM, Katriel Cohn-Gordon <[email-masked]>
wrote:

> they more efficient than *n* individual signatures for smallish
> cothorities e.g. size <10?
>
My understanding is that this is mainly a key management / audit issue:
Logs can be checked for compliance with RFC6962, after which their keys can
be distributed to clients. When adding monitors to the system, we'd have to
cope with:
* Monitoring the monitors for behaving correctly - the biggest issue being
defining what monitors do. Ideally monitors would notify domain owners of
newly-issued certificates for their domains, but how can that behaviour be
verified?
* ARPKI (as far as I understand) assumes independence between log operators
and monitors - something that is difficult to audit and, in practice, hard
to demand as parties motivated to participate in CT are parties with a
stake - CAs and browser vendors.
* Complexity: Adding another actor which, at least to my understanding,
would not add security to the system: If the threat is multiple actors
being compromised, a client can require signatures from multiple logs
rather than a single log and multiple monitors (please correct me if I'm
wrong in my understanding of ARPKI here).

> ​This seems to be a chicken-and-egg problem, since Google is the
> motivating force behind CT. I don't see why independent monitors would want
> to try out alternatives just in case someone at Google decides that maybe
> they'll be used.
>
This is where other forces could join and present better alternatives /
improvements - just like Tom Ritter created a Chromium patch to require CT
(which he unfortunately didn't submit for proper review), others can
present alternatives to Chromium developers (which are in a distinct part
of Google from the CT team), in the form of patches.