Malleability (cryptography)

related topics
{math, number, function}
{system, computer, user}
{company, market, business}
{war, force, army}

Malleability is a property of some cryptographic algorithms.[1] An encryption algorithm is malleable if it is possible for an adversary to transform a ciphertext into another ciphertext which decrypts to a related plaintext. That is, given an encryption of a plaintext m, it is possible to generate another ciphertext which decrypts to f(m), for a known function f, without necessarily knowing or learning m.

Malleability is often an undesirable property in a general-purpose cryptosystem, since it allows an attacker to modify the contents of a message. For example, suppose that a bank uses a stream cipher to hide its financial information, and a user sends an encrypted message containing, say, "TRANSFER $0000100.00 TO ACCOUNT #199." If an attacker can modify the message on the wire, and can guess the format of the unencrypted message, the attacker could be able to change the amount of the transaction, or the recipient of the funds, e.g. "TRANSFER $0100000.00 TO ACCOUNT #227."

On the other hand, some cryptosystems are malleable by design. In other words, in some circumstances it may be viewed as a feature that anyone can transform an encryption of m into a valid encryption of f(m) (for some restricted class of functions f) without necessarily learning m. Such schemes are known as homomorphic encryption schemes.

A cryptosystem may be semantically secure against chosen plaintext attacks or even non-adaptive chosen ciphertext attacks (CCA1) while still being malleable. However, security against adaptive chosen ciphertext attacks (CCA2) is equivalent to non-malleability.

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

In the RSA cryptosystem, a plaintext m is encrypted as E(m) = memod n, where (e,n) is the public key. Given such a ciphertext, an adversary can construct an encryption of mt for any t, as 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 m is encrypted as E(m) = (gb,mAb), where (g,A) is the public key. Given such a ciphertext (c1,c2), an adversary can compute (c_1, t \cdot c_2), which is a valid encryption of tm, for any t. In contrast, the Cramer-Shoup system (which is based on ElGamal) is not malleable.

Full article ▸

related documents
Calculus with polynomials
Partial function
Commutative ring
Byte-order mark
Algebraic extension
Extractor
Residue (complex analysis)
Steiner system
Hash collision
Weierstrass–Casorati theorem
Double negative elimination
Borel-Cantelli lemma
Iteration
Subtraction
Zeta distribution
Subalgebra
Nowhere dense set
Geometric mean
Static code analysis
Degenerate distribution
Category (mathematics)
Bernoulli process
Pseudometric space
Magma computer algebra system
Fibonacci coding
Differential cryptanalysis
Atlas Autocode
Waring's problem
Heap (data structure)
Abstract factory pattern