Chosen-plaintext attack

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?

No.
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.

Two notes:

• 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.

• The statment "But also note that most other standard modes (CBC, CFB, CTR, OFB) are vulnerable to chosen plaintext attacks as well." is completely false. CBC, OFB and OFB are CPA-Secure. May 17 '15 at 17:10
• @Gordon, proof please and I'll do some research on this I have a paper in mind but need to find it again...
– SEJPM
May 17 '15 at 19:28
• @Gordon, you seem to be right as I've revisited the mentioned paper and it assumes CPA resistance for the modes but makes clear that they aren't CCA-secure. I'll edit the answer.
– SEJPM
May 17 '15 at 19:39
• Refer to P.95-97 of Katz's book (link at: u-cursos.cl/usuario/777719ab2ddbbdb16d99df29431d3036/mi_blog/r/…) It is explicity stated. May 17 '15 at 19:46
• @Gordon, thank you. This book looks indeed very interesting as it seems to be more formal than Schneier's and "The Handbook". I already edited the question as my source from which I thought this is the case said CCA and not CPA.
– SEJPM
May 17 '15 at 19:51