7 ms·

Practically-Exploitable Cryptographic Vulnerabilities in Matrix

146 points by samwillis 4y ago

mananaysiempre 4y ago
This post was likely motivated by a current comment thread re this vulnerability, https://news.ycombinator.com/item?id=33009721 https://news.ycombinator.com/item?id=33009721, see there for some information on its impact. Also discussed in https://news.ycombinator.com/item?id=33009721 https://news.ycombinator.com/item?id=33009721 two months ago (42 points, 37 comments) with the participation of the researchers.
- samwillis 4y ago
  I posted it after seeing it on Twitter, it was presented at an event earlier in the week: https://mobile.twitter.com/claucece/status/1599929337007919104 https://mobile.twitter.com/claucece/status/15999293370079191...
gnull 4y ago
> It is common among secure messengers to require out-of-band verification to protect against active mallory-in-the-middle attacks. What is Mallory-in-the-middle? EDIT: It's the same as man-in-the-middle. Author's explain this when they first mention MiTM.
- gnarula 4y ago
  Cryptography parlance for a man-in-the middle adversary. https://en.wikipedia.org/wiki/Alice_and_Bob https://en.wikipedia.org/wiki/Alice_and_Bob might be of interest :)
  - gnull 4y ago
    I was sure it's something else, never heard of this being a standard term. Google search gives me only movie characters, "name meaning" pages, and a project called "Mallory in the middle" that implements some specific man-in-the-middle attack. I guess it's another case of those "raising awareness" changes, that is supposed not to cost anything, but just made me spend like 4 min confusedly googling what the new term means.
    - helloooooooo 4y ago
      It has to do with the history of using names like Alice and Bob in cryptography, and nothing to do within your suggested reason.
      - gnull 4y ago
        You mean calling the adversary Mallory? Yes, this is standard. The term mallory-in-the-middle is not, as you can confirm with one Google search. There's barely anyone using this term, and nobody was using it 4 years ago. At first, I thought that Mallory-in-the-middle was some special type of man-in-the-middle attack. In crypto, Mallory is a very specific type of adversary (active one, I think).
        Retr0id 4y ago
        While Mallory-in-the-middle is certainly less-common as a term, Mallory is most strongly associated with active-MitM examples, and vice-versa.
        deleted 4y ago
        [deleted]
        lucb1e 4y ago
        > There's barely anyone using this term, and nobody was using it 4 years ago. At my employer (security consultancy in Germany), we switched ~two weeks ago from "man" in the middle to "machine" in the middle as expansion for the MITM acronym. Mallory is also a good option, although more known to cryptographers than our mainly developer audience (who might have more of an idea what a machine is than a Mallory). It's all not perfect but we're figuring this out. Yes, neutral gender writing is indeed relatively new and won't be much on web searches. Apparently some others use AiTM for attacker in the middle (yes, with that capitalization), which most people hated and voted against (because capitalizing the The but not the in looks dumb and, also, everyone already knows mitm so that change harms readability even more). It'll be a while before the community settles on something and "man" is not the most commonly known one. Bear with us until then!
