Megolm key confusion

Established cryptographic algorithms like Signal’s double ratchet algorithm may include guidance or cautions for application or modifications of the parameters or construction used. But what can happen if you ignore said advice?

This article is a full disclosure on a low-severity key confusion vulnerability in version 3 of megolm, the latest version of megolm that is specified and used.

Timeline

• 2022-07-05: A pull request for adding a fixed version 4 of megolm was opened
• 2022-08-05: It was merged into vodozemac
• 2022-09-13: vodozemac 0.3.0 was released which contained the fixed version
• ca. 2024-08: I independently rediscover the vulnerability, but decided to not pursue this further
• 2026-02-26: I discover the aforementioned undeployed fix
• 2026-09-11: I publish this article

This change, as far as I am aware, is entirely undocumented and unspecified. I decided to immediately disclose the vulnerability due to languishing for several years at this point.

Overview of Megolm

Megolm is an AES-based authenticated message encryption system with built-in key ratchet that is used in matrix’s encrypted chats (both groups and DMs).

Megolm the Ratchet

The Megolm Ratchet consists of 3 parts, a 32 bit counter, an Ed25519 Keypair, and a 1024 bit ratchet. The public key part of the keypair is used to identify the exact ratchet used.

The Ratchet is seemingly intended to be able to cope with sessions that are up to $2^{32}$messages long which is an incredibly long time to go without rotating a session.

Keep in mind that once someone has obtained a raccopy of the ratchet, they can decrypt all further messages that use this session. Chat participants tend to be able to just ask other chat participants for the session.

Random unresolved questions and observations:

• the spec-recommended freqency for rotating the session has been 100 messages since the first version of the spec that supports end-to-end encryption. A significant part of both the ratchet state and the ratcheting logic only activate at $i>255$which is above that.
• Why is only part of the state updated every ratchet operation?
• Each ratcheting operation only uses 1/4 of the total ratchet, while the key is derived from the entire 1024 bit ratchet
• None of the steps in ratcheting or key generation use the Ed25519 keypair at all.
• Why is it different from the Olm ratchet?
  These are more thinkers than anything else. I don’t believe the construction to be insecure, more just more complex than it needs to be.

The Keypair in the room

The Keypair is used for two things:

• Signing encrypted messages
• Signing the serialized format of the session for sharing with other devices. The private key obviously is not shared.

Since the sessions are signed when shared, key forwarding (Bob sending Alice’s session to Charlie) can only re-transmit the session that was originally received, not one that has been ratcheted.

The Encryption Scheme

The entire ratchet is fed into HKDF-SHA-256 and an AES Key, an HMAC key, and an AES IV are extracted from it.

The message to be encrypted is encrypted with AES-256 CBC with PKCS #7 padding using the just calculated AES Key and AES IV.

The ciphertext is then packaged into a structure together with the ratchet index $i$and the version number of Megolm used (3 currently). Then an HMAC is calculated over this structure, truncated to 64 bits, and then appended. Then the entire message is signed using the Ed25519 key from the ratchet. This is again just appended to the end of the message.

The Issue

The mention of Signal’s Double Ratchet algorithm in the opening was not random. The document in fact considers truncation of authentication tags in AES-CBC with HMAC authentication tags.

Here is what it has to say about it (emphasis mine):

If the ENCRYPT() function is implemented using CBC and HMAC as described in Section 7.2, then truncating the final HMAC output to 128 bits to reduce message size is acceptable. Truncating it further might be acceptable, though requires careful analysis. In no case should the final HMAC be truncated to less than 64 bits.

So what was the special consideration?

I asked them via email in 2024 but have yet to receive an answer to the question. From my external perspective it appears like their consideration was adding the message signature. The signature prevents a malicious homeserver admin that has access to a ratchet from one of its users from impersonating the user silently.^[1]

Without it, a malicious actor in the room (including the homeserver) could artificially increase the message index of sessions and break them this way. This would have been possible even without knowledge of the session ratchet in the first place.

