After 20 years of AES, what are the retrospective changes that should have been made?

I realize that this could be very opinion based, but I feel that there should be some solid information on AES at this point that could be referenced. After 20 years, I expect that there should be a "woulda, coulda, shoulda" list somewhere. For instance, I suspect that one could have gotten away with two fewer rounds, which would still have an acceptable security margin, but would this increase the speed of the cipher significantly.

Is there a comprehensive retrospective on AES in literature now that it has been used for 20 years?

• 256-bit block size support, 512-bit key size support, and 32-rounds (yeah that is overkill make it 16) Jan 18 '21 at 13:52
• @kelalaka Why 512 bit key support? 256 bit security against QC? The snake oill papers would have to go all the way up to 1024 bit AES (actually, they already do sometimes)! Jan 18 '21 at 14:49
• @MaartenBodewes support doesn't mean that we need that immediately, yes Grover is optimal ( that is one way to attack). This is a bit conservative plan that should have been set. Not like snake oil. Jan 18 '21 at 14:54

Nobody seems to need a 192 bit version, we can do fine with just AES-128 and AES-256. Having a key that's 1.5 times the block size is a nuisance (or 0.75 times the block size if the block size is doubled).

The key schedules of AES-192 and AES-256 are vulnerable to attack; we could do with a better key schedule where even these attacks are avoided. They don't have much influence when the cipher is used for confidentiality, but we could do without those attacks regardless.

And while we're expanding the block size and fixing vulnerabilities to the key schedule anyway, we might as well make it suitable as underlying cipher for a cryptographic hash function and make it a tweakable block cipher.

• Now if we'd just do away with the tables, simplify the rounds and use more of them we've got Threefish :P Jan 18 '21 at 14:39
• Threefish is neat but it wasn't really intended to be a useful block cipher. It was more an experiment showing the cryptographic properties of its core design. Jan 19 '21 at 1:23
• @forest Citation needed. I mean, they did use it in the Skein SHA-3 proposal, and it was one of the final SHA-3 candidates. Isn't that serious enough? Sure, at first it is foremost meant for Skein, but there is no reason that they would not extend it's purpose afterwards like they did with Keccak - the sponge. Jan 19 '21 at 8:08
• The first answer here: security.stackexchange.com/questions/14068/… actually gives the (mostly historic) reasons why three levels were a requirement.
– Tom
Jan 19 '21 at 12:29
• @MaartenBodewes What I meant was that it was not intended as a drop-in replacement for other block ciphers and was instead meant as a cryptographic primitive for a hash function, not that it's insecure or poorly designed. Having a 1024-bit block is not a "useful feature" for a block cipher that is to be used for simple encryption where 128 or 256 is enough. Jan 21 '21 at 1:52

I don't think that saving rounds to increase speed is necessary. On machines with AES-NI (which is most today), it takes less time to encrypt in AES than it does to read from memory. There are rare cases where the time to encrypt is too slow.

One change that I think should have been made is to also standardize a larger block size. Although 128 bits seems very big, in a standard CTR/GCM mode of operation with a 96-bit IV, you can only encrypt $$2^{32}$$ different messages safely. There are other solutions, but a larger block size would be a simple and better long term solution.

• The issue(?) of the low number of rounds is why I asked a question about Rijndael's choice of round numbers. The answer seems to be that the designers really wanted to squeeze out performance by reducing security margin for smaller key sizes. Jan 18 '21 at 22:41
• Adding to what forest said, it’s also important to put this in the context of the hardware in use at the time. Yeah, AES encryption runs at memory bandwidth these days on modern hardware from 22 years after it was published, but at the time it originated, it was painfully slow. Had Rijmaen and Daemen not made the compromises they did to improve performance, I strongly suspect that it would be nowhere near as ubiquitous today (encryption and decryption performance are very important for a lot of the things AES is used for these days, which is why stuff like AES-NI exists). Jan 18 '21 at 23:53
• @benrg AES-NI can be used for 256-bit blocks, if my memory of the Intel whitepaper is correct. Jan 19 '21 at 0:46

A serious issues with AES is its sensitivity to timing and cache side-channel attacks in many portable pure-software implementations, due to the hard-to-avoid table lookups (exceptions: bitsliced implementation, CPUs without a data cache, CPUs with AES-NI, some slow code). An ARX cipher (in the sense of using only additions, rotations/shifts, and XOR; e.g Serpent) would avoid this cleanly, while remaining compatible with all CPUs. I think (in retrospect) it would have been a better choice.

Having a 256-bit block would be nice, and simplify a safe choice of IV.

• I agree on the issue but IMHO the solution is smaller, lower degree sboxes, not ARX. Something that can be computable in sliced fashion even for 1 block. That would allow also lower cost SCA protected implementation. ARX are terrible for masking. Jan 18 '21 at 15:26
• @Ruggero: a lot of crypto runs on standard PCs/servers, where there are legions of cross-process side channel leakages attacks due to caches, exploitable by software, including across virtualization it seems. ARX neatly avoids this whole class of SCA. I agree that things are different when we put (D)PDA in the mix, and that ARX may even be harder to protect. But Smart Cards, TPMs, SEs, HSMs and the like are quantitatively marginal, and I guess that there would be (likely is) hardware solutions.
– fgrieu
Jan 18 '21 at 17:59
• Serpent is not an ARX cipher. It is a bitsliced substitution permutation network. Jan 18 '21 at 22:43

All AES candidates due to specification were Pseudo-Random Permutation (PRP), however, today we don't need a PRP. We can live with a Pseudo-Random Function (PRF) since the CTR mode is designed for PRFs. CTR modes don't need the reverse operation as CBC. This can reduce the area/time cost of implementations.

As an example; the ChaCha is a PRF and turned into a cipher with the CTR mode. It is based on add-rotate-XOR (ARX) operations - 32-bit addition, bitwise addition (XOR), and rotation operations.

All of the cipher suites in the TLS 1.3 (AES-GCM, AES-CCM, and ChaCha20) use CTR mode. The bonus; no padding oracles.

Using AES (PRP) in GCM and CTR has a long message distinguisher and therefore we need to restrict the number of encryption blocks due to the PRP-PRF switching lemma.

So I can say, a PRF with 256/512-bits block size and 128/256/512 key and 128/256 IV sizes. With this, we can live without IV collisions and long message problems. Plus, 32/64 bit CPU friendly design.

Bonuses;

• "We can live with a PRF" is misleading. Building PRFs from scratch seems harder than building PRPs. The mentioned Chacha is obtained from a permutation P via the feed forward: $x \mapsto x\oplus P(x)$, and this has bound $2^{n/2}$. What saves it is $n=512$. Jan 19 '21 at 19:52
• @Fractalic that is true, however, we still have a PRF candidate. Consider that there was a competition for PRF based encryption and where will be the research. Besides, I don't see that is misleading, it is an answer to woulda, coulda, shoulda Jan 19 '21 at 19:59