A provably masked implementation of BIKE Key Encapsulation Mechanism

Loïc Demange; Mélissa Rossi

doi:10.62056/aesgvua5v

A provably masked implementation of BIKE Key Encapsulation Mechanism

Authors

Loïc Demange, Mélissa Rossi

Loïc Demange

Thales Gennevilliers, France
Inria Paris, France
ldemange-research at etik dot com

Mélissa Rossi

ANSSI, France
melissa dot rossi at ssi dot gouv dot fr

Keywords: BIKE PQC Side-Channel countermeasure Provable high-order masking $d$-probing model

Abstract

BIKE is a post-quantum key encapsulation mechanism (KEM) selected for the 4th round of the NIST's standardization campaign. It relies on the hardness of the syndrome decoding problem for quasi-cyclic codes and on the indistinguishability of the public key from a random element, and provides the most competitive performance among round 4 candidates, which makes it relevant for future real-world use cases. Analyzing its side-channel resistance has been highly encouraged by the community and several works have already outlined various side-channel weaknesses and proposed ad-hoc countermeasures. However, in contrast to the well-documented research line on masking lattice-based algorithms, the possibility of generically protecting code-based algorithms by masking has only been marginally studied in a 2016 paper by Chen et al. in SAC 2015. At this stage of the standardization campaign, it is important to assess the possibility of fully masking BIKE scheme and the resulting cost in terms of performances.

In this work, we provide the first high-order masked implementation of a code-based algorithm. We had to tackle many issues such as finding proper ways to handle large sparse polynomials, masking the key-generation algorithm or keeping the benefit of the bitslicing. In this paper, we present all the gadgets necessary to provide a fully masked implementation of BIKE, we discuss our different implementation choices and we propose a full proof of masking in the Ishai Sahai and Wagner (Crypto 2003) model.

More practically, we also provide an open C-code masked implementation of the key-generation, encapsulation and decapsulation algorithms with extensive benchmarks. While the obtained performance is slower than existing masked lattice-based algorithms, we show that masking at order 1, 2, 3, 4 and 5 implies a performance penalty of x5.8, x14.2, x24.4, x38 and x55.6 compared to order 0 (unmasked and unoptimized BIKE). This scaling is encouraging and no Boolean to Arithmetic conversion has been used.

References

[ABB⁺22]

Nicolas Aragon, Paulo Barreto, Slim Bettaieb, Loic Bidoux, Olivier Blazy, Jean-Christophe Deneuville, Phillipe Gaborit, Shay Gueron, Tim Guneysu, Carlos Aguilar Melchor, Rafael Misoczki, Edoardo Persichetti, Nicolas Sendrier, Jean-Pierre Tillich, Gilles Zémor, Valentin Vasseur, Santosh Ghosh, and Jan Richter-Brokmann. BIKE. Technical Report, National Institute of Standards and Technology, 2022.

Google Scholar ePrint

[ABC⁺23]

Melissa Azouaoui, Olivier Bronchain, Gaëtan Cassiers, Clément Hoffmann, Yulia Kuzovkova, Joost Renes, Tobias Schneider, Markus Schönauer, François-Xavier Standaert, and Christine van Vredendaal. Protecting dilithium against leakage: revisited sensitivity analysis and improved implementations. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2023(4):58–79, Aug. 2023. https://doi.org/10.46586/tches.v2023.i4.58-79.

Google Scholar ePrint

[Ale03]

Michael Alekhnovich. More on average case vs approximation complexity. In 44th FOCS, 298–307. October 2003. IEEE Computer Society Press. https://doi.org/10.1109/SFCS.2003.1238204.

Google Scholar ePrint

[BAA⁺19]

Nina Bindel, Sedat Akleylek, Erdem Alkim, Paulo S. L. M. Barreto, Johannes Buchmann, Edward Eaton, Gus Gutoski, Juliane Kramer, Patrick Longa, Harun Polat, Jefferson E. Ricardini, and Gustavo Zanon. qTESLA. Technical Report, National Institute of Standards and Technology, 2019.

Google Scholar ePrint

[BBD⁺16]

Gilles Barthe, Sonia Belaïd, François Dupressoir, Pierre-Alain Fouque, Benjamin Grégoire, Pierre-Yves Strub, and Rébecca Zucchini. Strong non-interference and type-directed higher-order masking. In Edgar R. Weippl, Stefan Katzenbeisser, Christopher Kruegel, Andrew C. Myers, and Shai Halevi, editors, ACM CCS 2016, 116–129. October 2016. ACM Press. https://doi.org/10.1145/2976749.2978427.

