Increasing number of rounds in AES

AES-128 requires 10 rounds ( AES Description, Wikipedia )

However Bruce Schneier has recommended AES-128 use 16 rounds ( Schneier on Security: New Attack on AES )

Could that be implemented as two full encryptions of AES-128? That is:

AES_128_ENCRYPT(key, data, mode); // 10 rounds of normal AES 128
AES_128(key, AES_128(key, data, mode), mode); // would this be 20 rounds of AES?


Would this need to be with two separate keys like in Triple DES ( Triple DES, wikipedia )?

-

The de-facto answer to any question about increasing the AES rounds is that as yet there doesn't appear to be any need, and any time you do so involves implementing at least some of it in custom code, which is inherently risky.

As far as running AES twice goes, have a look at Meet in the Middle (MITM) attacks. I don't know how relevant these will be to your target scenario given the space requirements, but in general they mean that running two encryptions is only twice as good as running one.

Throughout this post I'll refer to AES-128 as simply AES.

You certainly wouldn't be able to use the scheme you describe with the same key as this would not lead to 20 rounds of AES, because the key schedule would be incorrect for the second half of the rounds. Moreover, since the last round of AES is not the same as the intermediate rounds, you would end up with

[pre-whitening + 9 rounds + 1 last round ] + [ pre-whitening + 9 rounds + 1 last round]

If you were to extract the final values from the key schedule, you could use these to generate the next iteration of the key schedule. Using these two sets of data and your own implementation of AddRoundKey, you could remove the final round key, complete the final round into a full intermediary round and invert the pre-whitening that was about to occur (since pre-whitening just involves xoring in the next round of the keyschedule). However, by the point you've done this you've basically ended up implementing most of the internals of AES yourself, and in a very messy way. Worse still, any home-brew AES implementation is likely to have significant side-channel weaknesses, so should be avoided.

The following question (suggested by SE to the right) might help with understanding the key schedule side: how can i add more rounds to aes

-
Why would the key schedule be incorrect? (assuming that the key is given else where and AES_128 just does encryption). Also isn't the first round of AES different as well so it would be 2 initial rounds + 16 middle rounds + 2 last rounds? – Zimm3r Oct 17 '13 at 15:37
The key schedule for your 20 round variant would require you to initialise the second AES with the final values of the key schedule from the first implementation, rather than the original key. – figlesquidge Oct 17 '13 at 15:45
I guess the main point I was targetting was providing a response to the question "AES_128(key, AES_128(key, data, mode), mode); // would this be 20 rounds of AES?" – figlesquidge Oct 17 '13 at 15:47
What if it was the same key? You could never tell if it was right until you did the full two decryption as the first decryption would still be pseudo random noise wouldn't it? Also couldn't you just use a 512 bit key split in two? – Zimm3r Oct 17 '13 at 15:47
These things could be done (and I can't comment on the effectiveness of doing so), but at that point you're not describing using AES with 20 rounds at all - you're describing using AES twice with two keys that may or may not be the same. – figlesquidge Oct 17 '13 at 15:49

To answer your last question first, Triple DES does not need a longer key because it has more rounds than plain DES — rather, Triple DES needs more rounds than plain DES because it has a longer key (and because it aims to offer a security level appropriate for that key length).

To be more specific, plain DES only has a 56-bit key, meaning that it can be broken by brute force using only $2^{56}$ encryptions. That was fine back in the 1970s when it was designed, but by the late 1990s it had become demonstrably inadequate. Triple DES (or 3DES for short) was designed to fix this issue by doubling the key length to 112 bits, and so increasing the effort needed for a brute force attack to $2^{112}$ encryptions — not merely twice as much, but $2^{56} \approx 7.2 \times 10^{16}$ times as much as plain DES. This is still considered far beyond the reach of any computing power even conceivably available today or in the foreseeable future.

However, for the increased key length of 3DES to actually be useful, there could not be any obvious "short cuts" that would allow it to be broken faster than by brute force. Specifically, this is the reason why 3DES needs three DES encryptions, rather than only two: a naïve "cascade encryption" using plain DES with two different keys, as in:

$$C = {\rm DES}( {\rm DES}( P, K_1 ), K_2 )$$

would be vulnerable to a meet-in-the-middle attack requiring only about $2 \times 2^{56} = 2^{57}$ en/decryptions. Basically, given a known plaintext–ciphertext pair $(P,C)$, you first encrypt $P$ using plain DES with all the $2^{56}$ possible subkeys $K_1$ and store the results in a database. Then you decrypt the ciphertext $C$, again using plain DES, with all the possible subkeys $K_2$, and look the results up in the database to see which one matches one of the stored intermediate values. This gives you the two halves of the correct key (and possibly a few false positives, which you can filter out by trying them on further known plaintext–ciphertext pairs).

Triple DES avoids this attack by encrypting the output of the second DES encryption (actually, a decryption, but that's an irrelevant detail here) one more time, again using the first key:

$$C = \rm{3DES}( P, K_1 \mathbin{||} K_2 ) = {\rm DES}( {\rm DES}^{-1}( {\rm DES}( P, K_1 ), K_2 ), K_1 )$$

This defeats the attack, since there's no "halfway point" that you could reach from one direction knowing only $K_1$ and from the other direction knowing only $K_2$.

So, what about your suggestion of strengthening AES by encrypting the plaintext twice using the same key? Well, as correctly noted by user2883315, it won't give the same results as internally extending AES to twice as many rounds, since the key schedule and other details won't match.

Would it be any less secure, though? That's harder to say. It won't be vulnerable to the meet-in-the-middle attacks described above, since you're not even trying to increase the strength of AES beyond its normal key length.

However, the fact that your "double AES" consists simply of iterating the same encryption function twice might make it vulnerable to slide attacks. Honestly, though, even after reading the Biryukov & Wagner 2000 paper, I still can't say I understand these attacks well enough to say whether they might apply here or not. In particular, without a very serious weakness in AES, I'm not even sure how one might identify a slide pair for double AES, let alone exploit one.

Still, I'd be more comfortable if the two encryption keys were not the same. You could derive one of them from the other (or both from some master key) somehow, but I'm not sure what would be the optimal way to get a good speed / security tradeoff.

Obviously, using a standard KDF to expand a master key to twice its original size would work and should be secure, but might be considered too slow or complicated for some applications (although, in those cases, simply storing the pre-expanded key might be a viable alternative).

Conversely, simply XORing one of the keys with a constant (e.g. 0x555555...55) to obtain the other one would be fast and should be OK, as long as AES is secure enough — but, given that the whole point of the exercise is to strengthen AES against future attacks, this might not be a safe assumption.

-
As to the keys I know TrueCrypt when it offers to encrpyt with multiple ciphers just takes a PBKDF to generate say 768 bits and splits it up to three 256 bit keys – Zimm3r Oct 17 '13 at 19:13