When using AES-GCM-256 with random nonces, a limit of 2^32 encryptions is specified in order to have a low nonce collision probability. A new key has to be generated to take its place afterwards, I am at this point.

I used my old key to encrypt data that I stored on a cloud storage service, there is already a lot of data present and it would be bothersome to upload all the data encrypted with the new key again. I would like to store the old key to use it for decryption of the old content, but then the files would need to know which key was used for encryption and I'd need to add this information to all the filed in some way.

What are the best practices for switching to a new encryption key when this limit is almost reached? Is there anything I can do to prevent re-encrypting all the data?

  • 1
    How long is the used nonce? In encrypted storage typically for each file you use an own key, saved wrapped with a master key together with the file.
    – Robert
    Jul 23, 2021 at 21:33
  • The used nonce is a randomly generated 96-bit number. Thank you for the keyword "key-wrapping". I did not use key-wrapping, I just used a key to encrypt all the blocks (that changed) before uploading. I read a little bit into it and it looks like what I need. If I understand it correctly we gain that an attacker can only see that two different plaintexts are the same and no security is lost otherwise. This raises the question on key collisions, but this is already answered numerous times. Great, your comment made me do research to answer my own question! I'll try posting an answer myself ...
    – Gamer2015
    Jul 24, 2021 at 9:08

1 Answer 1


A comment from Robert gave me the key-word I needed to be able to do some research myself, so I'll post what I have learned and how it should be done in the first place. I am not sure what the best way to transition from my situation to the goal is in general, but I think this varies depending on outside constraints. For me it is best to re-encrypt all the data with the newly presented approach since there are no external constraints.

What to do in the first place?

Instead of just encrypting all the data with a single key, a new key should be generated for each file. These keys should be wrapped using a master-key and stored alongside the file. The master-key is your client secret and used purely for wrapping and unwrapping keys.

Why should it be done this way?

Key-wrapping algorithms have a number of properties including confidentiality, authenticity and, in particular, the property that an attacker can only see when two plaintexts match. Using the property that cryptographic keys have high entropy, this gives us a larger bound on the number of keys that can be wrapped.

- Better invocation limit or better collision probability

NIST specifies a limit of 2^32 invocations of AES-GCM per key when not using deterministic 96-bit nonces to keep the probability of a collision below 2^-32. Since I used randomly created 96-bit nonces, this limit also applies to the number of invocations I should limit myself to.

When using the key-wrapping approach from above by wrapping the 256-bit keys, the limit of invocations is increased drastically. The number of invocation for wrapping 256-bit-keys, that can be done with one key while keeping the same collision probability of 2^-32, is 2^112 (source: maths). In the same fashion, the number of invocations for wrapping 256-bit-keys can be reduced to 2^96 while reducing the probability of a collision to 2^-64.

- Changing the key is easier

Aside from the increased number of invocations it is now possible to update the master-key by only re-wrapping the file keys. This may still be a tedious task, but it is still far better and cheaper than to re-encrypt potentially gigabytes of data per file.

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.