Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

AES has several different variants:

  • AES-128
  • AES-192
  • AES-256

But why would someone prefer use one over another?

share|improve this question
    
You would use AES 256 to protect against quantum brute force attacks; Grover's algorithm speeds up a brute force attack by the square root of n (see en.wikipedia.org/wiki/Grover's_algorithm) –  Elliott Jul 14 '11 at 20:18
4  
As another side note, in my opinion there are a few reasons why an AES implementation could be cracked. Bad protocols (allowing padding oracle attacks, for instance), (time based) side channel attacks and bad practices such as forgetting to use a different IV vector for each CBC encrypt. Key size has nothing to do with any of these attack vectors. –  Maarten Bodewes - owlstead Jan 2 '12 at 17:23

4 Answers 4

up vote 34 down vote accepted

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.

The larger key sizes imply some CPU overhead (+20% for a 192-bit key, +40% for a 256-bit key: internally, the AES is a sequence of "rounds" and the AES standard says that there shall be 10, 12 or 14 rounds, for a 128-bit, 192-bit or 256-bit key, respectively). So there is some rational reason not to use a larger than necessary key.

A larger key size also resists better to large quantum computer attacks: Using Grover's algorithm, a brute-force attack on any k-bit key block cipher would only take $O(2^{k/2})$ steps, so a 256-bit key would still give 128-bit security, while a 128-bit key could be cracked in 2^64 operations, which is doable. But as far as I know, the threat of QC was an ulterior rationalization; also, it does not explain the 192-bit key size. (And quantum computers of this size are not yet in sight for the next some years.)

share|improve this answer
    
It should also be noted that 128-bit AES has had a lot more scrutiny than 192- and 256-bit AES. –  Fixee Oct 15 '11 at 0:15
    
Is there a technical reason why the 192/256 bit implementations have more rounds, or is it just the same "more is better" logic behind the longer key lengths? –  Dan Neely Feb 3 '12 at 21:35
8  
@DanNeely: a block cipher with 256-bit keys is supposed to offer resistance up to work factor $2^{256}$; there should not exist any (theoretical) attack which would be less expensive. An attack with cost $2^{200}$ is considered to be a "break" for a block cipher with a 256-bit key; but not for a block cipher with a 128-bit key, for which we "only" require resistance up to $2^{128}$ operations. The extra rounds help in obtaining that level of resistance. –  Thomas Pornin Feb 6 '12 at 23:49

The actual encryption algorithm is almost the same between all variants of AES. They all take a 128-bit block and apply a sequence of identical "rounds", each of which consists of some linear and non-linear shuffling steps. Between the rounds, a round key is applied (by XOR), also before the first and after the last round.

The differences are:

  • The longer key sizes use more rounds: AES-128 uses 10 rounds, AES-192 uses 12 rounds and AES-256 uses 14 rounds.
  • The derivation of the round keys looks a bit different.

For AES-128, we need 11 round keys, each of which consisting of 128 bits, i.e. 4 32-bit columns. The original cipher key consists of 128 bits (i.e. 4 columns). Call these $k_0$, $k_1$, $k_2$ and $k_3$. The key expansion algorithm now expands these to $k_0$ to $k_{43}$ (so we get 44 columns in total).

The key expansion works in a way that $k_i$ only depends directly on $k_{i-1}$ and $k_{i -N_k}$ (where $N_k$ is the number of columns in the key, i.e. 4 for AES-128). In most cases it is a simple $\oplus$, but after each $N_k$ key columns, a non-linear function $f_i$ is applied.

                              ┏━━━┓
   k_0    k_1    k_2    k_3 ─→┃f_1┃─╮
    │      │      │      │    ┗━━━┛ │
 ╭──│──────│──────│──────│──────────╯
 │  ↓      ↓      ↓      ↓
 ╰─→⊕   ╭─→⊕   ╭─→⊕   ╭─→⊕
    │   │  │   │  │   │  │
    ↓   │  ↓   │  ↓   │  ↓    ┏━━━┓
   k_4 ─╯ k_5 ─╯ k_6 ─╯ k_7 ─→┃f_2┃─╮
    │      │      │      │    ┗━━━┛ │
 ╭──│──────│──────│──────│──────────╯
 │  ↓      ↓      ↓      ↓
 ╰─→⊕   ╭─→⊕   ╭─→⊕   ╭─→⊕
    │   │  │   │  │   │  │
    ↓   │  ↓   │  ↓   │  ↓     ┏━━━┓
   k_8 ─╯ k_9 ─╯ k_10 ╯ k_11 ─→┃f_3┃─╮
    │      │      │      │     ┗━━━┛ │
 ╭──│──────│──────│──────│───────────╯
 │  ↓      ↓      ↓      ↓