Arathorn 4y ago
We (the matrix team) addressed the implementation vulnerabilities discussed here back in September: https://matrix.org/blog/2022/09/28/upgrade-now-to-address-encryption-vulns-in-matrix-sdks-and-clients https://matrix.org/blog/2022/09/28/upgrade-now-to-address-en.... The only pending work is switching to TOFU (trust on first use) and client-controlled room membership. Currently users get warned if a malicious device or user gets added to a room by a malicious server (assuming users in the room are verified). However, rather than warning, we could block it outright - but this is nontrivial as it means clients have to independently replicate the group membership semantics the server currently handles, which are complicated in a decentralised environment. https://github.com/matrix-org/matrix-spec-proposals/blob/fayed/cryptographic-membership/proposals/3917-cryptographic-membership.md https://github.com/matrix-org/matrix-spec-proposals/blob/fay... is the work ongoing to shift membership to be controlled clientside, and https://github.com/matrix-org/matrix-spec-proposals/blob/fayed/tofu/proposals/3834-tofu.md https://github.com/matrix-org/matrix-spec-proposals/blob/fay... is the work ongoing to shift to TOFU. Meanwhile, this work is blocked behind switching to matrix-rust-sdk-crypto across Element on Web, iOS and Android, so we only fix this in one (audited) place - and can also build on the newly audited vodozemac implementation of Matrix’s encryption: https://matrix.org/blog/2022/05/16/independent-public-audit-of-vodozemac-a-native-rust-reference-implementation-of-matrix-end-to-end-encryption https://matrix.org/blog/2022/05/16/independent-public-audit-.... This work is going well though - I for one have been dogfooding ElementR (Element with rust-sdk-crypto) on iOS as my daily driver for the last week, and we should be releasing it shortly.
- dodgerdan 4y ago
  To paraphrase another comment on this; if I have to trust the server for Matrix E2EE to work, why don’t I just use Slack? The whole point of E2EE is so you don’t have to trust the server. And a “warning” that says something like “your group chat has been compromised by someone with access to the server or it might just be bob bought a new phone” is laughable as a status quo.
  - Arathorn 4y ago
    The point is that if your threat model cares about interception, you have to verify the identity of users out of band - same as Signal or WhatsApp or whatever. Then, if you've done that, and an unverified device is added to the conversation, the warning shows up and explicitly means "your group chat has been compromised" - just like a big red TLS warning on a webpage means "this certificate is bad". It does *NOT* mean that "it might just be bob bought a new phone"; if bob bought a new phone, he'll have verified it when he logged in, and so the warning doesn't show up. Anyone who actually uses Matrix will be familiar with the fact that it's pretty rare to see a big red X on a user who you've verified, and when it happens, you go ping them to ask wtf is going on - much like you'd ping the webmaster of a site whose TLS certificate is bad. This is why the Matrix community is not up in arms about this "vulnerability" - it is literally following the intended design, right from the point that we announced verification back in https://element.io/blog/e2e-encryption-by-default-cross-signing-is-here/ https://element.io/blog/e2e-encryption-by-default-cross-sign.... Now, this design can absolutely be improved on - at the least, we could go back to freezing the room whenever there's an unverified device, forcing the users to decide how to flush out the old device. Or we could switch to TOFU, and block unverified devices by default. But we've chosen to prioritise migrating the clients onto a single E2EE codebase (matrix-rust-sdk-crypto) first, so we do that work in a single place, rather than in quadruplicate across matrix-{js,ios,android,rust}-sdk.
2Gkashmiri 4y ago
does this "vulnerability" disclosure and its ongoing fix support the idea that more people are looking at the code and finding faults, before they get exploited in the wild, making the software "better"? as opposed to blindly claiming "unhackable" argument, the software is getting better?
- greggarious 4y ago
  Nothing is unhackable but at least you have the right to patch open source projects.
  - simne 4y ago
    Properly used formal verification, could make unhackable software, but expensive, because of this used rarely. For example, I know people, who made formal verification of their soft for power plants.
- cvwright 4y ago
  It’s definitely making the software better. See the MSC3917 document linked by Arathorn. They have put a lot of effort into thinking about the threat models and how to address each them. Is it perfect? Well, no. But it’s a hard problem and they are making meaningful progress.
upofadown 4y ago
Any attempt to change the IV (initialization vector) in a counter based block cipher mode entirely breaks decryption. So I am not sure why the "IND-CCA" attack would need to be fixed. It is like claiming that a system is broken because an attacker can block message delivery.
- martinralbrecht 4y ago
  We explain how this works in Appendix A of https://nebuchadnezzar-megolm.github.io/static/paper.pdf https://nebuchadnezzar-megolm.github.io/static/paper.pdf but it's also a nice little exercise to work out how this breaks confidentiality. TL;DR: Yes, the plaintext coming out is not what you'd expect ("breaks decryption") but in a predictable way.
