KEY MODIFICATION ALGORITHM FOR WEAK KEYS IN BIKE KEM

ABSTRACT

Bit Flipping Key Encapsulation (BIKE) is a code-based Key Encapsulation Mechanism (KEM), selected by NIST as a finalist in the fourth round of Post-Quantum Cryptography (PQC) standardization. BIKE effectively addresses the principal limitation of traditional code-based cryptographic algorithms, specifically the issue of large key sizes. Concurrently, research efforts have increasingly focused on the characterization, measurement, and mitigation of decoder failure rates. Numerous proposals have been presented to enhance decoding techniques, resulting in iterative improvements to BIKE's decoding algorithms since its inception. Recent studies have identified that specific patterns within private keys, termed weak keys, considerably elevate the probability of decoder failures. In this paper, we propose a novel key modification algorithm designed explicitly to detect these weak keys and transform them into robust keys, significantly improving the overall reliability of the BIKE mechanism.

АННОТАЦИЯ

Bit Flipping Key Encapsulation (BIKE) представляет собой механизм инкапсуляции ключей на основе кода (KEM), выбранный NIST в качестве финалиста в четвертом раунде стандартизации пост квантовой криптографии (PQC). BIKE эффективно устраняет основное ограничение традиционных криптографических алгоритмов на основе кода, в частности, проблему больших размеров ключей. Одновременно с этим исследовательские усилия все больше сосредотачиваются на характеристике, измерении и смягчении показателей сбоев декодера. Было представлено множество предложений по улучшению методов декодирования, что привело к итеративным улучшениям алгоритмов декодирования BIKE с момента его создания. Недавние исследования выявили, что определенные шаблоны в закрытых ключах, называемые слабыми ключами, значительно повышают вероятность сбоев декодера. В этой статье мы предлагаем новый алгоритм модификации ключей, разработанный явно для обнаружения этих слабых ключей и преобразования их в надежные ключи, что значительно повышает общую надежность механизма BIKE.

Keywords: code-based encapsulation mechanism; BIKE; BIKE-Flip decoder; weak keys.

Ключевые слова: механизм инкапсуляции на основе кода; BIKE; Декодер BIKE-Flip; слабые ключи.

Introduction

In the contemporary digital environment, ensuring the security of key encapsulation mechanisms (KEM) has become increasingly critical to protect sensitive data. The necessity for such secure systems was underscored by the groundbreaking work of mathematician Peter Shor, who introduced an efficient quantum algorithm capable of factoring large integers into primes, thereby compromising classical cryptographic systems such as RSA, Diffie–Hellman, and elliptic curve cryptography [1]. Initially, Shor’s algorithm required quantum computational resources far exceeding the available quantum hardware. However, recent rapid advancements in quantum computing have significantly altered the landscape. While the first quantum computers in the late 20th century operated with merely a single qubit, by 2023 IBM had successfully launched a groundbreaking quantum processor featuring 1,000 qubits [2]. Recognizing the imminent threat posed by quantum algorithms, the National Institute of Standards and Technology (NIST) initiated the Post-Quantum Cryptography (PQC) Standardization Program [3]. This initiative has generated substantial research interest, accelerating developments and innovations in post-quantum cryptographic solutions designed to withstand quantum attacks.

Maintaining information security is becoming increasingly challenging due to the rapid development of quantum computing technologies. Among the cryptographic algorithms submitted to the recent NIST Post-Quantum Cryptography (PQC) Standardization competition, lattice-based schemes (e.g., CRYSTALS-Kyber, NewHope, and LAC) and code-based schemes (e.g., LEDAcrypt, BIKE, and RQC) attracted significant attention from researchers worldwide. On July 5, 2022, NIST announced CRYSTALS-Kyber as the selected algorithm for standardization and identified four additional candidates advancing to the fourth round. Notably, three out of these four finalists belong to the category of code-based cryptosystems, underscoring the importance and necessity of further research in this particular area [3].

