I am looking at the different attacks on RSA. I came across known-plaintext attack where the public key can be used to encrypt all possible messages until it finds a match on the sent encrypted message. However, on the book I found in the library it seems this form of attack is also called "Forward search attack".

If the message space is small or predictable, an adversary can decrypt a ciphertext c by simply encrypting all possible plaintext messages until c is obtained. Salting the message as described above is one simple method of preventing such an attack. -Handbook of Applied Cryptography

So are these attacks the same with different names or have I misunderstood it?


In context of public key encryption it is not really meaningful to consider known-plaintext attacks in the way this is done in context of symmetric encryption schemes (where an adversary gets hold of ciphertexts and knows the corresponding plaintexts and wants to recover the secret key). In public key encryption, everyone (as the public key is public) can produce ciphertexts for arbitrary messages of his choice. Consequently, an adversary can produce such pairs for any ciphertext of its choice and has not to wait to eavesdrop such pairs.

However, what is interesting in public key encryption is that an adversary who intercepts ciphertexts can not figure out which message is hidden in this ciphertext even if the adversary knows that the respective plaintext comes from a known set (in formal models this is reduced to a set of two elements, as discussed below).

The "forward search attack" in the HAC is a strategy the adversary can choose, i.e., to simply "trial encrypt" every element from the set and check if the ciphertext matches the intercepted. This attack strategy is feasible for every deterministic public key encryption scheme (such as textbook RSA), where multiple encryptions of the same message with respect to the same public key always yield the same ciphertext.

To formally treat security of public key encryption, we do not consider single attack strategies but a goal an adversary has to achieve within a concrete security model (attack class) and is typically modeled as a game between the adversary and a challenger. In indistinguishability games, the adversary can choose two messages and then gets back the ciphetext for one of these two and has to determine which message is hidden inside the ciphertext (where the adversary is given different "power", depending on the class of attack).

In the formal treatment of public key encryption, there is a model called indistinguishability under an eavesdropping attack, which essentially says that an adversary is allowed to choose two messages, then gets the ciphertext for one of these messages and has to determine which one has been encrypted significantly better than guessing. As, however, in public key encryption, the adversary can built its own encryption oracle by means of knowledge of the public key, this aforementioned notion is equivalent to the well known notion of indistinguishability under chosen plaintext attacks (IND-CPA). This attack game is essentially identical to the aforementioned, but the adversary additionally has access to an encryption oracle throughout the security game.

In the case of textbook RSA, an adversary can use this "forward search attack" as strategy to win the IND-CPA game. More precisely, when receiving the challenge ciphertext (one of the two submitted messages), then the adversary simply calls the encryption oracle for one of the two candidate messages. If the response ciphertext of the oracle is identical to the challenge ciphertext, the adversary knows that the message submitted to the oracle is in the challenge ciphertext, and the other one otherwise. By turning textbook RSA in a probabilistic scheme, e.g., by using OAEP, RSA can be made IND-CPA secure and this attack is no longer possible. It satisifies even the strongest notion of security, i.e., IND-CCA2 (see below).

In context of public key encryption schemes, the weakest notion of security considered today is IND-CPA (which is equivalent to the above mentioned eavesdropping) and the common stronger notions are indistinguishability under chosen ciphertext attacks (IND-CCA1) and a indistinguishability under adaptively chosen ciphertext attacks (IND-CCA2). In the latter two security games the adversary has additionally access to a decryption oracle during the security game (only before seeing the challenge in IND-CCA1 and also after seeing the challenge in IND-CCA2).

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.