Mélissa Rossi, 01/03/2018
I am glad to write the first post of our blog. I will describe a research project we started last summer. In our team, we are 4 members of the RISQ project out of 6 and we decided to study side-channel protections on lattice-based signature schemes. The entire work can be found in this article (eprint): Masking the GLP Lattice-Based Signature Scheme at Any Order written by Gilles Barthe, Sonia Belaïd, Thomas Espitau, Pierre-Alain Fouque, Benjamin Grégoire, Mehdi Tibouchi, and I for the EUROCRYPT 2018 conference.
The content of this paper may seem difficult to digest because we had to prove the security of each tiny part of a signature algorithm. Its frame is nonetheless very interesting; it involves a number of new techniques in the realm of masking countermeasures and I will do my best to present them clearly.
In addition to correctness and efficiency, one important aspect of the NIST post quantum competition is the security against physical attacks. Indeed, the chosen candidates should ultimately replace the currently deployed RSA and elliptic curve-based schemes. Protecting all candidates against side channels is an important challenge. Lattice-based cryptography is an attractive candidate in the post-quantum setting, as it allows to design implementations of a wide range of primitives with strong security guarantees and a good level of efficiency. However, protecting lattice-based schemes in an efficient manner poses new sets of challenges.
Protection against side channel attacks have been widely studied and powerful countermeasures exist. Among them, masking is probably the most deployed one. It consists in a secret sharing. Each sensitive intermediate value x is separated into d+1 shares xi , where d is a security parameter referred to as the masking order. The shares do not individually leak any information about x. To recover the value x, the attacker needs all d+1 shares xi. For a mod-p arithmetic masking (resp. Boolean masking), x is the sum mod p (resp. the xor) of all xi.
Masking can be done quite efficiently and has been applied to the decryption procedure of some lattice-based encryption schemes. But, the much more difficult case of lattice-based signatures has not been considered until now despite the obvious need of protection. One of the most studied lattice-based signature, BLISS, has resisted so far against classical attacks but has been repeatedly broken under various side-channel attacks (see the attacks from Bruinderink et al., Saarinen, Armknecht et al., Espitau et al. or Pessl et al. ).
The weakness of BLISS lied in two places: hard-to-protect implementations of Gaussian distributions and Gaussian rejection sampling. The bad news is that most lattice-based signature schemes contain either Gaussian distributions, Gaussian rejection sampling or both. However, there exist some other lattice-based signatures that look easier to protect with masking. Both the sampling of the randomness and the rejection sampling of signatures target uniform distributions in contiguous intervals. Examples of such schemes include the GLP scheme introduced in 2012. What’s more, this « Gaussian issue » has been considered so problematic that the designers of subsequent schemes have taken specific actions to deal with side-channels, such as dropping Gaussian distributions (See Dilithium) or using CacheAudit like in qTESLA. Now that some schemes avoid Gaussians in order to be easily protected against side channels, the next step is to effectively protect them with masking.
In our work, we describe the first masked implementation of a lattice-based signature scheme. We decided to focus on GLP and showed how to provably mask it in the Ishai–Sahai–Wagner (ISW) probing model at any order in a rather efficient manner. Even in the comparatively simple case of GLP, masking was surprisingly challenging!
The probabilistic nature of the signature generation, as well as its reliance on (uniform) rejection sampling, presented difficulties that had not occurred in earlier schemes, most of them deterministic.
- Most steps of the signing algorithm involve linear operations on polynomials that can be cheaply masked using mod-p arithmetic masking. However, for some operations like the generation of the randomness, this representation is less convenient and it seems harder to efficiently use arithmetic masking. Therefore, we had to carry out a conversion from Boolean masking to mod-p arithmetic masking. Such conversions have been introduced before in Coron et al., but only when the modulus p was a power of 2. Adapting such conversions to our setting required some tweaks and these conversions happened to be the costliest parts of our protection.
- Masking the hash function could have be done but it would have been terrible for performances. However, after a careful study, we figured that this masking is unnecessary. Indeed, to avoid this masking, we had to reveal the commitment value r. And we proved that the scheme is still secure with a public commitment. This stronger security property is intuitive when we see the signature scheme as the conversion of an identification protocol under the Fiat–Shamir transform. Indeed, the hash function computation corresponds to the verifier’s sampling of a random challenge c after it receives the commitment value r from the prover.
- Since some intermediate values are then revealed to the attacker, we had to adapt the notion of security from the ISW probing model to account for public outputs; the idea is not to state that public outputs do not leak relevant information, but rather than the masked implementation does not leak more information than the one that is released through public outputs.
Our proof of concept
We also made an unoptimized proof-of-concept implementation to assess the efficiency of the proposed countermeasure. Here are the implementation results on a single core of an Intel Core i7-3770 CPU.
In particular, we see that the overhead of our countermeasure with 2, 3 and 4 shares (secure in the d-probing model for d = 1, 2, 3 respectively) is around 15×, 30× and 73×. In view of the complete lack of optimizations of this implementation, we believe that those results are quite promising.
It is only the beginning of lattice masking
Our method should apply almost identically to other lattice-based Fiat–Shamir type signature schemes using uniform distributions in intervals (as opposed to Gaussian distributions). This includes the Bai–Galbraith signature scheme, as well as the recently proposed Dilithium signature.