New Records for Practical-data Chosen-plaintext Attacks on Round-reduced AES

As probably the most widespread block cipher, the AES has attracted tremendous cryptanalytical efforts since its standardization. In the single secret-key setting, Demirci-Selcuk Meet-in-the-Middle (DS-MitM) attacks have remained the state of the art on most rounds and have the lowest time complexities on all AES versions. However, after the research intensity had peaked with Derbez et al.'s seminal works from Eurocrypt'13 and FSE'13 and Li et al.'s improvements on the AES-192 at FSE'14, the generic technical evolution on DS-MitM attacks stagnated. Subsequent works automated the technique or concentrated on ciphers other than the AES. But it took one decade until Dong et al. (DCC'24) advanced the progress on DS-MitM attacks. Their approach uses constraints in both the offline and online phases, which produced improved attacks on AES-192 and -256 in the chosen-plaintext setting and on all versions in the practical-data setting. In this work, we demonstrate that Dong et al.'s use of constraints could be further improved, leading to better attacks on all versions of the AES with practical data complexity. We emphasize that our attacks do not threaten the security of the full AES versions but refine our understanding of their security margins under practical data settings.