Skip to main content
New
Stack Overflow Jobs powered by Indeed: A job site that puts thousands of tech jobs at your fingertips (U.S. only). Search jobs
24 votes
Accepted

What is complexity leveraging

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 ...
Yehuda Lindell's user avatar
12 votes

What do NM-CPA and NM-CCA mean?

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 ...
Squeamish Ossifrage's user avatar
12 votes
Accepted

Is there a way of maintaining malleability in a homomorphic encryption system while making it infeasible to perform chosen ciphertext attacks?

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 ...
Mikero's user avatar
  • 13.4k
8 votes
Accepted

Non-malleability of One Time Pad Encryption

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 ...
Ella Rose's user avatar
  • 19.6k
6 votes
Accepted

What do NM-CPA and NM-CCA mean?

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 ...
SEJPM's user avatar
  • 46.1k
6 votes
Accepted

How can one turn a malleable encryption to not malleable

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 ...
Mikero's user avatar
  • 13.4k
5 votes
Accepted

Is E_k(M)||H(m) form of MAC secure?

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 ...
kelalaka's user avatar
  • 48.7k
4 votes

Is E_k(M)||H(m) form of MAC secure?

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, ...
Yehuda Lindell's user avatar
4 votes

Malleable encryption

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 ...
MickLH's user avatar
  • 181
3 votes

Proof of concept for RSA malleability

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, ...
fgrieu's user avatar
  • 142k
3 votes

Non-malleability of One Time Pad Encryption

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 ...
dade's user avatar
  • 1,323
2 votes

ElGamal malleability for a given function f(m)

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 ...
SEJPM's user avatar
  • 46.1k
2 votes
Accepted

Non malleable Encryption scheme

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 - ...
gusto2's user avatar
  • 1,192
2 votes
Accepted

Malleability for varying length message

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 ...
Maarten Bodewes's user avatar
  • 92.9k
2 votes
Accepted

ECDSA: with knowledge of private key, can we make signatures with partially chosen content?

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 ...
Ruggero's user avatar
  • 7,104
2 votes
Accepted

"Fixing" PCBC mode?

It seems while this scheme fixes the "ciphertext-swapping" problem, it permits modifying the first block of ciphertext $C_1$ and the $IV$ together without affecting the decryption of the ...
ManRow's user avatar
  • 343
2 votes
Accepted

How to create the ciphertext that generates a desired plaintext in CBC (previous cipher- and plaintext are known)

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. ...
kelalaka's user avatar
  • 48.7k
1 vote
Accepted

Cryptography particular block length valid message

The trick with PKCS#5 padding (or the nearly equivalent PKCS#7 padding) is that it ends with a byte that indicates the number of padding bytes that was added to the message. You'd add $1$ to $n$ bytes ...
1 vote

Is there a name for an encryption scheme that do not return $\bot$ when a different key is used during decryption?

If as you write "we want" this property, then I think the property is called key equivocation, which is supposed to make it harder for an attacker to distinguish the correct key from wrong ...
Amit's user avatar
  • 432
1 vote

malleability of the Elgamal cryptosystem

Sounds a bit like coursework. (: Some ideas to get you started: Are you aware of how a ciphertext $C = (c_1, c_2)$ is constructed? That is, can you state $c_1$ and $c_2$ in terms of the message $m$, ...
Morrolan's user avatar
  • 1,157
1 vote

Making a cipher non-malleable using a plaintext transform?

Is there any existing approach that does anything similar to this? Basically some sort of modern version of Russian copulation? There is one existing idea which is currently used in some RSA ...
Modal Nest's user avatar
  • 1,443
1 vote
Accepted

SHA256 hash malleability

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 ...
poncho's user avatar
  • 148k
1 vote

Proofs that NM-CPA implies IND-Cpa and $\text{IND-CCA} \leftrightarrow \text{NM-CCA}$

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 ...
Frédéric Dumont's user avatar
1 vote

Non-malleability of One Time Pad Encryption

The examples given of the 'Heil Hitler' -ending messages and the simplistic 'yes/no' messages have no real world applications, as you might have guessed, and are given as scholarly examples to ...
francogrex's user avatar
1 vote

Non-malleability of One Time Pad Encryption

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 ...
Rob's user avatar
  • 349
1 vote
Accepted

The differences between the attackers in the definitions of IND-ATK and NM-ATK

You say: Actually, $A_2$ and $B_2$ are both used to decide which one of two messages are encrypted for the challenge. However, this is not true. The definition of the IND and NM games are ...
cygnusv's user avatar
  • 4,992
1 vote

Malleable encryption

Could you describe the key distribution scheme? If you want symmetric encryption, then your requirement that the intermediaries cannot decrypt anything precludes them all from having the same key, so ...
Dan_JH_YK_CC's user avatar

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