Efficient Weak Key Recovery for QC-MDPC Codes like BIKE

Code-based cryptography, originally proposed nearly 50 years ago, has been highly successful in the NIST standardization process for post-quantum key encapsulation mechanisms. With HQC and BIKE, two of the considered candidates are based on the hardness of quasi-cyclic codes. One important attack first presented by Guo et al. at ASIACRYPT 2016 that targets moderately dense codes is the distance spectrum recovery attack. The attack makes use of the correlation between the error patterns causing a decryption failure and the sparse private key. However, for random keys, decoding failures are highly unlikely and the attack thus only succeeds with negligible probability. Another line of cryptanalysis on quasi-cyclic code-based cryptosystems has focused on weak keys with higher DFR, which invalidate the provable security guarantees. However, so far the distance spectrum of such weak keys have never been analyzed, leaving a gap in the cryptanalysis research of modern code-based cryptosystems. In this work, we show that Type I weak keys feature a new distance spectrum not analyzed before that cannot be attacked with known key recovery techniques proposed by Guo et al. Instead, we introduce a new key recovery algorithm that, considering the reaction attacker setting, exceeds the state-of-the-art recovery methods by exploiting the distance spectrum of the new weak keys with high probability. When considering a natural side-channel occurring in real-world implementations of the decoding phase, our attack can be enhanced even further.