3
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The reason I was not worried about exposing $N0$ is that it I thought that an attacker could not derive any useful information from it assuming that AES-CTR is secure. $\endgroup$ – Demi Apr 13 '16 at 16:01
  • $\begingroup$ One disadvantage of your approach is that the new randomness must be completely random, as opposed to just being widely distributed (to prevent collisions). $\endgroup$ – Demi Apr 13 '16 at 16:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.