research-article

Machine-Learning Side-Channel Attacks on the GALACTICS Constant-Time Implementation of BLISS

Authors:

Soundes Marzougui,

Patrick Gersch,

Juliane Krämer,

Jean-Pierre SeifertAuthors Info & Claims

ARES '22: Proceedings of the 17th International Conference on Availability, Reliability and Security

Article No.: 34, Pages 1 - 11

https://doi.org/10.1145/3538969.3538980

Published: 23 August 2022 Publication History

Abstract

Due to the advancing development of quantum computers, practical attacks on conventional public-key cryptography may become feasible in the next few decades. To address this risk, post-quantum schemes that are assumed to be secure against quantum attacks are being developed. Lattice-based algorithms are promising replacements for conventional schemes, with BLISS being one of the earliest post-quantum signature schemes in this family. However, required subroutines such as Gaussian sampling have been demonstrated to be a risk for the security of BLISS, since implementing Gaussian sampling both efficient and secure with respect to physical attacks is challenging.

This paper presents three related power side-channel attacks on GALACTICS, the latest constant-time implementation of BLISS. All attacks are based on power side-channel leakages we identified in the Gaussian sampling and signing algorithm of GALACTICS. To run the attacks, a profiling phase on a device identical to the device under attack is required to train machine learning classifiers. In the attack phase, the leakages of GALACTICS enable the trained classifiers to predict sensitive internal information with high accuracy. We demonstrate the practicality of the attacks by running GALACTICS on a Cortex-M4 and provide proof-of-concept data and implementation for all our attacks.

References

[1]

Erdem Alkim, Joppe W. Bos, Léo Ducas, Karen Easterbrook, Brian LaMacchia, Patrick Longa, Ilya Mironov, Michael Naehrig, Valeria Nikolaenko, Chris Peikert, Ananth Raghunathan, and Douglas Stebila. 2020. FrodoKEM: Learning with errors key encapsulation. https://frodokem.org/. Submission to the NIST Post-Quantum Cryptography standardization project, Round 3.

[2]

Gilles Barthe, Sonia Belaïd, Thomas Espitau, Pierre-Alain Fouque, Mélissa Rossi, and Mehdi Tibouchi.2019a. https://github.com/espitau/GALACTICS.

[3]

Gilles Barthe, Sonia Belaïd, Thomas Espitau, Pierre-Alain Fouque, Mélissa Rossi, and Mehdi Tibouchi. 2019b. GALACTICS: Gaussian Sampling for Lattice-Based Constant- Time Implementation of Cryptographic Signatures, Revisited. In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security(CCS ’19). Association for Computing Machinery, New York, NY, USA, 2147–2164.

Digital Library

[4]

Daniel J. Bernstein and Tanja Lange. 2008. eBACS: ECRYPT Benchmarking of Cryptographic Systems. https://bench.cr.yp.to. [Online; accessed 15-March-2022].

[5]

Joppe W. Bos, Craig Costello, Michael Naehrig, and Douglas Stebila. 2015. Post-Quantum Key Exchange for the TLS Protocol from the Ring Learning with Errors Problem., 553-570 pages. https://doi.org/10.1109/SP.2015.40

Digital Library

[6]

Martin Brisfors, Sebastian Forsmark, and Elena Dubrova. 2020. How Deep Learning Helps Compromising USIM., 135–150 pages. https://doi.org/10.1007/978-3-030-68487-7_9

Digital Library

[7]

Tobias Brunner. 2008. strongSwan: the Open Source IPsec-based VPN Solution. https://github.com/strongswan/strongswan. [Online; accessed 15-March-2022].

[8]

L. Devroye. 1986. Non-Uniform Random Variate Generation.

[9]

Léo Ducas, Alain Durmus, Tancrède Lepoint, and Vadim Lyubashevsky. 2013. Lattice Signatures and Bimodal Gaussians., 40–56 pages. https://doi.org/10.1007/978-3-642-40041-4_3

[10]

Léo Ducas, Steven D. Galbraith, Thomas Prest, and Yang Yu. 2020. Integral Matrix Gram Root and Lattice Gaussian Sampling Without Floats., 608–637 pages.

