Editing Malleability (cryptography)

{{Short description|Property of some cryptographic algorithms}}
'''Malleability''' is a property of some [[cryptography|cryptographic]] [[algorithm]]s.<ref>{{cite journal
 | first1 = Danny 
 | last1 = Dolev
 | author2-link = Cynthia Dwork
 | first2 = Cynthia
 | last2 = Dwork
 | author3-link = Moni Naor
 | first3 = Moni
 | last3 = Naor
 | title = Nonmalleable Cryptography
 | journal = [[SIAM Journal on Computing]]
 | volume = 30
 | issue = 2
 | pages = 391–437
 | year = 2000
 | doi = 10.1137/S0097539795291562
| citeseerx = 10.1.1.49.4643
 }}</ref> An encryption algorithm is "malleable" if it is possible to transform a [[ciphertext]] into another ciphertext which decrypts to a related [[plaintext]]. That is, given an encryption of a plaintext <math>m</math>, it is possible to generate another ciphertext which decrypts to <math>f(m)</math>, for a known function <math>f</math>, without necessarily knowing or learning <math>m</math>.

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, "{{mono|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 change the amount of the transaction, or the recipient of the funds, e.g.  "{{mono|TRANSFER $0100000.00 TO ACCOUNT #227}}". 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 <math>m</math> into a valid encryption of <math>f(m)</math>  (for some restricted class of functions <math>f</math>) without necessarily learning <math>m</math>. Such schemes are known as [[homomorphic encryption]] schemes.

A cryptosystem may be [[Semantic security|semantically secure]] against [[Chosen-plaintext attack|chosen-plaintext attacks]] or even non-adaptive [[Chosen-ciphertext attack|chosen-ciphertext attacks]] (CCA1) while still being malleable. However, security against [[Adaptive chosen-ciphertext attack|adaptive chosen-ciphertext attacks]] (CCA2) is equivalent to non-malleability.<ref name=":0">{{Cite book|work= Advances in Cryptology – CRYPTO '98 |title= Relations among notions of security for public-key encryption schemes |last1=Bellare |first1=Mihir |last2=Desai |first2=Anand |last3= Pointcheval |first3=David |last4=Rogaway |first4=Phillip |date= 1998-08-23 |publisher= Springer Berlin Heidelberg |isbn= 978-3540648925 |editor-last= Krawczyk |editor-first= Hugo |series= Lecture Notes in Computer Science |pages= 26–45 |language=en |doi= 10.1007/bfb0055718}}</ref>

==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.

== Complete non-malleability ==
Fischlin, in 2005, defined the notion of complete non-malleability as the ability of the system to remain [[Non-Malleable Codes|non-malleable]] while giving the adversary additional power to choose a new public key which could be a function of the original public key.<ref>{{Cite book|last=Fischlin|first=Marc|title=Automata, Languages and Programming |date=2005-07-11|chapter=Completely Non-malleable Schemes|volume=3580|series=Lecture Notes in Computer Science|language=en|publisher=Springer, Berlin, Heidelberg|pages=[https://archive.org/details/automatalanguage2005inte/page/779 779–790]|doi=10.1007/11523468_63|isbn=9783540275800|citeseerx=10.1.1.501.6445|chapter-url=https://archive.org/details/automatalanguage2005inte/page/779}}</ref> 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]]

== References ==
{{reflist}}

[[Category:Cryptography]]
[[Category:Theory of cryptography]]