# Tag Info

14

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

13

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

13

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

12

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

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

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

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

7

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

6

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

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

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

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

3

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

3

The important thing to note here is that $\mathsf{D}(k,0)=0$ does not necessarily imply that $\mathsf{E}(k,0)=0$. That is the reason why your attack does not work in general. To illustrate, let $(\mathsf{E},\mathsf{D})$ be a CCA secure encryption scheme. We then construct a new encryption scheme $(\mathsf{E'},\mathsf{D'})$ as follows: $$\mathsf{E'}(k,m) = ... 3 Chosen Ciphertext Attacks against RSA (such as Bleichenbacher's Attack on PKCS #1 encryption) do not actually reveal the private key. If they don't, they why do we say that they are a threat? Well, it's because that the keys are generally not of interest to the attacker. Instead, given an encrypted message, the attacker actually wants to know what that ... 2 All the details have been published in the paper titled "IEEE Symposium on Security and Privacy - Cryptography in the Web: The Case of Cryptographic Design Flaws in ASP.NET" http://netifera.com/research/poet/ieee-aspnetcrypto.pdf 2 You are correct; whoever put together the above proof typo'ed that point; we have c \times d \equiv 1 \pmod {\phi(n)}, or more accurately, c \times d \equiv 1 \pmod {lcm(p-1, q-1)}. On the other hand, the attacker isn't expected to be able to compute step 2 (he can't, he doesn't know the value of lcm(p-1,q-1), and hence cannot compute d). Instead, ... 2 The standard approach is to break this problem into two pieces: What information is unavoidably leaked, merely by computing the desired function? In your case, the goal is to compute \sum_i x_i. This sum unavoidably leaks a little bit of information about the x_i's. For instance, as you correctly state, if we somehow know that all x_i's are ... 2 This is tricky and I don't know that there is a generic way to take care of all domain/auxiliary information. The way we typically do proofs in multi-party computations is by defining an ideal world and show that the information generated in the ideal world (usually the encrypted inputs and the outputs) could be used to simulate the real world protocol ... 2 I am assuming that n is small enough that the counter never rolls over and repeats, and that the IV is chosen randomly from the space of all possible IVs. The length of the plaintext is leaked, but that is leaked by the ciphertext anyways. The plaintext for a given ciphertext is leaked as the attacker can feed that in to the oracle. AFAIK, however, ... 2 There are two possible ways (I can think of) an attacker could mess you up here, but they both stem from very poor design. So I don't know how realistic they are. Note: the following figure assumes a 64-bit blocksize CFB is only self synchronizing against insertions/deletions of a specific length. The length is determined by the shift register. If the ... 2 The answer to your question is contained in the Authenticity bound (Theorem 5.1). This is because Authenticity implies non-malleability (see e.g. http://eprint.iacr.org/2011/092.pdf). Note that only one term in the bound refers to the length of the tag (referred to by the variable \tau):$$\mathbf{Adv}_{OCB}^{auth}[\mathrm{Perm}(n), \tau] (A) \leq ...

2

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

2

No, CCA does not imply authenticated encryption. CCA tries to recover the secret using chosen ciphertexts. A well designed block cipher should in itself already process the property that the key cannot be retrieved. If used with a properly implemented block mode of operation, this property should hold. Using authenticated encryption a CCA attack should not ...

2

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

2

No. RSA-OAEP is indistinguishable under adaptive chosen cipher text attacks (and even non malleable under adaptive chosen cipher text attacks), but it is not an instance of authenticated encryption. - The sender who encrypts the message might even be anonymous to the recipient who decrypts the message. More generally, in a successful Chosen Cipher text ...

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