- SAI_Peregrinus 4y ago
  It only entirely breaks decryption if the ciphertext is authenticated. In something like bare CBC mode it only breaks the decryption of the next block, all later blocks are unaltered. Usually cryptographers consider anything less secure than IND-CCA3[1] Secure (authenticated INDistinguishability under adaptive Chosen Ciphertext Attack) to be "insecure" in the most general sense of security. The system must defend against forged messages, not simply keep the contents of messages confidential. Accepting forged messages almost always leads to some way to break confidentiality eventually. [1] https://crypto.stackexchange.com/a/26738/17861 https://crypto.stackexchange.com/a/26738/17861
  - upofadown 4y ago
    I think you might mean IND-CCA2 here. IND-CCA3 doesn't seem to have gotten a lot of traction as a "notion". At any rate, once you have a deployed a system, theoretical notions of security are much less important. You then have to show an actual weakness if you want to convince someone to change something.
  - tptacek 4y ago
    You're talking to an HN user with a hobbyhorse about authenticated encryption being, at least sometimes, a bad thing; they reached this opinion after being pressed on the weaknesses of PGP's authenticator. There's no actual debate here: the authors of the paper call the attack they're referring to out as a design flaw, but not an exploitable weakness. Presumably, the Matrix team will fix this as soon as it's tractable; I don't think any involved cryptography engineer is sticking up for the design.
upofadown 4y ago
Most of these attacks are about user identity. I would be interested to know if fixing them broke usability as is so often the case. The identity issue is basically the issue in end to end encrypted messaging. Identity gets a lot harder when you have more than two participants in such a chat.
tptacek 4y ago
I think this is the most impactful set of cryptographic findings ever presented against any secure messaging system. I don't think the authors agree with me, but I'll say it anyways: this is a landmark paper. Here are the findings: 1. The Matrix protocol, as designed at the time, gave servers control over both group membership and over device ownership. Because all Matrix messages in practice are group messages, this means that servers control all the keys, and can decrypt arbitrary messages. They can do that by surreptitiously injecting "users" into groups, whereupon the members of the group will send that "user" their group key, or by surreptitiously adding devices to user accounts. 2. The out-of-band key verification primarily used by Matrix (there are several, this is I think the primary one), SAS, was cryptographically broken. There are a variety of long-term keys managed for each Matrix account; in the SAS subprotocol, 2 of those keys are used without domain separation (that is, no identifier is mixed into the protocol to mathematically establish "this key should only be valid if it was generated in the context of this use"). As a result, servers can spoof SAS completion for users by cleverly arranging identifiers for those users. 3. Servers can spoof user messages, simply by slapping another user's identity on "forwarded room key" messages. This produces a warning, and is a building-block attack. 4. Matrix uses two different cryptographic messaging protocols, Olm and Megolm. Olm is a point-to-point cryptographic ratchet (think classic Signal), and Megolm is the group protocol. Matrix uses Olm for housekeeping tasks and Megolm for messaging. Both protocols keep their own cryptographic state. You can confuse a Matrix target by unexpectedly mixing Olm and Megolm messages, in tandem with the previous building-block attack, to spoof user identities without any warnings (you do this by spoofing open a Megolm "channel", which is like a messaging leg of a Matrix group). 5. Matrix has an encrypted backup subprotocol so that the server can escrow keys between devices (that is, Matrix provides secure encrypted storage of message state for users, ostensibly arranged so the server can't read any of it). The previous reliable spoofing attack can be used by the server to break it, and recover any user's encrypted state: you spoof a user to themselves and trick them into setting a backup key that you control. Some obvious takeaways here: * In a group secure messaging protocol, group membership is key management. If group membership is insecure, the system is insecure. Matrix isn't the first secure messenger to blow up over group membership. * All modern secure messengers are complex. If you look at Signal's design, you'll see cryptographic construction on top of cryptographic construction. But a sound protocol is restrained. The pieces all fit together organically. Matrix, on the other hand, sprawls. There is a tremendous amount of stuff going on, and it's difficult to reason about. * The Matrix team is responding to these vulnerabilities by altering the protocol. That's good. But the initial response given to the researchers regarding group membership was that they were going to accept the risk(!) of server-controlled group messaging, and concentrate on ensuring warnings were reliably given to users. Group membership is key management. By the time you're reading a warning, an attacker is decrypting messages. To shoplift the words of a great sage, the god-damned plane has crashed into the mountain.

