"Unable to decrypt: The sender's device has not sent us the keys for this message." (The UISI bug)

[richvdh]

Update 2023-02-27

This issue is now superceded by element-hq/element-meta#245

Historical information follows.

---

This message (or, less often, the closely related "OLM.UNKNOWN_MESSAGE_INDEX") can be caused by a number of things. This bug serves as a reference to the reasons we know about.

• You logged into your device, or joined the room, after the message was sent. This is sort-of by design, though Hide undecryptable messages which predate your device's participation in a e2e room #2258, Let devices request keys to decrypt past history for a room. element-meta#647 and Let megolm session keys be available to devices added by invited users since the point they are invited #2713 are relevant.
• The sender has blacklisted your device. This is definitely by design, though see Improved communication to recipient that the sender didn't want you to see their message #3831 for improving visibility on this.
• The keys haven't arrived yet. Patience you must have.

Client-specific bugs:

• Olm is prone to race conditions across multiple tabs #2325 [olm is racy when riot-web is used in multiple tabs]
• vector-im/element-web#3309 (also on android/ios) [We can still throw away one-time keys which have messages in-flight]
• We should prioritise established olm sessions over half-open ones when sending outgoing messages #2783 (also on android/ios) [prioritise established olm sessions over half-open ones]
• different devices with the same curve25519 key confuse the olm layer element-meta#1143 (also on android/ios) [different devices with the same curve25519 key confuse the olm layer]
• Stuck in a loop generating and failing to upload one-time keys #4216 / Stuck in a loop generating and failing to upload one-time keys riot-android#1289 / Stuck in a loop generating and failing to upload one-time keys element-ios#1256 [We throw away all our one-time-keys and replace them with new ones]
• Stale device lists when users re-join e2e rooms #4983 / [e2e issue] Decrypt error related to new device creation  matrix-org/matrix-ios-sdk#340 / Stale device lists when users re-join e2e rooms riot-android#1603 [yet another device list sync bug]
• Race in decrypting events causes UISI #5001 (fixed riot-web 0.12.5) [race in decryption]
• Check that device list is updated correctly when encryption is turned on in a room #2672 / Stale device lists #2305 / device list update is *still* racy #3796 / e2e : Stale device lists  element-ios#955 (fixed riot-ios 0.5.0) / E2E: Stale device lists riot-android#863 (fixed riot-android 0.6.10) [racy device list sync]
• Make sure we process to-device messages before generating new one-time-keys #2782 [process incoming messages before uploading new keys]
• We sometimes fail to decrypt events which arrive in the initialsync #2273
• network blips during device key download stop megolm key-sharing working #2562
• [e2e] Corrupted OlmSessions riot-android#799 (fixed, but you may still have broken Olm sessions because of it)
• Out-of-sync olm sessions riot-android#1209 (fixed in riot-android 0.6.10, but you may still have broken Olm sessions because of it)
• We don't appear to be retrying /sendToDevice requests matrix-org/matrix-js-sdk#1866 (fixed for room keys at least)
• Might not be using available session backups for some reason, and we don't re-check them when attempting to fix UISIs Cannot decrypt old message #20461 When requesting keys from other sessions to attempt to resolve decryption errors, also double-check key backups in 4S #21026

Protocol/server things:

• possible to run out of one-time-keys on rarely-used devices #3187
• Users whose servers were unreachable when you logged in will send you undecryptable messages matrix-org/synapse#2165
• if your server goes down, when it comes back you get messages long before the keys #3754
• Restoring a phone (or browser tab) from backup will break Olm if the other device still exists. #3822
• one-time-key upload/claim is racy #3868
• sometimes the sending device doesn't seem to know about some recipients in the room #3846 [sometimes the sending device doesn't seem to know about some users in the room] (hopefully will be fixed by state resets)?
• Failures uploading one-time keys riot-android#1208 (fixed in synapse v0.21.0-rc3)
• sometimes we use an out-of-date server for send_joins matrix-org/synapse#2418 (joins can seed from servers with stale state)
• vector-im/element-web#6989 Device lists can get out of sync

Unexplained:

• to_device message went missing from vdh->matthew with megolm session data #2711

[ara4n]