Google Scholar ePrint

[BBE⁺18]

Gilles Barthe, Sonia Belaïd, Thomas Espitau, Pierre-Alain Fouque, Benjamin Grégoire, Mélissa Rossi, and Mehdi Tibouchi. Masking the GLP lattice-based signature scheme at any order. In Jesper Buus Nielsen and Vincent Rijmen, editors, EUROCRYPT 2018, Part II, volume 10821 of LNCS, 354–384. April / May 2018. Springer, Heidelberg. https://doi.org/10.1007/978-3-319-78375-8_12.

Google Scholar ePrint

[BGR⁺21]

Joppe W. Bos, Marc Gourjon, Joost Renes, Tobias Schneider, and Christine van Vredendaal. Masking kyber: first- and higher-order implementations. IACR TCHES, 2021(4):173–214, 2021. https://doi.org/10.46586/tches.v2021.i4.173-214.

Google Scholar ePrint

[BMvT78]

E. Berlekamp, R. McEliece, and H. van Tilborg. On the inherent intractability of certain coding problems (corresp.). IEEE Transactions on Information Theory, 24(3):384–386, 1978. https://doi.org/10.1109/TIT.1978.1055873.

Google Scholar ePrint

[BOG20]

Mario Bischof, Tobias Oder, and Tim Güneysu. Efficient Microcontroller Implementation of BIKE. In Emil Simion and Rémi Géraud-Stewart, editors, Innovative Security Solutions for Information Technology and Communications, 34–49. Cham, 2020. Springer International Publishing. https://doi.org/10.1007/978-3-030-41025-4_3.

Google Scholar ePrint

[CARG23]

Agathe Cheriere, Nicolas Aragon, Tania Richmond, and Benoît Gérard. Bike key-recovery: combining power consumption analysis and information-set decoding. 2023.

Google Scholar ePrint

[CCK21]

Ming-Shing Chen, Tung Chou, and Markus Krausz. Optimizing BIKE for the intel haswell and ARM cortex-M4. IACR TCHES, 2021(3):97–124, 2021. https://doi.org/10.46586/tches.v2021.i3.97-124.

Google Scholar ePrint

[CEvMS16]

Cong Chen, Thomas Eisenbarth, Ingo von Maurich, and Rainer Steinwandt. Masking large keys in hardware: A masked implementation of McEliece. In Orr Dunkelman and Liam Keliher, editors, SAC 2015, volume 9566 of LNCS, 293–309. August 2016. Springer, Heidelberg. https://doi.org/10.1007/978-3-319-31301-6_18.

Google Scholar ePrint

[CGKT22]

Ming-Shing Chen, Tim Güneysu, Markus Krausz, and Jan Philipp Thoma. Carry-less to BIKE faster. In Giuseppe Ateniese and Daniele Venturi, editors, ACNS 22, volume 13269 of LNCS, 833–852. June 2022. Springer, Heidelberg. https://doi.org/10.1007/978-3-031-09234-3_41.

Google Scholar ePrint

[CGTV15]

Jean-Sébastien Coron, Johann Großschädl, Mehdi Tibouchi, and Praveen Kumar Vadnala. Conversion from arithmetic to Boolean masking with logarithmic complexity. In Gregor Leander, editor, FSE 2015, volume 9054 of LNCS, 130–149. March 2015. Springer, Heidelberg. https://doi.org/10.1007/978-3-662-48116-5_7.

Google Scholar ePrint

[CGV14]

Jean-Sébastien Coron, Johann Großschädl, and Praveen Kumar Vadnala. Secure conversion between Boolean and arithmetic masking of any order. In Lejla Batina and Matthew Robshaw, editors, CHES 2014, volume 8731 of LNCS, 188–205. September 2014. Springer, Heidelberg. https://doi.org/10.1007/978-3-662-44709-3_11.

Google Scholar ePrint

[Cho16]

Tung Chou. QcBits: constant-time small-key code-based cryptography. In Benedikt Gierlichs and Axel Y. Poschmann, editors, CHES 2016, volume 9813 of LNCS, 280–300. August 2016. Springer, Heidelberg. https://doi.org/10.1007/978-3-662-53140-2_14.

Google Scholar ePrint

[CJRR99]

