Efficient Boolean-to-Arithmetic Mask Conversion in Hardware
Authors
Aein Rezaei Shahmirzadi, Michael Hutter
Aein Rezaei Shahmirzadi
PQShield, Oxford, UK
aein dot shahmirzadi at pqshield dot com
aein dot shahmirzadi at pqshield dot com
Michael Hutter
PQShield, Oxford, UK
michael dot hutter at pqshield dot com
michael dot hutter at pqshield dot com
Keywords:
Secure Mask Conversion
Mixed Boolean Arithmetic (MBA)
Boolean-to-Arithmetic (B2A)
Arithmetic-to-Boolean (A2B)
Side-Channel Analysis
DPA Countermeasures
Hardware Implementation
Physical Security
Abstract
Masking schemes are key in thwarting side-channel attacks due to their robust theoretical foundation. Transitioning from Boolean to arithmetic (B2A) masking is a necessary step in various cryptography schemes, including hash functions, ARX-based ciphers, and lattice-based cryptography. While there exists a significant body of research focusing on B2A software implementations, studies pertaining to hardware implementations are quite limited, with the majority dedicated solely to creating efficient Boolean masked adders. In this paper, we present first- and second-order secure hardware implementations to perform B2A mask conversion efficiently without using masked adder structures. We first introduce a first-order secure low-latency gadget that executes a B2A2k in a single cycle. Furthermore, we propose a second-order secure B2A2k gadget that has a latency of only 4 clock cycles. Both gadgets are independent of the input word size k. We then show how these new primitives lead to improved B2Aq hardware implementations that perform a B2A mask conversion of integers modulo an arbitrary number. Our results show that our new gadgets outperform comparable solutions by more than a magnitude in terms of resource requirements and are at least 3 times faster in terms of latency and throughput. All gadgets have been formally verified and proven secure in the glitch-robust PINI security model. We additionally confirm the security of our gadgets on an FPGA platform using practical TVLA tests.
References
[AHMP10]
Jean-Philippe Aumasson, Luca Henzen, Willi Meier, and Raphael C.-W. Phan. SHA-3 Proposal BLAKE. https://131002.net/blake. December 2010.
[BBD+15]
Gilles Barthe, Sonia Belaïd, François Dupressoir, Pierre-Alain Fouque, Benjamin Grégoire, and Pierre-Yves Strub. Verified Proofs of Higher-Order Masking. In EUROCRYPT 2015, volume 9056 of LNCS, pages 457–485, Sofia, Bulgaria. April 2015. Springer, Heidelberg. DOI: 10.1007/978-3-662-46800-5_18
[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 CCS 2016, pages 116–129, Vienna, Austria. October 2016. ACM. DOI: 10.1145/2976749.2978427
[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 EUROCRYPT 2018, volume 10821 of LNCS, pages 354–384, Tel Aviv, Israel. April 2018. Springer, Cham. DOI: 10.1007/978-3-319-78375-8_12
[BC22]
Olivier Bronchain and Gaëtan Cassiers. Bitslicing Arithmetic/Boolean Masking Conversions for Fun and Profit with Application to Lattice-Based KEMs. IACR Transactions on Cryptographic Hardware and Embedded Systems (TCHES), 2022(4):553–588, 2022. DOI: 10.46586/TCHES.V2022.I4.553-588
[BCZ18]
Luk Bettale, Jean-Sébastien Coron, and Rina Zeitoun. Improved High-Order Conversion From Boolean to Arithmetic Masking. IACR Transactions on Cryptographic Hardware and Embedded Systems (TCHES), 2018(2):22–45, 2018. DOI: 10.13154/TCHES.V2018.I2.22-45
[BDCU17]
Alex Biryukov, Daniel Dinu, Yann Le Corre, and Aleksei Udovenko. Optimal First-Order Boolean Masking for Embedded IoT Devices. In CARDIS 2017, volume 10728 of LNCS, pages 22–41, Lugano, Switzerland. November 2017. Springer. DOI: 10.1007/978-3-319-75208-2_2
[BDH+21]
Shivam Bhasin, Jan-Pieter D'Anvers, Daniel Heinz, Thomas Pöppelmann, and Michiel Van Beirendonck. Attacking and Defending Masked Polynomial Comparison for Lattice-Based Cryptography. IACR Transactions on Cryptographic Hardware and Embedded Systems (TCHES), 2021(3):334–359, 2021. DOI: 10.46586/TCHES.V2021.I3.334-359
[BDK+21]
Michiel Van Beirendonck, Jan-Pieter D'Anvers, Angshuman Karmakar, Josep Balasch, and Ingrid Verbauwhede. A Side-Channel-Resistant Implementation of SABER. ACM Journal on Emerging Technologies in Computing Systems (JETC), 17(2):1–26, 2021. DOI: 10.1145/3429983
[Ber08]
Daniel J. Bernstein. ChaCha, a Variant of Salsa20. In State of the Art of Stream Ciphers Workshop (SASC), pages 3–5, Lausanne, Switzerland. Februar 2008.
[BFG+17]
Josep Balasch, Sebastian Faust, Benedikt Gierlichs, Clara Paglialonga, and François-Xavier Standaert. Consolidating Inner Product Masking. In ASIACRYPT 2017, volume 10624 of LNCS, pages 724–754, Hong Kong, China. December 2017. Springer. DOI: 10.1007/978-3-319-70694-8_25
[BG22]
Florian Bache and Tim Güneysu. Boolean Masking for Arithmetic Additions at Arbitrary Order in Hardware. Applied Sciences, 12(5), 2022.
[BPO+20]
Florian Bache, Clara Paglialonga, Tobias Oder, Tobias Schneider, and Tim Güneysu. High-Speed Masking for Polynomial Comparison in Lattice-based KEMs. IACR Transactions on Cryptographic Hardware and Embedded Systems (TCHES), 2020(3):483–507, 2020. DOI: 10.13154/TCHES.V2020.I3.483-507
[Cas22]
Gaëtan Cassiers. Composable and Efficient Masking Schemes for Side-channel Secure Implementations. PhD thesis, Université Catholique de Louvain, June 2022.
[CG00]
Jean-Sébastien Coron and Louis Goubin. On Boolean and Arithmetic Masking against Differential Power Analysis. In Cryptographic Hardware and Embedded Systems (CHES), volume 1965 of LNCS, pages 231–237, Worcester, MA, USA. August 2000. Springer, Heidelberg. DOI: 10.1007/3-540-44499-8_18
[CGLS21]
Gaëtan Cassiers, Benjamin Grégoire, Itamar Levi, and François-Xavier Standaert. Hardware Private Circuits: From Trivial Composition to Full Verification. IEEE Transactions on Computers, 70(10):1677–1690, 2021. DOI: 10.1109/TC.2020.3022979
[CGM+23]
Gaëtan Cassiers, Barbara Gigerl, Stefan Mangard, Charles Momin, and Rishub Nagpal. Compress: Reducing Area and Latency of Masked Pipelined Circuits. IACR Cryptology ePrint Archive, Paper 2023/1600. 2023.
[CGMZ23]
Jean-Sébastien Coron, François Gérard, Simon Montoya, and Rina Zeitoun. High-order Polynomial Comparison and Masking Lattice-based Encryption. IACR Transactions on Cryptographic Hardware and Embedded Systems (TCHES), 2023(1):153–192, 2023. DOI: 10.46586/TCHES.V2023.I1.153-192
[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 FSE 2015, volume 8731 of LNCS, pages 130–149, Istanbul, Turkey. March 2015. Springer, Heidelberg. DOI: 10.1007/978-3-662-48116-5_7
[CGTZ23]
Jean-Sébastien Coron, François Gérard, Matthias Trannoy, and Rina Zeitoun. Improved Gadgets for the High-Order Masking of Dilithium. IACR Transactions on Cryptographic Hardware and Embedded Systems (TCHES), 2023(4):110–145, 2023. DOI: 10.46586/TCHES.V2023.I4.110-145
[CGV14]
Jean-Sébastien Coron, Johann Großschädl, and Praveen Kumar Vadnala. Secure Conversion between Boolean and Arithmetic Masking of Any Order. In Cryptographic Hardware and Embedded Systems (CHES), volume 8731 of LNCS, pages 188–205, Busan, South Korea. September 2014. Springer, Heidelberg. DOI: 10.1007/978-3-662-44709-3_11
[Cor17]
Jean-Sébastien Coron. Higher-Order Conversion from Boolean to Arithmetic Masking. In Cryptographic Hardware and Embedded Systems (CHES), volume 10529 of LNCS, pages 93–114, Taipei, Taiwan. September 2017. Springer. DOI: 10.1007/978-3-319-66787-4_5
[CS20]
Gaëtan Cassiers and François-Xavier Standaert. Trivially and Efficiently Composing Masked Gadgets With Probe Isolating Non-Interference. IEEE Transactions on Information Forensics and Security, 15:2542–2555, 2020. DOI: 10.1109/TIFS.2020.2971153
[FBR+22]
Tim Fritzmann, Michiel Van Beirendonck, Debapriya Basu Roy, Patrick Karl, Thomas Schamberger, Ingrid Verbauwhede, and Georg Sigl. Masked Accelerators and Instruction Set Extensions for Post-Quantum Cryptography. IACR Transactions on Cryptographic Hardware and Embedded Systems (TCHES), 2022(1):414–460, 2022. DOI: 10.46586/TCHES.V2022.I1.414-460
[FGP+18]
Sebastian Faust, Vincent Grosso, Santos Merino Del Pozo, Clara Paglialonga, and François-Xavier Standaert. Composable Masking Schemes in the Presence of Physical Defaults & the Robust Probing Model. IACR Transactions on Cryptographic Hardware and Embedded Systems (TCHES), 2018(3):89–120, 2018. DOI: 10.13154/TCHES.V2018.I3.89-120
[FLS+10]
Niels Ferguson, Stefan Lucks, Bruce Schneier, Doug Whiting, Mihir Bellare, Tadayoshi Kohno, Jon Callas, and Jesse Walker. The Skein Hash Function Family. https://www.schneier.com/wp-content/uploads/2015/01/skein.pdf. October 2010.
[GJJR11]
Gilbert Goodwill, Benjamin Jun, Josh Jaffe, and Pankaj Rohatgi. A Testing Methodology for Side-Channel Resistance Validation. Non-Invasive Attack Testing (NIAT) Workshop. https://csrc.nist.gov/csrc/media/events/non-invasive-attack-testing-workshop/documents/08_goodwill.pdf. 2011.
[GJM+16]
Hannes Groß, Manuel Jelinek, Stefan Mangard, Thomas Unterluggauer, and Mario Werner. Concealing Secrets in Embedded Processors Designs. In CARDIS 2016, volume 10146 of LNCS, pages 89–104, Cannes, France. November 2016. Springer. DOI: 10.1007/978-3-319-54669-8_6
[GMK16]
Hannes Groß, Stefan Mangard, and Thomas Korak. Domain-Oriented Masking: Compact Masked Hardware Implementations with Arbitrary Protection Order. In Workshop on Theory of Implementation Security (TIS), Vienna, Austria. October 2016. ACM. DOI: 10.1145/2996366.2996426
[Gou01]
Louis Goubin. A Sound Method for Switching between Boolean and Arithmetic Masking. In Cryptographic Hardware and Embedded Systems (CHES), volume 2162 of LNCS, pages 3–15, Paris, France. May 2001. Springer, Heidelberg. DOI: 10.1007/3-540-44709-1_2
[GP99]
Louis Goubin and Jacques Patarin. DES and Differential Power Analysis. In Cryptographic Hardware and Embedded Systems (CHES), volume 1717 of LNCS, pages 158–172, Worcester, MA, USA. August 1999. Springer. DOI: 10.1007/3-540-48059-5_15
[GT02]
Jovan Dj. Golic and Christophe Tymen. Multiplicative Masking and Power Analysis of AES. In Cryptographic Hardware and Embedded Systems (CHES), volume 2523 of LNCS, pages 198–212, San Francisco, USA. August 2002. Springer. DOI: 10.1007/3-540-36400-5_16
[HT16]
Michael Hutter and Michael Tunstall. Constant Time Higher-Order Boolean-to-Arithmetic Masking. https://eprint.iacr.org/2016/1023. IACR Cryptology ePrint Archive, Paper 2016/1023. 2016.
[HT19]
Michael Hutter and Michael Tunstall. Constant-Time Higher-Order Boolean-to-Arithmetic Masking. Journal of Cryptographic Engineering, 9(2):173–184, 2019. DOI: 10.1007/S13389-018-0191-Z
[ISW03]
Yuval Ishai, Amit Sahai, and David A. Wagner. Private Circuits: Securing Hardware against Probing Attacks. In CRYPTO 2003, volume 2729 of LNCS, pages 463–481, Santa Barbara, California, USA. August 2003. Springer, Heidelberg. DOI: 10.1007/978-3-540-45146-4_27
[KJJ99]
Paul Kocher, Joshua Jaffe, and Benjamin Jun. Differential Power Analysis. In CRYPTO 1999, volume 1666 of LNCS, pages 388–397, Santa Barbara, California, USA. August 1999. Springer, Heidelberg. DOI: 10.1007/3-540-48405-1_25
[KMMS22]
David Knichel, Amir Moradi, Nicolai Müller, and Pascal Sasdrich. Automated Generation of Masked Hardware. IACR Transactions on Cryptographic Hardware and Embedded Systems (TCHES), 2022(1):589–629, 2022. DOI: 10.46586/TCHES.V2022.I1.589-629
[Kni23]
David Knichel. Formal Verification and Automated Masking of Cryptographic Hardware. PhD thesis, Ruhr University Bochum, Germany, September 2023.
[Koc96]
Paul Kocher. Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems. In CRYPTO 1996, volume 1109 of LNCS, pages 104–113, Santa Barbara, California, USA. August 1996. Springer, Heidelberg. DOI: 10.1007/3-540-68697-5_9
[KS73]
Peter M. Kogge and Harold S. Stone. A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence Equations. IEEE Transactions on Computers, 22(8):786–793, 1973. DOI: 10.1109/TC.1973.5009159
[KSM19]
Yuichi Komano, Hideo Shimizu, and Hideyuki Miyake. Integrative Acceleration of First-order Boolean Masking for Embedded IoT Devices. Journal of Information Processing, 27:585–592, 2019. DOI: 10.2197/IPSJJIP.27.585
[KSM20]
David Knichel, Pascal Sasdrich, and Amir Moradi. SILVER - Statistical Independence and Leakage Verification. In ASIACRYPT 2020, volume 12491 of LNCS, pages 787–816, Daejeon, South Korea. December 2020. Springer. DOI: 10.1007/978-3-030-64837-4_26
[MBR19]
Lauren De Meyer, Begül Bilgin, and Oscar Reparaz. Consolidating Security Notions in Hardware Masking. IACR Transactions on Cryptographic Hardware and Embedded Systems (TCHES), 2019(3):119–147, 2019. DOI: 10.13154/TCHES.V2019.I3.119-147
[MME10]
Amir Moradi, Oliver Mischke, and Thomas Eisenbarth. Correlation-Enhanced Power Analysis Collision Attack. In Cryptographic Hardware and Embedded Systems (CHES), volume 6225 of LNCS, pages 125–139, Santa Barbara, California, USA. August 2010. Springer. DOI: 10.1007/978-3-642-15031-9_9
[MPO05]
Stefan Mangard, Norbert Pramstaller, and Elisabeth Oswald. Successfully Attacking Masked AES Hardware Implementations. In Cryptographic Hardware and Embedded Systems (CHES), volume 3659 of LNCS, pages 157–171, Edinburgh, Scotland. August 2005. Springer. DOI: 10.1007/11545262_12
[NDKV24]
Quinten Norga, Jan-Pieter D'Anvers, Suparna Kundu, and Ingrid Verbauwhede. Mask Conversions for d+1 Shares in Hardware, with Application to Lattice-based PQC. https://eprint.iacr.org/archive/2024/114/20240126:091208. IACR Cryptology ePrint Archive, Paper 2024/114/20240126:091208. 2024.
[New]
NewAE. CW305 Artix FPGA Target. https://rtfm.newae.com/Targets.
[NRR06]
Svetla Nikova, Christian Rechberger, and Vincent Rijmen. Threshold Implementations Against Side-Channel Attacks and Glitches. In Information and Communications Security (ICICS), volume 4307 of LNCS, pages 529–545, Raleigh, NC, USA. December 2006. Springer, Heidelberg. DOI: 10.1007/11935308_38
[NW97]
Roger M. Needham and David J. Wheeler. TEA Extensions. Technical Report, Computer Laboratory, University of Cambridge. https://www.cix.co.uk/ klockstone/xtea.pdf. 1997.
[RBN+15]
Oscar Reparaz, Begül Bilgin, Svetla Nikova, Benedikt Gierlichs, and Ingrid Verbauwhede. Consolidating Masking Schemes. In CRYPTO 2015, volume 9215 of LNCS, pages 764–783, Santa Barbara, California, USA. August 2015. Springer. DOI: 10.1007/978-3-662-47989-6_37
[SM15]
Tobias Schneider and Amir Moradi. Leakage Assessment Methodology - A Clear Roadmap for Side-Channel Evaluations. In Cryptographic Hardware and Embedded Systems (CHES), volume 9293 of LNCS, pages 495–513, Saint Malo, France. September 2015. Springer. DOI: 10.1007/978-3-662-48324-4_25
[SMG15]
Tobias Schneider, Amir Moradi, and Tim Güneysu. Arithmetic Addition Over Boolean Masking—Towards First- and Second-Order Resistance in Hardware. In ACNS 2015, volume 9092 of LNCS, pages 559–578, St.Petersburg, Russia. June 2015. Springer, Heidelberg. DOI: 10.1007/978-3-319-28166-7_27
[SPOG19]
Tobias Schneider, Clara Paglialonga, Tobias Oder, and Tim Güneysu. Efficiently Masking Binomial Sampling at Arbitrary Orders for Lattice-Based Crypto. In PKC 2019, volume 11443 of LNCS, pages 534–564, Beijing, China. April 2019. Springer. DOI: 10.1007/978-3-030-17259-6_18
[WH17]
Yoo-Seung Won and Dong-Guk Han. Efficient Conversion Method from Arithmetic to Boolean Masking in Constrained Devices. In COSADE 2017, volume 10348 of LNCS, pages 120–137, Paris, France. April 2017. Springer. DOI: 10.1007/978-3-319-64647-3_8
PDF
History
Submitted: 2024-07-09
Accepted: 2024-09-02
Published: 2024-10-07
Accepted: 2024-09-02
Published: 2024-10-07
How to cite
Aein Rezaei Shahmirzadi and Michael Hutter, Efficient Boolean-to-Arithmetic Mask Conversion in Hardware. IACR Communications in Cryptology, vol. 1, no. 3, Oct 07, 2024, doi: 10.62056/a3c0l2isfg.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.