67 votes
Accepted

Easy explanation of "IND-" security notions?

The ideal encryption scheme $E$ would be one that, for every ciphertext $C=E(K, M)$, if the key remains secret for the adversary, the probability of identifying $M$ is negligible. Since that is not ...
user avatar
29 votes
Accepted

What do the signature security abbreviations like EUF-CMA mean?

Notation. Sets are represented using the calligraphic font and algorithms using the straight font. Throughout, $\Sigma:=(\mathsf{K},\mathsf{S},\mathsf{V})$ denotes a signature scheme on a key-space $\...
user avatar
  • 4,503
22 votes

Possibility of Chosen Plaintext Attack (CPA) in real-world scenario?

Bruce Schneier foresaw your skepticism and directly answered this question in "Applied Cryptography": Known-plaintext attacks and chosen-plaintext attacks are more common than you might think. It ...
user avatar
  • 321
21 votes
Accepted

If RSA is only used to encrypt symmetric keys which are random, what's wrong with textbook RSA?

This is a common mistake, so I'd like to give an in-depth answer. Basically, what you are proposing is to rely on the ONE-WAYNESS of RSA as a ONE-WAY FUNCTION, rather than relying on its CPA or CCA ...
user avatar
20 votes

Why is CBC with predictable IV considered insecure against chosen-plaintext attack?

If your IV is predictable this is as (in)secure as assuming that you have a zero vector IV. And a zero vector IV allows you to perform a so-called Adaptive Chosen Plaintext Attack (ACPA). Why? ...
user avatar
  • 345
17 votes

Possibility of Chosen Plaintext Attack (CPA) in real-world scenario?

It's not necessary that you encounter a situation like this in the real world to motivate the definition. There are some weaker adversaries that you would like to rule out in your security model, and ...
user avatar
  • 3,802
17 votes

Possibility of Chosen Plaintext Attack (CPA) in real-world scenario?

Practical chosen-plaintext attacks have been discovered against modern cryptosystems like TLS/SSL. One noteworthy type of vulnerability can occur when a cryptosystem includes a compression step before ...
user avatar
14 votes
Accepted

Does IND-CPA imply PRF?

If there exists an IND-CPA symmetric encryption scheme (where the key is shorter than the total length of the messages, i.e., the scheme is not the OTP), then there are one-way functions. A sequence ...
user avatar
12 votes
Accepted

What are the practical implications of ciphertext distinguishability?

This isn't really a "hard" answer, but an attempt to give some intuition or motivation. One can interpret indistinguishability as an overapproximation of the most common notions of security: Any ...
user avatar
  • 11.2k
12 votes
Accepted

Chosen Plaintext attack on AES in ECB mode

Suppose we have a block cipher that takes a 16 byte plaintext and produces a 16 byte ciphertext (that is to say $\mathcal{Enc}: \{0,1\}^{128} \rightarrow \{0, 1\}^{128}$). We use this block cipher to ...
user avatar
  • 3,952
11 votes

Why is CBC with predictable IV considered insecure against chosen-plaintext attack?

The answer by mwhs is very wrong about CBC-MAC and its use of IV!! It is perfectly fine and secure to use the same IV for CBC-MAC! In fact, Jonathan Katz and Yehuda Lindell recommend using zero vector ...
user avatar
  • 219
11 votes

Possibility of Chosen Plaintext Attack (CPA) in real-world scenario?

There are some interesting examples in section 3.4.2 of Katz-Lindell book. Here is just one of them: During World War II, the British placed mines at certain locations and (intentionally) managed to ...
user avatar
  • 990
10 votes

What is the difference between chosen-plaintext attack and adaptive-chosen-plaintext attack?

With chosen-plaintext attack, the attacker is allowed to choose an arbitary amount of plaintext to encrypt. After that he/she can't do that again, he/she has to work with the current data. With the ...
user avatar
  • 3,820
10 votes

Is One Time Pad considered Chosen-Plaintext Attack Secure?

Note: In this answer, I stick to a definition of the One Time Pad where the random pad is used only One Time; at least, I've the name of it as support! Otherwise, it is well known that the OTP ...
user avatar
  • 125k
