SCIENCE CHINA Information Sciences, Volume 62, Issue 3: 032102(2019) https://doi.org/10.1007/s11432-017-9382-2

Related-tweakey impossible differential attack on reduced-round Deoxys-BC-256

More info
  • ReceivedDec 27, 2017
  • AcceptedFeb 28, 2018
  • PublishedJan 31, 2019


Deoxys-BC is the internal tweakable block cipher of Deoxys, a third-round authenticated encryption candidate at the CAESAR competition. In this study, by adequately studying the tweakey schedule, we seek a six-round related-tweakey impossible distinguisher of Deoxys-BC-256, which is transformed from a 3.5-round single-key impossible distinguisher of AES, by application of the mixed integer linear programming (MILP) method. We present a detailed description of this interesting transformation method and the MILP-modeling process.Based on this distinguisher, we mount a key-recovery attack on 10 (out of 14) rounds of Deoxys-BC-256.Compared to previous results that are valid only when the key size $>204$ and the tweak size $<52$, our method can attack 10-round Deoxys-BC-256 as long as the key size $\geq174$ and the tweak size $\leq82$. For the popular setting in which the key size is 192 bits, we can attack one round more than previous studies.Note that this paper only gives a more accurate security evaluation and does not threaten the security of full-round Deoxys-BC-256.


This work was supported by National Key Research and Development Program of China (Grant No. 2017YFA0303903), National Natural Science Foundation of China (Grant No. 61672019), National Cryptography Development Fund (Grant No. MMJJ20170121), Zhejiang Province Key RD Project (Grant No. 2017C01062), Fundamental Research Funds of Shandong University (Grant No. 2016JC029), and China Postdoctoral Science Foundation (Grant No. 2017M620807).


[1] Jean J, Nikolić I, Peyrin T, et al. Deoxys v1.41. Submitted to CAESAR, October 2016. Google Scholar

[2] Daemen J, Rijmen V. The Design of rijndael. In: AES - the Advanced Encryption Standard. Berlin: Springer, 2002. Google Scholar

[3] Liskov M, Rivest R L, Wagner D. Tweakable block ciphers. J Cryptol, 2011, 24: 588-613 CrossRef Google Scholar

[4] Beierle C, Jean J, Kölbl S, et al. The SKINNY family of block ciphers and its low-latency variant MANTIS. In: Advances in Cryptology - CRYPTO 2016. Berlin: Springer 2016. 123--153. Google Scholar

[5] Borghoff J, Canteaut A, Gneysu T, et al. PRINCE - a low-latency block cipher for pervasive computing applications. In: Advances in Cryptology - ASIACRYPT 2012. Berlin: Springer, 2012. 208--225. Google Scholar

[6] Avanzi R. The QARMA block cipher family - almost MDS matrices over rings with zero divisors, nearly symmetric Even-Mansour constructions with non-involutory central rounds, and search heuristics for low-latency S-Boxes. IACR Trans Symmetric Cryptology, 2017, 1: 4--44. Google Scholar

[7] Jean J, Nikolić I, Peyrin T. Tweaks and keys for block ciphers: The TWEAKEY framework. In: Advances in Cryptology - ASIACRYPT 2014. Berlin: Springer, 2014. 274--288. Google Scholar

[8] Cid C, Huang T, Peyrin T, et al. A security analysis of Deoxys and its internal tweakable block cphers. IACR Trans Symmetric Cryptology, 2017, 3: 73--107. Google Scholar

[9] Bellare M, Hoang V, Tessaro S. Message-recovery attacks on Feistel-based format preserving encryption. In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Seucrity, Vienna, 2016. 444--455. Google Scholar

[10] Ankele R, Banik S, Chakraborti A, et al. Related-key impossible-differential attack on reduced-round SKINNY. In: Applied Cryptography and Network Security - ACNS 2017. Berlin: Springer, 2017. 208--228. Google Scholar

[11] Derbez P, Fouque P-A, Jean J. Improved key recovery attacks on reduced-round AES in the single-key setting. In: Advances in Cryptology - EUROCRYPT 2013. Berlin: Springer, 2013. 371--387. Google Scholar

[12] Biham E, Keller N. Cryptanalysis of reduced variants of Rijndael. In: Third AES Candidate Conference, 2000. Google Scholar