[11]

Thomas Espitau, Pierre-Alain Fouque, Benoît Gérard, and Mehdi Tibouchi. 2017a. Side-Channel Attacks on BLISS Lattice-Based Signatures: Exploiting Branch Tracing against strongSwan and Electromagnetic Emanations in Microcontrollers. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. ACM, Dallas Texas USA, 1857–1874.

Digital Library

[12]

Thomas Espitau, Pierre-Alain Fouque, Benoît Gérard, and Mehdi Tibouchi. 2017b. Side-Channel Attacks on BLISS Lattice-Based Signatures: Exploiting Branch Tracing against StrongSwan and Electromagnetic Emanations in Microcontrollers. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security(Dallas, Texas, USA) (CCS ’17). Association for Computing Machinery, New York, NY, USA, 1857–1874. https://doi.org/10.1145/3133956.3134028

Digital Library

[13]

Pierre-Alain Fouque, J. Hoffstein, Paul Kirchner, Vadim Lyubashevsky, T. Pornin, T. Prest, Thomas Ricosset, Gregor Seiler, William Whyte, and Z. Zhang. 2019. Falcon: Fast-Fourier Lattice-based Compact Signatures over NTRU.

[14]

Leon Groot Bruinderink, Andreas Hülsing, Tanja Lange, and Yuval Yarom. 2016. Flush, Gauss, and Reload – A Cache Attack on the BLISS Lattice-Based Signature Scheme. In Cryptographic Hardware and Embedded Systems – CHES 2016, Benedikt Gierlichs and Axel Y. Poschmann (Eds.). Vol. 9813. Springer Berlin Heidelberg, Berlin, Heidelberg, 323–345.

[15]

Tim Güneysu, Markus Krausz, Tobias Oder, and Julian Speith. 2018. Evaluation of Lattice-Based Signature Schemes in Embedded Systems. 385–388. https://doi.org/10.1109/ICECS.2018.8617969

[16]

Lenstra H.W. jr., Lenstra, and A.K. Lovász L.1982. Factoring Polynomials with Rational Coefficients.Math. Ann. 261(1982), 515–534. http://eudml.org/doc/182903

[17]

Jaehun Kim, Stjepan Picek, Annelie Heuser, Shivam Bhasin, and Alan Hanjalic. 2018. Make Some Noise: Unleashing the Power of Convolutional Neural Networks for Profiled Side-channel Analysis. Cryptology ePrint Archive, Report 2018/1023. https://eprint.iacr.org/2018/1023.

[18]

Suhri Kim and Seokhie Hong. 2018. Single Trace Analysis on Constant Time CDT Sampler and Its Countermeasure. Applied Sciences 8, 10 (Oct. 2018), 1809.

[19]

Donald E. Knuth. 1997. The Art of Computer Programming, Volume 2 (3rd Ed.): Seminumerical Algorithms. Addison-Wesley Longman Publishing Co., Inc., USA.

Digital Library

[20]

