ATProto Messaging Identity Delegation

WG E2EE
1

Hey folks. Earlier this year we proposed a first step of interoperability as the delegation of DID to a single messaging identity (at a time), and offered Distributed MLS as a solution to concerns about centralized state and MLS.

Building out those ideas, we’ve since launched our beta, and described in detail how it’s implemented and some of the lessons we’ve learned along the way.

To recap the way I saw the interoperability problem in March:

We need alignment on the following components for inter-user interoperability

  1. Delegation from ATProto DID to user-controlled messaging identity keys

  2. A scheme to form encryption sessions with those identity keys

  3. Ways to transport messages encrypted with those encryption sessions.

  4. Schema for the message contents

For apps serving the same user to interoperate, they need to further cooperate to

  • Communicate changes to the user’s trusted recipient set

  • Synchronize message history

I don’t think this needs to implicate inter-user interoperability, but I’ll note that this is a complex feature set, akin to what Facebook launched for messenger, and the challenge we (and I expect you all) face is how to roll out that complete feature set incrementally but securely

We are an implementer of E2EE messages with ATProto identities. We have been building from the beginning for users on independent infrastructure, with independent clients, to be able to talk to users on Germ. We think we have solutions to offer in this space, but we also want to ensure the basis of interoperability matches the security guarantees of E2EE messaging like Signal. We do not think we need to regress security to accomplish interoperability.

Our experience building our ATProto integration indicates we need an interoperable mechanism for users to signal changes in trust (like the safety number warnings in Signal), and we continue to think the serial delegation of ATProto DID to a single identity is the correct abstraction.

Threat model

We should assume that the default implementation of PDS is a persistently online entity not under the user’s physical control, which users authenticate to with resettable credentials. Delegating PDS keys to the server was an explicit choice to allow users to have that low-friction experience of delegating key management. Exceptional users may take control of their PDS keys, but we should not base security assumptions on exceptional users, nor require users to reclaim PDS key management to get equivalent security guarantees to Signal. For example, It should not be possible for a compromise of the user’s PDS credentials (e.g. Bluesky password + 2FA) to enable eavesdropping on ongoing conversations.

Consequently, we should treat the user’s PDS, and the apps they use for messaging, as distinct but complementary entities. This is useful - it separates the sharp edges of key management from a recoverable, user identity. Thankfully, this is basically the shape that Signal has - delegating from a recoverable, low-trust phone number to high-trust device-bound keys - so we have familiar UX patterns to fall in on.

User Warnings about Changes in Trust

The existing trust model on Signal has the following characteristics:

  • Users trust on first use when contacting someone on Signal

  • Users can inspect and compare the cryptographic identities they are conversing with, and as.

  • Users are alerted if the cryptographic identity changes from what they previously verified or have been communicating with.

So while Alice does not have to reason about Bob’s adding or removing of linked devices, or even migration to a new phone, Alice is notified if Bob re-registers on a new phone.

We conclude that

  • It is possible, likely, and useful for users to be informed of changes in other users’ security state
  • For users to make sensible choices, clients need a mechanism to allow for trusted changes of recipient(device) set, to more fully distinguish untrusted changes of device set.

This is the threat model and UX intent for our recommendation that ATProto delegate to a single messaging identity key at a time. This isn’t a restriction to a single device - it’s an abstraction of the user’s trusted device set into a single identity for others to reason about. Different clients can pursue different strategies for implementing multiple apps and devices behind this identity.

This simple abstraction allows for a simple rule for presenting security boundary alerts. If Alice’s PDS publishes a new delegated identity key, without cross signing from the predecessor key known to Bob, Bob should treat it as a security boundary and warn the user.

4 Likes
2

@markmx.bsky.social since you didn’t mention it here, I think it’s worth pointing out that your project, and thus the source of these observations, is Germ (complimentary)

2 Likes
3

:man_facepalming:. Thanks Paul!

I had to take out some more linked content since discourse wouldn’t let this new user spam so many links :stuck_out_tongue:

This is our write up of Germ’s integration with AT proto:

And the Facebook messenger E2EE white papers:

2 Likes
4

I upgraded your user level manually but will look at some other options to get us there. ATProto OAuth is a nice spam bot barrier already.

Welcome Mark, thanks for sharing.

2 Likes
5

Mark, thanks for writing this up, it gives us something concrete to discuss.

It should not be possible for a compromise of the user’s PDS credentials (e.g. Bluesky password + 2FA) to enable eavesdropping on ongoing conversations.

I agree on this. So long as each new device generates it’s own a new key pair (private kept to the device) this is can be accomplished. (There is a question of how to make the new device pub key an authorized key which is my next question.)

Based on your approach, when a user adds a second device:

  1. How does the new device become part of the “trusted device set”?
6

Do you have any thoughts on how to solve the message transport in a way that doesn’t lock users into a specific app?

7

For those reading this that are new to building decentralized E2EE messaging, I want to point you to two in-the-wild projects mentioned in a post I published last spring:

Both of those projects have a well defined public identity key (Nostr pub key, XMTP Inbox key). And both support multiple devices/application installations by delegating authority (via signing with the primary identity key) to a key pair created for that device/installation. I point this out to establish a norm for how this is done.

With ATProto, the user is cryptographically known by the #atproto entry in the DID:

