Using AES-CTR to generate AES subkeys from a master key and nonce

Question

Suppose I would like to encrypt some data using AES-GCM because it has hardware support on my processor and it is secure.

Unfortunately, I don't like the 96-bit nonce size, because I want to randomly generate the nonce each time (to avoid having to keep state).

So instead of it, I use my 256-bit master key to encrypt 32 null bytes with AES in CTR mode with a 127-bit nonce, and use the resulting keystream as the AES-GCM key.

I have now a $96 + 127 = 223$ bit nonce, which is plenty long enough to generate afresh each time.

I presume that this is secure since a block cipher in CTR mode can be used as a CSPRNG (as here).

Am I correct?

Answer 1

If I understand correctly:

You have a 256-bit master key $K0$
Generate a random 128-bit value $N0$ and set the last bit to 0
Generate a 256-bit keystream $K1$ using $E_{K0}(N0)$ || $E_{K0}(N0 \oplus 1)$
Generate a random 96-bit value $N1$
Using $K1$ as the key, and $N1$ as the nonce, encrypt your message with AES256-GCM, and authenticate $N0$ as associated data
Include $N0$ with the ciphertext

As you suggested, this should give a 127-bit effective nonce size for generation of the key $K1$, plus a 96-bit nonce size for the actual nonce, resulting in 16 byte ciphertext expansion, and minimal extra computation, but now with a $2^{-111.5}$ probability of a key/nonce pair reuse.

Because there are only $2^{127}$ possible keys, you may want to consider additional ciphertext expansion, and instead generate a 256-bit nonce $N0$, encrypting the whole thing with ECB or CBC to get $K1$.

Be aware, security proofs may include keeping the nonce $N0$ (effective state) of the PRNG secret, and here you are providing it as part of the ciphertext. I would do it like this:

You have a 256-bit master key $K0$
Generate a random 256-bit value $N0$
Generate 256-bit key $K1$ by hashing $N0$ with something like SHA-384
Generate a random 96-bit value $N1$ (optional)
Generate $S$ = $E_{K0}(N0)$
Using $K1$ as the key, and $N1$ as the nonce, encrypt your message with AES256-GCM, and authenticate $S$ as associated data
Include $S$ with the ciphertext

Encryption only requires a single hash iteration beyond the initial scheme, in addition to the ciphertext expansion from $S$. Decryption of the message requires decryption of $S$ followed by hashing to recover $K1$. In this scenario a GCM nonce $N1$ is not required to be generated, since you are using a new 256-bit key with each message you can use a fixed nonce. You could also get $N1$ from the unused remainder of the hash output. The GCM key is also protected by encrypting the state of the PRNG, which is now a random input to a hash function.

It is probably not insecure to do it your way, I just do not feel good about exposing $N0$ directly. If the system RNG has some problem, exposure of $N0$ (or even $N1$) could give an attacker information they could use against you in some way. Dual-EC is a good example.