Chengan Hou, Shuyi Wang, Meicheng Liu

Walsh Spectrum Puncturing Revisited: Toward Automated Linear Key Recovery Attacks

Introduction

Walsh spectrum puncturing revisited: toward automated linear key recovery attacks. Automate linear key recovery attacks with a new MILP model for Walsh Spectrum Puncturing (WSP). Optimize attacks on AES finalist Serpent and ISO standard PRESENT, reducing complexities and extending attack rounds.

Abstract

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.

Review

This paper addresses a crucial and often overlooked challenge in symmetric-key cryptanalysis: the automation and optimization of the key recovery phase in linear attacks. While the search for optimal linear approximations has largely been automated over decades of research, the subsequent key recovery step has remained largely manual and heuristic. The recent introduction of Walsh Spectrum Puncturing (WSP) by Flórez-Gutiérrez and Todo [FT24] further complicated this landscape by presenting a significantly larger number of candidate key recovery map approximations, making manual optimization practically intractable. This work therefore tackles a critical bottleneck, striving to bring the key recovery process closer to the efficiency and rigor enjoyed by the approximation search. The authors propose a robust methodology to tackle this challenge. Firstly, they provide formal proofs establishing that the approximate key recovery map strategy introduced in [FT24] is indeed optimal for specific puncturing techniques, namely Bit Puncturing and LAT Subspace Puncturing. Building on this theoretical foundation, the core contribution lies in the development of an MILP (Mixed-Integer Linear Programming) model designed to automatically search for the optimal approximate key recovery map specifically tailored for WSP. This MILP model represents a significant methodological advancement, transforming a largely manual and intuitive process into an automated, systematic optimization problem, which is a major step towards bridging the automation gap in linear cryptanalysis. The practical impact of this research is substantial, demonstrated through improved key recovery attacks on well-known cryptographic primitives. Applying their automated model, the authors successfully reduce the time complexity of a 12-round Serpent key recovery attack: from 2^189.7 to 2^184.8 for Serpent-192, and from 2^210.4 to 2^200.4 for Serpent-256. Furthermore, for the ISO standard PRESENT-128, they update the key recovery attack on its 29-round variant and, significantly, extend the attack to 30 rounds for the first time. These results not only set new benchmarks for these ciphers but, more importantly, underscore the efficacy of their automated approach, paving the way for more systematic and potentially deeper cryptanalytic insights into a broader range of symmetric-key primitives.

Full Text

Comments

You need to be logged in to post a comment.