Public Key Infrastructure

[paragonie-scott]

Just to document what I'm currently working on, which is a blocker for some of the other high priority issues:

I'm building a system that allows developers using barge to upload their public keys, which will then be synchronized out to the entire network.

Threat Model

We want to protect against these threats:

• An attacker capable of compromising the package server (ours is called the Skyport) who wants to replace the public key for a specific supplier, silently, and only for specific clients. (If this succeeds, it allows them to produce forged automatic updates for that supplier.)
• A nation-state attacker armed with the capability to perform legal coercion attacks against our infrastructure, who might want to perform silent targeted attacks.

This does not try to protect against:

• Signing key theft.
• Malicious package developers.

The goal is to place less automatic trust in the infrastructure that updates are delivered through, and instead encourage informed trust decisions for the developers of the updates themselves.

Solution

We will maintain a Merkle tree of all key transactions (insert/delete) from the day version 1.0.0 is released. Every Airship that communicates with our Skyport will maintain a mirror of this data structure.

Every Airship operator will be able to add their own notaries whom they trust to vouch for the authenticity of this Merkle tree.

Upon a new key being created, or an old key being revoked, each Airship will:

1. Download the new key information and the Merkle root for each update.
2. Select a random notary from their individually trusted peers. (The package server MUST have no record of who trusts which notaries.)
3. Send this chosen notary a challenge nonce and sequence number for the latest node (which the notary will sign along with the corresponding Merkle root).
4. Verify the Ed25519 signature of the notary's response and check that the nonce is the same one that was sent.
5. Repeat steps 2-4 for several notaries (if more than one is configured).

If the Merkle root doesn't match the one your notaries send for that sequence number (or all of your notaries have no knowledge of this sequence number even after they poll the server), it will discard one backtrack and start over until it finds a match. If none are found, all updates are discarded.

To identify attacks, all mismatched roots can optionally be broadcasted to our security team. ("Scream bloody murder.")

Keyggdrasil

Name: Key + Yggdrasil, which in Norse mythology is the World Tree.

This is an (currently not finished) implementation of the above solution. We are taking inspiration from Convergence and Certificate Transparency to provide a decentralized verification mechanism.

[paragonie-scott]

The past 8 commits were largely unrelated to this effort. Instead, I was trying to make sure we have little technical debt moving onto version 0.2.0.

[paragonie-scott]

Ok, the workflow goes something like this:

1. A developer using barge creates/revokes a new key.
2. The key update message is transmitted to the channel.
3. Airships will routinely query the channel for key updates, and maintain a mirror of the Merkle tree of these updates.
4. When one is found, it will select at least one random "notary" to verify they see the same Merkle tree.
   • A notary is another Airship that this Airship trusts to authenticate the message they receive.
   • Notaries will in turn notify their peers to ensure the update propagates throughout the network.
5. If all notaries agree with what the user sees, the key-update will be applied.
   • If it's not the supplier's first key, it will also require the update to have been signed by one of their master keys.

This just ensures consistency and history-immutability across the network. A shared, append-only data structure with decentralized verification makes silent targeted attacks impractical. (You would need to be able to generate collisions in a growing BLAKE2b tree to attack this scheme.)

---

What's left to do:

• Verify master key signatures.
• Apply key updates to the local key store.
• Test thoroughly.

[paragonie-scott]

I'm marking this as closed. All we need to do is "parse the validated updates to add/remove keys" and then test.