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

From: Tom Ritter <[email-masked]>
Date: Sun, 4 Oct 2015 11:37:45 -0500

On 30 September 2015 at 09:01, Eran Messeri <[email-masked]> wrote:
>  improvements - just like Tom Ritter created a Chromium patch to require CT
> (which he unfortunately didn't submit for proper review), others can present

I had a discussion with the people in charge of that area of Chrome
about a similar topic, and re-notified them when I made my blog post.
They had previously indicated they were eschewing additional
complexity for now and didn't reply about suggesting integrating the
require-CT idea. If there is a chance at actually landing the code, I
will go back and clean it up, but if it's going to sit out for 4
releases and then need to be mostly-redone I'll wait a bit longer.
Let's take this offline with the appropriate people.

Going back to Bryan's idea, I'd like to understand a little bit more
about the crypto and its constraints. I apologize for not thoroughly
reading the paper but I hope you'll humor me ...

So it's an N-of-M scheme producing a single signature. I gather than M
needs to be decided upon in the beginning, on set-up, and all the
shares need to be created by a single entity and then provided to the
independent entities?  Is this understanding correct?

That's unfortunate, as it still represents a single point of trust.
It's less, to be sure, and I don't think it's insurmountable for the
'normal' person's notion of trust, but I'm less sure about the legal
"This organization is going to have some sort of agreement with some
other organizations and lawyers have read it" notion of trust. If you
expect to give a key share to, say, ICANN and to CNNIC you need to be
able to say you're pretty darn independent. Is there any way to let
people generate their own key shares and then assemble them into a
public key?

Fixing M in the beginning seems to be an engineering problem more than
a trust one. You're committing yourself to this many shares, and as
time goes on and organizations stop signing, M will stay the same but
the potential number of signers will decrease, and trust will
gradually erode as well. If I understand that the key shares are part
of a Merkle Tree, it seems it might be possible to grow M and add key
shares? This would change the public key of course, but I'm assume we
can handle the rotation.

Also, the slides mention "1-of-k" but I assume it's truly N-of-M and
not 1-of-M correct? Because we should assume at least 1 if not a few
orgs will have their key share compromised and we need to set N high
enough that the average security of the group of organizations is high
enough that compromising N orgs would be difficult.

I think I communicated this before, but I'm supportive of the idea,
I'm just skeptical about the practicality of it. Not from a math or
engineering aspect, but from a humans-interfacing-with-humans aspect.
But if there's code that runs, clear instructions to follow, and a
test network to join - I have a spare box I would set to participating
=)

-tom

---

From: Stephen Kent <[email-masked]>
Date: Tue, 6 Oct 2015 10:16:11 -0400

Katriel,

> ​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?
Note that CT does not require all Monitors to be third parties; 
self-Monitoring is a viable
option and avoids the problem of detecting a misbehaving (3rd party) 
Monitor. In that
context, having multiple Monitors sign something about a cert may not 
work out well.

The Audit function notifies Monitors (and browser vendors, indirectly?) 
about log
misbehavior, not clients. I say this because clients (browsers) get log 
metadata
from browser vendors, and thus most will not need to consume data from 
Auditors.
Monitors need audit info to decide whether the logs they are watching 
are misbehaving,
and browser vendors need to know the same, to properly manage the log 
metadata
distributed to users of their products.
> 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?
Monitors watch logs for entries of interest to the Subjects that serve. 
(This is true
even for self-Monitors.) So, it's not clear on whose behalf a Monitor 
would sign info
about an STH.

Steve

---

From: Stephen Kent <[email-masked]>
Date: Tue, 6 Oct 2015 10:18:42 -0400

Eran,
>
>
> On Wed, Sep 30, 2015 at 2:35 PM, Katriel Cohn-Gordon <[email-masked] 
> <mailto:[email-masked]>> wrote:
>
>     ​ 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?
>
> 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?
I've proposed what I believe Monitor behavior should be in several 
messages, and it is now
codified in the arch doc.
> * 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.
I'd add Subjects here too.