For anyone reading this looking for a workaround, the best advice currently is that if you suddenly find yourself unable to decrypt messages from someone, ask them to open up your contact details on their client. This should force their Riot to resync its copy of your device list, increasing the chance that the next message sent will actually be encrypted for your current device.

If this doesn't work, you have no choice but create a new room (or worst case, export your session keys, logout, login and import your session keys), until the workaround in #3553 is implemented (or this meta-bug is finally closed up)

[lampholder]

Making forward progress on this requires either @richvdh to hop back into it, or for him to hand over to somebody else.

[ara4n]

I just spent a while reviewing all of the known remaining UISI causes with @richvdh. UISI bugs fall into two broad categories:

Wedged olm sessions:

• vector-im/element-web#3309: Olm sessions can get wedged if we throw away OTKs for messages in-flight
• We should prioritise established olm sessions over half-open ones when sending outgoing messages #2783: We can reduce the risk of vector-im/element-web#3309 by prioritising established olm sessions over half-open ones
• Olm is prone to race conditions across multiple tabs #2325: Olm sessions corrupt & wedge if you open the same Riot in multiple tabs
• different devices with the same curve25519 key confuse the olm layer element-meta#1143: If you reuse node-localstorage and share curve25519 keys between different device IDs, Olm wedges <-- NOT A BUG FOR RIOT<->RIOT.
• Restoring a phone (or browser tab) from backup will break Olm if the other device still exists. #3822: If users restore a device backup or tab whilst the existing device is still around and active, Olm will wedge.

Missing megolm keys:

• Users whose servers were unreachable when you logged in will send you undecryptable messages matrix-org/synapse#2165: Caused if federation is broken when you login, so remote HS don't get told about your new device.
  • There is no solution to this; if alice doesn't know bob's new device exists when encrypting messages for him, he'll never be able to decrypt them.