However, it was not feasible to advance without introducing modifications and optimizations to align with contemporary cryptographic standards. Despite its computational efficiency—for instance, the original McEliece cryptosystem outperforms RSA in speed with 514 binary operations per bit for encryption and 5,140 for decryption, compared to RSA's 2,402 and 738,112, respectively—the algorithm based on Goppa codes suffers from a critical drawback: an excessively large key size of approximately 67,072 bytes for a code length of n = 1024 [4]. To address this limitation, researchers proposed substituting Goppa codes with quasi-cyclic moderate-density parity-check (QC-MDPC) codes [5], enabling code-based cryptosystems to remain competitive alongside lattice-based counterparts. One of the most promising candidates employing QC-MDPC codes is the Bit Flipping Key Encapsulation (BIKE) algorithm.

Nevertheless, it is difficult to assume the existence of a cryptosystem entirely free from vulnerabilities, and BIKE is no exception. One of the most notable threats to BIKE is a class of reaction-based attacks, such as the key recovery attack introduced by Guo, Johansson, and Stankovski (GJS), which exploits decoder failures [6]. In response to this, the Fujisaki–Okamoto (FO) CCA transformation was implemented to enhance security against such attacks [7]. Although this transformation enabled the verification of ciphertext integrity, it could not fully ensure indistinguishability under chosen-ciphertext attacks (IND-CCA). To achieve λ-bit IND-CCA security, the decoder failure rate (DFR) must remain below the threshold of 2⁻ˡ [8].

Initially, BIKE employed a bit-flipping decoder known for its relatively high DFR, making the scheme vulnerable to both side-channel and reaction-based attacks [9]. Over time, the BIKE decoding mechanism underwent several iterations to enhance its efficiency and robustness. In 2020, the bit-flipping decoder was replaced with the Black-Gray Flip decoder, which offered improved performance, a lower DFR, and constant-time implementation to mitigate side-channel risks [10]. The most recent advancement came in October 2024 with the introduction of BIKE-Flip in version 5.2. This decoder features a simplified architecture compared to its predecessor and demonstrates improved resistance to weak key patterns—previously identified as a major cause of decoding failures [10].

In addition to the decoders developed by the original authors of BIKE, various alternative and enhanced decoding strategies have been proposed in the literature. One such example is the Weighted Bit Flipping (WBF) decoder, which assigns weights to syndrome components to assess their reliability and prioritize bit flipping accordingly. This approach achieves a significantly lower decoder failure rate (DFR) compared to the Black-Gray Flip decoder. However, the improvement in error correction comes at the cost of increased computational complexity. To balance performance and efficiency, researchers have proposed hybrid decoding schemes that combine WBF with Black-Gray Flip methods [11]. Another notable development is the PickyFix decoder, which improves execution speed while maintaining constant-time operation to protect against side-channel attacks. Nonetheless, it also suffers from increased computational overhead, limiting its practical deployment in resource-constrained environments [12].

Related Work

Replacing the decoder alone did not fully eliminate BIKE's vulnerabilities, as another critical issue remained. Recent studies have shown that certain types of private keys lead to poor decoder failure rates (DFR), regardless of the decoding algorithm employed [13–16]. In [16], the authors examined the bit-flipping decoder and concluded that the impact of such weak keys on overall DFR is negligible. However, subsequent research [13] challenged this claim by demonstrating that weak keys can significantly increase DFR beyond acceptable thresholds and therefore must not be overlooked. To address this, a key classification algorithm was proposed to distinguish between weak and normal keys. While the suggested solution in [13] involves discarding weak keys and regenerating them, this paper introduces an alternative approach: a key transformation mechanism that converts weak keys into valid, robust ones without requiring full key regeneration.

Background

Definition 1 [17]. A binary linear block code with parameters (n, k, d) is a set of codewords where the component wise mod-2 sum of any two codewords results in another codeword within the same code.

Definition 2 [18]. A quasi-cyclic (QC) with index l is a linear code that remains unchanged when l positions shift its codewords.

Definition 3 [19].The Hamming weight refers to the count of non-zero digits within a word.The parity check matrix for a quasi-cyclic (QC) code can be represented as where each segment is a binary matrix structured as

                                                                   (1)

and generator matrix [20] can be written as

                                                (2) 

Definition 4 [13]. The multiplicity of distance is determined as

Weak keys

Type 1: A key is the weak key if  such that for some , with  = d − f and  = d.  is a function that replaces  with

Type 2: Compared with Type 1 weak keys for Type 2 weak keys one distance with high multiplicity is enough.

Type 3: This type of weak key does not consider only one block but the intersection between , which creates an ambiguity for the decoder. [21]

Consequences of using weak keys

Assume we have parity check matrix H with columns j and l, where non-zero bits have identical positions (m). For normal keys, m will be small, if m large keys are called weak. Due to the large intersection both j and l have similar parity check equations, which will cause to decoder go back and forth, incapable of finding the correct vector e [13].

Key modification algorithm

This algorithm aims to deal with polynomials that have distances with high multiplicity. To understand the main concept let’s take polynomials   and . We work on

1. Find distances and multiplicities where  distance for  and = and shifts for  from  and  from , let’s say shift is  which is number of bits should move right to get . If we find distances to get lower multiplicity of them and get rid of type 1 and 2 weak keys , we find shifts to avoid having similar columns in  and

Table 1: distances of polynomial

Table 2.

Initial distances and multiplicity

Table 3.

Initial shifts

2.Get the bits which should be flipped  lets say our threshold=3 then we would take  as 14-11=3 and recompute distances also from (11-17)%47=41 , (11-14)%47=44 so it will also help us against type 3 weak keys  and  as (14-44)%47=44

3.Create zones . Red zone is distances which should not be met for new bits which are distances with multiplicity >=threshold-2 as using one distance we can get up to  two points by subtracting and adding.

Table 4.

Distance and multiplicity (first iteration)

Also, multiplicity >=threshold-1 red zone for shifts should be created

Table 5.

Shifts (first iteration)

4.Create blacklist, which is for red zone adding and subtracting distance from non-zero points and adding to non-zero points of  distances from shift red.

Blacklist:[0,3,7,10,11,14,17,20,24,27,30,33,34,37,41,44]

5.Find safe bit that is not in the list of non-zero bits and not in blacklist. The first bit can be x. Then we update multiplicity and red zones (do not compute everything from start , just add values created by new bit). And repeat steps 3-5 for remaining bits.

Table 6: distance and multiplicity (second iteration)

Table 7.

Shifts (second iteration)

Blacklist:[0,3,4,7,10,11,13,14,16,17,18,20,21,24,27,28,30,31,33,34,37,40,41,43,44,45,46]

So the next bit will be  and our new key=

Table 8.

Distance and multiplicity (final)

Table 9.

Shifts (final)

Testing and results

Tests were done on BIKE reference implementation version 5.2 with BIKE-Flip decoder on [10]. Security level=128, r=12323,  and t=134.

Table 10.

Result for Type 1 and 2 weak keys

To see results let’s look at distance multiplicities and count of distances as there are many distances so it will be too big to place here (Table 6.12 and Table 6.13)

Table 11.

Multiplicity and distances count for type 1 before transformation

High multiplicities cause decoding failure and it is main way how weak keys are created.

Table 12.

Multiplicity and distances count for type 1 after transformation

After transformation there is no high multiplicity , so there should not be any fluctuations. Threshold is five , so function eliminated all multiplicities higher than five.

Table 13.

Result for Type 3 weak keys

Lets look at shift counts.

Table 14.

Shifts and distances count for type 3 before transformation

Table 15.

Shifts and distances count for type 3 after transformation

Threshold is five so function got rid of every multiplicity equal or more than five.

Conclusion

BIKE remains a strong candidate for future standardization as a post-quantum key encapsulation mechanism. Therefore, it is essential to thoroughly investigate and mitigate all potential vulnerabilities. This paper proposes an efficient algorithm for detecting and transforming weak keys into normal ones, thereby reducing the decoder failure rate without requiring full key regeneration. Future research should focus on addressing error floors—another contributing factor to high DFR—as well as on further enhancing and optimizing decoders to ensure both security and performance in practical deployments.

References:

