Cache Attack on BLISS Lattice-Based Signature Scheme

Public-key cryptography, including the BLISS lattice-based signature scheme, is pervasive in digital security, from code signing to online communication. The looming threat of scalable quantum computers has led to the development of post-quantum cryptography, such as lattice-based cryptography, which offers promising solutions with solid security arguments and efficient constructions. However, side-channel attacks, like cache access patterns, pose a risk, highlighting the need for further research in this evolving field.

• Cryptography
• BLISS
• Lattice-based
• Quantum threat
• Side-channels

erigg Follow

Uploaded on Sep 24, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Flush, Gauss, and Reload A Cache Attack on the BLISS Lattice-Based Signature Scheme Leon Groot Bruinderink, Andreas H lsing, Tanja Lange, Yuval Yarom Peaks in Dutch Cyber Security Research

2. Flush, Gauss, and Reload A Cache Attack on the BLISS Lattice- Based Signature Scheme Leon Groot Bruinderink (TU/e), Andreas H lsing (TU/e), Tanja Lange (TU/e), Yuval Yarom (University of Adelaide & NICTA)

3. (Public-key) cryptography is ubiquitous Code signing (Signatures) Software updates Software distribution Mobile code Communication security (Signatures, PKE / KEX) TLS, SSH, IPSec, ... eCommerce, online banking, eGovernment, ... Private online communication 3

4. The quantum threat Scalable quantum-computers can efficiently break today s public-key cryptography Predictions for first QC range from 20 years to never Risc assessment 4

5. Post-quantum cryptography Cryptography conjectured to withstand attacks with (scalable) quantum computers Different areas: Hash-based, code-based, multivariate, isogeny-based and lattice-based cryptography Transition in US planned within next 10 years (NSA & NIST)

6. Lattice-based cryptography Based on problems from lattice theory: (approximate) shortest vector problem / closest vector problem Post-quantum candidate Efficient constructions for signatures and key- exchange are known Solid formal security arguments Fast implementations First field tests by Google

7. Side-channels Implementations might leak secret information through timing, cache-access patterns, electro-magnetic radiation, power consumption... Not covered by standard security models. 7

8. Discrete Gaussians Basic building block in lattice-based cryptography. Used to hide secret. Unknown how to implement efficiently in constant time. (But also unknown how to exploit) 8

9. BLISS (Ducas, Durmus, Lepoint, Lyubashevsky, CRYPTO 2013) Bimodal lattice signature scheme Most advanced lattice-based signature scheme Open-source implementation in StrongSwan library. 9

10. BLISS signature Random bit ??? = ?, ? , ? = ?(???|| ); ? = ? + 1?? ? Discrete Gaussian vector Secret key 10

11. Challenges Found side-channels only leak partial information about ? Information is noisy Only one trace per ? 11

12. Results Side-channel attack on BLISS (full break). Practical cache attack on both samplers implemented by designers. First algorithm to un-hide secret key given side- channel information for Gaussian noise. Can compute secret key after < 5000 signatures. 12

13. Paper in proceedings of CHES 2016 Full version available at IACR eprint archive http://eprint.iacr.org/2016/300 Thank you! Questions? 13