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?


For each encryption generate 16 bytes random salt (16-BYTES-RANDOM).
TMP-AES-16-BYTES-KEY = HKDF-EXPAND-SHA1(STATIC-AES-KEY-16-BYTES | 16-BYTES-RANDOM, 16)
Write in message first plain 16 bytes generated random.
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.
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.