24

In short: You must authenticate the IV. Which particular attacks apply if you don't depends on the block cipher mode; I will give two common examples. In CTR mode, an attacker who fiddles with the IV can forge authenticated messages, but the content of the corresponding plaintext is beyond his control (since he doesn't know the key). Depending on the ...


21

Complexity leveraging is a type of reduction where the "reduction algorithm" runs in a complexity class that is greater than the adversary. For example, one may construct a simulator that runs in time $n^{\log n}$ although the adversary is only polynomial time. When considering the simulation paradigm, this is not very satisfactory. For example, in ...


12

I know of two lines of work on this question. It is indeed possible to allow malleability but still make some guarantees in the presence of a chosen-ciphertext attack: Manoj Prabhakaran & Mike Rosulek: Reconciling Non-malleability with Homomorphic Encryption. Dan Boneh and Gil Segev and Brent Waters: Targeted Malleability: Homomorphic Encryption for ...


8

A cipher $E_k(m)$ is malleable if there is a nontrivial binary relation $\sim$ on messages such that given $c = E_k(m)$, it is easy to find $c' = E_k(m')$ with $m \sim m'$. For example, AES-CTR is malleable because for any $m$ and $m'$ with $m' = m \oplus \delta$, it is easy to compute $$c' = c \oplus \delta = E_k(m) \oplus \delta = E_k(m \oplus \delta) = ...


8

The Problem The One-Time Pad offers perfect secrecy. However, it does not protect the integrity or authenticity of the message - An adversary can flip bits of the ciphertext, and the receiver will have no way of detecting the manipulation. Consider the case where a single bit is sent encrypted with a One-Time Pad, used to indicate a "yes/no" value as to ...


6

It seems like you are asking about converting an IND-CPA encryption scheme into an IND-CCA one. In the symmetric-key setting, the standard approach that works is Encrypt-then-MAC. In the public-key setting, this is a longstanding open question. There is no known black-box construction of IND-CCA from IND-CPA, nor is there a known impossibility of such a ...


6

As mikeazo notes in the comments, RSA operates on the ring $\mathbb Z / n\mathbb Z$ of integers modulo $n$, for a given modulus $n = pq$. In this ring, $$E(m) \cdot t^e \equiv m^e \cdot t^e \equiv (mt)^e \equiv E(mt)\ \pmod n.$$ In particular, for $n = 35$, $e = 23$, $$17^{23} \cdot 2^{23} \equiv 33 \cdot 18 \equiv 594 \equiv 34 \equiv 34^{23}\ \pmod{35}...


5

FFX is not malleable. It's a strong tweakable pseudo-random permutation, where the "strong" here indicates that both encryption and decryption look like random permutations from the attacker's perspective. In particular, there's no relationship between the plaintexts of closely related ciphertexts (aside from the trivial observation that different ...


5

Yes. Assume that the attacker knows the ciphertext $c = c_1 \mathbin\| c_2$, the initialization vector $v$ and the plaintext $m = m_1 \mathbin\| m_2$. This tells them that $D_k(c_1) = m_1 \oplus v$ and $D_k(c_2) = m_2 \oplus c_1$, where $D_k(\cdot)$ denotes block cipher decryption under the (unknown) key $k$. In particular, this implies that, if the ...


5

The Encrypt then MAC is done in general in order to be sure to decrypt into the correct plaintext, without risking of parsing a non-authentic plaintext message. If you don't MAC the IV, then Mallory (attacker that can tamper with messages as a man-in-the-middle) can modify the IV and your MAC will be still validated as good. So you will decrypt into an ...


5

The answer may depend on your exact definitions of "homomorphic" and "malleable", but I'll give it a shot. Basically, homomorphic encryption denotes that, given encryptions $E_k(x)$ and $E_k(y)$ of some values $x$ and $y$, it is possible to obtain an encryption of $x\ast y$ under $k$ from $E_k(x)$ and $E_k(y)$, where $\ast$ is some binary operation, without ...


5

The point (( also see this answer)) is that the hash calculation is free for everybody and we assume that your methodology is known by Kerckhoffs's principles. Anybody can calculate the hash of any information and this may leak the encrypted message. In Cryptography, we consider the attackers computationally bounded, but not restricted to adapt any method on ...


4

Vigenere Cryptosystem is as follow: You chose a key $(K_0,...,K_{m-1})$ consisting of elements in $Z_{26}$. Then a ciphertext for the message $(M_0,...,M_{n-1})$ is $$(M_i+K_{i\mod m}\mod 26)_{i \in [0..n-1]}$$ It is easy to see that you can generate a ciphertext for the message $(M_0+1,...,M_{n-1}+1)$ by adding 1 to each letter. It is therefore by ...


4

I believe it would match the relaxed RCCA security, but it looks like it wouldn't be of much use because reencryption would not be secure. You could generate reencryptions of any ciphertext, but they would not be indistinguishable from each other, i.e. given $c_1$ and $c_2$ you can determine easily whether $c_2$ is a reencryption of $c_1$.


