# Tag Info

39

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

17

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

15

In a chosen-ciphertext attack, the attacker is assumed to have a way to trick someone who knows the secret key into decrypting arbitrary message blocks and tell him the result. The attacker can choose some arbitrary nonsense as an "encrypted message" and ask to see the (usually) different nonsense it decrypts to, and he can do this a number of times. Having ...

14

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

12

After reading the paper How to Break XML Encryption (thanks to Krzysztof for the link), here are my two cents. This attack relies on the fact that a CBC-ciphertext C = (IV, C1, ... Cd) can be decomposed into pairs of (IV, C1), (C1, C2), (C2, C3), ... (C(d-1), Cd), each of which is also a valid CBC ciphertext for the same key, relating to the corresponding ...

10

Neither. It means that an attacker can decrypt all messages that have been encrypted using this standard. The attack is a padding oracle attack. That means that, if the attacker has a ciphertext they want to decrypt, they can send several variations of the ciphertext to the server. By analyzing the server's responses (e.g., error messages returned), it ...

10

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

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 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 $IND-$ notation ...

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

8

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

8

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

8

Another variant (besides the ones explained by Henning) which I also would call chosen-ciphertext attack, is one where the attacker doesn't get the whole plaintext corresponding to its chosen ciphertext, but only a result like "valid" or "not valid", i.e. he has a validation oracle, with some useful definition of "valid". The goal is to decrypt some message ...

7

In step 2, the adversary outputs two messages. One of these will be selected at random for encryption. You can think of the adversary sending these messages to a "challenger" that also has oracle access (or is the oracle itself). It doesn't really matter who is running the challenge since the challenger doesn't have any "intelligence." All the challenger ...

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

The idea of IND-CCA2 (indistinguishable under an adaptive chosen-ciphertext attack) is that the attacker has no chance to distinguish the ciphertexts of two given plaintext messages, even if it can feed the decryption machine other ciphertexts for decryption. In the second part of the experiment, the adversary has to chose two messages for the challenge (of ...

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

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

5

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

5

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

5

Informally, CCA2 does not permit any kind of modification of ciphertexts, while RCCA permits some alteration as long as it does not alter the original message. For example, think of a publicly randomizable encryption scheme, that is, a scheme that permits to alter the original randomness used during encryption. CCA2 would consider these ciphertexts as ...

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

4

No, there are also CCA games for private key encryption schemes. There you have additional encryption oracles that you can use, to obtain encryptions for messages of your choice (in a private key encryption scheme you can not encrypt yourself, because this requires the secret key). See here for a concise explanation and comparison: http://crypto.cs.uiuc.edu/...

4

I believe it would match the relaxed RCCA security, but it looks like it wouldn't be of much use because reencryption would not be secure. You could generate reencryptions of any ciphertext, but they would not be indistinguishable from each other, i.e. given $c_1$ and $c_2$ you can determine easily whether $c_2$ is a reencryption of $c_1$.

4

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

4

After some thought, I think the answer is in fact NO, even for CCA1 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 into ...

3

The initial notion of semantic security from Goldwasser and Micali has been shown to be euqivalent to what we call today indistinguishability under chosen plaintext attacks (IND-CPA). Yes that's only security against a passive adversary and actually the weakest reasonable security notion that we use today. The authors of the second paper you link seem to ...

3

Your third question asked how this attack relates to pre-existing applications of CBC. Before being used to break XML encryption, it was used on certain protocols run over TLS/SSL. See my answer here. For other protocols like IPSEC, WTLS, and SSH, the original paper proposing the attack has a good discussion of its applicability (in Section 5).

3

[EDIT: I am assuming a public key system here] IND-CCA2 summary: get encryption key. make decryption queries on chosen ciphertexts. obtain challenge ciphertext on $m_L$, $m_R$, two equal-length messages chosen by you, the attacker. The challenger is suppsed to randomply pick one, encrypt it and return the ciphertext. make decryption queries as in 2. ...

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