Feasibility of Upgrading Cryptographic ciphers?

[Librechain]

This request was originally added as an issue under the 'element-web' repo (/vector-im/element-web); they advised that it should be moved here

Original Request URL - element-hq/element-web#19835

Going to republish my original request below for convenience.

Upgrading Cryptographic Scheme for Matrix - Feasibility?

Recently, the NSA deprecated 128-bit strength cryptography (secp256k1 specifically; I think the NIST SP reference still recommends ed25519).

This isn't something that I believe is an impending security issue but it does fall in line with the overall ethos of Matrix, which is to provide an unprecedented and unrivaled level of security in their chat app.

First Proposal - Intermediate Upgrade

At some point in the not so distant future, it is expected that there will be a mass migration to some of the quantum-resistant ciphers we saw appear in the NIST's PQC competition (now in its 3rd round). Putting speculation about quantum computers to the side, there have been many other advances in cryptanalysis and computing in general that seem to put 128-bit security in question in the longer-term.

The most recent Suite B published by NSA dropped sha256 and secp256k1. While ed25519 is not secp256k1, the removal of sha256 alongside the latter led me to wonder if the NSA felt that 128-bit strength cryptography was no longer sufficient to secure data & communications vs. simply having misgivings about secp256k1. I am aware that there are properties specific to the secp256k1 algorithm that make it uniquely susceptible to cryptanalytic attacks (i.e., 'nonce leakage'), in a way that ed25519 is not. However, this is not the case with sha256.

Its hard for me to justify that the deprecation of sha256 was done in preparation for quantum-capable computers in the near term or future since there is no perceptible advantage quantum computers will have when it comes to attempting to 'crack' the hash (the biggest fear comes from the potential destruction of ecdh + pki schemes).

This Has to be Done at Some Point Anyway

Its obviously up for debate whether this must be done now. Many would likely argue that there is no impending risk at this very point in time. But there is a virtual unanimous consensus that these cryptographic schemes will need to be swapped out at some point in the not so distant future (likely before the end of the decade, if not sooner).

When its too late, its too late obviously. That statement isn't meant to fearmonger at all but rather emphasize the greater point that even if this is done prematurely, it won't be for naught. Also, getting the ball rolling on this earlier will allow time for proper testing, feedback, further ideas etc.; nobody wants to be swapping out cryptographic algorithms with a gun to their heads, so to speak.

Willing to Work on This Implementation Independently

If the team feels this proposal is interested but is swamped with work, I'd be more than happy to give this a swing under appropriate guidance.

Please advise whenever you all get a chance. Great job with this project overall though - Matrix is something we needed in the open source community & hopefully it is here to stay for a very long time.

[ShadowJonathan]

There are two areas in matrix that use encryption at it's core; Server-signing keys, and E2EE keys.

Both are (to a degree) designed to swap to other implementations if the need requires, server keys names are prefixed with ed25519:<NAME>, so any server could easily switch on that (once implementation lands), however, a future MSC which could possibly switch to hash-based names (which i remembered there was talk about) should take this switching possibility into account.

E2EE is governed by the m.room.encryption state event, which has a content like follows;

{
    "algorithm": "m.megolm.v1.aes-sha2"
}

If possible, a new algorithm could be added here that addresses your concerns. However, switching encryption algorithms in the middle of a room is an as-of-yet undefined behaviour, so that has to be specced as well.

---

Note that i am not a cryptography expert, and only know some bits and bobs about the spec.

@uhoreg is the SCT member here who knows all about encryption, and he'd be able to tell you some more about this.

[FSG-Cat]

My knowledge of crypto isnt the best but if my google search is not incorrect NIST are looking for Public Key Crypto but we also need something that is Symetric most likely. Like SIDH is as far as i understand one of the promising canditates in this space especially since it would mean we keep our PFS assuming SIDH gets proven to be secure enough. (Plus key sizes are still resonable and not absolutely massive)

Now as for upgrading the crypto in a room well that is a can of worms because downgrade attacks have to be avoided and all the things like that.

[uhoreg]

https://github.com/matrix-org/matrix-doc/issues/2458 is a very-related issue, and my response to that issue applies to this issue as well, at least as far as end-to-end encryption goes. We also use ed25519 for signatures from servers, and sha256 in various things, such as constructing event IDs. Switching event IDs to be based on, say, sha512 or sha-3 would require a new room version.

[uhoreg]

I also meant to say, it's not clear whether we should switch to ed448/x448 soon, and then switch again to something post-quantum, or if we should wait until there's a clear post-quantum algorithm to switch to and only switch once.

[FSG-Cat]

I think that we should only switch once one of these 2 conditions are met. There is a strong enougth desire or need to justify swapping multiple times potentially or theres a solid standard established so the switch is only done once.

Situation 1 can happen if we say in theory Quantum computers evolve way faster than our post-quantum algorithms do as an example of a situation.

Situation 2 is well simple once there are clear standards for what is best for matrix then its a nobrainer from my prespective to start the process of migrating.

Assuming that standards get made quick enough and matrix adopts them quickly enough we should have ample time to migrate before attacking the previous systems becomes a practical real world concern from non nation state actors. Nation state actors are expected to be a concern quite earlier than other parties due to the amount of resources they are usually willing to spend on an attack.

[richvdh]

I'm not sure that this issue is offering any particular value. Upgrading the ciphers is certainly feasible, with an updated version of Olm and Megolm; whether the value of doing so right now is worth the opportunity cost is rather more questionable.

#975 is a discussion on what post-quantum crypto in Matrix might look like; #1557 is a tracker for what we're likely to do in the short term. (Changing the ciphers isn't currently on the list, but never say never.)

Accordingly, I'm going to close this.