4

Several cryptosystems possess this partially homomorphic property. Notable examples include Benaloh, and Naccache-Stern which generalizes it, as well as Damgård–Jurik which generalizes the Paillier cryptosystem. A worked example of the latter scheme: The encryption primitive is defined as $E(m)=g^m\cdot r^n \mod n^2$ for a random element $r \in \mathbb{Z}$...


4

There's a classic paper by Bellare, Desai, Pointcheval and Rogaway about the standard security notions: "Relations Among Notions of Security for Public Key Encryption Schemes" (PDF). This paper relates all the standard security notions you've heard of and gives definitions for all of them. I'll use it as the reference for this answer. So first we need to ...


4

The answer given by @kelalaka is 100% correct; this breaks the security of encryption and so shouldn't be used. However, I want to add that this doesn't even guarantee integrity. In particular, integrity should hold even if the attacker knows the message. Assume that the attacker knows $m$ and wishes to change the first bit. This change can be easily made (...


3

The one-time pad has the property that (as long as one key is only used for one encryption) the ciphertext contains (information theoretically) no information about the plaintext. However, this is something which does not exclude any form of malleability. Non-malleability is a property which is often required in protocol design, because ciphertext ...


3

NAND is not the appropriate combiner for RSA malleability , and can causes the issue observed by making what's produced larger than the public modulus $N$. RSA malleability applies to textbook RSA, where encryption goes $$x\to \text{Enc}_{(N,e)}(x)=x^e\bmod N$$ and malleability is the property $$\text{Enc}_{(N,e)}(x_1\cdot x_2\bmod N)=\text{Enc}_{(N,e)}(x_1)...


3

I just want to add some additional information to the answer of Ilmari. As Ilmari has already described in his answer, when using RSA you work in the ring of integers ${\mathbb Z}/{\mathbb Z}_n$, which is also called a residue class ring. This means that it consists of the set of residue classes $[i]$, where the $i$'th class is defined as the set $\{a \...


3

Depending on how malleability is defined, the question actually has some merit. Given to the Wikipedia definition of malleability, a cipher is malleable if there exists at least one function $g$ over the set of possible cipher texts, and one function $f$ over the set of possible plain texts, such that given any cipher text $c_0$, the cipher text $c_1 = g(...


2

Ed25519 in the default implementation is malleable. It includes the public key $A$ in the hashed message, so it cannot be modified It includes $R$ in the hashed message, so it cannot be modified $S$ is encoded as a 256 bit. But since it's a scalar, $S^\prime = S + k \cdot l$ is equivalent to $S$ for any integral $k$ (where $l$ is the order of the subgroup, ...


2

The answer to your question is contained in the Authenticity bound (Theorem 5.1). This is because Authenticity implies non-malleability (see e.g. http://eprint.iacr.org/2011/092.pdf). Note that only one term in the bound refers to the length of the tag (referred to by the variable $\tau$): $$\mathbf{Adv}_{OCB}^{auth}[\mathrm{Perm}(n), \tau] (A) \leq \...


2

To understand how this works, let's first recap how ElGamal works: All parties agree on system parameters $(\mathbb G_q,q,g)$ first such that and the order of $g$ in $\mathbb G_q$ is $q$. All the formulaes to follow need to be read as being done in $\mathbb G_q$ written multiplicatively, except if specified otherwise. Next the recipient picks a random $x\...


2

IMHO the best option to mitigate the maleability is using the authenticated encryption. So every scheme that includes the authentication tag should not be malleable (when done properly). Examples - the GCM mode, CCM, etc..


2

If the attacker has the ability of choosing the private key, then he can create a valid signature $(r,s)$ with a target value for $s$ for any message $m$. The attack works in the following way: The attacker choose its target $s$, generates a random ephemeral key $k$ and computes the hash of the message $e = H(m)$. Then the attacker computes the scalar ...


2

Yes, you got it right. You XOR'ed the correct bits, copied the IV and then shortened the message. Nothing wrong with that approach. The only thing that I'm a bit critical about is the one based indexing instead of the zero based indexing. Most mathematicians use zero based indexing (because it is compatible with modular calculations, for instance) and ...


2

CBC-R To better understand the attack on the paper, It is better to look at the original CBC-R attack to understand the above attack. Practical Padding Oracle Attacks, Juliano Rizzo and Thai Duong. USENIX 2010 This work shows how to turn the padding oracle into an encryption oracle. With padding oracle, we can get decryption of any ciphertext. Choose a ...


1

I believe that, if you make a plausible-sounding assumption on the SHA256 hash compression operation, you can show that the only malleability SHA256 has are length extension attacks. This plausible assumption is that, for a fixed input state, then the mapping between message block and output state acts like a random oracle [1] With this assumption, suppose ...


1

This paper, AFAICT: https://www.cs.ucdavis.edu/~rogaway/papers/relations.pdf It is about the security of public-key encryption, but the proofs about the relations between security definitions are applicable to symmetric encryption.


Only top voted, non community-wiki answers of a minimum length are eligible