Suresh Chari, Charanjit S. Jutla, Josyula R. Rao, and Pankaj Rohatgi. Towards sound approaches to counteract power-analysis attacks. In Michael J. Wiener, editor, CRYPTO'99, volume 1666 of LNCS, 398–412. August 1999. Springer, Heidelberg. https://doi.org/10.1007/3-540-48405-1_26.

Google Scholar ePrint

[Cor14]

Jean-Sébastien Coron. Higher order masking of look-up tables. In Phong Q. Nguyen and Elisabeth Oswald, editors, EUROCRYPT 2014, volume 8441 of LNCS, 441–458. May 2014. Springer, Heidelberg. https://doi.org/10.1007/978-3-642-55220-5_25.

Google Scholar ePrint

[Cor17]

Jean-Sébastien Coron. High-order conversion from Boolean to arithmetic masking. In Wieland Fischer and Naofumi Homma, editors, CHES 2017, volume 10529 of LNCS, 93–114. September 2017. Springer, Heidelberg. https://doi.org/10.1007/978-3-319-66787-4_5.

Google Scholar ePrint

[CPRR14]

Jean-Sébastien Coron, Emmanuel Prouff, Matthieu Rivain, and Thomas Roche. Higher-order side channel security and mask refreshing. In Shiho Moriai, editor, FSE 2013, volume 8424 of LNCS, 410–424. March 2014. Springer, Heidelberg. https://doi.org/10.1007/978-3-662-43933-3_21.

Google Scholar ePrint

[DDF14]

Alexandre Duc, Stefan Dziembowski, and Sebastian Faust. Unifying leakage models: from probing attacks to noisy leakage. In Phong Q. Nguyen and Elisabeth Oswald, editors, EUROCRYPT 2014, volume 8441 of LNCS, 423–440. May 2014. Springer, Heidelberg. https://doi.org/10.1007/978-3-642-55220-5_24.

Google Scholar ePrint

[DG19]

Nir Drucker and Shay Gueron. A toolbox for software optimization of QC-MDPC code-based cryptosystems. Journal of Cryptographic Engineering, 9(4):341–357, November 2019. https://doi.org/10.1007/s13389-018-00200-4.

Google Scholar ePrint

[DHP⁺22]

Jan-Pieter D’Anvers, Daniel Heinz, Peter Pessl, Michiel Van Beirendonck, and Ingrid Verbauwhede. Higher-order masked ciphertext comparison for lattice-based cryptography. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2022(2):115–139, Feb. 2022. https://doi.org/10.46586/tches.v2022.i2.115-139.

Google Scholar ePrint

[DKR⁺20]

Jan-Pieter D'Anvers, Angshuman Karmakar, Sujoy Sinha Roy, Frederik Vercauteren, Jose Maria Bermudo Mera, Michiel Van Beirendonck, and Andrea Basso. SABER. Technical Report, National Institute of Standards and Technology, 2020.

Google Scholar ePrint

[FO99]

Eiichiro Fujisaki and Tatsuaki Okamoto. Secure integration of asymmetric and symmetric encryption schemes. In Michael J. Wiener, editor, CRYPTO'99, volume 1666 of LNCS, 537–554. August 1999. Springer, Heidelberg. https://doi.org/10.1007/3-540-48405-1_34.

Google Scholar ePrint

[GAB19]

Antonio Guimarães, Diego F. Aranha, and Edson Borin. Optimized implementation of QC-MDPC code-based cryptography. Concurrency and Computation: Practice and Experience, 31(18):e5089, 2019. https://doi.org/https://doi.org/10.1002/cpe.5089.

Google Scholar ePrint

[Gal62]

R. Gallager. Low-density parity-check codes. IRE Transactions on Information Theory, 8(1):21–28, 1962. https://doi.org/10.1109/TIT.1962.1057683.

Google Scholar ePrint

[GHJ⁺22]

Qian Guo, Clemens Hlauschek, Thomas Johansson, Norman Lahr, Alexander Nilsson, and Robin Leander Schröder. Don’t reject this: key-recovery timing attacks due to rejection-sampling in hqc and bike. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2022(3):223–263, Jun. 2022. https://doi.org/10.46586/tches.v2022.i3.223-263.

Google Scholar ePrint

[GJS16]

Qian Guo, Thomas Johansson, and Paul Stankovski. A key recovery attack on MDPC with CCA security using decoding errors. In Jung Hee Cheon and Tsuyoshi Takagi, editors, ASIACRYPT 2016, Part I, volume 10031 of LNCS, 789–815. December 2016. Springer, Heidelberg. https://doi.org/10.1007/978-3-662-53887-6_29.

