Re: [Proposal] Table-level Transparent Data Encryption (TDE) and KeyManagement Service (KMS)

>> I vote for AES 256 rather than 128.
>
> Why?  This page seems to think 128 is sufficient:
>
>         https://crypto.stackexchange.com/questions/20/what-are-the-practical-differences-between-256-bit-192-bit-and-128-bit-aes-enc
>
>         For practical purposes, 128-bit keys are sufficient to ensure security.
>         The larger key sizes exist mostly to satisfy some US military
>         regulations which call for the existence of several distinct "security
>         levels", regardless of whether breaking the lowest level is already far
>         beyond existing technology.

After researching AES key sizes a bit more my vote is (surprisingly?) for AES-128.  My reasoning is about security, I did not consider performance impacts in my decision.

The purpose of longer keys over shorter keys is about ensuring brute-force attacks are prohibitively expensive.  Finding a flaw in the algorithm is the goal of cryptanalysis.  Brute force attacks are only advanced by increasing computing power.

"The security of a symmetric cryptosystem is a function of two things:  the strength of the algorithm and the length of the key.  The former is more important... " [1] (pg 151)

"The algorithm must be so secure that there is no better way to break it than with a brute-force attack." [1] (pg 152)

Finally, a stated recommendation on key size:  "Insist on at least 112-bit keys." [1] (pg 153)  Schneier also mentions in that section that breaking an 80-bit key (brute force) is likely not realistic for another 30 years.  ETA: 2045 based on dated published.  Brute forcing a 128 bit key is much further in the future.

Knowing the algorithm is the important part, onto the strength of the algorithm.  The abstract from [2] states:

"In the case of AES-128, there is no known attack which is faster than the 2^128 complexity of exhaustive search. However, AES-192 and AES-256 were recently shown to be breakable by attacks which require 2^176 and 2^119 time, respectively."

This shows that both AES-128 (2^128) and AES-192 (2^176) both provide more protection in this case than the AES-256 algorithm provides (2^119).  This may be surprising because all AES encryption does not work the same way, even though it's "all AES."  Again from [2]:

"The key schedules of AES-128 and AES-192 are slightly different, since they have to apply more mixing operations to the shorter key in order to produce the slightly smaller number of subkeys for the various rounds. This small difference in the key schedules plays a major role in making AES-256 more vulnerable to our attacks, in spite of its longer key and supposedly higher security."

It appears the required key mixing that occurs with shorter key lengths is actually a strength of the underlying algorithm, and simplifying the key mixing is bad.  They go on to restate this in a more succinct and damning way:  "... it clearly indicates that this part of the design of AES-256 is seriously flawed."

Schneier also mentions how small changes can have big impacts on the security: "strong cryptosystems, with a couple of minor changes, can become weak." [1] (pg 152)

[1] Schneier, B. (2015). Applied Cryptography: Protocols, Algorithms and Source Code in C (20th Anniversary ed.). John Wiley & Sons.

[2] Biryukov, A., Dunkelman, O., Keller, N., Khovratovich, D., & Shamir, A. (2009). Key Recovery Attacks of Practical Complexity on AES-256 Variants with up to 10 Rounds. Retreived from https://eprint.iacr.org/2009/374.pdf


Ryan Lambert
RustProof Labs