Analysis of Ascon, DryGASCON, and Shamash Permutations

Year 2020, Volume: 9 Issue: 3, 172 - 187, 01.09.2020

Cihangir Tezcan

https://izlik.org/JA82CH64TE

Abstract

Ascon, DryGASCON, and Shamash are submissions to NIST's lightweight cryptography standardization process and have similar designs. We analyze these algorithms against subspace trails, truncated differentials, and differential-linear distinguishers. We provide probability one 4-round subspace trails for DryGASCON-256, 3-round subspace trails for \DryGASCON-128, and 2-round subspace trails for \Shamash permutations. Moreover, we provide the first 3.5-round truncated differential and 5-round differential-linear distinguisher for DryGASCON-128. Finally, we improve the data and time complexity of the 4 and 5-round differential-linear attacks on Ascon.

Keywords

Lightweight cryptography , Authenticated encryption , Cryptanalysis

References

• A. Bar-On, O. Dunkelman, N. Keller and A. Weizman, DLCT: A New Tool for Differential-Linear Cryptanalysis. In: Ishai Y, Rijmen V (editors) Advances in Cryptology – EUROCRYPT 2019. Lecture Notes in Computer Science, Springer 2019, vol 11476, pp. 313-342. doi:/10.1007/978-3-030-17653-2 11
• G. Bertoni, J. Daemen, M. Peeters and G. V. Assche, The Keccak SHA-3 Submission. Submission to NIST (Round 3 3) 2011, http://keccak.noekeon.org/Keccak-submission-3.pdf. Ac- cessed: September 23, 2020
• E. Biham, A. Biryukov and A. Shamir, Cryptanalysis of SKIP- JACK Reduced to 31 Rounds using Impossible Differentials, Journal of Cryptology 2005; vol. 18(4), pp. 291-311. doi: 10.1007/s00145-005-0129-3
• E. Biham, O. Dunkelman and N. Keller, Enhancing Differential- Linear Cryptanalysis, In: Zheng Y (editor). Advances in Cryp- tology - ASIACRYPT 2002, 8th International Conference on the Theory and Application of Cryptology and Information Security, Queenstown, New Zealand, December 1-5, 2002, Proceedings. Lecture Notes in Computer Science, Springer 2002, vol. 2501, pp. 254-266. doi:10.1007/3-540-36178-2 16
• E. Biham and A. Shamir, Differential Cryptanalysis of DES-like CryptosystemsIn: Menezes A, Vanstone S A (editors). Advances in Cryptology - CRYPTO ’90, 10th Annual International Cryptol- ogy Conference, Santa Barbara, California, USA, August 11-15, 1990, Proceedings. Lecture Notes in Computer Science, Springer 1990, vol. 537, pp. 2-21. doi:10.1007/3-540-38424-3 1
• C. Blondeau, B. G´erard and J. Tillich, Accurate Estimates of the Data Complexity and Success Probability for Various Cryptanalyses, Des. Codes Cryptogr. vol. 59, pp. 3–34 (2011). doi:10.1007/s10623-010-9452-2
• J. Daemen, Permutation-based Encryption, Authentication and Authenticated EncryptionDIAC - Directions in Authenticated Ci- phers, 2012, https://keccak.team/files/KeccakDIAC2012.pdf. Ac- cessed: September 23, 2020
• C. Dobraunig, M. Eichlseder and F. Mendel, Heuristic Tool for Linear Cryptanalysis with Applications to CAESAR Candidates, In: Iwata T, Cheon J H (editors). Advances in Cryptology - ASI- ACRYPT 2015 - 21st International Conference on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, November 29 - December 3, 2015, Proceedings, Part II. Lecture Notes in Computer Science, Springer 2015, vol. 9453, pp. 490-509. doi:10.1007/978-3-662-48800-3 20
• C. Dobraunig, M. Eichlseder, F. Mendel and M. Schla¨affer, ASCON v1, Submission to the CAESAR Competition 2014, https://competitions.cr.yp.to/round1/asconv1.pdf. September 23, 2020 Accessed:
• J. H. Evertse, Linear Structures in Blockciphers, In: Chaum D, Price W L (editors). EUROCRYPT. Lecture Notes in Computer Science, Springer 1987, vol. 304, pp. 249-266.
• L. Grassi, C. Rechberger and S. Rİnjom, Subspace Trail Cryptanalysis and its Applications to AES, IACR Transactions on Symmetric Cryptology 2016; vol. 2016(2), pp. 192-225. doi:10.13154/tosc.v2016.i2.192-225
• P. Jovanovic, A. Luykx and B. Mennink, Beyond 2 c/2 Security in Sponge-based Authenticated Encryption Modes, In: Sarkar P, Iwata T (editors). Advances in Cryptology - ASIACRYPT 2014 - 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, R.O.C., December 7-11, 2014. Proceedings, Part I. Lecture Notes in Computer Science, Springer 2014, vol. 8873, pp. 85-104. doi:10.1007/978-3-662-45611-8 5
• L. R. Knudsen, Truncated and Higher Order Differentials, In: Preneel B (editor). Fast Software Encryption: Second Interna- tional Workshop. Leuven, Belgium, 14-16 December 1994, Pro- ceedings. Lecture Notes in Computer Science, Springer (1994), vol. 1008, pp. 196-211. doi:10.1007/3-540-60590-8 16
• S. K. Langford and M. E. Hellman, Differential-Linear Crypt- analysis, In: Desmedt Y (editor). Advances in Cryptology - CRYPTO ’94, 14th Annual International Cryptology Conference, Santa Barbara, California, USA, August 21-25, 1994, Proceed- ings. Lecture Notes in Computer Science, Springer 1994, vol. 839, pp. 17-25. doi:10.1007/3-540-48658-5 3
• G. Leander, M. A. Abdelraheem, H. AlKhzaimi and E. Zenner, A Cryptanalysis of PRINTcipher: The Invariant Subspace Attack, In: Rogaway P (editor). Advances in Cryptology - CRYPTO 2011 - 31st Annual Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2011. Proceedings. Lecture Notes in Computer Science, Springer 2011, vol. 6841, pp. 206-221. doi:10.1007/978- 3-642-22792-9 12
• G. Leander, C. Tezcan and F. Wiemer, Searching for Sub- space Trails and Truncated Differentials, IACR Transactions on Symmetric Cryptology 2018; vol. 2018(1), pp. 74-100. doi:10.13154/tosc.v2018.i1.74-100
• Y. Li, G. Zhang, W. and W. Wang, Cryptanalysis of Round- Reduced ASCON, Sci. China Inf. Sci. 2017, 60, 038102. doi:10.1007/s11432-016-0283-3
• Z. Li, X. Dong and X. Wang, Conditional Cube At- tack Symmetric Cryptology 2017, vol. 2017(1), pp. 175-202. doi:10.13154/tosc.v2017.i1.175-202 IACR Transactions on
• R. H. Makarim and C. Tezcan, Relating Undisturbed Bits to Other Properties of Substitution Boxes, In: Eisenbarth T, ¨Ozt¨urk E (editors). Lightweight Cryptography for Security and Privacy - Third International Workshop, LightSec 2014, Istanbul, Turkey, September 1-2, 2014, Revised Selected Papers. Lecture Notes in Computer Science, Springer 2014, vol. 8898, pp. 109-125. doi:10.1007/978-3-319-16363-5 7
• M. Matsui, Linear Cryptanalysis Method for DES Cipher, In: Helleseth T (editor). Advances in Cryptology - EUROCRYPT ’93, Workshop on the Theory and Application of of Crypto- graphic Techniques, Lofthus, Norway, May 23-27, 1993, Pro- ceedings. Lecture Notes in Computer Science, Springer 1993, vol. 765, pp. 386-397. doi:10.1007/3-540-48285-7 33
• K. McKay, L. Bassham, M. S. Turan and N. Mouha, Report on Lightweight Cryptography, NIST Internal Report NISTIR 8114, 2017. doi:10.6028/NIST.IR.8114
• D. Penazzi and M. Montes, Shamash (and shamashash) Lightweight (version ization https://csrc.nist.gov/CSRC/media/Projects/Lightweight- Cryptography/documents/round-1/spec- doc/ShamashAndShamashash-spec.pdf Accessed: September 23, 2020 Cryptography Standard- round 1 submission, NIST 2019, [25] S. Riour, Drygascon, In: Standardization Process Round 1 Submission, NIST 2019, Lightweight Cryptography https://csrc.nist.gov/CSRC/media/Projects/Lightweight- Cryptography/documents/round-1/spec-doc/drygascon-spec.pdf. Accessed: September 23, 2020
• R. L. Rivest, The invertibility of the XOR of Rotations of a Binary Word, International Journal of Computer Mathematics 2011; vol. 88(2), pp. 281-284. doi:10.1080/00207161003596708
• S. Sun, L. Hu, P. Wang, K. Qiao, X. Ma and L. Song, Automatic Security Evaluation and (Related-key) Differential Characteristic Search: Application to SIMON, PRESENT, LBlock, DES(L) and Other Bit-oriented Block Ciphers, In: Sarkar P, Iwata T (editors). Advances in Cryptology - ASIACRYPT 2014 - 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, R.O.C., December 7-11, 2014. Proceedings, Part I. Lecture Notes in Computer Science, Springer 2014, vol. 8873, pp. 158-178. doi:10.1007/978- 3-662-45611-8 9
• C. Tezcan, The Improbable Differential Attack: Cryptanalysis of Reduced Round CLEFIA, In: Gong G, Gupta K C (editors). Progress in Cryptology - INDOCRYPT 2010 - 11th International Conference on Cryptology in India, Hyderabad, India, December 12-15, 2010. Proceedings. Lecture Notes in Computer Science, Springer 2010, vol. 6498, pp. 197-209. doi:10.1007/978-3-642- 17401-8 15 [29] C. Tezcan, Improbable Differential Journal Computational pp. Applied doi:10.1016/j.cam.2013.06.023 of and Mathematics 2014; vol. 259, 503-511.
• C. Tezcan, Truncated, Impossible, and Improbable Differential Analysis of ASCON, In: Camp O, Furnell S, Mori P (edi- tors). Proceedings of the 2nd International Conference on In- formation Systems Security and Privacy, ICISSP 2016, Rome, Italy, February 19-21, 2016. SciTePress (2016), pp. 325-332. doi:10.5220/0005689903250332
• Y. Todo, Structural Evaluation by Generalized Integral Prop- erty, In: Oswald E, Fischlin M (editors) Advances in Cryptology - EUROCRYPT 2015 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, April 26-30, 2015, Proceedings, Part I. Lecture Notes in Computer Science, Springer 2015, vol. 9056, pp. 287-314. doi:10.1007/978-3-662-46800-5 12
• M. S. Turan, K. McKay, C. Calik, D. Chang and L. Bassham, Status Report on the First Round of the NIST Lightweight Cryptography Standardization Process, NIST Internal Report NISTIR 8268, 2019 . doi: 10.6028/NIST.IR.8268