Megolm P2P Cross-Verification and Encryption

[ghost-amnesiac]

Idea

Alternative to #300, #246, #234. Before anyone asks, no, this is not a joke idea.

Instead of a symmetric key, use the Double Ratchet algorithm combined with the Olm/Megolm scheme to negotiate keys and encrypt chat messages between players using NCR. (This doesn't imply sending messages over Matrix due to size inefficiencies, it only uses the Megolm encryption.)

• On first use with a genuine account, the NCR client generates a session composed of an asymmetric keypair (Ed25519 is current standard for Megolm) which signs key negotiation messages.
• When first negotiating with another user, a simple keyword or emoji cross verification allows the user to validate the authenticity of the other user via an out-of-band channel, or the user can choose trust-on-first-use.
• Once a session is verified, it can sign new session identities so that verification need only happen once per player.
• Depending on level of security required, verified sessions of a player can also sign sessions from another player that they have verified themselves to cross-verify identities on servers with many players without manual interaction.
• Once a user has verified another, as long as their session persists (or, as a new session, is signed by another trusted session), they will never need to verify again.

Reasoning

Advantages:

• Automated key negotiation over insecure chat channels, with optional session-based out-of-band cross verification to further guarantee authenticity and defeat any theoretical MITM attacks from Microsoft
• Partial forward secrecy offered by Double Ratchet, over no forward secrecy at all for symmetric keys
• Scalable to massive numbers of participant players
• Algorithm has already been plenty tested in real chat applications such as Signal and Matrix, and security has been independently audited.
• Existing matrix-org/olm lib in C/C++/JS, porting to Java should be relatively simple
• Stealing a user's MS account will not allow them to impersonate the player over Megolm encrypted channels with other players that have already talked to them encrypted due to trust-on-first-use; they would need to steal a session secret from the player's computer
• No central server or dependent external service

Disadvantages:

• As the Matrix model is impractical here, all session management and cross verification functionality will need to be written from scratch, which is quite significant
• Different players may not trust each other with encrypted messages. Players that choose to not verify each other will form isolated group Megolm chat sessions. Players can also be in several such groups at once. Allowing players to manage Megolm chat sessions requires complicated logic to safely handle and presents UX issues
• Key negotiation fires off many encrypted messages whenever new participants join the Megolm session, and whenever Megolm session keys are rotated. Very annoying for server admins and non-NCR players
• If the player cannot access any session secrets and doesn't have a backup (e.g. dead drive, moved computer), they will need to generate a new unverified session and other players who have talked to them encrypted previously will be warned that they might be an impersonator, and need to manually approve the new identity
• Unlike Matrix, a player revoking a compromised session of their own is difficult if not impossible to achieve; session keys must be kept secret. Maybe encode some session metadata in unused skin image regions for revocations?

Other Information

No response

[Madis0]

How would the messages look in practice?

[ghost-amnesiac]

After decryption, the plaintext message is displayed like a normal chat message, possibly with an icon which indicates the encryption status of the message. Megolm handshake messages are completely hidden by default, but a debug switch might be used to show them.

🔐 <Player1> polar bear

For the server or vanilla players, the encrypted messages will appear to be garbled similar to the existing symmetrically encrypted messages, although for standardization it is best to use some sort of header. A mockup for an encrypted message could look like this:

<Player1> encryptedmessage m1:aravP9OiYI3j2fJiF8hx232IJY/je7ddFBH+JhGMdJTvLsSydzHqm5eQrO4NYuMdmR8H6N2BB+wa7Rl3L+PqzdwyOCvFih3Ud7JGVL0GjYQEkXYzvjXzLMPMDI2TZGsL7PHGoREIF35CMGHbrVNM/MdgaLHkj7eKx/c=

(m1 is a placeholder protocol version)

It could also be possible to compress ciphertext via Unicode encoding.

[Aizistral]

Overall I am not opposed to this proposal, especially given how well it's laid out. However, my biggest concern with it is the neccessity of sending messages automatically on behalf of a player for the purpose of session establishment, without that player's manual input. This can break in many ways (for instance, due to chat rate limits on a given server), and players may not understand what has gone wrong or why the mod tried to send a message without their input in the first place. I have rejected many potential encryption systems in the past based on this concern, as I do not have any ideas at the time regarding how we can make the design intuitive for most users. If you have a good suggestion regarding how we can handle this, feel free to put it forward.

[ghost-amnesiac]

Active peer discovery is difficult to implement given that there is usually only one shared communication channel. As it is, there are three suggested main approaches to this problem, and it may be possible to implement several in tandem and let the user choose based on their use case:

• As usual, send ciphertext and negotiate over the main chat channel. Suitable for private Realms and servers. To address the concern of zero-input negotiation, peer discovery could be disabled by default and enabled by the user on a per-server basis. Players will need to manually choose to send peer discovery beacons to chat for the first time.

• Advertise encryption support and protocol version via unused skin pixel regions. Users that would like to proactively join encrypted chat sessions can, on server configurations that support them, use direct message commands like /msg to establish peer-to-peer sessions automatically outside of the main chat channel. However, P2P traffic grows at a factorial rate with user count if done exclusively through direct messages. Perhaps use a network of Raft-elected router peers to propagate messages more efficiently? Megolm encryption will still ensure session integrity in such cases. Suitable for larger public servers. Players on offline mode servers without skins can still discover each other manually, perhaps by choosing to send a tiny beacon message to chat, before negotiating over P2P.

• As a last resort on servers with more hostile and proactive moderation, route encrypted chat traffic over a third-party service, bypassing the server chat entirely. Several specialized approaches are available for relaying depending on the desired implementation:

  • Use a central server for relaying encrypted messages. This has centralization / fingerprinting concerns and is suseptible to DoS.
  • Use ICE STUN to set up a direct UPnP network connection between players. This has very obvious privacy downsides and does not work over complex NAT environments, but is simpler to implement.
  • Clients can deploy single-use Tor hidden services as negotiation relays and exchanging Ed25519 keys (onion addresses) using direct messages briefly. Players switch between onion services of other players on-the-fly to balance traffic. Most resilient and secure, but complex, requires network negotiation once, and out-of-order delivery is more of a concern.
    • At this point, why not just deploy ephemeral Matrix homeservers over Tor hidden services, where each player is their own homeserver? It could handle all of the heavy lifting, encryption and sessions included, though it would take a toll on performance and network load.

It is also important to consider that active peer discovery is mutually exclusive with deniability of using third-party communication channels, as the server can potentially impersonate a player to test whether a player has a mod implementing such a protocol enabled. Probing, DoS resistance, and deanonymization attacks are important factors to consider too.

Determining exactly how much data can be safely exchanged via out-of-band channels like skins without interfering with other popular mods can be helpful for brainstorming theoretical relay negotiation methods.

[Cuteistfox]

the encryption is really coming from "lets encrypt so microso_ er mojang studios dosent read are messages"to "lets desighn a inband asymetric encryption system for minecrafy chat with palsible deniablity and active peer discovery or pasive peer discoverly via skin pixels but out-of-band-ish or useing upnp to dox users but encrypting messages"(okay seriesly dont use the upnp and instead use onion adresses