Revisiting Higher-Order Differential(-Linear) Attacks from an Algebraic Perspective --Applications to Ascon, Grain v1, Xoodoo, and ChaCha

The higher-order differential-linear (HDL) attack was studied for the first time by Biham, Dunkelman and Keller at FSE 2005, where a linear approximation is appended to a higher-order differential (HD) transition. It is a natural generalization of the differential-linear (DL) attack, but there are two main obstacles for its practical usage: (a) there is no known method to trace probabilistic HD trails; (b) the bias of a HDL approximation is estimated as 2^2l-1pq^2l , where l; p are the order and probability of the HD and q the bias of the appended linear approximation. Therefore, the bias can become exponentially small when jqj ̸= ½ and l ≫ 1. As a result, the HDL cryptanalysis has attracted much less attention compared to its DL counterpart since its proposal. Inspired by the algebraic perspective on DL attacks recently proposed at CRYPTO 2021, in this paper we show that the HDL attack can be made much more practical with a similar algebraic treatment. The bias of an l-th order HDL approximation is thus related to the bias of the superpoly of a cube for a so-called l-th order differential supporting function (DSF). In addition, although the cryptography community has known that HD, integral and cube attacks have close relationships, there has been no explicit formula to describe their exact transformation thus far. This new algebraic perspective applied to the HD attack gives precisely such a simple and direct formula.

Unsurprisingly, HD/HDL attacks have the potential to be more effective than their simpler Differential/DL counterpart. We provide three new methods to detect possible HD/HDL distinguishers, including: (a) an estimation of the algebraic degree of the DSF; (b) the so-called higher-order algebraic transitional form (HATF); (c) experimental methods based on cube testers. With these methods, we present HD  distinguishers for 7 and 8 rounds of the Ascon permutation in the black-box model with 2²³ and 2⁴⁶ data/time complexity respectively, zero-sum distinguisher for full 12-round Ascon permutation with 2⁵⁵ date/time complexity, (almost) deterministic HDL approximations for 4 and 5 rounds of the Ascon initialization, and new key-recovery attacks on 5 and 6 rounds of the Ascon AEAD. All these results greatly improve over the best-known attacks on reduced Ascon. Note these attacks in this paper are applicable to both Ascon-128 and Ascon-128A. We also give a conditional HD approximation for 130-round Grain v1 (5 more rounds than the previous best conditional differential approximation) and new 4-round deterministic HDL distinguishers for the permutation Xoodoo with only 4 chosen-plaintexts. Finally, we further applied our strategy to the ARXbased cipher ChaCha, obtaining 3.5-, 4- and 4.5-round  distinguishers and again improving over the state-of-the-art.