Improved Related-Key Differential Attacks against AES-256

In this paper, we revisit the differential meet-in-the-middle attack and classical differential attack on AES-256 under the related-key setting, as introduced in Boura et al.'s ToSC 2023 and Song et al.'s Asiacrypt 2024 works. We propose new attacks against 13-round AES-256, all with significantly lower complexities. This is achieved through an efficient method for identifying weak keys, which enables a better utilization of differential propagation. Furthermore, we present multiple attack scenarios and their complexities by considering various weak keys derived from the key generation process. Our attacks have data complexity between <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow> <mml:mn>89</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> </mml:math> and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow> <mml:mn>112</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> </mml:math> and time complexity between <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow> <mml:mn>189.9</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> </mml:math> and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow> <mml:mn>233.9</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> </mml:math> depending on the proportion of weak keys that varies from <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow> <mml:mo>−</mml:mo> <mml:mn>11</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> </mml:math> to <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow> <mml:mo>−</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> </mml:math> , marking a substantial advance over previous approaches.