BODIO: A bit-oriented distance-iterated optimizer for key search with bitwise linear leakage

Key search with bitwise linear leakage aims to identify the unique key that enables correct encryption in block ciphers whose hardware implementations exhibit bitwise linear leakage. This problem is challenging due to the discrete and large-scale search space, and the presence of substantial physical noise. Existing approaches typically combine correlation power analysis with heuristic algorithms to improve search efficiency, but they suffer from three main limitations: susceptibility to local optima due to noise-induced bias, misalignment with bit-level leakage characteristics, and high human and computational cost due to complex operator design and hyperparameter tuning. To address these challenges, the key search problem under bitwise linear leakage is reformulated as a binary optimization problem, and a bit-oriented optimization paradigm is introduced to explicitly align the search process with bit-level leakage characteristics. Based on this formulation, BODIO, a Bit-Oriented Distance-Iterated Optimizer inspired by the grey wolf optimizer, is proposed. BODIO mitigates noise-induced search bias through hierarchical guidance, preserves population diversity via an individual diversifier, and employs a one-bit-flip mechanism for precise refinement, thereby improving robustness and reducing the risk of premature convergence. Moreover, BODIO adopts a fully distance-iterated structure with fewer hyperparameters and improved structural extensibility. Simulation and Field-Programmable Gate Array (FPGA) experiments demonstrate that BODIO reduces the required number of power traces by 25.6% in simulation and 11.6% in FPGA experiments compared with the state-of-the-art method, while maintaining a 90% success rate and achieving competitive runtime performance, demonstrating its effectiveness and robustness.