Extending AES-GCM initialization vector

Well, supposing everything is properly domain separated, nonces are always generated randomly for encryption queries, and your KDF behaves like a perfectly random function, the first step is to bound the probability of a nonce repeat. A birthday bound tells us that this happens with probability at most $$ q^2/2^{256}\,, $$ where $q$ is the number of encryption/decryption queries. So let's rule this case out, and move to the case where this never happens.

Next is the event of key collisions. Again, a simple birthday bound gives us a probability of at most $$ q^2/2^{256} $$ that there are repeated derived keys.

Now what we have here is, in fact, an instance of multi-user GCM where the same nonce is always used. That is, you have up to $q$ independent instances of GCM, and to break the scheme it suffices to break any one of these instances. (Strictly speaking, the multi-user setting gives you more freedom in choosing how many queries per user you can use, whereas here you're limited to 1 (encryption) query per user.)

The multi-user security of GCM was conveniently analyzed by Hoang, Tessaro, and Thiruvengadam in the ideal cipher model, which tells us in Theorem 3.1 $$ \begin{align*} \mathbf{Adv}_{\mathtt{CAU}[H,E]}^{\text{mu-ae}} \le &\frac{d(p+q) + n(q + \sigma + p)}{2^k} + \frac{\sigma(2B + cn + 3)}{2^n} \\& + \frac{2q+1}{2^{2n}} + \frac{\sigma(\sigma + ncd) + 2pq}{2^{k+n}}\,. \end{align*} $$ Here we can set $n = 128$, $k = 256$, $d = q$ ($d$ is the number of nonce repetitions across users; since the nonce is fixed, this is equal to the number of queries), $c$ is a bound on the differential probability of $H$ (for GHASH, it can be set to $B/2^n$), $B$ is the maximum message size in blocks, $\sigma$ is the total number of blocks across queries (which can be bounded by $qB$), and $p \le 2^{n-2}$ is the number of offline AES evaluations (i.e., bruteforce of the key).

So, roughly speaking, as long as your messages are sufficiently short (to keep the $O\left(\frac{qB^2}{2^{128}}\right)$ term down), and the total number of queries remains well below $2^{128}$ (to keep the terms $2q^2/2^{256}$ and $O\left(\frac{q^2 + pq}{2^{256}}\right)$ down), as you suggested, this scheme should remain secure.

Solved by user592 (11,680 )
Sep 01, 2020 at 21:42