JVNTA#94494000
Malleability attack against executables encrypted by CBC mode with no integrity check

Overview

Researchers at NTT, University of Hyogo, and NEC have identified a security issue that leads to executing arbitrary code in executable files that are encrypted by CBC mode with no integrity check. This issue has been published in ACNS 2020.

There is a risk that an encrypted executable file may be manipulated by an attacker without prior knowledge of plaintext or secret key, resulting in arbitrary code execution if the developer does not take measures against the attack.

Developers can refer to the "Solution" section for countermeasures.

Products Affected

Encryption systems or software that use the following block cipher modes of operation with no integrity check may be affected. 

• CBC mode
• CFB mode

Description

About CBC mode

CBC mode is one of the most commonly used modes of operation for a block cipher, a type of symmetric key encryption. CBC mode encrypts each data block derived from a plaintext block XORed with the previous cipher block. The first block of plaintext is XORed with a value called IV (initialization vector).

In this article, let M₁, M₂, ..., M_n be each plaintext block, C₁, C₂, ..., C_n, be each cipher block, and E_k be an encryption algorithm, respectively.

Mechanism of attack against CBC mode encryption without an integrity check

Multiple plaintext blocks can be modified to arbitrary values by leveraging the CBC mode's characteristic of performing XOR with the previous cipher block. This attack requires the following preconditions.

Precondition 1: An attacker knows one X-Y pair (X: pre-encryption data block; Y: encrypted data block) where Y = E_k(X).
Precondition 2: An attacker is able to modify arbitrary cipher blocks

Tampering with plaintext blocks

If an attacker attempts to tamper with the second plaintext block represented by M₂ in the figure above, the value of M₂ is found by the following formula:

C₁ ⊕ X = M₂

Here, if any cipher block can be changed to any value (precondition 2), the attacker can modify M₂ by replacing C₁ with (X ⊕ M_target), as follows:

(X ⊕ M_target) ⊕ X = M_target

However, the value of M₁ will be changed to an unpredictable value since C₁ has been changed.



Also, since the attacker can create X by replacing C₄ with Y, M₄ can be modified to arbitrary value by replacing C₃ with (X ⊕ M_target2). However, M₃ will be changed to an unexpected value.



In this way, with a pair of X and Y where Y = E_k(X), it is possible to modify every other plaintext block to an arbitrary value, even if the attacker does not have the key. Instead, the plaintext will be broken every other block.

This type of attack is known as CBC malleability attack.

Attack on executable files

The executable file generally has the same header value for each CPU architecture. An attacker can calculate the X value from the header and insert the shellcode into a specific part of the file (plaintext blocks), which leads to arbitrary code execution. Although controllable blocks are not contiguous, by using the jump instruction (cf. Bletsch et al., 2011; Carlini and Wagner, 2014), it is possible to execute code that is longer than a single block.



This attack can be successfully conducted if the first block of the shellcode is injected in the proper location in the file. However, this study shows the attacker may be able to inject and execute arbitrary code with a non-negligible probability.

Impact

Although the attack can only be successful when an attacker successfully predicts the proper location to inject the attack code, and the probability of success is 2^-10 to 2^-18, an attacker can cause arbitrary code execution. This could lead to various malicious activities such as application execution and backdoor injection.

Solution

Software developers should implement the following countermeasures:

Use CBC mode with an integrity check by a message authentication code (MAC)

It is effective to implement an integrity check by using MAC.

MAC value T of (C || IV) can be derived as follows, where K’ key is different from that used for encryption. The tuple (T, C || IV) should be kept as the ciphertext for validation.

T = MAC (K', C || IV)

** Note that CRYPTREC Ciphers List recommends CMAC and HMAC for MAC algorithms.

Before decrypting the data, you should compute T = MAC (K' || IV) again and confirm that the re-computed T matches the stored T. You should decrypt the data only when both T values are the same. If a cipher block C has been tampered with, the both T values will be different, and you can detect tampering and prevent the attack. Since the attacker does not know the value of K', they cannot compute the correct MAC value T = MAC (K', C' || IV) for tampered cipher block C'.

Use XTS mode

When you need to preserve the message length, you can use XTS mode instead of CBC.

For application users, the following measures are recommended:

Even if your application uses CBC mode without an integrity check, the application may let you change the encryption algorithm or modes of operation. In this case, you can select a mode other than CBC or CFB to avoid the attack.