1. Indistinguishable Chosen Plaintext Attack¶
Before formally introducing Ind-CPA (Indistinguishable-Chosen Plaintext Attack), let’s first state why RSA, ElGamal are not secure due to “meet-in-the-middle” attack.
1.1. Knowledge required¶
1.2. Insecurity of RSA¶
Plaintext \(m = M_1 \times M_2\). This is the case where the plaintext is easy to factorize.
We can see the multiplication property of RSA.
Attack
The idea is to build a sorted database and do a meet-in-the-middle attack.
Suppose Malice knows \(m < 2^l\) and \(m\) is a coimposite number with non-negligible probability satisfying \(m=M_1M_2\) with \(M_1, M_2 < 2^{l/2}\), then \(C = M_1^e M_2^e~mod~N\).
The database stores \(1^e, 2^e, 3^e, \cdots, (2^{l/2})^e~mod N\).
Search the database to find \(C/{i^e}~mod~N\) for \(i = 1, 2, \cdots, 2^{l/2}\) such that
Then, Malice knows that the plaintext is \(m = ij\).
Why this is crucial Suppose the system uses 1024 bit RSA to encrypt 56 bit DES session key. DES key can be discovered by factoring the key into 2 integers using \(2^{56/2} \cdot 1024 = 2^{38} bits \approx 34.35 GB\). So don’t use RSA to encrypt short key, password.
1.3. Insecure of ElGamal¶
ElGamal choose prime number \(p\), primitive root \(g\), secret key \(a\) and \(b = g^a~mod~p\).
\(E(m) = (g^k, mb^k) = (y, z)\) for a random number \(k\).
\((\frac{y}{p}) = (\frac{g}{p})^k = (-1)^k\) \(\Rightarrow\) parity of \(k\) can be determined.
\((\frac{z}{p}) = (\frac{m}{p})(\frac{b}{p})^k\) \(\Rightarrow\) we know \((\frac{b}{p})\) and parity of \(k\) \(\Rightarrow\) \((\frac{m}{p})\).
Adversary can choose a plaintext \(x_1\) in \(QR_p\) and \(x_2\) in \(QNR_p\) and distinguish the ciphertext.
see Jacobi Symbol for additional information.
1.4. Lessons¶
No deterministic system can protect bit security;
Random message needs to be added to make it semantically secure;
Any deterministic PKS can be made semantically secure by random padding
1.5. How to Do Random Padding¶
\(E\) is the PKC algorithm. \(H\) is a hash function with block size \(m\). To encrypt plaintext \(m\), pick a random number \(r \in \mathbb{Z}_n\)
\(E^*(x) = (E(r), H(r) \oplus m) = (y_1, y_2)\)
\(D^*(y_1, y_2) = H(D(y_1)) \oplus y_2\)
1.6. Semantic Security¶
A PKC system is semantic secure if \(\nexists\) PPT algorithm \(A\) with an advantage \(2^{-k}\epsilon\) (\(k\) can be 1024) such that:
\(A\) picks two plaintexts \(x_1\) and \(x_2\) (A chosen plaintext)
PKC picks an index \(i \in \{0, 1\}\) and generates one ciphertext \(y = E(x_i)\)
\(A\) guesses \(i = 0~or~1\) when receiving \(y\).
If such \(A\) exists, it is a ciphertext distinguisher.
1.6.1. Mental Poker Game¶
Alice is in NYC, Bob is in London. Both of them choose a card from three cards. Cards are encrypted into messages and must be dealt fairly. Fairly means:
all possible hands have same likelihood;
no idea about other person’s cards;
A & B are cheaters \(\Rightarrow\) no trust;
there should be verification that the game has been played fairly.
We should use a cipher with “commutative property” such that
1.6.1.1. Fair Deal Protocol¶
Alice encrypts 3 cards as \(C_i = E_A(M_i), i=1, 2, 3\). Send ciphers \(\{C_i\}_{i=1}^3\) to Bob in random order.
Bob randomly select one cipher \(C \in \{C_i\}_{i=1}^3\), then encrypts it \(CC = E_B(C)\) and sends another cipher \(C'=\{C_i\}_{i=1}^3\setminus C\) to Alice.
Now \(CC\) is Bob’s hand, \(C'\) is Alice’s hand
Alice decrypts both \(C'\) and \(CC\) and sends \(C''=D_A(CC)\) to Bob.
Bob decrypts \(C''\) and obtains his hand.
Suppose RPK system is using RSA. Let \(N\) be the shared modulus and \(N = pq\). Let \((e_A, d_A)\) and \((e_B, d_B)\) be the encrypt and decrypt keys of Alice and Bob. Before finishing a game, Alice and Bob keep their secret key but disclose for verification. Observe that, if some cards in \(QR_n\), but some not, then Alice and Bob will know which of the card is chosen, because RSA can not change the \(QR_n\) property of plaintext and ciphertext.
1.7. Probabilistic Encryption Algorithm¶
Two algorithms will be introduced.