Malleability (cryptography)

From Wikipedia, the free encyclopedia

Malleable is a term used in the analysis of cryptographic algorithms:

A malleable encryption algorithm allows transformations on the ciphertext to produce meaningful changes in the plaintext. That is, given a plaintext P and the corresponding ciphertext C = E(P), it is possible to generate C₁ = f(C) so that the decryption of C₁ is a function P₁ = f'(P) of the original plaintext P, with arbitrary but known functions f and f'.

Stream ciphers are examples of malleable encryption algorithms. In a stream cipher, the ciphertext is produced by taking the exclusive or of the plaintext and a stream based on a secret key (). Given an arbitrary P₁, it is possible to generate .

Malleability is 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 can change the amount of the transaction, or the recipient of the funds.

Other malleable encryption algorithms include:

RSA. If the attacker obtains the ciphertext ( where P is the plaintext and n is the public modulus) the attacker can produce the ciphertext C₁ corresponding to any P₁ = kP by multiplying the original ciphertext by . For this reason, RSA is commonly used together with padding methods such as OAEP or PKCS1.

ElGamal is similarly malleable: for example, given an encryption (c₁,c₂) of some (possibly unknown) message m, one can easily construct an encryption of the message 2m. Therefore ElGamal is not secure under chosen ciphertext attack. On the other hand, the Cramer-Shoup system (which is based on ElGamal) is secure under chosen ciphertext attack.

It is possible to build non-malleable encryption algorithms from malleable ones.

Paillier is malleable "by design". It is an additive homomorphic cryptosystem; this means that, given only the public-key and the encryption of m₁ and m₂, one can compute the encryption of m₁ + m₂.