Tout D'abord

Eric Piret

Je Tiens

Pierre-Alain Fouque

Sihem Mesnager

Karine Ville

REMERCIEMENTS

B References

Résumé en français

La cryptographie en boîte blanche (white-box cryptography) est le domaine de la cryptographie dédié à la conception d'implémentations de primitives cryptographiques sûres face à un attaquant ayant le contrôle total du dispositif sur lequel est déployée cette implémentation. L'implémentation en boîte blanche d'une primitive est donc une implémentation dont un attaquant ne peut pas retrouver la clé même en ayant son contrôle total, ainsi que le contrôle de la plateforme sur laquelle elle est exécutée. L'un des enjeux majeurs de sécurité auquel la cryptographie boîte blanche doit répondre est la résistance aux attaques par canaux cachés (side-channel attacks). A cette fin, les designers ont pour but d'éliminer ou atténuer au maximum toute dépendance entre les variables de l'implémentation et ses données sensibles, comme les clés secrètes. L'une des contre-mesures classiques pour cela est l'utilisation de schémas de masquage. Néanmoins, les implémentations mettant en oeuvre des schémas de masquage sont vulnérables à un autre type d'attaques : les attaques par faute, dans lesquelles un attaquant perturbe intentionnellement le fonctionnement normal de l'implémentation dans le but d'extraire de potentielles informations de cette exécution modifiée.

De plus, au delà d'assurer la sécurité de leurs implémentations dans ce modèle d'attaques, les concepteurs d'implémentations en boîte blanche doivent également prendre en compte leurs coûts tout en optimisant leurs performances. En d'autres termes, la question du compromis entre la sécurité, les coûts et les performances d'une implémentation cryptographique demeure dans le domaine de la cryptographie en boîte blanche. La cryptographie lightweight (légère) est le domaine de la cryptographie dédié aux implémentations compatibles avec des dispositifs aux capacités limitées. Ces dispositifs, de par leurs cas d'usages, sont fréquemment vulnérables aux attaques en boîte blanche. Par conséquent, la question de la "white-boxabilité" des algorithmes lightweight se pose également.

La contribution de cette thèse est double. Dans la première partie, nous discutons l'adéquation à une implémentation en boîte blanche des dix primitives finalistes du concours de standardisation des algorithmes lightweight du NIST. Nous développons par la suite une implémentation en boîte blanche tabularisée de GIFT, la principale sous-fonction cryptographique de GIFT-COFB. Pour finir, nous décrivons une attaque différentielle sur cette construction, et étudions l'adéquation des critères de résistance d'une SBox à cette attaque avec les critères de choix de la SBox de GIFT.

Dans la seconde partie de ce manuscrit, nous décrivons la construction de notre schéma de masquage de l'opération bit-à-bit AND résistant à l'introduction de fautes, et pouvant être implémenté avec uniquement des opérations bit-à-bit. Pour cela, ce schéma utilise un code correcteur d'erreurs, et plus précisément un code correcteur d'erreurs BCH. Nous décrivons également comment les opérations NOT et XOR peuvent être implémentées afin d'être compatibles avec ce schéma de masquage, pour qu'il puisse être appliqué aux implémentations bitslicées de toute primitive cryptographique.

1 White-Boxabilité des Primitives Finalistes du Concours de Standardisation des Algorithmes Lightweight du NIST Cette thèse débute par l'analyse de la "white-boxabilité" des finalistes du concours de standardisation des algorithmes lightweight du NIST [SMC `21]. En effet, les primitives cryptographiques lightweight sont largement déployées sur des dispositifs aux capacités limitées, qui sont fréquemment sujets aux attaques en boîte blanche en raison de leurs cas d'usages. La question de la résistance de ces candidats à la standardisation face à ces attaques s'est donc posée. Après analyse des spécifications des dix finalistes, nous avons établi que la primitive la plus adéquate à être implémentée en boîte blanche est GIFT-COFB, et plus précisément sa principale sous-fonction cryptographique GIFT [BPP `17a]. Pour cela, différents critères ont été pris en compte, comme la sécurité de la primitive à la publication d'un état (state), ou la répartition des variables secrètes (notamment liées à la clé) tout au long de la primitive [START_REF] Charlès | Review of the white-box encodability of NIST lightweight finalists[END_REF].

L'idée derrière la conception de cette implémentation consiste à encoder les sorties de chaque instance de la SBox de 4 bits de GIFT, afin de construire une nouvelle table de substitution de 8 bits, nommée TBox. A cette fin, tout d'abord, une seconde table de substitution de 4 bits est choisie aléatoirement. Les quatre ensembles de 2 bits consécutifs en sortie de la TBox sont obtenus en utilisant 4 encodages de 2 bits différents, avec en entrée un bit de sortie de la SBox de GIFT et un bit de sortie de la seconde table de substitution. Pour que l'implémentation conserve la fonctionnalité de GIFT, les décodages sont appliqués en entrée des TBoxes correspondantes de la ronde suivante, déterminées en fonction de la permutation de 128 bits de GIFT.

Néanmoins, nous démontrons que la connaissance par l'attaquant de la SBox de GIFT implique la possibilité d'une attaque différentielle visant deux rondes consécutives de GIFT afin déterminer la clé utilisée. Pour finir, nous étudions l'existence de potentielles SBoxes de 4 bits vérifiant les propriétés de celle de GIFT tout en empêchant la possibilité de cette attaque.

Un Nouveau Schéma de Masquage Résistant Aux Attaques par Fautes

Le bitslicing consiste à implémenter une primitive comme un circuit combinatoire en software [START_REF] Mercadier | Usuba: Optimizing & trustworthy bitslicing compiler[END_REF]. Nombre d'implémentations en boîte blanche sont basées sur des implémentations bitslicées elle-mêmes composées d'opérations bit-à-bit, sur lesquelles sont appliqués des schémas de masquage. Les schémas de masquage étant par nature des contre-mesures contre les attaques par canaux cachés, nous avons développé un nouveau schéma de masquage composé d'opérations bit-à-bit et résistant aux attaques par faute [START_REF] Gravouil | A new generic fault resistant masking scheme using error-correcting codes[END_REF]. Plus précisément, ce schéma peut être appliqué sur des implémentations bitslicées de toutes primitives cryptographiques et corriger de potentielles fautes sans détériorer ou stopper l'exécution dès leur détection. Ces implémentations vont donc toujours retourner des résultats, qui sont corrects même en cas d'introduction de fautes, ce qui constitue un réel bénéfice dans ce domaine des schémas de masquage résistants aux fautes.

Pour cela, nous utilisons un code correcteur d'erreurs BCH, puisque c'est un code cyclique qui permet donc une facile gestion de la parité du poids de Hamming de ses mots de code, et puisque son processus de correction peut être implémenté avec uniquement des opérations bit-à-bit (AND, OR, XOR, NOT). La valeur binaire de chaque mot de code est cette parité. Ainsi, les mots de code de poids de Hamming pair représentent la valeur 0, et les mots de code de poids de Hamming pair représentent la valeur 1.

Schémas de Masquage

Dans un corps K, masquer une variable X consiste à construire n in sousvariables x i nommées shares, telles que X " x 0 ' . . .' x nin´1 . Par construction, chaque ensemble d'au plus n in ´1 shares est indépendant de la variable originale X, c'est-à-dire @i P t0, . . . , n in ´1u, @v P K, @pv 0 , . . . , v i´1 , v i`1 , . . . , v nin´1 q P K nin´1 , P ppX 0 , . . . , X i´1 , X i`1 , . . . , X nin´1 q " pv 0 , . . . , v i´1 , v i`1 , . . . , v nin´1 q|X " vq " P ppX 0 , . . . , X i´1 , X i`1 , . . . , X nin´1 q " pv 0 , . . . , v i´1 , v i`1 , . . . , v nin´1 qq Les valeurs des shares x 0 , . . . , x nin´2 sont choisies aléatoirement, puis la dernière share x nin´1 est calculée telle que x nin´1 " X ' x 0 ' . . . ' x nin´2 . Comme développé dans [BBP `16], la complexité de l'extraction d'information sur X devient exponentielle en le nombre de shares n in .

Pour une fonction f avec n entrées X i et une sortie Y , un schéma de masquage dans lequel chaque entrée est divisée en n in shares X i,j et chaque sortie en n out shares Y j décrit n out sous-fonctions F j telles que Y 0 " F 0 pX 0,0 , . . . , X 0,nin´1 , . . . , X n´1,0 , . . . , X n´1,nin´1 q Y 1 " F 1 pX 0,0 , . . . , X 0,nin´1 , . . . , X n´1,0 , . . . , X n´1,nin´1 q . . . Y nout´2 " F nout´2 pX 0,0 , . . . , X 0,nin´1 , . . . , X n´1,0 , . . . , X n´1,nin´1 q Y nout´1 " F nout´1 pX 0,0 , . . . , X 0,nin´1 , . . . , X n´1,0 , . . . , X n´1,nin´1 q , avec $ ' ' & ' ' % X i " nin´1 À j"0 X i,j @i P t0, . . . , n ´1u Y " nout´1 ř j"0 Y j " f pX 0 , . . . , X n´1 q

Détermination des Paramètres

Afin de garantir sa sécurité contre les probing attacks de premier ordre, nous avons construit notre schéma pour qu'il respecte conjointement trois propriétés, à savoir correctness, non-completeness et uniformity ( [START_REF] Nikova | Threshold implementations against side-channel attacks and glitches[END_REF]). Ces propriétés impliquent respectivement que la somme des shares en sortie du schéma est bien égale au résultat de la fonction d'origine avec les mêmes entrées, que chaque share en sortie ne dépend jamais de tous les shares d'une même entrée et que les valeurs possibles des shares d'une même sortie sont équiprobables.

Respecter conjointement ces propriétés introduit des contraintes sur le choix des paramètres de notre schéma. C'est pourquoi nous avons construit notre schéma de masquage avec 4 shares pour chaque entrée et 4 shares en sortie. Cela a également influencé le choix des paramètres du code correcteur d'erreurs BCH mis en oeuvre, à savoir sa longueur et son polynôme générateur. De même, le fait que chaque mot de code représente la parité de son poids de Hamming en valeur binaire implique que le polynôme générateur soit de parité impaire, afin qu'il soit possible de construire des mots de code de parités différentes.

Design du Schéma de Masquage Introduction 3 Thesis Introduction

Security Models and White-Box Cryptography

Cryptographic primitives were first designed so that an attacker having access to only its inputs and corresponding outputs would not be in capacity of retrieving the secret key. This security model has been labeled as "black-box" security model, where implementing a cryptographic primitive is supposed to be secure. Hence, any weakness in an implementation can only arise from the design of the primitive itself and potential relations between its inputs and outputs.

Nevertheless, this assumption rapidly turned out to not be realistic. Indeed, implementations are particularly sensitive to attacks labeled as "side-channel attacks". Those types of attacks exploit flaws of the implementation that are correlations between some sensitive data of the algorithm, for instance the secret key bits, and physical data leakage during some executions of this implementation. Those data leakages can be of different types, as for example execution time, electromagnetic emanations, or power consumption of the device executing the implementation [START_REF] Caddy | Side-channel attacks[END_REF]. Consequently, side-channel countermeasures aim to eliminate any relation between sensitive data of the primitive and those physical data leakages [START_REF] Prouff | Masking against sidechannel attacks: A formal security proof[END_REF]. For instance, in the timing attack case, conditional statements depending on the sensitive data must be avoided. An attacker exploiting those flaws as well as potential weaknesses in the design of the primitive spotted in the black-box security model is considered being an attacker in the "grey-box" security model.

Over the course of the last twenty years, the development of devices like Internet of Things (IoT) devices has led to an increasing need of cryptography. Likewise, the expansion of subscription television and then streaming services has brought a need of cryptography to ensure correct and secure Digital Right Managment (DRM). Nevertheless, the open nature of these devices and services constitute an additional threat to the security of these cryptographic primitives. Indeed, a potential attacker can then have total access over the execution platform of the algorithm and its implementation : he can even be the owner of the device. This model of attacker is considered an attacker in the "white-box" security model. A primitive being secure in this model imply that it is, first of all, secure in the grey-box model and thus naturally in the black-box model, and that it is not possible to recover the key for an attacker having total access to the implementation and its execution platform.