146 points by samwillis 4y ago

This post was likely motivated by a current comment thread re this vulnerability, https://news.ycombinator.com/item?id=33009721 https://news.ycombinator.com/item?id=33009721, see there for some information on its impact. Also discussed in https://news.ycombinator.com/item?id=33009721 https://news.ycombinator.com/item?id=33009721 two months ago (42 points, 37 comments) with the participation of the researchers.

samwillis 4y ago
I posted it after seeing it on Twitter, it was presented at an event earlier in the week: https://mobile.twitter.com/claucece/status/1599929337007919104 https://mobile.twitter.com/claucece/status/15999293370079191...

gnull 4y ago

> It is common among secure messengers to require out-of-band verification to protect against active mallory-in-the-middle attacks. What is Mallory-in-the-middle? EDIT: It's the same as man-in-the-middle. Author's explain this when they first mention MiTM.

gnarula 4y ago
Cryptography parlance for a man-in-the middle adversary. https://en.wikipedia.org/wiki/Alice_and_Bob https://en.wikipedia.org/wiki/Alice_and_Bob might be of interest :)
- gnull 4y ago
  I was sure it's something else, never heard of this being a standard term. Google search gives me only movie characters, "name meaning" pages, and a project called "Mallory in the middle" that implements some specific man-in-the-middle attack. I guess it's another case of those "raising awareness" changes, that is supposed not to cost anything, but just made me spend like 4 min confusedly googling what the new term means.
  - helloooooooo 4y ago
    It has to do with the history of using names like Alice and Bob in cryptography, and nothing to do within your suggested reason.
    - gnull 4y ago
      You mean calling the adversary Mallory? Yes, this is standard. The term mallory-in-the-middle is not, as you can confirm with one Google search. There's barely anyone using this term, and nobody was using it 4 years ago. At first, I thought that Mallory-in-the-middle was some special type of man-in-the-middle attack. In crypto, Mallory is a very specific type of adversary (active one, I think).
      - Retr0id 4y ago
        While Mallory-in-the-middle is certainly less-common as a term, Mallory is most strongly associated with active-MitM examples, and vice-versa.
      - deleted 4y ago
        [deleted]
      - lucb1e 4y ago
        > There's barely anyone using this term, and nobody was using it 4 years ago. At my employer (security consultancy in Germany), we switched ~two weeks ago from "man" in the middle to "machine" in the middle as expansion for the MITM acronym. Mallory is also a good option, although more known to cryptographers than our mainly developer audience (who might have more of an idea what a machine is than a Mallory). It's all not perfect but we're figuring this out. Yes, neutral gender writing is indeed relatively new and won't be much on web searches. Apparently some others use AiTM for attacker in the middle (yes, with that capitalization), which most people hated and voted against (because capitalizing the The but not the in looks dumb and, also, everyone already knows mitm so that change harms readability even more). It'll be a while before the community settles on something and "man" is not the most commonly known one. Bear with us until then!

Arathorn 4y ago

We (the matrix team) addressed the implementation vulnerabilities discussed here back in September: https://matrix.org/blog/2022/09/28/upgrade-now-to-address-encryption-vulns-in-matrix-sdks-and-clients https://matrix.org/blog/2022/09/28/upgrade-now-to-address-en.... The only pending work is switching to TOFU (trust on first use) and client-controlled room membership. Currently users get warned if a malicious device or user gets added to a room by a malicious server (assuming users in the room are verified). However, rather than warning, we could block it outright - but this is nontrivial as it means clients have to independently replicate the group membership semantics the server currently handles, which are complicated in a decentralised environment. https://github.com/matrix-org/matrix-spec-proposals/blob/fayed/cryptographic-membership/proposals/3917-cryptographic-membership.md https://github.com/matrix-org/matrix-spec-proposals/blob/fay... is the work ongoing to shift membership to be controlled clientside, and https://github.com/matrix-org/matrix-spec-proposals/blob/fayed/tofu/proposals/3834-tofu.md https://github.com/matrix-org/matrix-spec-proposals/blob/fay... is the work ongoing to shift to TOFU. Meanwhile, this work is blocked behind switching to matrix-rust-sdk-crypto across Element on Web, iOS and Android, so we only fix this in one (audited) place - and can also build on the newly audited vodozemac implementation of Matrix’s encryption: https://matrix.org/blog/2022/05/16/independent-public-audit-of-vodozemac-a-native-rust-reference-implementation-of-matrix-end-to-end-encryption https://matrix.org/blog/2022/05/16/independent-public-audit-.... This work is going well though - I for one have been dogfooding ElementR (Element with rust-sdk-crypto) on iOS as my daily driver for the last week, and we should be releasing it shortly.

