The Conflict Between Malleability and Chosen Ciphertext Security

16 concepts4 papers1 proposal

In modern cryptography, the gold standard for privacy is security against adaptive chosen-ciphertext attacks (known as CCA2 security). In a CCA2 security game, an adversary is given a target ciphertext $C$ and wants to deduce its underlying plaintext $M$. To help them, they are given access to a "decryption oracle"—a black box that will decrypt any ciphertext they submit, with exactly one catch: they cannot submit the target ciphertext $C$ itself.

This setup sounds highly restrictive for the attacker, but it contains a fatal flaw if the underlying encryption scheme is malleable. Malleability means that an adversary can take a valid ciphertext $C$ and mathematically transform it into a different valid ciphertext $C'$ such that $C'$ decrypts to a plaintext $M'$ that is predictably related to $M$.

If a scheme is both malleable and gives the attacker access to a decryption oracle, the security model collapses. The attacker simply transforms the target ciphertext $C$ into $C'$, submits $C'$ to the oracle (which is allowed because $C' \neq C$), receives $M'$, and reverses the mathematical transformation to uncover the secret message $M$.

Understanding this fundamental tension—and how it manifests across algebraic structures and protocol implementations—is critical to designing secure encryption systems.


The Homomorphic Paradox: Required vs. Forbidden Malleability

The conflict between malleability and CCA2 security is nowhere more apparent than in Homomorphic Encryption (HE). By definition, homomorphic encryption allows a third party to perform computations on encrypted data. If you have an encryption of $A$ and an encryption of $B$, an additively homomorphic scheme lets you combine them to create a valid encryption of $A + B$ without ever decrypting them.

This means homomorphic encryption is intentionally malleable.

Because of this inherent property, achieving CCA2 security in a fully homomorphic scheme is mathematically impossible. Yet, cryptographic designs occasionally attempt to bridge this gap. In Analysis of Gong et al.'s CCA2-Secure Homomorphic Encryption, Lee et al. expose this fundamental incompatibility by breaking a scheme that claimed to achieve both properties.

The mechanism the authors use is a re-randomization attack. Because the homomorphic scheme must allow ciphertexts to be altered during computation, an adversary can exploit these exact algebraic operations to alter the challenge ciphertext. By raising components of the ciphertext to a random power, the adversary generates a completely new, valid ciphertext that still encrypts the exact same underlying message. When this re-randomized ciphertext is handed to the decryption oracle, the oracle decrypts it completely, handing the original plaintext straight back to the attacker.


Inherited Malleability in Composite Schemes

This vulnerability is not unique to homomorphic encryption. Many standard public-key primitives, such as ElGamal encryption, rely on algebraic groups where multiplication or exponentiation maps cleanly from the ciphertext space to the plaintext space. When designers bundle these malleable primitives together to build more complex features, the resulting composite schemes often quietly inherit these vulnerabilities.

For example, in Insecurity of the Public Key Encryption with Filtered Equality Test Proposed by Huang et al, Lee et al. analyze a specialized protocol designed to test whether two ciphertexts contain the same message without decrypting them. The underlying architecture relied on ElGamal-type structures. The authors demonstrate that because the protocol lacked explicit, robust binding mechanisms to lock the components of the ciphertext together, an attacker could mathematically manipulate a target ciphertext into a related variant. By passing this variant to a decryption oracle, the attacker could systematically extract information about the target message, proving that combining malleable components without strict isolation guarantees CCA2 insecurity.


Structural Malleability: The Danger of Unauthenticated Padding

Malleability does not only arise from elegant abstract algebra; it can also be introduced mechanically through protocol design. In practical block-cipher implementations, messages rarely fit perfectly into fixed block sizes (like 16 bytes). To fix this, protocols append "padding" data to fill out the final block.

If a protocol fails to cryptographically verify the integrity of this padding, it introduces structural malleability.

This exact vulnerability was uncovered in Telegram's custom encryption protocol, MTProto. In On the CCA (in)security of MTProto, Orlandi et al. demonstrate that the protocol's authentication tag failed to cover the entirety of the transmitted data—specifically excluding the padding segments.

MTProto Ciphertext Structure:
[ Encrypted Message Data ] [ Unauthenticated Padding ]
  ^ Covered by Auth Tag      ^ Ignored by Auth Tag (Malleable!)

Because the decryption process did not verify the integrity of the padding length or content, the authors show that an attacker could append random data or alter the padding bytes without invalidating the ciphertext. The receiver's decryption oracle would process this modified ciphertext, strip away the altered padding, and successfully return the original plaintext with 100% probability. By creating multiple valid ciphertexts for the same message, the protocol violated the core non-malleability requirements of authenticated encryption, opening the door to chosen-ciphertext exploits.


Enforcing Rigidity: Padding Schemes as Malleability Blockers

To safely use naturally malleable public-key functions like RSA or Rabin, cryptographers must use a mechanism that destroys their algebraic flexibility. This is achieved by using cryptographic padding schemes that act as rigidity enforcers.

Instead of encrypting a raw message $M$, the message is first processed through a padding scheme (like Optimal Asymmetric Encryption Padding, or OAEP). OAEP uses a two-round Feistel network with cryptographic hash functions to highly entangle the message with random noise. This ensures that if an attacker attempts to mathematically manipulate the resulting ciphertext, the underlying plaintext structure is completely obliterated. When the decryption oracle checks the decrypted block, the padding verification fails, and the oracle rejects the query rather than returning a related message.

Raw Message (Malleable) ──> [ Padding Scheme (e.g., OAEP/SAEP) ] ──> Rigid Block ──> RSA/Rabin ──> Non-Malleable Ciphertext

While standard OAEP requires two rounds of hashing to achieve this security reduction, Dan Boneh demonstrates in Simplified OAEP for the RSA and Rabin Functions that this overhead can be reduced. Boneh introduces SAEP and SAEP+, proving that for specific algebraic functions like RSA and Rabin, a single round of Feistel-like padding is sufficient to guarantee chosen-ciphertext security. By ensuring that any ciphertext manipulation causes an immediate padding check failure, these simplified schemes efficiently eliminate the malleability that attackers rely on to exploit decryption oracles.

Key Foundational Work

On the CCA (in)security of MTProto (2015) — contributed 6 concept elements to this direction.
Simplified OAEP for the RSA and Rabin Functions (2001) — contributed 1 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 4 papers
  2. Version 1 · 2026-10-04 · 8 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_ciphertext_malleability_malleability_sec_1fea7809,
  title = {ciphertext malleability (malleability-security trade-off)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/ciphertext-malleability-malleability-security-trade-off/rdr_1fea7809e0cb4d7b95e9f6b69b3afdee},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 2, frozen text):

@misc{lacuna_ciphertext_malleability_malleability_sec_1fea7809_v2,
  title = {ciphertext malleability (malleability-security trade-off)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/ciphertext-malleability-malleability-security-trade-off/rdr_1fea7809e0cb4d7b95e9f6b69b3afdee/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake