International Association
for Cryptologic Research

Ultra-fast AES round-based software cryptographic authentication/encryption primitives have recently seen important developments, fuelled by the authenticated encryption competition CAESAR and the prospect of future high-profile applications such as post-5G telecommunication technology security standards. In particular, Universal Hash Functions (UHF) are crucial primitives used as core components in many popular modes of operation for various use-cases, such as Message Authentication Codes (MACs), authenticated encryption, wide block ciphers, etc. In this paper, we extend and improve upon existing design approaches and present a general framework for the construction of UHFs, relying only on the AES round function and 128-bit word-wide XORs. This framework, drawing inspiration from tweakable block ciphers design, allows both strong security arguments and extremely high throughput. The security with regards to differential cryptanalysis is guaranteed thanks to an optimized MILP modelling strategy, while performances are pushed to their limits with a deep study of the details of AES-NI software implementations. In particular, our framework not only takes into account the number of AES-round calls per message block, but also the very important role of XOR operations and the overall scheduling of the computations.We instantiate our findings with two concrete UHF candidates, both requiring only 2 AES rounds per 128-bit message block, and each used to construct two MACs. First, LeMac, a large-state primitive that is the fastest MAC as of today on modern Intel processors, reaching performances of 0.068 c/B on Intel Ice Lake (an improvement of 60% in throughput compared to the state-of-the-art). The second MAC construction, PetitMac, provides an interesting memory/throughput tradeoff, allowing good performances on many platforms.

About 20 years ago, Wagner showed that most of the (then) known techniques used in the cryptanalysis of block ciphers were particular cases of what he called commutative diagram cryptanalysis. However, to the best of our knowledge, this general framework has not yet been leveraged to find concrete attacks.In this paper, we focus on a particular case of this framework and develop commutative cryptanalysis, whereby an attacker targeting a primitive E constructs affine permutations A and B such that E ○ A = B ○ E with a high probability, possibly for some weak keys. We develop the tools needed for the practical use of this technique: first, we generalize differential uniformity into “A-uniformity” and differential trails into “commutative trails”, and second we investigate the commutative behaviour of S-box layers, matrix multiplications, and key additions.Equipped with these new techniques, we find probability-one distinguishers using only two chosen plaintexts for large classes of weak keys in both a modified Midori and in Scream. For the same weak keys, we deduce high probability truncated differentials that can cover an arbitrary number of rounds, but which do not correspond to any high probability differential trails. Similarly, we show the existence of a trade-off in our variant of Midori whereby the probability of the commutative trail can be decreased in order to increase the weak key density. We also show some statistical patterns in the AES super S-box that have a much higher probability than the best differentials, and which hold for a class of weak keys of density about 2−4.5.

Ascon is a sponge-based Authenticated Encryption with Associated Data that was selected as both one of the winners of the CAESAR competition and one of the finalists of the NIST lightweight cryptography standardization effort. As this competition comes to an end, we analyse the security of this algorithm against cube attacks. We present a practical cube attack against the full 6-round encryption in Ascon in the nonce-misuse setting. We note right away that this attack does not violate the security claims made by the designers of Ascon, due to this setting.Our cryptanalysis is a conditional cube attack that is capable of recovering the full capacity in practical time; but for Ascon-128, its extension to a key recovery or a forgery is still an open question. First, a careful analysis of the maximum-degree terms in the algebraic normal form of the Ascon permutation allows us to derive linear equations in half of the capacity bits given enough cube sums of dimension 32. Then, depending on the results of this first phase, we identify smaller-degree cubes that allow us to recover the remaining half of the capacity. Overall, our cryptanalysis has a complexity of about 240 adaptatively chosen plaintexts, and about 240 calls to the permutation. We have implemented the full attack and our experiments confirm our claims.Our results are built on a theoretical framework which allows us to easily identify monomials whose cube-sums provide linear equations in the capacity bits. The coefficients of these monomials have a more general form than those used in the previous attacks against Ascon, and our method enables us to re-frame previous results in a simpler form. Overall, it enables to gain a deeper understanding of the properties of the permutation, and in particular of its S-box, that make such state-recoveries possible.