[Cryptography] ratcheting DH strengths over time

[Jerry Leichter]

> Oh, and an addendum: you can up your DH primes all you like, but if
> the key exchange is then driving RC4 or 1DES for the actual
> communications or what have you, you lose. Cryptographic protocols
> like TLS depend on several moving parts -- key exchange, hashes,
> symmetric ciphers, etc.
> 
> The NSA's policy seems to be that you set all of these to be more or
> less of equivalent security and there's no point in having a steel
> wall with a paper door, and that seems to make some sense. Keep all
> your parts in balance....

> So, how does one automatically upgrade not only the strength of the
> asymmetric subsystem but also the symmetric ciphers and hashes in use?
> I'm not sure one does -- so perhaps the auto upgrade point is
> moot.
> 
> Or, perhaps there's a cleverer idea possible here that I'm not seeing.
I think you're comparing unlike things, because our knowledge of cryptography is in a funny state.

Our asymmetric cryptography is based on well-understood mathematical problems, and there are well-understood, way-better-than-brute-force, attacks on them.  Security for these algorithms is based on (a) assuming no significantly better mathematical attacks will arise; (b) setting the key sizes and other parameters so large that even the best known algorithms are too slow to be practical in some specific time frame.  But the growth rate for these attacks is not very fast - certainly not relative to the growth rate of encryption and decryption - so over time any fixed size key will become vulnerable.

In this case, increasing the key size makes sense.

Our symmetric cryptography, on the other hand, is based on algorithms that we believe cannot be attacked using anything significantly better than a brute-force attack.  In this case, even 128-bit keys are pretty much beyond, not just current technical capabilities, but any technical capabilities we can reasonably imagine.  256-bit keys are immune to any brute-force-attack that's even vaguely consistent with the physics we know.  Meanwhile, encryption and decryption with 256-bit keys is very fast on existing hardware.

If there's an attack on our symmetric crypto, it will be through some kind of surprising breakthrough.  This hasn't happened with any fielded encryption algorithm in modern memory, though it *has* happened, repeatedly, for one-way functions.

Given this reality, there's really nothing to be gained by increasing key sizes, or any other security parameter, for symmetric crypto and similar algorithms.  It's either a waste of effort since the current key sizes are already forever out of reach; or useless against an attack against the algorithm itself.

We could certainly put DH or RSA or any of the ECC algorithms into a similar state by choosing very large security parameters - e.g., 1-Mbit keys.  Unfortunately, we can't do that because it would put actual *use* of the algorithms out of practical reach.
                                                        -- Jerry