While thinking about this recent question about a hash-then encrypt design, I reread the MAC-encrypt vs. encrypt-MAC question and noticed this answer quoting a paper showing that MAC-then-encrypt is secure with stream ciphers, even if not generically.
However, there's this attack when the MAC is deterministic and the cipher a stream cipher (or a block cipher in e.g. CTR or OFB mode, or even a OTP):
- Assume the attacker knows the authenticated plaintexts of two different equal-length messages: $m_1||MAC(m_1)$ and $m_2||MAC(m_2)$.
- The attacker intercepts the ciphertext of a third equal-length message: $E_k(m_3) = S_k(n) \oplus (m_3||MAC(m_3))$, where $S_k(n)$ is a unique keystream from nonce $n$.
- The attacker can now modify the message in flight to $S_k(n) \oplus (m_1||MAC(m_1)) \oplus (m_2||MAC(m_2)) \oplus (m_3||MAC(m_3))$.
- With a high probability, that is only a valid message when $m_3$ matches either $m_1$ or $m_2$, which the attacker could learn from whether the receiver e.g. asks for a new message (assuming corruption) or accepts it. If it was one of those two messages, it becomes the other instead.
This seems to both give the attacker information on the original message $m_3$ and allow them to forge communications.
Is there something wrong with the attack (e.g. did I assume too much) or is this just a lesser break than the paper (pdf) from that answer considers?