Is MAC-then-encrypt with stream ciphers secure?

Question

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):

1. Assume the attacker knows the authenticated plaintexts of two different equal-length messages: $m_1||MAC(m_1)$ and $m_2||MAC(m_2)$.
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$.
3. 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))$.
4. 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?

Answer 1

As correctly pointed out in a comment, the authenticated encryption model assumes that

• the attacker knows the algorithm;
• the attacker can query the encryption oracle with any plaintext $P$ (and a unique nonce $N$) and get MAC-then-Encrypt ciphertext $C$;
• the attacker can query the decryption oracle with any string $C$ pretending to be a ciphertext.

No other data is available to the attacker. The assumption you made that the MAC alone is available is too strong.