# Tag Info

100

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

51

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

27

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

26

Definitions / Introduction We define (this is solely for our example): $enc()$ and $dec()$ as the encryption and decryption function using CBC mode, with a constant key. any block cipher will do $\oplus$ is the XOR operation. $n$ the amount of plain text blocks. the length of a block in bytes is $16$ (i.e. 128 bit). $m_1$ through $m_n$ the plain text ...

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

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

9

Proving $\gcd(e, e_2) = 1$ is easy; all you need to do is rely on the property $\gcd(e, e_2) = \gcd(e, e-e_2)$ Now $e$ and $e_2$ differs in a single bit (because Peter flipped one bit in $e$ to form $e_2$), and hence $|e - e_2|$ is a power of two (the sign of which depends if Peter flipped a zero bit or a one bit), and hence has $2$ as its only prime ...

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

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

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

9

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

9

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

7

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

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

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

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

INT-CTXT and INT-PTXT are usually on considered for private-key encryption. For public-key encryption, no correct encryption scheme can satisfy those requirements. (Proof: The adversary can run the encryption algorithm on an arbitrary message and submit it as its output. Since it made no queries to its encryption oracle, this ciphertext violates both INT-...

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

After some thought, I think the answer is in fact NO, even for IND-1-CCA* and even for Shoup's OAEP+. RSA-OAEP/OAEP+ work by taking a message $m$, producing a padding $p(m,r)$ and then encrypting this, so $c = f(p(m,r))$ where $f$ is RSA encryption, and $f(u) = u^e \pmod{N}$ is deterministic. In fact, the whole point of OAEP(+) is to inject some entropy ...

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 $... 5 The proof of (1) is not given in the chapter on symmetric encryption since it requires knowing the hybrid proof technique that is taught in Chapter 7. However, the argument is proven in Chapter 11 for the asymmetric case (see Theorem 11.6 and the proof on page 383). Essentially the same proof holds for the symmetric case as well (except that instead of the ... 5 What you describe is Chosen-Plaintext Attack (CPA) and AES and secure block ciphers are designed to be secure against this. Having$2^{16}\$ chosen-plaintext under one key doesn't help you to extract the AES key. You have to go to the full-brute force to find the key. Since you have one target, you cannot get help from attacking many keys simultaneously. ...

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