Paper 2022/845

Key Structures: Improved Related-Key Boomerang Attack against the Full AES-256

Jian Guo, Nanyang Technological University, Singapore
Ling Song, Jinan University, China
Haoyang Wang, Shanghai Jiao Tong University, China

This paper introduces structure to key, in the related-key attack settings. While the idea of structure has been long used in keyrecovery attacks against block ciphers to enjoy the birthday effect, the same had not been applied to key materials due to the fact that key structure results in uncontrolled differences in key and hence affects the validity or probabilities of the differential trails. We apply this simple idea to improve the related-key boomerang attack against AES-256 by Biryukov and Khovratovich in 2009. Surprisingly, it turns out to be effective, i.e., both data and time complexities are reduced by a factor of about 2^8, to 2^92 and 2^91 respectively, at the cost of the amount of required keys increased from 4 to 2^19. There exist some tradeoffs between the data/time complexity and the number of keys. To the best of our knowledge, this is the first essential improvement of the attack against the full AES-256 since 2009. It will be interesting to see if the structure technique can be applied to other AES-like block ciphers, and to tweaks rather than keys of tweakable block ciphers so the amount of required keys of the attack will not be affected.

Available format(s)
Attacks and cryptanalysis
Publication info
Published elsewhere. ACISP 2022
AES differential boomerang key structure related key
Contact author(s)
guojian @ ntu edu sg
songling qs @ gmail com
haoyang wang @ sjtu edu cn
2022-06-27: approved
2022-06-27: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jian Guo and Ling Song and Haoyang Wang},
      title = {Key Structures: Improved Related-Key Boomerang Attack against the Full {AES}-256},
      howpublished = {Cryptology ePrint Archive, Paper 2022/845},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.