# Why is a one-time MAC secure for MAC-then-encrypt with randomized-CTR but not randomized-CBC?

The Coursera cryptography 1 course says:

If you want to use MAC-then-encrypt mode then you should either use randomized-CTR or randomized-CBC. And if you use randomized-CTR then one-time-MAC is sufficient.

Here is the slide:

I have two question regarding this:

1. How we can use one-time-MAC without negotiating the different keys for each message?
2. What is wrong with randomized-CBC that doesn't allow us to use with one-time-MAC?

1. How can we use one-time-MAC without negotiating the different keys for each message?

If you use a universal hashing one-time MAC, and you encrypt it with CTR mode, effectively you are creating a Carter–Wegman–Shoup MAC:

• Carter and Wegman showed[1] that if $$r, s_0, s_1, \dots$$ are independent uniform random and $$H_r$$ is a universal hash with bounded difference probability $$\Pr[H_r(x) - H_r(y) = \delta] < \varepsilon$$ for all $$x \ne y$$ and $$\delta$$, then the forgery probability for the authenticator $$m_i \mapsto H_r(m_i) + s_i$$ is bounded by $$\varepsilon$$.

• Shoup suggested[2] deriving $$s_i = E_k(i)$$ for a block cipher $$E$$, which is essentially what you get with MAC-then-encrypt in CTR mode. Since $$E_k$$ is a permutation you run up against the birthday bound, of course, just like any use of a block cipher in CTR mode.

1. What is wrong with randomized-CBC that doesn't allow us to use with one-time MAC?

Offhand, I am not sure! If the one-time MAC is a universal hash with bounded collision probability $$\Pr[H_r(x) = H_r(y)] < \varepsilon$$ for all $$x \ne y$$, then this intuitively sounds like it ought to be a secure construction, because $$m \mapsto F_k(H_r(m))$$ is a secure long-input, short-output PRF if $$F_k$$ is a secure short-input, short-output PRF and $$H_r$$ has bounded collision probability[3]. That's not exactly the scenario we have here, because there is not one fixed family $$F_k$$—if we encrypt $$m \mathbin \| H_r(m)$$, we get $$E_k(\mathit{iv} \oplus m) \mathbin\| E_k(E_k(\mathit{iv} \oplus m) \oplus H_r(m)),$$ so $$m$$ figures in twice, but it's pretty close, so intuitively it seems like this should be secure.

Of course, it's not clear that the mere security of a one-time MAC—a bound on forgery probability after a single attempt—implies any of this even with CTR: I'm assuming bounds on collision or difference probabilities, specifically. Maybe you could ask Dan Boneh what he meant.

There is also a danger of padding oracles with CBC in MAC-then-encrypt or MAC-and-encrypt, because CBC works on sequences of blocks rather than sequences of bits, which is why it is hard to get right: practical realizations like TLS and SSH had mistakes for years that leaked plaintexts via padding oracles.