Randomly shuffle a larger key based on the IV to make the private key unique?

Question

Suppose you have a larger secret key than you need, e.g. 512 bits for a 128 bit symmetric encryption algorithm. For something like AES-GCM the IV is random, unique, and public. So both Alice and Bob could use the IV to randomly shuffle their larger shared secret key to produce a unique encryption key for the message.

It would be mathematically very unlikely for IV and thus for the key to ever be repeated between messages. Wouldn't that make any encryption algorithm more secure? If you took a 512bit key and randomly choose 16 bytes without replacement, you have (64−16)!/64!​= 48!/64!​ = 1.0221346459144×10^28 or about 2^93 unique permutations. So practically speaking, both the IV and the secret key would be unique for every message.

That should be more secure right? Not that it matters that much, because it was already secure. But, it would seem to me that the benefit would be that if you were somehow able to break one message (e.g. with a known plaintext attack) you don't automatically break any others. I know it's usually a bad idea to get creative with crypto, but this does seem interesting to me.

Answer 1

This doesn't make a lot of sense.

On the one hand, you operate under the assumption that AES is so fundamentally broken that it's practically possible to retrieve the key from ciphertexts. There isn't any publicly known attack that even comes close to this. If there was, this would be world news. Of course individual implementations can have issues (e.g., side channel vulnerabilities), but this is fixed by switching to a correct implementation, not by modifying AES.

On the other hand, your proposed solution would be completely inadequate if AES really was fundamentally broken. All you're doing is hide a few bytes of your “master key”. If an attacker can practically break AES, they may not even care about the “master key” -- depending on how difficult the hypothetical attack is. And even if they need the “master key” to save work, each ciphertext in your model leaks a large portion of it (up to 1/4), so the security margin is awfully small. The actual solution would be to immediately replace AES.

To summarize, it seems your suggestion is a solution that doesn't work for a problem that doesn't exist.

Of course it is valid to think about safeguards for hypothetical breakthroughs in cryptography and, for example, combine different algorithms. But such schemes need to be professionally designed, because this isn't trivial. And it's still questionable how relevant this is in practice.