dodgerdan 4y ago
To paraphrase another comment on this; if I have to trust the server for Matrix E2EE to work, why don’t I just use Slack? The whole point of E2EE is so you don’t have to trust the server. And a “warning” that says something like “your group chat has been compromised by someone with access to the server or it might just be bob bought a new phone” is laughable as a status quo.
- Arathorn 4y ago
  The point is that if your threat model cares about interception, you have to verify the identity of users out of band - same as Signal or WhatsApp or whatever. Then, if you've done that, and an unverified device is added to the conversation, the warning shows up and explicitly means "your group chat has been compromised" - just like a big red TLS warning on a webpage means "this certificate is bad". It does *NOT* mean that "it might just be bob bought a new phone"; if bob bought a new phone, he'll have verified it when he logged in, and so the warning doesn't show up. Anyone who actually uses Matrix will be familiar with the fact that it's pretty rare to see a big red X on a user who you've verified, and when it happens, you go ping them to ask wtf is going on - much like you'd ping the webmaster of a site whose TLS certificate is bad. This is why the Matrix community is not up in arms about this "vulnerability" - it is literally following the intended design, right from the point that we announced verification back in https://element.io/blog/e2e-encryption-by-default-cross-signing-is-here/ https://element.io/blog/e2e-encryption-by-default-cross-sign.... Now, this design can absolutely be improved on - at the least, we could go back to freezing the room whenever there's an unverified device, forcing the users to decide how to flush out the old device. Or we could switch to TOFU, and block unverified devices by default. But we've chosen to prioritise migrating the clients onto a single E2EE codebase (matrix-rust-sdk-crypto) first, so we do that work in a single place, rather than in quadruplicate across matrix-{js,ios,android,rust}-sdk.

2Gkashmiri 4y ago

does this "vulnerability" disclosure and its ongoing fix support the idea that more people are looking at the code and finding faults, before they get exploited in the wild, making the software "better"? as opposed to blindly claiming "unhackable" argument, the software is getting better?

greggarious 4y ago
Nothing is unhackable but at least you have the right to patch open source projects.
- simne 4y ago
  Properly used formal verification, could make unhackable software, but expensive, because of this used rarely. For example, I know people, who made formal verification of their soft for power plants.
cvwright 4y ago
It’s definitely making the software better. See the MSC3917 document linked by Arathorn. They have put a lot of effort into thinking about the threat models and how to address each them. Is it perfect? Well, no. But it’s a hard problem and they are making meaningful progress.

upofadown 4y ago

Any attempt to change the IV (initialization vector) in a counter based block cipher mode entirely breaks decryption. So I am not sure why the "IND-CCA" attack would need to be fixed. It is like claiming that a system is broken because an attacker can block message delivery.

martinralbrecht 4y ago
We explain how this works in Appendix A of https://nebuchadnezzar-megolm.github.io/static/paper.pdf https://nebuchadnezzar-megolm.github.io/static/paper.pdf but it's also a nice little exercise to work out how this breaks confidentiality. TL;DR: Yes, the plaintext coming out is not what you'd expect ("breaks decryption") but in a predictable way.
SAI_Peregrinus 4y ago
It only entirely breaks decryption if the ciphertext is authenticated. In something like bare CBC mode it only breaks the decryption of the next block, all later blocks are unaltered. Usually cryptographers consider anything less secure than IND-CCA3[1] Secure (authenticated INDistinguishability under adaptive Chosen Ciphertext Attack) to be "insecure" in the most general sense of security. The system must defend against forged messages, not simply keep the contents of messages confidential. Accepting forged messages almost always leads to some way to break confidentiality eventually. [1] https://crypto.stackexchange.com/a/26738/17861 https://crypto.stackexchange.com/a/26738/17861
- upofadown 4y ago
  I think you might mean IND-CCA2 here. IND-CCA3 doesn't seem to have gotten a lot of traction as a "notion". At any rate, once you have a deployed a system, theoretical notions of security are much less important. You then have to show an actual weakness if you want to convince someone to change something.
