3
$\begingroup$

As AES progresses through multiple rounds, approximately how does it security increase round by round up to its maximum? I'm curious about the shape of the curve. Is it linear, some kind of exponential, a power law curve, etc.?

$\endgroup$
2

1 Answer 1

3
$\begingroup$

A few data points for AES-128. In 2018 Bar-On, Dunkelman, Keller, Ronan and Shamir described a 32-bit attack on 5 round AES (attack complexity here is the maximum of data, memory and computation requirements) and claimed a 99-bit attack on 7 round AES. The 2011 biclique cryptanalysis paper of Bogdanov, Khovratovich and Rechberger claims a 125.4-bit attack on 8 rounds and a 126.18-bit attack on 10 rounds. I'll claim a 128-bit attack against 11 rounds :-)

Based on our current knowledge then, perhaps it looks like an S-curve? Of course cryptanalytic effort has focussed strongly on larger numbers of rounds and I'd be hesitant to hypothesise any security vs. rounds function based on this.

ETA: The quoted figures for 8 and 10 rounds were for a related key biclique attack. The current best generic attack for 10 rounds is $2^{126.01}$

$\endgroup$
6
  • 1
    $\begingroup$ S curvy perhaps for attack complexity vs rounds, but the question is strength vs rounds. So your s-curve needs to be inverted, or plotted as (128 - attack complexity) vs rounds. I.e.asymptotic to zero. $\endgroup$
    – Paul Uszak
    Mar 24, 2021 at 11:23
  • 1
    $\begingroup$ Although you have answered my referenced question :-) $\endgroup$
    – Paul Uszak
    Mar 24, 2021 at 11:30
  • $\begingroup$ What about small numbers of rounds? e.g. 1-4 rounds? My impression is that one round is pretty trivial to break. Otherwise it does look like a sort of S curve where things get good around 5 rounds and diminishing returns kick in after 8-9 rounds. $\endgroup$ Mar 24, 2021 at 17:43
  • 1
    $\begingroup$ The 2011 biclique cryptanalysis is a related key attack that has no place for encryption since we are expected to choose uniform random keys. It is related to consructing hash functions from any block cipher. The 2018 article is the full round attack $\endgroup$
    – kelalaka
    Mar 24, 2021 at 18:25
  • $\begingroup$ Thanks @kelalaka ! Before I edit to update the 10 round estimate, do you know if the biclique crowd had an estimate for 8-9 rounds in the non-related key setting? $\endgroup$
    – Daniel S
    Mar 24, 2021 at 18:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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