Paul Kocher, Joshua Jaffe, and Benjamin Jun. 1999. Differential Power Analysis. In Advances in Cryptology — CRYPTO’ 99, Michael Wiener (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 388–397.

[21]

Vadim Lyubashevsky. 2009. Fiat-Shamir with Aborts: Applications to Lattice and Factoring-Based Signatures. In Advances in Cryptology – ASIACRYPT 2009, Mitsuru Matsui (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 598–616.

Digital Library

[22]

Vadim Lyubashevsky. 2012. Lattice Signatures without Trapdoors. In Advances in Cryptology – EUROCRYPT 2012, David Pointcheval and Thomas Johansson (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 738–755.

Digital Library

[23]

Houssem Maghrebi, Thibault Portigliatti, and E. Prouff. 2016. Breaking Cryptographic Implementations Using Deep Learning Techniques. IACR Cryptol. ePrint Arch. 2016 (2016), 921.

[24]

Daniele Micciancio and Michael Walter. 2017. Gaussian Sampling over the Integers: Efficient, Generic, Constant-Time., 455–485 pages.

[25]

Peter Pessl. 2016. Analyzing the Shuffling Side-Channel Countermeasure for Lattice-Based Signatures., 153–170 pages.

[26]

Peter Pessl, Leon Groot Bruinderink, and Yuval Yarom. 2017a. To BLISS-B or Not to Be: Attacking StrongSwan’s Implementation of Post-Quantum Signatures. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security (Dallas, Texas, USA) (CCS ’17). Association for Computing Machinery, New York, NY, USA, 1843–1855. https://doi.org/10.1145/3133956.3134023

Digital Library

[27]

Peter Pessl, Leon Groot Bruinderink, and Yuval Yarom. 2017b. To BLISS-B or Not to Be: Attacking StrongSwan’s Implementation of Post-Quantum Signatures. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security (Dallas, Texas, USA) (CCS ’17). Association for Computing Machinery, New York, NY, USA, 1843–1855. https://doi.org/10.1145/3133956.3134023

Digital Library

[28]

Thomas Pöppelmann, Léo Ducas, and Tim Güneysu. 2014. Enhanced Lattice-Based Signatures on Reconfigurable Hardware. In Cryptographic Hardware and Embedded Systems – CHES 2014, Lejla Batinaand Matthew Robshaw (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 353–370.

Digital Library

[29]

Oscar Reparaz, Josep Balasch, and Ingrid Verbauwhede. 2017. Dude, is my code constant time?, 1697-1702 pages. https://doi.org/10.23919/DATE.2017.7927267

[30]

Markku-Juhani O. Saarinen. 2018. Arithmetic coding and blinding countermeasures for lattice signatures - Engineering a side-channel resistant post-quantum signature scheme with compact signatures. J. Cryptogr. Eng. 8, 1 (2018), 71–84.

[31]

Bo-Yeon Sim, Jihoon Kwon, Joohee Lee, Il-Ju Kim, Tae-Ho Lee, Jaeseung Han, Hyojin Yoon, Jihoon Cho, and Dong-Guk Han. 2020. Single-Trace Attacks on Message Encoding in Lattice-Based KEMs. IEEE Access 8(2020), 183175–183191. https://doi.org/10.1109/ACCESS.2020.3029521

[32]

Andreas Steffen March 2017. strongSwan: the Open Source IPsec-based VPNSolution (version 5.5.2). https://www.strongswan.org.

[33]

Mehdi Tibouchi and Alexandre Wallet. 2020. One Bit Is All It Takes: A Devastating Timing Attack on BLISS’s Non-Constant Time Sign Flips. Journal of Mathematical Cryptology 15, 1 (Nov. 2020), 131–142.

[34]

R. K. Zhao, R. Steinfeld, and A. Sakzad. 2020. FACCT: FAst, Compact, and Constant-Time Discrete Gaussian Sampler over Integers. IEEE Trans. Comput. 69, 1 (Jan. 2020), 126–137.

Digital Library

Cited By

Sharma CSingh GMuttum PMahajan S(2024)CNN-FastText Multi-Input (CFMI) Neural Networks for Social Media Clickbait ClassificationRecent Advances in Computer Science and Communications10.2174/012666255828391423122106543717:6Online publication date: Sep-2024
https://doi.org/10.2174/0126662558283914231221065437
Nouma SYavuz A(2023)Lightweight Digital Signatures for Internet of Things: Current and Post-Quantum Trends and Visions2023 IEEE Conference on Dependable and Secure Computing (DSC)10.1109/DSC61021.2023.10354177(1-2)Online publication date: 7-Nov-2023
https://doi.org/10.1109/DSC61021.2023.10354177
Redkins BKuzminykh IGhita B(2023)Work-in-Progress: Security of Public-Key Schemes in the Quantum Computing Era – A Literature Review2023 IEEE International Black Sea Conference on Communications and Networking (BlackSeaCom)10.1109/BlackSeaCom58138.2023.10299759(414-419)Online publication date: 4-Jul-2023
https://doi.org/10.1109/BlackSeaCom58138.2023.10299759
Show More Cited By

Index Terms

Machine-Learning Side-Channel Attacks on the GALACTICS Constant-Time Implementation of BLISS
1. Security and privacy
  1. Cryptography
    1. Cryptanalysis and other attacks

Recommendations

Side-Channel Attacks on BLISS Lattice-Based Signatures: Exploiting Branch Tracing against strongSwan and Electromagnetic Emanations in Microcontrollers
CCS '17: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security

In this paper, we investigate the security of the BLISS lattice-based signature scheme, one of the most promising candidates for postquantum-secure signatures, against side-channel attacks. Several works have been devoted to its efficient implementation ...
Single-Trace Side-Channel Attacks on NTRU Implementation
Abstract
Most of the currently used cryptosystems are not secure in the presence of cryptographically relevant quantum computers. As the research in quantum technologies proceeds, a need for quantum-safe cryptography is imminent. NTRU is a post-quantum ...
On the Feasibility of Single-Trace Attacks on the Gaussian Sampler Using a CDT
Constructive Side-Channel Analysis and Secure Design
Abstract
We present a single-trace attack against lattice-based KEMs using the cumulative distribution table for Gaussian sampling and execute it in a real-world environment. Our analysis takes a single power trace of the decapsulation algorithm as input ...

Comments

Information & Contributors

Information

Published In

cover image ACM Other conferences

ARES '22: Proceedings of the 17th International Conference on Availability, Reliability and Security

August 2022

1371 pages

ISBN:9781450396707

DOI:10.1145/3538969

Copyright © 2022 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 August 2022

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Funding Sources

the German Federal Ministry of Education and Research
the Deutsche Forschungsgemeinschaft (DFG)

Conference

ARES 2022

ARES 2022: The 17th International Conference on Availability, Reliability and Security

August 23 - 26, 2022

Vienna, Austria

Acceptance Rates

Overall Acceptance Rate 228 of 451 submissions, 51%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
77
Total Downloads

Downloads (Last 12 months)18
Downloads (Last 6 weeks)2

Reflects downloads up to 15 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Sharma CSingh GMuttum PMahajan S(2024)CNN-FastText Multi-Input (CFMI) Neural Networks for Social Media Clickbait ClassificationRecent Advances in Computer Science and Communications10.2174/012666255828391423122106543717:6Online publication date: Sep-2024
https://doi.org/10.2174/0126662558283914231221065437
Nouma SYavuz A(2023)Lightweight Digital Signatures for Internet of Things: Current and Post-Quantum Trends and Visions2023 IEEE Conference on Dependable and Secure Computing (DSC)10.1109/DSC61021.2023.10354177(1-2)Online publication date: 7-Nov-2023
https://doi.org/10.1109/DSC61021.2023.10354177
Redkins BKuzminykh IGhita B(2023)Work-in-Progress: Security of Public-Key Schemes in the Quantum Computing Era – A Literature Review2023 IEEE International Black Sea Conference on Communications and Networking (BlackSeaCom)10.1109/BlackSeaCom58138.2023.10299759(414-419)Online publication date: 4-Jul-2023
https://doi.org/10.1109/BlackSeaCom58138.2023.10299759
Düzlü SKrämer JPöppelmann TStruck P(2023)A Lightweight Identification Protocol Based on LatticesPublic-Key Cryptography – PKC 202310.1007/978-3-031-31368-4_4(95-113)Online publication date: 7-May-2023
https://dl.acm.org/doi/10.1007/978-3-031-31368-4_4
Marzougui SKabin IKrämer JAulbach TSeifert J(2023)On the Feasibility of Single-Trace Attacks on the Gaussian Sampler Using a CDTConstructive Side-Channel Analysis and Secure Design10.1007/978-3-031-29497-6_8(149-169)Online publication date: 3-Apr-2023
https://dl.acm.org/doi/10.1007/978-3-031-29497-6_8
Ulitzsch VMarzougui STibouchi MSeifert J(2022)Profiling Side-Channel Attacks on DilithiumSelected Areas in Cryptography10.1007/978-3-031-58411-4_1(3-32)Online publication date: 24-Aug-2022
https://dl.acm.org/doi/10.1007/978-3-031-58411-4_1

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View Table of Contents