E2EE scheme that's under consideration for Mastodon 

(First, I'm talking from my perspective and not on behalf of Eugen or the Mastodon project)

There's still a long way to go, but we're working on providing end-to-end encryption of chat-like messages in Mastodon.

The cryptographic protocol we're considering is basically that used in XMPP's OMEMO, Signal, and part of Matrix (part of Matrix, because Matrix also features another protocol, that provides weaker security but is much more efficient in group chats).

Like Matrix and OMEMO, your server will still know who you're talking with and when (Signal does manage to avoid that to a great extent).

Message Franking

There's one feature we are discussing that I want to talk about a bit: message franking. It's a scheme designed by Facebook to enable the receiver of a message to report it to their server without revealing other messages in the process.

Basically, it works by having the sender hash (using HMAC) the message with a key they generate just for signing that single message. They then encrypt that key together with the message. So, the hash is visible to the server, but not the message nor the key. So it cannot, at that point, be verified by the server or infer anything about the message or key.

The server then takes note of the hash, and who sent the message to whom. It then signs that note with its own key (that key can be private, it's not important). It could also encrypt it. Nobody but the server needs to be able to read and verify it, but it's also not super important if anyone else can.

Then the server gives that signed note, along with the message, to the receiver, and forgets about it.

Upon receiving the message, the receiver performs the usual checks, but now, it has the message and the HMAC key, so it is able to verify the HMAC hash. If the HMAC hash is invalid, that means the sender lied, and he won't be able to report it. So the receiver just discards it (it could display an error message to the user, but that's not important). Otherwise, the receiver can report it. How? By sending the message, along with the HMAC key and the signed note back to the server.

The server first decode/decrypts the note, verifies its signature so that it can be sure that it indeed made that note, and then, since it has the HMAC key, can finally check the HMAC hash and verify that the reported message is indeed the message that was sent.

To lie about the reported message, you'd have to find another message and another key that match the hash, which is exactly what the HMAC algorithm tries to make impossible, and for which there are no known attack to this day.

Since you need the key and the message, on its own, the key does not let you learn anything about the message. If you were almost sure you knew the message, you'd still need the key to verify it.

According to a paper (— I'm going to trust here, I intuitively understand the reasoning, but I don't have enough knowledge to be completely sure about it, the message franking construction isn't even needed because the underlying protocol already has the same properties, if you reveal just the right key. This means adding message franking doesn't make the deniability of the protocol actually weaker. Adding it just makes it easier to implement and also makes sure that you disclose exactly the message you were reporting and not a few more (the alternative would be to reveal the input to the key derivation function for one message, but it could be used for more than one message, although it would usually be a short amount of messages)

E2EE scheme that's under consideration for Mastodon, more on message franking 

In my previous post I wrote:

The server then takes note of the hash, and who sent the message to whom. It then signs that note with its own key (that key can be private, it's not important). It could also encrypt it. Nobody but the server needs to be able to read and verify it, but it's also not super important if anyone else can.

Well… it's indeed not important for message franking to work that the verification can only be performed by the platform. But if the franking value (what I called “that note”) is verifiable by anyone, this gives power to disclose and prove they received a message, not only to the platform, but to anyone who trusts it, without that server's involvement. This is more power than receivers currently have, and that's probably unreasonable to have.

This is why the implementation we are working on will sign the franking value with a private key only the issuing server knows about. Furthermore, it will rotate the key, so that after a while, a message cannot be verified anymore.

Also, a client should not keep the franking value and HMAC key forever: indeed, if an attacker did witness the encrypted messages (e.g. by compromising one of the participant's instances or successfully MITMing them) and later got a hold on the HMAC keys, it would be able to verify those messages. Furthermore, if the franking value can be verified by anyone (which, again, won't be the case for Mastodon's, but that may be the case for other implementations), an attacker wouldn't have to breach the servers and the receiving client, only the latter.

This is the extent to which Message Franking weakens deniability. That extent can be largely diminished, and it doesn't weaken other properties.

Show thread

E2EE scheme that's under consideration for Mastodon 

@Thib Je comprends pas c’est qui le receveur, d’où y a trois parties dans le signalement d’un message? (je demande en français psk la crypto c’est déjà horriblement pas clair pour moi en français…)

re: E2EE scheme that's under consideration for Mastodon 

@melunaka y a la personne qui envoie le message (que j'ai dit sender), la personne à qui il est destiné (receiver), et le (ou les) serveur(s) sur lequel le message transite. Le chiffrement est bout-à-bout, mais le transport ça reste du fediverse.

re: E2EE scheme that's under consideration for Mastodon 

@Thib ah oui oki, j’ai mélangé envoi de message et signalement car la séparation était pas évidente pour moi dans ton texte mais en relisant c’est plus clair, merci!

E2EE scheme that's under consideration for Mastodon 

@Thib This is really clever.

E2EE scheme that's under consideration for Mastodon 


Du seul cours de sécurité que j'ai suivi j'ai retenu que j'étais absolument nul pour imaginer les détournements posible de l'algorithme...
Mais je ne comprends pas bien (ça fait longtemps, je n'ai plus les maths en tête) ce qui empêche de générer la clé qui donnera le bon hash une fois que l'on a écrit un faux message ?

PS: ton lien ne marche pas car tu n'as pas mis d'espace après le .pdf

E2EE scheme that's under consideration for Mastodon 

@LienRag argh le lien cassé hmpf

pour ce qui est de trouver une clé qui donne le bon hash avec un autre message, c'est un des buts de HMAC. En gros, ça réutilise des fonctions de hash cryptographiques (dont le but est que tu ne trouve pas de collision), en incorporant aussi la clé. Après comme tout en crypto, il est possible qu'il y ait des vulnérabilités, mais il n'y en a pas de connues pour l'instant.

Pour simplifier HMAC, en gros, t'as une clé, un message, et une fonction de hash (quand t'utilise HMAC, tu l'utilise avec une fonction de hash spécifique, en fait). HMAC(message, clé) dans l'idée ça revient à calculer hash(message + clé). Si tu sais pas trouver une collision dans la fonction de hash, tu sais pas beaucoup plus le faire ici. (En vrai c'est HMAC est un peu plus compliqué, pour éviter quelques attaques par extension—du genre qu'on connais sur certaines fonctions de hash cryptographiques, mais le principe reste le même)

E2EE scheme that's under consideration for Mastodon 

It sounds like the HMAC scheme would make it possible to prove that someone sent a message, even when he deleted it. This destroys the deniability that Mastodon currently allows for.

This toot (w/o a HMAC) may be forged by my or your server and that provides some deniability. A toot with a HMAC can permanently be attributed to me, even when it is deleted on both servers.
This could be a problem for all kinds of activists.

E2EE scheme that's under consideration for Mastodon 

@allo under that scheme, encrypted messages would be deleted from the server right after they were retrieved, unlike right now.

You are right though, that the sender wouldn't be able to delete the commitment, which means as long as the receiver keeps it they can indeed prevent denial. If you trust the server but not the receiver, this indeed looks like a downgrade. If you don't trust the server, they can store the info as long as they want, under the current scheme and under the new, and under the new scheme, the client collaborating with them would make the deniability as weak whether there is a franking HMAC or not. I'm not sure that this is this much of an issue, but it should be made clear.

Toots with HMAC can be forged too, the guarantee the server has that it hasn't been forged is the same as before. However, the receiver might now this was part of a legitimate session, so if you factor that in, the denial might be lower.

E2EE scheme that's under consideration for Mastodon 

@allo one possibility if you do trust the server but not the receiver (if you don't, and don't trust the receiver either, you've lost anyway) could be the server signing the franking value with keys it throws away after a while, meaning you could only report a message, say, up to 1 month after it was sent. Not sure how much that would be useful.

E2EE scheme that's under consideration for Mastodon 

Maybe the user could be allowed to change keys often, so they may publish the old signing key afterwards, so anyone can forge signatures afterwards (but the receiver knows that he got the message when the signing key was private).
On the other hand this would involve more changes like where to publish the keys and if it is plausible that the message was forged using a disposed key or if the adversary just ignores the scheme.

E2EE scheme that's under consideration for Mastodon 

@allo i'm not sure what key you're talking about here, the server won't actually care about any long-living key for that feature.

When I meant “forged” in my last message, I was actually talking about the sender's account (or their server) being breached/impersonated. That can happen already, and that's your only deniability right now (I mean, along with the server being distrustful).

The proof under the new scheme is “the server has seen the message pass” + “the client can actually tell what the message was”. The underlying message can be sent through a breached account just as before. The server can be untrustful about the “the server has seen the message pass” as before. The client cannot lie about what the message was, but without getting the info from the server that the message itself was indeed sent from the incriminated account, and trusting it, it's useless.

E2EE scheme that's under consideration for Mastodon 

@Thib I think OTR has a feature (and probably OMEMO as well?) that the receiver can verify the message when it is received, but when someone finds my message on his PC they will not be able to prove that it was sent by me.
On the other hand I am not sure if this was ever used in court or if it is only a crypto nerds dream that it will help him when someone finds the message.

re: E2EE scheme that's under consideration for Mastodon 

@allo oh, basically in the crypto protocol (Signal/Olm) the keys with which messages are signed and encrypted change every time the communication changes direction (which means you can have a bunch of messages sharing the same keys, e.g. quick succession of messages sent when the other peer was offline), and a well-behaved client would throw them away. So even if you were to have a key at one point, you wouldn't have the next, nor the previous, and you wouldn't be able to decrypt nor verify anything.

With the message franking thing, this property is mostly preserved, but as a client you can prove anyone who observed the encrypted message passing on the transport layer (that is, your server, or an attacker MITMing it) what the message corresponds to. It wouldn't let people verify or decrypt previous/future messages either, but keeping the key stored might be detrimental to deniability indeed. We should probably recommend clients not to keep a hold of those HMAC keys forever (that means limiting the timeframe during which the message can be reported).

re: E2EE scheme that's under consideration for Mastodon 

@allo added some thoughts related to the longevity of the HMAC keys and franking value:

re: E2EE scheme that's under consideration for Mastodon 

@Thib Thank you for adding this to the discussion.

I am looking forward to the feature!

Sign in to participate in the conversation
Mastodon (instance perso)

This is a small personal instance running on a couple small ARM servers at home.