"verificationMethod": [
    {
        "id": "did:plc:wtk7wq3y3i64z3umv44eutuj#atproto",
        "type": "Multikey",
        "controller": "did:plc:wtk7wq3y3i64z3umv44eutuj",
        "publicKeyMultibase": "zQ3shb54hTooamG8BmJ8gVa9K5pbZcaAweBKqfGwT7X9F92mZ"
    }

Any update to the PDS is signed by this key, and assumed to have been permitted by the user that controls this ATProto identity. If we create an NSID to hold delegated messaging identity keys in the PDS, then we can assume the user authorized them. I don’t see how delegating to a singular messaging identity key helps other than to create a weird mechanism to lock out multiple apps from doing ATProto messaging.

It should be noted, that from a UX perspective, Germ could still choose to provide the “trust signals” to the user when either the DID key changes or there are any updates to any delegated messaging identity keys.

Also, WRT to storing delegated messaging identity keys in the PDS, you could even take this idea a step further (which I did not do in AT-SMS) and create an NSID for KeyPackages, and each app could be sure to refresh KeyPackages as they are consumed.

8

In those comparisons, where do the private keys reside?

I think you are carrying over a linguistic presumption from cryptocurrencies that users control their private keys, hence users are equivalent to their chain identities.

The norm in ATProto is that users delegate the PDS private keys to another agent, like users do with Coinbase. So it is incorrect to say that users act by using the PDS keys. They act by authenticating to the PDS, and the PDS uses the private keys it has been delegated. The entire scheme discussed here of transparently delegating back from PDS keys to a key that is asserted to be under user control, is to cross back over that trust boundary.

1 Like
9

I ask you to refrain from, as you are here and have on Bluesky in explaining your rejection of MLS, attributing malice to the complexity of key management for end to end encrypted systems. It is hard enough to build these systems already, I don’t have time or interest, in making more complex than it needs to be.

My overarching goal in this WG is to simplify the interface between users, so that we do not foreclose different modes of cooperation among a user’s own devices by requiring that Alice participate in Bob’s manipulation of his device set. Bob, go figure it out for yourself amongst your apps, and with the help of the PDS, tell Alice what she needs to know. I don’t have fully formed thoughts on the transport interface, but I expect a similar abstraction.

The normative experience - for Signal, iMessage, Zoom, and Matrix, off the top of my head are

  • When I add a new device and I am already registered for messaging, one of my already registered devices must approve the addition, or else I blow away the previous registration and start from scratch. It is not safe for an entity outside my trusted set to add itself to my trusted set.
  • You can look to each of these systems for inspiration on how to implement inter-app cooperation. They’re subtly different. Zoom has, IIRC, high and low trust devices (I think conference phones, for example). Signal also doesn’t have a flat device set - you have one phone, which can delegate to several linked devices. Presumably the cryptography follows that use case.

Yes, the system could be a lot simpler if you assumed users had custody of their PDS keys. That is not an accurate assumption for the default user, and I am pointing out the ways that will fail them.

If you assume for your users the exceptional case that the user is congruent to their PDS, then you can easily fit in the single key abstraction by delegating to the verification key, never changing it, and proceeding with the rest of the certificate scheme in AT-SMS. That self-delegation says exactly what you mean to say - my messaging boundary is exactly my PDS - anything the PDS authorizes is my trusted set.

10

In those comparisons, where do the private keys reside?

Which private keys?
X25519 private keys are on the device, otherwise it’s not E2EE, right? (this is not a carry over from crypto, this a carryover from Signal) The public side of the X25519 key is in the KeyPackage In the case of XMTP, the "Messaging ID Key” signs the KeyPackage. So:
MailBox key (think PDS Key) – signs –> per-device Messaging ID key – signs –> KeyPackage

The norm in ATProto is that users delegate the PDS private keys to another agent, like users do with Coinbase. So it is incorrect to say that users act by using the PDS keys. They act by authenticating to the PDS, and the PDS uses the private keys it has been delegated.

We are building AT Protocol messaging, right? Control over the PDS key, is at the heart of control over the ATProto identity?

I appreciate the extra level of concern you are bring to this and think there is a way to still add this additional security with apps like Germ, but it feels like it is straying from AT Protocol fundamentals.

11

in explaining your rejection of MLS, attributing malice to the complexity of key management for end to end encrypted systems.

Please do not attribute my critique of MLS (TreeKEM) or design elements in this forum to malice on the part of the designers or you. For MLS, it is the byproduct of the design, not out of malice, but because the primary use cases of nearly every one involved were all centralized services.

The biggest threat we face is the power of centralization so I will not shy away from being vocal about design choices that risk creating more centralization (even if unintended). I am here because I very much want to create a decentralized alternative to WhatsApp (in the same way AT Protocol is decentralized). If it will create centralization, I try to point it out (eg. dids, matrix/mastodon ids) I don’t assume malice is at the heart of most of these decisions.

Maybe in the future we jump on a call to talk through this stuff to ensure motives are obvious.

Yes, the system could be a lot simpler if you assumed users had custody of their PDS keys.

I think I am missing something fundamental in my understanding of what you mean by this. Let me ask a question to try and discern it. Don’t I have to assume everyone with a Germ link on their profile was controlling the PDS when it was added?

12

Thank you

So, the XMTP and Nostr identity keys are device-bound?

Does it change our assumptions if the identity private keys are instead held in a virtual machine that Bluesky or Blacksky are operating?