Simple Power Analysis of Polynomial Multiplication in HQC

summary

The gist

The single-trace Simple Power Analysis (SPA) attack against HQC exploits power consumption leakage during polynomial multiplication at the beginning of HQC decryption to recover a significant portion…

In short

The research performed a single-trace Simple Power Analysis (SPA) attack against HQC decryption by monitoring power consumption during polynomial multiplication at the start of the process. The attack successfully recovered a significant portion of the private key with a 99.69% success rate. This demonstrates that certain HQC implementations are vulnerable to SPA attacks, and new multiplication functions can offer performance gains while resisting this specific side-channel threat.

Key concepts

Simple Power Analysis (SPA)
This attack method analyzes the overall power consumption trace of a cryptographic operation to identify patterns. The researchers looked for distinct power signatures corresponding to specific steps in the polynomial multiplication algorithm, such as those related to key bits, allowing them to deduce secret information without needing complex statistical analysis.
Hamming Quasi-Cyclic (HQC)
HQC is a specific type of lattice-based public-key cryptosystem. The paper focuses on its decryption process because the power consumption leakage occurs during the initial polynomial multiplication step, which is crucial for recovering the private key from encrypted data.
Polynomial Multiplication (Karatsuba/mul1)
The core mathematical operation targeted is multiplying two polynomials using a recursive Karatsuba algorithm, specifically implemented via the mul1 algorithm. The power consumption during this specific multiplication step leaks information about the private key polynomial 'y' being processed.

Terminology used across episodes

This episode discusses

The paper

Simple Power Analysis of Polynomial Multiplication in HQC · Read on arXiv

Czech Technical University in Prague

The Hamming Quasi-Cyclic (HQC) cryptosystem was selected for standardization in the fourth round of the NIST Post-Quantum Cryptography (PQC) standardization project. The goal of the PQC project is to standardize one or more quantum-resistant public-key cryptographic algorithms. In this paper, we present a single-trace Simple Power Analysis (SPA) attack against HQC that exploits power consumption leakage that occurs during polynomial multiplication performed at the beginning of HQC decryption. Using the ChipWhisperer-Lite board, we perform and evaluate the attack, achieving a 99.69% success rate over 10 000 attack attempts. We also propose various countermeasures against the attack and evaluate their time complexity.

DOI: 10.5220/0014418500004061

Transcript

Introduction to the show: ident: Security Radio. Generated commentary on the latest security and cryptography papers.

Nadia: We're looking at the paper: "Simple Power Analysis of Polynomial Multiplication in HQC".

Elias: Here's the gist of the paper. The single-trace Simple Power Analysis (SPA) attack against HQC exploits power consumption leakage during polynomial multiplication at the beginning of HQC decryption to recover a significant portion of the private key Attack Target and Context The paper presents a single-trace simple power analysis (SPA) attack against the Hamming Quasi-Cyclic (HQC) cryptosystem which exploits power consumption leakage that occurs during polynomial multiplication performed at the beginning of HQC decryption.

Nadia: The goal of this attack is to recover the private key by analyzing power consumption during polynomial multiplication that is performed at the beginning of HQC decryption.

Elias: The target implementation for this attack is the Additional implementation of HQC included in the NIST Round 4 submission.

Nadia: This target implementation is particularly relevant as it is included in both the PQClean and liboqs libraries.

Title and authors: Nadia: So we're talking about this paper now titled Simple Power Analysis of Polynomial Multiplication in HQC. It’s really about exploiting power leakage during polynomial multiplication right at the start of HQC decryption to pull out a piece of the private key.

Elias: Yeah, and they’re focusing on the specific implementation used in both PQClean and liboqs, which is important for anyone working with these post-quantum systems. This attack targets how that multiplication is done using a recursive Karatsuba algorithm.

Priya: So what exactly is the core problem here? Is this just a theoretical weakness, or are we talking about something practical that an attacker can actually use against real hardware?

Nadia: It's practical, Priya. They use the ChipWhisperer-Lite board to measure power traces and they found a success rate of ninety-nine point six nine percent over ten thousand attack attempts <ref:2601.07634#pg1>. That’s a really high number for a single trace analysis; it shows this is quite effective when you get the right conditions.

Elias: The specific vulnerability they're hitting is in the base-case sixty-four-bit multiplication algorithm that gets used after the Karatsuba recursion hits sixty-four bits <ref:2601.07634#pg3,base-case 64-bit multiplication algorithm>. They find that by repeating this attack on different parts, or limbs, of the private key polynomial, you can potentially recover the entire private key.

Priya: So if I'm just listening to this, what does that mean for my data security? Am I worried about something leaking during standard HQC operations?

Nadia: It means if someone can get a single power trace of the decryption process, they can get a significant portion of that private key. They aren't just looking at one spot; they are analyzing how the multiplication looks—specifically, by observing a noticeable drop between neighboring peaks in the measurement record to figure out four bits of that key limb.

