Information Theoretic Evaluation of   Raccoon's Side-Channel Leakage

Dinal Kamel; François-Xavier Standaert; Olivier Bronchain

doi:10.62056/abkp2c3w9p

Information Theoretic Evaluation of Raccoon's Side-Channel Leakage

Authors

Dinal Kamel, François-Xavier Standaert, Olivier Bronchain

Dinal Kamel

UCLouvain, Crypto Group, Louvain-la-Neuve, Belgium
dina dot kamel at uclouvain dot be

François-Xavier Standaert

UCLouvain, Crypto Group, Louvain-la-Neuve, Belgium

Olivier Bronchain

NXP Semiconductors, Leuven, Belgium

Keywords: Post-Quantum Cryptography Signature Schemes Side-Channel Analysis Masking Countermeasure CRYSTALS-Dilithium Raccoon

Abstract

Raccoon is a lattice-based scheme submitted to the NIST 2022 call for additional post-quantum signatures. One of its main selling points is that its design is intrinsically easy to mask against side-channel attacks. So far, Raccoon's physical security guarantees were only stated in the abstract probing model. In this paper, we discuss how these probing security results translate into guarantees in more realistic leakage models. We also highlight that this translation differs from what is usually observed (e.g., in symmetric cryptography), due to the algebraic structure of Raccoon's operations. For this purpose, we perform an in-depth information theoretic evaluation of Raccoon's most innovative part, namely the AddRepNoise function which allows generating its arithmetic shares on-the-fly. Our results are twofold. First, we show that the resulting shares do not enforce a statistical security order (i.e., the need for the side-channel adversary to estimate higher-order moments of the leakage distribution), as usually expected when masking. Second, we observe that the first-order leakage on the (large) random coefficients manipulated by Raccoon cannot be efficiently turned into leakage on the (smaller) coefficients of its long-term secret. Concretely, our information theoretic evaluations for relevant leakage functions also suggest that Raccoon's masked implementations can ensure high security with less shares than suggested by a conservative analysis in the probing model.

References