Steve

---

From: Bryan Ford <[email-masked]>
Date: Thu, 22 Oct 2015 16:59:29 +0200

Hi Tom, picking up your thread from earlier this month (again sorry for the long delay)…

> independent entities?  Is this understanding correct?

No, at least in its current form there is technically particular threshold that needs to be decided on ahead of time, left unchanged, or even agreed on by everyone.  The leader/proposer (e.g., log server) produces a message, collects “partial signatures” from any subset of the M co-signers it deems to be online and available, and works with them to produce a collective signature that documents exactly which subset of the M potential co-signers was actually present and contributed to the signature.  By implication, it’s obvious from the collective signature how many of those co-signers were present, so if the leader (perhaps maliciously) tries to leave a bunch of honest participants out in one or more rounds, there’s lots of opportunity for anyone to notice and ask questions.

In essence, the collective signing protocol as it stands produces something semantically equivalent in information content to up to M individual signatures, but merely “optimised” for a full rather than empty set of co-signers.  If all M signers are online and participating in a given signing round - as I would hope and expect to be the expected normal operating practice - then the collective signature is basically equivalent in size and verification cost to a single individual signature.  The size and verification cost of the collective signature then basically increases as more and more nodes “go missing”, basically because the collective signature needs to include (verifiable) metadata about the missing nodes allowing signature verifiers to “subtract out” those nodes’ components of the composite public key.  In the worst case, if the leader really wants to produce a collective signature with only 1 or 2 nodes actually participating, then the collective signature will get big. :)

We do have an alternative design we’re working on that always produces constant-size signatures whose composition doesn’t vary depending on the participants, along the lines of traditional threshold crypto based on Shamir secret sharing but just more scalable.  That’s very useful for other things, but indeed requires you to pick and agree on a particular threshold from the start, and doesn’t leave a documentation trail indicating who was “missing from the role call” in each round.  So for present purposes the current approach actually seems preferable to me, if a bit less crypto-whiz-bang.

> people generate their own key shares and then assemble them into a

No one needs to generate key pairs on behalf of everyone else: all participants generate their own key pairs independently and keep the private parts secret, just as in the M-individual-signatures case.  The main restriction is those keys all have to be generated in an agreed-upon cryptographic group: e.g., P-256, or P-something-else, or Ed25519 or Goldilocks.  Since elliptic curves used for signing are pretty standardised anyway (unlike the DSA practice of having new group parameters for each key pair), this doesn’t seem like a significant issue.

> shares? This would change the public key of course, but I'm assume we

I’m assuming the members of M are reputable, relatively stable independent organisations who are able and committed to keep servers alive at least most of the time, so that it should be a fairly exceptional event (and a moment of public shame!) for such a witness/co-signing server to go AWOL even for one signing round.  Of course an organisation running a witness server could just suddenly go belly-up or decide to stop providing service without notice, but that will just mean that a “witness 15 was missing” metadata record will be present in each collective signature record signed with that group configuration until the next time the group configuration is updated.

I envision the group configuration being updated not too often, e.g., preferably like once a year or at most once every few months.  One obvious avenue for group configuration updates is simply to handle them the same way that updates to root CA certs, root log server certs, and other roots of trust are handled in web browsers: i.e., just align root-configuration updates with the software update cycle.

Would a witness group configuration need to be “valid for 3 years” like root certificates?  That’s one possibility that might not be unreasonable, but collective signing gives us other interesting and potentially better alternatives.  For example, if a witness group’s composition changes every year or every quarter, then the last thing the leader might do in the prior group configuration is use it to collectively witness and sign a successorship record, stating what the next group configuration record is.  The successor group configuration can have not only added and/or removed members, but also all the remaining members can generate brand-new key pairs for each successive group configuration, and those participants can immediately scrub the private keys they were using in the prior configuration.  Clients who might be running months- or years-old web browser versions or whatnot can still “chain forward” by following multiple such successorship links from the last configuration they know and trust to the latest configuration.  This would thus not only ensure that old clients can transition to new roots of trust more seamlessly than they do now, but would also allow all the keys used in collective signing to have more like 1-year (or 3-month) lifespans rather than the currently typical 3-ish-year windows.

