Editing Malleability (cryptography) (section)

==Example malleable cryptosystems==
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 <math>k</math>, as <math>E(m) = m \oplus S(k)</math>. An adversary can construct an encryption of <math>m \oplus t</math> for any <math>t</math>, as <math>E(m) \oplus t = m \oplus t \oplus S(k) = E(m \oplus t)</math>.

In the [[RSA (algorithm)|RSA]] cryptosystem, a plaintext <math>m</math> is encrypted as <math>E(m) = m^e \bmod n</math>, where <math>(e,n)</math> is the public key. Given such a ciphertext, an adversary can construct an encryption of <math>mt</math> for any <math>t</math>, as <math display="inline">E(m) \cdot t^e \bmod n = (mt)^e \bmod n = E(mt)</math>. For this reason, RSA is commonly used together with [[padding (cryptography)|padding]] methods such as [[Optimal Asymmetric Encryption Padding|OAEP]] or PKCS1.

In the [[ElGamal]] cryptosystem, a plaintext <math>m</math> is encrypted as <math>E(m) = (g^b, m A^b)</math>, where <math>(g,A)</math> is the public key. Given such a ciphertext <math>(c_1, c_2)</math>, an adversary can compute <math>(c_1, t \cdot c_2)</math>, which is a valid encryption of <math>tm</math>, for any <math>t</math>.
In contrast, the [[Cramer-Shoup system]] (which is based on ElGamal) is not malleable.

In the [[Paillier cryptosystem|Paillier]], [[ElGamal]], and [[RSA (algorithm)|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 <math>m_1</math> and <math>m_2</math>, one can compute a valid encryption of their sum <math>m_1+m_2</math>. In ElGamal and in RSA, one can combine encryptions of <math>m_1</math> and <math>m_2</math> to obtain a valid encryption of their product <math>m_1 m_2</math>.

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 [[Cipher Block Chaining|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.