As a user, I want e2e to work seamlessly when I restore my device from backup

[dbkr]

ie. the current problem that when a device is cloned, olm sessions break.

This is not the right place for this, but I think the answer here is:

• On device where we can store data that won't be included in a backup and it's very unlikely a backup will be created in any way that ignores this (ie. iOS, I think), we can use this such that when the user restores a backup, we can detect it.
• On platforms where we can't do this, we store a nonce for each device in account data and a list of nonces locally on the device. At device creation time (ie. registration/login) send a new random nonce to the server account data and push it onto the end front of the local list. On each cold start, wait until the first server sync is complete before making any device-specific client/server API calls (eg. sending message on olm sessions). Generate a new random nonce, send this to account data on the server and push it onto the front of the local list. Whenever a new nonce arrives down the sync for that device (at any point, not just during this initial checking process), delete any nonces further back in the list than that one. If the new nonce doesn't appear in the list, the device has been cloned.

Whenever we detect that a device has been cloned, we must immediately stop making device-specific client/server API calls, (probably) prompt the user, then discard the current device keys and olm sessions and create a new device (with current c/s API this probably means logging in again, akin to a soft logout). Note we can keep the megolm session keys, sync data, etc. We then cross-sign this new device, prompting the user for passphrase/recovery key or obtaining from a secure enclave if we have it.

NB. by writing data to a non-backed up location, the user will always be prompted to set up their new device on a newly restored device. With the nonce method, they stopped using their old device after backing up, their new device may just 'inherit' the identity of the old device. This is fine, since if they resume using the old device, it will detect that it has been cloned.

NB2. We don't even need to spec the nonce method since it's entirely client-specific by definition (ie. specific to an individual client's local data storage). We may still want to put it in the spec so save other clients from having to re-solve the same problem.

[jryans]

In the near term, we only need to have Olm unwedging for this story. This is already implemented on web, but not yet on mobile.

[manuroe]

For reference:
element-hq/element-ios#2129
element-hq/element-android#847