Is AES-GCM with static key and dynamic salt safe to reuse IV/nonce

Problem: want to encrypt messages/objects/files using AES-GCM with the same secret key in a safe way, but want to do it in distributed/stateless way, so the IV of previous encryptions with the same key are not known and as I understand AES-GCM is not so secure with many messages if random IV is used.

Would example of this solution be secure?

1. For each encryption generate 16 bytes random salt (16-BYTES-RANDOM).

2. TMP-AES-16-BYTES-KEY = HKDF-EXPAND-SHA1(STATIC-AES-KEY-16-BYTES | 16-BYTES-RANDOM, 16)

3. Write in message first plain 16 bytes generated random.

4. Use the TMP-AES-16-BYTES-KEY to authenticate first 16 random bytes and encrypt secret data and add tag using 12 bytes IV all zeros.

To decrypt do the opposite - derive temp key from message random and secret key.

• It seems you want to reinvent the IV and name it salt. Regarding the claim "... as I understand AES-GCM is not so secure with many messages if random IV is used.", this is probably wrong in general. It can be a problem, if the number of messages means it's likely that an IV is used twice (e.g. IV too short).
– tylo
Commented Oct 20, 2017 at 14:08

In your description, AES/GCM is always used with a new, fresh key, different from all previous keys. Thus, you are not reusing IV with the same key. In that sense, this should be fine from a security point of view.

However, this seems overly complex and begs the question of: why? The simple way would be to use the static key "as is" and to use a random IV for each message.

GCM is actually defined for all IV sizes up to $2^{64}-1$ bits. When using as IV a controlled monotonic counter such as a message sequence number, a 12-byte IV is recommended, as it guarantees non-reuse. However, when using a random IV, the probability of IV reuse is actually lowest if you use a bit larger IV os 16 bytes or more. When the IV is not exactly 12 bytes in length, the GCM specification mandates a first pass of hashing with its internal, keyed, soft-of-hash function (called GHASH). As an added bonus, internal IV reuse, which would be made quite improbable thanks to the whole 128-bit space, would furthermore be "hidden" from onlookers because GHASH is keyed. Not all implementations of GCM support IV sizes of more than 12 bytes, but then, why would you use poor implementations?

To sum up, while what you suggest does not seem obviously flawed, a simpler and more standard solution exist: just use your key as is, and a random IV. Preferably, boost the IV size to 16 bytes.

• I'm confused about where you see the advantage of >96 bit IVs, when they get hashed down to 96 bits? Commented Oct 20, 2017 at 13:10
• @CodesInChaos They are not hashed down to 96 bits but to 128 bits (i.e. the 32-bit CTR counter does not start at 1 in that case). This reduces probability of CTR counter collision since you do not actually encrypt individual messages of 500 GB each. Commented Oct 20, 2017 at 13:32
• Thank you, I was a bit worried about using non 96-bit IV, because of many recommendations, but I guess it is recommended for performance. Would it be more secure to use 32-bytes vs 16-bytes IV if it is hashed down to 128-bits? Commented Oct 23, 2017 at 7:36
• @JanisCoders Since it is hashed down to 16 bytes, setting the IV to a larger value has only negligible security benefits. There is a slight advantage in space coverage (hashing 128-bit values into 128 bits yields only something like 68% of the space), but we are talking about fractions of bits here. Commented Oct 23, 2017 at 12:36
• I'm amazed, but I just looked at the bouncy castle implementation and found that they are indeed doing exactly what you described. You made my day, thanks! For a long time I worried about this problem, and it seemed not possible to do it right (multiple clients synchronizing encrypted messages with the cloud). Commented Nov 20, 2017 at 23:00