Malleability is a property of some
cryptographic algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
s. An encryption algorithm is "malleable" if it is possible to transform a
ciphertext
In cryptography, ciphertext or cyphertext is the result of encryption performed on plaintext using an algorithm, called a cipher. Ciphertext is also known as encrypted or encoded information because it contains a form of the original plaintex ...
into another ciphertext which decrypts to a related
plaintext
In cryptography, plaintext usually means unencrypted information pending input into cryptographic algorithms, usually encryption algorithms. This usually refers to data that is transmitted or stored unencrypted.
Overview
With the advent of comp ...
. That is, given an encryption of a plaintext
, it is possible to generate another ciphertext which decrypts to
, for a known function
, without necessarily knowing or learning
.
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, "." If an attacker can modify the message on the wire, and can guess the format of the unencrypted message, the attacker could change the amount of the transaction, or the recipient of the funds, e.g. "". Malleability does not refer to the attacker's ability to read the encrypted message. Both before and after tampering, the attacker cannot read the encrypted message.
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
into a valid encryption of
(for some restricted class of functions
) without necessarily learning
. Such schemes are known as
homomorphic encryption
Homomorphic encryption is a form of encryption that permits users to perform computations on its encrypted data without first decrypting it. These resulting computations are left in an encrypted form which, when decrypted, result in an identical ...
schemes.
A cryptosystem may be
semantically secure In cryptography, a semantically secure cryptosystem is one where only negligible information about the plaintext can be feasibly extracted from the ciphertext. Specifically, any probabilistic, polynomial-time algorithm (PPTA) that is given the ciph ...
against
chosen plaintext attack
A chosen-plaintext attack (CPA) is an attack model for cryptanalysis which presumes that the attacker can obtain the ciphertexts for arbitrary plaintexts.Ross Anderson, ''Security Engineering: A Guide to Building Dependable Distributed Systems''. ...
s or even non-adaptive
chosen ciphertext attack
A chosen-ciphertext attack (CCA) is an attack model for cryptanalysis where the cryptanalyst can gather information by obtaining the decryptions of chosen ciphertexts. From these pieces of information the adversary can attempt to recover the hidden ...
s (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
A pseudorandom sequence of numbers is one that appears to be statistically random, despite having been produced by a completely deterministic and repeatable process.
Background
The generation of random numbers has many uses, such as for rand ...
stream based on a secret key
, as
. An adversary can construct an encryption of
for any
, as
.
In the
RSA cryptosystem, a plaintext
is encrypted as
, where
is the public key. Given such a ciphertext, an adversary can construct an encryption of
for any
, as
. For this reason, RSA is commonly used together with
padding methods such as
OAEP or PKCS1.
In the
ElGamal cryptosystem, a plaintext
is encrypted as
, where
is the public key. Given such a ciphertext
, an adversary can compute
, which is a valid encryption of
, for any
.
In contrast, the
Cramer-Shoup system (which is based on ElGamal) is not malleable.
In the
Paillier
The Paillier cryptosystem, invented by and named after Pascal Paillier in 1999, is a probabilistic asymmetric algorithm for public key cryptography. The problem of computing ''n''-th residue classes is believed to be computationally difficult. The ...
,
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
and
, one can compute a valid encryption of their sum
. In ElGamal and in RSA, one can combine encryptions of
and
to obtain a valid encryption of their product
.
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
In cryptography, a message authentication code (MAC), sometimes known as a ''tag'', is a short piece of information used for authenticating a message. In other words, to confirm that the message came from the stated sender (its authenticity) and ...
is required to guard against any method of tampering.
Complete non-malleability
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.
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.
See also
*
Homomorphic encryption
Homomorphic encryption is a form of encryption that permits users to perform computations on its encrypted data without first decrypting it. These resulting computations are left in an encrypted form which, when decrypted, result in an identical ...
References
{{reflist
Cryptography