This is the generic IT problem of backward compatibility, made harder by crypto.
In IT, a common way to deal with backward compatibility is having a version field at start of data structures, allowing applications to decide if they recognize the format, and handle it if they can. New applications handle old formats, at least during a transition period. This can be extended to cryptographic payloads by having the version field in clear, and the rest encrypted/authenticated according to the version field.
When the method to encrypt/authenticate does not change, there is no crypto-specific issue, and usual mechanisms to deal with enriching data structures without compatibility break will do (e.g. in JSON, it's possible to add new fields that old applciations will skip). In the following I assume the crypto has changed, and a version field allows to detect that.
The problem now is, that (1) all the previous messages are stored on the server in the old format and (2) an "old" client may try to message a "new" client which forces me to somehow resolve this mismatch between the communicated messages' formats.
If the new client can still decipher the old format, neither is an issue. That's the way to go!
The real hard problem is when a "new" client sends a message. There are many choices, neither of which is perfect. Some of these:
- New clients always use the new format, which old clients won't understand.
- New clients use the old format until some trigger (switch date, message from server), then use the new format. Old clients won't be usable after the switch, and new clients won't enjoy the new features of the new format until that event.
- New clients use new format after the trigger or if there is some clue the receiver (or all the receivers) understands it, e.g. because the sending client has received an authenticated message from (all) the recipient(s) that indicates support of the new format, perhaps implicitly by using it.
- New clients generate both formats until the trigger and send both to the server, which stores them; old clients fetch the old format, new clients fetch the new and in case of failure fetch the old format. The server must handle requests in both formats, and needs more storage and more traffic in the interim period.