As mentioned before, the session is identified by a keypair’s public key, yet the keypair is not involved in the ratcheting in any way. This means that it is possible to create a pair of sessions that:

• have a different keypair ($K_{1}≠K_{2}$) but the same ratchet ($R_{1}=R_{2}$)
• have the same keypair $K_{1}=K_{2}$but different ratchets ($R_{1}≠R_{2}$)

The first one lets the same key/iv pair be used for multiple messages, but unlike AES-GCM, AES-CBC-HMAC doesn’t let you extract the encryption key from that. The second one allows you to make clients disagree about the exact value of the ratchet and thus decrypt the message to different values.

Ordinarily this would not be a problem because HMAC is key-committing and finding two keys which MAC the ciphertext to the same value is equivalent to finding a collision in SHA-256. ^[2] The problem here however is that the MAC is truncated to 64 bits, meaning that it is possible, with large enough compute capabilities, to find a colliding pair of keys

Proof of Concept

Unfortunately, possible does not mean feasible. Here is the operations that go into each iteration

• HKDF-Extract step: HMAC-SHA256 with all-zeroes key and the ratchet state. We can pre-compute the first block and if we keep the first half of the ratchet the same we only need to calculate 1 SHA-256 block
• Hashing of the output of HKDF-Extract: This is just 1 SHA-256 block
• The first 64 bytes $p$in the HKDF-Expand: This is 1 SHA-256 blocks
• First iteration of the HKDF-Expand: One final block on top of $p$. This is 1 SHA-256 block
• Second iteration of the HKDF-Expand: Still only one block on top of $p$. This is 1 SHA-256 block
• Hashing of the output of HKDF: This is 1 SHA-256 block.
• The final mac: The shortest message possible is 13 bytes. With HMAC-SHA256 this is 2 SHA-256 Blocks
• GRAND TOTAL: 8 SHA-256 blocks
  So how fast can I calculate SHA-256?

# openssl speed sha256

Doing sha256 ops for 3s on 64 size blocks: 24,550,256 sha256 ops in 2.95s

Hm that won’t do how about,

# hashcat -b --hash-mode 1400

Hash-Mode 1400 (SHA2-256)
Speed.#01........:  6928.1 MH/s (97.89ms) @ Accel:96 Loops:1024 Thr:256 Vec:1

Better but let’s check cloud gpus

Hashcat & ProjectPhysX/OpenCL Benchmark - 1 x nVidia B200 SXM ($4831197) · Snippets · GitLab

Speed.#1.........: 17948.6 MH/s (67.80ms) @ Accel:8 Loops:1024 Thr:1024 Vec:1

only a little over 2.5x speed gain for the fastest commercially available gpu?

Let’s see how far it gets us:

$\frac{2^{64}H}{18\frac{GH}{s}} = 1024819115 s ≈ 11861 d$

yikes.

So yeah this attack requires a sizeable GPU cluster to pull off. Based on Vultr’s pricing it would be about $850,000. It is probably cheaper to buy a wrench^{[citation needed]}

But why?

Honestly, I do not understand why the truncation was considered a good idea. The best idea i got is that the 10^[3]-32^[4] byte reduction on the wire was considered more important than security. Of course, if they were concerned about wire size, not encoding the ciphertext with base64 would provide greater gains with 96 bytes of plaintext, which would be any megolm v4 message, and any megolm v3 message with more than 19 bytes of content (so probably all megolm v3 messages in practice also)

Potential Solution

Vodozemac has supported the unspecced version for several years at this point. I think it is time to .publish the spec for the new version and start sending messages with it. This however will break any client that still relies on libolm, an officially abandoned cryptography library with several active CVEs, as well as any homebrew implementations of libolm. Support for the new version is easily added since it involves merely not truncating the MAC and verifying the whole MAC for version 4.

Since the matrix spec proposal mechanism happens exclusively on github, I am unable to send in a spec myself.