> enough that compromising N orgs would be difficult.

Hmmm, could you point out which slide you’re referring to?  Might be a typo.

> engineering aspect, but from a humans-interfacing-with-humans aspect.

The organisational and incentive question is indeed important as well.  Another way to view this, though, is not just as a way to protect users/clients as they validate an authority’s (e.g., CA’s or log server’s) statements, but also as a way for the authority to protect itself by disincentivizing anyone who might want to work hard to steal their private keys and use them (in whatever fashion) in secret.  Currently, if a hacker or some country’s spy agency manages to acquire those private keys by whatever means, they can be used in secret, probably in a completely different part of the world and unbeknownst to the genuine authority, to synthesise entirely fake “views of the world” for targets on attacker-controlled networks for example.   CT currently makes such secret misuse a bit harder but by no means impossible.  

But if all of the authority’s statements (e.g., STHs) are supposed to be collectively signed by a substantial fraction of a large and diverse set of independent participants around the world, the potential value to an attacker of the authority’s private key is greatly diminished: even once the hacker or spy agency gets the key, they won’t be able to sign a statement that clients will accept unless they also get it witnessed and co-signed by a significant fraction of the same group of witnesses, at which point it’s pretty certain the misuse will be detected immediately in a most public and potentially embarrassing fashion.  

In essence, it’s a way for authorities who sign public statements to de-value their private keys as hacking targets, disincentivizing hacking or other forms of “acquisition” attempts in the first place by making the private keys effectively worthless for doing anything in secret.  Perhaps an “enlightened authority” might even be willing to pay some kind of tiny trickle of compensation to the (reliable, reputable) group of witnesses it contracts with to help collectively protect it in this fashion.

> test network to join - I have a spare box I would set to participating

Sounds great, thanks for the offer!  The code is already online (https://github.com/DeDiS/cothority), and we’re working hard to get it stable and well-documented enough for multi-site testing; we’d love to have you (and anyone else interested) join into a test “witness cothority” we’re in the process of getting set up.

Cheers
Bryan

---

From: Tom Ritter <[email-masked]>
Date: Fri, 23 Oct 2015 13:58:45 -0500

Thanks for this, I was pretty far off from my assumptions!

> In essence, the collective signing protocol as it stands produces something semantically equivalent in information content to up to M individual signatures, but merely “optimised” for a full rather…

Oh.  Really cool!  I think the larger size of signatures might be an
issue for SCTs, but like you mention, doing it for STHs seems quite
reasonable!

> No one needs to generate key pairs on behalf of everyone else: all participants generate their own key pairs independently and keep the private parts secret, just as in the M-individual-signatures…

Agreed; nice!

> I’m assuming the members of M are reputable, relatively stable independent organisations who are able and committed to keep servers alive at least most of the time, so that it should be a fairly ex…

I am less sure about that.  The more expectations placed on an
organization around uptime and reliability - the fewer organizations
you'll have participating.  I have to think a more successful model is
"Run this software for a month, get used to it, and then we'll add
you.  Keep it up as best you can, and if you have problems keeping it
up, we might remove you on our quarterly membership changes."

> Would a witness group configuration need to be “valid for 3 years” like root certificates?  That’s one possibility that might not be unreasonable, but collective signing gives us other interesting…

Chaining is good, requiring software updates doesn't seem very good.

> Hmmm, could you point out which slide you’re referring to?  Might be a typo.

Can't find it, must have gotten confused about your intro slide.