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