7
$\begingroup$

Semantic Security is a concept that made New Cryptography, (that is Cryptography invented after 1975) into a rigorous science. It connected old cryptography (that is Shannon's information theory-based cryptography) to New Cryptography.

Suppose that we use a randomly chosen 128-bit IV to encipher a 128-bit message $m$, and AES with a randomly chosen key $k$, to generate a 256-bit cipher-text computed as: $IV \| \mathrm{AES}(k,(IV \oplus m))$. Here $\|$ means concatenation and $\oplus$ means exclusive or.

Why is this scheme semantically secure against an eavesdropper, but not against an active attacker? -- i.e why is it secure against Chosen Plaintext Attack, but not against Chosen Ciphertext Attack?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Hint: what could an attacker do if he could submit arbitrary ciphertexts (other than the challenge ciphertext)? $\endgroup$
    – poncho
    Apr 21, 2017 at 15:51
  • 2
    $\begingroup$ CPA is the same as eavesdropping for public-key cryptosystems but not for private-key ones! $\endgroup$
    – fkraiem
    Apr 21, 2017 at 16:55

1 Answer 1

Reset to default
6
$\begingroup$

To answer the question, its necessary to invoke the following security definition, which requires that for any encryption scheme $\pi$ to have indistinguishable encryptions under chosen ciphertext attack (viz., for the scheme to be CCA secure), the following condition, which I'll describe, must hold in the so called "CCA distinguishing game" (throughout, I'm using the notation of Katz and Lindell, and the CCA property is more expansively described in their text Intro to Modern Cryptography, 2nd ed. CRC Press):

$\textbf{Pr}[\textbf{PrivK}_{\mathcal{A},\pi}^{cca}(n) = 1] \leq 1/2 + \text{negl}(n)$

Here $\textbf{Pr}[E=e]$ denotes the probability that experiment $E$ has outcome $e$, and $\textbf{PrivK}_{\mathcal{A},\pi}^{cca}(n) = 1$ denotes the outcome where the CCA adversary $\mathcal{A}$ wins the CCA distinguising game ($K$ is an encryption key of length $n$ and $\text{negl}(n)$ is a "negligible'' function in $n$). Also, throughout we assume $\mathcal{A}$ is PPT.

(this definition needs to be expanded to allow for encrpytions and decryptions of multiple messages in an analogous vein to the "Left-Right" or LR-Oracle CPA security game described here - https://cseweb.ucsd.edu/~mihir/cse207/w-se.pdf, but the above definition is sufficient for illustration purposes)

So to restate, the CCA security definition requires that the above condition for the scheme $\pi$ must hold in the CCA distinguishing game $\textbf{PrivK}_{\mathcal{A},\pi}^{cca}(n)$ in order for the scheme to be CCA secure. The rules of the game are that the adversary $\mathcal{A}$ has oracle access to the encryption and decryption functions, and it proceeds by her selecting 2 equal length messages $m_0$ and $m_1$ and submitting them to the encryption oracle, which flips a coin and based on the outcome sets a bit $b$ to either 0 or 1. Based on the value of $b$, the oracle encrypts either $m_0$ or $m_1$ and returns the resulting ciphertext $c$ to $\mathcal{A}$ (which is also called the challenge ciphertext). $\mathcal{A}$ can continue to invoke the encryption and decryption oracle on any messages other than the challenge ciphertext. At the end, $\mathcal{A}$ outputs a bit $b^{\prime}$. The adversary wins the game, which is denoted by the condition $\textbf{PrivK}_{\mathcal{A},\pi}^{cca}(n) = 1$ when $b^{\prime} = b$.

Now consider a CPA secure counter mode encryption scheme such as AES-128-CTR. $\mathcal{A}$ can choose messages $m_0 = 0^{128}$ and $m_1 = 1^{128}$ and submit them to the encryption oracle. Suppose that the oracle sets $b = 0$ and returns the challenge ciphertext $c$. The adversary can then flip the first bit of c resulting in a ciphertext $c^{\prime}$. Since $ c^{\prime} \ne c$, $\mathcal{A}$ can legitimately submit this to the decryption oracle which returns the plaintext $10^{127}$, at which point $\mathcal{A}$ outputs $b^{\prime} = 0$ and can trivially win the game every time thereby violating the CCA security condition $\textbf{Pr}[\textbf{PrivK}_{\mathcal{A},\pi}^{cca}(n) = 1] \leq 1/2 + \text{negl}(n)$

Improve this answer
$\endgroup$
4
  • $\begingroup$ Rohit Khera's answer is excellent and clearlty shows that in particular AES-128-CTR is CPA-secure but not CCA-secure. $\endgroup$
    – Istvan Simon
    Apr 22, 2017 at 18:43
  • $\begingroup$ But what I proposed is not AES-128-CTR , so her answer could be improved. Let me rephrase my question slightly, so it is made perhaps clearer. Suppose that I am the CCA attacker and I want to change the ciphertext so that when decoded it will change a single bit of the 128-bit original message. Say I would like to change the 85-th bit of the message from 0 to 1. What ciphertext should I send under the scheme I proposed which uses AES that accomplishes this? $\endgroup$
    – Istvan Simon
    Apr 22, 2017 at 18:48
  • $\begingroup$ @IstvanSimon in this case, since in your original question you defined your ciphertext as $IV||AES(k,IV \oplus m)$ where m is 128 bits long, in order to flip the 85th bit of the of the original 128 bit message, you would flip the 85th bit of the IV. $\endgroup$
    – Rohit Khera
    Apr 25, 2017 at 18:37
  • $\begingroup$ Yes Rohit Khera's answer is perfect. $\endgroup$
    – Istvan Simon
    May 7, 2017 at 18:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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