Elias: And what’s interesting is that their analysis shows all their errors come from just those first four bits of the key limb, and only when those bits are zero or fifteen. That gives them a very specific pattern to look for.

Priya: That specificity is helpful, but I wonder how strong this attack really is against real-world defenses. Are these findings based on an implementation that's actually hardened?

Title and authors: Nadia: They tested their countermeasures, and they found that reducing the size of the lookup table to just one by using 'b' itself was a way to slow things down a bit, but they also mentioned removing a cache timing attack countermeasure and replacing it with classical masking.

Elias: And on the performance side, they measured how much slower these defenses made things compared to the original implementation. They found that their protected functions, base mul2 and base mul3, were significantly faster than the original base mul function.

Priya: Faster is good for performance in general, but if it means we have to use more complex masking techniques just to stop a power analysis attack, what’s the trade-off?

Nadia: The paper shows that base mul2 was about two point three times faster than base mul, and base mul3 was about six point nine times faster. So you get a big speed boost while trying to stay protected from this specific SPA attack.

Elias: But they also noted a caveat in their testing; they said the masking technique is effective for stopping the attack, but it might still allow an attacker to recover both the masked value of that key limb and the mask itself.

Priya: So if we implement these new multiplication functions, base mul2 or base mul3, are we guaranteed protection against this specific SPA method? Or is there another way they could attack it?

Nadia: The paper implies that by implementing those specific improved functions, you can be resistant to the proposed SPA attack while still getting a performance advantage over the standard setup. They are showing how to make it faster and safer at the same time.

Elias: In this work, they propose classical masking techniques specifically Boolean masking to protect private key values during those multiplication steps in HQC decryption. This allows for computation while obscuring the actual values being processed from power analysis attacks.

Priya: That sounds like a solid defense mechanism because it's based on established ideas, but I still have to wonder about the complexity of implementing that masking correctly across all the polynomial multiplication steps.

Nadia: Exactly. They did test these improved functions against ten million calls and they showed they were resistant to their SPA attack while offering that performance benefit we just talked about.

Title and authors: Elias: Overall, this paper, "Simple Power Analysis of Polynomial Multiplication in HQC," presents a new single-trace simple power analysis attack that recovers a significant portion of the private key with a ninety-nine point six nine percent success rate.

Priya: It’s interesting how they focused on just one part of the decryption process—the polynomial multiplication at the very beginning—to get away with this level of recovery.

Nadia: That focus is what makes it simple, Priya; it isolates a specific mathematical operation and shows that even in post-quantum cryptography, power leakage can reveal key material if the implementation isn't careful.

Elias: They also introduced new multiplication functions, base mul2 and base mul3, which they show are resistant to this proposed SPA attack while still offering significant performance advantages over the original implementation.

Priya: So, if we look at what this means for the next few years in PQC development, are we going to need to bake these kinds of specific countermeasure evaluations directly into every cryptographic primitive?

Nadia: It suggests that analyzing those specific multiplication routines—the Karatsuba algorithm implementation, for instance—is a necessary step when hardening any new standard like HQC.

Elias: They're also exploring the application of classical masking techniques like Boolean masking to protect private key values during those multiplication steps in HQC decryption, which is a concrete defense they put forward.

Priya: I'm still thinking about what they didn't cover deeply—how much effort it takes to truly secure that masking against sophisticated side-channel attacks beyond this specific SPA test.

Nadia: They flagged that the masking technique might still allow an attacker to recover both the masked value of a and the mask value, which is a fair limitation they pointed out.

Elias: So, in conclusion, this paper on Simple Power Analysis of Polynomial Multiplication in HQC shows how a single trace can recover ninety-nine point six nine percent of the private key with their ten thousand attempts <ref:2601.07634#pg1,Simple Power Analysis of Polynomial Multiplication in HQC>.

Priya: It’s a stark reminder that even when we have these new post-quantum algorithms, the physical implementation details are just as vulnerable as the math itself.

Nadia: That's right, it shows that focusing on how polynomial multiplication is actually coded is crucial for security in this area.

The paper's summary: Nadia: So, to put it simply, this paper shows that you can take just one power trace during the very first step of HQC decryption and pull out a chunk of the private key.

Elias: Yeah, they’re looking at that initial polynomial multiplication right where everything starts happening. It targets the specific way this multiplication is done using a recursive Karatsuba algorithm.

Priya: So, what does that actually mean for us? Is this just a theoretical weakness, or can someone actually use this against real hardware?

Nadia: It’s practical because they used actual hardware, the ChipWhisperer-Lite board. and they got a success rate of ninety-nine point six nine percent over ten thousand tries. that’s high enough to show it works when you get the right conditions.

Elias: The paper focuses on recovering a specific part of the private key polynomial, the value of y, by analyzing how power consumption changes during that multiplication process.

Priya: If they can recover a significant portion of the key from just one trace, that’s pretty alarming for anyone using this system. what are the numbers on what they found?

