Why is asymmetric encryption IND-CPA?

Question

According to Wikipedia, the IND-CPA game is:

The challenger generates a key pair PK, SK based on some security parameter k (e.g., a key size in bits), and publishes PK to the adversary. The challenger retains SK. The adversary may perform a polynomially bounded number of encryptions or other operations. Eventually, the adversary submits two distinct chosen plaintexts $M_0$, $M_1$ to the challenger. The challenger selects a bit b $ \in \{0, 1\}$ uniformly at random, and sends the challenge ciphertext C = E(PK, $M_b$) back to the adversary. The adversary is free to perform any number of additional computations or encryptions. Finally, it outputs a guess for the value of b.

http://en.wikipedia.org/wiki/Ciphertext_indistinguishability

1. Because the adversary has the PK, this means he can encrypt any arbitrary text. Why can't he compare the ciphertexts from $M_0$, $M_1$ with the challenge ciphertext? Is the function $E$ different for the adversary and for the challenger?

2. Does this mean classic hash functions like SHA1, MD5, etc are not IND-CPA secure?

Thanks in advance!

Answer 1

This isn't just limited to asymmetric schemes; in any chosen-plaintext attack, even for symmetric ciphers, the attacker can (by definition of the CPA game) compute as many encryptions as they like (limited to polynomial time, of course). Formally, we say the adversary is given access to an "encryption oracle."

Anyway, you have stumbled across a necessary property for CPA security: any cipher that has IND-CPA security has to be nondeterministic. That is, every time a value is encrypted, the ciphertext should be (with overwhelming probability) different. Hence, an attacker can compute $E(m_1)$ and $E(m_2)$, but the challenge ciphertext will be different from either of those thanks to nondeterminism.

As a concrete example, look at the CBC mode for a block cipher. In this mode, each encryption uses an unpredictable IV which is XORed with the first block. Hence, each time you encrypt the same message, it will be (again, with overwhelming probability) a different ciphertext. So, you can't compare ciphertexts to learn if the plaintexts are equal.

In the case of RSA, a careful padding scheme has to be used to transform RSA into a nondeterministic scheme. One such popular padding scheme is Optimal Asymmetric Encryption Padding, often abbreviated as OAEP.

Does this mean classic hash functions like SHA1, MD5, etc are not IND-CPA secure?

Hash functions aren't encryption schemes, so the notion of indistinguishable encryptions doesn't really apply. However, I suppose you could say they don't have "indistinguishable digests" under chosen-plaintext attacks because they are deterministic: if you wanted to build a distinguisher under CPA, you'd do exactly as you suggest in your question, namely compute $H(m_1)$ and $H(m_2)$ and compare that to the "challenge digest."

Actually, there is no secret associated with a hash function, so hash functions don't have indistinguishable digests under any model. If the attacker gets to know the messages, they can just compute the digest of the messages and compare them directly. So, in some sense, an attacker always has access to a "hashing oracle" by the nature of the algorithm. Instead of "indistinguishable digests", a hash function's quality is usually judged on how collision-resistant it is, how hard it is to find pre-images, and so forth.