1
$\begingroup$

Suppose that we have a symmetric 256-bit master key, and we want to encrypt using AES-GCM with random IVs. I understand that with random IVs, the lifetime of the master key is 2^32 in order to conform to NIST requirements.

Let's assume that we want to increase the lifetime of the master key. Can we do this by adding a key derivation step before the actual encryption? Assuming that we use the master key as input keying material and a random nonce in HKDF, can we extend the master key's lifetime?

In other words, is AES-GCM(HKDF(MasterKey, ...), IV, ...) offering any advantage regarding the total number of messages versus AES-GCM(MasterKey, IV, ...)?

Specifically, assuming that HKDF has a fixed salt and random 128-bit nonce as input, and GCM uses a 96-bit random IV, then I assume that (WK, IV) have a lower collision probability than (IV). If this assumption is correct, how does one go about calculating a bound for the master key's lifetime?

$\endgroup$
2
  • $\begingroup$ "I understand that with random IVs, the lifetime of the master key is 2^32 in order to conform to NIST requirements." Yeah, but... GCM is based on CTR mode and there's research that suggests that you should limit the total amount of data encrypted with a single key (irrespective of how many IVs are used) to be about 64 GB (depending on your risk tolerance). "In particular, we show that message-recovery attacks against the CTR mode can be mounted with roughly the same requirements and the same complexity as attacks against the CBC mode." See eprint.iacr.org/2018/159.pdf $\endgroup$ May 20, 2022 at 12:41
  • $\begingroup$ Some collision calculations is done here; Multiple AES Key Derivation from a master key also, is it possible to use AES-GCM-SIV? $\endgroup$
    – kelalaka
    May 20, 2022 at 20:42

1 Answer 1

1
$\begingroup$

Let's assume that we want to increase the lifetime of the master key. Can we do this by adding a key derivation step before the actual encryption? Assuming that we use the master key as input keying material and a random nonce in HKDF, can we extend the master key's lifetime?

Yes, certainly when it comes to the requirements of GCM anyway. There may of course be other considerations because the same master key is still protecting a possibly large amount of messages.

In other words, is AES-GCM(HKDF(MasterKey, ...), IV, ...) offering any advantage regarding the total number of messages versus AES-GCM(MasterKey, IV, ...)?

Potentially yes, it of course depends on the other inputs of HKDF, but as long as the input to HKDF is unique you have a secure one-way function that makes the derived keys independent of each other.

Specifically, assuming that HKDF has a fixed salt and random 128-bit nonce as input, and GCM uses a 96-bit random IV, then I assume that (WK, IV) have a lower collision probability than (IV).

There is no "nonce" defined as an input parameter to HKDF, but you can use one within the Info field.

A "fixed salt" is of little to no use. You can however use an empty salt parameter and use a nonce as part of the Info parameter and be reasonably secure.

With a salt you don't have to think about domain separation (e.g. the use your master key for anything else that might interfere), source independent extraction (e.g. the possible repetition of the nonce or bad entropy of the master key) - but you can do without.

Actually, you can skip a step if you want and just use HKDF-Expand if your master key has enough entropy. In that case, there is no Salt parameter required.

I would recommend having some additional constant string in the Info field that can also be used to derive keys from the master for additional use cases. For instance, the Info field could use a label called "EncapKey". This simply indicates what the use case of the derived subkeys is - it provides some domain separation.

If this assumption is correct, how does one go about calculating a bound for the master key's lifetime?

Let's assume that you output 256-bit keys and use at least SHA-256 as an underlying hash. Then the additional chance of collision can be considered negligible; it depends entirely on the collision properties of the nonce provided.

As indicated, there may be other reasons why you want to refresh your master key now and then, because the security of the messages still depends on that one single key.

$\endgroup$
6
  • $\begingroup$ Thank you for your reply. I am still a bit confused regarding this. In rwc.iacr.org/2018/Slides/Gueron.pdf the authors follow a similar approach but their computed boundaries are different. Furthermore, in the original paper they state that AES-GCM with key derivation does not allow for more messages to be encrypted when the IV is chosen randomly (just longer messages). In your reply, are you implying that this is entirely dependent on the HKDF output, or did I misunderstand? HKDF input relies on the same entropy source as the IV, so the birthday problem kicks in in both info and IV. $\endgroup$ May 20, 2022 at 13:02
  • $\begingroup$ Ah, sorry, yes, if you use a 128 bit random nonce then you need to consider the birthday bound for that, obviously. I was put on the wrong foot as you distinguished between a salt and a nonce in your question. Can you indicate what you think is the difference between these two terms? $\endgroup$
    – Maarten Bodewes
    May 20, 2022 at 14:47
  • $\begingroup$ By nonce I basically meant putting 16 random bytes in the info. I would like to generalize this issue outside of the choice of the KDF though. In theory, does appending a KDF step before the AESGCM step make the system handle more than 2^32 messages securely? And if so, is it because it is hard to find (WK, IV) pair collisions than plain IV collisions (i.e., the case of plain GCM with the KDF step)? $\endgroup$ May 20, 2022 at 15:19
  • $\begingroup$ Yes, the collision would be entirely in the sub-key generation. As the key changes you don't need a random IV at all, as the set key, IV would now rest almost entirely on the strength of the key. So in that sense it makes more sense to put all the random bits in your Info. I don't think it matters much, but it makes more sense to me to put all those bits in the salt - that's a per-derivation random value after all - and then use some label in the Info field. The disadvantage of that is that you'd have to use the full HKDF though. $\endgroup$
    – Maarten Bodewes
    May 20, 2022 at 16:19
  • $\begingroup$ Why would it rest on subkey derivation? Wouldn't we have to multiply the collision probabilities of both the subkey and the IV happening together? $\endgroup$
    – millenseed
    May 21, 2022 at 5:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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