"Failed to decrypt message" is broken by design

Certain messaging applications¹ have the ability to produce an error message as such:

Failed to decrypt message.

or,

Message was not encrypted for this device.

If your messaging application has the ability to produce this error message under normal operation, it is fundamentally broken.²

Why?

For this message to arise, two conditions must hold:

1. You are trying to decrypt a message for which you do not hold the key
2. This message somehow came into your hands

For this to happen (non-maliciously), such a thing as an untrusted key that still gets shared with your counterparties must exist. For a message to wrongfully fail to decrypt, a sender must lack trust in a key which the recipient was meaning to trust. This possibilility also implies something worse: the possibility of trust in a key which the recipient was not meaning to trust.

There is no good reason to allow this possibility. The idea that a sender would be better posed to make judgements about which devices of the recipient are and aren’t trusted is ludicrous. If the recipient has authorized a compromised device, the jig is up anyway.

There is, however, a bad reason: the deliberate goal of allowing clients to create half-trusted states, so they can add a new device 30 seconds quicker.

That’s a lot of effort to replicate the worst aspects of PGP: PGP treats the email address as an inherently unreliable identifier and therefore has to bolt on a new identifier (with its associated Zooko’s triangle-like problems). Here, somebody for some reason decided to induce such unreliability into a system that was built from scratch.

And what did it buy them? Even Telegram defaults to adding new devices by either scanning a QR code from or entering an OTP code sent to a previous device. Even Gmail demands you complete a 2FA challenge if you log in from a new device. Allowing anybody with valid credentials (or control over the server!) to add a new key only makes sense if:

1. Your users keep all their passwords in their head (meaning no password managers, meaning password reuse)
2. Your users frequently lose access to all of their devices at once
3. This happens often enough you don’t wish to make “cold start” an exception state that effectively requires the account to be deleted
4. You are allowing unencrypted messages to be sent, presumably as a crutch for the entirely self-inflicted unreliability of the encrypted ones

In other words, if you are Matrix.

Isn’t this mainly due to desyncs?

One objection could be that Matrix already sort of tries to do this. Using one device, you can mark other devices as trusted, which in principle should solve the problem.

There are two points at which this objection fails to survive contact with reality:

1. Have you ever used Matrix? This problem very, very clearly is not solved!
2. This doesn’t actually solve the key desync issue; what would be needed is to copy over the ephemeral keys (session keys/prekeys) to the new device, but in a “slave state” such that it does not attempt to take command over them and ratchet, but rather just has its key added atomically.

What should be done instead?

Devices should only either be fully trusted or not authenticated at all, and each user must have the final word on deciding which devices are trusted. There are a few different practical ways of doing this:

1. Master device, the Signal approach. There is one device that gets to handle key management and add/remove others, and the others just get to decrypt.
2. Flat system, which is somehow done everywhere except for E2E: All devices get to add/remove others. Practically, this could be accomplished by just sharing the decryption key material internally, possibly coupled with a ratchet. This does have nasty properties when it comes to compromise isolation, but some would argue compromise isolation is a chimera anyway.
3. Threshold system, probably not done anywhere: A quorum of devices get to add/remove other devices. Practically, this would need some kind of a consensus system and a ledger.³

Another implication of this is that you must never allow login with password: Once you’ve first registered, you will need a pre-existing device to copy over keys, which will also take care of authentication. A password is no good, since it doesn’t allow you to sign or decrypt anything, and so has no reason to exist.