International Association for Cryptologic Research

International Association
for Cryptologic Research


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
DOI: 10.13154/tosc.v2017.i3.73-107
Search ePrint
Search Google
Abstract: 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.
  title={A Security Analysis of Deoxys and its Internal Tweakable Block Ciphers},
  journal={IACR Trans. Symmetric Cryptol.},
  publisher={Ruhr-Universit├Ąt Bochum},
  volume={2017, Issue 3},
  author={Carlos Cid and Tao Huang and Thomas Peyrin and Yu Sasaki and Ling Song},