Score:2

Chosen Plain text attack

jp flag

I have a course work for university, the question is:

Consider a symmetric encryption scheme with its encryption operation written as

$$C = E(K, R||P)$$

where $E$ is a block cipher encryption algorithm, $K$ is an encryption key, $R$ is a random nonce (i.e., it is randomly generated for each encryption), $P$ is a plaintext, $C$ is a ciphertext, and "$||$" denotes concatenation.

Let the block size be $n$, $R$ is $u$-bit long $(0<u<n)$, the length of $P$ is $v = n-u$ so $R||P$ is exactly one block long. The values $u$ and $v$ are public information.

  1. Explain that given K and C, how one can compute $P$ [1%]

  2. Assume that an adversary (who does not know $K$) has the capability ot choose arbitrary plaintexts and obtain the corresponding ciphertexts. This is done through an oracle, to which the adversary can submit a number of encryption queries. For example, if the block cipher is AES, the oracle is an AES accelerator. In each query, the adversary chooses a pair of $v$-bit plaintext, $P_0$ and $P_1$, and sends them to the oracle. After receiving $q$ such queries, the oracle randomly chooses a bit value $b$ from 0 or 1. If $b = 0$, the oracle will respond with the encryptions of the plaintext $P_0$ for all pairs in the $q$ queries. If $b = 1$, it will respond with the encryption of plaintexts $P_1$ for all the pairs in the $q$ queries. The goal of the adversary is to discover the value $b$. Such an attack is called a chosen plaintext attack (CPA). How does the adversary choose $q$ pairs of $P_0$ and $P_1$ in order to find the value $b$? Explain your answer. [4%]

I am struggling with part 2. So far I have read the wikipedia page (https://en.wikipedia.org/wiki/Chosen-plaintext_attack) for chosen plaintext attacks, which mostly makes sense to me.

Can someone please explain to me why we would even send 2 plaintexts to the oracle then try to guess which ones encryption is being returned to us, to me this makes no sense as surely it would make more sense to just send each plaintext separately and get both of their cipher texts, so that we can learn details about the encryption system.

Any help on understanding this would greatly be appreciated.


3rd-party edit: as explained in the comment, the lecturer who gave the question explained that we can choose the length of $P$, and therefore that of nonce $R$. As DannyNiu mentioned in the comment, if we weren't able to do so, then the encryption is secure under CPA.

DannyNiu avatar
vu flag
My limited crypto maths tells me that un-authenticated non-deterministic encryption is already CPA-secure. Can you give me a bit of hint too? @fgrieu
hasin avatar
jp flag
@fgrieu, I spoke to my lecturer about this question today, and he said that the question is saying that the attacker sends the oracle 2 plaintexts and then the oracle sends back one ciphertext, depending on the value b it chooses. He then said that the question is asking for an explanation on how you would determine which plaintexts encryption was sent back to the attacker from the two initially plaintexts sent. Given this information I understand the question better, however I'm still not sure what to do right now
fgrieu avatar
ng flag
@ hasin: read again: the attacker sends the oracle $2q$ plaintexts, not $2$; and that's critical to a solution. Your question asks why the oracle is like this; I think that's expected to be taken as a given of the problem.
hasin avatar
jp flag
@fgrieu, I still don't understand how having q queries will enable me to determine whether or not b is 1 or 0, which is exactly what the question is asking. He did however highlight the fact that seeing as we can choose the length of the plaintexts to send we can indirectly manipulate the length of the random nonce. However, I dont understand how this allows me to determine the value of b after q queries.
kelalaka avatar
in flag
I found this question not well-written. Consider the nonce as prefix, what you need to send to figure out?
Score:2
ng flag

why would we even send 2 plaintexts to the oracle then try to guess which ones encryption is being returned to us?

That's the basis of the standard theoretical experiments that define the security of a cipher under Chosen Plaintext Attack.

The question is about a slight variant. After reordering things in a way that makes no difference for honest oracle, the setup is equivalent to:

  1. The adversary sends to the oracle $q$ pairs $(P_{i,0},P_{i,1})$ for $i\in[0,q)$, thus totaling $2\,q\,v$ bits. In this, the adversary chooses $v$ or/and $q$, within some non-precisely set limits.
  2. The oracle generates a large secret key $K$, a single bit $b$, and $q$ random values $R_i$ of $u=n-v$ bits, all uniformly and independently at random; then computes and outputs to the adversary $q$ cryptograms $C_i=E(K,R_i\mathbin\|P_{i,b})$ for $i\in[0,q)$, thus totaling $q\,n$ bits.
  3. The adversary examines the output of step 2 and outputs a guess of $b$, which should be sizably better than random.

This setup can be viewed either

  • as a CPA experiment with multiple $v$-bit plaintexts (sent non-interactively), with the twist that the same $b$ is used for all plaintexts;
  • or as the standard CPA experiment with a single long $q\,v$-bit plaintext, for a mode of operation of the cipher at hand that is what ECB is to a block cipher.

Hints† replacing those I gave in comments: There is a method giving the adversary good probability of success subject to plausible conditions on parameters, met for AES-256 as $E$ (thus $n=128$), $v=80$ (thus 10-byte $P$), $q$ about 20 million (thus about <400MiB sent to and ≈300MiB received from the oracle). To find it, wonder what can be meaningfully tested in the output of step 2; then unravel.


† We tend to only give hints to homework, and to give them in comments rather than answer. I made an exception because I had to say more than comfortably fits comments, and it appeared several in the audience could be interested.

kelalaka avatar
in flag
I'm not sure that $P_{i,0}$ and $P_{i,1}$ have the same nonce.
fgrieu avatar
ng flag
@kelalaka: true, that's unclear in the original problem statement. But that's indistinguishable by an arbitrarily powerful adversary or/and even with knowledge of $K$, and does not matter to the advantage of an adversary strategy.
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.