.......................................
 │  ↓      ↓      ↓      ↓
 ╰─→⊕   ╭─→⊕   ╭─→⊕   ╭─→⊕
    │   │  │   │  │   │  │
    ↓   │  ↓   │  ↓   │  ↓
   k_40 ╯ k_41 ╯ k_42 ╯ k_43

The functions $f_i$ are nonlinear functions build from the AES S-box (applied on each byte separately), a rotation by one byte, and an XOR with a round constant depending on $i$ (this is the element of $GF(2^8)$ corresponding to $x^{i-1}$, but there also is a table in the standard).

Then the key selection algorithm simply takes $k_0 \dots k_3$ as the first round key, $k_4\dots k_7$ as the second one, until $k_{40} \dots k_{43}$ as the last one.

AES-192 looks almost the same, but with six columns in parallel. As we need 13 round keys (=52 key columns), this will be done until $k_{51}$ (i.e. 8 full rows and four keys in the ninth row).

For AES-256 (and all variants of Rijndael with more than 192 bits of key), there is an additional non-linear transformation after the fourth column:

                                                             ┏━━━┓
  k_0    k_1    k_2    k_3       k_4    k_5    k_6    k_7 ──→┃f_1┃─╮
   │      │      │      │         │      │      │      │     ┗━━━┛ │
╭──│──────│──────│──────│─────────│──────│──────│──────│───────────╯
│  ↓      ↓      ↓      ↓     ┏━┓ ↓      ↓      ↓      ↓
╰─→⊕   ╭─→⊕   ╭─→⊕   ╭─→⊕   ╭→┃g┃→⊕   ╭─→⊕   ╭─→⊕   ╭─→⊕
   │   │  │   │  │   │  │   │ ┗━┛ │   │  │   │  │   │  │
   ↓   │  ↓   │  ↓   │  ↓   │     ↓   │  ↓   │  ↓   │  ↓     ┏━━━┓
  k_8 ─╯ k_9 ─╯ k_10 ╯ k_11 ╯    k_12 ╯ k_13 ╯ k_14 ╯ k_15 ─→┃f_2┃─╮
   │      │      │      │         │      │      │      │     ┗━━━┛ │
╭──│──────│──────│──────│─────────│──────│──────│──────│───────────╯
│  ↓      ↓      ↓      ↓     ┏━┓ ↓      ↓      ↓      ↓
╰─→⊕   ╭─→⊕   ╭─→⊕   ╭─→⊕   ╭→┃g┃→⊕   ╭─→⊕   ╭─→⊕   ╭─→⊕
   │   │  │   │  │   │  │   │ ┗━┛ │   │  │   │  │   │  │
   ↓   │  ↓   │  ↓   │  ↓   │     ↓   │  ↓   │  ↓   │  ↓     ┏━━━┓
  k_16 ╯ k_17 ╯ k_18 ╯ k_19 ╯    k_20 ╯ k_21 ╯ k_22 ╯ k_23 ─→┃f_3┃─╮
   │      │      │      │         │      │      │      │     ┗━━━┛ │
╭──│──────│──────│──────│─────────│──────│──────│──────│───────────╯
│  ↓      ↓      ↓      ↓         ↓      ↓      ↓      ↓
....................................................................
│  ↓      ↓      ↓      ↓     ┏━┓ ↓      ↓      ↓      ↓
╰─→⊕   ╭─→⊕   ╭─→⊕   ╭─→⊕   ╭→┃g┃→⊕   ╭─→⊕   ╭─→⊕   ╭─→⊕
   │   │  │   │  │   │  │   │ ┗━┛ │   │  │   │  │   │  │
   ↓   │  ↓   │  ↓   │  ↓   │     ↓   │  ↓   │  ↓   │  ↓     ┏━━━┓
  k_48 ╯ k_49 ╯ k_50 ╯ k_51 ╯    k_52 ╯ k_53 ╯ k_54 ╯ k_55 ─→┃f_7┃─╮
   │      │      │      │                                    ┗━━━┛ │
