- Assuming that the nonce values are unique and generated according to some fixed public counter sequence that is not under the attacker's control, is the encryption scheme described above (i.e. pad the nonce to a full cipher block, prepend it to the plaintext, and encrypt the result using CBC mode with an all-zero IV) actually IND-CPA secure?
Yes, nonce-based CBC has reasonable IND-CPA security bounds just like traditional CBC.
- If so, is there a published proof of this? If not, is there a known attack under the IND-CPA model that doesn't assume the attacker can choose the nonces?
Yes: there is a published proof just below. (I leave it to the asker to specify restrictions on venue that would exclude pseudonymous feathery bloviators on the internet.)
- How does the quantitative security (e.g. attacker's advantage as a function of the number of encryption oracle queries) compare to standard CBC mode with random IVs? AFAICT, both are basically only secure up to the birthday bound, but a more detailed analysis could be useful.
Quantitatively, the security drops with the number of queries times the number of blocks, because there is a potential for a ciphertext-chaining block to coincide with a nonce. But the security of CBC itself already drops with the square of the total number of blocks, which is larger than that already (unless every message is a single block long).
- As a bonus, what if the nonce is padded to some fixed length that is less than a full cipher block? Is the resulting scheme still IND-CPA secure (assuming that the nonce doesn't overflow, of course) and if so, how does this affect the number of messages that can be safely encrypted?
How you format the nonce is inconsequential as long as nonces are distinct. The crux is that in case (2) below, $m_{n_1,i+1} \oplus f(\cdots \oplus m_{n_1,i})$ is uniform random, so it has equal probability of coinciding with any fixed nonce. Although stated in terms of the nonce $n_0$, the proof really assumes only that the first block fed to the cipher is unique.
Details.
An attack $A$ on a cipher is random algorithm that submits a sequence $m_0, m_1, \dots, m_{q-1}$ of $q$ queries (possibly adaptively), for messages up to $\ell$ blocks long, to an encryption oracle; for the last two queries the oracle returns the encryption of only one of them, determined by a fair coin toss, and the attack wins if it guesses correctly which face the coin landed on. The IND-CPA advantage of an attack $A$ is defined to be $$\operatorname{Adv}^{\operatorname{IND-CPA}}_{\mathcal O}(A) := |\Pr[A(\mathcal O)] - 1/2|,$$ where $\Pr[A(\mathcal O)]$ is the success probability of $A$ on the oracle $\mathcal O$. (The oracle is assumed to know how to count.)
Fix a block size $b$. Each message $m_n = m_{n,0} \mathbin\| m_{n,1} \mathbin\| \cdots$ will be an integral number of $b$-bit blocks. For a function $F$ and a block $\mathit{iv}$, define $$\operatorname{CBC}_F(\mathit{iv}, m_n) := F(\mathit{iv} \oplus m_{n,0}) \mathbin\| F(F(\mathit{iv} \oplus m_{n,0}) \oplus m_{n,1}) \mathbin\| \cdots.$$
In traditional CBC mode for a random function $F\colon \{0,1\}^b \to \{0,1\}^b$ of blocks, to answer a query for the $n^{\mathit{th}}$ message $m_n$, the encryption oracle samples $\mathit{iv}_n$ uniformly at random and reveals $$\operatorname{TCBC}_F(m_n) := \mathit{iv}_n \mathbin\| \operatorname{CBC}_F(\mathit{iv}_n, m_n).$$ The success probability $\Pr[A(\operatorname{TCBC}_F)]$ of any attack $A$ against traditional CBC is bounded by the standard CBC theorem: for uniform random $f$, $$\Pr[A(\operatorname{TCBC}_f)] \leq 1/2 + O(q^2 \ell^2/2^b).$$ To allow decryption one usually instantiates traditional CBC with $F = E_k$ for a block cipher $E$ and a uniform random key $k$; the standard permutation-for-function substitution lemma just adds $O(q^2/2^b)$ to the probability.
Define the following alternative scheme, where $G\colon \{0,1\}^b \to \{0,1\}^b$ is another random function of blocks: To answer a query for the $n^{\mathit{th}}$ message $m_n$, the oracle reveals $$\operatorname{NCBC}_{F,G}(m_n) := G(n) \mathbin\| \operatorname{CBC}_F(G(n), m_n).$$ If $F = G$, call it $\operatorname{NCBC}_F$. Consider the following cases:
- $G = g$ is a uniform random function $g$ independent of $F$. Obviously, this is identical to traditional CBC mode for any $F$, because each output $g(n)$ is independent uniform random for distinct $n$ just like $\mathit{iv}_n$, so $$\Pr[A(\operatorname{NCBC}_{F,g})] = \Pr[A(\operatorname{TCBC}_F)].$$
- $F$ and $G$ are the same uniform random function $f$. This case is distinguishable from the preceding one only in the event that $n_0$ coincides with $m_{n_1,i+1} \oplus f(\cdots \oplus m_{n_1,i})$ for some $n_0$, $n_1$, $i$ among the messages submitted to the oracle, which happens with probability bounded by $O(q^2 \ell/2^b)$ where $\ell$ is the mean query length. Thus, if $R$ is the event of this coincidence,
\begin{align*}
\Pr[A(\operatorname{NCBC}_f)]
&= \Pr[A(\operatorname{NCBC}_f) \mathrel| R] \Pr[R] \\
&\quad + \Pr[A(\operatorname{NCBC}_f) \mathrel| \lnot R] \Pr[\lnot R] \\
&\leq \Pr[R] + \Pr[A(\operatorname{NCBC}_f) \mathrel| \lnot R] \\
&= O(q^2 \ell/2^b) + \Pr[A(\operatorname{NCBC}_{f,g})].
\end{align*}
(Exercise for reader: Write down a concrete formula for a bound on $\Pr[R]$. To make it simpler, replace $m_{n_1,i+1} \oplus f(\cdots \oplus m_{n_1,i})$ by, say, $m_{n_1,i+1} \oplus f(n_1\mathbin\|i)$: ensuring distinct inputs to $f$ can only raise the probability that one of the chaining values coincides with one of the nonces, and every output of $f$ on distinct inputs is independent uniform random.)
- $F = G = \pi$ for a uniform random permutation $\pi$. By a standard theorem about substituting uniform random permutations for uniform random functions, for any algorithm $A$ making $q$ queries,
\begin{align*}
\Pr[A(\operatorname{NCBC}_\pi)]
&\leq \Pr[A(\operatorname{NCBC}_f)] + q(q - 1)/2^{b + 1} \\
&= \Pr[A(\operatorname{NCBC}_f)] + O(q^2/2^b).
\end{align*}
(Alternatively, one can use the somewhat better but less standard bound $\Pr[A(\operatorname{NCBC}_\pi)] \leq \delta \cdot \Pr[A(\operatorname{NCBC}_f)]$ where $\delta = (1 - (q - 1)/2^b)^{-q/2}$.)
- $F = G = E_k$ for a uniform random key $k$ and a block cipher $E$. The distance between $\Pr[A(\operatorname{NCBC}_{E_k})]$ and $\Pr[A(\operatorname{NCBC}_\pi)]$ is the PRP advantage $\operatorname{Adv}^{\operatorname{PRP}}_E(A')$ of $A'(\phi) := A(\operatorname{NCBC}_\phi)$ to distinguish the block cipher $E$ from a uniform random permutation; presumably $E$ was chosen by years of cryptanalysis to put a confident bound on this distance for all reasonable numbers $q \ell$ of block cipher evaluations.
Thus, the success probability of an attack on nonce-based CBC making $q$ queries of mean length $\ell$ is bounded by:
\begin{align*}
\Pr[A(\operatorname{NCBC}_{E_k})]
&\leq \Pr[A(\operatorname{NCBC}_\pi)]
+ \operatorname{Adv}^{\operatorname{PRP}}_E(A') \\
&\leq \Pr[A(\operatorname{NCBC}_f)]
+ O(q^2/2^b)
+ \operatorname{Adv}^{\operatorname{PRP}}_E(A') \\
&\leq \Pr[A(\operatorname{NCBC}_{f,g})]
+ O(q^2 \ell/2^b)
+ O(q^2/2^b)
+ \operatorname{Adv}^{\operatorname{PRP}}_E(A') \\
&= \Pr[A(\operatorname{TCBC}_f)]
+ O(q^2 \ell/2^b)
+ \operatorname{Adv}^{\operatorname{PRP}}_E(A') \\
&\leq 1/2 + O(q^2 \ell^2/2^b)
+ O(q^2 \ell/2^b)
+ \operatorname{Adv}^{\operatorname{PRP}}_E(A') \\
&= 1/2 + O(q^2 \ell^2/2^b)
+ \operatorname{Adv}^{\operatorname{PRP}}_E(A'),
\end{align*}
or
\begin{equation}
\operatorname{Adv}^{\operatorname{IND-CPA}}_{\operatorname{NCBC}_{E_k}}
\leq O(q^2 \ell^2/2^b)
+ \operatorname{Adv}^{\operatorname{PRP}}_E(A'),
\end{equation}
i.e. essentially the same as for traditional CBC with a block cipher $E$.