To protect the key from such attacker, one of the first and most known method that was proposed by Chow et al. [START_REF] Chow | White-box cryptography and an AES implementation[END_REF] in 2002 consists in tabularizing then encoding the implementation. Their original idea was to turn the AES algorithm into a giant look-up table mapping each possible plaintext to its corresponding ciphertext, consequently avoiding any manipulation of the key. Nevertheless, such a look-up table matching all 128-bit plaintexts to 128-bit ciphertexts would be too heavy and thus unrealistic (2 128 ˚128 " 2 135 bits). Therefore, the chosen solution was to build a network of encodings look-up tables. Nonetheless, this scheme has been broken many times in the literature

([BGEC04], [MRP13], [LR13]).
Indeed, side-channel attacks inherited from the grey-box attack model are one of the main threats a white-box implementation need to thwart. The Chow et al. implementation is notably sensitive to this type of attacks. Among the variety of countermeasures to side-channel attacks, masking is the most developed topic.

Variable Sharing and Masking Schemes

In a field K, masking a variable X consists in splitting it into n in sub-variables X 0 , . . . , X nin´1 of K named shares, such that X " X 0 ' . . . ' X nin´1 . Furthermore, each tuple of at most pn in ´1q variables X i is independent from X, i.e. @i P t0, . . . , n in ´1u, @v P K, @pv 0 , . . . , v i´1 , v i`1 , . . . , v nin´1 q P K nin´1 , P ppX 0 , . . . , X i´1 , X i`1 , . . . , X nin´1 q " pv 0 , . . . , v i´1 , v i`1 , . . . , v nin´1 q|X " vq " P ppX 0 , . . . , X i´1 , X i`1 , . . . , X nin´1 q " pv 0 , . . . , v i´1 , v i`1 , . . . , v nin´1 qq

To that end, the values of the shares X 0 , . . . , X nin´2 are chosen uniformly at random in K, and the value of the last share X nin´1 is computed so that X " X 0 ' . . . ' X nin´1 . Therefore, if the value of a variable Z is correlated to a sensitive value X then, as each share Z i separately is independent from Z, they are independent from the sensitive value X. As stated in [BBP `16], the tuple of shares pZ i q 0ďiďnin´1 still depends on X but, because of the noise, the complexity of the extraction of information then becomes exponential in the number of shares n in . Each set of n in sub-variables X i such that X " X 0 ' . . . ' X nin´1 is named a n in -sharing of X.

On a larger scale, masking schemes describe how, for a given function f with n inputs X k and m outputs Y k " f k pX 0 , . . . , X n´1 q, the sharings of the outputs of f are built as functions of the sharings of its inputs. As an example, if each input is split into n in shares and each output is split into n out shares, a masking scheme pF i,j q 0ďiăm,0ďjănout describes the n out ˚m sub-functions F i,0 , . . . , F i,nout´1 with 0 ď i ă m such that Y i,0 " F i,0 pX 0,0 , . . . , X 0,nin´1 , . . . , X n´1,0 , . . . , X n´1,nin´1 q Y i,1 " F i,1 pX 0,0 , . . . , X 0,nin´1 , . . . , X n´1,0 , . . . , X n´1,nin´1 q . . . Y i,nout´2 " F i,nout´2 pX 0,0 , . . . , X 0,nin´1 , . . . , X n´1,0 , . . . , X n´1,nin´1 q Y i,nout´1 " F i,nout´1 pX 0,0 , . . . , X 0,nin´1 , . . . , X n´1,0 , . . . , X n´1,nin´1 q

, with $ ' ' & ' ' % X k " nin´1 ř j"0
X k,j for all k P t0, . . . , n ´1u

Y k " nout´1 ř j"0
Y k,j " f k pX 0 , . . . , X n´1 q for all k P t0, . . . , m ´1u

For the most usual case of a function f admitting n inputs and one output, if each input is split into n in shares and the output is split into n out shares, a masking scheme pF i q 0ďiănout of f describes the n out sub-functions F 0 , . . . , F nout´1 such that Y 0 " F 0 pX 0,0 , . . . , X 0,nin´1 , . . . , X n´1,0 , . . . , X n´1,nin´1 q Y 1 " F 1 pX 0,0 , . . . , X 0,nin´1 , . . . , X n´1,0 , . . . , X n´1,nin´1 q . . .

Y nout´2 " F nout´2 pX 0,0 , . . . , X 0,nin´1 , . . . , X n´1,0 , . . . , X n´1,nin´1 q Y nout´1 " F nout´1 pX 0,0 , . . . , X 0,nin´1 , . . . , X n´1,0 , . . . , X n´1,nin´1 q , with $ ' ' & ' ' % X i " nin´1 À j"0 X i,j @i P t0, . . . , n ´1u Y " nout´1 ř j"0 Y j " f pX 0 , . . . , X n´1 q
Such masking scheme is noted a pn in , n out q-masking scheme of the function f , and precisely a n s -masking scheme if n s " n in " n out .

Research Questions

The primary purpose of this thesis was to develop improvements to the whitebox cryptographic primitives used in the Kudelski Group products, that are mostly symmetric white-box cryptographic primitives. Consequently, I started my PhD researches by constituting a state-of-art of white-box cryptography, and particularly symmetric white-box cryptography. I then chose to focus in the field of bitsliced implementations using masking schemes.

Two of the main threats to cryptographic primitives and notably cryptographic primitives in the white-box attack model are side-channel attacks and fault attacks. Fault attacks consist of disrupting the correct functioning of the cryptographical primitive to observe faulty behaviour of variables depending on sensitive data ([GT04], [START_REF] Otto | Fault attacks and countermeasures[END_REF]). Leaked information can then be processed with statistic or analytic methods, thereby disclosing all or part of sensitive data involved in the computation. The masking schemes designed with fault resistance in mind usually adopt the strategy of detecting faults instead of correcting them. At the detection of a fault, they abort or deteriorate the execution of the implementation. Masking schemes are by design countermeasures against side-channel attacks, therefore I aimed to develop a masking scheme that could combine resistance to side-channel attacks as well as resistance to fault attacks, and that would only be using Boolean operations in order to be applied on Boolean implementations. More precisely, this masking scheme would not only detect faults but correct them, allowing the execution of the implementation to carry on in a correct manner.

With this aim in mind, I introduced error-correcting codes in this new masking scheme, and more precisely BCH error-correcting codes since the corresponding decoding can be performed with only Boolean operations.

On the other hand, one of the main challenges cryptography needs to deal with consists in balancing the security of a cryptographic primitive with its costs and performances. This is notably important when the considered cryptographic primitive is deployed on a device with constrained capacities, like for example the IoT (Internet of Things) products developed by the Kudelski Group. Consequently, performances and costs remain important parameters to take into consideration when designing a white-box secure implementation.

To that end, the company offered an internship to Alex Charlès so we would work in collaboration to evaluate the "white-boxability" of the primitives finalists of the NIST Lightweight Cryptography Standardization Contest. This criterion was not part of the Standardization Contest criteria, therefore the aim of this study was to pick the Lightweight Contest finalist the most suitable to first undergo a primary layer of white-boxing, and then be bitsliced to apply the masking scheme developed during my PhD. We selected GIFT-COFB and more precisely its core cryptographic function GIFT, and developed a tabularized encoding solution to apply to GIFT before bitslicing, based on Chow et al. white-box AES ([CEJvO02]).

Thesis Overview

In the preamble of this dissertation we will first detail the tools used for the thesis, i.e. the notations and theoretical basis to our study. Then, we will present an overview of the state-of-the-art of white-box cryptography contests and bitsliced masking schemes.

This first part of this dissertation will discuss in section 6 the study of the white-boxability of the NIST Lightweight Cryptography Standardization Contest finalists. We selected GIFT-COFB and built a tabularized white-box implementation of GIFT, the main cryptographic block of this finalist, that is described in section 7. This work has been presented at the NIST Lightweight Cryptography Workshop 2022 [START_REF] Charlès | Review of the white-box encodability of NIST lightweight finalists[END_REF]. Finally, a differential attack on this implementation will be introduced, as well as a potential evolution of the GIFT SBox so that our implementation could resist this attack. This work is described in a paper currently being finalized.

The second part of the dissertation presents in section 9 the rationale behind the design of the new fault resistant masking scheme, before describing this design in section 10. Finally, section 11 details the application of the scheme to a global implementation of a cryptographic primitive. This masking scheme is presented in [START_REF] Gravouil | A new generic fault resistant masking scheme using error-correcting codes[END_REF].

Tools for the Thesis

Notations

This dissertation will use the following notations :

• For a random variable X, we note P pXq its probability distribution and H its entropy pHpXq " ´řx P pX " xq log 2 pP pX " xqqq.

• For random variables X and Y , -We note HpX|Y q " ř x ř y P pX " x, Y " yq log P pX"x,Y "yq P pY "yq the conditional entropy of X given Y.

-IpX; Y q " HpXq ´HpX|Y q is the mutual information between X and Y.

• We consider K a field with charpKq " 2.

• For an array a P K n , we note HW paq the Hamming weight of a, i.e. the number of non-zero elements of a.

• For a, b P K n , we note d HW pa, bq " HW pa ´bq the Hamming distance between a and b.

• For an array y " py n´1 , . . . , y 0 q P K n , we note ypXq " y n´1 X n´1 `. . . ỳ1 X `y0 P KrXs its corresponding polynomial.

• For a 128-bit array b " pb 0 , b 1 , ..., b 127 q, we note b " B 0 B 1 ...B 15 its decomposition in 16 bytes.

• We note the parity of a polynomial P P KrXs to be HW pP q mod 2.

• For a set S, we note #S its cardinality.

• For px n´1 , . . . , x 0 q P F n 2 such that n´1 ř i"0

x i 2 i " x P N, we note pxq n " px n´1 , . . . , x 0 q.

-For px n´1 , . . . , x 0 q P F n 2 such that px n´1 , . . . , x 0 q " pxq n and S an SBox with n-bit inputs, we note Srx n´1 . . . x 0 s " Srxs.

• For x P F 2 , we note x " x ' 1.

-For px n´1 , . . . , x 0 q P F n 2 , we note x n´1 . . . x 0 the array x n´1 . . . x 0 P F n 2 . -Particularly, for pa, b, c, dq P F 4 2 , we note abcd the array abcd. • For v P F 2 2 and v 0 P F 2 , we note v " v 0 if the value of the first bit of v is known to be v 0 and the value of the second bit is yet to be determined.

• We note ' the scalar product of F 4 2 . • We note a nibble to be a unit of four bits, corresponding to half a byte.

Probability Property

The following property on sums of products of uniform, independent and identically distributed random variables over F 2 will be used in subsubsection 9.1.5. Property 1. Let n P N ‹ . Let a 0 , . . . , a n´1 , b 0 , . . . , b n´1 be 2n uniform, independent and identically distributed (i.i.d.) random variables over F 2 . Then,

Ppa 0 b 0 ' . . . ' a n´1 b n´1 " 0q " 10 2 n`2 ´1 2 n´1 `1 2 Proof.
We first suppose that n " 1. Then Ppa 0 b 0 " 0q " 1 ´Ppa 0 b 0 " 1q. As a 0 and b 0 are uniform and i.i.d. variables over

F 2 , Ppa 0 b 0 " 1q " Ppa 0 " 1qPpb 0 " 1q " 1 2 ˚1 2 " 1 4 . Thus Ppa 0 b 0 " 0q " 1 ´1 4 " 3 4 . Simultaneously, for n " 1, 10 2 n`2 ´1 2 n´1 `1 2 " 10 2 1`2 ´1 2 1´1 `1 2 " 10 8 ´1 `1 2 " 5 4 ´1 2 " 3 4 .
We now suppose that there exists n P N ‹ such that the property is verified for this value of n, i.e. for any 2n uniform and i.i.d. random variables over F 2 a 0 , . . ., a n´1 , b 0 , . . ., b n´1 , Ppa 0 b 0 ' . . . ' a n´1 b n´1 " 0q " 10 2 n`2 ´1 2 n´1 `1 2 . We then consider a 0 , . . . , a n , b 0 , . . . , b n 2pn `1q uniform and i.i.d. random variables over F 2 . Subsequently,

Ppa 0 b 0 ' ... ' a n´1 b n´1 ' a n b n " 0q " Ppa 0 b 0 ' ... ' a n´1 b n´1 " 0 X a n b n " 0q `Ppa 0 b 0 ' ... ' a n´1 b n´1 " 1 X a n b n " 1q " Ppa 0 b 0 ' ... ' a n´1 b n´1 " 0qPpa n b n " 0q `Ppa 0 b 0 ' ... ' a n´1 b n´1 " 1qPpa n b n " 1q " ˆ10 2 n`2 ´1 2 n´1 `1 2 ˙˚3 4 `ˆ1 ´ˆ10 2 n`2 ´1 2 n´1 `1 2 ˙˙˚1 4 " 30 2 n`4 ´3 2 n`1 `3 8 `1 4 ´10 2 n`4 `1 2 n`1 ´1 8 " 20 2 n`4 ´2 2 n`1 `2 8 `1 4 " 10 2 pn`1q`2 ´1 2 pn`1q´1 `1 2
Therefore, by induction, the property is verified for every n P N ‹ .

Substitution Boxes Properties

In 1949, Shannon suggested to combine two different approaches to mitigate the cryptanalysis of a block cipher, namely diffusion and confusion ([Sha49], [START_REF] Wyseur | White-Box Cryptography[END_REF]).

In a few words, diffusion consists in maximizing the propagation of any plaintext bit or key bit difference to all ciphertext bits. Ideally, flipping one of these plaintext or key bits would lead to a flip of each ciphertext bits with probability 1 2 . Diffusion is usually achieved by bit permutations and/or linear operations in block ciphers.

Confusion consists in complexifying as much as possible the dependence between plaintext, key and ciphertext bits. To that end, block ciphers use nonlinear operations, usually defined as Substitution Boxes (SBoxes) implemented as look-up tables.

Property 2. Let n P N ‹ . There exists 2 n ! n-bit to n-bit SBoxes.

Property 3. Let m, n P N ‹ . An m-bit input to n-bit output SBox weighs 2 m ˚n bits.

To achieve a good confusion, different properties of SBoxes can be considered, as listed in [BPP `17b] : Definition 1 (DDT). Let S be a m-bit to n-bit SBox. The Difference Distribution Table (DDT) of S is the 2 m ˆ2n -table defined such that The differential score of an SBox S is #GI `#GO, observed from 1-1 bit DDT.

DDT pδ i , δ o q " #tx P F m 2 | Srx ' δ i s " Srxs ' δ o u for pδ i , δ o q P F m
• The Good Inputs (GI) observed from the 1-1 DDT are the input differences δ i P F m 2 verifying HW pδ i q " 1 such that there does not exist an input x P F m 2 and an output difference δ o P F n 2 verifying HW pδ o q " 1 such that Srx ' δ i s " Srxs ' δ o .

• The Good Outputs (GO) observed from the 1-1 DDT are the output differences δ o P F n 2 verifying HW pδ o q " 1 such that there does not exist an input x P F m 2 and an input difference δ i P F m 2 verifying HW pδ i q " 1 such that Srx ' δ i s " Srxs ' δ o .

All inputs (resp. outputs) that are not Good Inputs (resp. Good Outputs) are considered Bad Inputs (resp. Bad Outputs). Definition 4 (from [BPP `17b]). The linear score of an SBox S is #GI #GO, observed from 1-1 bit LAT.

• The Good Inputs (GI) observed from the 1-1 LAT are the input operands α P F 4 2 verifying HW pαq " 1 such that for each output operand β P F 4 2 LAT pα, βq " 0, i.e. #tx P F 4 2 | α ' x " β ' Srxsu " 8.

• The Good Outputs (GO) observed from the 1-1 LAT are the output operands β P F 4 2 verifying HW pβq " 1 such that for each input operand α P F 4 2 , LAT pα, βq " 0, i.e. #tx P F 4 2 | α ' x " β ' Srxsu " 8. All inputs (resp. outputs) that are not Good Inputs (resp. Good Outputs) are considered Bad Inputs (resp. Bad Outputs). Furthermore, potential supplementary properties of Substitution Boxes may fragilize the cryptographic primitives they are used in : for example, their linearity.

Property 4 (Cardinality of Linear SBoxes). Let n P N ě2 . The number of linear n-bit Substitution Boxes verify

p2 n ´1q ˚p2 n ´2q ˚. . . ˚p2 n ´2n´1 q " n´1 ź i"0 p2 n ´2i q
Proof. Let S be a n-bit linear SBox. For every x such that 0 ď x ă 2 n , Srpxq n s " Srpxq n ' p0q n s " Srpxq n s ' Srp0q n s, thus Srp0q n s " p0q n .

By linearity, all values of the SBox only depend on the values of Srp1q n s, Srp2q n s, Srp2 2 q n s, . . . , Srp2 n´1 q n s. Indeed, for every x P N such that 0 ď x ă 2 n , there exists px n´1 , . . . , x 0 q P F n 2 such that x " ř n´1 i"0 x i 2 i´1 . Subsequently, Srpxq n s " À n´1 i"0 x i Srp2 i q n s.

• As mentioned above, the value of Srp0q n s is fixed to be p0q n . Therefore, there exists 2 n ´1 potential values for Srp1q n s, that are the nonzero values of F n 2 . In the same manner, it implies that, given the value of Srp1q n s there exists 2 n ´2 possible values of Srp2q n s : the values of F n 2 z tSrp0q n s, Srp1q n su. Thus, at this point, the values of Srp0q n s, Srp1q n s, Srp2q n s and Srp3q n s " Srp1q n s ' Srp2q n s are fixed.

• It remains 2 n ´22 possible values for Srp2 2 q n s : the elements of F n 2 z tSrpiq n s for 0 ď i ď 3u. Then, once this value chosen, the 2 3 values tSr ř 2 i"0 x i p2 i q n s for px 2 , x 1 , x 0 q P F 3 2 u are fixed.

• In the same way, it remains 2 n ´23 different values for Srp2 3 q n s : the elements of F n 2 z tSr ř 2 i"0 x i p2 i q n s for px 2 , x 1 , x 0 q P F 3 2 u. Once this value has been chosen, the 2 4 first values of S (tSr ř 3 i"0 x i p2 i q n s for px 3 , x 2 , x 1 , x 0 q P F 4 2 u) are fixed.

This process can be repeated : for the choice of the value of Srp2 k q n s there exists 2 n ´2k possibilities : the elements of F n 2 z tSr ř k´1 i"0 x i 2 i s for px k´1 , . . . , x 0 q P F k 2 u. The last value to be chosen will be Srp2 n´1 q n s, with 2 n ´2n´1 possibilities.

As a conclusion, as detailed above all values of the linear SBox S can be deduced from Srp2 0 q n s, Srp2 1 q n s, . . . , Srp2 n´1 q n s, and there exists respectively 2 n ´20 , 2 n ´21 , . . . , 2 n ´2n´1 possibilities for each. Hence, the number of linear n-bit SBoxes verify p2 n ´1q ˚p2 n ´2q ˚. . . ˚p2 n ´2n´1 q " n´1 ź i"0 p2 n ´2i q

Bitslicing

Firstly introduced and applied on DES in [START_REF] Biham | A fast new DES implementation in software[END_REF], bitslicing consists in implementing an operation as a combinatorial circuit in software ( [START_REF] Mercadier | Usuba: Optimizing & trustworthy bitslicing compiler[END_REF]). In other words, the basic idea of bitslicing is to implement an operation using only Boolean operators XOR, AND, OR and NOT on bits. To that end, n-bit variables of this operation are implemented as n variables of one bit. Bitslicing look-up tables avoids cache-timing attacks, as the result value of the circuit is computed at each instance and cannot be stored into the cache. For example, [START_REF] Kwan | Reducing the gate count of bitslice DES[END_REF] describes how to implement the 4-bit SBox of DES using 56 gates XOR, AND, OR or NOT, and the 3-bit SBox S " r2, 0, 1, 6, 3, 5, 4, 7s can be written as b 2 b 1 b 0 " Sra 2 a 1 a 0 s with

x 0 " a 0 AND a 1 x 1 " a 0 XOR a 1 x 2 " NOT a 0 x 3 " x 1 AND a 2 x 4 " x 2 AND a 1 b 0 " x 4 XOR a 2 b 1 " x 2 XOR a 1 b 2 " x 0 XOR x 3
Bitslicing is notably useful when performing several instances of the implementation in a parallel manner is needed. Indeed, a m-bit register can be filled with m one-bit variables arised from m different instances of the implementation.

Bitsliced implementations are by nature resistant to timing attacks. Timing attacks aim to extract the key (or a secret variable) from a cryptographic primitive by exploiting the variations of the execution time depending on this primitive inputs [START_REF] Brumley | Remote timing attacks are practical[END_REF]. Bitsliced implementations are composed of the bitwise operations mentioned hereinabove, and those operations are by design constanttime, hence the timing attack resistance.

There exists different ways to bitslice an implementation. Some papers like [START_REF] May | An implementation of bitsliced DES on the Pentium MMX TM processor[END_REF] or [START_REF] Bao | Bitsliced implementations of the PRINCE, LED and RECTANGLE block ciphers on AVR 8-bit microcontrollers[END_REF] describe bitsliced implementations specifically designed for certain cryptographic primitives. Many methods destined to bitslice any cryptographic primitive focus on the bitslicing of SBoxes, that are the usual non-linear operations of those primitives ([GR16], [START_REF] Sovyn | Bitsliced implementation of non-algebraic 8×8 cryptographic s-boxes using ×86-64 processor SIMD instructions[END_REF]). To be able to fully bitslice any primitive, [START_REF] Mercadier | Usuba, Compilateur Bitslicing Optimisant)[END_REF] introduces the Usuba language and its corresponding compiler Usubac. Usubac takes the description of a symmetric cryptographic primitive in this language and produces a bitsliced implementation of the primitive in C.

Error-Correcting Codes

For the new masking scheme described in section 10, we firstly aim to use an error-correcting code with an easy management of codewords parities, hence the choice of cyclic codes. Furthermore, since the masking scheme is designed to only be constituted of Boolean operations, we choose BCH codes as they can be decoded in constant time via the Peterson-Gorenstein-Zierler algorithm ( [START_REF] Peterson | Encoding and error-correction procedures for the bose-chaudhuri codes[END_REF]).

To that end, we first remind basic properties of error-correcting codes and subsequently BCH error-correcting codes.

Basic Properties

We first remind basic properties of error-correcting codes needed for the remainder of the dissertation. Definition 8 (Cyclic codes [START_REF] Augot | An introduction to linear and cyclic codes[END_REF]). Let n P N ‹ . A linear code C of length n is said to be a cyclic code if all cyclic permutations of codewords belong to the code as well, i.e. pc 0 , c 1 , . . . , c n´1 q P C ùñ pc n´1 , c 0 , c 1 , . . . , c n´2 q P C Property 5 (Polynomial Representation of Codewords). For a cyclic code C of length n over a finite field F q ,

• we can identify each codeword pc 0 , c 1 , . . . , c n´1 q P F n q to its polynomial representation c 0 `c1 X `c2 X 2 `. . . `cn´1 X n´1 P F q rXs{pX n ´1q and reciprocally.

• there exists a polynomial gpXq P F q rXs such that, for each codeword pc 0 , c 1 , . . . , c n´1 q, gpXq|c 0 `c1 X `c2 X 2 `. . . `cn´1 X n´1 . This polynomial gpXq is noted generator polynomial of the cyclic code C.

BCH Error-Correcting Codes

BCH error-correcting codes are based on the following mathematical notions and properties. Thereafter, we will assume q to be a prime power.

Definition 9. Let n P N ‹ such that n ^q " 1, m the multiplicative order of q modulo n. Let s P t0, . . . , n ´1u. We note Cpsq the q-cyclotomic class of s modulo n :

Cpsq " ts, s ˚q, . . . , s ˚qms´1 u, with m s being the smallest non-zero integer verifying s " s ˚qms pmod nq.

Definition 10. Let n P N ‹ such that n ^q " 1, m the multiplicative order of q modulo n and α an element of F q m of multiplicative order n. Let s P t0, . . . , n ´1u. We note the polynomial M α s pXq to be

M α s pXq " ś iPCpsq pX ´αi q " ms´1 ś i"0 pX ´αsq i q.
Subsequently, the BCH (Bose Chaudhuri Hocquenghem) error-correcting codes can be defined as follows :

Definition 11 (BCH Code, [START_REF] Bose | Further results on error correcting binary group codes[END_REF], [START_REF] Bose | On a class of error correcting binary group codes[END_REF]). Let n P N ‹ , m the multiplicative order of q modulo n, α an element of F q m of multiplicative order n and b, δ P N such that δ ě 3. A cyclic code of length n over F q is said to be a BCH code of minimum Hamming distance at least δ if its generator polynomial gpXq verifies

gpXq " lcmpM α b pXq, M α b`1 pXq, . . . , M α b`δ´2 pXqq
Property 6 (Correction Capacity of a BCH Code). The correction capacity t of a BCH code of minimum Hamming distance at least δ verifies

t ě t δ ´1 2 u.

Additional Properties

For the selection of the parameters of the BCH code we use in the scheme that is detailed in subsection 9.1, we consider the following additional properties about the 2-cyclotomic classes and M α i polynomials.

Property 7. Let odd n P N ‹ such that n ě 3 and s P t0, . . . , n ´1u. The 2-cyclotomic class of s modulo n is a singleton if and only if s " 0.

Proof. On the one hand, by definition, Cp0q " t0u. On the other hand, suppose that there exists s P t0, . . . , n ´1u such that Cpsq " tsu. This implies that m s , defined as the smallest non-zero integer such that s " s ˚2ms pmod nq, also verifies that s ˚2ms´1 " s. Therefore, as naturally m s ´1 ă m s , the hypothesis on m s implies that m s ´1 " 0, and thus m s " 1. Therefore, s verifies 2 ˚s " s pmod nq, i.e. s " 0 pmod nq. Since s P t0, . . . , n ´1u, this implies that s " 0. As a conclusion, if the 2-cyclotomic class of s modulo n is a singleton, then s " 0.

Property 8. M α s P F q rXs. Proof. First of all, pM α s pXqq q " p ms´1 ś i"0

pX ´αsq i qq q " ms´1 ś i"0 pX ´αsq i q q " ms´1 ś i"0 X q ´αsq i`1 , therefore pM α s pXqq q " ms´1 ś i"0 X q ´αsq i`1 " ms´1 ś i"0
X q ´αsq i " M α s pX q q. Subsequently, we note M α s pXq " ř ms´1 j"0 a j X j , with a j P F q m for 0 ď j ď m s ´1. Then,

• pM α s pXqq q " p ms´1 ř j"0 a j X j q q " ms´1 ř j"0 a q j X qj • M α s pX q q " ms´1 ř j"0 a j pX q q j " ms´1 ř j"0 a j X qj Thus, M α s pXq q " M α s pX q q ùñ ms´1 ř j"0

a q j X qj " ms´1 ř j"0 a j X qj .
Consequently, since these polynomials are equal, it implies that for all 0 ď j ď m s ´1, a j " a q j , hence a j P F q . In conclusion, M α s pXq "

ms´1 ř j"0 a j X j P F q rXs.
Property 9. M α s is irreducible over F q .

Proof. By definition, α s P F q m is a root of M α s . If we suppose that M α s is not irreducible over F q rXs, then there exists a factor P P F q rXs admitting α s as a root, i.e. P pα s q " 0. As P P F q rXs, P pα sq q " P pα s q q " 0 and by extension P pα sq i q " 0 for all 0 ď i ď m s ´1. Consequently, M α s pXq " ms´1 ś i"0 pX ´αsq i q divides P . Moreover, P |M α s by hypothesis, therefore P " M α s . In conclusion, M α s is irreducible over F q rXs (and is the minimal polynomial of α s over F q rXs).

Property 10. Let ti 0 , i 1 , . . . , i r´1 u Ă t0, . . . , n´1u. The least common multiple of M α i 0 , M α i 1 , . . . , M α i r´1 is a product of some of these M α j polynomials.

Proof. First of all, we note tj 0 , . . . , j t´1 u the representatives of the different cyclotomic classes of i 0 , i 1 , . . . , i r´1 , in such a way that each different polynomial M α iv only appears once in the set tM α j 0 , . . . , M α j t´1 u. Therefore,

lcmpM α i 0 , M α i 1 , . . . , M α i r´1 q " lcmpM α j 0 , . . . , M α j t´1 q,
with the polynomials M α j 0 , . . . , M α j t´1 being two by two distincts. As these polynomials are irreducible (see Property 9) and two by two distincts, they are coprime. Therefore,

lcmpM α i 0 , M α i 1 , . . . , M α i r´1 q " lcmpM α j 0 , . . . , M α j t´1 q " M α j 0 ˚Mα j 1 ˚. . . ˚Mα j t´1 gcdpM α j 0 , M α j 1 , . . . , M α j t´1 q " M α j 0 ˚Mα j 1 ˚. . . ˚Mα j t´1
Thus, the least common multiple of M α i 0 , M α i 1 , . . . , M α i r´1 is a product of some of these polynomials.

State of the Art

State of the Art of White-Boxing Contests

Since the development of the white-box cryptography, a cat-and-mouse challenge has been running between designers and attackers. For a long time, the security of most solutions deployed in the industry relied on secrecy rather than on academic-proved designs. To that end, the ECRYPT-CSA consortium organized for the first time WhibOx, a white-box cryptography competition during the 2017 edition of CHES [Whia]. The purpose of this Catch The Flag challenge was to allow white-box design researchers to confront their implementations to all attackers of the white-box cryptography community.

Participant designers were invited to submit their implementations of AES-128 with freely-chosen fixed keys, written with only generic C instructions. Each submission needed to comply with different requirements, for example a source code of at most 50 MB, a compilation time of less than 100 seconds, an executable being 20 MB in size or less and using 20 MB of RAM or less, and a function call time of less than one second on average. The results of this contest illustrated the difficulty of white-box secure cryptography designing, as none of the 94 submitted challenges had remained unbroken at the end. Precisely, among those 94 submissions :

• 88 were broken in less than one week p94%q, including

• 81 that were broken in less than a day p86%q, including

• 55 that were broken in less than an hour p59%q, including

• 38 that were broken in less than 30 minutes p40%q, including • 20 that were broken in less than 10 minutes p21%q.

More precisely, the three most successful challenges resisted for respectively 11, 12 and 27 days ([GPRW20]).

Subsequently, a second edition of WhibOx was organized in 2019 by Crypto-Experts and CyberCrypt, that was still concerning AES-128 implementations in C [Whib]. Most of the requirements imposed during the first edition of WhibOx (including the ones mentioned above) were renewed. Among the 27 submissions of this edition :

• the 24 submissions that were broken p89%q were broken in less than a month, including

• 23 that were broken in less than two weeks p85%q, including

• 18 that were broken in less than a week p67%q, including

• 6 that were broken in less than a day p22%q, including

• none that were broken in less than an hour.

Three challenges had remained unbroken by the end of the contest (respectively 21 and 24 days after their submissions), but were later broken with greybox attacks in [START_REF] Goubin | Defeating stateof-the-art white-box countermeasures with advanced gray-box attacks[END_REF].

Finally, a third edition of the WhibOx contest was organized as the CHES 2021 Catch the Flag Challenge [Whic]. Nevertheless, the focus of this edition was public-key white-box cryptography, and more specifically the ECDSA signature (on NIST P256 curve) under a freely chosen secret key. Therefore the submissions were not in the symmetric white-box cryptography scope of this thesis.

Masking Offers Resistance to Side-Channel Attacks

The analysis of the security of the candidates of the WhibOx 2017 contest detailed in [START_REF] Estuardo | Security assessment of white-box design submissions of the CHES 2017 CTF challenge[END_REF] illustrates that side-channel attacks are a major threat to white-box implementations.

Masking constitutes a countermeasure to side-channel attacks. Indeed, as detailed in subsection 3.2, masking a variable x P K with n in shares x 0 , . . . , x nin´1 in K consists in replacing in an implementation the variable x by its shares px i q 0ďiănin . By definition of sharings, each tuple of n in ´1 shares x i is independent from x. Therefore, as the side-channel leakage of each share is independent from the side-channel leakage of other shares, recovering the variable x requires the retrieval of all n in shares.

Consequently, as detailed notably in [START_REF] Cassiers | Composable and efficient masking schemes for side-channel secure implementations[END_REF], if each share x i can be recovered with a probability p w then, since an attacker will be able to recover the original variable x only by retrieving all n in shares x i , he will be able to retrieve the value of x with a probability being Opp nin w q, hence the security enhancement.

Different Strategies to Mask an Implementation

Different types of masking have been developed in the literature. A branch has been notably devoted to the design of masking dedicated to specific cryptographic primitives. In these cases, a different masking scheme pF i q 0ďiănout is designed for each component function f of the considered primitive. The most studied primitive to be masked is AES. For example, in 2012, [START_REF] Nassar | RSM: A small and fast countermeasure for aes, secure against 1st and 2nd-order zero-offset scas[END_REF] expounded RSM, a countermeasure masking each component function of AES-256, that was later improved in [BBD `14]. Many papers including [ZSM `08], [START_REF] Fabrizio De Santis | Squeezing polynomial masking in tower fields -A higher-order masked AES s-box[END_REF] and [START_REF] Ghoshal | Several masked implementations of the Boyar-Peralta AES S-box[END_REF] focus on the masking of the SBox in AES, since it is its only non-linear operation, with high complexity. On the other hand, in 2021, [START_REF] Ming | A secure and highly efficient first-order masking scheme for AES linear operations[END_REF] aimed to improve the masking of the non-linear operations of AES, weaknesses of the then-existing constructions. Finally, in 2022, [ADN `22] focused on designing three different AES maskings that do not require fresh randomness.

The other major strategy consists in designing masking schemes operating on a lower level of the implementations of primitives, therefore allowing those schemes to not be specific to a cryptographic primitive. To that end, the implementations on which those masking schemes are applied are usually bitsliced implementations of any cryptographic primitive. Most masking schemes with this aim in mind are designed in finite fields of characteristic two (i.e. of the form F 2 k ), in particular F 2 . In this instance, the operations are mainly bitwise operations, namely XOR, AND, OR and NOT.

The bitwise operation f of a bitsliced implementation mostly targeted to be masked when following the second strategy is the AND operation. Indeed, among the four Boolean operations XOR, AND, NOT and OR,

• The XOR operation is associative with regards to input sharings. Therefore, performing a XOR between two variables using their sharings can be performed simply by XORing shares.

• The NOT operation can be performed on a sharing of a variable by flipping the value of one of its shares.

• The OR operation can be rewritten with three instances of the NOT operation and one instance of the AND operation, since a _ b " p a ^ bq.

State of the Art of Masking Schemes Security Properties

Different models have been introduced in the literature to assess the security of masking schemes, and different properties of these masking schemes can be sufficient conditions to ensure their security in those models.

Noisy Leakage Model Implies d-Probing Security

In 1999, Chari et For every set of d probes pp 0 , . . . , p d´1 q, this amounts to

Ipp 0 Y . . . Y p d´1 ; xq " 0
This property is much easier to prove than security in the noisy leakage model, but was thought to be not sufficiently accurate to describe the leakage. However, in 2014, Duc et al. proved in [START_REF] Duc | Unifying leakage models: From probing attacks to noisy leakage[END_REF] that security in the d-probing model implies security in the noisy leakage model.

Correctness

The first property that all masking schemes must comply with is correctness ( [START_REF] Bilgin | Threshold implementations : as countermeasure against higher-order differential power analysis[END_REF]). This property does not participate in the security of the scheme by itself, but is essential for the natural purpose of maintaining the functionality of the function to be masked f . Indeed, for a masking pF i q 0ďiďnout´1 of a function f such that Y " f pX 1 , . . . , X n q, the output shares functions pF i q 0ďiďnout´1 must verify that

nout´1 À i"0 F i ´pX 0,j q 0ďjănin , . . . , pX n´1,j q 0ďjănin ¯" f ˜nin´1 À j"0 X 0,j , . . . , nin´1 À j"0 X n´1,j

5.4.3

Non-Completeness

Property 12 (Non-Completeness, [START_REF] Nikova | Threshold implementations against side-channel attacks and glitches[END_REF], [START_REF] Bilgin | Threshold implementations : as countermeasure against higher-order differential power analysis[END_REF]). A masking scheme F verifies non-completeness if each of its component functions F i is independent of at least one share of each of the input variables of the scheme.

In other words, non-completeness is necessary when supposing that a probe on a combinational block (i.e. an operation) implies the leakage of all inputs of this combinational block ([RBN `15]). Consequently, for a masking scheme that does not satisfy non-completeness, a probe would imply the leakage of all shares of at least one input variable, and therefore the recovery of the value of this input.

Uniformity

Property 13 (Uniform Masking, [START_REF] Bilgin | Threshold implementations : as countermeasure against higher-order differential power analysis[END_REF]). A pn in , n out q-masking scheme F of a function f : K n Ñ K with n inputs X i and one output Y is said to be uniform if and only if @ px 0 , . . . , x n´1 q P K n , @ py 0 , . . . , y nout´1 q P K nout , P ´pY j q 0ďjďnout´1 " py j q 0ďjďnout´1 ˇˇpXiq 0ďiďn´1 " px i q 0ďiďn´1 ¯"

$ ' & ' % 1 |K| n out ´1 if f px 0 , . . . , x n´1 q " nout´1 À j"0 y j 0 otherwise
In other words, uniformity implies that, for each n-tuple of input values of f noted px 0 , . . . , x n´1 q, all n out -sharings py 0 , . . . , y nout´1 q that are computed by F with a n in -sharing of px 0 , . . . , x n´1 q as input are equiprobable.

Non-Completeness and Uniformity Imply 1-Probing Security

In [START_REF] Nikova | Threshold implementations against side-channel attacks and glitches[END_REF], Nikova et al. demonstrate that the three properties of correctness, uniformity and non-completeness constitute, when combined, sufficient conditions for the security of implementations against first-order probing attacks.

Lemma 1 ([NRR06]

). Non-completeness and uniformity implies 1-glitch probing extended security.

State of the Art of Boolean AND Masking Schemes

Our purpose is to design a masking scheme implementing the AND operation between two bits with only Boolean operations. Among Boolean operations, the masking of AND is by far the most developed since XOR and NOT are linear with regards to their input shares. Therefore, they can be performed on input sharings by respectively XORing shares or performing NOT on only one input share. Finally, the OR operation can be written as a combination of instances of AND and NOT.

We The implementations results, taken from [START_REF] Goudarzi | Secure multiplication for bitslice higherorder masking: Optimisation and comparison[END_REF], consider the straight implementations of ISW, BDF+ and BBP+ with loops, and BCPZ with macros.

✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ 1 st -Order Non-Completeness ✗ ✗ ✗ ✗ ✓ ✓ ✗ ✗ ✗ ✗ ✗ ✗ 2 nd -Order Non-Completeness ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗ ✗

Fault-Resistant Masking Schemes

The study of the WhibOx 2017 candidates in [AT20] also illustrates that fault attacks constitute the other major threat to white-box implementations. Therefore, fault-resistant masking schemes have been developed in order to combine resistance against the listed two major threats to white-box implementations, namely side-channel attacks and fault attacks. One of the solutions frequently used to do so consists in introducing error-correcting codes in the design of masking schemes.

The strategy most fault-resistant masking schemes use is detecting potential faults rather than correcting them. In the case of masking schemes based on error-correcting codes, it uses the fault detection property of the code to deteriorate the computation in the presence of a fault : this avoids the costly procedure of correction. For example, authors of [MAN `19] detail a countermeasure to combined side-channel and fault attacks, that associates masking with infective computation at the detection of a fault. Likewise, [RDB `18] describes CAPA (combined Countermeasure Against Physical Attacks) that is a side-channel countermeasure inherited from Multi-Party Computation. This methodology aborts the computation when detecting faults. Furthermore, [CCG `19] describes IPM-FD, a masking scheme derived from IPM (Inner Product Masking, [START_REF] Balasch | Theory and practice of a leakage resilient masking scheme[END_REF]) and DSM (Direct Sum Masking, [START_REF] Carlet | Direct sum masking as a countermeasure to side-channel and fault injection attacks[END_REF]) that performs error detection as well.

Most of the masking schemes using error-correcting codes necessitate the construction of suitable new error-correcting codes, as for example [START_REF] Carlet | Complementary dual codes for counter-measures to side-channel attacks[END_REF], and operate with words of these codes. Particularly, [BCC `14] introduces Orthogonal Direct Sum Masking (ODSM). This masking uses a code C and its dual D, then each element c P C is masked by XORing an element d P D. Subsequently, a method is provided to adapt the computation of the different steps of a block cipher, using ODSM. Additionally, most masking schemes using errorcorrecting codes use Maximum Distance Separable Codes specially designed for the masking scheme, as they can be considered optimal. Nevertheless, [START_REF] Castagnos | High-order masking by using coding theory and its application to AES[END_REF] describe a masking scheme using different non-MDS codes, depending on the scheme order.

In conclusion, the reasoning between our approach is to build a masking scheme that not only detects faults but corrects them. The overall computation is thus not distorted or aborted in the presence of a fault, but always return results, results that are correct. To do so, we aim to use an error-correcting code well studied in the literature, since it allows to select a code with an optimized correction process being compatible with bitslicing.

Part I

White-Boxing and NIST Lightweight Standardization Finalists 6 Study of the White-Boxability of NIST Lightweight Finalists

Lightweight cryptography is the cryptography field that aims to develop cryptographic primitives suitable to devices with constrained capacities. To fulfill the increasing need of cryptography in this type of devices, the NIST launched in 2015 the NIST Lightweight Cryptography Standardization Contest, a process to "solicit, evaluate, and standardize" cryptographic algorithms fulfilling these requirements.

Many of those devices with constrained capacities, as for example IoT ones, can be used in a context where they will be vulnerable to white-box attackers. Hence, we study the white-boxability of lightweight cryptographic primitives, and focus on the finalists of the NIST Lightweight Cryptography Standardization Contest.

Overview of NIST Lightweight Cryptography Standardization Contest

The NIST Lightweight Cryptography Standardization Contest was launched in August 2018 when the NIST published a call for algorithms to be standardized as "lightweight cryptographic standards with authenticated encryption with associated data (AEAD) and optional hashing functionalities" ([SMC `21]). Among the 57 submissions, 56 were confirmed as Round 1 candidates and announced in April 2019. After a first selection process, the 32 Round 2 candidates were revealed in August 2019. Finally, the 10 finalists were announced in March 2021 :

• ASCON [DEMS21] • Elephant [KCM20] • GIFT-COFB [BPP `17b],[BCI `20] • Grain-128AED [HJM `20] • ISAP [DEM `20] • PHOTON-Beetle [BCD `20]
• Romulus [GIK `20]

• SPARKLE [BBdS `20]

• TinyJambu [SSS `20]

• Xoodyak [DHP `20] In February 2023, NIST announced ASCON to be the standardized lightweight cryptography primitive, as it "meets the needs of most use cases where lightweight cryptography is required".

The different criteria used to decide between candidates were side-channel and fault attacks resistances, costs and performances, third-party analyses and suitability for hardware and software implementations [NIS]. As white-boxability was not part of those criteria, we proceed to review the white-boxability of the 10 finalists of the contest.

A First Selection on the Ten NIST Lightweight Candidates

To select one of the ten NIST lightweight cryptography finalist candidates, Alex Charlès and I made a first sorting following the arguments described below.

Firstly, an algorithm must not be broken with the disclosure of a state. Indeed, in this case, retrieving the key would require to break only the encoding of a state rather than the encoding scheme of the whole algorithm, thus weakening the security of the said encoding scheme. In the NIST status report of the second round candidates ([SMC `21], §3.3.4), PHOTON-Beetle [BCD `20], Sparkle [BBdS `20] and Xoodyak [DHP `20] are not in accordance with this argument.

Secondly, key information should be spread throughout an algorithm, as it will oblige a white-box attacker to attack more parts of this algorithm ([Wys09],

§3.2).

Finally, the Kerckhoffs's axiom imposes that it is supposed that the attacker knows the algorithm and its design except for the key. Therefore, retrieving a state of an algorithm allows an attacker to compute all operations that are not key-dependent. Thus, Isap [DEM `20], Ascon [DEMS21] and Grain128-AEAD [HJM `20] were eliminated.

The Choice of GIFT-COFB

Ruling Out TinyJAMBU and Romulus

TinyJAMBU [SSS `20] has an LFSR-based permutation that fills a 128-bit LFSR with its current state to clock it. As the feedback is computed using 5 bits of the LFSR content and one bit of the key, and recovering the bits used for the computation and the resulting feedback implies retrieving the key bits involved, the LFSR and feedback bits need to be encoded. However, each of the LFSR bits used in this computation can be reused up to 5 times during the following clocks, and will need to be decoded at each usage. That constitutes a drawback from the perspective of designing a white-box implementation of this algorithm, as decoding repetitively the same pieces of information could facilitate the attacker's access to them, and potentially lead to the break of the applied encoding scheme.

The 128-bit Romulus [GIK `20] state can be regarded as a matrix of 4x4 bytes. The MixColumns step of Romulus consists in XORing some state bytes with each other, as for TinyJAMBU. Thus, similarly as in TinyJAMBU, it will be necessary to decode some elements multiple times to achieve this MixColumns step, leading to the same potential weakness as the TinyJAMBU one.

The Elephant Case

Elephant [KCM20] uses a function maskpK, a, bq " mask a,b K that extends a key K depending on a, b P N. Those parameters a and b depend on the block indexes of the message and associated data. Thus mask a,b K depends only on constant inputs, so we would want to precompute it in a white-box implementation to reduce the manipulation of the key. However, the message length and the nonce length are potentially infinite, forcing to restrict their lengths. Though, if Elephant is using the Spongent-π permutation (Dumbo and Jumbo instances), a similar solution to the one we are proposing might be able to encode it, after spreading the XOR of mask a,b K through the permutation.

Choosing GIFT-COFB

Even though algorithmic white-box implementations may exist for the last three algorithms (TinyJAMBU, Romulus and Elephant), we finally choose GIFT-COFB [BCI `20] for a white-box implementation. GIFT-COFB uses GIFT [BPP `17b] to perform its cipher. There exists two versions of GIFT : GIFT-64 and GIFT-128. For the rest of our study, we considered GIFT to be GIFT-128. This block cipher GIFT-128 performs a 128-bit keyed encryption of a 128-bit plaintext, whereas COFB allows to cipher arbitrary-long inputs for an Associated Encryption with Associated Data, using GIFT.

We assume that a white-box implementation of GIFT-COFB would be the easier to realise amongst the other algorithms, as the key is only used in GIFT calls. Furthermore, GIFT XORs some key bits near the SubCells step, which allows us to develop an implementation similar to the one proposed in Chow et al. AES [START_REF] Chow | White-box cryptography and an AES implementation[END_REF].

Finally, we focus on realising a white-box implementation of simply GIFT rather than the whole GIFT-COFB primitive, as the key is not used in GIFT-COFB outside of GIFT occurences. Indeed, GIFT being white-box secure would theorically imply GIFT-COFB being also secure to a white-box attacker.

7 Our White-Box Implementation of GIFT

Overview of GIFT

As explained previously, we choose to concentrate our efforts into designing a white-box implementation of GIFT. The GIFT primitive consists in forty rounds, and uses three different operations in each of its forty rounds : SubCells, PermBits and AddRoundKey ([BPP `17b]).

Algorithm 1: GIFT(S,RK)

Input : S, the 128-bit state and RK the round keys Output: S 1 for i " 0 to 39 do GS " r1, 10, 4, 12, 6, 15, 3, 9, 2, 13, 11, 7, 5, 0, 8, 14s

• PermBits applies a bitwise permutation P B to the state.

• AddRoundKey XORs two bits of the current round key and one bit of a round constant to each 4-bit nibble of the state. To simplify the notations, we consider the round keys RK to include those round constants.

Presentation of Our Solution

We aim to build a white-box table-based implementation of GIFT. To that end, we first need to make a modification in the layout of GIFT, while retaining its correctness. Indeed, our solution first requires to merge AddRoundKey with SubCells. To do so, as AddRoundKey and SubCells are not consecutive in a same round, PermBits and AddRoundKey will be swapped. We use that, for S the state and E the key and round constants array, P BpSq ' E " P BpS ' P B ´1pEqq

Therefore, GIFT can be rewritten as described in Algorithm 2, in a way that facilitates the design of a table-based implementation of this primitive.

The SubCells and AddRoundKey operations can then be merged together in a single lookup table whose outputs will be encoded. Subsequently, to keep Algorithm 2: Č GIF T pS, Ą RK)

Input : S, the 128-bit state and Ą RK " P B ´1pRK q Output: S 1 for i " 0 to 39 do the correctness of GIFT, the inverses of the output encodings of the previous round will be applied to the table input. We name the resulting look-up table a TBox : Figure 1 represents T 0 , the right-most TBox of a round r. The eight output bits of each TBox are split into four 2-bit blocks, each one of them being encoded by a randomly-chosen 2-bit permutation G r,i . As a result, each 2-bit input block is decoded by the inverse G ´1 r´1,j of the corresponding output encoding of the previous round.

G ´1 r´1,15 G ´1 r´1,10 G ´1 r´1,5 G ´1 r´1,0 GIF T SBox c k 1 k 0 Intern LU T r,0 G r,3 G r,2 G r,1 G r,0
In each 2-bit block of the input, once decoded, the left bit corresponds to a bit of the GIFT state, while the right one goes as one of the four input bits of a randomly-chosen 4-bit bijective SBox ILU T .

Thus, on the one hand, the four decoded input blocks left bits go through the GIFT SBox GS (SubCells stage) and are then XORed to the key bits pk 1 , k 0 q and round constant bit c (AddRoundKey stage). On the other hand, the four decoded input blocks right bits go through the intern SBox ILU T . Then, similarly as for the input blocks, the left bit of each 2-bit output block is an output bit of GS and corresponds to a state bit of the actual GIFT computation, while the right bit is an output bit of ILU T and can be considered as a pseudo-random bit. As a conclusion, each of these 2-bit output blocks can be considered as pseudo-random as it corresponds to the output of a pseudo-random encoding computation, with half of its input being pseudo-random as well.

Finally, the PermBits step remains the same as in the original implementation of GIFT, except for the fact that the permutation is now applied to the two-bit output blocks instead of single bits.

Design Rationale

The Output Bits of the GIFT SBox Cannot Be Encoded Altogether

