22

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


20

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


11

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

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


7

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


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

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

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

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

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

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

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

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


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

Non-malleability of Scrypt w.r.t. to salt (as well as passphrase) follows from the definition of Scrypt (which simply pass that salt to that input of PBKDF2); the definition of PBKDF2 (which uses the salt followed by a non-malleable encoding of an integer as a massage passed to HMAC_SHA256); the non-malleability of HMAC_SHA256 w.r.t. the message; and perhaps ...


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

The randomness is not enough for IND-CCA-2. If we get a message (so $L$ bits of data plus the $y$ to reconstruct the random seed), we can modify it, say flip the first bit, and ask the decryption oracle for a decryption of the modified message (which will have the same $y$!), which we will get. Then the original message can easily be obtained: we get the ...


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

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

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

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

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


1

A quite realistic example: Presume that you are listening to German messages during WWII, and intercept messages that you think are for a one-time-pad. You know that every message ends in "Heil Hitler". So, the last 11 characters can be simply presumed. So, you badMsg=xor("Heil Hitler", "Retreat now"). Then when a message comes by, xor the last 11 ...


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