Analysis of Ascon, DryGASCON, and Shamash Permutations

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

Cihangir Tezcan

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