# Is MAC-then-encrypt with stream ciphers secure?

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?

-
You assumed too much. $\:$ (There's really nothing else to say.) $\;\;\;\;$ –  Ricky Demer Jul 24 '14 at 9:01
@RickyDemer, any specifics? E.g. is the problem 1. and that an attacker must never see authenticated plaintext? (Which implies the MAC key used in MAC-then-encrypt must never be used for anything else.) –  otus Jul 24 '14 at 9:17
The problem is 1; an attacker must never see authenticated plaintext. $\;$ –  Ricky Demer Jul 24 '14 at 9:21

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.

-
Ok, I guess it makes sense as the formal model. Nevertheless, it seems like something a practical implementation could get wrong. –  otus Jul 25 '14 at 7:55
Yes. The MAC here is essentially an intermediate variable in the encryption procedure. A secure implementation shall never leak any intermediate variables. –  Dmitry Khovratovich Jul 25 '14 at 9:28
That part should be known to all implementors, but the fact that you can't reuse the MAC to authenticate other (plaintext) strings is not the case with encrypt-then-MAC. –  otus Jul 25 '14 at 10:50
In your attack you do not reuse the MAC for other plaintexts. –  Dmitry Khovratovich Jul 25 '14 at 12:15
Yes, I mean that you do not reuse the same MAC value for another plaintext. –  Dmitry Khovratovich Jul 25 '14 at 13:00