105

When encrypting something with RSA, using PKCS#1 v1.5, the data that is to be encrypted is first padded, then the padded value is converted into an integer, and the RSA modular exponentiation (with the public exponent) is applied. Upon decryption, the modular exponentiation (with the private exponent) is applied, and then the padding is removed. The core of ...


56

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


14

There is an article* that answers the question in the negative for GCM and CCM. The article introduces the first formalization of the Releasing Unverified Plaintext (RUP) setting. The related security notion is the Ind-RUP. The security question is can an adversary forge messages with unverified messages? In this game, confidentiality is not relevant, since ...


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


11

In general, CTR mode is not secure against chosen-ciphertext attacks. (The same goes for the other classic block cipher modes of operation too; to get security against chosen-ciphertext attacks, you need authenticated encryption.) In your stated attack scenario, the attacker can obviously use the decryption oracle to decrypt any ciphertexts they intercept, ...


11

As already mentioned in a previous answer and the comments, you are right regarding that ElGamal is not secure against chosen-ciphertext attacks. An immediate reason is that the scheme is multiplicatively homomorphic, and that is not compatible with CCA: the attacker could query the decryption oracle with the ciphertext that results of multiplying the ...


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


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

For stream ciphers, IND-CCA1 and IND-CPA security differ precisely in that an attacker can choose the IV in the CCA1 game (because that's part of the ciphertext that can be submitted to the decryption oracle); but in the CPA game is constrained to whatever choice of IV the cryptosystem makes. We can artificially construct a stream cipher vulnerable under ...


10

how can we prevent the cipher from being returned in case the tag is wrong ? As far as I understand, to compute the tag the decryption process must be done entirely. Actually, GCM decryption can be done in a two-step procedure: Step 1: compute the expected GCM tag (which is a function of the ciphertext, AAD, teh secret H value, combined with the nonce and ...


9

The best you can get for homomorphic encryption schemes is non-adaptive chosen ciphertext security (IND-CCA1 security), see e.g. here for a quite up to date characterization. As you rightly observe homomorphic encryption schemes are malleable by definition and cannot provide adaptive security against chosen ciphertext attacks (be IND-CCA2 secure). Since ...


9

The CCA1 security of ElGamal is a big open question. There are no attacks known, but standard reductions don't seem to work. In 1991, Damgard proposed an ElGamal variant and proved it to be CCA1-secure (albeit under a very problematic non-falsifiable assumption, called the "knowledge of exponent assumption"); see the paper here http://link.springer.com/...


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

Let's consider CTR mode encryption with a random IV for a block cipher (essentially the same as stream cipher, but simpler to analyze since the formalization of stream cipher security is not fully standardized). On the one hand, it seems like it should be CCA1-secure since there is nothing that an attacker can do in the CCA1 queries that can help later. ...


8

You seem to have some misconception here. Obviously, you are investigating chosen ciphertext attacks (CCAs) on textbook RSA instead of chosen plaintext attacks (CPAs). To help you with your understanding I am discussing CPA on textbook RSA first. To analyse all these kinds of attacks we formally model the attack as a game between an adversary (trying to ...


7

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 ciphertext. In other words, the attacker may encrypt arbitrary messages. In a chosen ciphertext attack, the attacker can additionally (a chosen ciphertext attack ...


7

Bouncy Castle Java releases 1.60 and FIPS 1.0.1 (and former) have precisely the issue exploited in Manger's attack: an exception occurs when a ciphertext $c$ is submitted such that $c^d\bmod N$, expressed as a bytetring as wide as $N$, does not start with a 0x00 byte; and then the rest of the decryption process does not occur, leading to markedly faster ...


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

Essentially any IND-CPA-secure lattice-based cryptosystem offers additive homomorphism, up to a predetermined number of operations. I don't know of any IND-CCA1-secure post-quantum candidate that offers any homomorphic property, except Loftus-May-Smart-Vercauteren SAC'11, which is based on a nonstandard "knowledge of error" lattice assumption.


6

I'll answer your questions in order: 1. If any paper mentions attack as $2^{140}$, how the researchers determine this number of operations? By examining the mathematical properties of the algorithm and their attack. 2. Are these attacks only on paper or practically proven? There is no practical way to perform any operation $2^{140}$ times, so they are ...


6

Okay, I examined this for a while, and I'm pretty sure this is more of an oversight. They probably wanted to take $r\ge2bs_{i-1}-2B=2(bs_{i-1}-B)$. The same correction should go into the code. (Taking $r=2bs_{i-1}-2B$ is indeed too low a value and does not ensure the doubling of $s_i$ at every successive step, so your observation is correct.)


6

Well, it turns out that a straight-forward implementation of LWE key exchanges is vulnerable to chosen ciphertext attacks, in the case that one side reuses the same private value $a$ multiple times. In this straight-forward implementation, Alice generates a private vector $a$, and sends his key share $a M + \epsilon$. Then, when Bob receives this key share,...


6

Firstly, is this a correct threshold for considering a cipher secure? Not exactly. Security is a spectrum, so what is secure for some applications may not be secure for others. Is a $2^{-64}$ probability of attack success too much? For some it is far too high. For others, even $2^{-32}$ is fine. In the case of known plaintext attacks, an attacker is usually ...


5

Intuition The intuition behind the proof is that a valid ciphertext is correctly generated and, thus, an adversary should query to the random oracles to generate random strings in the ciphertext. In addition, notice that the hash value on an unqueried string is undetermined (to the adversary) in the random oracle model. Therefore, the chance to construct a ...


5

RFC 4880, OpenPGP (superseded RFC 2440 which was up to date in 2002) contains a chapter on security considerations, which also discusses the decryption oracle attack Jallad et al described: In late summer 2002, Jallad, Katz, and Schneier published an interesting attack on the OpenPGP protocol and some of its implementations [JKS02]. In this ...


5

CCA security assumes CPA security, and $m || H(m)$ is not CPA secure. This is simple to show: say that $C = E(m || H(m))$ is known, then an adversary can simply guess $m'$ and encrypt that. Then $C' = C$ will show the adversary that $m'=m$. To show a CCA attack you can use this attack. You can of course replace the value $2$ in that question with $y$ where $...


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