Impossible Differential Cryptanalysis on Deoxys-BC-256



Cyberspace Research Institute Shahid Beheshti University, G.C. Tehran, Iran


Deoxys is a final-round candidate of the CAESAR competition. Deoxys is built upon an internal tweakable block cipher Deoxys-BC, where in addition to the plaintext and key, it takes an extra non-secret input called a tweak. This paper presents the first impossible differential cryptanalysis of Deoxys-BC-256 which is used in Deoxys as an internal tweakable block cipher. First, we find a 4.5-round ID characteristic by utilizing a miss-in-the-middle-approach. We then present several cryptanalysis based upon the 4.5 rounds distinguisher against round-reduced Deoxys-BC-256 in both single-key and related-key settings. Our contributions include impossible differential attacks on up to 8-round Deoxys-BC-256 in the single-key model. Our attack reaches 9 rounds in the related-key related-tweak model which has a slightly higher data complexity than the best previous results obtained by a related-key related-tweak rectangle attack presented at FSE 2018, but requires a lower memory complexity with an equal time complexity.


[1] C. Cid, T. Huang, T. Peyrin, Y. Sasaki, and L. Song, “A security analysis of Deoxys and its internal tweakable block ciphers”, IACR Transactions on Symmetric Cryptology, 2017(3):73107,2017.
[2] Z.JiangandC.Jin,“ImpossibleDifferentialCrypt- analysis of 8-Round Deoxys-BC-256”, IEEE Access, Vol. 6, pp. 8890–8895, 2018.
[3] R. Zong, X. Dong, X. Wang, “Related-Tweakey Impossible Differential Attack on Reduced-Round Deoxys-BC-256”, SCIENCE CHINA Information Sciences.
[4] J. Jean, I. Nikolic, T. Peyrin, and Y. Seurin, “De-oxys v1.41”, Submitted to CAESAR, October 2016.
[5] J. Jean, I. Nikoli´ c, and T. Peyrin, “Tweaks and Keys for Block Ciphers : the TWEAKEY Framework”, Advances in Cryptology - ASIACRYPT 2014-20thInternationalConferenceontheTheory and Application of Cryptology and Information
Security, Kaoshiung, Taiwan, R.O.C., December 7-11, 2014, Proceedings, Part II, volume 8874 of Lecture Notes in Computer Science, pages 274288. Springer, 2014.
[6] J. Daemen, V. Rijmen, “AES Proposal : Rijndael”,NIST AES proposal, 1998.
[7] E. Biham, A. Biryukov, A. Shamir, “Miss in the middle attacks on IDEA and Khufu”, In L. Knudsen, editor, Fast Software Encryption, 6th international Workshop, Volume 1636 of Lecture Notes in Computer Science, pages 124138, Rome, Italy,
Springer-Verlag 1999.
[8] E. Biham, A. Biryukov, A. Shamir, “Cryptanalysis of Skipjack Reduced to 31 Rounds using Impossible Differentials”, in International Conference on the Theory and Applications of Cryptographic Techniques, 1999, pp. 12-23.
[9] M. Minier and M. Naya-Plasencia, “A related key impossible differential attack against 22 rounds of the lightweight block cipher LBlock”, In Information Processing Letters, Volume 112, Issue 16,2012, Pages 624-629, ISSN 0020-0190.
[10] J. Chen, Y. Wei, Y. Hu, “A New Method for Impossible Differential Cryptanalysis of 7-round Advanced Encryption Standard”, Proceedings of International Conference on Communications, Circuits and Systems Proceedings 2006, Vol. 3, pp.1577-1579, IEEE, 2006.
[11] C. Boura, M. Naya-Plasencia, and V. Suder,“Scrutinizing and Improving Impossible Differential Attacks: Applications to CLEFIA,Camellia, LBlock and Simon”, In ASIACRYPT 2014, Lecture Notes in Computer Science , volume 8873, pages 179-199, Springer, 2014.
[12] B. Bahrak and M. R. Aref, “Impossible differential attack on seven-round AES-128”, IET Information Security journal, Vol. 2, Number 2, pp.2832, IET, 2008.
[13] B. Bahrak and M. R. Aref, “A Novel Impossible Differential Cryptanalysis of AES”, proceedings of the Western European Workshop on Research in Cryptology 2007, Bochum, Germany, 2007.
[14] J. Lu, O. Dunkelman, N. Keller, and J. Kim,“New Impossible Differential Attacks on AES”, INDOCRYPT 2008. LNCS, vol. 5365, pp. 279293.Springer, Berlin, 2008.
[15] C. Dobraunig and E. List, “Impossible Differential and Boomerang Cryptanalysis of Round-Reduced Kiasu-BC”, pp.207222. Cham: Springer International Publishing, 2017.