Nadia: They found that all their errors come from just the first four bits of that key piece, and specifically only when those bits are zero or fifteen. it gives them a very clear pattern to look for in the measurement record.

Elias: That specific pattern is what makes it simple for the attack; you watch for a noticeable drop between two neighboring peaks in the power trace to figure out those four bits.

Priya: So, this tells us that the implementation details of how they coded that multiplication routine are actually very exposed to this kind of physical analysis.

Nadia: Exactly; it shows that even in post-quantum cryptography like HQC, focusing on just one mathematical operation at the start of decryption can lead to a big portion of the secret key being recovered.

Elias: They’re not just finding a flaw; they’re proposing solutions too, introducing new multiplication functions called base mul2 and base mul3 that are resistant to this power analysis attack.

Priya: So the authors are showing us how to make it faster while also trying to stop this specific type of side-channel leakage. what’s the performance trade-off there?

Nadia: They found that base mul2 was about two point three times faster than the original base mul, and base mul3 was about six point nine times faster. it means you get a significant speed boost while trying to stay protected from this SPA attack.

Elias: But they also admitted that the masking technique they introduced might still let an attacker recover both the masked value of that key piece and the mask itself, which is a limitation they pointed out.

Priya: That’s a real caveat; so even with these new functions and masking, there’s still some room for improvement in security against more advanced attacks.

Nadia: True. the paper proves this single-trace SPA attack works well against the specific implementation they were testing, but it highlights that you need to be careful about which parts of the algorithm you try to protect.

Elias: In short, this work confirms that a simple power analysis can recover a large piece of the private key from polynomial multiplication in HQC if not properly protected. and now we look at how these new functions attempt to fix it.

The paper's improvements: Tom: So, to recap, the paper didn't just show a vulnerability; they also suggested ways to fight it by creating new multiplication functions that are harder to attack and using classical masking techniques.

Nadia: Yeah, they developed these new functions base mul2 and base mul3 which are resistant to the simple power analysis attack while still being much faster than the original implementation.

Elias: The idea is that you get this significant performance advantage without introducing timing vulnerabilities that an attacker could exploit during those multiplication steps.

Priya: So they’re trying to find that sweet spot between having a secure, masked calculation and actually getting a usable speed boost for the system. what does the masking technique actually do here?

Nadia: They implemented Boolean masking, which is a classical method to protect private key values during those multiplication steps by obscuring the actual values being processed from power analysis attacks.

Elias: It’s an established concept, but they admit that it might still allow someone to recover both the masked value of that key piece and the mask value itself. so it’s not a complete fix for every scenario.

Priya: That means we still have to be careful; we get protection against this specific attack, but there are other ways an attacker could try to get around that masking later on.

Nadia: They flagged that limitation, and they showed their improved functions base mul2 and base mul3 were still resistant to the SPA attack when they tested them over ten million calls.

Elias: Their conclusion is basically that implementing these new multiplication routines offers a way to compute faster while staying protected from this specific side-channel method of extracting key material.

Priya: It’s interesting because it shows that hardening cryptography isn't just about changing the math, but also about making sure the low-level code and how it handles those calculations is also robust against physical leakage.

Nadia: Right; so these new functions are a practical step for developers trying to secure their post-quantum implementations without totally sacrificing performance. we’ll look next at what else is going on in the world of AI security because this paper shows how physical implementation leaks can be just as damaging as the math itself.

Conclusion: Tom: So we’re wrapping up this look at "Simple Power Analysis of Polynomial Multiplication in HQC," which basically shows how you can recover a chunk of the private key from just one power trace during the early decryption steps.

Nadia: Yeah, it really boils down to this: physical implementation details matter just as much as the underlying math when you’re dealing with post-quantum stuff like HQC.

Elias: They did show that these new base mul2 and base mul3 functions offer a performance boost while being resistant to this specific simple power analysis attack.

Priya: So, the main thing we see is that you can get this speed improvement without just relying on abstract theoretical protections; you need concrete code changes.

Nadia: Exactly; it’s about making the actual polynomial multiplication routine physically harder to analyze using power consumption measurements.

Elias: They also introduced classical masking techniques, like Boolean masking, which is a way to obscure those intermediate private key values during the multiplication steps in HQC decryption.

Priya: I still have that concern that even with these masks, an attacker could potentially recover both the masked value and the mask itself later on.

Nadia: True; they pointed out that there’s still room for refinement in how robust those masking schemes are against more sophisticated side-channel attacks.

Elias: In summary, this paper confirms that focusing on how polynomial multiplication is actually coded is crucial for security in this area because physical leakage can reveal key material.

Priya: It’s a solid piece of research showing the practical side of measurement and exploitation when applied to these new cryptographic standards.

Nadia: And it sets a benchmark for developers needing to be extra careful about the low-level operations in any post-quantum scheme they build.

Elias: We’ll keep an eye on those findings as we look at other HQC implementations out there and see if this pattern holds true elsewhere.

More episodes

← Home