Malleability (cryptography)

In a stream cipher, the ciphertext is produced by taking the exclusive or of the plaintext and a pseudorandom stream based on a secret key ${\displaystyle k}$, as ${\displaystyle E(m)=m\oplus S(k)}$. An adversary can construct an encryption of ${\displaystyle m\oplus t}$ for any ${\displaystyle t}$, as ${\displaystyle E(m)\oplus t=m\oplus t\oplus S(k)=E(m\oplus t)}$.

In the RSA cryptosystem, a plaintext ${\displaystyle m}$ is encrypted as ${\displaystyle E(m)=m^{e}{\bmod {n}}}$, where ${\displaystyle (e,n)}$ is the public key. Given such a ciphertext, an adversary can construct an encryption of ${\displaystyle mt}$ for any ${\displaystyle t}$, as ${\textstyle E(m)\cdot t^{e}{\bmod {n}}=(mt)^{e}{\bmod {n}}=E(mt)}$. For this reason, RSA is commonly used together with padding methods such as OAEP or PKCS1.

In the ElGamal cryptosystem, a plaintext ${\displaystyle m}$ is encrypted as ${\displaystyle E(m)=(g^{b},mA^{b})}$, where ${\displaystyle (g,A)}$ is the public key. Given such a ciphertext ${\displaystyle (c_{1},c_{2})}$, an adversary can compute ${\displaystyle (c_{1},t\cdot c_{2})}$, which is a valid encryption of ${\displaystyle tm}$, for any ${\displaystyle t}$. In contrast, the Cramer-Shoup system (which is based on ElGamal) is not malleable.

In the Paillier, ElGamal, and RSA cryptosystems, it is also possible to combine several ciphertexts together in a useful way to produce a related ciphertext. In Paillier, given only the public key and an encryption of ${\displaystyle m_{1}}$ and ${\displaystyle m_{2}}$, one can compute a valid encryption of their sum ${\displaystyle m_{1}+m_{2}}$. In ElGamal and in RSA, one can combine encryptions of ${\displaystyle m_{1}}$ and ${\displaystyle m_{2}}$ to obtain a valid encryption of their product ${\displaystyle m_{1}m_{2}}$.

Block ciphers in the cipher block chaining mode of operation, for example, are partly malleable: flipping a bit in a ciphertext block will completely mangle the plaintext it decrypts to, but will result in the same bit being flipped in the plaintext of the next block. This allows an attacker to 'sacrifice' one block of plaintext in order to change some data in the next one, possibly managing to maliciously alter the message. This is essentially the core idea of the padding oracle attack on CBC, which allows the attacker to decrypt almost an entire ciphertext without knowing the key. For this and many other reasons, a message authentication code is required to guard against any method of tampering.

Fischlin, in 2005, defined the notion of complete non-malleability as the ability of the system to remain non-malleable while giving the adversary additional power to choose a new public key which could be a function of the original public key.[3] In other words, the adversary shouldn't be able to come up with a ciphertext whose underlying plaintext is related to the original message through a relation that also takes public keys into account.

• Homomorphic encryption