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:


How we can use one-time-MAC without negotiating the different keys for each message?
What is wrong with randomized-CBC that doesn't allow us to use with one-time-MAC?
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] &lt; \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)] &lt; \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.