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

[Bryan Ford <[e-mail]>]

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

On 04 Oct 2015, at 18:37, Tom Ritter <[e-mail]> wrote:
> 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?

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.

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

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.

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

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.

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

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

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

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.

> 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
> =)

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