10 votes
Accepted

Building a combined encryption scheme from two encryption schemes that's secure if at least on of them is secure

You can generate a random string $s_1$ as long as the plaintext. Then XOR this value with the plaintext generating $s_2$. Now encrypt both parts using $\mathrm{Enc}_1$ and $\mathrm{Enc}_2$. You need ...
user avatar
  • 85.9k
10 votes

What are the practical implications of ciphertext distinguishability?

Katz & Lindell mention in their book "Introduction to Modern Cryptography: Principles and Protocols" an example of an IND-CPA attack from World War II. Navy cryptanalysts suspected that Japanese ...
user avatar
  • 4,832
9 votes

how to prove our algorithm is secure against chosen plaintext attack?

The usual approach to prove IND-CPA security is to construct a logical argumentation called "reduction". In this argumentation you first start with the assumption that certain computational problem is ...
user avatar
  • 4,832
9 votes
Accepted

Are there deterministic private-key encryption schemes that are CPA-secure?

Summarizing fkraiem's comment, a CPA-secure encryption scheme can not be deterministic. The reason is simple: the attacker is challenged to distinguish between the encryption of $m_0$ and $m_1$, but ...
user avatar
  • 3,802
9 votes

Is it possible to build a CPA-secure encryption scheme which remains secure even when the encryption of secret key is given?

You're in luck! Essentially every secure public-key encryption scheme on bit strings that is actually in use already has this property—and, even better, not just IND-CPA but often IND-CCA2/NM-CCA2*—...
user avatar
8 votes

Possibility of Chosen Plaintext Attack (CPA) in real-world scenario?

The lead up to the Battle of Midway also involved a chosen plaintext attack. The Americans had mostly broken the Japanese code JN-25b, and knew the Japanese were attacking "AF". They guessed that "...
user avatar
  • 1,480
8 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 ...
user avatar
8 votes
Accepted

Does AES-ECB with random padding added to each block satisfy IND-CPA?

First, I would not call this AES-ECB, since adding randomness means that it is not ECB. Second, when limiting the message space to what fits into one block, asymptotically -- meaning for a ...
user avatar
7 votes

Is One Time Pad considered Chosen-Plaintext Attack Secure?

Yes, the one-time pad model provides the technical notion of IND-CPA security. An adversary's advantage at the IND-CPA game is zero if the pad is uniform random. This is a standard—and, once you get ...
user avatar
7 votes

Chosen plaintext vs Chosen ciphertext

The difference is how the plaintext-ciphertext pairs that the attacker has access to are generated. In a chosen plaintext attack, the attacker chooses some plaintext and is handed the corresponding ...
user avatar
  • 11.2k
7 votes

How does chosen ciphertext attack on Elgamal work?

Assuming you don't use counter-measures against this kind of an attack, a chosen-ciphertext attack works as follows: Variables: $p$ is field prime, $\alpha$ is the chosen generator, $a$ is the ...
user avatar
  • 44.7k
7 votes
Accepted

Are all stream-ciphers IND-CPA?

No. There is a difference between the type of a cipher and the construction of a cipher. If a cipher is of a specific type for which there are known IND-CPA secure constructions then that doesn't ...
user avatar
  • 85.9k
7 votes
Accepted

Construct IND-CPA secure encryption scheme by combining two given schemes

The first remark is that the cryptosystems are used with independent keys. This is important, otherwise it is usually very hard to prove anything. The simple solution Now, the simple solution is, as ...
user avatar
  • 4,412
7 votes
Accepted

ElGamal CPA secure

So let's go through the IND-CPA game, shall we? Pick two messages $m_0$ and $m_1$ arbitrarily. Send them to the challenger who chooses $b\in\{0,1\}$ uniformly at random and returns you $c=E(m_b)$. ...
user avatar
  • 44.7k
7 votes
Accepted

CPA-security of CTR mode

One gap in your proposed argument is that $ctr$ is known to the adversary (it is included in the ciphertext), whereas saying "$G_k(ctr)$ is pseudorandom" implicitly assumes that both $k$ and $ctr$ are ...
user avatar

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