A Security Analysis of Deoxys and its Internal Tweakable Block Ciphers

  • Carlos Cid Information Security Group Royal Holloway, University of London
  • Tao Huang School of Physical and Mathematical Sciences Nanyang Technological University
  • Thomas Peyrin School of Physical and Mathematical, Temasek Laboratories; School of Computer Science and Engineering, Nanyang Technological University
  • Yu Sasaki NTT Secure Platform Laboratories, Tokyo
  • Ling Song Nanyang Technological University (Singapore); State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences
Keywords: Deoxys-BC, AES, authenticated encryption, block cipher, differential cryptanalysis, boomerang attack, MILP, linear incompatibility, ladder switch


In this article, we provide the first independent security analysis of Deoxys, a third-round authenticated encryption candidate of the CAESAR competition, and its internal tweakable block ciphers Deoxys-BC-256 and Deoxys-BC-384. We show that the related-tweakey differential bounds provided by the designers can be greatly improved thanks to a Mixed Integer Linear Programming (MILP) based search tool. In particular, we develop a new method to incorporate linear incompatibility in the MILP model. We use this tool to generate valid differential paths for reduced-round versions of Deoxys-BC-256 and Deoxys-BC-384, later combining them into broader boomerang or rectangle attacks. Here, we also develop a new MILP model which optimises the two paths by taking into account the effect of the ladder switch technique. Interestingly, with the tweak in Deoxys-BC providing extra input as opposed to a classical block cipher, we can even consider beyond full-codebook attacks. As these primitives are based on the TWEAKEY framework, we further study how the security of the cipher is impacted when playing with the tweak/key sizes. All in all, we are able to attack 10 rounds of Deoxys-BC-256 (out of 14) and 13 rounds of Deoxys-BC-384 (out of 16). The extra rounds specified in Deoxys-BC to balance the tweak input (when compared to AES) seem to provide about the same security margin as AES-128. Finally we analyse why the authenticated encryption modes of Deoxys mostly prevent our attacks on Deoxys-BC to apply to the authenticated encryption primitive.

How to Cite
Cid, C., Huang, T., Peyrin, T., Sasaki, Y., & Song, L. (2017). A Security Analysis of Deoxys and its Internal Tweakable Block Ciphers. IACR Transactions on Symmetric Cryptology, 2017(3), 73-107. https://doi.org/10.13154/tosc.v2017.i3.73-107