During an execution of GIFT, we cannot encode if only two out of the four output bits of an instance of the GIFT SBox GS within the same function, as they will map to different instances of GS in the following round due to the GIFT permutation. Furthermore, if we apply a 4-bit encoding to the 4-bit output of the GIFT SBox GS in a round r, it would force to decode those whole four bits before each GS instance of the next round r `1 that take as input a bit out of these four. Indeed, the GIFT permutation P B was designed to ensure that the four output bits of the SBox are linked to four different instances of the SBox in the following round, and the 4-bit encoding applied implies that to recover one of these bits it is mandatory to recover the whole four. Therefore, decoding and recovering the four needed input bits of an instance of GS implies to decode four blocks of four bits independently. Moreover, each 4-bit encoded output of an instance of GS would need to be transmitted to each of the four next round instances of GS taking one of its bits as input. Consequently, the resulting TBoxes would have 16 input bits. The weight of a n-bit to m-bit look-up table being 2 n ˚m bits, it would imply a TBox weight of (at very least) 2 16 bits, which is already too heavy regardless of the output size of the TBox.

In the case where we would split the 4 output bits of the SBox GS into two blocks of two bits and apply 2-bit encodings to each of these blocks, this encoding repartition would provide a differential attacker with information on the SBox GS inputs. Indeed, in this case, the attacker will be able to observe if modifying an input block to the SBox GS will impact the left half, the right half or the whole encoded output. As the value of GS is known to the attacker, he will easily be able to break the encodings.

Each Output Bit of the GIFT SBox Is 2-Bit Encoded

As stated above (subsubsection 7.3.1), it is not feasible to encode the output bits of an instance of the GIFT SBox altogether. For this reason, we decide to encode each of these four output bits separately, firstly by 2-bit encodings.

To ensure correctness throughout the different rounds, these 2-bit output encodings need to be inversed at the beginning of corresponding TBoxes of the following round. To that end, we use 2-bit input to 2-bit output encodings, and to obtain the extra pseudo-random input bit of each of those 2-bit encodings, we introduce the 4-bit pseudo-random SBox ILU T , that is bijective and non-linear. Thus, each TBox consists of 8 input bits and 8 output bits.

Once the 8-bit TBox input is decoded, each left bit of the four 2-bit blocks represents the state of GIFT, while the four remaining bits (the right bits of the 2-bit blocks) are pseudo-random bits. These four pseudo-random bits are mixed together thanks to the randomly-chosen bijective SBox ILU T to complexify differential attacks. Indeed, a single bit modification of the 8-bit input of a TBox will have an impact on the 2-bit output of the decoding of the corresponding 2-bit input block. Thus, at least one bit of the state or one pseudo-random bit will be modified. If a state bit is modified, then the 4-bit output of the GIFT SBox GS will be modified and if a pseudo-random bit is modified then the 4-bit output of ILU T will be modified. Hence, the overall 8-bit output of the TBox will be modified, and not only the 2-bit output block with the same index as the modified 2-bit input block. However, we will demonstrate in subsection 8.2 that the knowledge of the GIFT SBox GS leads to an differential 2-round attack.

Moreover, the randomly-chosen intern lookup table complicates a brute force attack. Indeed, there exists p2 n q! different n-bit lookup tables, so the 4-bit intern lookup table brings p2 4 q! « 2 44 possibilities. A brute force attack would also require to go through all the possible 2-bit lookup tables for each of the four input decodings and four output encodings, as well as for the four possible key values, and this, for each 256 inputs. Overall, this attack has to enumerate around 2 90 possibilities.

We have chosen the 2-bit encoding design as it was the lightest, but heavier encodings are also an option to enhance the brute-force attack resistance. Replacing the two middle 2-bit encodings and decodings by a 3-bit version also allows to have a 6-bit intern lookup table (around 2 296 possibilities), raising the total cost of a brute force attack to around 2 385 possibilities.

The Problem of the First and Last Round

Our white-box implementation implements GIFT with encoded inputs and outputs. To keep correctness with raw inputs, its first round input decodings and last round output encodings must be removed. At this point, in each TBox of the last round, the attacker would have access to the two output bits of the GIFT SBox GS that are not to be XORed with (unknown) round key bits. Indeed, we consider the round constant XORed to the left output bit of GS to be known, we can then recover the plain value of this bit. Thus, by brute-force, the attacker could recover the two other GS output bits, thus breaking all the TBoxes of the last round. This comprises the recovery of the input encodings of these TBoxes, that are inverses of the output encodings of the TBoxes of the penultimate round. These output encodings could hence be recovered and we could apply the same method to break the TBoxes of the penultimate round. Therefore, we could break the TBoxes round by round from the last round up until the first, thus leading to the break of the encoding scheme.

To avoid this kind of attacks, we suppose that GIFT is operating with encoded inputs and outputs. As a matter of fact, this is a use case common for instance in the DRM field.

x 3 x 2 y 3 y 2 G ´1 r´1,5 x 1 x 0 y 1 y 0 G ´1 r´1,0 GS y 7 y 5 y 3 y 1 GS in ILU T in z 7 z 5 z 3 z 1 GS out ILU T out c k 1 k 0 GS ‹ out ILU T r,0 y 6 y 4 y 2 y 0 z 6 z 4 z 2 z 0 Gr,3 z 7 ' c z 6 t 7 t 6 Gr,2 z 5 ' k 1 z 4 t 5 t 4
Gr,1 In this section, we first detail how, even in the case where ILU T is non linear, the attacker knowledge of the GIFT SBox GS results in the possibility of a differential attack targeting two consecutive rounds of TBoxes. Then, we demonstrate that this attack can be simplified if ILU T is linear. Finally, we look for the existence of a SBox complying with the GIFT SBox properties while preventing this 2-round differential attack. To that end, we use the notations detailed in subsection 8.1.

z 3 ' k 0 z 2 t 3 t 2 Gr,0 z 1 z 0 t 1 t 0 Encod in T Box out

Notations

To investigate the differential properties of a TBox, we use the following notations, illustrated in Figure 2 with T 0 , the right-most TBox of a round r. Additionally, we note that the reasoning developed in this section is valid for any TBox of any round but the last, as TBoxes of the following round will need to be considered. The intermediate values of the TBox can be detailed as :

• T Box in " px 7 x 6 x 5 x 4 x 3 x 2 x 1 x 0 q the input of the TBox.

• Decod out " py 7 y 6 y 5 y 4 y 3 y 2 y 1 y 0 q " pG ´1 r´1,15 px 7 x 6 q G ´1 r´1,10 px 5 x 4 q G ´1 r´1,5 px 3 x 2 q G ´1 r´1,0 px 1 x 0 qq the output of the input decodings.

• GS in " py 7 y 5 y 3 y 1 q the input of the SBox GS.

• GS out " pz 7 z 5 z 3 z 1 q " GSry 7 y 5 y 3 y 1 s the output of the SBox GS.

• GS out * " ppz 7 'cqpz 5 'k 1 qpz 3 'k 0 qz 1 q the output of the SBox GS, XORed with c the round constant bit and pk 1 , k 0 q the key bits.

• ILU T in " py 6 y 4 y 2 y 0 q the input of the intern SBox ILU T .

• ILU T out " pz 6 z 4 z 2 z 0 q " ILU T ry 6 y 4 y 2 y 0 s the output of the intern SBox ILU T .

• Encod in " ppz 7 ' cqz 6 pz 5 ' k 1 qz 4 pz 3 ' k 0 qz 2 z 1 z 0 q the input of the output encodings.

• T Box out " pt 7 t 6 t 5 t 4 t 3 t 2 t 1 t 0 q " pG r,3 ppz 7 ' cqz 6 q G r,2 ppz 5 ' k 1 qz 4 q G r,1 ppz 3 ' k 0 qz 2 q G r,0 pz 1 z 0 qq the output of the TBox.

Differential Attack

The 2-round differential attack can be decomposed into three major steps : first of all, we show that the left bit of each input encoding of the TBox T 0 can be recovered, i.e. for each input encoding G ´1 r´1,j and each px l , x m q P F 2 2 , we recover y l P F 2 such that G ´1 r´1,j px l x m q " y l . The second step applies the same principle to the TBoxes of the following round to recover the left bits of their input encodings, and especially to the left bits of the input encodings that are inverses of the output encodings of T 0 . This implies that, for each output encoding G r,k of T 0 and each pt l , t m q P F 2 2 , we can recover z ‹ l P F 2 such that G r,k pz ‹ 1 q " t l t m . Finally, the last step uses this knowledge about the encodings of T 0 and the knowledge of the GIFT SBox GS to recover k 0 and k 1 , the key bits embedded in T 0 .

First Step Of The Attack

As detailed hereinabove, to perform our attack, we first choose px 7 , x 6 , x 5 , x 4 , x 3 , x 2 q P F 6 2 and note that

• G ´1 r´1,15 px 7 x 6 q " y 7 y 6

• G ´1 r´1,10 px 5 x 4 q " y 5 y 4

• G ´1 r´1,5 px 3 x 2 q " y 3 y 2

As G ´1 r´1,0 is a 2-bit encoding, it can be described as a bijective endomorphism of F 2 2 . Thus, for every py 1 , y 0 q P F 2 2 , there exists a unique input px

py1,y0q 1 , x py1,y0q 0 q P F 2 2 such that G ´1 r´1,0 px py1,y0q 1 x py1,y0q 0
q " py 1 , y 0 q.

For example, there exists px p0,0q 1 , x p0,0q 0 q P F 2 2 such that the computation of T 0 rx 7 x 6 x 5 x 4 x 3 x 2 x p0,0q 1 x p0,0q 0 s entails Decod out " py 7 y 6 y 5 y 4 y 3 y 2 00q and more broadly the intermediate values listed in Figure 3.

Likewise, there exists px p0,1q 1 , x p0,1q 0 q P F 2 2 such that the output of the input decodings is Decod out " py 7 y 6 y 5 y 4 y 3 y 2 01q. It then implies that the GIFT SBox

G ´1 r´1,0 GS y 7 y 5 y 3 0 GS in ILU T in z 7 z 5 z 3 z 1 GS out ILU T out c k 1 k 0 GS ‹ out ILU T r,0 y 6 y 4 y 2 0 z 6 z 4 z 2 z 0 Gr,3 z 7 ' c z 6 t 7 t 6 Gr,2 z 5 ' k 1 z 4 t 5 t 4
Gr,1 input GS in is py 7 y 5 y 3 0q and the ILU T input ILU T in is py 6 y 4 y 2 1q. Furthermore, we note the ILU T output ILU T out " ILU T ry 6 y 4 y 2 1s as pz 1 6 z 1 4 z 1 2 z 1 0 q. This entails that the inputs of the output encodings Encod in are ppz 7 ' cqz 1 6 pz 5 ' k 1 qz 1 4 pz 3 ' k 0 qz 1 2 z 1 z 1 0 q, as summed up in Figure 4. More broadly, on the one hand, when we compute T 0 rx 7 x 6 x 5 x 4 x 3 x 2 x py1,y0q 1 x py1,y0q 0 s for all py 1 , y 0 q P F 2 2 , the intermediate values Decod out obtained after the input decodings are :

z 3 ' k 0 z 2 t 3 t 2 Gr,0 z 1 z 0 t 1 t 0 Encod in T Box out
• py 7 y 6 y 5 y 4 y 3 y 2 00q

• py 7 y 6 y 5 y 4 y 3 y 2 01q

• py 7 y 6 y 5 y 4 y 3 y 2 10q

• py 7 y 6 y 5 y 4 y 3 y 2 11q Furthermore, we note • GSry 7 y 5 y 3 0s " pz 7 z 5 z 3 z 1 q • GSry 7 y 5 y 3 1s " pz 1 7 z 1 5 z 1 3 z 1 1 q

• ILU T ry 6 y 4 y 2 0s " pz 6 z 4 z 2 z 0 q

• ILU T ry 6 y 4 y 2 1s " pz 1 6 z 1 4 z 1 2 z 1 0 q
The intermediate values Encod in , inputs of output encodings for the computations of the T 0 rx 7 x 6 x 5 x 4 x 3 x 2 x py1,y0q 1 x py1,y0q 0 s are thus • ppz 7 ' cqz 6 pz 5 ' k 1 qz 4 pz 3 ' k 0 qz 2 z 1 z 0 q for py 1 , y 0 q " p0, 0q

• ppz 7 ' cqz 1 6 pz 5 ' k 1 qz 1 4 pz 3 ' k 0 qz 1 2 z 1 z 1 0 q for py 1 , y 0 q " p0, 1q

• ppz 1 7 ' cqz 6 pz 1 5 ' k 1 qz 4 pz 1 3 ' k 0 qz 2 z 1 1 z 0 q for py 1 , y 0 q " p1, 0q

• ppz 1 7 ' cqz 1 6 pz 1 5 ' k 1 qz 1 4 pz 1 3 ' k 0 qz 1 2 z 1 1 z 1 0 q for py 1 , y 0 q " p1, 1q 51 G ´1 r´1,15

x 7 x 6 y 7 y 6

T Box in

Decod out G ´1 r´1,10

x 5 x 4 y 5 y 4 G ´1 r´1,5

x 3 x 2 On the other hand, in the first place, we can compute the values of T " tT 0 rx 7 x 6 x 5 x 4 x 3 x 2 x 1 x 0 s | px 1 , x 0 q P F 2 2 u. These values can also be written as

y 3 y 2 G ´1 r´1,0 x p0,1q 1 x p0,1q 0 0 1 GS y 7 y 5 y 3 0 GS in ILU T in z 7 z 5 z 3 z 1 GS out ILU T out c k 1 k 0 GS ‹ out ILU T r,0 y 6 y 4 y 2 1 z 1 6 z 1 4 z 1 2 z 1 0 Gr,3 z 7 ' c z 1 6 t 1 7 t 1 6 Gr,2 z 5 ' k 1 z 1 4 t 1 5 t 1 4 Gr,1 z 3 ' k 0 z 1 2 t 1 3 t 1 2 Gr,0 z 1 z 1 0 t 1 1 t 1 0 Encod in T Box out
• pG r,3 ppz 7 ' cqz 6 q G r,2 ppz 5 ' k 1 qz 4 qG r,1 ppz 3 ' k 0 qz 2 q G r,0 pz 1 z 0 qq
• pG r,3 ppz 7 ' cqz 1 6 q G r,2 ppz 5 ' k 1 qz 1 4 qG r,1 ppz 3 ' k 0 qz 1 2 q G r,0 pz 1 z 1 0 qq • pG r,3 ppz 1 7 ' cqz 6 q G r,2 ppz 1 5 ' k 1 qz 4 qG r,1 ppz 1 3 ' k 0 qz 2 q G r,0 pz 1 1 z 0 qq • pG r,3 ppz 1 7 ' cqz 1 6 q G r,2 ppz 1 5 ' k 1 qz 1 4 qG r,1 ppz 1 3 ' k 0 qz 1 2 q G r,0 pz 1 1 z 1 0 qq For each of the elements listed above, we cannot determine the corresponding px 1 , x 0 q. For example, we cannot determine px 1 , x 0 q P F 2 2 such that T 0 rx 7 x 6 x 5 x 4 x 3 x 2 x 1 x 0 s " pG r,3 ppz 7 ' cqz 1 6 q G r,2 ppz 5 ' k 1 qz 1 4 qG r,1 ppz 3 ' k 0 qz 1 2 q G r,0 pz 1 z 1 0 qq, we only know that the value of pG r,3 ppz 7 ' cqz 1 6 q G r,2 ppz 5 ' k 1 qz 1 4 qG r,1 ppz 3 ' k 0 qz 1 2 q G r,0 pz 1 z 1 0 qq figures in the set T . Nevertheless, we demonstrate that information about the encodings can still be deduced from the values of T .

Indeed, as G r,3 is a bijection,

• if G r,3 ppz 7 ' cqz 6 q " G r,3 ppz 7 ' cqz 1 6 q " G r,3 ppz 1 7 ' cqz 6 q " G r,3 ppz 1 7 ' cqz 1 6 q, then pz 7 ' cqz 6 " pz 7 ' cqz 1 6 " pz 1 7 ' cqz 6 " pz 1 7 ' cqz 1 6 , i.e. z 7 " z 1 7 and z 6 " z 1 6 . • if G r,3 ppz 7 ' cqz 6 q ‰ G r,3 ppz 7 ' cqz 1 6 q ‰ G r,3 ppz 1 7 ' cqz 6 q ‰ G r,3 ppz 1 7 ' cqz 1 6 q, then pz 7 ' cqz 6 ‰ pz 7 ' cqz 1 6 ‰ pz 1 7 ' cqz 6 ‰ pz 1 7 ' cqz 1 6 , i.e. z 7 ‰ z 1 7 and z 6 ‰ z 1 6 . • if #tG r,3 ppz 7 'cqz 6 q, G r,3 ppz 7 'cqz 1 6 q, G r,3 ppz 1 7 'cqz 6 q, G r,3 ppz 1 7 'cqz 1 6 qu " 2, then #tppz 7 'cqz 6 q, ppz 7 'cqz 1 6 q, ppz 1 7 'cqz 6 q, ppz 1 7 'cqz 1 6 u " 2. Consequently, either z 7 " z 1 7 and z 6 ‰ z 6 or z 7 ‰ z 1 7 and z 6 " z 6 .

The numerical value of the GIFT SBox GS is known (see subsection 7.1), and by notation GSry 7 y 5 y 3 0s " z 7 z 5 z 3 z 1 and GSry 7 y 5 y 3 1s " z 1 7 z 1 5 z 1 3 z 1 1 . Moreover, if for example z 7 " z 1 7 , then GSry 7 y 5 y 3 1s can be noted as z 7 z 1 5 z 1 3 z 1 1 . Hence, in this case :

#

GSry 7 y 5 y 3 0s " z 7 z 5 z 3 z 1 GSry 7 y 5 y 3 1s " z 7 z 1 5 z 1 3 z 1 1 ñ py 7 , y 5 , y 3 q " p1, 1, 0q or p1, 1, 1q ñ py 7 , y 5 q " p1, 1q ñ # G ´1 r´1,15 px 7 x 6 q " 1 G ´1 r´1,10 px 5 x 4 q " 1 Note that we can also set the values of px 7 , x 6 , x 5 , x 4 , x 1 , x 0 q and vary px 3 , x 2 q to obtain information about G ´1 r´1,15 , G ´1 r´1,10 and G ´1 r´1,0 , and keep the same principle when varying px 7 , x 6 q or px 5 , x 4 q.

To determine the value of the two key bits of this TBox T 0 of round r, the previous procedure needs to be applied in order to obtain the left bit of each of its four input encodings.

Second Step of the Attack : Consider TBoxes of Following Round

This first step can also be applied on the corresponding TBoxes of following round r `1, that admit G ´1 r,3 , G ´1 r,2 , G ´1 r,1 or G ´1 r,0 as one of their input decodings.

Hence, for all pa, bq P F 2 2 , we can recover c 3 , c 2 , c 1 , c 0 P F 2 such that

• G ´1 r,3 pabq " c 3 • G ´1 r,2 pabq " c 2 • G ´1 r,1 pabq " c 1 • G ´1 r,0 pabq " c 0
Therefore, regarding the inverses of these encodings G r,3 , G r,2 , G r,1 , G r,0 that are the output encodings of the TBox T 0 , we can for all pt, t 1 q P F 2 2 recover z7 , z5 , z3 , z1 P F 2 such that G r,3 pz 7 q " tt 1 , G r,2 pz 5 q " tt 1 , G r,1 pz 3 q " tt 1 and G r,0 pz 1 q " tt 1 .

Final Step Of The Attack

As the left bits of the TBox T 0 input encodings G ´1 r´1,15 , G ´1 r´1,10 , G ´1 r´1,5 and G ´1 r´1,0 are known, for any possible TBox input T Box in " px 7 , x 6 , x 5 , x 4 , x 3 , x 2 , x 1 , x 0 q P F 6 2 the corresponding intermediate GIFT SBox input GS in " py 7 y 5 y 3 y 1 q and thus GIFT SBox output GS out " GSry 7 y 5 y 3 y 1 s " pz 7 z 5 z 3 z 1 q can be deduced.

On the other hand, we can compute T Box out " pt 7 t 6 t 5 t 4 t 3 t 2 t 1 t 0 q " T 0 rx 7 x 6 x 5 x 4 x 3 x 2 x 1 x 0 s. Since the left bits of G ´1 r,3 , G ´1 r,2 , G ´1 r,1 and G ´1 r,0 are known as detailed in subsubsection 8.2.2, the values of pz 7 ' cq, pz 5 ' k 1 q, pz 3 ' k 0 q and z 1 P F 2 can be determined such that • When G ´1 r´1,0 px 1 x 0 q " 01, z 7 z 5 z 3 z 1 " GSry 7 y 5 y 3 0s and z 1 6 z 1 4 z 1 2 z 1 0 " ILU T ry 6 y 4 y 2 1s " ILU T ry 6 y 4 y 2 0s ' ILU T r0001s

" z 6 z 4 z 2 z 0 ' v 6 v 4 v 2 v 0 " pz 6 ' v 6 qpz 4 ' v 4 qpz 2 ' v 2 qpz 0 ' v 0 q
• When G ´1 r´1,0 px 1 x 0 q " 10,

z 1 7 z 1 5 z 1 3 z 1
1 " GSry 7 y 5 y 3 1s and z 6 z 4 z 2 z 0 " ILU T ry 6 y 4 y 2 0s

• When G ´1 r´1,0 px 1 x 0 q " 11,

z 1 7 z 1 5 z 1 3 z 1 1 " GSry 7 y 5 y 3 1s and z 1 6 z 1 4 z 1 2 z 1 0 " ILU T ry 6 y 4 y 2 1s " ILU T ry 6 y 4 y 2 0s ' ILU T r0001s " z 6 z 4 z 2 z 0 ' v 6 v 4 v 2 v 0 " pz 6 ' v 6 qpz 4 ' v 4 qpz 2 ' v 2 qpz 0 ' v 0 q
Thus, the different outputs of the TBox are

• G r,3 pz 7 z 6 qG r,2 pz 5 z 4 qG r,1 pz 3 z 2 qG r,0 pz 1 z 0 q

• G r,3 pz 7 pz 6 ' v 6 qqG r,2 pz 5 pz 4 ' v 4 qqG r,1 pz 3 pz 2 ' v 2 qqG r,0 pz 1 pz 0 ' v 0 qq

• G r,3 pz 1 7 z 6 qG r,2 pz 1 5 z 4 qG r,1 pz 1 3 z 2 qG r,0 pz 1 1 z 0 q

• G r,3 pz 1 7 pz 6 ' v 6 qqG r,2 pz 1 5 pz 4 ' v 4 qqG r,1 pz 1 3 pz 2 ' v 2 qqG r,0 pz 1 1 pz 0 ' v 0 qq By computing sets of values tT 0 rx 7 x 6 x 5 x 4 x 3 x 2 00s, T 0 rx 7 x 6 x 5 x 4 x 3 x 2 01s, T 0 rx 7 x 6 x 5 x 4 x 3 x 2 10s, T 0 rx 7 x 6 x 5 x 4 x 3 x 2 11su for px 7 , x 6 , x 5 , x 4 , x 3 , x 2 q P F 6 2 , it is possible to determine the value v 6 v 4 v 2 v 0 " ILU T r0001s. First of all, regarding the value of v 6 :

• If v 6 " 0 then tG r,3 pz 7 z 6 q, G r,3 pz 7 pz 6 'v 6 qq, G r,3 pz 1 7 z 6 q, G r,3 pz 1 7 pz 6 'v 6 qqu " tG r,3 pz 7 z 6 q, G r,3 pz 7 z 6 q, G r,3 pz 1 7 z 6 q, G r,3 pz 1 7 z 6 qu. Thus, -if z 1 7 " z 7 then #tG r,3 pz 7 z 6 q, G r,3 pz 7 z 6 q, G r,3 pz 7 z 6 q, G r,3 pz 7 z 6 qu " 1 -if z 1 7 " z 7 then #tG r,3 pz 7 z 6 q, G r,3 pz 7 z 6 q, G r,3 pz 7 z 6 q, G r,3 pz 7 z 6 qu " 2

• If v 6 " 1 then tG r,3 pz 7 z 6 q, G r,3 pz 7 pz 6 'v 6 qq, G r,3 pz 1 7 z 6 q, G r,3 pz 1 7 pz 6 'v 6 qqu " tG r,3 pz 7 z 6 q, G r,3 pz 7 z 6 q, G r,3 pz 1 7 z 6 q, G r,3 pz 1 7 z 6 qu. Thus, -if z 1 7 " z 7 then #tG r,3 pz 7 z 6 q, G r,3 pz 7 z 6 q, G r,3 pz 7 z 6 q, G r,3 pz 7 z 6 qu " 2 -if z 1 7 " z 7 then #tG r,3 pz 7 z 6 q, G r,3 pz 7 z 6 q, G r,3 pz 7 z 6 q, G r,3 pz 7 z 6 qu " 4

For example, we consider the second left-most output encoding G r,2 and the corresponding key bit k 0 . The attacker knows the values z 4 , z 1 4 , z 5 , z 1 5 P F 2 and the set of values G " tG r,2 ppz 5 ' k 0 qz 4 q, G r,2 ppz 5 ' k 0 qz 1 4 q, G r,2 ppz 1 5 ' k 0 qz 4 q, G r,2 ppz 1 5 ' k 0 qz 1 4 qu. Thus, he can at most recover the right input bits of G r,2 . More precisely, he knows the right bit of the inputs of G r,2 whose corresponding output belong to the set of values G : for g P G, he knows y P F 2 such that G r,2 pxyq " g, with an undetermined x P F 2 . Furthermore,

• If z 1
5 " z 5 and z 1 4 " z 4 then #G " 1. Twelve out of the twenty-four 2bit encodings g effectively verify that the right bit of the input of g whose corresponding output is G r,2 ppz 5 'k 0 qz 4 q equals to z 4 : among those twelve encodings, six verify that gp0z 4 q " G r,2 ppz 5 'k 0 qz 4 q and the other six verify that gp1z 4 q " G r,2 ppz 5 ' k 0 qz 4 q.

• If z 1 5 " z 5 and z 1 4 " z 4 then #G " 2. Four of the twelve 2-bit encodings g verifying that the right bit of the input ab P F 2 of g whose corresponding output is G r,2 ppz 5 ' k 0 qz 4 q equals to z 4 also verify that gpabq " G r,2 ppz 5 ' k 0 qz 4 q. Among those four encodings, two verify that gp0z 4 q " G r,2 ppz 5 ' k 0 qz 4 q and the other two verify that gp1z 4 q " G r,2 ppz 5 ' k 0 qz 4 q.

• If z 1 5 " z 5 and z 1 4 " z 4 then #G " 2. Four of the twelve 2-bit encodings g verifying that the right bit of the input ab P F 2 of g whose corresponding output is G r,2 ppz 5 ' k 0 qz 4 q equals to z 4 also verify that gpabq " G r,2 ppz 5 ' k 0 qz 4 q. Among those four encodings, two verify that gp0z 4 q " G r,2 ppz 5 ' k 0 qz 4 q and the other two verify that gp1z 4 q " G r,2 ppz 5 ' k 0 qz 4 q.

• If z 1 5 " z 5 and z 1 4 " z 4 then #G " 4. Two of the twelve 2-bit encodings g verifying that the right bit of the input ab P F 2 of g whose corresponding output is G r,2 ppz 5 ' k 0 qz 4 q equals to z 4 also verify that gpabq " G r,2 ppz 5 ' k 0 qz 4 q, gpabq " G r,2 ppz 5 ' k 0 qz 4 q and gpabq " G r,2 ppz 5 ' k 0 qz 4 q. Among those two encodings, one verifies that gp0z 4 q " G r,2 ppz 5 ' k 0 qz 4 q and the other one verifies that gp1z 4 q " G r,2 ppz 5 ' k 0 qz 4 q.

Therefore, in all cases there exists as many potential 2-bit encodings G r,2 compatible with k 0 " 0 as potential 2-bit encodings G r,2 compatible with k 0 " 1. Consequently, it is not possible for an attacker to determine key bits in a differential manner without further information on the output encodings of the TBox.

Conclusion

In this subsection we demonstrate that using a linear intern SBox ILU T in the presented TBox construction leads to the recovery of this SBox, but that does not allow an attacker to determine with certainty the key bits embedded in a TBox T by a differential attack on T itself.

Nevertheless using such a linear ILU T implies a slight improvement in the 2round differential attack detailed in subsection 8.2. We however do not consider this eventuality to constitute a major additionnal threat to the construction as, by Property 4, there exists ś 3 i"0 p2 4 ´2i q " 20160 linear 4-bit SBoxes. Therefore, the probability to randomly pick an 4-bit SBox that is linear equals to 20160 2 4 ! , i.e. around 2 ´30 , thus negligeable.

Another GIFT SBox

We search for the existence of an SBox complying with the GIFT SBox properties listed in subsubsection 8.4.1 while preventing the differential attack presented in subsection 8.2.

GIFT SBox Properties