Google Scholar ePrint

[GR20]

François Gérard and Mélissa Rossi. An Efficient and Provable Masked Implementation of qTESLA, pages 74–91. Springer International Publishing, 03 2020. https://doi.org/10.1007/978-3-030-42068-0_5.

Google Scholar ePrint

[HHK17]

Dennis Hofheinz, Kathrin Hövelmanns, and Eike Kiltz. A modular analysis of the Fujisaki-Okamoto transformation. In Yael Kalai and Leonid Reyzin, editors, TCC 2017, Part I, volume 10677 of LNCS, 341–371. November 2017. Springer, Heidelberg. https://doi.org/10.1007/978-3-319-70500-2_12.

Google Scholar ePrint

[ISW03]

Yuval Ishai, Amit Sahai, and David Wagner. Private circuits: securing hardware against probing attacks. In Dan Boneh, editor, CRYPTO 2003, volume 2729 of LNCS, 463–481. August 2003. Springer, Heidelberg. https://doi.org/10.1007/978-3-540-45146-4_27.

Google Scholar ePrint

[KDVB⁺22]

Suparna Kundu, Jan-Pieter D'Anvers, Michiel Van Beirendonck, Angshuman Karmakar, and Ingrid Verbauwhede. Higher-order masked saber. In Clemente Galdi and Stanislaw Jarecki, editors, Security and Cryptography for Networks, 93–116. Cham, 2022. Springer International Publishing. https://doi.org/?

Google Scholar ePrint

[KLRBG22]

Markus Krausz, Georg Land, Jan Richter-Brockmann, and Tim Güneysu. Efficiently masking polynomial inversion at arbitrary order. In Jung Hee Cheon and Thomas Johansson, editors, Post-Quantum Cryptography, 309–326. Cham, 2022. Springer International Publishing. https://doi.org/?

Google Scholar ePrint

[KLRBG23]

Markus Krausz, Georg Land, Jan Richter-Brockmann, and Tim Güneysu. A holistic approach towards side-channel secure fixed-weight polynomial sampling. In Alexandra Boldyreva and Vladimir Kolesnikov, editors, Public-Key Cryptography – PKC 2023, 94–124. Cham, 2023. Springer Nature Switzerland. https://doi.org/?

Google Scholar ePrint

[LDK⁺22]

Vadim Lyubashevsky, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Peter Schwabe, Gregor Seiler, Damien Stehlé, and Shi Bai. CRYSTALS-DILITHIUM. Technical Report, National Institute of Standards and Technology, 2022.

Google Scholar ePrint

[Lem19]

Daniel Lemire. Fast random integer generation in an interval. ACM Transactions on Modeling and Computer Simulation, 29(1):1–12, jan 2019. https://doi.org/10.1145/3230636.

Google Scholar ePrint

[MOG15]

Ingo Von Maurich, Tobias Oder, and Tim Güneysu. Implementing QC-MDPC McEliece Encryption. ACM Trans. Embed. Comput. Syst., April 2015. https://doi.org/10.1145/2700102.

Google Scholar ePrint

[MTSB13]

Rafael Misoczki, Jean-Pierre Tillich, Nicolas Sendrier, and Paulo S. L. M. Barreto. Mdpc-mceliece: new mceliece variants from moderate density parity-check codes. In 2013 IEEE International Symposium on Information Theory, volume, 2069–2073. 2013. https://doi.org/10.1109/ISIT.2013.6620590.

Google Scholar ePrint

[Nie86]

H. Niederreiter. Knapsack-type cryptosystems and algebraic coding theory. Problems of Control and Information Theory, 15(2):159–166, 1986. https://doi.org/?

Google Scholar ePrint

[RHHM17]

Melissa Rossi, Mike Hamburg, Michael Hutter, and Mark E. Marson. A side-channel assisted cryptanalytic attack against QcBits. In Wieland Fischer and Naofumi Homma, editors, CHES 2017, volume 10529 of LNCS, 3–23. September 2017. Springer, Heidelberg. https://doi.org/10.1007/978-3-319-66787-4_1.

Google Scholar ePrint

[RP10]

Matthieu Rivain and Emmanuel Prouff. Provably secure higher-order masking of AES. In Stefan Mangard and François-Xavier Standaert, editors, CHES 2010, volume 6225 of LNCS, 413–427. August 2010. Springer, Heidelberg. https://doi.org/10.1007/978-3-642-15031-9_28.

Google Scholar ePrint

