Towards the Links of Cryptanalytic Methods on MPC/FHE/ZK-Friendly Symmetric-Key Primitives
Symmetric-key primitives designed over the prime field Fp with odd characteristics, rather than the traditional Fn2 , are becoming the most popular choice for MPC/FHE/ZK-protocols for better efficiencies. However, the security of Fp is less understood as there are highly nontrivial gaps when extending the cryptanalysis tools and experiences built on Fn2 in the past few decades to Fp.At CRYPTO 2015, Sun et al. established the links among impossible differential, zero-correlation linear, and integral cryptanalysis over Fn2 from the perspective of distinguishers. In this paper, following the definition of linear correlations over Fp by Baignères, Stern and Vaudenay at SAC 2007, we successfully establish comprehensive links over Fp, by reproducing the proofs and offering alternatives when necessary. Interesting and important differences between Fp and Fn2 are observed.- Zero-correlation linear hulls can not lead to integral distinguishers for some cases over Fp, while this is always possible over Fn2proven by Sun et al..- When the newly established links are applied to GMiMC, its impossible differential, zero-correlation linear hull and integral distinguishers can be increased by up to 3 rounds for most of the cases, and even to an arbitrary number of rounds for some special and limited cases, which only appeared in Fp. It should be noted that all these distinguishers do not invalidate GMiMC’s security claims.The development of the theories over Fp behind these links, and properties identified (be it similar or different) will bring clearer and easier understanding of security of primitives in this emerging Fp field, which we believe will provide useful guides for future cryptanalysis and design.
Automatic Preimage Attack Framework on Ascon Using a Linearize-and-Guess Approach
Ascon is the final winner of the lightweight cryptography standardization competition (2018 − 2023). In this paper, we focus on preimage attacks against round-reduced Ascon. The preimage attack framework, utilizing the linear structure with the allocating model, was initially proposed by Guo et al. at ASIACRYPT 2016 and subsequently improved by Li et al. at EUROCRYPT 2019, demonstrating high effectiveness in breaking the preimage resistance of Keccak. In this paper, we extend this preimage attack framework to Ascon from two aspects. Firstly, we propose a linearize-and-guess approach by analyzing the algebraic properties of the Ascon permutation. As a result, the complexity of finding a preimage for 2-round Ascon-Xof with a 64-bit hash value can be significantly reduced from 239 guesses to 227.56 guesses. To support the effectiveness of our approach, we find an actual preimage of all ‘0’ hash in practical time. Secondly, we develop a SAT-based automatic preimage attack framework using the linearize-and-guess approach, which is efficient to search for the optimal structures exhaustively. Consequently, we present the best theoretical preimage attacks on 3-round and 4-round Ascon-Xof so far.