Ah, I they see they're using libolm, as is the Matrix project!
I have a number of critiques of libolm that I haven't developed into a practical attack, but are simple enough to fix (if you ignore the massive legacy support and backwards compatibility t̵r̵a̵p̵ ̵t̵h̵e̵y̵'̵v̵e̵ ̵s̵e̵t̵ ̵f̵o̵r̵ ̵t̵h̵e̵m̵s̵e̵l̵v̵e̵s̵ EDIT: see Arathorn's comment below).
Libolm is encrypting with AES-CBC [1]. In addition to side-stepping entire classes of attack (i.e. padding oracles), CTR would allow better performance: You can parallelize both encryption and decryption with CTR mode. With CBC mode, you can only parallelize decryption (but not encryption) since the IV for all but the first block is the previous block of ciphertext, which means you'll know the correct IV when decrypting but not when encrypting (since you have to calculate it sequentially).
Yes, they HMAC the ciphertext [2]. However, their variable name choice doesn't inspire confidence in its correctness.
Furthermore, they truncate the HMAC to 8 byes and attempt to justify the truncation by appending an Ed25519 signature, but that sort of configuration is just begging for a confused deputy scenario, like an old iMessage vulnerability [3]. It's no where near as bad (iMessage eschewed MACs entirely, this still uses a MAC, so it's not exploitable), but it's something that probably would make anyone working in cryptography (and any adjacent fields) give a confused puppy head tilt when they read it.
Regarding their ratcheting protocol [4]: Instead of feeding HMAC-SHA256 back into itself at each ratchet step, I'd feel way more comfortable if the protocol did HMAC-SHA512 and used one half of the output to derive encryption/authentication keys and the other half the ratcheting-forward key (instead of one HMAC-SHA256 for both purposes).
Using two distinct 256-bit secrets (even if they're generated from the same input at i=0) instead of reusing a secret strengthens the forward secrecy of the entire protocol.
HMAC-SHA256:
One ring to rule them all (at any given ratchet step).
HMAC-SHA512-split:
If you (against all odds) guess one of the keys, that doesn't give you the ratchet-forward key too, since they're two distinct keys (albeit generated deterministically from the same input).
Nothing I said above is exploitable, otherwise I'd be emailing their security team instead of posting on HN. :)
That being said, if the Libolm devs want to shore up the security of their protocol in a future revision, the following changes would go a long way:
1. Use HMAC-SHA-512 and split it in half for the ratcheting step of Olm/Megolm
Thanks for the feedback. So the reason for these choices of primitives when we wrote libolm was to keep close to libsignalprotocol (or libaxolotl as it was then), to try to keep the door open to interop with Signal at some level.
The primitives can be changed though once there's enough evidence to do so, and Matrix supports pluggable E2EE algorithms as per https://matrix.org/docs/spec/client_server/r0.6.0#messaging-... - so I'm not convinced this is a "massive legacy support and backwards compatibility trap" that we've set for ourselves.
I appreciate the context. It's probably wise to abandon Signal interop.
My reasoning here is: Moxie isn't ever going to acquiesce on the points he's stubborn about, and Olm/Megolm could otherwise be a great cryptographic design with or without his approval.
His eponymous talk on 36C3 was similarly disappointing, mostly defending stubborn choices. Glad I didn't decide to spend the time watching it in person and got to see another talk by watching this one back instead.
> I appreciate the context. It's probably wise to abandon Signal interop.
> Olm/Megolm could otherwise be a great cryptographic design with or without his approval.
Could you (or Arathorn) expand on why Olm should deviate from the Signal protocol, instead of trying to reproduce it as closely as possible? Which requirements are different?
I understand that the Signal protocol is the state of the art in terms of E2EE for 1:1 conversations (and small groups). I understand how Matrix wants to address big groups and thus need Megolm. Where does this leave Olm?
> Could you (or Arathorn) expand on why Olm should deviate from the Signal protocol, instead of trying to reproduce it as closely as possible?
Because the only premise for strictly adhering to the Signal protocol has been invalidated by Moxie's personality.
With a false premise, why maintain a true conclusion?
In my OP comment, I outlined some criticisms of what they're doing, and suggested ways to improve it. Some of these (dropping AES-CBC+HMAC for AES-CTR+HMAC) have meaningful gains but, strictly speaking, are not Signal-compat.
The change to the ratcheting protocol adds a layer of indirection in the forward secrecy, but that also deviates from Signal. (My proposed change would make it closer to what the Noise Protocol Framework does.)
> Which requirements are different?
The technical requirements aren't changed, but you can get better performance AND security on more platforms by using XChaCha20 instead of AES-CBC, so that's a meaningful security gain that Signal cannot boast (i.e. in the context of legacy Android devices).
If it's HMAC'd, there's no sidestepping of padding oracles needed. Error side channels are a consequence of chosen ciphertext attacks, not of padding. Switching to CTR would not "go a long way" towards shoring up the security of their protocol.
I do not understand your "confused deputy" attack. Can you outline it in more detail?
> I do not understand your "confused deputy" attack. Can you outline it in more detail?
I'm literally referring to "the iMessage attack".
If you recall, iMessage did ECDSA(AES(m, ek), sk) without an intermediary HMAC. Libolm does have an (albeit truncated) HMAC, so the attack doesn't apply at all here. But it's still a design smell.
If I could extend their construction (which looks like the setup to the iMessage attack, without the punchline) into a real attack, I would have just disclosed it to them and not commented publicly.
How the attack I envision would work if their HMAC suddenly got erased from the protocol: Establish a multi-device setup, flip bits in ciphertext you want to decrypt, sign with Ed25519, observe padding oracle.
(A truncated HMAC does prevent that in the real world, but at a 32-bit security level rather than a 128-bit security level.)
These are (somewhat nitpicky) design critiques, not security vulnerabilities. :)
Edit to add: Also, the iMessage attack had some other weirdness that isn't relevant for what I'm describing, but was very relevant for iMessage being broken.
Isn't it a little weird to tell people to do major surgery on a crypto design, especially in ways that depart from the well-regarded design they derived it from, on account of attacks that don't work against that design?
It's only weird if you put Signal's specific design decisions from 2013 on a pedestal and declare it perfect and incapable of being improved.
(N.b. I don't expect my specific suggestions to be adopted. However, I view complaining without offering solutions to be poor form, so I offered some alongside my complaints.)
Of course, any deviation from Signal's design can and should be vetted by the same experts that vetted Signal's. And if they're unavailable to vet the derivations, the conservative thing to do is grit your teeth and bear Signal's legacy until they become available.
However, if Signal still targets Android 4.4 phones in 2020, there's a lot of devices without AES-NI and thus improving upon their AES-CBC design decision is worth probing at least.
In addition to my previous comments, I also have a thing about reflexively suggesting that people eliminate CBC from their designs. Depending on circumstances, CBC can be a safer choice than CTR (and CTR-derived modes like the AEAD stream ciphers); different failure modes.
You're entitled to your thing. Granted, CBC mode has a better misuse story than CTR, but an extended-nonce ChaPoly AEAD is likely to be safer in most of Signal's installed userbase (n.b. the same userbase Matrix and Jitsi would be targeting in a lot of cases), given the ARM SIMD (AES-NI equivalent) situation.
Chapoly depends on a reliable per-message CSPRNG. CBC wants randomness too, of course, but the failure mode under randomness hiccups isn't "coughs up keys". If you have a system working with CBC+HMAC, what's the advantage to shouldering that additional risk?
In a new design, I'd recommend Chapoly too. But this isn't a new design. Changing things has cost.
> If you have a system working with CBC+HMAC, what's the advantage to shouldering that additional risk?
The details you probably want me to put here are a bit fuzzy still, and I've solicited others' to provide clarity and insight into the specifics, so I apologize if this is hand-wavy, but your question deserves an answer.
Given:
Most smartphones are built on ARM architecture. At the very least, I'm confident about Android being ARM. I've never purchased an Apple product in my life, and can't rightly say much about their internals.
"In order to offer low cost options, device manufacturers sometimes use low-end processors such as the ARM Cortex-A7, which does not have hardware support for AES. On these devices, AES is so slow that it would result in a poor user experience; apps would take much longer to launch, and the device would generally feel much slower."
Even for smartphones that use ARMv8-A and newer, OEM weirdness can get in the way of that. Without tearing a specific model of a specific phone apart, I can't really give you much more information than that.
The advantage to the additional risk of ChaPoly is to not cough up keys to JavaScript running in a web browser capable of leveraging a cache-timing attack against software AES, in the smartphones that most people can afford.
That is to say, while it's true that the CSPRNG failure mode of ChaPoly is bad (but relies on conditions the attacker probably can't control), the failure mode of software AES is equally bad and can be influenced by an attacker.
> In a new design, I'd recommend Chapoly too. But this isn't a new design. Changing things has cost.
If there is significant market share where the device has a reliable CSPRNG but not hardware AES (post-OEM tampering), I'd argue that the security gain of a ChaPoly migration is worth the cost of changing, in particular.
The ratcheting changes are mostly a hygiene issue and probably won't be meaningfully important. I was just being nitpicky.
I think you misunderstood what I'm talking about here.
[ App (Java -> Dvorak) ]--.
>--- Same CPU
[ Web Browser with JS ]--`
My argument wasn't about "it" running in a web browser. I was arguing that side-channel attacks that can be exploited from a browser on the same CPU (as per djb's AES cache attack paper) are pretty bad, considering "trick user into opening a webpage" is a pretty low-hanging fruit attack vector.
It's like a standard padding oracle attack, but 4 billion times slower (on average) and requires 4 billion times more CPU work and bandwidth, and you have to be able to distinguish between a HMAC failure and a padding error.
I have a number of critiques of libolm that I haven't developed into a practical attack, but are simple enough to fix (if you ignore the massive legacy support and backwards compatibility t̵r̵a̵p̵ ̵t̵h̵e̵y̵'̵v̵e̵ ̵s̵e̵t̵ ̵f̵o̵r̵ ̵t̵h̵e̵m̵s̵e̵l̵v̵e̵s̵ EDIT: see Arathorn's comment below).
Libolm is encrypting with AES-CBC [1]. In addition to side-stepping entire classes of attack (i.e. padding oracles), CTR would allow better performance: You can parallelize both encryption and decryption with CTR mode. With CBC mode, you can only parallelize decryption (but not encryption) since the IV for all but the first block is the previous block of ciphertext, which means you'll know the correct IV when decrypting but not when encrypting (since you have to calculate it sequentially).
Yes, they HMAC the ciphertext [2]. However, their variable name choice doesn't inspire confidence in its correctness.
Furthermore, they truncate the HMAC to 8 byes and attempt to justify the truncation by appending an Ed25519 signature, but that sort of configuration is just begging for a confused deputy scenario, like an old iMessage vulnerability [3]. It's no where near as bad (iMessage eschewed MACs entirely, this still uses a MAC, so it's not exploitable), but it's something that probably would make anyone working in cryptography (and any adjacent fields) give a confused puppy head tilt when they read it.
Regarding their ratcheting protocol [4]: Instead of feeding HMAC-SHA256 back into itself at each ratchet step, I'd feel way more comfortable if the protocol did HMAC-SHA512 and used one half of the output to derive encryption/authentication keys and the other half the ratcheting-forward key (instead of one HMAC-SHA256 for both purposes).
Using two distinct 256-bit secrets (even if they're generated from the same input at i=0) instead of reusing a secret strengthens the forward secrecy of the entire protocol.
HMAC-SHA256: One ring to rule them all (at any given ratchet step).
HMAC-SHA512-split: If you (against all odds) guess one of the keys, that doesn't give you the ratchet-forward key too, since they're two distinct keys (albeit generated deterministically from the same input).
Nothing I said above is exploitable, otherwise I'd be emailing their security team instead of posting on HN. :)
That being said, if the Libolm devs want to shore up the security of their protocol in a future revision, the following changes would go a long way:
1. Use HMAC-SHA-512 and split it in half for the ratcheting step of Olm/Megolm
2. Use AES-CTR instead of AES-CBC
3. Stop truncating MACs
[1]: https://gitlab.matrix.org/matrix-org/olm/blob/master/docs/me...
[2]: https://gitlab.matrix.org/matrix-org/olm/-/blob/930c4677547e...
[3]: https://blog.cryptographyengineering.com/2016/03/21/attack-o...
[4]: https://gitlab.matrix.org/matrix-org/olm/blob/master/docs/me...