TL;DR
This paper demonstrates that machine learning, particularly Convolutional Neural Networks (CNNs), can effectively break the EdDSA digital signature algorithm using only a single power consumption trace during the attack phase. This highlights a significant vulnerability in public-key cryptography implementations and suggests that deep learning techniques are broadly applicable to side-channel attacks across different cryptographic primitives.
What Problem Does This Paper Address?
Side-channel attacks (SCAs) exploit physical leakage (like power consumption) from cryptographic implementations to extract secret information. While machine learning (ML) has shown great success in attacking symmetric-key ciphers (like AES), its application to public-key cryptography (PKC) has been less explored, with sparse results. This paper aims to bridge this gap by investigating the effectiveness of various ML techniques, including deep learning, for mounting power analysis attacks on EdDSA, a widely used public-key signature scheme. The challenge lies in adapting and evaluating these powerful ML tools for the specific characteristics of PKC implementations, which often employ different mathematical structures and countermeasures compared to symmetric ciphers.
Methods
The authors employ several machine learning techniques for profiling attacks:
- Template Attack (TA): Used as a baseline, this traditional profiling method relies on creating statistical models (templates) of the device's behavior.
- Random Forest (RF): An ensemble learning method that builds multiple decision trees to improve prediction accuracy.
- Support Vector Machines (SVM): A powerful classification algorithm that finds an optimal hyperplane to separate data, with variations for linear and radial kernels.
- Convolutional Neural Networks (CNNs): A deep learning architecture inspired by the human visual cortex, known for its effectiveness in pattern recognition. The paper uses a VGG-16-like architecture adapted for time-series data.
The core of the attack involves analyzing power consumption traces during the scalar multiplication operation within the EdDSA signature generation process. The goal is to recover the ephemeral private key r, which is derived from the message and a secret auxiliary key b. The paper also explores dimensionality reduction techniques like Principal Component Analysis (PCA) to see if they impact performance.
Datasets
The paper introduces a newly created, publicly available dataset for EdDSA side-channel analysis. This dataset is structured similarly to the ASCAD database for symmetric ciphers. It contains:
- Profiling Traces: Used to train the ML models.
- Attack Traces: Used to evaluate the performance of the trained models.
The dataset focuses on the power consumption during the lookup table (LUT) operation within the elliptic curve scalar multiplication of Ed25519, specifically targeting the fetching of precomputed chunks. The traces are derived from an STM32F4 microcontroller running an Ed25519 implementation from WolfSSL. The dataset consists of 6400 labeled traces, divided into profiling (5120) and attacking (1280) groups, with a 80/20 split for training/validation within the profiling set.
Key Insights and Ideas
- Deep Learning Dominance: CNNs emerge as the most powerful technique, achieving near-perfect accuracy and significantly outperforming traditional methods like Template Attacks.
- Single Trace Attack Feasibility: Remarkably, CNNs can achieve 100% accuracy with just a single trace in the attack phase when no dimensionality reduction is applied. This is a critical finding for practical security.
- Generalizability of CNNs: The CNN architecture used in this paper was previously shown to be effective for AES side-channel attacks. Its success on EdDSA suggests that deep learning models can generalize well across different cryptographic primitives and implementations, indicating common underlying patterns in side-channel leakage.
- Impact of Dimensionality Reduction: While PCA can reduce computational load, it significantly degrades the performance of CNNs, suggesting that raw, high-dimensional features are crucial for their effectiveness. SVM, however, remains robust to PCA.
- Minimal Data Requirement: The paper demonstrates that CNNs can achieve perfect profiling with as few as 30 traces per class for training, making the attack feasible even with limited profiling data.
Key Results
- Accuracy: Without dimensionality reduction, CNNs achieve 100% accuracy in recovering a single nibble of the key. Other methods like SVM and RF also achieve very high accuracies (above 99%). Template Attack performs the worst.
- Success Rate: CNNs achieve a 100% success rate (correct key candidate ranked first) with just one trace in the attack phase. Other methods require more traces to reach a similar success rate.
- Training Data Efficiency: For CNNs, 30 traces per class are sufficient to achieve perfect profiling accuracy.
- PCA Impact: Applying PCA (even with an optimal number of components) leads to a performance drop for CNNs, while SVM remains stable.
Limitations and Future Work
- No Countermeasures: The attack was performed on an Ed25519 implementation in WolfSSL that does not feature explicit countermeasures against side-channel attacks (beyond constant-time implementation). The authors acknowledge this limitation.
- Future Work: The authors plan to evaluate CNNs on Ed25519 implementations that include various countermeasures to test the limits of deep learning in side-channel analysis. They also aim to encourage the sharing of datasets for public-key cryptography SCA to foster further research.
Summary updated