In this blog post, we discuss Side Channel Analysis attacks (SCA), how to counter them with masking, and the framework we’ve introduced to design masking-friendly schemes, as a joint work between researchers, Thomas Espitau, Guilhem Niot, and Thomas Prest from PQShield, with Muhammed F. Esgin, Amin Sakzad, and Ron Steinfeld from Monash University.
In 2022, NIST announced the first post-quantum schemes for standardization: Kyber – for key encapsulation; Dilithium, Falcon, and SPHINCS+ for digital signatures. These schemes have been heavily scrutinized by the research community, and there is strong confidence in their mathematical foundations (lattices, hash functions).
However, some deployment environments are subject to a large range of attacks and implementation of these schemes requires extra care to counter side-channel attacks. We will discuss the masking techniques and proofs used in Plover, a lattice-based hash-and-sign signature.
Side-channel attacks (SCA)
When a device physically runs an algorithm, it might inadvertently reveal information about the operations it’s performing or the data being processed. For example, performing intense computations could deplete a smartphone’s battery or increase its temperature. Such information leaks could also occur through execution time, electromagnetic emissions, or sounds produced by the device.
Even subtle indicators such as the flicker of an LED could be exploited for data. (Ars Technica). These vulnerabilities fall under the category of side-channels, and are susceptible to Side-Channel Attacks (SCA), which exploit these leaks in order to access sensitive data.
Post-quantum cryptographic methods are not immune to SCAs (Saarinen). Attacks have been successfully demonstrated against schemes such as Falcon (Falcon Down, or ZLYW23).
For example, in ZLYW23, the authors exploit the fact that computations with a negative integer incur a larger power consumption. Indeed, negative numbers are likely to be represented with many bits set to ‘one’ (high Hamming weight). This allows attackers to recover the sign of the scalar product <sig, sk> during the signature process of Falcon, or equivalently, a partial direction of the secret. In the following figure, taken from ZLYW23, the arrow represents a signature. If <sig, sk> is positive, we know that sk is in the orange zone; if it is negative, sk is in the blue zone.
By observing a sufficient number of signature generations, it is possible to recover sk from this leakage. This demonstrates that even a leakage as small as one bit per execution can be devastating. Therefore, in scenarios susceptible to SCAs, it’s crucial to implement protective measures against them.
How to employ masking to defeat SCA
Numerous strategies can be employed to mitigate side-channel attacks (SCA), but let us concentrate on masking – one of the most studied, most general, most effective, and commonly-used countermeasures.
The principle of masking is to spread sensitive data across multiple shares, complicating an attacker’s attempt to simultaneously acquire all shared values together. Masking involves dividing each sensitive variable into d random parts, such that only the sum of all parts restores the original variable. For example, for x = 7 in ℤ16 (the set of integers modulo 16), a possible masking of x with three shares could be (12, 5, 8), because (12 + 5 + 6) mod 16 = 23 mod 16 = 7. Experiments indicate that when using d shares, the difficulty of executing an attack grows exponentially with d.
However, the challenge lies in processing operations on masked data. Certain operations, such as addition modulo q, are straightforward. For instance, given shares (12, 5, 6) for 7 and (7, 4, 10) for 5, the sum ((12+7) mod 16, (5+4) mod 16, (6+10) mod 16)) equals (3, 9, 0), which correctly represents the sum 12. This operation requires only d additions in ℤ16, making masked addition efficient. Generally, linear operations, like multiplying a masked vector by a matrix, can also be masked efficiently. However, other types of operation, such as multiplication, might not be as straightforward to mask.
Masking standardized schemes
Unfortunately, masking techniques are difficult to implement efficiently for the standardized schemes Falcon and Dilithium.
Thomas Prest previously discussed the case of Dilithium in detail. Masking Dilithium comes with two main difficulties:
- The need to sample small secret values
- The need to evaluate the sign of a masked value.
Both of these requirements are very expensive to implement with masking, and masked implementations of Dilithium can only support a small number of shares.
To tackle this, our research team at PQShield introduced the masking-friendly signature scheme Raccoon, submitted to the NIST PQC call for additional signatures. Raccoon solves the aforementioned issues, and scales efficiently to any number of masking shares!
When it comes to Falcon (the other lattice-based NIST standardized signature scheme) masking is even more difficult, and how to perform it practically, remains an open problem. Falcon is based on a fundamentally different paradigm to Dilithium, which relies on a complex sampling operation requiring the use of floating-point arithmetic. This is critical, as there is no known efficient way to implement masking for floats.
The signature scheme Mitaka is a Falcon-like signature scheme introduced in 2021, which was claimed to be easy to mask, and an efficient solution to counter SCAs. However, the proof of their masking was shown by Thomas Prest, lead researcher at PQShield to be flawed, a discovery that returned us to the initial open question.
That is where our most recent work comes into play.
PQShield and Monash researchers have jointly authored the article “Plover: Masking-Friendly Hash-and-Sign Lattice Signatures”, published at EUROCRYPT 2024, a flagship IACR-affiliated cryptography conference. In this paper, we realise that techniques underlying Raccoon are in fact very generic, and can be leveraged in the masking of various schemes with additional technical tools. Notably, we introduced the signature scheme Plover, the first Falcon-like masking-friendly signature scheme!
Ryan Claus (Gold Coast Wildlife Photography)
Image by Mark David
Our Masking Toolkit
The limitations of Falcon’s resistance to side-channel attacks came into the discussion as colleagues from Monash University visited PQShield’s Paris office during Summer 2023.
After the successful design of Raccoon, a natural discussion led us to think about the applicability of its techniques to Falcon. And so, we sat around a table to draft some ideas.
This opened the path to a fruitful collaboration that lasted several months, not only leading to Plover, the first Falcon-like, masking-friendly signature scheme, but also to the formalization of a generic toolkit for designing easy-to-mask lattice-based schemes.
Our toolkit comes with three components:
- AddRepNoise: an algorithm to sample short vectors from a given distribution in masked form. AddRepNoise was initially introduced in Raccoon, but not formally proven. This is a recurrent need in lattice-based schemes like Plover and Raccoon.We now give a high level intuition for AddRepNoise. The idea of the algorithm is to compute, in masked form, the sum of many small noises in such a way that only a fraction of them may leak. The algorithm proceeds by first defining share vectors [[vi]] for i = 1, …, r with shares sampled from a small uniform distribution. It then applies a typical refresh operation (not detailed here) to each [[vi]] to redistribute or equalize noise among shares. The last step consists in computing their sum [[v]] = [[vi]] + … + [[vr]].Thanks to the noise redistribution, an observer would need to learn all shares of some [[vi]] to learn useful information, which is exponentially hard. So its best strategy will be to leak information about individual noises during the first phase. As leaking more information gets exponentially harder, it ensures that, at most, a few small noises leak.Consider a concrete example using integers modulo 16 with d=4 shares and r=2 noise addition repetitions. Assume that noises are sampled from a uniform distribution in the set {0,1,2,3}. In the first step, the algorithm samples [[v1]] = (1,2,0,3), and [[v2]] = (1,0,1,2). Then it redistributes the shares of [[v1]] to (15, 7, 2, 14), and [[v2]] to (0, 9, 3, 8). Observe that the new shares sum to the same value as before. Finally it computes [[v]] = [[v1]]+[[v2]] = (15, 0, 5, 6). After refreshing, learning less than d=4 shares of [[v1]] or [[v2]] indeed leaks only random values, and the only leakage remaining is before refreshing.This example highlights the effectiveness of using modular arithmetic and structured noise addition in cryptographic protocols for distributing a secret across multiple holders securely.
- We employ “noise flooding”, a generic method to replace non-linear operations with linear operations. At the cost of increasing the size of parameters, it is possible to replace hard-to-mask operations with much simpler ones.Most lattice-based schemes do indeed compute signatures as a linear combination of the secret plus some noise. In order to make the signature independent of the secret, usual techniques include performing rejection sampling (Dilithium), or having a complex noise distribution (Falcon). Noise flooding removes the need for these by accepting that signatures leak part of the secret, but security remains guaranteed by taking a (much) larger noise width.
- New proof techniques, SNIu, to prove the security of masked schemes in the t-probing model, designed with our toolkit.
The most common type of security check used in the context of side channel resistance is called the probing model, first described by Ishai, Sahai, and Wagner in 2003. In simple terms, this model assumes that an attacker can select up to t specific internal variables in an algorithm to secretly listen to the data passing through them. The algorithm is considered secure under this model if the attacker, even after obtaining these t values, gains no useful information about the original secret input of the algorithm.
Earlier proof techniques from Barthe and others in the probing model split all variables into d shares, and show that the algorithm is secure up to d – 1 probes. In our work, we introduce a new concept called t-strong non-interference with unshared input values (t-SNIu). This idea introduces a new twist: algorithms now also take new, unique inputs that aren’t mixed or shared. Our model shows that only a small number of these inputs leak during the execution in the probing model. This is leveraged by algorithms such as AddRepNoise, for which the small noises are secret, but if there are sufficiently many, and only a fraction of them leaks, the scheme remains secure.
Introducing Plover, the first Falcon-like masking friendly signature scheme
As a first application of our toolkit, we introduce Plover, which gives a positive answer to the so far open question of having a maskable lattice-based scheme following the same paradigm as Falcon.
Its parameters are comparable with Raccoon, and the performance of Plover also scales very well with the number of masking shares. Noting d the number of shares used through the algorithm, the complexity of Raccoon and Plover scales by a factor d · log(d).
Plover is also the first scheme to benefit from our new proof techniques, having fully-proven masking security. Indeed a small part of Raccoon was lacking a formal proof, and our paper closes this gap.
As a result, we hope other researchers will also leverage these new results in their work, and make post-quantum cryptography more easily amenable to even the most exposed environments.