AnarchKey: Experimental PKI for Securing Software Updates

[paragonie-scott]

EDIT: If you want to see the early client-side implementation of this idea: https://github.com/paragonie/herd

---

This was originally posted on Patreon but their editor is suboptimal.

---

This is probably months away from seeing the light of day, but I'm trying to design an experimental Public Key Infrastructure (PKI) that does not rely on trusted Authorities, and instead depends on an independently auditable append-only data structure to be secure.

You may be familiar with Chronicle.

This idea is to use a Chronicle, or a local replication of a Chronicle, as a central source of truth for both:

• Update files (and their Ed25519 signatures)
• Changes to vendor-publickey pairs
  • New key registration
  • Old key revocation

In order to for this to work, I'll need to build a separate library that uses an array of Chronicles (ideally, two or more replication instances that fallback to the upstream source as a last resort to minimize network congestion) as data sources to add/remove keys and append update messages to a local database.

As an optional feature, core developers' keys may be allowed to authorize replacement keys for vendors whose keys were lost (e.g. due to poor backup strategies) and/or to revoke public keys if the vendor's secret key was compromised. This will be disabled by default, but some platforms (WordPress, Joomla!, etc.) may elect to enable it.

At the end of the tunnel, this work will allow us to build secure automatic updates into every open source PHP project in 2018.