[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 Trans. Cryptogr. Hardw. Embed. Syst., 2023(4):58–79, 2023. DOI: 10.46586/TCHES.V2023.I4.58-79

Google Scholar ePrint

[BAE⁺24]

Olivier Bronchain, Melissa Azouaoui, Mohamed ElGhamrawy, Joost Renes, and Tobias Schneider. Exploiting Small-Norm Polynomial Multiplication with Physical Attacks Application to CRYSTALS-Dilithium. IACR Trans. Cryptogr. Hardw. Embed. Syst., 2024(2):359–383, 2024. DOI: 10.46586/TCHES.V2024.I2.359-383

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, Advances in Cryptology - EUROCRYPT 2018 - 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29 - May 3, 2018 Proceedings, Part II, volume 10821 of Lecture Notes in Computer Science, pages 354–384. 2018. Springer. DOI: 10.1007/978-3-319-78375-8_12

Google Scholar ePrint

[BCG⁺23]

Julien Béguinot, Wei Cheng, Sylvain Guilley, Yi Liu, Loïc Masure, Olivier Rioul, and François-Xavier Standaert. Removing the Field Size Loss from Duc et al.'s Conjectured Bound for Masked Encodings. In Elif Bilge Kavun and Michael Pehl, editors, Constructive Side-Channel Analysis and Secure Design - 14th International Workshop, COSADE 2023, Munich, Germany, April 3-4, 2023, Proceedings, volume 13979 of Lecture Notes in Computer Science, pages 86–104. 2023. Springer. DOI: 10.1007/978-3-031-29497-6_5

Google Scholar ePrint

[BS21]

Olivier Bronchain and François-Xavier Standaert. Breaking Masked Implementations with Many Shares on 32-bit Software Platforms or When the Security Order Does Not Matter. IACR Trans. Cryptogr. Hardw. Embed. Syst., 2021(3):202–234, 2021. DOI: 10.46586/TCHES.V2021.I3.202-234

Google Scholar ePrint

[BVC⁺23]

Alexandre Berzati, Andersson Calle Viera, Maya Chartouny, Steven Madec, Damien Vergnaud, and David Vigilant. Exploiting Intermediate Value Leakage in Dilithium: A Template-Based Approach. IACR Trans. Cryptogr. Hardw. Embed. Syst., 2023(4):188–210, 2023. DOI: 10.46586/TCHES.V2023.I4.188-210

Google Scholar ePrint

[CDSU23]

Gaëtan Cassiers, Henri Devillez, François-Xavier Standaert, and Balazs Udvarhelyi. Efficient Regression-Based Linear Discriminant Analysis for Side-Channel Security Evaluations Towards Analytical Attacks against 32-bit Implementations. IACR Trans. Cryptogr. Hardw. Embed. Syst., 2023(3):270–293, 2023. DOI: 10.46586/TCHES.V2023.I3.270-293

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, Advances in Cryptology - CRYPTO '99, 19th Annual International Cryptology Conference, Santa Barbara, California, USA, August 15-19, 1999, Proceedings, volume 1666 of Lecture Notes in Computer Science, pages 398–412. 1999. Springer. DOI: 10.1007/3-540-48405-1_26

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, Advances in Cryptology - EUROCRYPT 2014 - 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Copenhagen, Denmark, May 11-15, 2014. Proceedings, volume 8441 of Lecture Notes in Computer Science, pages 423–440. 2014. Springer. DOI: 10.1007/978-3-642-55220-5_24

Google Scholar ePrint

[DFS15]

Alexandre Duc, Sebastian Faust, and François-Xavier Standaert. Making Masking Security Proofs Concrete - Or How to Evaluate the Security of Any Leaking Device. In Elisabeth Oswald and Marc Fischlin, editors, Advances in Cryptology - EUROCRYPT 2015 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, April 26-30, 2015, Proceedings, Part I, volume 9056 of Lecture Notes in Computer Science, pages 401–429. 2015. Springer. DOI: 10.1007/978-3-662-46800-5_16

Google Scholar ePrint

[DFS16]

Stefan Dziembowski, Sebastian Faust, and Maciej Skórski. Optimal Amplification of Noisy Leakages. In Eyal Kushilevitz and Tal Malkin, editors, Theory of Cryptography - 13th International Conference, TCC 2016-A, Tel Aviv, Israel, January 10-13, 2016, Proceedings, Part II, volume 9563 of Lecture Notes in Computer Science, pages 291–318. 2016. Springer. DOI: 10.1007/978-3-662-49099-0_11

Google Scholar ePrint

[dPPRS23]

Rafaël del Pino, Thomas Prest, Mélissa Rossi, and Markku-Juhani O. Saarinen. High-Order Masking of Lattice Signatures in Quasilinear Time. In 44th IEEE Symposium on Security and Privacy, SP 2023, San Francisco, CA, USA, May 21-25, 2023, pages 1168–1185. 2023. IEEE. DOI: 10.1109/SP46215.2023.10179342

Google Scholar ePrint

[FMM⁺24]

Sebastian Faust, Loïc Masure, Elena Micheli, Maximilian Orlt, and François-Xavier Standaert. Connecting Leakage-Resilient Secret Sharing to Practice: Scaling Trends and Physical Dependencies of Prime Field Masking. In Marc Joye and Gregor Leander, editors, Advances in Cryptology - EUROCRYPT 2024 - 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zurich, Switzerland, May 26-30, 2024, Proceedings, Part IV, volume 14654 of Lecture Notes in Computer Science, pages 316–344. 2024. Springer. DOI: 10.1007/978-3-031-58737-5_12

Google Scholar ePrint

[GP99]

Louis Goubin and Jacques Patarin. DES and Differential Power Analysis (The "Duplication" Method). In Çetin Kaya Koç and Christof Paar, editors, Cryptographic Hardware and Embedded Systems, First International Workshop, CHES'99, Worcester, MA, USA, August 12-13, 1999, Proceedings, volume 1717 of Lecture Notes in Computer Science, pages 158–172. 1999. Springer. DOI: 10.1007/3-540-48059-5_15

Google Scholar ePrint

[HLM⁺23]

Clément Hoffmann, Benoît Libert, Charles Momin, Thomas Peters, and François-Xavier Standaert. POLKA: Towards Leakage-Resistant Post-quantum CCA-Secure Public Key Encryption. In Alexandra Boldyreva and Vladimir Kolesnikov, editors, Public-Key Cryptography - PKC 2023 - 26th IACR International Conference on Practice and Theory of Public-Key Cryptography, Atlanta, GA, USA, May 7-10, 2023, Proceedings, Part I, volume 13940 of Lecture Notes in Computer Science, pages 114–144. 2023. Springer. DOI: 10.1007/978-3-031-31368-4_5

Google Scholar ePrint

[ISW03]

Yuval Ishai, Amit Sahai, and David A. Wagner. Private Circuits: Securing Hardware against Probing Attacks. In Dan Boneh, editor, Advances in Cryptology - CRYPTO 2003, 23rd Annual International Cryptology Conference, Santa Barbara, California, USA, August 17-21, 2003, Proceedings, volume 2729 of Lecture Notes in Computer Science, pages 463–481. 2003. Springer. DOI: 10.1007/978-3-540-45146-4_27

Google Scholar ePrint

[IUH22]

Akira Ito, Rei Ueno, and Naofumi Homma. On the Success Rate of Side-Channel Attacks on Masked Implementations: Information-Theoretical Bounds and Their Practical Usage. In Heng Yin, Angelos Stavrou, Cas Cremers, and Elaine Shi, editors, Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, CCS 2022, Los Angeles, CA, USA, November 7-11, 2022, pages 1521–1535. 2022. ACM. DOI: 10.1145/3548606.3560579

Google Scholar ePrint

[KGM⁺21]

Thilo Krachenfels, Fatemeh Ganji, Amir Moradi, Shahin Tajik, and Jean-Pierre Seifert. Real-World Snapshots vs. Theory: Questioning the t-Probing Security Model. In 42nd IEEE Symposium on Security and Privacy, SP 2021, San Francisco, CA, USA, 24-27 May 2021, pages 1955–1971. 2021. IEEE. DOI: 10.1109/SP40001.2021.00029

Google Scholar ePrint

[LBS19]

Itamar Levi, Davide Bellizia, and François-Xavier Standaert. Reducing a Masked Implementation's Effective Security Order with Setup Manipulations And an Explanation Based on Externally-Amplified Couplings. IACR Trans. Cryptogr. Hardw. Embed. Syst., 2019(2):293–317, 2019. DOI: 10.13154/TCHES.V2019.I2.293-317

Google Scholar ePrint

[LZS⁺21]

Yuejun Liu, Yongbin Zhou, Shuo Sun, Tianyu Wang, Rui Zhang, and Jingdian Ming. On the Security of Lattice-Based Fiat-Shamir Signatures in the Presence of Randomness Leakage. IEEE Trans. Inf. Forensics Secur., 16:1868–1879, 2021. DOI: 10.1109/TIFS.2020.3045904

Google Scholar ePrint

[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, Applied Cryptography and Network Security - 17th International Conference, ACNS 2019, Bogota, Colombia, June 5-7, 2019, Proceedings, volume 11464 of Lecture Notes in Computer Science, pages 344–362. 2019. Springer. DOI: 10.1007/978-3-030-21568-2_17

Google Scholar ePrint

[MMMS23]

Loïc Masure, Pierrick Méaux, Thorben Moos, and François-Xavier Standaert. Effective and Efficient Masking with Low Noise Using Small-Mersenne-Prime Ciphers. In Carmit Hazay and Martijn Stam, editors, Advances in Cryptology - EUROCRYPT 2023 - 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23-27, 2023, Proceedings, Part IV, volume 14007 of Lecture Notes in Computer Science, pages 596–627. 2023. Springer. DOI: 10.1007/978-3-031-30634-1_20

Google Scholar ePrint

[MOP07]

Stefan Mangard, Elisabeth Oswald, and Thomas Popp. Power analysis attacks - revealing the secrets of smart cards. Springer 2007.

Google Scholar ePrint

[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, 26th USENIX Security Symposium, USENIX Security 2017, Vancouver, BC, Canada, August 16-18, 2017, pages 199–216. 2017. USENIX Association.

Google Scholar ePrint

[PR13]

Emmanuel Prouff and Matthieu Rivain. Masking against Side-Channel Attacks: A Formal Security Proof. In Thomas Johansson and Phong Q. Nguyen, editors, Advances in Cryptology - EUROCRYPT 2013, 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, Greece, May 26-30, 2013. Proceedings, volume 7881 of Lecture Notes in Computer Science, pages 142–159. 2013. Springer. DOI: 10.1007/978-3-642-38348-9_9

Google Scholar ePrint

[RJH⁺18]

Prasanna Ravi, Mahabir Prasad Jhanwar, James Howe, Anupam Chattopadhyay, and Shivam Bhasin. Side-channel Assisted Existential Forgery Attack on Dilithium - A NIST PQC candidate. IACR Cryptol. ePrint Arch., 2018.

Google Scholar ePrint

[SM16]

Tobias Schneider and Amir Moradi. Leakage assessment methodology - Extended version. J. Cryptogr. Eng., 6(2):85–99, 2016. DOI: 10.1007/S13389-016-0120-Y

Google Scholar ePrint

[SMY09]

François-Xavier Standaert, Tal Malkin, and Moti Yung. A Unified Framework for the Analysis of Side-Channel Key Recovery Attacks. In Antoine Joux, editor, Advances in Cryptology - EUROCRYPT 2009, 28th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cologne, Germany, April 26-30, 2009. Proceedings, volume 5479 of Lecture Notes in Computer Science, pages 443–461. 2009. Springer. DOI: 10.1007/978-3-642-01001-9_26

Google Scholar ePrint

[SVO⁺10]

François-Xavier Standaert, Nicolas Veyrat-Charvillon, Elisabeth Oswald, Benedikt Gierlichs, Marcel Medwed, Markus Kasper, and Stefan Mangard. The World Is Not Enough: Another Look on Second-Order DPA. In Masayuki Abe, editor, Advances in Cryptology - ASIACRYPT 2010 - 16th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, December 5-9, 2010. Proceedings, volume 6477 of Lecture Notes in Computer Science, pages 112–129. 2010. Springer. DOI: 10.1007/978-3-642-17373-8_7

Google Scholar ePrint

[UMTS22]

Vincent Quentin Ulitzsch, Soundes Marzougui, Mehdi Tibouchi, and Jean-Pierre Seifert. Profiling Side-Channel Attacks on Dilithium - A Small Bit-Fiddling Leak Breaks It All. In Benjamin Smith and Huapeng Wu, editors, Selected Areas in Cryptography - 29th International Conference, SAC 2022, Windsor, ON, Canada, August 24-26, 2022, Revised Selected Papers, volume 13742 of Lecture Notes in Computer Science, pages 3–32. 2022. Springer. DOI: 10.1007/978-3-031-58411-4_1

Google Scholar ePrint

PDF Open access

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

History

Submitted: 2024-07-09
Accepted: 2024-09-02
Published: 2024-10-07

How to cite

Dinal Kamel, François-Xavier Standaert, and Olivier Bronchain, Information Theoretic Evaluation of Raccoon's Side-Channel Leakage. IACR Communications in Cryptology, vol. 1, no. 3, Oct 07, 2024, doi: 10.62056/abkp2c3w9p.

License

Copyright is held by the author(s)

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

@article{CiC-1-3-44,
    author = "Kamel, Dinal and Standaert, François-Xavier and Bronchain, Olivier",
    journal = "{IACR} {C}ommunications in {C}ryptology",
    publisher = "{I}nternational {A}ssociation for {C}ryptologic {R}esearch",
    title = "Information Theoretic Evaluation of   Raccoon's Side-Channel Leakage",
    volume = "1",
    number = "3",
    date = "2024-10-07",
    year = "2024",
    issn = "3006-5496",
    doi = "10.62056/abkp2c3w9p"
}

TY - JOUR
AU - Kamel, Dinal
AU - Standaert, François-Xavier
AU - Bronchain, Olivier
PY  - 2024
TI  - Information Theoretic Evaluation of   Raccoon's Side-Channel Leakage
JF  - IACR Communications in Cryptology
JA  - CIC
VL  - 1
IS  - 3
DO  - 10.62056/abkp2c3w9p
UR  - https://doi.org/10.62056/abkp2c3w9p
AB  - <p>  Raccoon is a lattice-based scheme submitted to the NIST 2022 call         for additional post-quantum signatures. One of its main selling         points is that its design is intrinsically easy to         mask against side-channel attacks. So far, Raccoon's physical security guarantees         were only stated in the abstract probing model.         In this paper, we discuss how these         probing security results translate into guarantees in more realistic leakage models.         We also highlight that this translation differs from what is usually observed         (e.g., in symmetric cryptography), due to the algebraic structure of         Raccoon's operations.         For this purpose, we perform an in-depth information theoretic evaluation         of Raccoon's most innovative part, namely the AddRepNoise         function which allows generating its arithmetic shares on-the-fly.   Our results are twofold. First, we show that         the resulting shares do not enforce a statistical security         order (i.e., the need for the side-channel adversary to estimate higher-order         moments of the leakage distribution), as usually expected when masking.         Second, we observe that the         first-order leakage on the (large) random coefficients manipulated         by Raccoon cannot be efficiently turned into   leakage on the (smaller) coefficients of its long-term secret.         Concretely, our information theoretic evaluations for relevant leakage functions         also suggest that         Raccoon's masked implementations can ensure high         security with less shares than suggested by         a conservative analysis in the probing model. </p>
ER  -

Dinal Kamel, François-Xavier Standaert, and Olivier Bronchain, Information Theoretic Evaluation of Raccoon's Side-Channel Leakage. IACR Communications in Cryptology, vol. 1, no. 3, Oct 07, 2024, doi: 10.62056/abkp2c3w9p.