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 2 89 and 2 112 and time complexity between 2 189.9 and 2 233.9 depending on the proportion of weak keys that varies from 2 − 11 to 2 − 2 , marking a substantial advance over previous approaches.