Towards Tight Differential Bounds of Ascon

A Hybrid Usage of SMT and MILP

Abstract

Being one of the winners of the CAESAR competition and a finalist of the ongoing NIST lightweight cryptography competition, the authenticated encryption with associated data algorithm Ascon has withstood extensive security evaluation. Despite the substantial cryptanalysis, the tightness on Ascon’s differential bounds is still not well-understood until very recently, at ToSC 2022, Erlacher et al. have proven lower bounds (not tight) on the number of differential and linear active Sboxes for 4 and 6 rounds. However, a tight bound for the minimum number of active Sboxes for 4 − 6 rounds is still not known.
In this paper, we take a step towards solving the above tightness problem by efficiently utilizing both Satisfiability Modulo Theories (SMT) and Mixed Integer Linear Programming (MILP) based automated tools. Our first major contribution (using SMT) is the set of all valid configurations of active Sboxes (for e.g., 1, 3 and 11 active Sboxes at round 0, 1 and 2, respectively) up to 22 active Sboxes and partial sets for 23 to 32 active Sboxes for 3-round differential trails. We then prove that the weight (differential probability) of any 3-round differential trail is at least 40 by finding the minimum weights (using MILP) corresponding to each configuration till 19 active Sboxes. As a second contribution, for 4 rounds, we provide several necessary conditions (by extending 3 round trails) which may result in a differential trail with at most 44 active Sboxes. We find 5 new configurations for 44 active Sboxes and show that in total there are 9289 cases to check for feasibility in order to obtain the actual lower bound for 4 rounds. We also provide an estimate of the time complexity to solve these cases. Our third main contribution is the improvement in the 7-year old upper bound on active Sboxes for 4 and 5 rounds from 44 to 43 and from 78 to 72, respectively. Moreover, as a direct application of our approach, we find new 4-round linear trails with 43 active Sboxes and also a 5-round linear trail with squared correlation 2⁻¹⁸⁴ while the previous best known linear trail has squared correlation 2⁻¹⁸⁶. Finally, we provide the implementations of our SMT and MILP models, and actual trails to verify the correctness of results.