Exact Soft Analytical Side-Channel Attacks using Tractable Circuits
Thomas Wedenig, Rishub Nagpal, Gaëtan Cassiers, Stefan Mangard, Robert Peharz
Abstract
Detecting weaknesses in cryptographic algorithms is of utmost importance for designing secure information systems. The state-of-the-art soft analytical side-channel attack (SASCA) uses physical leakage information to make probabilistic predictions about intermediate computations and combines these "guesses" with the known algorithmic logic to compute the posterior distribution over the key. This attack is commonly performed via loopy belief propagation, which, however, lacks guarantees in terms of convergence and inference quality. In this paper, we develop a fast and exact inference method for SASCA, denoted as ExSASCA, by leveraging knowledge compilation and tractable probabilistic circuits. When attacking the Advanced Encryption Standard (AES), the most widely used encryption algorithm to date, ExSASCA outperforms SASCA by more than 31% top-1 success rate absolute. By leveraging sparse belief messages, this performance is achieved with little more computational cost than SASCA, and about 3 orders of magnitude less than exact inference via exhaustive enumeration. Even with dense belief messages, ExSASCA still uses 6 times less computations than exhaustive inference.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
2 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Fast Reconstruction of Mixtures of Bernoulli Product Distributions cites The Limits of Tractable Marginalization
- Semantic Probabilistic Layers for Neuro-Symbolic Learning cites Einsum Networks: Fast and Scalable Learning of Tractable Probabilistic Circuits
- The Limits of Tractable Marginalization cites Semantic Probabilistic Layers for Neuro-Symbolic Learning
Cited by top-tier papers2
Builds on2
- Einsum Networks: Fast and Scalable Learning of Tractable Probabilistic CircuitsRobert Peharz, Steven Lang, Antonio Vergari, Karl Stelzner et al.ICML 2020 · 155 citations
- Semantic Probabilistic Layers for Neuro-Symbolic LearningKareem Ahmed, Stefano Teso, Kai-Wei Chang, Guy Van den Broeck et al.NeurIPS 2022 · 133 citations
Related papers
- Identifying Cache-Based Side Channels through Secret-Augmented Abstract InterpretationShuai Wang, Yuyan Bao, Xiao Liu, Pei Wang et al.USENIX Security 2019 · 57 citations
- A Thorough Evaluation of RAMBAMDaniel Lammers, Amir Moradi, Nicolai Müller, Aein Rezaei ShahmirzadiCCS 2023 · 1 citation
- SCASE: Automated Secret Recovery via Side-Channel-Assisted Symbolic ExecutionDaniel Weber, Lukas Gerlach, Leon Trampert, Youheng Lü et al.USENIX Security 2025
- Secure Wire Shuffling in the Probing ModelJean-Sébastien Coron, Lorenzo SpignoliCRYPTO 2021 · 13 citations
- Cross-Device Profiled Side-Channel Attacks using Meta-Transfer LearningHonggang Yu, Haoqi Shan, Maximillian Panoff, Yier JinDAC 2021 · 38 citations
