54

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 possible in practice, the second most reasonable approach is to define constraints strong enough to satisfy some definition of security. The $\operatorname{IND-}$ ...


29

These aren't "attacks" in and of themselves, they are simply a way to classify attacks depending on how many assumptions they make. For instance, if an attack requires plaintext-ciphertext pairs to recover the key, but they don't have to be any particular pairs, that attack is categorized as a known-plaintext attack. However if another attack required the ...


22

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 is not unheard-of for a cryptanalyst to get a plaintext message that has been encrypted or to bribe someone to encrypt a chosen message. You may not even have to ...


21

(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 $\mathcal{K}$, message-space $\mathcal{M}$ and signature-space $\mathcal{S}$. Since only a single key-pair is involved in the discussion, to avoid cluttering, ...


19

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 security as an encryption scheme. The advantage of using RSA as a one-way function is that no padding etc is needed. Now, the first important thing to note is ...


18

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? Assume that you have a encryption mechanism that works in CBC mode. This means, that on the first iteration the $IV$ is XORed with your input message (which is ...


17

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 CPA-security usually would encompass them all. Think for example of an encryption scheme which is intended to be used to encrypt one bit, like "yes" or "no". ...


17

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 encryption (which TLS used to do). This led to several well-known exploits such as CRIME and BREACH. In CRIME, the adversary attacks a visitor of a HTTPS-...


15

XXTEA (also known as Corrected Block TEA) is a block cipher with $128$-bit key and block width parameterizable to $n\cdot32$ bits for $n\ge2$. It is an Unbalanced Feistel Cipher making $q=6+\lfloor52/n\rfloor$ passes over the block, with $q\cdot n$ rounds each modifying $32$ bits of the block. The round function is a simple Add-Rotate-Xor function of two 32-...


14

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 of articles have shown how to construct pseudorandom generators out of OWFs (culminating with this paper). By the GGM construction, pseudorandom generators can ...


11

CBC mode encryption is defined as: $C_i = E_k(P_i\oplus C_{i-1})$ (with $P_i$ being the $i$th plaintext block, and $C_{i-1}, C_i$ being the ciphertext blocks. What might happen if we have a lot of ciphertext encrypted with the same key is if two ciphertexts happen to be the same, that is: $C_i = C_j$ If we see that, we can then immediately deduce that: ...


11

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 system that is broken in a more practical way will also fail to meet indistinguishability, that is, all practically important security requirements are in fact ...


11

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 let the Germans discover them. They knew that the Germans would encrypt the locations and send back to the headquarters. These encrypted messages were used by ...


10

I do not remember if we checked this explicitly, but my guess is that in the chosen-plaintext setting the biclique attack would still be faster than the exhaustive search, maybe by the factor of 2 compared with 4 in the chosen-ciphertext setting. However, both results are pretty far from declaring AES broken in any sense. Such small gain over exhaustive ...


10

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 adaptive-chosen-plaintext attack, he/she can do the same as with the chosen-plaintext attack, but is also allowed to encrypt new data after the attacker has ...


10

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 to decrypt both to XOR the two parts together again. This is similar to secret sharing where you need two parts of a key to decrypt. If $\mathrm{Gen}_1$ and $\...


10

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 encrypt two blocks worth of unknown data, call them $m1$ and $m2$. Additionally we are allowed to prepend some data to these two blocks, let's call it $m0$ (we ...


9

The XXTEA cipher is badly broken. Even though the paper is not published at a conference, the author verified it on reduced versions of XXTEA. You should never ever use a cipher or a hash function, that has been broken in academic terms, in particular if you are not a cryptographer. Attacks always get better, and a cipher does not attract much attention ...


9

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 IV when invoking CBC-MAC because it saves storage and bandwidth in practical settings! (souce: Introduction to Modern Cryptography, Second Edition) The ...


9

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 encryption scheme consisting of XOR with a repeated key is insecure by even the weakest standard (unknown plaintext with redundancy). Late addition: further, I stick ...


9

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 ciphertexts containing the fragment "AF" where referring to the Midway island. Then, they told officials at Midway to send unencrypted messages reporting they ...


9

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 hard (for example, the Decisional Diffie-Hellman assumption), and then you proceed to demonstrate that if your crypto scheme were insecure with respect to IND-...


9

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*—because they can all be factored into a KEM/DEM structure via a hash function $H$ like SHAKE128:† (KEM) Generate a uniform random $k$ and encapsulation $y$ ...


8

This isn't just limited to asymmetric schemes; in any chosen-plaintext attack, even for symmetric ciphers, the attacker can (by definition of the CPA game) compute as many encryptions as they like (limited to polynomial time, of course). Formally, we say the adversary is given access to an "encryption oracle." Anyway, you have stumbled across a necessary ...


8

That sounds like an overly succinct description of the 'Find then Guess' (FTG) notion of security, described in the paper "A Concrete Security Treatment of Symmetric Enryption". And you are correct, there is something the test is missing: the two 'challenge' plaintexts must be the same length ($|m_0| = |m_1|$). Also, the description is so succinct I can't ...


8

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 he also has access to an encryption oracle (and he can query the oracle at whatever input he wants!). If the encryption scheme yields the same ciphertexts each ...


8

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 "AF" was Midway, but to be sure they had Midway send a cleartext message that their fresh water system was broken, and soon picked up a Japanese message "AF was ...


8

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 pseudorandom permutation with block size $n$ -- this construction is actually even CCA-secure (and so non-malleable, since indistinguishability and non-malleability are ...


7

It seems to me that what you need is a public-key signature scheme like rsa signatures. The process would work something like this: A user license $L$ is created by your license generator Your system signs it to give $s(L)$ and the licence is $\{L,s(L)\}$. When program tries to open the user's license $\{t,v\}$: The system verifies that $v$ is indeed a ...


7

Encryption using a block cypher such as AES by passing plaintext blocks directly to the encryption function is known as Electronic Code Book mode (ECB) and is not CPA secure as (as you say in your question) it is entirely deterministic and two identical plaintext blocks will result in two identical ciphertext blocks. To prevent this an initialisation ...


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