The GIFT SBox GS has been chosen according to the following properties ([BPP `17b], §3.3):

• The implementation cost of GS should be of at most 17 units, with the operations NOT, NAND, NOR counting as 1 unit, and XOR and XNOR as 2 units.

• GS should have differential score and linear score of at least 4. (see subsection 4.3)

• There exists a common BOGI permutation for both differential and linear cases. In other words, there exists a permutation of t0001, 0010, 0100, 1000u such that the Bad Outputs (BO) are mapped to Good Inputs (GI) in both of DDT and LAT cases.

• # p∆x, ∆yq P F 4 2 ˆF4 2 |# x P F 4 2 |GSrxs ' GSrx ' ∆xs " ∆y ( ą 4 ( ď 2.
• # x P F 4 2 |GSrxs ' GSrx ' ∆xs " ∆y ( ą 4 ùñ HW p∆xq `HW p∆yq ě 4.

Attack Resistance Property

The attack presented in subsection 8.2 functions thanks to the differential properties of the GIFT SBox GS. To prevent this attack from happening, an SBox S must ensure that no differential SBox computation leads to exploitable information.

For instance, noting Sry 7 y 5 y 3 0s " z 7 z 5 z 3 z 1 and Sry 7 y 5 y 3 1s " z 7 *z 5 *z 3 *z 1 * with z i * P tz i , z i , z 1 i u and z 1 i being either z i or z i (but not determined), no information about y 7 , y 5 or y 3 should leak thanks to the knowledge of the values of S. In other words, we must have P ˜yi " 0 Sry 7 y 5 y 3 0s " z 7 z 5 z 3 z 1 Sry 7 y 5 y 3 1s " z 7 *z 5 *z 3 *z 1 * ¸" 1 2 for every i P t3, 5, 7u.

For example, if there exists a tuple py 7 , y 5 , y 3 q P F 3 2 such that Sry 7 y 5 y 3 0s " z 7 z 5 z 3 z 1 and Sry 7 y 5 y 3 1s " z 7 z 1 5 z 1 3 z 1 , then we must have that for each pvy 7 , vy 5 , vy 3 q P F 3 2 Srvy 7 vy 5 vy 3 0s " vz 7 vz 5 vz 3 vz 1 implies that Srvy 7 vy 5 vy 3 1s " vz 7 vz 1 5 vz 1 3 vz 1 . Hence, no information on py 7 , y 5 , y 3 q would leak.

To avoid any point of attack, the previous property should stand for every pair • Sry 7 y 5 y 3 0s and Sry 7 y 5 y 3 1s

• Sry 7 y 5 0y 1 s and Sry 7 y 5 1y 1 s • Sry 7 0y 3 y 1 s and Sry 7 1y 3 y 1 s • Sr0y 5 y 3 y 1 s and Sr1y 5 y 3 y 1 s and for every z 7 *z 5 *z 3 *z 1 *, with z i * P tz i , z i , z 1 i u. Therefore, this implies that, to thwart this attack on the TBox, the underlying SBox S should obey to the following property : Property 14. There exists ps 3 , s 2 , s 1 , s 0 q P F 4 2 such that for all py 7 , y 5 , y 3 , y 1 q P F 4 2 , Sry 7 y 5 y 3 y 1 s " Sry 7 y 5 y 3 y 1 s ' ps 3 , s 2 , s 1 , s 0 q.

Consequently, there exists 16˚15˚14˚12˚10˚8˚6˚4˚2 " 30˚2 7 ˚8! » 2 27 4bit SBoxes satisfying this property. We aim to determine if any of these SBoxes could also satisfy the GIFT SBox properties.

A New SBox

After an heuristic research, we determine the following SBox GS 1 that complies with most of the GIFT SBox properties.

GS 1 " r5, 0, 3, 4, 15, 6, 1, 10, 2, 9, 14, 7, 12, 11, 8, 13s Indeed, GS 1 presents the following 1-1 Difference Distribution Table (Table 2) and 1-1 Linear Approximation Table (Table 3)

3: 1-1 LAT of GS 1
Thus, firstly, the repartition between Good Inputs and Bad Inputs on the one hand and Good Outputs and Bad Outputs on the other hand that are observed from the 1-1 DDT are :

• GI D " t0001, 1000u • GO D " t0001, 1000u • BI D " t0010, 0100u • BO D " t0010, 0100u
Secondly, the repartition between Good Inputs and Bad Inputs on the one hand and Good Outputs and Bad Outputs on the other hand that are observed from the 1-1 LAT are :

• GI L " t0001, 0010u
• GO L " t0001, 0010, 0100u

• BI L " t0100, 1000u • BO L " t1000u
Therefore, we can sum up the compliance of GS 1 to the GIFT SBox properties as following:

• GS 1 has for differential score #GI D `#GO D " 4 and linear score #GI L #GI D " 5. 9 Masking Scheme Design Rationale

The second goal of this thesis is to design a Boolean masking scheme composed of Boolean operations that, complementary to its side-channel countermeasure nature by design, can correct at most two one-bit flipping faults committed during (or just before) its execution. This section details the main design choices made during the development of this new masking scheme. First of all, it will be described how the scheme verifies the properties listed in subsection 5.4 that are sufficient conditions for first-order probing security. Subsequently, it will be explained how the correction of input shares is performed at the beginning of the scheme execution.

Masking Scheme Design Constraints

We aim to design our AND masking scheme so that it verifies the three implementation properties listed in Lemma 1 (correctness, uniformity and noncompleteness) to ensure its first order probing security. The purpose of the scheme is to compute a ^b with a, b P F 2 , while supposing that all input shares A i from input A and B i from input B are words of an error-correcting code in order to introduce code correction at the beginning of the scheme. In other words, HW p À i A i q mod 2 " a and HW p

À i B i q mod 2 " b.
To ensure compatibility between consecutive instances of the scheme, this implies that all the output shares will be codewords as well. Since the goal is to design a Boolean masking scheme, we aim to use an error-correcting code whose corresponding decoding process could be written with only Boolean operations, which is the case for BCH error-correcting codes, via the Peterson-Gorenstein-Zierler algorithm ( [START_REF] Peterson | Encoding and error-correction procedures for the bose-chaudhuri codes[END_REF]). Furthermore, we also want to introduce randomness, with random polynomials R i of respective parities r i .

To achieve this, we design in the first place variables s i P F 2 intented to be the parities of the codewords S i , output shares of our scheme. These output shares parities depend on products between parities a i and b i of shares of different inputs, products a i r j or r i b j between parities of input shares and parities of random polynomials, and products r i r j between parities of random polynomials. We aim to design those variables s i so that they comply with both uniformity and non-completeness properties regarding the input shares and random polynomials parities a i , b i and r i . Finally, by the correctness property, the sum of these output shares parities s i will be equal to a ^b.

In the remainder of this subsection, we describe how these aimed design and masking scheme properties influence the construction of output shares parities s i and the choice of the used BCH code.

Non-Completeness Implies a Condition on the Number of Shares

First of all, to be able to perform one instance of the scheme after another, the number of output shares needs to be equal to the number of shares of each input. Furthermore, to comply with non-completeness the number of input shares of both a and b cannot be equal to 2. Indeed, in this case, we would suppose that • a is represented by two codewords shares A 0 and A 1 of respective parities a 0 and a 1 such that a 0 ' a 1 " a.

• b is represented by two codewords shares B 0 and B 1 of respective parities b 0 and b 1 such that b 0 ' b 1 " b.

• There are two output codewords shares S 0 and S 1 of respective parities s 0 and s 1 depending on parities a 0 , a 1 , b 0 and b 1 , such that their sum s 0 ' s 1 verifies s 0 ' s 1 " a ^b.

Therefore, the input shares parities a i and b i and output shares parities s 0 and s 1 would verify that

s 0 ' s 1 " a ^b " a 0 b 0 ' a 0 b 1 ' a 1 b 0 ' a 1 b 1
As a result, there would be four different products a i b j of input shares parities to be distributed among the two output shares parities s i , namely a 0 b 0 , a 0 b 1 , a 1 b 0 and a 1 b 1 . Consequently, at least one variable s i would be computed from two (or more) of those products. But, since there are only two shares a i and two shares b i , the sum of any two out of the four products a i b j can not verify non-completeness.

In conclusion, the number n in of input and output shares of the scheme needs to be at least 3.

Parity Requirement on the BCH Code Generator Polynomial

As we consider a i and b j the parities of codewords input shares and s i the parities of codewords output shares, the generator polynomial of the BCH correcting code they belong to needs to be of odd parity so that variables a i , b j and s i could take either values in F 2 . To that end, we suppose the generator polynomial of this BCH correcting code of length n to be gpXq " lcmpM α b pXq, M α b`1 pXq, . . . , M α b`δ´2 pXqq, such that m is the multiplicative order of 2 modulo n and α is an element of F q m of multiplicative order n. Based on Property 10, gpXq can be written as a product of M α i pXq polynomials.

Furthermore, according to its definition, the degree of a polynomial M α i pXq is determined by the cardinality of Cpiq, the corresponding 2-cyclotomic class of i. Therefore, on the one hand, Property 7 states that for any possible code length n the only 2-cyclotomic class modulo n of cardinality one is Cp0q, the 2cyclotomic class of 0. Consequently, the corresponding polynomial M α 0 pXq has even parity, since M α 0 pXq " X ´α0 " X `1. On the other hand, this property also implies that all other 2-cyclotomic classes modulo n have a cardinality of at least two, so the polynomials M α i pXq with 0 ă i ă n have a degree greater than or equal to two.

In addition to this, all irreducible polynomials of F 2 rXs with degree greater than or equal to two have odd parity, as otherwise they would admit 1 as a root, and therefore could be factorized by X `1. Consequently, as they are irreducible polynomials of F 2 rXs according to Property 9, all polynomials M α i pXq with 0 ă i ă n have odd parity.

As a conclusion, to ensure its odd parity, the generator polynomial gpXq of the BCH code used in the scheme must not be a multiple of M α 0 pXq " X `1. In other words, this generator polynomial gpXq " lcmpM α b pXq, M α b`1 pXq, . . . , M α b`δ´2 pXqq must verify that 0 R tb mod n, b `1 mod n, . . . , b `δ ´2 mod nu, i.e. 0 ă b ă n ´pδ ´2q.

Maximizing the BCH Code Dimension

In subsubsection 9.2.5, it will be detailed why a BCH code of correction capacity at least two is needed to ensure the correctness of the scheme. Since the correction capacity t of a BCH code of minimum Hamming distance at least δ verifies t ě t δ´1 2 u, imposing t ě 2 necessitates that δ ě 5. Therefore, the generator polynomial gpXq of the BCH code we aim to use can be rewritten in the form of

gpXq " lcmpM α b pXq, M α b`1 pXq, M α b`2 pXq, M α b`3 pXqq, with 0 ă b ă n ´3.
Furthermore, we know that subsequently we will need codewords to act as masks to be applied to an array of cross-products of parities among input shares parities a i and b i and random polynomials parities r i , and this in order to compute the parities s i of the output shares. To ensure correctness, all crossproducts involved of form a i r j , r i b j or r i r j must appear in an even number of variables s i and all cross-products involved of form a i b j must feature in an odd number of variables s i , therefore those codewords need to have a certain number of exponents in common. To that end, we aim to maximize the search space for these codewords, and thus the dimension of the code they will belong to.

Randomness Requirement and its Impact on the BCH Code Choice

We note n r the total number of random polynomials involved in the scheme.

We suppose the number of random polynomials associated to each input to be identical, that is to say that there exists as many random polynomials parities r j that are to be multiplied to input shares parities a i than random polynomials parities r i that are to be multiplied to input shares parities b j . Consequently, n r is even and the number of random polynomials associated to each input is equal to nr 2 . To keep a reasonable randomness requirement of our scheme, we impose on ourselves that the number nr 2 of random variables associated to each input is strictly less than the number of shares of each input. For instance, the number of random polynomials parities r j that are to be multiplied to the input parities a i is defined to be strictly less than the number n in of shares A i , and reciprocally.

As the number n in of input shares A i is equal to the number of input shares B i , it implies that

n r 2 ă n in .
Therefore, by definition of n in and nr 2 , there exists at most pn in `nr 2 q 2 products of parities involved in the computation of output shares parities s i , divided as follows:

• n 2 in products a i b j of input shares parities

• nin˚nr 2 products a i r j • nin˚nr 2 products r i b j • `nr 2 ˘2 products r i r j
The total number of these products is considered to be an upper bound of the length of the BCH code used in the scheme, as codewords serving as masks will be applied to the array gathering them (see section 10). Therefore, applying a mask to an array that would be longer than this array would provoke a loss of efficiency. In the same manner, n 2 in is a lower bound of the code length n since it corresponds to the number of products a i b j , that are imperatively involved in the computations of s i variables to ensure correctness. To sum up, the code length n must verify that

n 2 in ď n ď pn in `nr 2 q 2
First and foremost, supposing that the number of shares n in is 3 and the number of random polynomials associated to each input nr 2 is 2, these bounds imply that the code length n would verify that 9 ď n ď 25. For every potential code length n complying with those bounds, the minimal degree of generator polynomials verifying the conditions detailed in subsubsection 9.1.3 is listed in Table 4 Therefore, for a code length n within the bounds 9 ď n ď 25, the maximum potential dimension of a BCH code of correction capacity at least 2 is k " 12, reached for either n " 21 or n " 23. These cases correspond to BCH codes of cardinality 2 12 .

Secondly, if the number of shares n in is 4 and the number of random polynomials associated to each input nr 2 is 3, then the code length n verifies 16 ď n ď 49. Retaining the same BCH code properties, the maximum potential dimension value reaches k " 29 when n " 45, as listed in Table 5 Since the code dimension k " 29 implies a rather large search space for potential codewords serving as masks, we select the corresponding number of shares n in " 4. Subsequently, if the number of random polynomials associated to each input nr 2 verifies nr 2 ď 2, then it implies that pn in `nr 2 q 2 ă n " 45. This brings a contradiction to the condition that pn in `nr 2 q 2 is an upper bound of the value of code length n, therefore we define nr 2 " 3. Therefore, the BCH code used in the scheme has length n " 45, cardinality 2 29 and generator polynomial gpXq " lcmpM α pXq, M α 2 pXq, M α 3 pXq, M α 4 pXqq " pX 12 `X3 `1q ˚pX 4 `X `1q " X 16 `X13 `X12 `X7 `X3 `X `1, with m " 12 is the multiplicative order of 2 modulo n " 45 and α is a 45 th primitive root of unity in F q m " F 2 12 .

Ensuring Uniformity and Correctness

Since we choose the number of shares to be n in " 4 and the number of random polynomials associated to each input to be nr 2 " 3, there exists at most 49 different products of parities involved in the computation of the output shares parities s i . Those parities can be divided in the following way :

• 16 products of form a i b j that must all be present in an odd number of s i computations.

• 12 products of form a i r j , 12 products of form r i b j and 9 products of form r i r j . Each of these products does not necessarily need to be present in the computation of any parity s i , but if it does, it needs to be involved in an even number of s i computations to guarantee correctness (so that the occurrences could cancel themselves).

It can be noticed that, to ensure uniformity, it is compulsory that each s i includes at least one single parity, i.e. one variable of the form a i , b i or r i . Indeed, as variables a i , b i and r i are independent from one another and verify equiprobability in F 2 , all products of two of those variables admit p 3 4 , 1 4 q as probability vector in F 2 . Therefore, sums of those products cannot be equiprobable according to Property 15 hereinbelow.

Property 15. Let P the set of products of form a i b j , a i r j , r i b j and r i r j . Any sum s of elements in P complying with non-completeness cannot be equiprobable in F 2 .

Proof. We will suppose for this proof that the sum s comprises addends of the four types. If otherwise, this does not change the core of the demonstration. Rearranging the addends according to their type, such sum s can be written in the form of a j0 b k0 ' . . . ' a jΘ´1 b kΘ´1 ' a l0 r m0 ' . . . ' a lΛ´1 r mΛ´1 ' r n0 b o0 ' . . . ' r nχ´1 b oχ´1 ' r p0 r q0 ' . . . ' r p ψ´1 r q ψ´1 , with 0 ď Θ ď 16, 0 ď Λ ď 12, 0 ď χ ď 12 and 0 ď ψ ď 9.

As s complies with non-completeness, it involves at most n in ´1 " 3 different shares a i . We will note them a υ , a δ and a ξ . In potential cases where strictly less than three shares a i would be involved in the computation of s, we can consider a υ , a δ or a ξ to be null. Subsequently, s can be also be rewritten such that

s " a υ V B υ ' a δ V B δ ' a ξ V B ξ ' r 0 V B 0 ' r 1 V B 1 ' r 2 V B 2 ,
with each V B i being a sum of at most n in ´1 " 3 variables b i and some variables r i among r 3 , r 4 and r 5 . In the same way as for variables a υ , a δ and a ξ , if r 0 , r 1 or r 2 are not involved in s, we respectively consider V B 0 , V B 1 or V B 2 to be null.

By definition of sharings (subsection 3.2), any tuple of at most n in ´1 " 3 parities b i of shares B i constitute a set of variables independent from one another. Furthermore, random polynomials R i are independent one from another and independent from shares B i by design, and so are their respective parities b i and r i . Therefore, each sum V B i verifies Therefore, to guarantee the uniformity of each s i , at least one single parity among the variables a i , b i and r i needs to figure in the computation of each s i . Moreover, similarly as for products a i r j , r i b j and r i r j , these single parities must be added in even numbers of s i computations to ensure the correctness of the overall scheme.

Therefore, to build the output shares parities s i , we first randomly split the 16 products of parities of form a i b j among s 0 , s 1 , s 2 and s 3 so that each of them complies with non-completeness. At this point, each s i variable cannot verify equiprobability (according to Property 15). Consequently, we add three single variables to pairs of s i to ensure global equiprobability of each s i among the values observed for all possible inputs, and then equiprobability conditioned by the value of a ^b necessary for the uniformity property. Among all single variables, using r 0 , a 2 and r 5 allows us to do so while verifying non-completeness.

Subsequently, we add products of form a i r j ,r i b j or r i r j one after another to pairs of s i variables, so that, when conditioned by either value of a ^b, the probability of each value of ps 0 , s 1 , s 2 , s 3 q verifying s 0 ' s 1 ' s 2 ' s 3 " a ^b equals to `1 2 ˘3, while retaining the non-completeness property. We obtain the following formulas for the respective parities of output shares S 0 , S 1 , S 2 and S 3 :

• s 0 " r 1 b 1 'r 2 b 1 'r 0 'a 1 r 3 'a 2 r 5 'a 2 b 2 'a 3 r 3 'a 3 b 2 'r 1 b 0 'a 3 b 1 'r 1 r 5 'r 2 r 5 • s 1 " r 1 b 1 ' r 0 ' a 2 b 1 ' a 0 b 2 ' a 2 r 5 ' a 0 b 1 ' a 0 r 3 ' a 3 b 0 ' r 2 b 2 ' a 0 b 0 ' r 2 r 5 ' a 2 ' r 1 r 5 ' r 0 r 3 • s 2 " a 3 b 3 'a 1 r 5 'r 5 'a 3 r 3 'r 2 b 2 'a 1 b 2 'r 1 b 0 'r 2 r 5 'r 2 b 0 'a 2 'r 0 r 3 'a 2 r 4 • s 3 " a 2 b 3 ' r 2 b 1 ' a 1 r 5 ' a 1 b 1 ' r 5 ' a 1 r 3 ' a 0 r 3 ' a 1 b 0 ' a 0 b 3 ' r 2 r 5 ' r 2 b 0 ' a 1 b 3 ' a 2 b 0 ' a 2 r 4

Input Shares Correction

To fulfill our purpose of developing the new masking scheme to be fault-resistant, we design the input shares correction part as described in subsubsection 9.2.2. Additionally, we specify in subsubsection 9.2.1 the fault attack model we place ourselves into. Furthermore, for the purpose of detail, the effective functioning of the input shares correction part will be described for the different fault cases considered by our scheme in subsubsection 9.2.4 and subsubsection 9.2.5.

Fault Attack Model

For the design of this new masking scheme, we place ourselves in the one-bit flipping fault attack model, that is to say we consider an attacker to be able to randomly flip a bit in the implementation. Indeed, this is a fault attack model likely to be used by an attacker targeting a bitsliced implementation.

We demonstrate below the resistance of the masking scheme to the introduction of at most two one-bit faults in its input shares, as it is a reasonable fault resistance goal for each AND operation among all AND instances of the bitsliced implementation of a cryptographic primitive.

Input Shares Correction Design

The objective of the correcting design is to be able to correct potential faults in the masking scheme input shares, that is to say to correct faults committed at the end of the preceding instances or just before the beginning of the current instance of the scheme. That is why we impose that all input and output shares of the masking scheme will be codewords, and why the code correction is placed at the beginning of the scheme rather than at the end : as instances of the scheme are supposed to be used successively in a wider bitsliced implementation to mask different ANDs, this implies that faults committed in the last stages of one instance of the scheme or just after the end will be corrected at the beginning of the following instances.

To that end, to minimize the number of corrections needed we compute and correct sub-sums of input shares instead of correcting each input share separately. For non-completeness compliance, it is not possible to add all polynomial shares A i of input A (or all polynomial shares B i of input B) in a same sub-sum. Furthermore, we aim to design those sub-sums in such a way that, while using the smallest number of them, it is feasible in case of a fault to determine whether it was committed on A or B although they are sub-sums of shares coming from both inputs A and B. To do so, we determine the following repartition of input shares between sub-sums V 0 , V 1 and V 2 and correct those sub-sums into respective codewords noted

V 1 0 , V 1 1 and V 1 2 : • V 0 " A 0 ' A 1 ' B 0 ' B 1 • V 1 " A 2 ' A 3 ' B 2 ' B 3 • V 2 " A 2 ' A 3 ' B 0 ' B 1
We can outline this repartition of polynomial shares A i and B i among subsums V 0 , V 1 and V 2 as follows in Figure 5.

Subsequently, we add the sub-sums V i and their corrected values V 1 i to the polynomial input shares A i and B i to obtain the modified input shares A 1 i and B 1 i . These modified input shares will be used instead of the initial ones for the remainder of the masking scheme.

• A 1 0 " A 0 ' V 0 • A 1 1 " A 1 ' V 1 1 • A 1 2 " A 2 ' V 2 • A 1 3 " A 3 ' V 1 2 • B 1 0 " B 0 ' V 1 • B 1 1 " B 1 ' V 1 0 • B 1 2 " B 2 ' V 2 • B 1 3 " B 3 ' V 1 2
We can notice that the formulas of sub-sums V i imply that introducing a one-bit fault on share A 0 brings the same impact on the scheme as introducing a fault on A 1 . In the same way, introducing a one-bit fault on A 2 brings the same impact as introducing a fault on A 3 , as well as introducing a fault on B 0 or B 1 , or on B 2 or B 3 . Therefore, for the remainder of this dissertation, we will exclusively consider faults in A 0 , A 2 , B 0 or B 2 to simplify the notations.

Regarding the correctness of parities of sub-sums V i depending on the location of the fault, Table 6 indicates if the parities of the sub-sums V 0 , V 1 or V 2 are correct after the introduction of a fault on one input share (A 0 , A 2 , B 0 or

B 2 ). Fault Location V i V 0 V 1 V 2 A 0 ✗ ✓ ✓ A 2 ✓ ✗ ✗ B 0 ✗ ✓ ✗ B 2 ✓ ✗ ✓
Table 6: Correctness of the parity of sub-sums V i depending on the location of the single one-bit fault According to the definitions of the sub-sums V i and regardless of the one-bit fault location, the parities of corresponding corrected sub-sums V 1 i verify • HW pV 1 0 q mod 2 " a 0 ' a 1 ' b 0 ' b 1 • HW pV 1 1 q mod 2 " a 2 ' a 3 ' b 2 ' b 3 • HW pV 1 2 q mod 2 " a 2 ' a 3 ' b 0 ' b 1 Moreover, if the one-bit fault impacts a sub-sum V i (see Table 6), then HW pV i q mod 2 " HW pV 1 i q mod 2 ' 1.

Fault Location Parities of V 0 ' V 1 1 ' V 2 ' V 1 2 V 1 0 ' V 1 ' V 2 ' V 1 2 A 0 b 0 ' b 1 ' b 2 ' b 3 ' 1 a 0 ' a 1 ' a 2 ' a 3 A 2 b 0 ' b 1 ' b 2 ' b 3 ' 1 a 0 ' a 1 ' a 2 ' a 3 B 0 b 0 ' b 1 ' b 2 ' b 3 a 0 ' a 1 ' a 2 ' a 3 ' 1 B 2 b 0 ' b 1 ' b 2 ' b 3 a 0 ' a 1 ' a 2 ' a 3 ' 1
Table 7: Parities of sub-sums V i and V 1 i allow to correct the impact of a one-bit fault on an input share.

the minimum number of sub-sums needed to cover all potential fault locations while complying with non-completeness is three, as deployed in our scheme.

Furthermore, in this two one-bit faults scenario, each sub-sum naturally carries at most two one-bit faults. In this case, this sub-sum, despite being faulted, represents the correct parity as parities are computed modulo 2. Nevertheless, we impose that the BCH code we use has a correction capacity of at least 2, to avoid the eventuality where a correction of two faults by a BCH code of correction capacity strictly less than two could modify the sub-sum in question and its then-correct parity.

• A 1 0 " A 0 ' V 0 • A 1 1 " A 1 ' V 1 1 • A 1 2 " A 2 ' V 2 • A 1 3 " A 3 ' V 1 2 • B 1 0 " B 0 ' V 1 • B 1 1 " B 1 ' V 1 0 • B 1 2 " B 2 ' V 2 • B 1 3 " B 3 ' V 1 2 10.

Array of Subproducts

We consider n r " 6 random polynomials R 0 , R 1 , R 2 , R 3 , R 4 , R 5 P F 45 2 . Moreover, we note a i P F 2 the parities of respective input shares A 1 i , b i P F 2 the parities of respective input shares B 1 i and r i P F 2 the parities of respective random polynomials R i . Subsequently, we compute the following array of products of parities, noted mCP :

mCP " » - - - - - r 2 b 3 a 3 b 3 r 1 b 1 a 2 b 3 r 2 b 1 a 3 r 4 r 0 a 1 r 5 a 1 b 1 a 0 r 4 a 2 b 1 r 0 b 2 a 0 b 2 r 5 r 1 r 3 a 1 r 3 a 1 r 4 a 2 r 5 a 2 b 2 a 3 r 3 a 0 b 1 a 0 r 3 a 3 b 0 r 0 b 1 a 1 b 0 r 0 r 5 r 2 r 3 r 1 r 4 a 3 b 2 r 2 b 2 a 1 b 2 a 0 b 0 r 1 b 0 r 0 b 0 a 3 b 1 a 0 b 3 a 0 r 5 r 2 r 5 r 2 b 0 a 2 r 1 r 5 a 1 b 3 r 0 r 3 a 2 b 0 a 2 r 4 fi ffi ffi ffi ffi fl
The positioning of the products in the array enables to compute the output shares parities s i by applying to mCP the following masks maskS 0 , maskS 1 , maskS 2 , maskS 3 P F 45 2 . The literal formulas of those output shares parities s i depending on a i , b i and r i are listed in subsubsection 9.1.5. In this manner, each output parity s i can be computed the following way :

s i " 44 ÿ j"0 pmCP rjs & maskS i rjsq
These masks, whose values are listed hereinbelow, are also codewords. Therefore, they can be corrected a few times among all the masked AND occurrences of a global bitsliced implementation of a cryptographic primitive. maskS 0 " » -----0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 1 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 1 0 0 1 0 0 0 0 fi ffi ffi ffi ffi fl maskS 1 " » -----0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 1 0 1 0 0 fi ffi ffi ffi ffi fl maskS 2 " » -----0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 0 1 fi ffi ffi ffi ffi fl maskS 3 " » -----0 0 0 1 1 0 0 1 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 1 0 1 1 fi ffi ffi ffi ffi fl These masks maskS i are respectively equivalent to the following codewords ms i pXq :

• ms 0 pXq " X 42 `X40 `X38 `X29 `X27 `X26 `X25 `X16 `X12 X10 `X7 `X4 , with ms 0 " pX 26 `X24 `X23 `X21 `X19 `X18 X16 `X15 `X13 `X12 `X10 `X9 `X7 `X6 `X5 `X4 q ˚gpXq

• ms 1 pXq " X 42 `X38 `X34 `X32 `X27 `X24 `X23 `X22 `X15 X13 `X7 `X5 `X4 `X2 , with ms 1 " pX 26 `X23 `X20 `X19 `X18 X16 `X12 `X11 `X10 `X6 `X3 `X2 q ˚gpXq

• ms 2 pXq " X 43 `X37 `X31 `X25 `X15 `X14 `X12 `X7 `X6 `X5 `X2 `1, with ms 2 " pX 27 `X24 `X23 `X19 `X18 `X16 `X14 `X13 `X11 X8 `X7 `X6 `X5 `X3 `X `1q ˚gpXq

• ms 3 pXq " X 41 `X40 `X37 `X36 `X31 `X29 `X23 `X20 `X9 `X7 X6 `X3 `X `1, with ms 3 " pX 25 `X24 `X22 `X21 `X19 `X17 X15 `X14 `X13 `X12 `X11 `X9 `X8 `X7 `X6 `1q ˚gpXq

Output Shares Computation

For 0 ď i ď 3, we compute the variables x i,0 , x i,1 , x i,2 , x i,3 P F 2 depending on variables a i , b i and r i , such that the following sets are four sets of independent and equiprobable variables.

• s 0 , s 1 , s 2 , x 0,0 , x 0,1 , x 0,2 and x 0,3

• s 1 , s 0 , s 3 , x 1,0 , x 1,1 , x 1,2 and x 1,3

• s 2 , s 0 , s 3 , x 2,0 , x 2,1 , x 2,2 and x 2,3

• s 3 , s 1 , s 2 , x 3,0 , x 3,1 , x 3,2 and x 3,3

Subsequently, we randomly choose four codewords C 0,0 , C 1,0 , C 2,0 , C 3,0 P F 45 2 of odd parity, and twenty-four codewords of even parity (C 0,j , C 1,j , C 2,j , C 3,j P F 45 2 for 1 ď j ď 6). Finally, we use those codewords and these sets of variables in F 2 to compute the output shares S 0 , S 1 , S 2 , S 3 P F 45 2 such that

• S 0 " s 0 ˚C0,0 `s1 ˚C0,1 `s2 ˚C0,2 `x0,0 ˚C0,3 `x0,1 ˚C0,4 `x0,2 ˚C0,5 x0,3 ˚C0,6 • S 1 " s 1 ˚C1,0 `s0 ˚C1,1 `s3 ˚C1,2 `x1,0 ˚C1,3 `x1,1 ˚C1,4 `x1,2 ˚C1,5 x1,3 ˚C1,6 • S 2 " s 2 ˚C2,0 `s0 ˚C2,1 `s3 ˚C2,2 `x2,0 ˚C2,3 `x2,1 ˚C2,4 `x2,2 ˚C2,5 x2,3 ˚C2,6 • S 3 " s 3 ˚C3,0 `s1 ˚C3,1 `s2 ˚C3,2 `x3,0 ˚C3,3 `x3,1 ˚C3,4 `x3,2 ˚C3,5 x3,3 ˚C3,6
In this manner, each output share S i verifies uniformity and can equiprobably take 2 7 " 128 different values. With the codewords C i,j we choose, we obtain the following formulas for the output shares codewords S i : S 0 " ps 0 , s 1 ' x 0,0 , s 2 , s 0 ' x 0,1 , s 0 ' x 0,0 , x 0,2 ' x 0,0 , x 0,2 , s 1 , s 1 ' s 2 ' x 0,2 ' x 0,1 , s 2 , x 0,2 , s 1 ' x 0,1 , s 2 , s 1 , s 1 ' s 2 ' x 0,3 ' x 0,1 , s 2 , s 1 , s 1 ' s 2 ' x 0,2 , s 2 , x 0,3 , x 0,3 ' x 0,1 , x 0,2 , s 1 , s 2 , s 0 ' x 0,1 , s 0 , s 1 , s 2 ' x 0,1 , x 0,2 , s 0 , x 0,3 ' x 0,1 , s 0 ' x 0,0 , x 0,3 ' x 0,1 , s 0 , x 0,2 , x 0,2 ' x 0,0 , x 0,2 ' x 0,1 x 0,3 ' x 0,0 , s 0 ' x 0,0 , x 0,3 , s 0 ' x 0,0 , s 0 , x 0,3 , x 0,3 ' x 0,0 , x 0,3 ' x 0,0 q S 1 " ps 0 , s 1 , s

3 ' x 1,0 , s 0 , s 1 , s 1 , s 0 , x 1,3 ' x 1,1 , s 3 ' x 1,0 , s 3 ' x 1,1 , x 1,3 , x 1,3 ' x 1,0 , s 3 , x 1,3 ' x 1,1 , s 3 ' x 1,1 , s 3 ' s 0 ' x 1,1 ' x 1,1 , s 0 ' x 1,0 , s 3 ' x 1,1 ' x 1,3 , s 3 , x 1,3 , x 1,3 ' x 1,0 , s 0 , s 1 ' x 1,1 , s 3 ' x 1,1 ' x 1,0 , s 0 , s 0 , s 1 ' x 1,1 , s 3 ' s 0 ' x 1,1 , s 0 , s 1 , x 1,1 , s 1 ' x 1,1 , s 1 , x 1,1 , s 1 ' x 1,0 , x 1,1 , x 1,1 ' x 1,1 , s 1 , s 1 ' x 1,0 , x 1,1 , x 1,3 ' x 1,0 , x 1,1 ' x 1,0 , x 1,1 , x 1,3 , x 1,3 q S 2 " ps 3 , x 2,0 ' x 2,2 , s 3 , x 2,3 ' x 2,1 , x 2,0 ' x 2,1 , x 2,0 ' x 2,2 , s 2 , s 2 ' x 2,2 , s 2 ' x 2,2 , x 2,3 , s 0 , s 3 ' x 2,1 , s 3 ' s 0 ' x 2,3 , s 0 ' x 2,1 ' x 2,2 , s 3 , s 2 , s 0 ' x 2,1 ' x 2,2 , x 2,3 ' x 2,2 , s 2 , s 2 , s 2 ' x 2,1 , x 2,3 ' x 2,1 , s 3 , s 0 , x 2,3 , s 2 , s 2 , s 3 ' x 2,1 , s 2 , s 2 , s 0 , s 3 ' s 0 ' x 2,0 ' x 2,2 , s 0 ' x 2,1 , s 3 , s 3 ' x 2,2 , s 0 ' x 2,3 ' x 2,0 ' x 2,1 ' x 2,2 , s 0 , x 2,0 , x 2,0 , x 2,3 , x 2,0 , x 2,3 , x 2,3 , x 2,0 , x 2,0 q
11 Application to a Global Implementation

The AND masking scheme presented above requires that its input and output shares are represented by codewords. Therefore, to be able to apply it on a bitsliced implementation of any cryptographic primitive, the three other Boolean operations (OR, XOR and NOT) need to be addressed considering this requirement on the format of their inputs and outputs. First of all, the XOR operation is associative with regards to input sharings, hence the input shares of a XOR can be just XORed to one another to compute output shares. In our AND masking scheme set-up where each input is split into four shares such that HW pA 0 ' A 1 ' A 2 ' A 3 q mod 2 " a and HW pB 0 ' B 1 ' B 2 ' B 3 q mod 2 " b, the most straightforward manner to compute a ' b depending on codewords input shares A i and B i is the following :

• S 0 " A 0 ' B 0 • S 1 " A 1 ' B 1 • S 2 " A 2 ' B 2 • S 3 " A 3 ' B 3
Therefore, the sum of parities of output shares S i carries the correct value. Indeed, HW pS 0 ' S 1 ' S 2 ' S 3 q mod 2 " HW pA 0 ' B 0 q `HW pA 1 ' B 1 q `HW pA 2 ' B 2 q `HW pA 3 ' B 3 q mod 2 " HW pA

0 ' A 1 ' A 2 ' A 3 q `HW pB 0 ' B 1 ' B 2 ' B 3 q mod 2 " a ' b
As a result, this XOR implementation is compatible with the new masking scheme, since its input shares are codewords and its output shares S i are codewords as well, as sums of codewords.

Secondly, regarding the OR operation, it can be noticed that it can be written as a combination of an AND operation and three NOT operations. As a matter of fact, a _ b " p a ^ bq Therefore, the OR operation can be implemented using the AND masking scheme developed in this thesis and the NOT implementation described hereinbelow. Thus, the only bitwise operation left to be implemented to be able to apply our AND masking scheme to any cryptographic algorithm is the NOT operation, detailed in the following subsection.

Implementation of the NOT Operation

As we consider input and output shares of the AND operation to be codewords, input and output shares of the NOT operation need to be codewords as well to ensure compatibility. Hence, the NOT operation takes as input shares codewords A 0 , A 1 , A 2 and A 3 and returns codewords S 0 , S 1 , S 2 and S 3 such that HW pA 0 q `HW pA 1 q `HW pA 2 q `HW pA 3 q mod 2 " HW pS 0 q `HW pS 1 q HW pS 2 q `HW pS 3 q `1 mod 2. The basic idea of the implementation is to add random codewords to the three first input shares A 0 , A 1 and A 2 , then add to A 3 a codeword of parity opposite to the parity of the sum of the random codewords XORed to A 0 , A 1 and A 2 .

The major drawback to this solution lies in the fact that computing random codewords can rapidly become costly. This can be done either by computing random messages and multiplying them by the generator polynomial of the code gpXq, or by testing the residue of random arrays y P F 45 2 modulo gpXq until finding one verifying ypXq " 0 mod gpXq. Moreover, those operations would have to be performed using only bitwise operations as well, so that the implementation of the cryptographic primitive would be exclusively made up of bitwise operations.

To limitate this extra cost, we aim to re-use codewords already involved in our AND masking scheme : the masks ms 0 pXq, ms 1 pXq, ms 2 pXq and ms 3 pXq (listed in subsection 10.2). To that end, we pick random variables v i,j P F 2 for 0 ď i ď 2 and 0 ď j ď 3, and use them in the computation of output shares S 0 , S 1 , S 2 and S 3 such that :

• S 0 " A 0 ' pv 0,0 ˚ms 0 pXqq ' pv 0,1 ˚ms 1 pXqq ' pv 0,2 ˚ms 2 pXqq ' pv 0,3 ms 3 pXqq

• S 1 " A 1 ' pv 1,0 ˚ms 0 pXqq ' pv 1,1 ˚ms 1 pXqq ' pv 1,2 ˚ms 2 pXqq ' pv 1,3 ms 3 pXqq

• S 2 " A 2 ' pv 2,0 ˚ms 0 pXqq ' pv 2,1 ˚ms 1 pXqq ' pv 2,2 ˚ms 2 pXqq ' pv 2,3 ms 3 pXqq

• S 3 " A 3 ' ppv 0,0 ' v 1,0 ' v 2,0 q ˚ms 0 pXqq ' ppv 0,1 ' v 1,1 ' v 2,1 q ˚ms 1 pXqq ' ppv 0,2 ' v 1,2 ' v 2,2 q ˚ms 2 pXqq ' ppv 0,3 ' v 1,3 ' v 2,3 q ˚ms 3 pXqq ' gpXq

Thereby A 0 ' A 1 ' A 2 ' A 3 ' S 0 ' S 1 ' S 2 ' S 3 " gpXq.
As detailed in subsubsection 9.1.2, the BCH code generator polynomial gpXq has been chosen to have odd parity. Thus,

HW pS 0 ' S 1 ' S 2 ' S 3 q mod 2 " HW pA 0 ' A 1 ' A 2 ' A 3 q `1 mod 2.
In conclusion, this implementation effectively performs the NOT operation with regards to its input sharing.

Tests

We test the new masking scheme presented in this thesis on a AES implementation with a randomly-chosen fixed key using the TBoxes of [START_REF] Chow | White-box cryptography and an AES implementation[END_REF] bitsliced with the Usuba tool ( [START_REF] Mercadier | Usuba, Compilateur Bitslicing Optimisant)[END_REF]). This implementation is composed of 37586 AND gates, 2293 NOT gates and 66751 XOR gates and can be summarized as follows in algorithm 4 : Algorithm 4: TBoxed AES With Fixed Key Input : P, the 128-bit plaintext and RK the round keys Output: C, the 128-bit ciphertext 1 for r " 1 to 9 do 2 P Ð Shif tRowspP q 3 P Ð T r,0 rP 0 s...T r,15 rP 15 s 4 P Ð M ixColumnspP q 5 end for 6 C Ð T 10,0 rP 0 s...T 10,15 rP 15 s 7 return C

• For the 8-bit TBoxes of rounds 1 to 9 p1 ď r ď 9q, T r,i rxs " Srx ' Shif tRowspRK r´1 q i s • For the 8-bit TBoxes of round 10, T 10,i rxs " Srx ' Shif tRowspRK 9 q i s ' RK 10,i

• The AES ShiftRows transformation can be considered as a 128-bit bitwise permutation.

• The AES MixColumn transformation can also be be considered as a 128bit bitwise operation.

We test with a processor Intel(R) Core(TM) i7-6600U CPU @ 2.60GHz three different versions of this implementation :

• The raw bitsliced implementation where the TBoxes are bitsliced and the ShiftRows and MixColumn operations are implemented with Boolean operations AND, OR, NOT and XOR as well.

• The bitsliced implementation where the NOT operation is performed by flipping a bit share, the XOR operation is implemented by XORing shares and the AND operation is masked by the ISW masking scheme ([ISW03]), that is the most known and studied Boolean AND masking scheme but does not offer fault-attack resistance.

• The bitsliced implementation where the NOT operation is performed as described in subsection 11.1, the XOR operation is implemented by XORing polynomial shares and the AND operation is masked by the new masking scheme presented in this paper.

We obtain the following values: These results show that masking a bitsliced implementation entails an increase of the binary size and particularly of the execution time, even when using a classic and well-studied masking scheme as ISW. It can also be noticed that, thanks to the use in the implementation of macros that are inherited from the bitslicing by Usuba, the binary size of the implementation masked with the new scheme remains almost equal to the binary size of the implementation masked with ISW. Likewise, the execution time of the implementation masked with the new scheme only doubles compared to the execution time of the implementation masked with ISW, although the new scheme offers the additional property of fault correction compared to ISW.

Conclusion

The first purpose of this PhD study is to develop enhancements and new tools for the white-box cryptographic needs of the Kudelski Group. In this dissertation, we first describe the study of the white-boxability of the NIST Lightweight Cryptography Standardization Contest finalists. Indeed, lightweight cryptography primitives are now widely deployed on devices with constrained capacities that are vulnerable to white-box attackers. Therefore, we aim to determine the finalist submission of the contest that is the most suitable to a white-box implementation : GIFT-COFB, and more precisely GIFT, its cryptographic core block.

Many white-box implementations are based on bitsliced implementations composed themselves of Boolean operations, including some of the most resistant challenges submitted to white-box cryptography contests WhibOx 2017 and WhibOx 2019. Masking schemes being by nature countermeasures to sidechannel attacks, we then develop a new masking scheme composed of Boolean operations that is resistant to fault attacks. More precisely, this scheme can be applied on implementations of any primitive, and corrects potential faults without deteriorating or aborting the computation. These implementations will then always return results, results that are correct even if a fault has been introduced during computation. This constitutes a huge practical benefit in the field of fault-resistant masking schemes.

To that end, we use BCH error-correcting codes as BCH decoding can be performed with only Boolean operations as well. The design rationale behind the masking scheme together with the description of the scheme are detailed in the second part of the dissertation. Finally, the masking scheme is applied to a bitsliced implementation of AES and compared to the raw bitsliced implementation and the implementation using the masking scheme ISW.

Directions for Future Research

The different considerations for further research that this dissertation has led us to are the following :

Investigate the Possibility of Using Other Error-Correcting Codes

The error-correcting code used in the design of the masking scheme presented in this dissertation is the BCH error-correcting code, chosen for its easy management of codewords parity because of its cyclicity and for its decoding process that can be implemented using Boolean operations. Nevertheless, using such type error-correcting code while complying with the properties needed for the scheme imply a BCH error-correcting code of rather high length, here chosen to be 45.

It would be relevant to investigate if other types of error-correcting codes would be suitable to comply with the properties needed while using a smaller code length.

Experimentally and Theoretically Prove the Side-Channel Security of the Masking Scheme

The uniformity, non-completeness and correctness properties ensure the firstorder probing security of the masking scheme, so we would need further analysis to determine the exact probing security order of the scheme.

In the same way, it would be relevant to experimentally confirm the sidechannel resistance of an implementation of a cryptographic primitive using the presented AND masking scheme.

Balance Between Performance and Correction Efficiency

It can easily be noticed that the correction design is the most costly part of the masking schemes, whether in performances or memory. Therefore, we can ask ourselves if, throughout a whole bitsliced implementation, it is possible to remove the correction part at the beginning of some of the instances of the AND masking scheme to improve performances, while not impacting too much the fault correction capacity of this implementation.

Likewise, there exists distinct input bits values px p0,1q 1 , x p0,1q 0 q, px p1,0q 1 , x p1,0q 0 q, px p1,1q 1 , x p1,1q 0 q P F 2 2 such that G ´1 r´1,0 px py1,y0q 1

x py1,y0q 0 q " y 1 y 0 for all py 1 , y 0 q P F 2 2 . Therefore, the computations of T 0 r00 11 01 x t pt 1 7 t 1 6 t 1 5 t 1 4 t 1 3 t 1 2 t 1 1 t 1 0 q, pt 2 7 t 2 6 t 2 5 t 2 4 t 2 3 t 2 2 t 2 1 t 2 0 q, pt 3 7 t 3 6 t 3 5 t 3 4 t 3 3 t 3 2 t 3 1 t 3 0 q, pt 4 7 t 4 6 t 4 5 t 4 4 t 4 3 t 4 2 t 4 1 t 4 0 qu " tpG r,3 ppz 7 'cqz 6 qG r,2 ppz 5 'k 1 qz 4 qG r,1 ppz 3 'k 0 qz 2 qG r,0 pz 1 z 0 qq, pG r,3 ppz 7 'cqz 1 6 qG r,2 ppz 5 'k 1 qz 1 4 qG r,1 ppz 3 'k 0 qz 2 qG r,0 pz 1 z 1 0 qq, pG r,3 ppz 1 7 'cqz 6 qG r,2 ppz 1 5 'k 1 qz 4 qG r,1 ppz 1 3 'k 0 qz 2 qG r,0 pz 1 1 z 0 qq, pG r,3 ppz 1 7 'cqz 1 6 qG r,2 ppz 1 5 'k 1 qz 1 4 qG r,1 ppz 1 3 'k 0 qz 2 qG r,0 pz 1 1 z 1 0 qqu " t T 0 r00 11 01 x Then, GSry 7 0y 3 y 1 s " z 7 z 5 z 3 z 1 and GSry 7 0y 3 y 1 s " z 1 7 z 1 5 z 3 z 1 , which implies py 7 , y 3 , y 1 q " p0, 0, 1q, p0, 1, 1q, p1, 0, 1q or p1, 1, 1q. Therefore y 1 " 1, i.e. G ´1 r´1,0 p10q " 1 .

As a conclusion, all left bits of the four input encodings can be recovered by applying the same method with different input bits. Therefore, in the current exemple, the attacker can recover the following left bits of the four input encodings G ´1 r´1,15 , G ´1 r´1,10 , G ´1 r´1,5 and G ´1 r´1,0 :

G ´1

A.2 Second and Final Steps of the Attack

We now demonstrate how to deduce the two key bits of a TBox knowing the left half of the inverse of its output encodings. To that end, we still consider the TBox T 0 with the same notations, and suppose that T 0 does not belong to the last round of GIFT. We assume that, thanks to the procedure above, the attacker knows that the input encodings verify Likewise, we suppose that the attacker knows the left halves of G ´1 r,2 and G ´1 r,1 , the inverses of the middle output encodings G r,2 and G r,1 of T 0 . They are obtained by applying the same procedure to the corresponding TBoxes of round r `1 that admit G ´1 r,2 and G ´1 r,1 as input encodings, and they provide information on the output encodings of T 0 themselves : Finally, this knowledge on the input and output encodings is sufficient to conclude the attack. Indeed, it can be used to determine with certainty some of the intermediate values of the computation of T 0 for any randomly chosen input. For example, the computation of T 0 r00 00 00 00s presents the following intermediate values : Abstract: White-box cryptography is dedicated to the implementations of cryptographic primitives that are secure against an attacker being in total control of the devices they are deployed on. One of the main security challenges it needs to address is side-channel security. To that end, designers aim to eliminate the dependence between variables and sensitive data. Classical countermeasures to do so are masking schemes. However, implementations using masking schemes are still vulnerable to fault attacks.

G ´1
Moreover, the classical cryptographic compromise between security, costs and performances remains in white-box cryptogra-phy. Lightweight cryptography is the field of cryptography designed for devices with constrained capacities, therefore the question of the white-boxability of lightweight cryptographic algorithms arises as well.

In the first part of the thesis, we discuss the suitability of the finalists of the NIST Lightweight Cryptography Standardization Contest to white-boxing. We then develop a white-box implementation of GIFT. In the second part of the thesis, we describe a new construction of a bitwise AND masking scheme correcting faults using BCH error-correcting codes and only composed of Boolean operations on bits.

Definition 5 .

 5 Let A be a finite alphabet and n P N ‹ . An error-correcting code over A of length n is a non-empty set of A n . Definition 6 (Minimal Distance). Let C be an error-correcting code of length n. The minimal Hamming distance d of C verify d " min x,yPC d HW px, yq Definition 7 (Correction Capacity). Let C be an error-correcting code of length n and minimal Hamming distance d. The correction capacity t of the code C verifies t " t d ´1 2 u.

•

  SubCells applies the 4-bit GIFT SBox GS to all 4-bit nibbles of the 128 bit state.

Figure 1 :

 1 Figure 1: T 0 , the right-most TBox of round r

Figure 2 :

 2 Figure 2: Intermediate notations of T 0 , the right-most TBox of round r

Figure 3 :

 3 Figure 3: Example of intermediate values of T 0

Figure 4 :

 4 Figure 4: Second example of intermediate values of T 0

s

  present the respective following intermediate values :• For T 0 r00 11 01 xWe can subsequently compute the values of T = t T 0 r00 11 x t T 0 r00 11 01 00s, T 0 r00 11 01 01s, T 0 r00 11 01 10s, T 0 r00 11 01 11s u. As a result, t p00 01 00 11q, p10 01 10 11q, p01 01 11 11q, p11 01 01 11q u "

T 0

 0 r00 11 01 01s, T 0 r00 11 01 10s, T 0 r00 11 01 11su

Titre:

  Masquage Booléen Résistant aux Attaques par Fautes et White-Boxabilité de Primitives Cryptographiques Légères Mot clés : Cryptographie White-Box, Masquage Résistant aux Fautes, Cryptographie Légère Résumé : La cryptographie white-box est dédiée aux implémentations sûres face à un attaquant ayant le contrôle total des dispositifs sur lesquels elles sont déployées. Un des enjeux majeurs auquel elle doit répondre est la résistance aux attaques side-channel. A cette fin, les concepteurs d'implémentations white-box ont pour but d'atténuer au maximum toute dépendance entre les variables de l'implémentation et ses données sensibles. Pour cela, l'une des contre-mesures classiques est l'utilisation de schémas de masquage, néanmoins vulnérables aux attaques par fautes. La cryptographie white-box doit aussi considérer le compromis coûts-performances de ses implémentations : la question de la « white-boxabilité » des primitives légères, adaptées aux dispositifs aux capacités limitées se pose donc. Dans cette thèse, nous discutons tout d'abord de la white-boxabilité des finalistes du processus de standardisation de primitives légères du NIST, et présentons une implémentation white-box de GIFT. Dans la seconde partie, nous décrivons notre schéma de masquage de l'opération AND résistant à l'introduction de fautes grâce à l'usage de codes correcteurs BCH et pouvant être implémenté avec uniquement des opérations bit-à-bit. Title: Boolean Fault-Resistant Masking and White-Boxability of Lightweight Cryptography Keywords: White-Box Cryptography, Fault-Resistant Masking, Lightweight Cryptography

  I White-Boxing and NIST Lightweight Standardization Finalists 6 Study of the White-Boxability of NIST Lightweight Finalists 6.1 Overview of NIST Lightweight Cryptography Standardization Contest . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 A First Selection on the Ten NIST Lightweight Candidates . . . 9.1.1 Non-Completeness Implies a Condition on the Number of Shares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.1.2 Parity Requirement on the BCH Code Generator Polynomial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.1.3 Maximizing the BCH Code Dimension . . . . . . . . . . . 9.1.4 Randomness Requirement and its Impact on the BCH Code Choice . . . . . . . . . . . . . . . . . . . . . . . . . 9.1.5 Ensuring Uniformity and Correctness . . . . . . . . . . . 9.2 Input Shares Correction . . . . . . . . . . . . . . . . . . . . . . . 9.2.1 Fault Attack Model . . . . . . . . . . . . . . . . . . . . . 9.2.2 Input Shares Correction Design . . . . . . . . . . . . . . . 9.2.3 The Correction Design Preserves Non-Completeness . . . 9.2.4 One-bit Fault on One Input Share . . . . . . . . . . . . . 9.2.5 One-bit Faults on Two Input Shares . . . . . . . . . . . .

10 A New Fault Resistant Masking Scheme 10.1 Input Shares Correction . . . . . . . . . . . . . . . . . . . . . . . 10.2 Array of Subproducts . . . . . . . . . . . . . . . . . . . . . . . . 10.3 Output Shares Computation . . . . . . . . . . . . . . . . . . . . . 11 Application to a Global Implementation 11.1 Implementation of the NOT Operation . . . . . . . . . . . . . . . 11.2 Tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Conclusion A Attack Numerical Example A.1 First Step of the Attack . . . . . . . . . . . . . . . . . . . . . . . A.2 Second and Final Steps of the Attack . . . . . . . . . . . . . . . .

  table of the Difference Distribution Table DDT composed of coefficients DDT pδ i , δ o q such that the input and output differences δ i P F m 2 and δ o P F n

		2	ˆFn 2
	In particular, Banik et. al.	introduce in [BPP `17b] the 1-1 DDT, i.e.
	the sub-2
	have both Hamming weight one.
	Definition 2 (from [BPP `17b]).

  test the uniformity and non-completeness properties on four different examples of such masking schemes : ISW ([ISW03]) and the three different multiplication gadgets presented in[START_REF] Goudarzi | Secure multiplication for bitslice higherorder masking: Optimisation and comparison[END_REF], namely the BDF+ algorithm of [BDF `17], the BBP+ algorithm of [BBP `16] and the BCPZ algorithm of[START_REF] Battistello | Horizontal side-channel attacks and countermeasures on the ISW masking scheme[END_REF]. The results are presented in Table1.

			ISW			BDF+			BBP+			BCPZ
	Number of shares d	2	4	8	2	4	8	2	4	8	2	4	8
	Uniformity

Table 1 :

 1 Properties of ISW, BDF+, BBP+ and BCPZ gadgets

	Probing Security Order	1	3	7	1	3	7	1	1	3	1	3	7
	Clock cycles	75 291 1155		77 146		344 1204 108 498 2106
	Code Size (Bytes) 164 164 164		248 244		344 344 240 648 2324
	Random Variables	1	6	28	1	1	2	1	5	19	1	10	68

  BO D ùñ π D pxq P GI D x P BO L ùñ π L pxq P GI L

	These permutations verify
	π 1 : 0001 Ñ 0100	π 2 : 0001 Ñ 0100
	0010 Ñ 0001	0010 Ñ 1000
	0100 Ñ 1000	0100 Ñ 0001
	1000 Ñ 0010	1000 Ñ 0010

• There exists two BOGI permutations that are common to differential and linear case, i.e. permutations π i : t0001, 0010, 0100, 1000u Ñ t0001, 0010, 0100, 1000u such that # x P

Table 4 :

 4 hereunder, together with the corresponding maximum BCH code dimension. Maximum code dimension depending on code length, with generator polynomial gpXq of adequate form, for a number of shares n in " 3

	Code Length n	9 11 13 15 17 19 21 23 25
	Minimal Generator Polynomial Degree	8 10 12	8	16 18	9	11 20
	Corresponding Maximum Code Dimension	1	1	1	7	1	1	12 12	5

Table 5 :

 5 . In this case, the cardinality of the code equals to 2 29 . Maximum code dimension depending on code length, with generator polynomial gpXq of adequate form, for a number of shares n in " 4

	Code Length n	17 19 21 23 25 27 29 31 33
	Minimal Generator Polynomial Degree	16 18	9	11 20 20 28 10 20
	Corresponding Maximum Code Dimension	1	1	12 12	5	7	1	21 13
	Code Length n	35 37 39 41 43 45 47 49
	Minimal Generator Polynomial Degree	15 36 24 20 28 16 23 42
	Corresponding Maximum Code Dimension	20	1		15 21 15 29 24	7

Pour la conception de ce nouveau schéma de masquage, nous nous plaçons dans le modèle d'attaque one-bit flipping fault, c'est-à-dire que nous considérons qu'un attaquant est capable d'aléatoirement remplacer la valeur d'un bit par son opposée dans l'implémentation. En effet, c'est un modèle d'attaque par faute susceptible d'être utilisé par un attaquant contre une implémentation bitslicée. Nous construisons ce schéma pour qu'il puisse résister à l'introduction d'au plus deux telles fautes dans ses shares d'entrée.Pour pouvoir corriger d'éventuelles fautes dans chaque share d'entrée, corriger chaque share individuellement nécessiterait 8 corrections. Afin d'éviter autant de corrections et donc d'améliorer les performances du schéma, nous construisons des sous-sommes de shares d'entrée. Nous montrons que le nombre minimum de sous-sommes à construire pour qu'une faute détectée par la correction d'une sous-somme soit attribuée à la correcte entrée tout en conservant la propriété de non-completeness est 3.Nous effectuons par la suite diverses multiplications entre les parités des shares en entrée, et avec les parités des polynômes aléatoirement choisis. Ces valeurs sont rassemblées dans une matrice sur laquelle sont appliqués différents masques, eux-mêmes mots du code, dans le but de calculer les parités des shares de sortie. Pour assurer la pérennité du schéma dans le cas d'exécutions successives dans l'implémentation d'une primitive cryptographique et assurer que les shares en sortie n'ont pas subi de faute, nous construisons ces shares comme étant des mots du code BCH utilisé. Enfin, afin de respecter la propriété d'uniformity, ces shares sont construits de manière équiprobable.

$ ' ' ' ' & ' ' ' ' % G ´1 r,3 pt 7 t 6 q " pz 7 ' cq G ´1 r,2 pt 5 t 4 q " pz 5 ' k 1 q G ´1 r,1 pt 3 t 2 q " pz 3 ' k 0 q G ´1 r,0 pt 1 t 0 q " z 1 , i.e.

$ ' ' ' &

' ' ' % G r,3 ppz 7 ' cq q " t 7 t 6 G r,2 ppz 5 ' k 1 q q " t 5 t 4 G r,1 ppz 3 ' k 0 q q " t 3 t 2 G r,0 pz 1 q " t 1 t 0 Hence, GS out * " ppz 7 'cqpz 5 'k 1 qpz 3 'k 0 qz 1 q is also known. In conclusion, for any TBox input T Box in " px 7 , x 6 , x 5 , x 4 , x 3 , x 2 , x 1 , x 0 q P F 6 2 we can determine both GS out " pz 7 z 5 z 3 z 1 q and GS out * " ppz 7 ' cqpz 5 ' k 1 qpz 3 ' k 0 qz 1 q. Thus, the value of key bits pk 1 , k 0 q can be deduced from the values of pz 5 ' k 1 q, pz 3 ' k 0 q, z 5 and z 3 .

A numerical example of the major steps of the attack can be found in Appendix A.

Intern SBox ILUT and Differential Properties

Using a Linear Intern SBox ILUT Leads to its Recovery

In this subsection we suppose that we use in the TBox T 0 an intern linear SBox ILU T . Thus, as an example, when noting pv 6 , v 4 , v 2 , v 0 q " ILU T r0001s then for all pa, b, c, dq P F 4 2 verifying ILU T rabcds " ef gh P F 4 2 , ILU T rabcds " ILU T rabcds ' ILU T r0001s " ef gh ' v 6 v 4 v 2 v 0 .

Subsequently, let px 7 , x 6 , x 5 , x 4 , x 3 , x 2 q P F 6 2 . We note $ ' & ' % G ´1 r´1,15 px 7 x 6 q " y 7 y 6 G ´1 r´1,10 px 5 x 4 q " y 5 y 4 G ´1 r´1,5 px 3 x 2 q " y 3 y 2

We then compute successively T 0 rx 7 x 6 x 5 x 4 x 3 x 2 00s, T 0 rx 7 x 6 x 5 x 4 x 3 x 2 01s, T 0 rx 7 x 6 x 5 x 4 x 3 x 2 10s and T 0 rx 7 x 6 x 5 x 4 x 3 x 2 11s. As detailed above in the general case of the attack, this implies that among these four computations the output bits py 1 , y 0 q P F 2 2 of the right-most input encoding G ´1 r´1,0 take alternatively (but not necessarily respectively) the four values 00, 01, 10 and 11 of F 2 2 . Therefore, the inputs and outputs of the GIFT SBox GS and the intern SBox ILU T are :

• When G ´1 r´1,0 px 1 x 0 q " 00, pz 7 z 5 z 3 z 1 q " GSry 7 y 5 y 3 0s and pz 6 z 4 z 2 z 0 q " ILU T ry 6 y 4 y 2 0s Therefore, if there exists px 7 , x 6 , x 4 , x 3 , x 2 q P F 6 2 such that the left-most 2-bit output block G r,3 pz 7 z 6 q takes the same value in F 2 2 for the four computations of T 0 rx 7 x 6 x 5 x 4 x 3 x 2 00s, T 0 rx 7 x 6 x 5 x 4 x 3 x 2 01s, T 0 rx 7 x 6 x 5 x 4 x 3 x 2 10s and T 0 rx 7 x 6 x 5 x 4 x 3 x 2 11s, then v 6 " 0. Likewise, if this 2-bit output block takes four different values, then v 6 " 1. Thus, as v 6 is known to the attacker, he can for a given px 7 , x 6 , x 5 , x 4 , x 3 , x 2 q P F 6 2 determine whether z 1 7 " z 7 or z 1 7 " z 7 , i.e., for y 7 y 6 " G ´1 r´1,15 px 7 x 6 q, y 5 y 4 " G ´1 r´1,10 px 5 x 4 q, y 3 y 2 " G ´1 r´1,5 px 3 x 2 q and GSry 7 y 5 y 3 0s " z 7 z 5 z 3 z 1 , whether

In the same manner, v 4 can be recovered considering the set of values of the second left-most 2-bit output block tG r,2 ppz 5 ' k 0 qz 4 q, G r,2 ppz 5 ' k 0 qpz 4 ' v 4 qq, G r,2 ppz 1 5 ' k 0 qz 4 q, G r,2 ppz 1 5 ' k 0 qpz 4 ' v 4 qqu. This can be applied to the recovery of v 4 , v 2 and v 0 such that it is possible for an attacker to determine

Likewise, it is possible for an attacker to determine the values of ILU T r0010s, ILU T r0100s and ILU T r1000s, and subsequently all values of ILU T , as for all py 6 , y 4 , y 2 , y 0 q P F 4 2 , ILU T ry 6 y 4 y 2 y 0 s " py 6 ˚ILU T r1000sq' py 4 ˚ILU T r0100sq' py 2 ˚ILU T r0010sq ' py 0 ˚ILU T r0001sq.

The Knowledge of the Intern SBox ILUT Simplies the 2-Round Differential Attack

We demonstrate that the knowledge of the intern SBox ILU T simplifies the recovery of the left bit of the input encodings of the TBox T 0 . For that purpose, we still suppose px 7 , x 6 , x 5 , x 4 , x 3 , x 2 q P F 6 2 with G ´1 r´1,3 px 7 x 6 q " y 7 y 6 , G ´1 r´1,2 px 5 x 4 q " y 5 y 4 and G ´1 r´1,1 px 3 x 2 q " y 3 y 2 , and more broadly retain the notations developed in subsubsection 8.2.1.

In the generic setting of the attack described in subsection 8.2, when computing T 0 rx 7 x 6 x 5 x 4 x 3 x 2 00s, T 0 rx 7 x 6 x 5 x 4 x 3 x 2 01s, T 0 rx 7 x 6 x 5 x 4 x 3 x 2 10s and T 0 rx 7 x 6 x 5 x 4 x 3 x 2 11s, the different input arrays of output encodings Encod in are noted :

• ppz 7 ' cqz 6 pz 5 ' k 1 qz 4 pz 3 ' k 0 qz 2 z 1 z 0 q for py 1 , y 0 q " p0, 0q

for py 1 , y 0 q " p1, 1q with # GSry 7 y 5 y 3 0s " z 7 z 5 z 3 z 1 GSry 7 y 5 y 3 1s " z 1 7 z 1 5 z 1 3 z 1 1 and # ILU T ry 6 y 4 y 2 0s " z 6 z 4 z 2 z 0 ILU T ry 6 y 4 y 2 1s " z 1 6 z 1 4 z 1 2 z 1 0 Thus, regarding the value of the first 2-bit output block in the four computations,

• If #tG ´1 r´1,3 ppz 7 ' cqz 6 q, G ´1 r´1,3 ppz 7 ' cqz 1 6 q, G ´1 r´1,3 ppz 1 7 ' cqz 6 q, G ´1 r´1,3 pz 1 7 ' cqz 1 6 u " 4, then #tpz 7 'cqz 6 , pz 7 'cqz 1 6 , pz 1 7 'cqz 6 , pz 'cqz 1 6 u " 4, thus z 1 7 " z 7 and z 1 6 " z 6 .

• If #tG ´1 r´1,3 ppz 7 ' cqz 6 q, G ´1 r´1,3 ppz 7 ' cqz 1 6 q, G ´1 r´1,3 ppz 1 7 ' cqz 6 q, G ´1 r´1,3 pz 1 7 ' cqz 1 6 u " 1, then #tpz 7 'cqz 6 , pz 7 'cqz 1 6 , pz 1 7 'cqz 6 , pz 'cqz 1 6 u " 1, thus z 1 7 " z 7 and z 1 6 " z 6 .

• If #tG ´1 r´1,3 ppz 7 ' cqz 6 q, G ´1 r´1,3 ppz 7 ' cqz 1 6 q, G ´1 r´1,3 ppz 1 7 ' cqz 6 q, G ´1 r´1,3 pz 1 7 ' cqz 1 6 u " 2, it cannot be determined whether z 1 7 " z 7 and z 1

6 " z 6 or z 1 7 " z 7 and z 1 6 " z 6 .

Thus, the different input arrays of output encodings Encod in can be written as :

• ppz 7 ' cqz 6 pz 5 ' k 1 qz 4 pz 3 ' k 0 qz 2 z 1 z 0 q for py 1 , y 0 q " p0, 0q

• ppz 7 ' cqpz 6 ' v 6 q pz 5 ' k 1 qpz 4 ' v 4 q pz 3 ' k 0 qpz 2 ' v 2 q z 1 pz 0 ' v 0 qq for py 1 , y 0 q " p0, 1q

• ppz 1 7 ' cqz 6 pz 1 5 ' k 1 qz 4 pz 1 3 ' k 0 qz 2 z 1 1 z 0 q for py 1 , y 0 q " p1, 0q

• ppz 1 7 ' cqpz 6 ' v 6 q pz 1 5 ' k 1 qpz 4 ' v 4 q pz 1 3 ' k 0 qpz 2 ' v 2 q z 1 1 pz 0 ' v 0 qq for py 1 , y 0 q " p1, 1q

As a result, the third case where #tG ´1 r´1,3 ppz 7 ' cqz 6 q, G ´1 r´1,3 ppz 7 ' cqz 1 6 q, G ´1 r´1,3 ppz 1 7 ' cqz 6 q, G ´1 r´1,3 pz 1 7 ' cqz 1 6 u " 2 can be rewritten as #tG ´1 r´1,3 ppz 7 ' cqz 6 q, G ´1 r´1,3 ppz 7 ' cqpz 6 ' v 6 qq, G ´1 r´1,3 ppz 1 7 ' cqz 6 q, G ´1 r´1,3 ppz 1 7 ' cqpz 6 ' v 6 qqu " 2. As v 6 is known, it can be deduced whether z 1 7 " z 7 or z 1 7 " z 7 . At this point, the left bits of the input encodings of the TBox T 0 can be recovered by the 2-round attack detailed in subsection 8.2.

Nevertheless, we prove hereinbelow that the knowledge of the intern SBox ILU T of the TBox T 0 (whether being deduced thanks to its linearity or not) does not enable an attacker to recover the key bits by a differential attack on T 0 only.

The Knowledge of the Intern SBox Does Not Lead to a Differential Attack on the TBox Itself

In this section, we suppose that in the set-up stated in subsection 8.2 the intern SBox ILU T is known to the attacker. Therefore, the left bits of the input encodings of T 0 can be recovered as detailed in subsubsection 8.3.2.

Knowledge on the input left bits of output encodings of T 0 is essential for an attacker to determine with certainty its key bits, even if he has entirely broken the input encodings beforehand. Indeed, if we suppose that the attacker has effectively broken those input encodings, then when fixing the input of three 2-bit input blocks and computing the outputs of T 0 when varying the fourth 2-bit input block, he could effectively deduce the outputs of the GIFT SBox GS and the intern SBox ILU T .

Nevertheless, the key bits to be determined are added afterwards to the GS output bits. Given the four computed outputs of T 0 , there exists for every possible key bits pk 0 , k 1 q P F 2 2 potential corresponding outputs encodings G r,3 , G r,2 , G r,1 and G r,0 .

For example, we suppose px 5 , x 4 , x 3 , x 2 , x 1 , x 0 q P F 6 2 . As mentioned above, by hypothesis we assume that the attacker has entirely broken the input encodings (whether by brute force or not). Thus, the attacker knows the input encodings output values G ´1 r´1,10 px 5 x 4 q " y 5 y 4 , G ´1 r´1,5 px 3 x 2 q " y 3 y 2 and G ´1 r´1,0 px 1 x 0 q " y 1 y 0 . Throughout the four computations of T 0 r00x 5 x 4 x 3 x 2 x 1 x 0 s, T 0 r01x 5 x 4 x 3 x 2 x 1 x 0 s, T 0 r10x 5 x 4 x 3 x 2 x 1 x 0 s and T 0 r11x 5 x 4 x 3 x 2 x 1 x 0 s, the inputs and outputs of the GIFT SBox GS and the inputs and outputs of the intern SBox ILU T are (not necessarily respectively)

As by hypothesis the values of SBoxes GS and ILU T are known to the attacker, he can compute those four different values GSr0y 5 y 3 y 1 s, GSr1y 5 y 3 y 1 s, ILU T r0y 4 y 2 y 0 s and ILU T r1y 4 y 2 y 0 s. The output arrays of output encodings corresponding to those pairs of GS and ILU T outputs will then respectively be noted

The output bits values z i and z 1 i , the round constant bit c value as well as the outputs of the TBox output encodings T 0 r00x 5 x 4 x 3 x 2 x 1 x 0 s, T 0 r01x 5 x 4 x 3 x 2 x 1 x 0 s, T 0 r10x 5 x 4 x 3 x 2 x 1 x 0 s and T 0 r11x 5 x 4 x 3 x 2 x 1 x 0 s are known to the attacker, the key bits k 0 and k 1 are not. Even with this knowledge, the attacker does not have enough information on the output encodings to determine with certainty the key bits.

ñ HW p∆xq `HW p∆yq ě 4 Moreover, GS 1 complies with the differential attack property (i.e. Property 14) as for all py 7 , y 5 , y 3 , y 1 q P F 4 2 , GS 1 ry 7 y 5 y 3 y 1 s " GS 1 ry 7 y 5 y 3 y 1 s ' p1, 0, 0, 0q.

Nevertheless, this SBox has an implementation cost of 20 units. Indeed, its bitsliced implementation (detailed in algorithm 3) consists of 6 XOR, 3 NOT, 2 NAND, 1 NXOR and 1 NOR, with respective costs of two, one, one, two and one unit.

We note nevertheless that the instructions of this bitsliced implementation do not comply with the types recommended in [BPP `17b], designed for the ease of the implementation of the SBox inverse.

