Paper 2025/632

On breaking McEliece keys using brute force

Abstract

In the McEliece public-key encryption scheme, a private key is almost always not determined uniquely by its associated public key. We highlight a structural characterization of equivalent private keys that reduces the cost estimate for a simple private-key search using the support-splitting algorithm (SSA) by a polynomial but practically very substantial factor. In addition, we show how to apply the attack to extended codes in order to further improve the performance of the attack. (All of these techniques appear to be known to experts, but not all details have previously been laid out in the literature.) In addition to spelling out the — thus far — missing details underlying these attack strategies, we provide an optimized software implementation of the SSA for this kind of key search and demonstrate its capabilities in practice by solving a key-recovery challenge with a naïve a‑priori cost estimate of $2^{91}$ bit operations in just ${\approx}\,1470$ core days, testing ${\approx}\,7700$ private-key candidates per core and second in the process. We stress that the speedup from those equivalences on private keys and from our implementation techniques is merely polynomial and does not indicate any weakness in realistic instantiations of the McEliece cryptosystem, whose parameter choices are primarily constrained by decoding attacks rather than ludicrously more expensive key-recovery attacks.