[13] Mouha N, Wang Q J, Gu D W, et al. Differential and linear cryptanalysis using mixed-integer linear programming. In: Information Security and Cryptology - Inscrypt 2011. Berlin: Springer, 2011. 57--76. Google Scholar

[14] Wu S B, Wang M S. Security evaluation against differential cryptanalysis for block cipher structures. https://eprint.iacr.org/2011/551. Google Scholar

[15] Sun S W, Hu L, Wang P, et al. Automatic security evaluation and (related-key) differential characteristic search: Application to SIMON, PRESENT, LBlock, DES(L) and other bit-oriented block ciphers. In: Advances in Cryptology - ASIACRYPT 2014. Berlin: Springer, 2014. 158--178. Google Scholar

[16] Sun S W, Hu L, Song L, et al. Automatic security evaluation of block ciphers with S-bP structures against related-key differential attacks. In: Information Security and Cryptology - Inscrypt 2013. Berlin: Springer, 2013. 39--51. Google Scholar

[17] Sun S W, Hu L, Wang M Q, et al. Towards finding the best characteristics of some bit-oriented blcok ciphers and automatic enumeration of (related-key) differential and linear characteristics with predefined properties. https://eprint.iacr.org/2014/747. Google Scholar

[18] Fu K, Wang M Q, Guo Y H, et al. MILP-based automatic search algorithms for differential and linear trails for Speck. In: Fast Software Encryption - FSE 2016. Berlin: Springer, 2016. 268--288. Google Scholar

[19] Sasaki Y, Todo Y. New impossible differential search tool from design and cryptanalysis aspects. In: Advances in Cryptology - EUROCRYPT 2017. Berlin: Springer, 2017. 185--215. Google Scholar

[20] Cui T T, Jia K T, Fu K, et al. New automatic search tool for impossible differentials and zero-correlation linear approximations. http://eprint.iacr.org/2016/689. Google Scholar

  • Figure 3

    Search for longer related-key differential.

  • Table 1   Cryptanalysis results for Deoxys-BC-256. Our attack can be mounted on Deoxys-BC-256 with a wider key size range. Because the cipher adopts the TWEAKEY framework (such as the tweak-updating mode, i.e., the tweak can be changed but the key stays the same), our attack is more efficient as the data complexity can be beyond full-codebook. A beyond-full-codebook attack on SKINNY was published in ; we give a more specified description about beyond-full-codebook attacks in Subsection .
    Primitive Number of rounds Tweak size Key size Time Data Attack type Ref.
    8/14 128 128 $\leq~2^{128}$ MitM [1]
    $\leq$ 8/14 128 128 $\leq~2^{128}$ Differential [1]
    Deoxys-BC-256 9/14 128 128 $2^{128}$ $2^{117}$ Rectangle [8]
    10/14 $<52$ $>204$ $2^{204}$ $2^{127.58}$ Rectangle [8]
    10/14 $\leq82$ $\geq174$ $2^{173.1}$ $2^{135}$ Impossible differential This paper
  • Table 2   $h$-permutation
    $i$ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
    $h(i)$ 1 6 11 12 5 10 15 0 9 14 3 4 13 2 7 8
  • Table 3   Actual values of impossible differential conforming the distinguisher
    Round Index $\Delta~{\rm~TK}^1$ $\Delta~{\rm~TK}^2$ $\Delta~{\rm~STK}$ $\Delta~X$ $\Delta~Z$ $\Delta~W$
    1 8 0x3d 0x3d
    9 0x3d 0x47
    10 0x00 0x00
    11 0x00 0x7a
    2 8 0x66 0x5b 0x3d
    9 0x36 0x71 0x47
    11 0x7a
    3 9 0x66 0xb6 0xd0
    14 0x36 0xe3 0xd5
    4 14 0x66 0x6c 0x0a
    7 0x36 0xc6 0xf0
    5 7 0x66 0xd9 0xbf
    0 0x36 0x8d 0xbb 0x3e 0xd5
    1 0xba 0x2d
    2 0x00
    3 0x7c
    6 0 0x66 0xb3 0xd5
    1 0x36 0x1b 0x2d
    7 1 0x66 0x66 0x00
    6 0x36 0x36 0x00
    8 6 0x66 0xcd 0xab 0xab
    15 0x36 0x6d0x5b 0x5b

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有