Does Size Matter? AES 128-Bit Encryption is (Probably) Good Enough

Recently, I was asked to opine on whether AES 128-bit encryption was adequate, or if the customer’s cryptography standard should require 256-bit operation. 

Source: Wikipedia – “SubBytes – one of the four rounds of AES”

Background

I’m not a deep algorithm expert, but will share a bit of research with you. NIST in 2001 selected three members of the Rijndael algorithm family – each with a block size of 128 bits, but three different key lengths: 128, 192 and 256 bits – to become the Advanced Encryption Standard (AES). Thus, AES is based on the Rijndael encryption method for replacing, changing and performing xor operations on bytes of plaintext and it remains the de facto global symmetric key encryption standard.

AES uses a combination of substitution and permutation against a 4×4 matrix of bytes. It’s designed to run fast in both software and hardware; in fact CPU vendors have optimized chipsets for it. The key size used for an AES cipher specifies the number of plaintext transformation rounds where the algorithm uses 10 cycles of repetition for 128-bit keys, 12 for 192-bit keys, 14 for 256-bit keys. After an initial round where each byte of plaintext is combined with a block of the round key using bitwise xor, the 10, 12 or 14 cycles of repetition are performed. Each cycle consists of four steps called SubBytes, ShiftRows, MixColumns and AddRoundKey. 

It’s also interesting to note that for the purposes of enterprise symmetric key size standard selection, the 128 versus 256-bit question can be abstracted to cover multiple standards. In general, key sizes for other algorithms that, like AES, have no known computational short cuts can also be described as requiring “128 bits of worth of work” or “256 bits of work.”

Does Size Matter?

I picked up the following from a learned discussions on Security Stack Exchange:

“[U.S. army] regulations…called for three distinct levels [based on pre-computer experience that most algorithms could be broken and the most robust were very slow and hard to use]. Their designers just assumed that the lower level were necessarily weak in some way, but weakness was not mandatory. So the NIST decided to formally follow the regulations (ask for three key sizes) but to also do the smart thing (the lowest level had to be unbreakable with foreseeable technology). 128 bits are quite sufficient for security…. Therefore AES accepts 256-bit keys because of bureaucratic lassitude: it was easier to demand something slightly nonsensical (a key size overkill) than to amend military regulations.”

Attacks on AES

Pursuant to this question, I did some research on cryptanalysis attacks on AES. Some “progress” was made in the 2009 to 2011 time frame, but the conclusion is that these attempts still fall far short of a practical, computationally feasible method to “crack” AES. For those interested, here are the deep references:

• Related-key Cryptanalysis of the Full AES-192 and AES-256
• Biclique Cryptanalysis of the Full AES – Microsoft Research

I can’t find anything more recent, which is very favorable for continued longevity of AES. But of course more breakthroughs could come in the future and quantum cryptography looms over the industry like a sword of Damocles…

The Devil is in the Details

I searched for the latest recommendation from Bruce Schneier and found that from looking at the same cryptanalysis research, he research a surprising conclusion: size does matter, but not in the way that you’d think! Schneier by the way, wrote a seminal book on cryptography years ago and recently co-authored “Cryptography Engineering: Design Principles and Practical Applications.” 

From Schneier’s blog: “This is what I wrote about AES in 2009. I still agree with my advice…Cryptography is all about safety margins. If you can break n rounds of a cipher, you design it with 2n or 3n rounds. What we’re learning is that the safety margin of AES is much less than previously believed. And while there is no reason to scrap AES in favor of another algorithm, NST should increase the number of rounds of all three AES variants. At this point, I suggest AES-128 at 16 rounds, AES-192 at 20 rounds, and AES-256 at 28 rounds. Or maybe even more; we don’t want to be revising the standard again and again.

And for new applications I suggest that people don’t use AES-256. AES-128 provides more than enough security margin for the forseeable future. But if you’re already using AES-256, there’s no reason to change.”

Bottom Line

Considering the uncertainty and complexity around drawing any lasting conclusions on algorithm / key size strength, rather than reflexively picking a larger key size, it may be as important or more important to emphasize:

• Flexibility in algorithm choices
• The ability to quickly migrate from one algorithm / key size set to another
• Double-encrypt the most sensitive data to using diverse algorithms and/or tokenization as a second method

Concerning double encryption, it may be more practical than you think. In a recent post called Is There a Gold Standard for Enterprise Encryption I delve into the tradeoffs between encrypting at lower or higher levels of the IT stack. The post explains that whereas application or database encryption support high levels of granularity and separation of duty, storage volume encryption provides pervasive or broad encryption coverage. Storage volume encryption is actually more effective against physical or virtual infrastructure level attacks that sweep up swap files and backups as well as authoritative data, but is completely ineffective against anyone with system administrator or operator credentials.

Double encryption isn’t as crazy as it seems 🙂

Additional compensating controls – especially data collection minimization, multi-factor authentication, separation of duty, continuous automated monitoring and frequent control efficacy audits – are also indicated.