Walsh Spectrum Puncturing Revisited: Toward Automated Linear Key Recovery Attacks

Linear cryptanalysis has long served as a cornerstone in the security analysis of symmetric-key cryptanalytic primitives. Through more than 30 years of community efforts, it has become routine to use automated tools to search for the optimal linear approximations. In stark contrast, the key recovery part is still far from automation and optimization. The situation became even more challenging after the work of Flórez-Gutiérrez and Todo [FT24], where the newly introduced Walsh Spectrum Puncturing (WSP) technique brought a large number of candidate key recovery map approximations. In this paper, we formally prove that the approximate key recovery map proposed by [FT24] is the optimal strategy for Bit Puncturing and LAT Subspace Puncturing. We then propose an MILP model to automatically search for the optimal approximate key recovery map for WSP. The automated model is used to improve the linear key recovery attack on the AES finalist Serpent and the ISO standard PRESENT. We reduce the time complexity of the 12-round Serpent key recovery attack to 2184.8 (from 2189.7) for Serpent-192 and to 2200.4 (from 2210.4) for Serpent-256. For PRESENT-128, we update the key recovery attack on its 29-round variant, and extend the attack to 30 rounds for the first time.