Part II

A New Fault Resistant Masking Scheme

As mentioned above, all random polynomials R i are independent from each other by design. Likewise, they are independent from shares A i , and shares A i are also independent from shares B i , therefore so are their respective parities a i , b i and r i . Hence all variables a i , r 0 , r 1 and r 2 are independent from sub-sums V B j , and any sub-sum S of variables a i , r 0 , r 1 and r 2 verifies PpS " 0q " PpS " 1q " 1 2 . Furthermore, for x = 0, 1 or 2, we note v x " r x and for x = υ, δ or ξ we note v x " a x . Then, in the same manner that PpS " 0q " PpS " 1q " 1 2 , each product

4 . Moreover, we suppose that there exists tx 0 , . . . ,

Consequently, the sum s can be rewritten in the form of

• V A i being either v x P ta υ , a δ , a ξ , r 0 , r 1 , r 2 u or a sub-sum of variables in ta υ , a δ , a ξ , r 0 , r 1 , r 2 u.

• each v x appearing only once among all the V A i Therefore, all the sums V A i and V B i are independent from one another and equiprobable in F 2 . Based on Property 1, this implies that

Furthermore, if we suppose s being equiprobable, then Pps " 0q " 1 2 . It thus implies that 10 2 Ω`2 ´1 2 Ω´1 `1 2 " 1 2 , then 10 2 Ω`2 ´1 2 Ω´1 " 0 ðñ 10 2 Ω`2 " 1 2 Ω´1 ðñ 10 " 8, hence the contradiction. Consequently, a sum s " a j0 b k0 ' . . .' a jΘ´1 b kΘ´1 ' a l0 r m0 ' . . . ' a lΛ´1 r mΛ´1 ' r n0 b o0 ' . . . ' r nχ´1 b oχ´1 ' r p0 r q0 ' . . . ' r p ψ´1 r q ψ´1 " V A 0 V B 0 '. . .'V A Ω´1 V B Ω´1 of elements of set P cannot be equiprobable.

In the case when no fault has been committed, all sub-sums V i are then naturally not faulted. Therefore, by definition of sub-sums V 1 i , it implies that V 1 i " V i for i " 0, 1, 2 and 3. In this manner, the modified input shares A 1 i and B 1 i stay coherent with the original input shares of the scheme, given that

The Correction Design Preserves Non-Completeness

In this subsection we verify that the correction design detailed above comply with non-completeness. First of all, we assume that no fault is committed. In this case, by definition, all sub-sums V i and corresponding corrected values

Secondly, we notice that, in the case where a fault is committed, it does not change the involvment (or not) of shares A i and B i in the computations of modified input shares A 1 i and B 1 i . As a result, those modified input shares A 1 i and B 1 i verify non-completeness with regards to the original input shares A i and B i .

One-bit Fault on One Input Share

Sub-sums V 0 and V 1 are designed to cover all possible locations for input shares faults, whereas, in case of a fault detected by one of those two sub-sums, V 2 is designed to determine whether this fault has initially been committed on a share A i of A or on a share B i of B.

In this section, we detail the impact on the parities of all modified input shares A 1 i and B 1 i of a one-bit fault on one input share A i or B i . With this aim in mind, from now onwards, we note a i and b i the parities of respective non-faulted input shares A i and B i . For example, if a fault is committed on A 2 , it implies that • HW pA 2 q mod 2 " a 2 ' 1

• HW pA i q mod 2 " a i for i P t0, 1, 3u

A 2 is involved in the computations of sub-sums V 1 and V 2 , but not in the computation of V 0 . Therefore, commit one fault on A 2 impacts the sub-sums V 1 and V 2 , but not V 0 . Consequently, the parities of the three sub-sums V 0 , V 1 and V 2 in this case are :

• HW pV 0 q mod 2 " HW pV 1 0 q mod 2 " a 0 ' a 1 ' b 0 ' b 1

• HW pV 1 q mod 2 " HW pV 1 1 q mod 2 ' 1 " a 2 ' a 3 ' b 2 ' b 3 ' 1

• HW pV 2 q mod 2 " HW pV 1 2 q mod 2 ' 1 " a 2 ' a 3 ' b 0 ' b 1 ' 1 Consequently, it implies that the sums of the parities of modified shares A 1 i and B 1 i are respectively equal to the sums of the parities of non-faulted shares B i and A i . As a matter of fact,

Therefore, we can observe in Table 7 that the parity of V

e. the sum of sub-sums and corrected sub-sums added to shares A i ) behaves such that, regardless of the position of the one-bit fault, HW pA 1

Likewise, the parity of the sum of sub-sums and corrected sub-sums added to shares

3 q mod 2 " a 0 ' a 1 ' a 2 ' a 3 . On an input share scale, Table 8 represents the correctness of parities of the modified input shares A 1 i and B 1 i (obtained after the XOR of variables V i and V 1 i to the initial input shares A i and B i ). In other words, this table indicates if, after the XOR of sub-sums V i and of the results of their respective corrections V 1 i , each modified input share A 1 i or B 1 i carries the same parity as would have carried the corresponding input share

Table 8: Correctness of the parity of input shares A 1 i and B 1 i after the XOR of variables V i and V 1 i in a single fault location case Moreover, we can notice that modified input shares

and B 1 3 are not necessarily codewords in the case where a fault has been detected. At this point, the only requirement for the correctness of the following steps of the masking scheme is that the parities of

Furthermore, on a wider scope, when applied on a bitsliced implementation of a cryptographic primitive this design does not correct the original faulted input share(s) A i or B i . This can be acceptable if the number of AND instances in the implementation is low, or if only very few faults are introduced in the overall implementation as these faults would be corrected at the beginning of each instance that involves the corresponding faulted share. Otherwise, there will rapidly exist instances of the masking scheme whose inputs would hold more faults that the correction design is able to handle.

To avoid this issue, all input shares A i or B i can be replaced at the end of the scheme by codewords of respective parities the parities of B 1 i and A 1 i (i.e. b i or a i ). Indeed, as precedently detailed, HW pA 1

These observations still stand in the case detailed in the subsubsection hereinafter, where two one-bit faults are committed on two different input shares.

One-bit Faults on Two Input Shares

We now consider the case where two one-bit faults are committed on two different input shares among the eight shares A i and B i . Table 9 represents the impact on the correctness of sub-sums V 0 , V 1 and V 2 of committing a one-bit fault on each share of each couple of two different input shares among A 0 , A 2 , B 0 and B 2 .

Table 9: Correctness of the parity of variables V i , depending on locations of two one-bit faults on two input shares For example, commit a one-bit fault on both input shares A 2 and B 2 will impact both sub-sums

Accordingly, in spite of these two faults, the parities of

the parities of non-faulted inputs B and A.

Subsequently, in the case where the two faults are committed on shares of the same input (i.e. on A 0 and A 2 or on B 0 and B 2 ), the impacts of these faults will naturally cancel themselves regarding the parity of the sum of the modified shares of this input. Consequently, the parity of the sum of the modified shares of each input will be correct even without correction. Nevertheless, it can be noted that the correction process still keeps the correctness of the parities of the sums of shares of each input. Indeed, if faults are committed for example on A 0 and A 2 , it impacts V 0 , V 1 and V 2 . Therefore, in this case the parities of respective sums of modified shares A 1 i and B 1 i verify

Similarly as for Table 8, Table 10 indicates if each of the modified input shares A 1 i and B 1 i carries the same parity as would have carried the corresponding input share in a non-faulted environment in the two one-bit faults case, depending on the locations of these faults.

Fault

Locations Modified Input

Share

Table 10: Correctness of parities of modified input shares A 1 i and B 1 i after the XOR of variables V i and V 1 i in a two faults locations case Moreover, it can be noticed that using only two variables V i would not be enough to ensure both the correctness of parities of input shares and the noncompleteness of those sub-sums V i .

Indeed, to ensure non-completeness not all the shares A i can figure in the computation of a same sub-sum V i , and in the same manner not all the shares B i can figure in the computation of a same sub-sum V j . Nevertheless, to ensure that all potential input fault locations are covered, all input shares A i and B i must feature in at least one sub-sum V i . Supposing that we employ only two sub-sums, these two conditions combined imply that both sub-sums would comprise at the same time some shares A i from A and some shares B i of B. Therefore, it is not possible to attribute with certainty a fault detected on one of these sub-sums to the input where it has been committed initially. That is why 10 A New Fault Resistant Masking Scheme This section details the design of the masking scheme in three parts. The first subsection describes the input shares correction design, then the second subsection explains the core operations of the AND multiplication. Finally, the construction of the output shares is detailed in the third subsection.

Input Shares Correction

As explained in subsubsection 9.1.4, we choose to use the BCH code of length n " 45 with the maximum dimension. To that end, we consider m " 12 the multiplicative order of 2 modulo n, α a 45 th primitive root of unity in F q m and therefore determine the generator polynomial gpXq of the BCH code we use to be gpXq " lcmpM α pXq, M α 2 pXq, M α 3 pXq, M α 4 pXqq " pX 12 `X3 `1q ˚pX 4 `X `1q " X 16 `X13 `X12 `X7 `X3 `X `1.

To compute a ^b with a, b P F 2 , we represent a and b by codewords A and B P F 45 2 verifying HW pAq mod 2 " a and HW pBq mod 2 " b. We then suppose each of those two input codewords A and B to be split between four shares. In other words, we randomly pick shares A 0 , A 1 , A 2 , A 3 , B 0 , B 1 , B 2 and B 3 that are codewords as well and verify A " A

Firstly, we perform code correction on the input shares to prevent any faults introduced at the end of preceding operations or just before the start of the current instance of the scheme. As explained in subsubsection 9.2.2, we must avoid the correction of each of the eight input shares for performance reasons. Consequently, we compute the following three intermediate sub-sums V 0 , V 1 and V 2 and correct them into respective codewords

Subsequently, thanks to these variables V i and their corresponding corrected codewords V 1 i , we can correct the parities of shares A i and B i by computing modified shares A 1 i and B 1 i as follows :

This appendix will detail the different steps of the attack on a TBox mentioned in subsection 8.2. To that end, we keep the notations of the intermediate values of a TBox detailed in subsection 8.1.

A.1 First Step of the Attack

The first step of the attack illustrates how to deduce the left half of the input encodings of a TBox. We consider the right-most TBox T 0 of a round r, with key bits pk 1 , k 0 q " p1, 1q, round constant bit c " 0, the intern SBox ILU T " r0110, .

First of all, from an attacker viewpoint, we randomly consider the values of the six left-most input bits px 7 , x 6 , x 5 , x 4 , x 3 , x 2 q to be p0, 0, 1, 1, 0, 1q. By the bijectivity of encodings, there exists a unique value px p0,0q 1 , x p0,0q 0 q P F 2 2 such that G ´1 r´1,0 px p0,0q 1 x p0,0q 0 q " 00. Thus, the computation of T 0 r00 11 01 x Although it is not possible to determine yet i P t0, 1, 2, 3u such that p00 00 11q = pt i 7 t i 6 t i 5 t i 4 t i 3 t i 2 t i 1 t i 0 q, as G r,3 ppz 7 ' cqz 6 q ‰ G r,3 ppz 7 ' cqz 1 6 q ‰ G r,3 ppz 7 ' cqz 6 q ‰ G r,3 ppz 1 7 ' cqz 1 6 q it can be deduced by the bijectivity of G r,3 that z 7 ‰ z 7 pand z 1 6 ‰ z 6 q, i.e. z 1 7 " z 7 . Furthermore, G r,2 ppz 5 ' k 1 qz 4 q " G r,2 ppz 5 ' k 1 qz 1 4 q " G r,2 ppz 1 5 ' k 1 qz 4 q " G r,2 ppz 1 5 ' k 1 qz 1 4 q, hence z 1 5 " z 5 and z 1 4 " z 4 . In the same manner, it can be determined that z 1 3 " z 3 , z 1 2 " z 2 , z 1 1 " z 1 and z 1 0 " z 0 . Consequently, GSry 7 y 5 y 3 0s " z 7 z 5 z 3 z 1 implies that y 7 , y 5 and y 3 verify that GSry 7 y 5 y 3 1s " z 7 z 5 z 3 z 1 . According to the values of the SBox GS it can then be deduced that the unique possible value of py 7 , y 5 , y 3 q is p0, 1, 1q. Therefore G ´1 r´1,15 p00q " 0 , G ´1 r´1,10 p11q " 1 and G ´1 r´1,5 p01q " 1 . This method can be repeated while changing the six fixed input bits and potentially the varying 2-bit input block to determine the remaining left bit values of the four input encodings. For example, considering px 7 , x 6 , x 5 , x 4 , x 3 , x 2 q " p1, 0, 0, 1, 1, 0q, the output values of the TBox are Consequently, G r,2 pk 1 z 4 q " 00 and G r,1 pk 0 z 2 q " 10. Therefore, by the bijectivity of the output encodings G r,2 and G r,1 , the values of key bits k 1 and k 0 verify pk 1 , k 0 q " p1, 0q, i.e. pk 1 , k 0 q " p1, 1q.