Leaky McEliece: Secret Key Recovery From Highly Erroneous Side-Channel Information

The McEliece cryptosystem is a strong contender for post-quantum schemes, including key encapsulation for confidentiality of key exchanges in network protocols. A McEliece secret key is a structured parity check matrix that is transformed via Gaussian elimination into an unstructured public key. We show that this transformation is a highly critical operation with respect to side-channel leakage. We assume leakage of the elementary row operations during Gaussian elimination, motivated by actual implementations of McEliece in real world cryptographic libraries (Classic McEliece and Botan). We propose a novel algorithm to reconstruct a secret key from its public key with information from a Gaussian transformation leak. Even if the obtained side-channel leakage is extremely noisy, i.e., each bit can be flipped with probability as high as $\tau \approx 0.4$, our algorithm still succeeds to recover the secret key in a matter of minutes for all proposed (Classic) McEliece instantiations. Remarkably, for high-security McEliece parameters, our attack is more powerful in the sense that it can tolerate even larger $\tau$. Technically, we introduce a novel cryptanalytic decoding technique that exploits the high redundancy exhibited in the McEliece secret key. This allows our decoding routine to succeed in reconstructing each column of the secret key successively. Our result stresses the necessity to well protect highly structured code-based schemes such as McEliece against side-channel leakage