Soatok yesterday alleged a pair of vulnerabilities in the Matrix Vodzemac cryptography library. I’m going to focus on the first here,

The basic gist of the issue is this:

• Normally in Elliptic Curve Diffie-Hellman, you multiply your private key by the other party’s public key.
• If, instead of their public key, they send you the “identity” curve element, then the output of the multiplication is also the identity element
• This means that the output of your ECDH operation is the identity element.
• This means that the keys securing your communications are all-zero, and a passive observer can now decrypt your messages.

Now that sounds bad, I’ll agree. RFC 7748, which defines X25519, calls this case out:

Protocol designers using Diffie-Hellman over the curves defined in this document must not assume “contributory behaviour”. Specially, contributory behaviour means that both parties’ private keys contribute to the resulting shared key. Since curve25519 and curve448 have cofactors of 8 and 4 (respectively), an input point of small order will eliminate any contribution from the other party’s private key. This situation can be detected by checking for the all- zero output, which implementations MAY do, as specified in Section 6. However, a large number of existing implementations do not do this.

It notes that implementations MAY check for the all zero output, but does not require this. It states that an application that requires “contributory behaviour” MUST check for this case, and it gives us a definition of that.

Who needs contributory behaviour?

Alice and Bob exchange public keys with each other, and then do ECDH to compute a shared secret. They then verify that they have the same secret, e.g. by signing it with pre-established keys.

Now lets’ say Mallory is sitting in the middle. She swaps the public keys for the identity elements. Alice and Bob now generate all-zeroes shared secrets. The signature check passes, but Mallory can read all of their messages (and even impersonate them to each other)

It turns out that Alice and Bob’s protocol required contributory behaviour and they should have checked for the all-zero output (or a small order public key input).

Most modern protocols compute a hash of the ECDH output and two public keys to compute a shared secret. This would also have caught such tampering.

Does Matrix require contributory behaviour?

The specific issue raised is with regards to Vodzemac’s implementation of Olm. In particular, it is with the Initial Setup portion, which is an implementation of Signal’s X3DH.

Alice wants to send a message to Bob, but doesn’t have an established cryptographic session. She downloads a key bundle from Bob, which contains an Identity Key and an Ephemeral Key. This bundle is signed by Bob’s Identity Key.

Mallory cannot tamper with the keys inside Bob’s key bundle, because they are signed.

Alice computes ECDH outputs between:

• Her Identity Key and Bob’s Ephemeral Key
• Her Ephemeral Key and Bob’s Identity Key
• Her Ephemeral Key and Bob’s Ephemeral Key.

She sends Bob her Identity and Ephemeral keys (and also his Ephemeral public key, so that he can locate the corresponding private key), some additional information (irrelevant to us here), and a ciphertext encrypted with the shared secret.

Bob computes the same ECDH outputs.

If Mallory tampers with the keys inside Alice’s message, the two parties will generate different ECDH outputs, and the ciphertext that Alice sent will fail to decrypt.

In summary, Olm does not require contributory behaviour.

Does Signal check for all-zeroes outputs?

Soatok often recommends use of Signal. I cannot disagree with this recommendation; it is by far the most secure messaging protocol available today.

As discussed before, Matrix’ Olm is a derivative of Signal’s X3DH. This raised the question for me: Does Signal’s implementation check for all-zeroes outputs?

First of all, we’ll have to change the question slightly. Signal no longer uses X3DH. Instead, it uses PQXDH, which is a modification of X3DH that adds post-quantumn security by adding a PQ KEM such as ML-KEM.

And the answer is that yes it does. But only as of a week ago. Prior to that change, libsignal did not check whether the public key provided by the other party was contributory. Checking a much older version that did implement X3DH, it does not check that the input public keys were contributory.

The Signal developers have not made any public statements about this change. It is notably absent from their release notes for libsignal. They, like me, do not appear to believe it to be security critical.

As a side note, I find the fact that this change was made on the same day Soatok disclosed things to matrix.org a tad curious. Did Soatok inform one of the signal developers about his findings, prompting the change?

Should Vodzemac check for this case?

Maybe. I think this would be nice “defence in depth” practice.

But I don’t think it’s absence is a security vulnerability. The only person who can force your shared secret to all zeroes is the party you’re communicating with, who can also just leak your shared secret or their private keys.

Does this mean you should use Martix?

I’m not going to endorse Matrix. It leaks metadata like a seive, and has a history of state inconsistency issues causing room breakage. It may be the least bad option for large group chats, but that says more about the lack of alternatives than anything else. I use it, but somewhat begrudgingly.

For one to one chats, the gold standard of secure messaging is and remains Signal.