Security of AES in CTR mode with fixed nonce (but different key)

Question

If I am using AES in CTR mode and use a unique key every time but the same nonce, is this secure?

If so, does it make a difference if the nonce is public?

Answer 1

Yes, if you use a different key for each message, then it's secure, and it's not a problem if you use a public (or fixed) nonce.

One example where this comes up is the Integrated Encryption Scheme, which uses a symmetric system to encrypt the actual message, and which internally generates a key that will be used only for that message. Note that in IES, you'll also need to implement integrity protection as well (e.g. a MAC)

Answer 2

Yes, this is probably safe. If you choose the keys randomly and/or using a secure KDF, with no chance of an attacker being able to directly influence them, I'd even upgrade that "probably" to "definitely" (assuming that AES itself is not broken, of course).

However, it's worth noting that in many common models of nonce-based encryption the attacker is assumed to be able to choose the nonce. If the attacker gets to choose part of the key instead, that potentially opens the cipher to related-key attacks. AES is known to be theoretically vulnerable to such attacks, in the sense that there are known related-key attacks that, while still too slow to carry out in practice, can in theory break AES faster than pure brute force.

So while currently, as far as we know, AES is still practically unbreakable even if the attacker gets to choose arbitrary relations between the keys, that's definitely a known weak point that future attacks might conceivably weaken further. As the old crypto maxim goes, "attacks only get better, not worse." In any case, since related-key attacks are easy enough to avoid by using a good KDF, there's really no excuse to design a system that could be vulnerable to them.