If you remember kobold letters, you already know not to blindly trust emails. But it’s not just HTML emails that can be deceiving. In this article, we’ll take a look at S/MIME and how we can use the concept of invisible salamanders to craft messages that tell each recipient a different story. Let’s talk about Salamander/MIME.
Invisible salamanders
But before we do that, I want to briefly introduce the attack that inspired me to investigate this issue: Invisible Salamanders. I would also like to take this opportunity to thank Sophie Schmieg for giving me the idea to look into this.
Invisible salamanders were introduced in 2018 by Yevgeniy Dodis, Paul Grubbs, Thomas Ristenpart and Joanne Woodage in their paper Fast Message Franking: From Invisible Salamanders to Encryptment. In this paper, they describe an attack against Facebook’s attachment franking that prevented abusive messages from being reported to Facebook.
They did this by sending two messages (or “salamanders” as Facebook calls them) with the same ciphertext but different keys. Due to an issue with the message deduplication in the abuse reporting system, only one of the ciphertext/key combinations would be reported to Facebook’s abuse team.
Since the chosen encryption scheme (in this case AES-GCM) does not commit to the key, the recipient doesn’t know if they are using the correct key. In the trivial case of a wrong key, this will result in the plaintext being made up of unusable garbage bytes when decrypted. However, by merging two messages in a file format-specific way, it is also possible to produce a ciphertext that can be decrypted into two different usable plaintexts. In their paper, Dodis et al. showed this for JPEG and BMP.
Salamander/MIME
While the message franking and deduplication issues are specific to the Facebook Messenger, the general issue of missing key commitment is not limited to this case.
Email encryption, and specifically S/MIME (although I see no reason why this shouldn’t apply to PGP/MIME as well), also has no key commitment. This becomes relevant when an email is sent to multiple recipients. In this article we’ll only look at the case of two recipients, but the principle can easily be extended to more.
S/MIME is – at its base – a fairly standard public-key encryption protocol, so the cleartext message is encrypted using a symmetric key algorithm and a random session key. This session key is then encrypted for each recipient using their respective public keys.
Invisible salamanders were targeting AES-GCM, but – although AES-GCM is part of the S/MIME v4.0 standard – we’ll have a better chance of getting our attack to work on a wide range of clients if we use AES-128-CBC, which is mandatory since S/MIME v3.2.
Luckily, adopting the concept for AES-CBC isn’t too difficult.
AES-CBC
CBC or Cipher Block Chaining is a mode of operation for block ciphers where each plaintext block is XORed with the previous ciphertext block (or IV if there isn’t any) before being fed into a block cipher. While the block cipher would normally use the same key for each block, the scheme will still work if we change the key for each block.
This allows us to adapt CBC as shown in the diagram below:
Modified CBC mode encryption
Since each block of ciphertext depends only on the corresponding plaintext, the key and the previous ciphertext block, the recipient will still be able to decrypt any block for which they have the key, even if they don’t know the key for all the blocks.
This allows us to construct a chipertext that decodes to different plaintexts depending on the key used, as long as each part is a multiple of the block size and the plaintext can handle some garbage bytes in the places where the key doesn’t fit.
Depending on the key, different parts will be decrypted.
The parts that decrypt to garbage bytes are something we will deal with later when constructing the message. For now, we need to look at another problem: padding.
When encrypting a message with a block cipher, the plaintext is usually padded to allow lengths that are not multiples of the block size. In our case, the expected padding is PKCS#7.
PKCS#7 padding adds n bytes to the plaintext, where each added byte has the value of n. The value of n is chosen so that the final length of the plaintext is a multiple of the block size and at least one byte of padding is added. So if the plaintext is already a multiple of the block size, a full block of padding is added.
For the second plaintext, corresponding to key 2, this is not a problem. We can just apply the padding as usual. However, the first plaintext, corresponding to key 1, ends on a block of garbage bytes. Because the padding is at least one byte long, the recipient can recognise if the padding is invalid, and most email clients will reject the message in this case. Therefore we have to make sure, the padding is valid for both keys.
The solution to this problem lies in the initialization vector (IV). Any change in the IV will propagate through the whole ciphertext and as we haven’t used the IV so far, we can freely chose it.
Only the padding of one of the plaintexts can be directly controlled.
By choosing a suitable IV we can produce any possible outcome for the last block, and while it is difficult to predict the whole block, the padding scheme is simple enough that we can just try different IVs until one of them produces a valid padding.
Since any block which has a 1 as its last byte will have valid padding, this solves the problem quickly and reliably.
The message
Now that we know how to create the ciphertext, we need to construct a suitable message that can handle the garbage bytes. Fortunately, email clients ignore everything before the headers. So unless we are unlucky enough to accidentally produce a valid header, we don’t have to worry about this.
However, garbage bytes that come after the message will be visible:
The naive attempt of just concatenating two messages does not work.
One approach that proved to be quite successful is to use multipart/alternative to declare all subsequent bytes as an unsupported alternative format. The following listing demonstrates this:
| |
Most email clients1 will just show the message “Axolotls are the best salamanders.” and completely ignore the unknown content type text/foo. This also gives us a convenient way to pad the message to have a length, that is a multiple of the block size, as also all padding will be ignored as part of the text/foo message.
The second message is even simpler: as already mentioned, all tested clients ignore the garbage bytes that come before the message. This means that the following message will work just fine:
| |
Bringing everything together
With the encryption scheme and the two messages, we now have everything we need to put the pieces together and construct an S/MIME encrypted email.
If we encrypt the two messages we just selected using the modified AES-CBC, we obtain the following ciphertext:
Cipher: AES-CBC
Key 1: c2259aa217688c75f25c4348d8a790dc
Key 2: 565a406a113cc81112c0be8b6570ba8b
IV: 99d2214a53b4cf2489fc0dea993166b2
Ciphertext:
140105ac9f23b44def3697d8a49ad9979d7e60a110b652be3d1ddfa304f3446c
fe69340abaf6e146ea05ef2dd17584f70052ba0cf9e0cef78b5f5ab2e0e391f8
1263f50102fb8653a47f6a00023e3e1161526bb863ecbb35ef1ce2215c043f67
7a14bfa55b825a9e0a91135b22ac24af2168b7b3cf3056faebda2c39e31683a0
957fc51fbbecf2d75372d7086f56ea7d0053ca48c755171fe35c06ee98bc8901
d28d422cf5a5d40e56e797bb4e321495f2cb94eeb6bcd824dbff208323d50412
80e757edb922508e70c1467d12eaf5819ab5a0ae4eb88220e8e31c9d23a02ba5
01bddd90486bd02cbea2cc21704d5d42ddd9594a357a575508455537630f131c
48f6b1358c972489432a41520bd33cd2059fbe2b36c8c367a8c124af1f33c705
efbde5b6f118f1a324b31b61e70875eaf35c9d557e31d8a82d86b93cb3f178a5
These are the values we need to construct the enveloped data. The EncryptedContentInfo looks like the following in every other S/MIME encrypted email: We use aes128_cbc as the algorithm, our IV as parameter and the ciphertext as encryptedContent.
The interesting part happens with the RecipientInfo. Usually we would encrypt the same AES key with the public key of each recipient. Instead we will use Key 1 for one recipient and Key 2 for the second recipient. Without having the private keys of both recipients, it is not possible to determine, that two different keys have been used.
I have uploaded example.eml and the private keys of Alice and Bob (the password is 1234) for readers who want to reproduce the following steps.
If we decrypt the email with Alice’s key, we get the multipart/alternative message with garbage bytes at the end of the message:
The message can be decrypted with Alice's private key.
When the email is opened in an email client (like Thunderbird here, but it works the same way in other clients like Outlook or Evolution1), the text/plain alternative is displayed:
This is what the email looks like for Alice.
If we decrypt the email with Bob’s key, we get the text/plain message with garbage bytes at the beginning of the message:
The message can be decrypted with Bob's private key.
The garbage bytes are not visible when the email is opened in an email client:
This is what the email looks like for Bob.
We are now able to send an email to multiple recipients, each with a different message.
What does that mean and how can we fix this?
Did we break S/MIME? Technically not, as we did not violate any security guarantees. Email encryption without a signature only guarantees confidentiality, which remains intact. However, for most users this will not make a meaningful difference. Especially in the context of phishing, it is more about the expectations of the user than about hard guarantees.
This brings us to the first possible mitigation of the problem: do not trust emails that are encrypted but not signed. Email clients could encourage this by not showing a green tick or lock in this case, but a more detailed message. There are not many situations where this combination is desirable anyway.
But it’s usually better not to put the responsibility for security decisions on the user. Could email clients implement a fix for Salamander/MIME?
Salamander/MIME can’t be detected without decrypting the message or at least comparing the session key. With access to multiple private keys, the session keys (or simply the decrypted messages) can be compared to reliably detect the problem. While this is not a viable solution in most environments, it may be an option for email encryption gateways.
With access to only one of the private keys, the garbage bytes could still be used as a heuristic to detect this, but this would also likely break existing implementations as the email is technically valid. I informed the teams responsible for Thunderbird, Evolution and Outlook, which are the main S/MIME clients, of my findings in advance. All three teams decided – given the lack of options and the limited risk – to take no immediate action.
To prevent Salamander/MIME reliably, the S/MIME specification would have to be changed. If a future version of S/MIME introduced a scheme that supported key commitment, we would have a guarantee that all recipients would receive the same message, and Salamander/MIME would be fixed for good (once people actually use the new scheme).