╭──│──────│──────│──────│──────────────────────────────────────────╯
│  ↓      ↓      ↓      ↓
╰─→⊕   ╭─→⊕   ╭─→⊕   ╭─→⊕
   │   │  │   │  │   │  │
   ↓   │  ↓   │  ↓   │  ↓
  k_56 ╯ k_57 ╯ k_58 ╯ k_59

$g$ is a simpler variant of $f_i$: simply the application of the AES S-box on every byte of the column in parallel (without the rotation or the round constant, thus without an index).

Here we need 15 round keys, i.e. 60 columns, which means to do seven and a half round of key expansion.

(I now did read the word practical in the question, and my post doesn't really apply here ... but there seems to be no better question to post this as an answer, so I still post it here.)

share|improve this answer
2  
Awesome answer. As a "user" (not a professional cryptographer), it's awesome to get more details on the algorithms I'm using everyday. Thanks, Paŭlo. –  Barry Wark Dec 28 '11 at 14:29
    
Came across this today. Very good. The wikipedia article on AES confused me. Under The MixColumns Step they give the a matrix used for multiplication when using a "128-bit key". Thought the mix columns step was the same for all key sizes in AES, but different when the block size changes. Is wikipedia wrong? –  mikeazo Nov 27 '13 at 13:00
1  
@mikeazo Yes, I think it should be "128 bit block" there. (I'm going to edit this now.) –  Paŭlo Ebermann Nov 27 '13 at 20:43
    
Actually, the MixColumns-step is applying the same operation on each column, and the different block size variants of Rijndael only differ in the number of columns, not in the size of those. So the matrix stays the same for all Rijndael (and AES) variants. –  Paŭlo Ebermann Nov 27 '13 at 20:59

The difference is that all known attacks on AES [but see comments] require in the neighborhood of 2length attempts to succeed; that is, there's no better method known than simply trying different keys by brute force.

It follows, then, that a 256 bit key is 2128 times as hard to crack as a 128 bit key.

Of course, computing each encrypted block with 256 bit keys is harder too.

The choice of key length should be based on risk: the damage that will be done if an attack is successful.

share|improve this answer
    
In other words, if cracking will result in Armageddon, use 1024? ;) –  Arlen Beiler Jul 12 '11 at 21:11
6  
Depends on how long you're willing to wait for Armageddon. Seriously, if something is too sensitive for 256 bits, you should worry more about someone proving P=NP, 'cause then all bets are off. –  Charlie Martin Jul 13 '11 at 0:41
    
The choice of key length should also be based on time: for how much time must your data be safe? (taking into account cheaper and more powerful computers as time passes, and eventual future breaks in AES). –  Géal Jul 13 '11 at 7:56
2  
There are actual several attacks against AES, reducing time below 2^length. The attacks can be done in 2^119, 2^176, and 2^200 respectively. schneier.com/blog/archives/2009/07/another_new_aes.html –  samoz Jul 13 '11 at 13:19
3  
@samoz I haven't read the full paper yet, but notice that there are several special conditions on that: fewer rounds than standard, and related keys. Real-world use uses the same number of rounds as the standard and uses unrelated keys from an entropy source. But you're right that there are known attacks on AES variants under special conditions that are less computationally intense. –  Charlie Martin Jul 15 '11 at 14:04

In my opinion, if AES-128 is broken, then it's highly likely that AES-192 and AES-256 will fall too (because these types of attacks are structural and easily extend to longer key-lengths). In fact, we know a successful attack on AES will not be via exhaustive key search on a conventional computer.

There is, however, some chance that key-size will matter in face of a practical attack: suppose the attack takes about the square-root of the size of the key-space (kind of like a collision-attack on hash functions; in fact, quantum computers will give this kind of speedup on exhaustive key search via Grover's Algorithm). Then the square-root of $2^{128}$ becomes practical whereas the square-root of $2^{256}$ remains out of reach. Nevertheless, I guarantee you if AES-128 falls, people will quickly migrate away from the longer-key variants out of worry that they will fall too.

Attacks don't get worse... they only get better.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.