Finding the Needle in the Haystack: Breaking Blinded RSA via Unsupervised Learning

TL;DR

Even with state-of-the-art protections like message/exponent blinding and constant-time execution, RSA isn't safe. This paper presents a framework that uses unsupervised machine learning to sift through power measurements and find a single "best trace" that leaks the secret key. By combining PCA with two new metrics—EBCF and ISD—the authors reduced the brute-force complexity of a 1024-bit RSA attack to a trivial $2^{15.5}$.

The "Single-Trace" Wall

In the world of Side-Channel Analysis (SCA), blinding is a formidable defense. By randomizing the message and the exponent for every execution, an attacker is denied the luxury of averaging thousands of traces to cancel out noise. You get one shot—one trace per randomization.

Prior unsupervised attempts (like k-means clustering) existed, but they faced a "feature selection" nightmare: How do you know which samples in a power trace actually correlate to the secret bits without a labeled training set?

Methodology: PCA + EBCF + ISD

The authors solve this by treating each power trace as a standalone dataset.

1. Preprocessing with PCA

Instead of manually picking "Points of Interest," the framework applies Principal Component Analysis (PCA) to segments of the trace. This concentrates the variance (and hopefully the leakage) into a few Principal Components.

2. Measuring Uncertainty: EBCF

The Entropy-Based Cost Function (EBCF) is the heart of the "trace selection." It uses the posterior probabilities from a Bayes classifier to calculate the uncertainty of a classification.

• Insight: A trace with low total entropy is one where the Square and Multiply operations are clearly separated in the latent space. By minimizing EBCF, we find the "cleanest" trace in a batch of 1,000 noisy measurements.

3. Exploiting Logic: ISD

The Square-and-Multiply algorithm has a physical law: a Multiply must be followed by a Square. If the ML model predicts Multiply -> Multiply, the sequence is "Illegal." The Illegal Sequence Detection (ISD) metric counts these violations. It serves as a sanity check—if a trace has many illegal sequences, the classification is likely wrong, even if the entropy (EBCF) is low.

Experimental Battleground

The researchers targeted a 32-bit ARM Cortex-M4 (STM32F303) running the GMP library. They implemented a "Multiply-Always" variant of RSA to ensure constant-time behavior.

Key Findings:

• Leaking Components: PCA successfully isolated the leakage. For the 320-bit key, PC 8 contained almost all exploitable information.
• Trace Selection: In a pool of 1,000 traces, the EBCF correctly identified the traces with the lowest actual classification error.
• Brute-Force Reduction: For 1024-bit RSA, while the ML wasn't perfect, the ISD identified exactly where the errors were, allowing a guided brute-force search that succeeded in under $2^{16}$ attempts.

Critical Insight: Why This Matters

The most profound takeaway is that unsupervised metrics can act as a proxy for ground truth. Usually, you need the real key to know if your attack is working. Here, EBCF and ISD allow an attacker to "know" they've found the right key (or are very close) just by looking at the internal consistency of the side-channel data and the cryptographic algorithm's rules.

Conclusion & Limitations

The attack is highly effective but currently relies on trace segmentation (knowing where one operation ends and the next begins). While the authors demonstrated this is possible via static alignment, highly jittered or asynchronous hardware might still pose a challenge.

Future research will likely see these metrics integrated into Deep Learning loss functions, creating "Self-Supervised" SCA models that need no labeled data at all.