[Cryptography] AES-256- More NIST-y? paranoia

[Jerry Leichter]

On Oct 7, 2013, at 11:45 AM, Arnold Reinhold <agr at me.com> wrote:
> If we are going to always use a construction like AES(KDF(key)), as Nico suggests, why not go further and use a KDF with variable length output like Keccak to replace the AES key schedule? And instead of making provisions to drop in a different cipher should a weakness be discovered in AES,  make the number of AES (and maybe KDF) rounds a negotiated parameter.  Given that x86 and ARM now have AES round instructions, other cipher algorithms are unlikely to catch up in performance in the foreseeable future, even with an higher AES round count. Increasing round count is effortless compared to deploying a new cipher algorithm, even if provision is made the protocol. Dropping such provisions (at least in new designs) simplifies everything and simplicity is good for security.
That's a really nice idea.  It has a non-obvious advantage:  Suppose the AES round instructions (or the round key computations instructions) have been "spiked" to leak information in some non-obvious way - e.g., they cause a power glitch that someone with the knowledge of what to look for can use to read of some of the key bits.  The round key computation instructions obviously have direct access to the actual key, while the round computation instructions have access to the round keys, and with the standard round function, given the round keys it's possible to determine the actual key.

If, on the other hand, you use a cryptographically secure transformation from key to round key, and avoid the built-in round key instructions entirely; and you use CTR mode, so that the round computation instructions never see the actual data; then AES round computation functions have nothing useful to leak (unless they are leaking all their output, which would require a huge data rate and would be easily noticed).  This also means that even if the round instructions are implemented in software which allows for side-channel attacks (i.e., it uses an optimized table instruction against which cache attacks work), there's no useful data to *be* leaked.

So this is a mode for safely using possibly rigged hardware.  (Of course there are many other ways the hardware could be rigged to work against you.  But with their intended use, hardware encryption instructions have a huge target painted on them.)

Of course, Keccak itself, in this mode, would have access to the real key.  However, it would at least for now be implemented in software, and it's designed to be implementable without exposing side-channel attacks.

There are two questions that need to be looked at:

1.  Is AES used with (essentially) random round keys secure?  At what level of security?  One would think so, but this needs to be looked at carefully.
2.  Is the performance acceptable?

BTW, some of the other SHA-3 proposals use the AES round transformation as a primitive, so could also potentially be used in generating a secure round key schedule.  That might (or might not) put security-critical information back into the hardware instructions.

If Keccak becomes the standard, we can expect to see a hardware Keccak-f implementation (the inner transformation that is the basis of each Keeccak round) at some point.  Could that be used in a way that doesn't give it the ability to leak critical information?
                                                        -- Jerry