• if your server goes down, when it comes back you get messages long before the keys #3754: Caused by your HS federation being broken when someone starts a new megolm session to you, but you then receive messages from other HSes before you receive your megolm keys
  • We could query the origin HS (if it's available again) for the keys, to speed up the recovery process.
• possible to run out of one-time-keys on rarely-used devices #3187: You ran out of Olm OTKs, so can't start a new Olm session, and thus share Megolm keys (or do anything else)
• device list update is *still* racy #3796: If Alice adds a new device whilst we're downloading her old device list, we may not spot the new device.
• Users in short-lived incognito tabs may never be able to share megolm keys, unless they can dehydrate/rehydrate their device somehow. #3825: If Alice and Bob only ever use Riot in short-lived incognito windows, they may never successfully exchange megolm keys
• ...possibly other bugs where the act of loading the target's MemberInfo kicks the sender into refreshing their device list?

Rich estimates UISIs to roughly be caused 50/50 split between the two.

However, all of the 'missing megolm key' class of bugs can be worked around by giving users a way of recovering missing megolm keys - and in some cases (broken federation; matrix-org/synapse#2165) this is the only plausible solution. In turn, if we had a way of recovering missing megolm keys, we'd also have a way to share history to new devices - the infamous 'share history' bug (#2286).

Therefore the suggestion is to focus entirely[1] on solving the problem of sharing megolm keys, given the value of solving both the 'missing megolm key' bugs as well as the 'sharing history' feature is greater than the value of solving the individual bitty 'wedged olm session' bugs (which all have different solutions). This means setting aside UISI hell and forging ahead and solving history sharing (#2286) or at least a subset of it. This could well include improving the UX for sharing history by supporting cross-signed keys (#2714).

[1] We can probably progress the 'multiple tabs' problem (#2325) in parallel. And the plan is to finish the devicelist race #3796 first.

[richvdh]

element-hq/element-meta#1143: If you reuse node-localstorage and share curve25519 keys between different device IDs, Olm wedges <-- NOT A BUG FOR RIOT.

Well, it is a bug for riot, in that if anyone uses the js-sdk in the obvious manner, riot fails to talk e2e with the resultant client. It's arguable whose fault that is - ideally both ends would be fixed. But it's not a bug for riot inasmuchas it doesn't affect riot<->riot comms.

...possibly other bugs where the act of loading the target's MemberInfo kicks the sender into refreshing their device list?

AFAIK the only thing that loading the MemberInfo would solve these days is #3796.

[ara4n]

writing https://github.com/vector-im/riot-web/issues/2286#issuecomment-299605919 made me realise that perhaps we can also improve the experience here in general with better error messages. For instance, do we have any way of detecting when an Olm session has got wedged, such that we can complain about that (and perhaps reset it?) rather than just whine about missing megolm keys?

[richvdh]

Yes, we can certainly improve this. We can give the user feedback about failing to decrypt to_device messages (though they tend to get replayed at initial sync, so we'd have to think how to avoid false positives). element-hq/riot-android#800 randomly, covers that. If we can get it reliable, we can start a new Olm session to try and unwedge things. We can also consider giving better feedback from the sender's end (#2494).

In general it's hard to tell the cause of any particular UISI, because you can't correlate it to a to_device you couldn't decrypt.

[pik]

If users restore a device backup or tab whilst the existing device is still around and active, Olm will wedge.
If you reuse node-localstorage and share curve25519 keys between different device IDs, Olm wedges <-- NOT A BUG FOR RIOT<->RIOT.

While it is possible at the moment I don't really like the idea of the same keys on multiple devices (this is surely a security risk). Notably also device_keys changing while device_id remains the same is another way to wedge olm sessions (the client sharing the megolm session key thinks they sent keys to the associated device, but that device has new keys and cannot decrypt the olm session).

[richvdh]

@pik: please take your questions about element-hq/element-meta#1143 and #3822 to the relevant bugs.

Another thing we should consider on this bug is a way for the recipient to distinguish "the sender failed to send to you" vs "the sender chose not to send to you" (either they blocked you or your device explicitly, or because they had the 'Never send encrypted messages to unverified devices from this device' setting (matrix-org/matrix-js-sdk#336) checked).

• basically we should be able to distinguish between "it went a bit wrong" and "expected behaviour".

Of course that would probably mean the sender sending a "you're blocked' notification to the recipient, but that wouldn't be hard.

[richvdh]

Added #3845 for the "blocked vs failure" sidebar

[richvdh]

We're closing this in favour of element-hq/element-meta#245, which needs a whole load of updates, but is probably still more up-to-date than this issue (and there's no point having two issues tracking the same thing)

[nituladaboneko]

wow

5y later
and this is still an unresolved issue

was excited to move our team from google hangouts to element

but alas
another poor quality open source project

[vmario89]

we are using element for 2.5 years now and for us the errors have gone completely. it works stable 99% of time. element + matrix are not a poor source project, but your opinion

[shmerl]

This is still happening (encrypted room, one user joining from iOS element client can't ready any messages with such error showing up). Doesn't happen with Web and Android clients. So can be iOS specific at this point.

[ShadowJonathan]

iOS is currently going through a rewrite, so after that (Element X) replaces the current iOS app, those issues would most likely be resolved, as it uses the more-vetted rust-based matrix SDK to do crypto.

[shmerl]

Is there some status page for Element X for iOS to track the progress?

[ShadowJonathan]

Element X is at https://github.com/vector-im/element-x-ios, the room is here.

There is a "Meta" repository for element now, where there are issues tagged with Element X iOS. I don't know where the central "project" board for Element X is, but it's likely that its not entirely public, as it is the domain of Element's Product Team.

The best way to "track" Element X's progress is to join the room, join the testflight, provide feedback (so you can help it along), and then finally notice that the testflight stops updating, and everyone is talking about the "better" Element app currently available for download in the store.

(Please keep in mind that the issues on the meta repo are not meant to be commented on, they're meant to be a way for the element team to communicate resources, and so adding noise would not help)

[richvdh]

Please keep in mind that the issues on the meta repo are not meant to be commented on

I'm not sure that's true? element-meta is used to track issues that span more than one Element client implementation. Comments on issues in it are as welcome there as in the individual repositories.

That said:

• element-meta does have a relatively high proportion of "tracker" issues which exist only to link out to other, more granular issues. Typically discussion is more appropriate on the lower-level issues than the tracker issues.
• comments along the lines of "why isn't this thing ready yet" aren't going to be terribly helpful in any case.

[pylapp]

Followed the following steps and it worked like a charm:

• export all my keys
• log out
• kill the all
• log in with recovery sentence