TL;DR
This paper introduces a novel method to derive reliable upper bounds on information leakage from cryptographic implementations through side channels, particularly for scenarios with limited input complexity. By leveraging concepts from communication theory, they establish that the channel capacity provides a natural bound for mutual information learned from multivariate Gaussian side channels, directly linked to the device's signal-to-noise ratio (SNR). This framework allows for a more precise assessment of attack complexity, especially when attackers can average multiple leakage traces.
What Problem Does This Paper Address?
Leakage-resilient cryptography aims to secure cryptographic implementations against side-channel attacks by guaranteeing security even when a certain amount of information leaks. However, a significant challenge lies in accurately quantifying this leakage and establishing concrete bounds based on physical properties. Existing methods often struggle to provide precise, device-specific leakage bounds, especially for multivariate side channels, which are more representative of real-world attacks. This paper addresses the need for a reliable and theoretically grounded method to determine these leakage bounds, enabling better security assessments for leakage-resilient schemes.
Methods
The core of this paper's contribution lies in adapting concepts from communication theory to the side-channel analysis domain. Specifically, they model the side-channel leakage as a multivariate linear communication channel with Gaussian noise.
- Channel Capacity as a Leakage Bound: They establish that the channel capacity of an n-to-m communication channel serves as a natural upper bound for the mutual information (MI) learned from multivariate side channels with Gaussian noise. This bound is shown to be determined by the device-specific signal-to-noise ratio (SNR).
- Impact of Signal Averaging: The paper investigates how attackers can improve their SNR by averaging multiple leakage traces. They demonstrate that this averaging effect leads to an exponential gain in SNR with respect to the number of "points of interest" (POIs) used from the leakage traces.
- Linear Channel Model: A linear channel model ($l_x = Hx + \nu$) is used, where $l_x$ is the leakage trace, $x$ is the secret state, $H$ is the side-channel matrix, and $\nu$ is the noise vector. This model allows for the application of established communication theory results.
- Derivation of Leakage Bounds: By adapting MIMO channel capacity formulas and considering the specific constraints of side-channel analysis (e.g., real-valued information, unknown $H$), they derive leakage bounds based on the signal covariance ($E_y$) and noise covariance ($E_\nu$) matrices.
- Attack Complexity Tool: The derived bounds are used to create a tool for computing the minimum attack complexity (number of traces) required to learn a certain amount of information.
Datasets
The paper uses power measurements from a real system on chip (SoC) featuring a KECCAK-f[400] engine implemented on the UMC 65 nm LL 1P8M technology (referred to as FULMINE). This hardware serves as the basis for evaluating the soundness of their model and bounds. They construct multivariate Gaussian templates for the power consumption of specific parts of the KECCAK-f[400] permutation (5-bit and 8-bit intermediate states) using 1400 power measurements per class for training.
Key Insights and Ideas
- Channel Capacity is the Natural Bound: The paper elegantly bridges information theory and side-channel analysis by showing that channel capacity is the fundamental limit on how much information an attacker can extract from a side channel, given Gaussian noise.
- SNR is Key: The derived leakage bounds are directly tied to the signal-to-noise ratio (SNR) of the side channel. This highlights the importance of understanding and characterizing the physical properties that influence SNR.
- Averaging Power: Signal averaging is a powerful technique for attackers, and the paper quantifies its benefit, showing an exponential gain in SNR with respect to the number of POIs. This is crucial for understanding the security implications of schemes that allow repeated executions.
- Model Versatility: The linear channel model and the derived bounds are shown to be applicable to various common leakage models (identity, Hamming Weight, time-serialized, localized), making the framework broadly useful.
- Practical Relevance: The experimental validation on a real ASIC (FULMINE) demonstrates that the theoretical bounds align well with actual measured mutual information, lending strong credibility to their approach.
Key Results
- The paper provides a theoretical framework for deriving leakage upper bounds for multivariate Gaussian side channels using channel capacity.
- They show that averaging $N$ leakage traces increases the SNR by a factor of $N^m$, where $m$ is the number of POIs.
- Experimental results on the KECCAK-f[400] permutation on the FULMINE ASIC confirm that the mutual information (MI) stays within the derived channel capacity bounds.
- The study provides a tool to estimate the minimum attack complexity (number of traces) required for an attacker to recover parts of a secret state.
- For the ISAP authenticated encryption scheme on FULMINE, the analysis indicates that recovering the full state is practically infeasible with power analysis attacks given the used measurement setup and a reasonable number of POIs.
Limitations and Future Work
- Gaussian Noise Assumption: The model relies on the assumption of Gaussian noise. While this is a common and often reasonable assumption, real-world noise might exhibit more complex distributions.
- Linear Channel Model: The primary model is linear. While the authors mention that non-linear mappings can be added, the core derivations are based on linearity.
- Unknown H: The side-channel matrix $H$ is typically unknown to the attacker. The derived bounds are general and do not require prior knowledge of $H$, but practical template construction still relies on estimating the leakage behavior.
- Future Work: The authors suggest further investigation into how non-ideal leakage distributions (i.e., deviations from perfect channel utilization) affect the attack complexity. They also imply that their framework can be extended to analyze more complex leakage scenarios and different types of side channels. The practical infeasibility of recovering the ISAP state on FULMINE suggests that leakage-resilient schemes can be effective, but further analysis on more complex implementations and attack scenarios would be valuable.
Summary updated