[SAB⁺22]

Peter Schwabe, Roberto Avanzi, Joppe Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, John M. Schanck, Gregor Seiler, Damien Stehlé, and Jintai Ding. CRYSTALS-KYBER. Technical Report, National Institute of Standards and Technology, 2022.

Google Scholar ePrint

[Sen21]

Nicolas Sendrier. Secure sampling of constant-weight words ? application to bike. 2021.

Google Scholar ePrint

[SKC⁺19]

Bo-Yeon Sim, Jihoon Kwon, Kyu Young Choi, Jihoon Cho, Aesun Park, and Dong-Guk Han. Novel side-channel attacks on quasi-cyclic code-based cryptography. IACR TCHES, 2019(4):180–212, 2019. https://doi.org/10.13154/tches.v2019.i4.180-212.

Google Scholar ePrint

[vMG14]

Ingo von Maurich and Tim Güneysu. Towards side-channel resistant implementations of QC-MDPC McEliece encryption on constrained devices. In Michele Mosca, editor, Post-Quantum Cryptography - 6th International Workshop, PQCrypto 2014, 266–282. October 2014. Springer, Heidelberg. https://doi.org/10.1007/978-3-319-11659-4_16.

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/aesgvua5v

History

Submitted: 2024-01-09
Accepted: 2024-03-05
Published: 2024-04-09

How to cite

Loïc Demange and Mélissa Rossi, "A provably masked implementation of BIKE Key Encapsulation Mechanism," IACR Communications in Cryptology, vol. 1, no. 1, Apr 09, 2024, doi: 10.62056/aesgvua5v.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.

@article{CiC-1-1-23,
    author = "Demange, Loïc and Rossi, Mélissa",
    journal = "{IACR} {C}ommunications in {C}ryptology",
    publisher = "{I}nternational {A}ssociation for {C}ryptologic {R}esearch",
    title = "A provably masked implementation of {BIKE} Key Encapsulation Mechanism",
    volume = "1",
    number = "1",
    date = "2024-04-09",
    year = "2024",
    issn = "3006-5496",
    doi = "10.62056/aesgvua5v"
}

TY - JOUR
AU - Demange, Loïc
AU - Rossi, Mélissa
PY  - 2024
TI  - A provably masked implementation of BIKE Key Encapsulation Mechanism
JF  - IACR Communications in Cryptology
JA  - CIC
VL  - 1
IS  - 1
DO  - 10.62056/aesgvua5v
UR  - https://doi.org/10.62056/aesgvua5v
AB  - <p>BIKE is a post-quantum key encapsulation mechanism (KEM) selected for the 4th round of the NIST's standardization campaign. It relies on the hardness of the syndrome decoding problem for quasi-cyclic codes and on the indistinguishability of the public key from a random element, and provides the most competitive performance among round 4 candidates, which makes it relevant for future real-world use cases. Analyzing its side-channel resistance has been highly encouraged by the community and several works have already outlined various side-channel weaknesses and proposed ad-hoc countermeasures. However, in contrast to the well-documented research line on masking lattice-based algorithms, the possibility of generically protecting code-based algorithms by masking has only been marginally studied in a 2016 paper by Chen et al. in SAC 2015. At this stage of the standardization campaign, it is important to assess the possibility of fully masking BIKE scheme and the resulting cost in terms of performances.</p><p>In this work, we provide the first high-order masked implementation of a code-based algorithm. We had to tackle many issues such as finding proper ways to handle large sparse polynomials, masking the key-generation algorithm or keeping the benefit of the bitslicing. In this paper, we present all the gadgets necessary to provide a fully masked implementation of BIKE, we discuss our different implementation choices and we propose a full proof of masking in the Ishai Sahai and Wagner (Crypto 2003) model.</p><p>More practically, we also provide an open C-code masked implementation of the key-generation, encapsulation and decapsulation algorithms with extensive benchmarks. While the obtained performance is slower than existing masked lattice-based algorithms, we show that masking at order 1, 2, 3, 4 and 5 implies a performance penalty of x5.8, x14.2, x24.4, x38 and x55.6 compared to order 0 (unmasked and unoptimized BIKE). This scaling is encouraging and no Boolean to Arithmetic conversion has been used.</p>
ER  -

Loïc Demange and Mélissa Rossi, "A provably masked implementation of BIKE Key Encapsulation Mechanism," IACR Communications in Cryptology, vol. 1, no. 1, Apr 09, 2024, doi: 10.62056/aesgvua5v.