37
$\begingroup$

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?

$\endgroup$
3
  • 8
    $\begingroup$ 256-bit block size support, 512-bit key size support, and 32-rounds (yeah that is overkill make it 16) $\endgroup$ – kelalaka Jan 18 at 13:52
  • 1
    $\begingroup$ @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)! $\endgroup$ – Maarten Bodewes Jan 18 at 14:49
  • 4
    $\begingroup$ @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. $\endgroup$ – kelalaka Jan 18 at 14:54
34
$\begingroup$

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.

$\endgroup$
6
  • 9
    $\begingroup$ Now if we'd just do away with the tables, simplify the rounds and use more of them we've got Threefish :P $\endgroup$ – Maarten Bodewes Jan 18 at 14:39
  • 1
    $\begingroup$ 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. $\endgroup$ – forest Jan 19 at 1:23
  • 2
    $\begingroup$ @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. $\endgroup$ – Maarten Bodewes Jan 19 at 8:08
  • 1
    $\begingroup$ The first answer here: security.stackexchange.com/questions/14068/… actually gives the (mostly historic) reasons why three levels were a requirement. $\endgroup$ – Tom Jan 19 at 12:29
  • $\begingroup$ @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. $\endgroup$ – forest Jan 21 at 1:52
20
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$ – forest Jan 18 at 22:41
  • 2
    $\begingroup$ 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). $\endgroup$ – Austin Hemmelgarn Jan 18 at 23:53
  • $\begingroup$ Rijndael with a larger block size would be slow without extensions to AES-NI. AEZ seems like a nice alternative, and I wish it got more attention (and hence analysis). It's rather complicated, but much simpler if you restrict it to 256-bit blocks (instead of n-bit for any n), and even simpler if you drop the tweakability which is only fair since AES doesn't have it. $\endgroup$ – benrg Jan 19 at 0:18
  • $\begingroup$ Actually, maybe I'm wrong about 256-bit Rijndael needing new instructions. You may be able to just fix up the ShiftRows step with some masks and xors. $\endgroup$ – benrg Jan 19 at 0:32
  • $\begingroup$ @benrg AES-NI can be used for 256-bit blocks, if my memory of the Intel whitepaper is correct. $\endgroup$ – forest Jan 19 at 0:46
15
$\begingroup$

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.

$\endgroup$
3
  • 3
    $\begingroup$ 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. $\endgroup$ – Ruggero Jan 18 at 15:26
  • $\begingroup$ @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. $\endgroup$ – fgrieu Jan 18 at 17:59
  • 3
    $\begingroup$ Serpent is not an ARX cipher. It is a bitsliced substitution permutation network. $\endgroup$ – forest Jan 18 at 22:43
10
$\begingroup$

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;

  • No padding oracles
  • There is no need for a key schedule as in ChaCha
  • No need for a separate decryption circuit.
  • CPU friendly.
  • Possibly an ARX - fast, cheap, and easy constant-time implementation on SW/HW.
$\endgroup$
5
  • $\begingroup$ TLS CCM? Who uses it? $\endgroup$ – kelalaka Jan 18 at 22:02
  • 3
    $\begingroup$ CCM in TLS is useful for embedded devices that have hardware-accelerated AES instructions, which is really the only situation where CCM might be faster than GCM. $\endgroup$ – forest Jan 18 at 22:39
  • $\begingroup$ @forest Thanks for pointing that, it uses CTR, too, also, the CBC-MAC of CCM doesn't need a PRP. $\endgroup$ – kelalaka Jan 18 at 22:43
  • 2
    $\begingroup$ "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$. $\endgroup$ – Fractalice Jan 19 at 19:52
  • 2
    $\begingroup$ @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 $\endgroup$ – kelalaka Jan 19 at 19:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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