Let F be a block cipher with 128-bit block length. Consider the following encryption scheme for 256-bit messages: to encrypt message $M=m_1∥m_2$ using key $k$ (where $|m_1|=|m_2|=128$), choose random 128-bit $r$ and compute the ciphertext $r∥F_k(r)\oplus m_1∥F_k(m_1)\oplus m_2$. Is there any strategy that leads to a valid chosen-plaintext attack?
This isn't secure by itself against chosen-plaintext attacks.
This mode is known as plaintext-feedback mode (PFB) and referenced for example in here.
The next point is this mode hasn't received much attention in the cryptographic literature, whereas other modes (CFB, OFB, CBC, CTR) have.
- Don't roll your own crypto.
- Never use such modes if anyhow possible. Use established authenticated encryption modes like GCM.
Beyond that even CFB would be a better choice as you need to store the plaintext to encrypt the next ciphertext in this case, whereas for CFB you only need to store the (safe?) ciphertext.
The first attack proceeds as follows:
Suppose your want to decipher $m_2$ and are allowed to view $C_2$ and to choose $m_1$ and to learn the corresponding $C_1$. Suppose further you know $r$, which is required for the valid recipient to know for decryption.
Now choose $m_1=r$. Observe that the following relation will hold $E(r)\oplus m_1 = C_1$. Now extract $E(r)$ by calculating $E(r)=m_1 \oplus C_1$ which is possible since you know $m_1$ and $C_1$.
Now observe further that $E(m_1)\oplus m_2 = C_2$ is equivalent to $E(r) \oplus m_2 = C_2$, as $m_1=r$ holds. As you already calculated $E(r)$ above you can now calculate $m_2$ via $m_2 = C_2 \oplus E(r) = C_2 \oplus m_1 \oplus C_1$.
There's a second attack that decrypt a given message $(r_X||C_X||C_Y)$.
Decrypting $C_X$ goes as follows.
Choose your message to be encrypted to be $(m_1=r_X||m_2)$ for an arbitrary $m_2$.
You'll get the ciphertext (from the oracle): $(r_1||C_1=m_1\oplus E(r_1)||C_2=m_2 \oplus E(m_1))$.
Now oberve that the following holds: $E(m_1)=E(r_X)=m_2 \oplus C_2$.
Therefore you can construct $m_X = C_X \oplus E(r_X) = C_X \oplus m_2 \oplus C_2$.
Ask for encryption of $(m_X||m_3)$ now.
You'll get $(r_2||C=m_X \oplus E(r_2)||C_3=m_3\oplus E(m_X))$.
Use this to calculate $E(m_X)=m_3 \oplus C_3$ and finally $m_Y = C_Y \oplus E(m_X) = C_Y \oplus m_3 \oplus C_3$.
You now successfully retrieved the message $(m_X||m_Y)$ using a chosen-plaintext attack.
Hence this scheme is broken.