Notes on Multiple Encryption and Content Filtering
Posted by ekr on 22 May 2022
As I mentioned in my post on EU's proposed CSAM regulation, any content filtering system has to worry about nonconforming clients which are trying to evade filtering. One obvious approach is to lie about message contents or the output of filtering algorithms. Another method of nonconformance that is often proposed is multiple encryption, in which you use an ordinary messaging system like WhatsApp or iMessage, but before you send messages you first encrypt them yourself, so that even if the main messaging system were broken, your data would still be secure.
Why not just use a different system? #
As noted in the Wikipedia page I linked to above, one reason to do multiple encryption is just to provide defense in depth in case the outer system is broken, but in this case, we are assuming that the outer system is broken because it is subject to some detection/monitoring requirement, so it's not adding much security value. It's not that hard to build your own messaging system, so why not just use one that isn't being monitored, for instance because it's too small to be subject to regulations, is located outside of the relevant jurisdiction, or has just decided not to comply?
The most obvious reason for using a common system is to conceal your activities: if most people use a messaging system that is subject to monitoring and you choose to use one that is not, that's a potential signal that you really want to hide and so are worth investigating in some other fashion. This is especially true if you are using a program that is explicitly associated with an activity that the authorities want to investigate as with something like Mujahedeen Secrets. Moreover, if you have to run your own messaging servers, then that's a point of attack, which you don't have if you encrypt messages and just send them over WhatsApp.
Detection and Steganography #
One obvious problem with multiple encryption is that the messaging system—which, recall, we assume is compromised—can just change their filtering algorithms to detect your inner encrypted messages and block or report them. How effective this is depends on precisely how the monitoring is done. At a high level, there are two main possibilities:
Targeted monitoring in which communications are generally not monitored but the authorities can target specific people or messages for monitoring. This is sometimes referred to as "exceptional access".
Continuous monitoring in which much or all of the content is scanned (this is what the EU regulation seems to contemplate).
In an exceptional access regime, because communications are generally encrypted and therefore can't be routinely scanned, your use of multiple encryption won't ordinarily be detected. Of course, if you are one of the people who is subject to surveillance, then that will be detected, but then all that is revealed is that you are using an inner layer of encryption, which may look suspicious, but then you wouldn't (at least in theory) be subject to exceptional access unless you were already suspected. It may even not result in your messages being blocked because law enforcement and intelligence agencies often want surveillance to be secret, and blocking your messages would reveal that they had been decrypting them.
By contrast, in a continuous monitoring regime, most if not all messages will be scanned and so just encrypting will be easily detected and can be blocked. This blocking doesn't reveal anything useful to the people using inner encryption because the fact of monitoring isn't a secret.
This doesn't mean that it's not possible to multiply encrypt in these situations, but it does mean that you have to do more than just encrypt; you need to have the encrypted data look like ordinary messages. There has been a fair amount of work on what's called steganography, which involves hiding messages in other messages. For instance, one might hide the true message in the first word of each line, like so:
[Source: Yahoo News, original by Sairam Gudiseva]
There are a lot of possible techniques here, such as hiding data in the low order bits of images or audio files. In general, anywhere that there is room for variation there is room to conceal data. The rise of machine learning techniques for generating content (e.g., GPT-3) also makes it easy to generate new plausible content which you can then hide your message in, as opposed to requiring you to take some existing content and tweak it (thus making it susceptible to detection based on comparing it to the original template).
Steganography has seen less work than other areas of communications security, so if this kind of thing sees wide use it will probably be a bit of an arms race for a while between concealment and detection, but I would expect concealment to win most of the time, just because there are is already so much natural variation in messages and so many ways to conceal information. False positives are even more of a problem here, because—unlike CSAM—it won't really be possible to manually determine whether something is steganography or not and so you're just left blocking a bunch of users.
Key Management #
If you're going to encrypt data, you need to have encryption keys that aren't known to the attacker, otherwise they will just try to decrypt everything that goes by with each key and see what works (this is known as "trial decryption"). Naively, this involves setting up a whole new identity system, as you're effectively running your own messaging system on top of someone else's (see here for a bit on what this involves) which is really a pain, but actually I think you could get a lot of value with much less.
More on Active Attacks #
Suppose that the multiple encryption system works by embeddeding DH keys in the low order bits of specific pixels in each image. When Alice and Bob first exchange messages, an active attacker could just stomp them with its own bits, which would result in either (1) establishing a pair of keys with Alice and Bob (2) or establishing what is apparently a pair of shared keys but is actually nothing (we could in principle have some kind of error check but obviously we don't want to do that because it makes inner encryption easy to detect). They then look for the first message that should be encrypted and try to decrypt it: if it works, then multiple encryption was probably in use; if it's garbage, then probably not.
But now what happens if there is another kind of multiple encryption which encodes a different kind of key in the same bits? The service can only try one of these, and if they get it wrong, then people can't establish keys, which they might notice, at which point word gets out that they are mounting active attacks. Similarly, if there is any method for double-checking the established keys (e.g., something like Signal's "safety numbers") then this will be quickly detected.
The basic idea would be to just do unauthenticated key establishment over the existing messaging system. What this means is that you use the same cryptographic protocols that you would use to set up keys (e.g., Diffie-Hellman) but you don't bother to authenticate the other side. This is much technically easier because you don't need an identity system at all; you're just relying on the identities provided by the existing messaging system you are running on top of (another good reason to use an existing messaging system rather than building your own). One could also imagine something intermediate where people publish their keys on Facebook or Twitter.
Of course, unauthenticated encryption leaves you open to active attack by the messaging system where it tries to establish its own keys with each side, but this kind of attack is going to be a lot more work than just passively monitoring each message, and they'll have to do it for every potential kind of inner encryption and for every pair of users. Moreover, this inherently involves damaging the messages, which is something that is likely to get noticed quite quickly if anybody bothers to check. So, while you're potentially vulnerable to a very dedicated attacker, in practice this would give you a lot of security.
One Versus Two-Sided Systems #
One very important limitation of multiple encryption systems like this is that they only work when both sides participate: each user needs to install some kind of new software that will handle the multiple encryption, and if you are just running the standard software, you'll either get something that looks like random junk or like whatever innocuous cover traffic is being used to hide the encrypted data in, depending on whether steganography is in use. This means that multiple encryption can be used to evade filtering in contexts like trading CSAM or buying drugs where (presumably) both sides have an interest in concealment, but can't really be used to evade filtering in cases like solicitation of minors because the minor isn't going to have installed the new program (and of course the service can fairly easily scan for a suggestion that they do so).
Of course some people just like their privacy, but the question is whether this is a useful signal on average. ↩︎