Diving Deep into the Weak Keys of Round Reduced Ascon

Abstract

At ToSC 2021, Rohit et al. presented the first distinguishing and key recovery attacks on 7 rounds Ascon without violating the designer’s security claims of nonce-respecting setting and data limit of 2⁶⁴ blocks per key. So far, these are the best attacks on 7 rounds Ascon. However, the distinguishers require (impractical) 2⁶⁰ data while the data complexity of key recovery attacks exactly equals 2⁶⁴. Whether there are any practical distinguishers and key recovery attacks (with data less than 2⁶⁴) on 7 rounds Ascon is still an open problem.
In this work, we give positive answers to these questions by providing a comprehensive security analysis of Ascon in the weak key setting. Our first major result is the 7-round cube distinguishers with complexities 2⁴⁶ and 2³³ which work for 2⁸² and 2⁶³ keys, respectively. Notably, we show that such weak keys exist for any choice (out of 64) of 46 and 33 specifically chosen nonce variables. In addition, we improve the data complexities of existing distinguishers for 5, 6 and 7 rounds by a factor of 2⁸, 2¹⁶ and 2²⁷, respectively. Our second contribution is a new theoretical framework for weak keys of Ascon which is solely based on the algebraic degree. Based on our construction, we identify 2^127.99, 2^127.97 and 2^116.34 weak keys (out of 2¹²⁸) for 5, 6 and 7 rounds, respectively. Next, we present two key recovery attacks on 7 rounds with different attack complexities. The best attack can recover the secret key with 2⁶³ data, 2⁶⁹ bits of memory and 2^115.2 time. Our attacks are far from threatening the security of full 12 rounds Ascon, but we expect that they provide new insights into Ascon’s security.