[Cryptography] We need a new encryption algorithm competition.

[Jerry Leichter]

On Mar 16, 2014, at 8:40 AM, Phillip Hallam-Baker <hallam at gmail.com> wrote:
> ...Right now we have a fairly well established mandatory to implement set:
> 
> AES-128, SHA2-256, HMAC-SHA2-256, [DH & RSA-Encrypt], RSA-Signature
> 
> ...Although that set is pretty well established it is starting to look a little on the old side. We have a consensus replacement for SHA2 but right now we don't have solid consensus on replacements for anything else.
> 
> It seems that we are pretty close to a consensus on the use of EC as the next generation digital signature algorithm. But there are a few more degrees of freedom there which need to be nailed down. There is the choice of curve in particular which is now subject to a lot of possibly justified paranoia.
> 
> So we can hypothesize a backup set of algorithms:
> 
> ??, SHA3, HMAC-SHA3 / ??-CCM, ECDH, ECDSA
> 
> Spot the problem? We currently have no backup for an encryption algorithm.
> 
> We really do need a backup for that slot and I don't think we can just take one of the AES runners up. The criteria for a reserve algorithm are not the same as for the default. Since the idea is that you can depend on the reserve algorithm even if the default is broken, it has to be tuned for security rather than performance.
I don't buy that contention.  It certainly doesn't describe the relationship of EC to RSA - I haven't heard any claims that EC is inherently more secure than RSA (in fact one might argue that the underlying hard problem in EC is less well-understood than the one in RSA); rather, the claim is that RSA is becoming too slow to be practical to retain adequate security in the face of advances in attacks, while EC gets by with much smaller keys (hence gets much better performance) at the required level of security.

SHA-3 seems comparable to SHA-2 in performance, even though we've had much less time to come up with clever optimizations.  (Of course, if you have hardware help, the story is different.)

A fallback for AES with significantly worse performance simply wouldn't be used.  People put as much hardware as needed out there to solve a problem; they don't add a whole bunch extra "just in case".  There might be specialized areas where higher security would trump performance, but as a *standard*, intended to be widely or even universally deployed, an algorithm that required a significant performance hit would have a really tough time getting accepted.  Note that, again, the comparison will shortly be, in some sense, rigged:  An ever-growing percentage of fielded machines will have hardware support for AES, making reaching even approximate parity using a pure software implementation of some other algorithm extremely difficult to achieve.

This latter issue raises an interesting question:  Give that you have fast hardware primitives for the SHA-2 and AES round functions, can you use them to construct different algorithms that you can reasonably hope will be secure against attacks that seriously weaken SHA-2 and AES?  Here's one example (which I make *no* claims about):  All the attacks we know of against iterative block ciphers are limited in the number of rounds that they can attack.  Given a decent round function and a decent key scheduling algorithm, with enough rounds the construction appears secure.  So suppose we added a couple of extra rounds to AES - relatively cheap given that the round function is in hardware.  To extend the key schedule, stretch the original key by applying the fast hardware SHA-2 to it.

                                                        -- Jerry