A Security Analysis of Deoxys and its Internal Tweakable Block Ciphers

Authors

  • Carlos Cid Information Security Group, Royal Holloway University of London, Egham, United Kingdom
  • Tao Huang School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore, Singapore
  • Thomas Peyrin School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore, Singapore; School of Computer Science and Engineering, Nanyang Technological University, Singapore, Singapore
  • Yu Sasaki NTT Secure Platform Laboratories, Tokyo, Japan
  • Ling Song School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore, Singapore;Temasek Laboratories, Nanyang Technological University, Singapore, Singapore; State Key Laboratory of Information Security (SKLOIS), Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China

DOI:

https://doi.org/10.13154/tosc.v2017.i3.73-107

Keywords:

Deoxys-BC, AES, authenticated encryption, block cipher, differential cryptanalysis, boomerang attack, MILP, linear incompatibility, ladder switch

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.

Published

2017-09-19

Issue

Section

Articles

How to Cite

A Security Analysis of Deoxys and its Internal Tweakable Block Ciphers. (2017). IACR Transactions on Symmetric Cryptology, 2017(3), 73-107. https://doi.org/10.13154/tosc.v2017.i3.73-107