Furthermore, I intend to make this new library (or a fork of it) work on PHP 5.2.4+ (thanks to sodium_compat), so it can be considered for inclusion in WordPress (assuming ticket #39309 sees some progress on their end).

I've attached some of the notes I've written down about this experimental design. In the coming weeks, I'll be soliciting feedback from other security/cryptography experts and then maybe building a proof-of-concept for the missing piece of the puzzle.

That's all I have to share at the moment. Let me know what you think about this initiative.

[defuse]

By checking the chronicles does this tell me that all the other chronicles have seen the same update file (or at least a file with the same hash), or just that everyone has seen the same public keys?

[paragonie-scott]

Yes. Both public keys and updates are chronicled.

The general idea is that people will use their webhost's replication Chronicle rather than the upstream Chronicle. Since replication instances verify the hashes and signatures of each record they copy over, this makes querying a replica more reliable of a defense against targeted attacks (especially if the user and the owner of the replica have a business relationship that disincentivizes malicious behavior).

However, for the sake of satisfying more paranoid threat models, I'm going to add support for querying multiple replicas to ensure they all see the same ledger entry. Users will be able to configure what is an acceptable level of quorum ("at least 1 other", "at least 51%", or "unanimous" all being acceptable answers depending on the trade-off desired).

[burdges]

You've looked at http://theupdateframework.com/ and related discussions https://github.com/rust-lang/crates.io/issues/75 right?

Just fyi, I want to write up and implement a forward-secure signature scheme for DVCSs eventually. In essence, it goes:

All repositories, or maybe all branches, have an ephemeral signing key S_i = si G. Anytime you commit the repository makes up a new keypair S{i+1} = s{i+1} G, signs (S{i+1}, H(signing key log head), H(commit)) with s_i, adds it to a signing key log as the new head, and erases the private key s_i.

These signing key logs are shared with push, pull, etc., but obviously rebase, etc. can never alter signing key log, so do expose more metadata about your work flow. In exchange, you have a completely automated signature scheme for which one cannot invisibly tamper with the past even if the dev machine is compromised.

A developer with no knowledge of PGP, etc. would still automatically sign all commits. In the future, they could become more interested in security and publicly verify one ephemeral signing keys in their repository's signing key log, which transitively verifies its entire signing key log. You could automatically sign builds with the current signing key log head too.

Also, repositories would de facto sign the signing key log heads when doing pull, etc., so one can trace the interactions between repositories. In fact, package managers like cargo could have repositories sign the signing key log heads for their dependencies, or users could do it manually for other projects , so one can trace the signing key logs across projects too.

There are reasons the signing key logs might fork, break, restart, etc., like a developer merges between copies of a repository, so you cannot be too strict about verifying anything, but it makes anything weird visible, improves forensics in the case of bugdoors, etc., and makes good security practices more asynchronous.

I'd considered wanted to add this to Pijul but who knows git might be easier. Anyways the larger task would be formalizing the security properties.

[paragonie-scott]

That's an interesting approach, adding signing to the DVCS itself. You can sorta get most of the way there yourself today by using git commit -S, but as you mentioned, that requires knowledge of PGP etc. The idea of the system I'm designing here is to secure tags/releases, not individual commits. Commit signing would be a neat value-add.

I'm familiar with TUF, and have mentioned it in the PIE blog before.

All repositories, or maybe all branches, have an ephemeral signing key S_i = si G. Anytime you commit the repository makes up a new keypair S{i+1} = s{i+1} G, signs (S{i+1}, H(signing key log head), H(commit)) with s_i, adds it to a signing key log as the new head, and erases the private key s_i.

What signature algorithm did you have in mind? It sounds like the goal is to build tree of one-time signatures, in which case, SPHINCS may be worth looking into.

There are reasons the signing key logs might fork, break, restart, etc., like a developer merges between copies of a repository, so you cannot be too strict about verifying anything, but it makes anything weird visible, improves forensics in the case of bugdoors, etc., and makes good security practices more asynchronous.

Yeah, that's why I don't sign commits, but I do sign tags (and therefore, releases).

[burdges]

An Ed25519 signature is only 64 bytes. SPHINCS signatures are like 41kb, so suitable for signing large releases, but not individual commits. You could build smaller single-use hash based signature schemes, but they'd break if you copied the repository.

[paragonie-scott]

I meant delving into the components that made SPHINCS (HORS, etc.) and referencing prior art, rather than using SPHINCS wholesale. I think SPHINCS+ and Gravity-SPHINCS would be better recommendations for alternative implementations.

Ed25519 is a good choice. I'm not 100% sure what you're hoping to gain from ephemeral signatures here. Ed25519 already does deterministic signatures safely (no nonce leaking).

[burdges]

You gain forward security: A compromised signing key cannot be used to fake signatures either forward or backward in time.

In fact, these signing key can be truly automated as they not be password protected: A developer who does not understand security can simply backup their repository to an unencrypted drive. If a hostile party steals it then they only gain the ability to sign a fork that starts at that point in time.

This attacker could pull in later commits of course, but it'd be obvious that they're working from another copied repository. I think forward security is largely a forensics tool in the signing context, while it elevates passive attacks to active attacks in the encryption context, but if you're cross signing between repositories then frequently an attacker must do active attacks to get those signatures.

[paragonie-scott]

This sounds interesting. I think I'd like to help get it to land in a DVCS, but it's a little out of scope right now.

[burdges]

Yes, I didn't meant to derail too much, just mentioned it as an aside. And yes SPHINCS is a nice choice for large things.

[paragonie-scott]

No problem at all, I'm happy you mentioned it. It could save a lot of headache down the line.

[JoshHarmon]

This might be getting a bit more into the implementation weeds than you were looking for, but AIUI, you're hoping that applications will use a hosting provider's Chronicle (presumably so that the "root" chronicle doesn't get murdered by millions of sites update-checking it to death). To me, this suggests that the provider would modify the source package (i.e. for autoinstallers and whatnot), which seems to me that it would break the ability to have true replication across the root chronicle and other providers (as diff providers would modify whatever chronicle config is present in the source for their own mirror, thus making the package different than what other Chronicles may present).

Hopefully you get what I'm trying to say (I have no idea if my brain is creating coherent thoughts at this time of the night). Am I missing something obvious?

[paragonie-scott]

To me, this suggests that the provider would modify the source package (i.e. for autoinstallers and whatnot), which seems to me that it would break the ability to have true replication across the root chronicle and other providers (as diff providers would modify whatever chronicle config is present in the source for their own mirror, thus making the package different than what other Chronicles may present).

I just open sourced the client-side implementation of this, so that might help!

https://github.com/paragonie/herd (very early WIP)

All a hosting provider has to do is append their replication instance to the appropriate data/config.json file. i.e. https://github.com/paragonie/herd/blob/c884a2f6b4088815d301cd0290e2095239c6cf71/tests/config/valid.json

Replication instances aren't as simple as "you have a dedicated Chronicle that can only replicate data". It's actually a separate feature built into a Chronicle, with a special URL: https://chronicle-public-test.paragonie.com/chronicle/replica

You can have a local Chronicle that serves one purpose but also mirrors dozens of other Chronicles. It's like having separate git repositories, the streams never cross.

Herd is aware of this, and queries the replicas (which have a distinct URL and public key, but should serve identical contents). You can configure a Quorum threshold as well, which allows you to say "I listed 10 replicas and want at least 6 of them to agree".

The hosting provider doesn't need to provide their own signatures, modify anything that breaks hashes/signatures, etc. They can literally toss up an instance, configure it to replicate, and then give their URL and public key to their customers.

[paragonie-scott]

Update: Herd is almost API-stable, which isn't too surprising given its limited scope. The CLI is tentatively named Shepherd but I might just shorten it before I tag the first release.

# Run regularly (e.g. cron script)
path/to/shepherd transcribe

# Get JSON responses from the CLI API that contain details about each update
path/to/shepherd list-updates sebastian comparator
path/to/shepherd get-updates sebastian comparator 2.1.1

So there are only two problems left to solve:

1. Building the tooling/protocol for developers to sign their own updates (and get this signature/etc. into Packagist).
2. Get Packagist to stream updates/etc. into their Chronicle. https://github.com/composer/packagist/issues/797

I've considered some approaches for the first stage of the problem in a way that will work with different DVCS products, but ultimately, the best approach is going to be to stage signatures locally and then send them to Packagist/etc. directly.

Therefore, the next stage: A simple composer plugin that tentatively is called composer release, that generates a signed metadata blob to a staging directory and then ships it off to configurable URLs (via some Packagist-supported authentication; e.g. auth tokens).