- tptacek 4y ago
  You're talking to an HN user with a hobbyhorse about authenticated encryption being, at least sometimes, a bad thing; they reached this opinion after being pressed on the weaknesses of PGP's authenticator. There's no actual debate here: the authors of the paper call the attack they're referring to out as a design flaw, but not an exploitable weakness. Presumably, the Matrix team will fix this as soon as it's tractable; I don't think any involved cryptography engineer is sticking up for the design.

upofadown 4y ago

Most of these attacks are about user identity. I would be interested to know if fixing them broke usability as is so often the case. The identity issue is basically the issue in end to end encrypted messaging. Identity gets a lot harder when you have more than two participants in such a chat.

tptacek 4y ago

I think this is the most impactful set of cryptographic findings ever presented against any secure messaging system. I don't think the authors agree with me, but I'll say it anyways: this is a landmark paper. Here are the findings: 1. The Matrix protocol, as designed at the time, gave servers control over both group membership and over device ownership. Because all Matrix messages in practice are group messages, this means that servers control all the keys, and can decrypt arbitrary messages. They can do that by surreptitiously injecting "users" into groups, whereupon the members of the group will send that "user" their group key, or by surreptitiously adding devices to user accounts. 2. The out-of-band key verification primarily used by Matrix (there are several, this is I think the primary one), SAS, was cryptographically broken. There are a variety of long-term keys managed for each Matrix account; in the SAS subprotocol, 2 of those keys are used without domain separation (that is, no identifier is mixed into the protocol to mathematically establish "this key should only be valid if it was generated in the context of this use"). As a result, servers can spoof SAS completion for users by cleverly arranging identifiers for those users. 3. Servers can spoof user messages, simply by slapping another user's identity on "forwarded room key" messages. This produces a warning, and is a building-block attack. 4. Matrix uses two different cryptographic messaging protocols, Olm and Megolm. Olm is a point-to-point cryptographic ratchet (think classic Signal), and Megolm is the group protocol. Matrix uses Olm for housekeeping tasks and Megolm for messaging. Both protocols keep their own cryptographic state. You can confuse a Matrix target by unexpectedly mixing Olm and Megolm messages, in tandem with the previous building-block attack, to spoof user identities without any warnings (you do this by spoofing open a Megolm "channel", which is like a messaging leg of a Matrix group). 5. Matrix has an encrypted backup subprotocol so that the server can escrow keys between devices (that is, Matrix provides secure encrypted storage of message state for users, ostensibly arranged so the server can't read any of it). The previous reliable spoofing attack can be used by the server to break it, and recover any user's encrypted state: you spoof a user to themselves and trick them into setting a backup key that you control. Some obvious takeaways here: * In a group secure messaging protocol, group membership is key management. If group membership is insecure, the system is insecure. Matrix isn't the first secure messenger to blow up over group membership. * All modern secure messengers are complex. If you look at Signal's design, you'll see cryptographic construction on top of cryptographic construction. But a sound protocol is restrained. The pieces all fit together organically. Matrix, on the other hand, sprawls. There is a tremendous amount of stuff going on, and it's difficult to reason about. * The Matrix team is responding to these vulnerabilities by altering the protocol. That's good. But the initial response given to the researchers regarding group membership was that they were going to accept the risk(!) of server-controlled group messaging, and concentrate on ensuring warnings were reliably given to users. Group membership is key management. By the time you're reading a warning, an attacker is decrypting messages. To shoplift the words of a great sage, the god-damned plane has crashed into the mountain.