Inspector Gadget
A Toolbox for Fair Comparison of Masking Gadgets, Application to Crystals-Kyber Compression
Authors
Camille Mutschler, Laurent Imbert, Thomas Roche
Laurent Imbert
LIRMM, CNRS, Univ. Montpellier, Montpellier, France
laurent dot imbert at lirmm dot fr
laurent dot imbert at lirmm dot fr
Keywords:
foo
Abstract
We introduce InspectorGadget, an Open-Source Python-based software for assessing and comparing the complexity of masking gadgets. By providing a limited set of characteristics of a hardware platform, our tool allows to estimate the cost of a masking gadget in terms of cycle count equivalent and memory footprint. InspectorGadget is highly flexible. It enables the user to define her own estimation functions, as well as to expand the set of gadgets and predefined microcontrollers. As a case-study, we produce a fair comparison of several masked versions of Kyber compression function from the literature, together with novel alternatives automatically generated by our tool. Our results confirm that an interesting middle ground exists between theoretical performance measures (asymptotic complexity or operations count) and real implementations benchmarks (clock cycle accurate evaluations). InspectorGadget offers both simplicity and genericity while capturing the main performance-related parameters of a hardware platform.
References
[ACLZ20]
Dorian Amiet, Andreas Curiger, Lukas Leuenberger, and Paul Zbinden. Defeating NewHope with a Single Trace. In Jintai Ding and Jean-Pierre Tillich, editors, Post-Quantum Cryptography - 11th International Conference, PQCrypto 2020, pages 189–205. 2020. Springer, Heidelberg. DOI: 10.1007/978-3-030-44223-1_11
[BBC+19]
Gilles Barthe, Sonia Belaïd, Gaëtan Cassiers, Pierre-Alain Fouque, Benjamin Grégoire, and François-Xavier Standaert. maskVerif: Automated Verification of Higher-Order Masking in Presence of Physical Defaults. In Kazue Sako, Steve Schneider, and Peter Y. A. Ryan, editors, ESORICS 2019, Part I, volume 11735 of LNCS, pages 300–318. September 2019. Springer, Heidelberg. DOI: 10.1007/978-3-030-29959-0_15
[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, pages 116–129. October 2016. ACM Press. 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 Jesper Buus Nielsen and Vincent Rijmen, editors, EUROCRYPT 2018, Part II, volume 10821 of LNCS, pages 354–384. 2018. Springer, Heidelberg. DOI: 10.1007/978-3-319-78375-8_12
[BBYS22]
Ileana Buhan, Lejla Batina, Yuval Yarom, and Patrick Schaumont. SoK: Design Tools for Side-Channel-Aware Implementations. In Yuji Suga, Kouichi Sakurai, Xuhua Ding, and Kazue Sako, editors, ASIACCS 22, pages 756–770. 2022. ACM Press. DOI: 10.1145/3488932.3517415
[BC22]
Olivier Bronchain and Gaëtan Cassiers. Bitslicing Arithmetic/Boolean Masking Conversions for Fun and Profit with Application to Lattice-Based KEMs. IACR TCHES, 2022(4):553–588, 2022. DOI: 10.46586/tches.v2022.i4.553-588
[BDK+21]
Michiel Van Beirendonck, Jan-Pieter D'Anvers, Angshuman Karmakar, Josep Balasch, and Ingrid Verbauwhede. A Side-Channel-Resistant Implementation of SABER. ACM J. Emerg. Technol. Comput. Syst., 17(2):10:1–10:26, 2021. DOI: 10.1145/3429983
[BGG+20]
Gilles Barthe, Marc Gourjon, Benjamin Grégoire, Maximilian Orlt, Clara Paglialonga, and Lars Porth. Open source publication of complete leakage model, implementations and the verification tool. 2020.
[BGR18]
Sonia Belaïd, Dahmun Goudarzi, and Matthieu Rivain. Tight Private Circuits: Achieving Probing Security with the Least Refreshing. In Thomas Peyrin and Steven Galbraith, editors, ASIACRYPT 2018, Part II, volume 11273 of LNCS, pages 343–372. December 2018. Springer, Heidelberg. DOI: 10.1007/978-3-030-03329-3_12
[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://tches.iacr.org/index.php/TCHES/article/view/9064 DOI: 10.46586/tches.v2021.i4.173-214
[CGD18]
Yann Le Corre, Johann Großschädl, and Daniel Dinu. Micro-architectural Power Simulator for Leakage Assessment of Cryptographic Software on ARM Cortex-M3 Processors. In Junfeng Fan and Benedikt Gierlichs, editors, COSADE 2018, volume 10815 of LNCS, pages 82–98. April 2018. Springer, Heidelberg. DOI: 10.1007/978-3-319-89641-0_5
[CGMZ22]
Jean-Sébastien Coron, François Gérard, Simon Montoya, and Rina Zeitoun. High-order Table-based Conversion Algorithms and Masking Lattice-based Encryption. IACR TCHES, 2022(2):1–40, 2022. DOI: 10.46586/tches.v2022.i2.1-40
[CGMZ23]
Jean-Sébastien Coron, François Gérard, Simon Montoya, and Rina Zeitoun. High-order Polynomial Comparison and Masking Lattice-based Encryption. IACR 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 Gregor Leander, editor, FSE 2015, volume 9054 of LNCS, pages 130–149. March 2015. Springer, Heidelberg. DOI: 10.1007/978-3-662-48116-5_7
[CGTZ23a]
Jean-Sébastien Coron, François Gérard, Matthias Trannoy, and Rina Zeitoun. High-order masking of NTRU. IACR TCHES, 2023(2):180–211, 2023. DOI: 10.46586/tches.v2023.i2.180-211
[CGTZ23b]
Jean-Sébastien Coron, François Gérard, Matthias Trannoy, and Rina Zeitoun. Improved Gadgets for the High-Order Masking of Dilithium. IACR 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 Lejla Batina and Matthew Robshaw, editors, CHES 2014, volume 8731 of LNCS, pages 188–205. September 2014. Springer, Heidelberg. DOI: 10.1007/978-3-662-44709-3_11
[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, pages 398–412. August 1999. Springer, Heidelberg. DOI: 10.1007/3-540-48405-1_26
[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, pages 441–458. May 2014. Springer, Heidelberg. DOI: 10.1007/978-3-642-55220-5_25
[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, pages 410–424. March 2014. Springer, Heidelberg. DOI: 10.1007/978-3-662-43933-3_21
[CS18]
Gaëtan Cassiers and François-Xavier Standaert. Improved Bitslice Masking: from Optimized Non-Interference to Probe Isolation. https://eprint.iacr.org/2018/438. Cryptology ePrint Archive, Report 2018/438. 2018.
[CS20]
Gaetan Cassiers and François-Xavier Standaert. Trivially and Efficiently Composing Masked Gadgets With Probe Isolating Non-Interference. IEEE Transactions on Information Forensics and Security, PP:1-1, February 2020. DOI: 10.1109/TIFS.2020.2971153
[DKRV18]
Jan-Pieter D'Anvers, Angshuman Karmakar, Sujoy Sinha Roy, and Frederik Vercauteren. Saber: Module-LWR Based Key Exchange, CPA-Secure Encryption and CCA-Secure KEM. In Antoine Joux, Abderrahmane Nitaj, and Tajjeeddine Rachidi, editors, AFRICACRYPT 18, volume 10831 of LNCS, pages 282–305. May 2018. Springer, Heidelberg. DOI: 10.1007/978-3-319-89339-6_16
[EO19]
Scott Egerton and Elisabeth Oswald. GILES. 2019.
[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, pages 537–554. August 1999. Springer, Heidelberg. DOI: 10.1007/3-540-48405-1_34
[GHP+21]
Barbara Gigerl, Vedad Hadzic, Robert Primas, Stefan Mangard, and Roderick Bloem. Coco: Co-Design and Co-Verification of Masked Software Implementations on CPUs. In Michael Bailey and Rachel Greenstadt, editors, USENIX Security 2021, pages 1469–1468. August 2021. USENIX Association.
[GJN20]
Qian Guo, Thomas Johansson, and Alexander Nilsson. A Key-Recovery Timing Attack on Post-quantum Primitives Using the Fujisaki-Okamoto Transformation and Its Application on FrodoKEM. In Daniele Micciancio and Thomas Ristenpart, editors, CRYPTO 2020, Part II, volume 12171 of LNCS, pages 359–386. August 2020. Springer, Heidelberg. DOI: 10.1007/978-3-030-56880-1_13
[Gou01]
Louis Goubin. A Sound Method for Switching between Boolean and Arithmetic Masking. In Çetin Kaya Koç, David Naccache, and Christof Paar, editors, CHES 2001, volume 2162 of LNCS, pages 3–15. May 2001. Springer, Heidelberg. DOI: 10.1007/3-540-44709-1_2
[GZSW19]
Pengfei Gao, Jun Zhang, Fu Song, and Chao Wang. Verifying and Quantifying Side-channel Resistance of Masked Software Implementations. ACM Trans. Softw. Eng. Methodol., 28(3), July 2019. DOI: 10.1145/3330392
[HKL+22]
Daniel Heinz, Matthias J. Kannwischer, Georg Land, Thomas Pöppelmann, Peter Schwabe, and Amber Sprenkels. First-Order Masked Kyber on ARM Cortex-M4. https://eprint.iacr.org/2022/058. Cryptology ePrint Archive, Report 2022/058. 2022.
[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, pages 463–481. August 2003. Springer, Heidelberg. DOI: 10.1007/978-3-540-45146-4_27
[KDB+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 - 13th International Conference, SCN 2022, Amalfi, Italy, September 12-14, 2022, Proceedings, volume 13409 of Lecture Notes in Computer Science, pages 93–116. 2022. Springer. DOI: 10.1007/978-3-031-14791-3_5
[KS22]
Pantea Kiaei and Patrick Schaumont. SoC Root Canal! Root Cause Analysis of Power Side-Channel Leakage in System-on-Chip Designs. IACR TCHES, 2022(4):751–773, 2022. DOI: 10.46586/tches.v2022.i4.751-773
[KSM20]
David Knichel, Pascal Sasdrich, and Amir Moradi. SILVER - Statistical Independence and Leakage Verification. In Shiho Moriai and Huaxiong Wang, editors, ASIACRYPT 2020, Part I, volume 12491 of LNCS, pages 787–816. December 2020. Springer, Heidelberg. DOI: 10.1007/978-3-030-64837-4_26
[LS15]
Adeline Langlois and Damien Stehlé. Worst-case to average-case reductions for module lattices. Designs, Codes and Cryptography, 75(3):565–599, 2015. DOI: 10.1007/s10623-014-9938-4
[MGTF19]
Vincent Migliore, Benoît Gérard, Mehdi Tibouchi, and Pierre-Alain Fouque. Masking Dilithium - Efficient Implementation and Side-Channel Evaluation. In Robert H. Deng, Valérie Gauthier-Umaña, Martín Ochoa, and Moti Yung, editors, ACNS 19, volume 11464 of LNCS, pages 344–362. June 2019. Springer, Heidelberg. DOI: 10.1007/978-3-030-21568-2_17
[MM22]
Nicolai Müller and Amir Moradi. PROLEAD A Probing-Based Hardware Leakage Detection Tool. IACR TCHES, 2022(4):311–348, 2022. DOI: 10.46586/tches.v2022.i4.311-348
[MOW17]
David McCann, Elisabeth Oswald, and Carolyn Whitnall. Towards Practical Tools for Side Channel Aware Software Engineering: 'Grey Box' Modelling for Instruction Leakages. In Engin Kirda and Thomas Ristenpart, editors, USENIX Security 2017, pages 199–216. August 2017. USENIX Association.
[MPH23]
Quentin L. Meunier, Etienne Pons, and Karine Heydemann. LeakageVerif: Efficient and Scalable Formal Verification of Leakage in Symbolic Expressions. IEEE Trans. Softw. Eng., 49(6):3359–3375, June 2023. DOI: 10.1109/TSE.2023.3252671
[OSPG18]
Tobias Oder, Tobias Schneider, Thomas Pöppelmann, and Tim Güneysu. Practical CCA2-Secure and Masked Ring-LWE Implementation. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2018(1):142–174, Feb. 2018. DOI: 10.13154/tches.v2018.i1.142-174
[PPM17]
Robert Primas, Peter Pessl, and Stefan Mangard. Single-Trace Side-Channel Attacks on Masked Lattice-Based Encryption. In Wieland Fischer and Naofumi Homma, editors, CHES 2017, volume 10529 of LNCS, pages 513–533. September 2017. Springer, Heidelberg. DOI: 10.1007/978-3-319-66787-4_25
[PV17]
Kostas Papagiannopoulos and Nikita Veshchikov. Mind the Gap: Towards Secure 1st-Order Masking in Software. In Sylvain Guilley, editor, COSADE 2017, volume 10348 of LNCS, pages 282–297. April 2017. Springer, Heidelberg. DOI: 10.1007/978-3-319-64647-3_17
[RdCR+16]
Oscar Reparaz, Ruan de Clercq, Sujoy Sinha Roy, Frederik Vercauteren, and Ingrid Verbauwhede. Additively Homomorphic Ring-LWE Masking. In Tsuyoshi Takagi, editor, Post-Quantum Cryptography - 7th International Workshop, PQCrypto 2016, pages 233–244. 2016. Springer, Heidelberg. DOI: 10.1007/978-3-319-29360-8_15
[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, pages 413–427. August 2010. Springer, Heidelberg. DOI: 10.1007/978-3-642-15031-9_28
[RRCB20]
Prasanna Ravi, Sujoy Sinha Roy, Anupam Chattopadhyay, and Shivam Bhasin. Generic Side-channel attacks on CCA-secure lattice-based PKE and KEMs. IACR TCHES, 2020(3):307–335, 2020. https://tches.iacr.org/index.php/TCHES/article/view/8592 DOI: 10.13154/tches.v2020.i3.307-335
[RRVV15]
Oscar Reparaz, Sujoy Sinha Roy, Frederik Vercauteren, and Ingrid Verbauwhede. A Masked Ring-LWE Implementation. In Tim Güneysu and Helena Handschuh, editors, CHES 2015, volume 9293 of LNCS, pages 683–702. September 2015. Springer, Heidelberg. DOI: 10.1007/978-3-662-48324-4_34
[SAB+20]
Peter Schwabe, Roberto Avanzi, Joppe Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, John M. Schanck, Gregor Seiler, and Damien Stehlé. CRYSTALS-KYBER. Technical report, National Institute of Standards and Technology. available at https://csrc.nist.gov/projects/post-quantum-cryptography/post-quantum-cryptography-standardization/round-3-submissions. 2020.
[SPOG19]
Tobias Schneider, Clara Paglialonga, Tobias Oder, and Tim Güneysu. Efficiently Masking Binomial Sampling at Arbitrary Orders for Lattice-Based Crypto. In Dongdai Lin and Kazue Sako, editors, PKC 2019, Part II, volume 11443 of LNCS, pages 534–564. April 2019. Springer, Heidelberg. DOI: 10.1007/978-3-030-17259-6_18
[SSB+21]
Madura A. Shelton, Niels Samwel, Lejla Batina, Francesco Regazzoni, Markus Wagner, and Yuval Yarom. Rosita: Towards Automatic Elimination of Power-Analysis Leakage in Ciphers. In NDSS 2021. February 2021. The Internet Society.
[UXT+22]
Rei Ueno, Keita Xagawa, Yutaro Tanaka, Akira Ito, Junko Takahashi, and Naofumi Homma. Curse of Re-encryption: A Generic Power/EM Analysis on Post-Quantum KEMs. IACR TCHES, 2022(1):296–322, 2022. DOI: 10.46586/tches.v2022.i1.296-322
[VDV21]
Michiel Van Beirendonck, Jan-Pieter D'Anvers, and Ingrid Verbauwhede. Analysis and Comparison of Table-based Arithmetic to Boolean Masking. IACR TCHES, 2021(3):275–297, 2021. https://tches.iacr.org/index.php/TCHES/article/view/8975 DOI: 10.46586/tches.v2021.i3.275-297
[XPR+22]
Zhuang Xu, Owen Pemberton, Sujoy Sinha Roy, David F. Oswald, Wang Yao, and Zhiming Zheng. Magnifying Side-Channel Leakage of Lattice-Based Cryptosystems With Chosen Ciphertexts: The Case Study of Kyber. IEEE Trans. Computers, 71(9):2163–2176, 2022. DOI: 10.1109/TC.2021.3122997
[ZMM23]
Jannik Zeitschner, Nicolai Müller, and Amir Moradi. PROLEAD_SW Probing-Based Software Leakage Detection for ARM Binaries. IACR TCHES, 2023(3):391–421, 2023. DOI: 10.46586/tches.v2023.i3.391-421
PDF
History
Submitted: 2024-04-08
Accepted: 2024-06-03
Published: 2024-07-08
Accepted: 2024-06-03
Published: 2024-07-08
How to cite
Camille Mutschler, Laurent Imbert, and Thomas Roche, "Inspector Gadget," IACR Communications in Cryptology, vol. 1, no. 2, Jul 08, 2024, doi: 10.62056/ah5wommol.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.