1. P. Shor, “Algorithms for quantum computation: Discrete logarithms and factoring,” Proceedings of 35th Annual Symposium on Foundations of Computer Science, 10 1996.
2. D. Castelvecchi, “Ibm releases first-ever 1,000-qubit quantum chip,”Dec 2023. [Online]. Available: https://www.nature.com/articles/d41586-023-03854 1#:∼:text=The%20company%20announces%20its%20latest,approach%20to%20error%20correction.&text=IBM%20has%20unveiled%20the%20first,bits%20in%20an%20ordinary%20computer.
3. T. L. Computer Security Division, “Post-quantum cryptography: Csrc.” [Online]. Available: https://csrc.nist.gov/Projects/Post-Quantum-Cryptography
4. M. Baldi, “Ldpc codes in the mceliece cryptosystem: attacks and countermeasures,” 09 2007.
5. R. Misoczki, J.-P. Tillich, N. Sendrier, and P. S. L. M. Barreto, “Mdpc-mceliece: New mceliece variants from moderate density parity-check codes,” in 2013 IEEE International Symposium on Information Theory,2013, pp. 2069–2073.
6. Q. Guo, T. Johansson, and P. Stankovski, “A key recovery attack on mdpc with cca security using decoding errors,” 12 2016, pp. 789–815.
7. N. Drucker, S. Gueron, D. Kostic, and E. Persichetti, “On the applicability of the fujisaki-okamoto transformation to the bike kem,” Cryptology ePrint Archive, Paper 2020/510, 2020, https://eprint.iacr.org/2020/510. [Online]. Available: https://eprint.iacr.org/2020/510
8. N. Sendrier and V. Vasseur, “About low dfr for qc-mdpc decoding,” Cryptology ePrint Archive, Paper 2019/1434, 2019, https://eprint.iacr.org/2019/1434. [Online]. Available: https://eprint.iacr.org/2019/1434
9. Q. Guo, T. Johansson, and P. Stankovski Wagner, “A key recovery reaction attack on qc-mdpc,” IEEE Transactions on Information Theory,vol. 65, no. 3, pp. 1845–1861, 2019.
10. [Online]. Available: https://bikesuite.org/
11. Nilsson, I. E. Bocharova, B. D. Kudryashov, and T. Johansson, “A weighted bit flipping decoder for qc-mdpc-based cryptosystems,” 2021 IEEE International Symposium on Information Theory (ISIT), pp. 1266–1271, 2021. [Online]. Available: https://api.semanticscholar.org/ CorpusID:234797761
12. T. B. Paiva and R. Terada, “Faster constant-time decoder for mdpc codes and applications to bike kem,” in Proceedings of CHES 2022. University of Sao Paulo, Brazil, 2022, code and data are publicly available. [Online]. Available: https://github.com/thalespaiva/pickyfix
13. M. R. Nosouhi, S. W. Shah, L. Pan, Y. Zolotavkin, A. Nanda, P. Gau- ravaram, and R. Doss, “Weak-key analysis for bike post-quantum key encapsulation mechanism,” IEEE Transactions on Information Forensics and Security, vol. 18, pp. 2160–2174, 2023.
14. N. Drucker, S. Gueron, and D. Kostic, “On constant-time qc-mdpc decoding with negligible failure rate,” Cryptology ePrint Archive, Paper 2019/1289, 2019, https://eprint.iacr.org/2019/1289. [Online]. Available: https://eprint.iacr.org/2019/1289
15. N. Aydin, B. Yildiz, and S. Uludag, “A class of weak keys for the qc-mdpc cryptosystem,” in 2020 Algebraic and Combinatorial Coding Theory (ACCT), 2020, pp. 1–4.
16. N. Sendrier and V. Vasseur, “On the Existence of Weak Keys for QC-MDPC Decoding,” Oct. 2020, working paper or preprint. [Online].  Available: https://inria.hal.science/hal-03139708
17. D. J. Costello and G. D. Forney, “Channel coding: The road to channel capacity,” Proceedings of the IEEE, vol. 95, no. 6, pp. 1150–1177, 2007.
18. C. G¨uneri, S. Ling, and B. ¨Ozkaya, “Quasi-cyclic codes,” 07 2020.
19. “Hamming weight.” [Online]. Available: https://www.oxfordreference.com/view/10.1093/oi/authority.20110803095918613
20. M. R. Nosouhi, S. W. A. Shah, L. Pan, and R. Doss, “Bit flipping key encapsulation for the post-quantum era,” IEEE Access, vol. 11, pp.56 181–56 195, 2023.
21. N. Drucker, S. Gueron, and D. Kostic, “Qc-mdpc decoders with several shades of gray,” Cryptology ePrint Archive, Paper 2019/1423, 2019,https://eprint.iacr.org/2019/1423.[Online]. Available: https://eprint.iacr.org/2019/1423