Paper 2026/1997 Original: eprint.iacr.org/2026/1997 ↗

LibFWHT: From Exact Walsh Spectra to Key Dependence in Differential-Linear Correlations

Abstract

The Walsh-Hadamard transform (WHT) computes the correlation of a Boolean function with every linear function at once. Cryptanalytic workflows transform large arrays repeatedly, in batches. However, available tools specialize in particular data types, platforms, or ecosystems. We present LibFWHT, an open-source C library for dense WHTs, with Python bindings and a command-line interface. It includes vectorized, multicore, and graphics processing unit (GPU) backends, batch operations, and routines for Boolean functions and substitution boxes (S-boxes). With one central processing unit (CPU) core, LibFWHT is 2.5 to 3.3 times faster than FFTW; on batched Boolean spectra with eight threads, it is up to 3.7 times faster than sboxU. On an NVIDIA H200, its device-resident GPU backend reaches 1.8 trillion operations per second and runs the same Boolean workload about 600 times faster than the CPU-only sboxU. We demonstrate LibFWHT in linear and differential-linear cryptanalysis of reduced-round SIMON-32, KATAN-32, BEANIE, KeeLoq, and RC5-16, all with 32-bit blocks. To the best of our knowledge, we report the first exact differential-linear distinguishers for KATAN-32, BEANIE, KeeLoq, and RC5-16. We measure these correlations over many sampled keys and ask which key bits make them vary. Using the geometric approach to cryptanalysis, we search for key-dependent trails to propose candidate round-key bits. The search alone does not show how much these bits affect the correlation, because contributions from trails that depend on the same bits can cancel. For an 84-round KATAN-32 distinguisher, the lowest-weight key-dependent trails we enumerated have contributions that sum to exactly zero. We therefore check the proposed bits using exact correlations on independently sampled master keys, with round keys derived by the cipher's key schedule. For a 13-round differential-linear distinguisher of SIMON-32, two round-key bits explain 93.1% of the variance in the measured signed correlations. They identify a low-correlation class containing about a quarter of the sampled keys. A single root-mean-square (RMS) correlation over all sampled keys hides this difference. For the low-correlation group, the usual data estimate is about 40 times the estimate based on the overall RMS. This compares group estimates and does not guarantee success for each key. Key dependence therefore belongs in the analysis, and we report distributions over keys rather than single numbers.