Boly Seck
email: seck.boly@ugb.edu.snidy.diop@esp.sn

Pierre-Louis Cayrel
email: pierre.louis.cayrel@univ-st-etienne.fr

Vlad-Florin Dragoi
email: vlad.dragoi@uav.ro

Idy Diop

Morgan Barbier
email: morgan.barbier@ensicaen.fr

Jean Belo Klamti
email: jbklamti@uwaterloo.ca

Vincent Grosso
email: vincent.grosso@univ-st-etienne.fr

Brice Colombier
email: b.colombier@univ-st-etienne.fr

A Side-Channel Attack against Classic McEliece when loading the Goppa Polynomial

Keywords: NIST PQC standardization, Classic McEliece, Side-Channel Attack, Template Attack, Goppa Polynomial

The NIST Post-Quantum Cryptography (PQC) standardization challenge was launched in December 2016 and recently, has released its first results. The whole process has given a considerable dynamic to the research in post-quantum cryptography, in particular to practical aspects, such as the study of the vulnerabilities of post-quantum algorithms to side-channel attacks. In this paper, we present a realistic template attack against the reference implementation of Classic McEliece which is a finalist of the 4th round of NIST PQC standardization. This profiled attack allowed us to accurately find the Hamming weight of each coefficient of the Goppa polynomial. With only one decryption, this result enables us first, to find directly the Goppa polynomial in the case of weak keys with the method of Loidreau and Sendrier (P. Loidreau and N. Sendrier, "Weak keys in the McEliece public-key cryptosystem", IEEE Trans. Inf. Theory, 2001). Then, in the case of "slightly less weak keys", we also find this polynomial with an exhaustive search with low complexity. Finally, we propose the best complexity reduction for exhaustive Goppa polynomial search on F2m . We attack the constant-time implementation of Classic McEliece proposed by Chen et al.. This implementation, which follows the NIST specification, is realized on a stm32f4-Discovery microcontroller with a 32-bit ARM Cortex-M4.

Introduction

In recent years, research on quantum computers has accelerated considerably [TF19; GI19; Lar+21]. These computers can theoretically solve difficult number theory problems (the integer factorization problem and the discrete logarithm problem) in polynomial time [START_REF] Feynman | Simulating physics with computers[END_REF][START_REF] Deutsch | Rapid solution of problems by quantum computation[END_REF][START_REF] Grover | A fast quantum mechanical algorithm for database search[END_REF][START_REF] Shor | Algorithms for quantum computation: discrete logarithms and factoring[END_REF]. Thus, if large-scale quantum computers are built, they will be able to break most current asymmetric systems such as RSA, ECDSA and ECDH. This would severely compromise the confidentiality and integrity of all digital communications. As a result, the cryptographic community has turned its attention to credible alternatives for dealing with quantum computing. Thus, in 2016, the National Institute of Standards and Technology (NIST) announced a call for proposals to standardize post-quantum cryptography (PQC) primitives [START_REF] Chen | NIST post-quantum cryptography standardization[END_REF]. This standardization process consists of several rounds, and only those applicants that best meet NIST's requirements in each round are selected to proceed to the next round.

On the fifth of July, 2022, NIST released the first four winning algorithms (a key establishment algorithm named CRYSTALS-Kyber, and three digital signature algorithms named CRYSTALS-Dilithium, FALCON, and SPHINCS+). The first three of these algorithms are based on structured lattices and the last one, SPHINCS+ is a hash-based signature scheme. These future standards are expected to be used by default for selecting post-quantum algorithms in many security products. Provided that these post-quantum algorithms are also combined with proven classical algorithms through hybrid mechanisms. The main goal of the process started by NIST is to replace three standards that are considered the most vulnerable to quantum attacks, i.e., FIPS 186-46 (for digital signatures), NIST SP 800-56A7 , and NIST SP 800-56B 8 (both for keys establishment in public-key cryptography).

Beside the four winners, an extension of the NIST PQC standardization campaign (4th round) is planned for key establishment algorithms: BIKE, HQC, Classic McEliece [START_REF] Chou | Classic McEliece: conservative code-based cryptography 10 October 2020[END_REF] (all three based on error-correcting codes). Classic McEliece was the first selected finalist for code-based cryptography as a Key Encapsulation Mechanism (KEM), while BIKE and HQC were two alternatives.

In addition to defining secure schemes and choosing secure parameters, an important issue, in the standardization process, is the impact of a scheme's implementation on its security. A general requirement on the implementation of a scheme is that the execution time of operations does not vary with the secret information (e.g., the secret key or plaintext). This is called a constant-time implementation. However, there are other side-channel attacks beside timing attacks that can allow an attacker to access secret information. Other side-channels include power consumption and electromagnetic, photonic, and acoustic emissions.

For many PQC systems, it is still unclear which side-channel attacks are feasible in practice and how to be protected against them. That is why the side-channel topic has become recurent in the NIST PQC seminar9 [Saa22; Rav+22]. In the past, code-based cryptosystems were subject to side-channel attacks even before NIST started the standardisation process [CD10; HMP10; Mol+11; Ava+11; Che+16]. However, the end of the first round of this challenging process defined the beggining of a side-channel race for physical security assesment. Indeed, Classic McEliece KEM oriented attacks appeared in a series of articles, where either the security of session key or of the private key was investigated [Lah+20; Cay+21; GJJ22; Col+22a; Sec+22; Gro+23; Col+23]. Here we make another step in this direction.

Contribution:

In this work, we focus on the constant-time implementation of Classic McEliece which is one of the finalists of the NIST PQC extended campaign. This is a KEM, which is conservatively built from a Public Key Encryption (PKE) designed for One-way under Chosen-Plaintext Attack (OW-CPA) security, namely Niederreiter's dual version of McEliece's PKE using Goppa binary codes, as described in Section 2.2. First, we perform a template attack during decryption in Classic McEliece to find the Hamming weights of the Goppa polynomial coefficients. Since the Goppa polynomial is loaded from memory during this step, we were able to track the execution step of the algorithm and measure the corresponding power consumption. With this information at hand, we have built a profile for each possible weight and deployed, using a single trace, our attack. At the end of this step, each weight was detected with an almost perfect accuracy. Finally, we have used this information to find the Goppa polynomial. In the case of weak keys with binary coefficients, the polynomial was retrieved directly from the Hamming weight. In the case of "slightly less weak keys", we show that in polynomial time one can compute the Goppa polynomial. Moreover, we have significantly improved the complexity of the best attack to find the Goppa polynomial on F 2 m from 2 1615 to 2 1174 for m = 13, n = 8192 and t = 128. Finally, we show that our attack is realistic compared to other side-channel attacks on Classic McEliece.

Organization: The paper is organized as follows: Section 2 provides some background information on code-based cryptography and briefly describes Classic McEliece scheme. Section 3 presents a detailed description of our template attack on the constant-time implementation of Classic McEliece on ARM Cortex-M4 [START_REF] Chen | Classic McEliece on the ARM Cortex-M4[END_REF] to recover the Hamming weights of the Goppa polynomial coefficients. In Section 4, we use this result to find the Goppa polynomial directly in the case of weak keys and reduce the complexity of the exhaustive search for the Goppa polynomial on F 2 m . Section 5 compares our attack with a recent side-channel attack of Guo et al. [START_REF] Guo | A Key-Recovery Side-Channel Attack on Classic McEliece Implementations[END_REF] on Classic McEliece and finally, we conclude this paper in Section 6.

Theoretical background

Preliminaries

Let us first recall basic definitions and notations used in coding theory. A linear code C over F q is a vector subspace of F n q of dimension k and the elements of C are called codewords. A generator matrix of C is a matrix G ∈ F k×n q such that its lines form a basis of the vector space C such that C = {xG|x ∈ F k q }. A parity-Check matrix is a matrix H ∈ F (n-k)×n q such that C = {y ∈ F n q |Hy T = 0}. To perform error detection and correction, a code C uses a norm, the most common one being the Hamming weight wt(y) = #{i, y i ̸ = 0}. Any linear code possesses a minimum distance, i.e.,

d(C) = min{wt(c) | c ∈ C, c ̸ = 0}.
(1)

Goppa codes

Definition 1 (Goppa code). Let g(x)

= g t x t + • • • + g 2 x 2 + g 1 x + g 0 ∈ F q m [x],
and let L = {α 1 , α 2 , ..., α n } ⊆ F q m such that, g(α i ) ̸ = 0, for all α i ∈ L. Then the code defined by

C = (c 1 , c 2 , . . . , c n ) ∈ F n q : n i=1 c i x -α i ≡ 0 mod g(x) (2)
is called Goppa code with parameters L and g(x), denoted by Γ (L, g).

For each i, gcd(x -α i , g(x)) = 1 since g(α i ) ̸ = 0, the value of (x -α i ) -1 is computed into

F q m [x] ⟨g(x)⟩ . Theorem 1. [MS77]
The multiplicative of (x-α i ) inverse exists in the quotient ring

F q m [x] ⟨g(x)⟩ ; the value of (x -α i ) -1 in F q m [x] ⟨g(x)⟩ is g(αi)-g(x)
x-αi

g(α i ) -1 . A vector c ∈ Γ (L, g) if and only if i c i g(αi)-g(x)
x-αi g(α i ) -1 ≡ 0 mod g(x).

Using this result, we can derive the following important corollary:

Corollary 1. [MS77]
For a Goppa code Γ (L, g), the parity check matrix over

F q m is H =      g(α 1 ) -1 g(α 2 ) -1 . . . g(α n ) -1 α 1 g(α 1 ) -1 α 2 g(α 2 ) -1 . . . α n g(α n ) -1 . . . . . . . . . . . . α t-1 1 g(α 1 ) -1 α t-1 2 g(α 2 ) -1 . . . α t-1 n g(α n ) -1      t×n . (3)
If we consider the elements of F q m as vectors of length m over F q by vector space isomorphism, we have a parity check matrix H for Γ (L, g) over F q to be a mt × n matrix, with at least t linearly independent columns over F q . Therefore, the Hamming distance of the Goppa code, d(Γ (L, g)) ≥ t + 1. Since at most mt rows are linearly independent, Rank(H) ≤ mt therefore, the dimension of the Goppa code is k ≥ n -mt.

Definition 2 (Primitive polynomial). An irreducible polynomial p(z) of degree m over F q is called a primitive polynomial if its roots form primitive elements of F q m . Remark 1. The number of irreducible polynomials of degree t with coefficients in F q m is approximately q mt t .

Code-base cryptography

We briefly present the McEliece cryptosystem [START_REF] Mceliece | A public-key cryptosystem based on algebraic[END_REF] and its variant, Niederreiter [START_REF] Niederreiter | Knapsack-type cryptosystems and algebraic coding theory[END_REF], and the KEM Classic McEliece whose implementation on ARM Cortex-M4 is the target of our attack.

McEliece cryptosystem

The McEliece cryptosystem was introduced by Robert J. McEliece in 1978. The basic idea of this cryptosystem is to use binary Goppa code (q = 2) with an efficient decoding algorithm that can correct up to t errors. The public key is a matrix G = SG ′ P where G ′ is a generator matrix of the Goppa code, S (resp. P ) is a random k × k non-singular (resp. n × n permutation) matrix. The code length n, the code dimension k, and the Hamming weight of the error wt(e) = t are public parameters, but the Goppa code Γ (L, g), matrices S and P are secrets. The encryption works by computing a code word for the plaintext x using the generator matrix G and by adding an error e. The ciphertext c is therefore computed as c = xG ⊕ e. The receiver corrects the error by applying the decoding algorithm with G ′ and recovers x.

The security of the system is based on the hardness of decoding a general linear code, a problem known to be N P-complete [START_REF] Berlekamp | On the inherent intractability of certain coding problems (corresp.)[END_REF].

Niederreiter cryptosystem This cryptosystem is a dual version of the McEliece cryptosystem. It was published by Harald Niederreiter in 1986. The main difference between the McEliece and the Niederreiter scheme is that the public key in Niederreiter's scheme is a parity check matrix instead of a generator matrix. In the Niederreiter scheme, the ciphertext is a syndrome c = He T where the error vector e is the image of the plaintext x by an encoding function ϕ. Therefore, an efficient syndrome decoding algorithm is used for decryption. In what follows, we will focus on the instantiation of Niederreiter using binary Goppa codes as in Classic McEliece [START_REF] Chou | Classic McEliece: conservative code-based cryptography 10 October 2020[END_REF] (see also [START_REF] Bernstein | McBits: fast constanttime code-based cryptography[END_REF] and [START_REF] Chou | McBits revisited[END_REF] for more details).

Classic McEliece Classic

McEliece is a code-based a KEM introduced by Bernstein et al. [START_REF] Bernstein | Classic McEliece: conservative code-based cryptography[END_REF]. It is composed of three algorithms (key generation, encapsulation and decapsulation) described below.

Key generation

The key pair generation in Classic McEliece is described as follows:

1. Construct a parity check matrix H ′ for a Goppa code Γ (L, g); 2. Transform H ′ into a mt × n binary matrix H by replacing each F 2 m -entry by a m-bit column; 3. Compute the systematic form [I mt |T ] of H and return {g(x), α 1 , α 2 , . . . , α n } as the secret key and T as the public key.

Encapsulation The session key K and its encapsulation are generated as follows:

1. Generate a random e ∈ F n 2 with wt(e) = t; 2. Compute the matrix H = [I mt |T ] by appending T to the identity matrix I mt and then a vector c0 = He T ; 3. Compute c1 = H(2|e) and generate ciphertext c = (c 0 |c 1 ), H represents the hash function SHAKE256; 4. Compute a 256-bit session key K = H(1|e|c).

Decapsulation Recovering the session key K ′ from a ciphertext c can be done as follows:

1. Split c as (c 0 |c 1 ), with c0 ∈ F mt 2 and c1 ∈ F 256 2 ; 2. Use the underlying decoding algorithm for Niederreiter scheme to recover e such that wt(e) = t and c0 = He T ; 3. Compute c′ 1 = H(2|e), and checks if c′

1 = c1 ; 4. Compute the session key K ′ = H(1|e|c).
If there is no failure at any stage during the decapsulation process and c′ 1 = c1 , then surely the session key K ′ will be identical to K. In this scenario, the same session key is established. Side-channel attacks are powerful tools for accessing secret information (passwords, secret keys, etc.) and pose a threat to cryptographic algorithm implementations. One of the most powerful techniques for evaluating side-channel information, template attack, was presented by Chari, Rao, and Rohatgi in [START_REF] Chari | Template attacks[END_REF].

The general idea of template attacks is to rely on a multivariate model of sidechannel traces to break secure implementations. In this section, we will first give a theoretical overview of template attacks, then we will show the information leakage related to the loading function of the coefficients of the Goppa polynomial during the decryption step of Classic McEliece and finally, we will present our template attack principle and results.

Template attacks

Multivariate-Gaussian model We consider the case where the electronic noise at each point of a power trace follows a normal distribution. This power consumption model does not take into account the correlation between neighboring points. To take into account this correlation between points, it is necessary to model a power trace t r as a multivariate normal distribution. The multivariate normal distribution is a generalization of the normal distribution to higher dimensions. It can be described by a covariance matrix C and a mean vector µ. The Probability Density Function (P DF ) of the multivariate normal distribution is given below.

P DF (t r ; (µ, C)) = 1 (2π) ℓ × det(C) exp - 1 2 (t r -µ) T C -1 (t r -µ) ( 4
)
where ℓ is the number of samples in the power trace t r . The covariance matrix C essentially characterizes the fluctuations in the power traces such as electronic noise. However, the multivariate normal distribution can also be used to characterize other components of power consumption. One of the problems with using the multivariate normal distribution is the cost of computing the covariance matrix C which grows quadratically with ℓ. Therefore, in practice, only small parts of the power traces are characterized.

General description Template attacks exploit that the power consumption also depends on the data that is being processed. In contrast to other types of power analysis attacks like Simple Power Analysis (SPA) [START_REF] Kocher | Differential power analysis[END_REF] or Differential Power Analysis (DPA) [START_REF] Kocher | Differential power analysis[END_REF]), template attacks consist of two phases. A building phase, in which the characterization of power consumption takes place, and a matching phase, in which the characterization is used to determine the secret information.

In template attack, the power traces can be characterized by a multivariate normal distribution, which is fully defined by a mean vector µ and covariance matrix C. This couple (µ, C) is called a template. We can characterize the attacked device to determine the templates of some instruction sequences. In the building phase, we use another device of the same type as the one being attacked that we can fully control. On this device, we execute these instruction sequences with different data d i and key k j to record the resulting power consumption. Then, we aggregate the traces that correspond to a pair of (d i , k j ), and estimate µ and C. Thus, we obtain a template h for every pair (d i , k j ).

h di,kj = (µ, C) di,kj .
As mentioned above the size of the covariance matrix grows quadratically with the number of points in the trace. The inverse of C, which is needed to compute the P DF , can be numerically problematic for large ℓ as shown by the authors in [START_REF] Eisenbarth | Building a side channel based disassembler[END_REF]. We need to find a strategy to determine the points that contain the most information about the characterized instruction. This is called Points of Interest (POI) and we denote the number of POI by N P OI . There are several methods to find the POIs, such as the Sum of Differences [RO04] that we will use in this paper, the Sum Of Squared Differences (SOSD) [START_REF] Gierlichs | Templates vs. stochastic methods[END_REF], the Signal to Noise Ratio (SNR) [START_REF] Mangard | Power analysis attacks: Revealing the secrets of smart cards[END_REF], the Principal Component Analysis (PCA) [START_REF] Archambeau | Template attacks in principal subspaces[END_REF] etc.

Next, we use the characterization and a power trace of the attacked device to determine the key. In this matching phase, we evaluate the probability density function of the multivariate normal distribution with (µ, C di,kj ) and the power trace of the attacked device. In other words, given a power trace t r of the attacked device, and a template h di,kj , we compute the P DF :

P DF (t r ; (µ, C di,kj )) = 1 (2π) N P OI × det(C) exp - 1 2 (t r -µ) T C -1 (t r -µ) .
(5) We do this for every template. As a result, we get the PDFs

P DF (t r ; (µ, C) d1,k1 ), . . . , P DF (t r ; (µ, C) d D ,k K ).
The probabilities measure how well the templates match a given trace t r and the highest value indicates the correct template. Since each template is associated with a key, we get an indication of the correct key. If all keys are equiprobable, the decision rule that minimizes the probability of a wrong decision is to decide for h di,kj if P DF (t r ; h di,kj ) > P DF (t r ; h di,kv )∀v ̸ = j. This is the Maximum Likelihood (ML) decision rule.

Templates with power models In addition to building templates for data and key pairs, there are other strategies. For example, if a device leaks the Hamming weight of the data, then moving the value 1 will result in the same power consumption as moving the value 2. Therefore, the template associated with value 1 will correspond to a trace in which value 1 is moved as well as the template associated with value 2. Thus, it is possible to build templates for values with different Hamming weights. Suppose we want to build templates for the output of a single-byte instruction sequence. We can simply build templates from 0 to 8 per byte. This is the approach we will take to build our templates for a decryption sequence in Classic McEliece implementation.

Measurement setup and leakage analysis

For our experiments, we used Classic McEliece variant mceliece8192128 (m = 13, n = 8192, t = 128) where the coefficients of the Goppa polynomial are represented on m bits. But for the purpose of the implementation in [START_REF] Chen | Classic McEliece on the ARM Cortex-M4[END_REF], each coefficient will be represented on 2 bytes instead of 1 byte and 5 bits. We attack a software implementation of the decapsulation algorithm (loading function of the coefficients of the Goppa polynomial, irr load 32x) running on an STM32F415RGT6 microcontroller [START_REF] Chen | Classic McEliece on the ARM Cortex-M4[END_REF]. The microcontroller features a 32-bit ARM Cortex-M4 core with 1 MB Flash memory and 192 kB SRAM.

The traces are acquired using the ChipWhisperer-Pro (CW1200) [START_REF] O'flynn | Chipwhisperer: An open-source platform for hardware embedded security research[END_REF] which is an open-source embedded security analysis platform for recording and analyzing power consumption. All traces are acquired at a sample rate 105 × 10 6 samples per second (105 MS/s). Data acquisition is controlled by scripts running on PC. The ChipWhisperer measures power consumption during loading of the coefficients of the Goppa polynomial g(x) of degree t. Once the acquisition is finished, the PC stores the measured trace on the hard disk. The measurement process is repeated depending on the desired number of traces. In traces, we can distinguish four patterns Fig. 1. These patterns are caused by the bitsliced representation used in the loading function irr load 32x. Bitslicing is a simulation of hardware implementations in software. It is an implementation trick to speed up software implementations. It was introduced by Biham[Bih97] in 1997 for DES. The basic idea of bitslicing is to represent n-bit data as a bit in n distinct registers. On 32-bit registers, there are 31 unused bits in each register, which can be filled in the same fashion by taking 31 other independent n-bit data and putting each of their n bits in one of the registers. Bitwise operators on 32-bit (e.g. AND, OR, XOR) then act as 32 parallel operators. The bitslicing in this loading function irr load 32x consists of transposing 32 16-bit coefficients into 16 different 32-bit registers for each round of the main loop. This loading function (Fig. 2) consists of the main loop to load the 128 coefficients in steps of 32 (hence the four patterns in Fig. 1) nested in two consecutive loops. These two loops each load 16 16-bit coefficients. Then, each of these 16 coefficients is transposed into 16 different 32-bit registers. Finally, a kind of assembly operation of We will now perform a power consumption analysis on the loading function irr load 32x. The hypothesis is that small variations in power level may be observed in a trace based on the output of this function. We analyze how the power consumption of the load function depends on the least significant bit (LSB) of 16-bit data with its transpose operation. If the LSB output produced by irr load 32x is 1 then, in theory, the device under test should consume more power in comparison with a 0 value. If the hypothesis holds, we may exploit this fact to deduce the Hamming weights of the coefficients during loading operations. It should be noted that this variation in power consumption is very small. The technique of differential power analysis used to determine the effect of the LSB on power consumption is the Difference Of Means (DOM).

We measured the power consumption of the microcontroller when loading 10 000 random coefficients. We obtain 10 000 power traces, then sort them into two subsets (5 000 power traces for LSB=1 and 5 000 power traces for LSB=0) and calculate the average of each subset. The DOM between each subset will infer whether the proposed hypothesis is significant. In the case of a significant hypothesis, the DOM between the two subsets will highlight the change in power consumption when LSB of 0 is compared to LSB of 1. The average of each subset is calculated point by point. Thus, the difference of means can then be calculated by simply subtracting the points in the first subset from the points in the second subset. The result of this DOM is shown in Fig. 4.

Principle and results

We have two significant peaks easily discernible. These two peaks reveal the moments when the power consumption of the microcontroller depends on the LSB. Thus this loading function irr load 32x leaks information. The transpose function also processes the same data as the loaded data and therefore the bitsliced representation according to this result also leads to information leakage. We now exploit this property in a power analysis attack to determine the Hamming weights of the Goppa polynomial coefficients g(x). Recall that in Classic McEliece, the secret key consists of the Goppa polynomial and the support. Therefore, recovering the secret key corresponds to recovering g(x) and L. It should also be noted that this experiment was done for the other 15 bits of the coefficient and the result is the same. In what follows, we will only use the loading of the first coefficient of g(x) without the transposition for the template attack. In this section, we present the template attack on loading the first 16-bit coefficient of g(x). We describe how to generate the templates from the random coefficient traces. Our template will attempt to recognize the Hamming weight of each coefficient at the output of the loading function irr load 32x. The goal of our attack is to find the Hamming weights of all 128 coefficients of g(x). This information will significantly reduce the complexity of the exhaustive search for the Goppa polynomial on F 2 m . For our experiment, we used the same device for building and matching phases.

As we said at the end of Section 3.1, we will build templates in Hamming weights.

Since each coefficient of g(x) is represented on 16 bits in [CC21], we will build 17 templates for each coefficient. A key point with template attacks is that they require a large amount of data to make good templates. We recall that each output of this load function is unique, so there is only one output with a Hamming weight of 0 and one with a weight of 16. This means that using random inputs, there is only a 1/(256) 2 probability of having a trace with a Hamming weight of 0 or 16.

In our experiment, we have efficiently used 350 000 traces, which allowed us to have a good distribution to build our templates. We then examine a trace and decide what its Hamming weight is. To set up the templates, we need to sort our template traces into 17 groups. The first group will consist of all traces that have a Hamming weight of 0. The next group has a Hamming weight of 1, etc., and the last group has a Hamming weight of 16. After sorting the traces by their Hamming weights, we look for the "average trace" for each weight. We create an array that contains 17 of these averages. We can always plot these averages to make sure that the average traces are correct. We will now use these average traces to find the POIs using the Sum of Differences method in Fig. 5. This method shows where these average traces have a lot of variances and the Fig. 5: Sum of Differences for 350 000 traces.

POIs are the highest peaks. In our case, we have one POI (sample 13). In the case where we had more peaks in the Sum of Differences, we cannot simply sort an array and choose the highest points. We have to make sure that the points are separated by some space. We can now construct our multivariate normal distribution for each Hamming weight. We need to write the 1 × N P OI mean vector µ and the N P OI × N P OI covariance matrix C at this POI for each Hamming weight. In our case N P OI = 1, the mean is a scalar and the covariance matrix is reduced to the variance. Our templates are ready, so we can use them to perform the matching phase now. For a decryption, using a random ciphertext, we recorded 17 power traces on the attacked device during the loading of the first coefficient of g(x). These 17 power traces correspond to the loading of the coefficients with Hamming weights set from 0 to 16. We load our 17 template traces for each coefficient with a fixed Hamming weight and apply the PDF for each target trace to check which template fits best. We were able to find the Hamming weight of the first coefficient of the Goppa polynomial on the device attacked during decryption with a success rate of 99.86% after 1000 simulations. This matching phase with one target trace takes about 4 seconds on an 8-core processor running at 3.6 GHz. Thus we manage with our templates to find the Hamming weight of the first coefficient of g(x) when it is loaded from memory. To find the Hamming weights of the remaining t-1 coefficients, it is necessary to construct t-1 groups of m + 1 templates in Hamming weights. We proceed in the same way as for the first coefficient, except that the position of the POI(s) will change because it depends on the position of the coefficient during loading. The knowledge of the Hamming weights of the coefficients of g(x) allowed us to improve the complexity of the exhaustive search for the Goppa polynomial on F 2 m .

Complexity of the Goppa polynomial search

In this section, we have given the complexity of finding the secret Goppa polynomial in the original McEliece with the knowledge of Hamming weights of its coefficients. Indeed, the key recovery attack against McEliece using irreducible Goppa code consists of recovering the Goppa polynomial g and the support L = {α 1 , α 2 , ..., α n } ∈ F n 2 m . However, the best way to proceed is described as follows [START_REF] Loidreau | Weak keys in the McEliece publickey cryptosystem[END_REF]:

1.
Step 1: Find an monic irreducible polynomial g of degree t such that the Goppa code Γ (L, g) is equivalent to the public code C.

2.

Step 2: Find the permutation by using the Support Splitting Attack (SSA) algorithm.

The cost of a such enumerative attack is given by Cost = λn 3 C irr where n is the code length and λ is a small constant depending on the implementation of the attack [START_REF] Loidreau | Weak keys in the McEliece publickey cryptosystem[END_REF]. C irr is the number of irreducible polynomials over F 2 m i.e the cardinal of search space. In the case of an extended code of Goppa, the value of C irr is given by [LS01]

C irr ≈ 2 m(t-3) mt . (6)
With the knowledge of Hamming weights δ j " g j , and by assuming that irreducible monic polynomials over F 2 m have a uniform distribution, the cardinal of the search space is given by

#Search Space = t-1 j=0 m δj t . (7)
In fact, to the best of our knowledge, there is no specific algorithm to construct an irreducible polynomial by knowing the Hamming weights of its coefficients. Therefore, finding such polynomials corresponds in practice to search in the set of all monic polynomials with corresponding coefficients Hamming weights set. Note that, in the case that the Goppa polynomial is an irreducible binary polynomial that corresponds to a weak key in [START_REF] Loidreau | Weak keys in the McEliece publickey cryptosystem[END_REF], with the knowledge of the Hamming weight of coefficients, the cardinal of the search space is equal to 1. Indeed, all coefficients with non-zero Hamming weight have their value equal to 1 thus, we can directly reconstruct the Goppa polynomial without searching (Table 2). While it was shown in [START_REF] Loidreau | Weak keys in the McEliece publickey cryptosystem[END_REF] that the computation time to find this irreducible binary polynomial for an instance where m = 10, n = 1024, and t = 50 with their implementation should be 500 years. We can also imagine a scenario in which the user generates non-binary polynomials with fixed weights for all coefficients (to speed up the generation of the public key). This technique only speeds up the generation of the public key offline but not the decryption process. We call this second case "slightly less weak keys". In the Table 2, we show the expression of the size of search space for two particular cases of "slightly less weak keys". It is sufficient to perform an exhaustive lowcomplexity search to recover the Goppa polynomial. Thus with the information on the Hamming weights of the coefficients of the Goppa polynomial, we have increased the set of weak keys proposed in [START_REF] Loidreau | Weak keys in the McEliece publickey cryptosystem[END_REF].

For non-binary irreducible polynomials where the extension degree is larger than 8, each finite field element is implemented at least on 2 bytes. Thus, for suitable values 0 ≤ i j ≤ δ j , one can look for polynomials whose coefficients have Hamming weight i j on the first byte and δ j -i j on the remaining m -8 bits. With this technique, the cardinality of the search space (7) becomes

#Search Space = t-1 j=0 8 ij m-8 δj -ij t ≤ 8 4 t m-8 ⌊ m-8 2 ⌋ t t . (8)
When extended code is implemented in the attack, this number should be divided by 2 m (2 m -1)m. Indeed there are 2 m (2 m -1)m polynomial g ′ such that the extended codes of the Goppa codes Γ (L, g ′ ) are equivalent to that of Γ (L, g). However, one can easily notice that with the systematic form of H, we can detect the problem of bad ciphertexts with Hamming weights less than or equal to t. This is not the only step where this attack could be compromised. Recall that the error locator polynomial is obtained with the Berlekamp-Massey algorithm.

At this point, the error locator polynomial, via its degree, directly reflects any intentional error or misformated chipertext. Indeed, when this polynomial is of degree lower than t the decryption must stop and thus one can avoid the GJJ attack. All of these point out towards the fact that the GJJ attack to find the secret key in Classic McEliece is not realistic.

Positive points in our attack Our template attack to find the Hamming weights of the Goppa polynomial coefficients on Classic McEliece is realistic compared to the key-recovery side-channel attack of Guo et al. for the variant mceliece8192128 as shown in the Table 4. First, we have no constraints on the Hamming weight of the ciphertexts and use fewer traces to recover the Hamming weight of Goppa polynomial coefficients. Secondly, we just follow the steps of the decryption execution in the implementation of Classic McEliece and we measure the trace of power consumption corresponding to the loading of the coefficients of the Goppa polynomial. Finally, our method has the particularity to be extended on other steps of decryption in Classic McEliece or other cryptosystems. Indeed, the loading of a vector of evaluation points is also performed just before the additive FFT for the evaluation of the error locator polynomial. If the setup is such that our attack can be reproduced we could gain the same information (Hamming weight) about the evaluation points. Also, notice that any decoding algorithm for binary Goppa codes has to use this/similar function for loading the Goppa polynomial and the points of evaluation. This information on the Hamming weights of the evaluation points, combined with our current results on the coefficients of the Goppa polynomial, will greatly improve our knowledge of the secret in Classic McEliece. We can also use this information on the evaluation points to apply the decoding method with a hint from [START_REF] Kirshanova | Decoding McEliece with a Hint -Secret Goppa Key Parts Reveal Everything[END_REF] to directly recover the Goppa polynomial.

Common countermeasure fail against our attack We recall that our attack on the loading function of the Goppa polynomial coefficients is performed on the optimized reference implementation of Classic McEliece on ARM-Cortex M4 [START_REF] Chen | Classic McEliece on the ARM Cortex-M4[END_REF]. This reference implementation represents the side-channel attack target of several recent papers [START_REF] Cayrel | Message-recovery laser fault injection attack on the classic McEliece cryptosystem[END_REF][START_REF] Colombier | Profiled Side-channel Attack on Cryptosystems based on the Binary Syndrome Decoding Problem[END_REF][START_REF] Guo | A Key-Recovery Side-Channel Attack on Classic McEliece Implementations[END_REF]. Shuffling is nowadays one of the most common and effective countermeasure techniques against most side-channel attacks [START_REF] Chen | Low-Cost Shuffling Countermeasures Against Side-Channel Attacks for NTT-Based Post-Quantum Cryptography[END_REF]. However, in our attack, shuffling does not work because loading the coefficients in a random order will not affect their Hamming weights. In general, we have shown in this work that this loading function is not appropriate for secret variables in Classic McEliece. Moreover, our proposal is a first step towards much more powerful and potentially generic possible attacks. Indeed, the loading of a list of secret coefficients is performed at several places in the decryption of a code-based cryptographic scheme, and if we can isolate the exact moment when such functions are loaded then we could imagine applying our attack.

Conclusion

In this paper, we have presented a side-channel attack against the reference implementation of Classic McEliece on ARM Cortex-M4. The side channel here corresponds to loading the coefficients of the Goppa polynomial from memory during decryption. The phase of matching of our profiled attack is very fast (about 4 seconds) and allows us to find the Hamming weights of the coefficients of the Goppa polynomial that is an important part of the secret key of Classic McEliece. First, this result allowed us to directly find the Goppa polynomial in the case of weak keys with the method of Loidreau and Sendrier. In the case of "slightly less weak keys", we manage to find this polynomial with a low-complexity exhaustive search. Thus, we increase the set of weak keys compared to the method of Loiderau and Sendrier. Then, this information about the Hamming weights of the coefficients also allowed us to give the best complexity reduction for Goppa polynomial search on F 2 m . Finally, we have shown that our attack is realistic (we only need a decryption of a random ciphertext) compared to other side-channel attacks on Classic McEliece. We also hope to apply it during in-memory loading of evaluation points to improve recent side-channel attack results on post-quantum cryptosystem implementations.

Fig. 1 :Fig. 2 :

 12 Fig. 1: Power consumption of the loading function of the Goppa polynomial.

Fig. 3 :

 3 Fig. 3: Zoom on a pattern in power consumption of loading function of the coefficients of g(x).

Fig. 4 :

 4 Fig. 4: Difference of means of power traces for LSB=1 and LSB=0.

Table 1 :

 1 Table 1 shows the parameters of Classic McEliece proposed in[Cho+20] . The main component of decapsulation in Classic McEliece is inspired by Chou et al. [Cho17]. This paper presents a fast constant-time implementation of the "McBits" proposed by Bernstein et al. [BCS13]. They use the FFT (Fast Fourier Transform) algorithms for root finding and syndrome computation, the Beneš network algorithm for secret permutation, and bitslicing for low-level operations. Parameter sets: sizes of public keys, secret keys and ciphertexts in bytes 3 Template Attack on Classic McEliece

	Variant of KEM	m	n	t	Sec. level Public key Secret key Ciphertext
	mceliece348864	12	3488	64	1	261120	6492	128
	mceliece460896	13	4608	96	3	524160	13608	188
	mceliece6688128 13	6688	128	5	1044992	13932	240
	mceliece6960119 13	6960	119	5	1047319	13948	226
	mceliece8192128 13	8192	128	5	1357824	14120	240

Table 2 :

 2 Size of the search space in the case of Weak keys

	key level	#Search Space
	Weak keys in [LS01]	2 m(t-3) mt
	Weak keys with knowledge of coefficients Hamming weight	1
	Slightly less weak keys with coefficients Hamming weight equal to 1 Slightly less weak keys with coefficients Hamming weight equal to 2	( m 1 ) t t ( m 2 )

t t

  Therefore, we can upper bound the number Cirr of irreducible polynomials with the knowledge of the Hamming weights of the polynomial coefficients by With our template attack on the implementation of Classic McEliece, we significantly reduced the cost of the exhaustive search of the Goppa polynomial in F 2 m . As shown in Table3, the knowledge of the Hamming weights of the Goppa polynomial coefficients allowed us for example to divide the size of the search space by 2 441 for the variant of Classic McEliece with m = 13, n = 8192 and t = 128 from 2 1615 to 2 1174 . To date, we propose here the best complexity reduction for an exhaustive Goppa polynomial search.

	m	t	n	log 2 (Cirr)			log 2 ( Cirr)	log 2 (Cirr/ Cirr)
					δj = 1 δj = 2 δj = 3 δj = m/2
	12 64 3488	725	158	274	338	534	191
	13 96 4608	1199	251	425	521	871	328
	13 128 6688	1615	347	578	706	1174	441
	13 119 6960	1498	320	535	654	1089	409
	13 128 8192	1615	347	578	706	1174
						8	t m-8	t
				Cirr ≤	4 2 m (2 m -1)mt ⌊ m-8 2 ⌋	.	(9)
	5 Comparison with other key recovery attacks
	We recall that the decryption in Classic McEliece is equivalent to the syndrome
	decoding of Goppa binary codes, including the steps of computing the syndrome

Table 3 :

 3 Complexity to find Goppa polynomial with the knowledge of the Hamming weights of its coefficients from template attack against parameters of Classic McEliece[START_REF] Chou | Classic McEliece: conservative code-based cryptography 10 October 2020[END_REF] polynomial and the error locator polynomial and that of its evaluation at points in F 2 m . This polynomial evaluation over F 2 m is realized thanks to the implementation of the additive FFT after having calculated the error locator polynomial with the Berlekamp-Massey (BM) algorithm. Recently, Guo et al.[START_REF] Guo | A Key-Recovery Side-Channel Attack on Classic McEliece Implementations[END_REF] proposed a key-recovery side-channel attack on reference implementations (on FPGA and ARM Cortex-M4) [CC21; WSN18] of Classic McEliece. They design an attack algorithm in which they submit special ciphertexts to the decryption oracle that correspond to single error cases in the plaintexts. They exploited a leak in the additive FFT with a fixed input error before using a machine learningbased classification algorithm to determine the error locator polynomial. They choose a plaintext or error e of Hamming weight equal to 1 before encrypting it. Then, the profiled attack allows them to find the secret polynomial of the error locator among the 2 m possibilities and thus obtain an element of the supportL. Finally, they designed new algorithms to recover the Goppa irreducible polynomial and then the full secret key.

	Attack	Hamming weight	Target
	Guo et al. [GJJ22]	1	The FFT additive
			and BM algorithm
	Our attack	no constraints	Loading function
			of Goppa polynomial coefficients

Table 4 :

 4 Profiled side-channel attacks on Classic McEliece Countermeasures for the GJJ attack The main drawback of the key-recovery side-channel attack on Classic McEliece by Guo et al. [GJJ22] is the constraint on the Hamming weight of the plaintexts. This attack requires decrypting ciphertexts with Hamming weights of 1 to recover the secret in Classic McEliece.

https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.PDF

https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.

800-56Ar2.PDF 8 https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP. 800-56Br1.PDF

https://csrc.nist.gov/Projects/post-quantum-cryptography/ workshops-and-timeline/pqc-seminars

Acknowledgments

The author Jean Belo Klamti was supported by a grant of the Ripple Impact Fund/Silicon Valley Community Foundation (Grant 2018-188473).


Sakna Bazzi

Liangjian Hu

Emmanuelle Schulz

Mohamed Mellah

Electrogenerated Sm(II)-Catalyzed Carbon Dioxide Reduction for β-Hydrocarboxylation of Styrenes

Keywords: Samarium, Catalysis, Electrochemistry, Carbon dioxide reduction, Alkenes, Hydrocarboxylation

The synthesis of carboxylic acids from low-value materials such as alkenes using CO 2 as a C 1 -building block remains a real challenge for synthetic chemists from both reactivity and selectivity perspective. Electrochemical carboxylations have been examined but they remain limited, still suffering from a crucial lack of selectivity. Herein we report a new catalytic protocol based on an electrogenerated Sm(II) catalyst as a powerful CO 2 reductant, able to perform exclusively anti-Markovnikov hydrocarboxylation of alkenes. This electrochemical approach overcomes several current limitations and allows direct βhydrocarboxylation of styrene derivatives, in a regioselective manner.

INTRODUCTION

Carboxylation with carbon dioxide as an abundant and inexpensive C1-building block has gained a tremendous boost in organic synthesis, 1 providing an extremely attractive way to access valuable carboxylic acids which are important motifs in pharmaceuticals. 2 Among these reactions, the carboxylation of unsaturated hydrocarbons using CO 2 is a particularly attractive route. Ongoing efforts to develop robust chemical protocols for this direct hydrocarboxylation reaction were, however, hampered by the high kinetic and thermodynamic stability of CO 2 , requiring consequently the use of strong reducing agents in most cases and leading to additional constraints in terms of functional group tolerance. 3 In this context, tangible improvements have been made by transition metal catalysis and photocatalysis, with the control of the regioselectivity of the addition intimately linked to the structure of the considered olefin. 4 Aliphatic alkenes are indeed transformed into alkanoic acids, whereas the high stability of  3 -benzylic metal intermediates delivered mainly branched carboxylic acids from styrene derivatives. Therefore, organometallic catalysis faced a real obstacle in trying to shift the CO 2 fixation to the βposition for the latter. Recent reports have demonstrated that a specific design of organometallic nucleophiles is a primary requisite for the modulation of site selectivity and extension of substrates in hydrocarboxylation with CO 2 . 5 Earlier attempts to selectively generate linear carboxylic acids from styrenes and phenylacetylenes derivatives were limited to the use of organoboranes, 6 organozinc and Grignard reagents. [START_REF] Greenhalgh | Iron-Catalyzed, Highly Regioselective Synthesis of α-Aryl Carboxylic Acids from Styrene Derivatives and CO2[END_REF] The nickel-catalyzed hydrocarboxylation of unsaturated bonds has nevertheless been controlled by the group of Martín by using appropriate ligands for the metal center and water as a formal hydride source. [START_REF] Gaydou | Site-Selective Catalytic Carboxylation of Unsaturated Hydrocarbons with CO2 and Water[END_REF] Photochemical carboxylation was also recently proved successful as activation mode for the synthesis of linear carboxylic acids. 9 The electrochemical carboxylation of hydrocarbons was considered as an alternative very early on, but its development remained relatively limited due to the lack of selectivity. 10,11 For styrene transformation, site-selective hydrocarboxylations are hardly achieved and a mixture of α-and βhydrocarboxylation or dicarboxylation is mostly observed. [START_REF] Ballivet-Tkatchenko | Electrocatalytic Reduction of CO2 for the Selective Carboxylation of Olefins[END_REF] Major advances in selective electrochemical carboxylation reactions of styrenes using carbon dioxide have, however, been reported very recently (Scheme 1). Nam and co-workers indeed developed a direct electrochemical β-selective hydrocarboxylation of styrenes using CO 2 and water, in which the site selectivity was controlled between βhydrocarboxylation and dicarboxylation. [START_REF] Kim | Electrochemical β-Selective Hydrocarboxylation of Styrene Using CO2 and Water[END_REF] Malkov and Buckley also established an electrochemical protocol with triethanolamine as proton source delivering carboxylic acids from diversely substituted aryl-olefins with a high βregioselectivity. Building on our recent developments for catalytic reactions mediated by electrogenerated low valent samarium species 15 and particularly on the electrochemical carboxylation of aryl halides [START_REF] Bazzi | CO2 Activation by Electrogenerated Divalent Samarium for Aryl Halide Carboxylation[END_REF] and benzyl halides, [START_REF] Bazzi | Electrogenerated Sm(II)-Catalyzed CO2 Activation for Carboxylation of Benzyl Halides[END_REF] we report here an alternative electrocatalytic approach for the regioselective βhydrocarboxylation of low value styrene derivatives.

RESULTS AND DISCUSSION

We began our investigation towards the hydrocarboxylation of styrene 1a as a benchmark substrate using SmCl 3 as a precatalyst, a samarium rod as the cathode, and a stainlesssteel grid as the anode at 5 mA/cm 2 current density (Table 1). The electrolysis was conducted in an undivided electrochemical cell according to the procedure developed for the carboxylation of aryl and benzyl halides. [START_REF] Bazzi | CO2 Activation by Electrogenerated Divalent Samarium for Aryl Halide Carboxylation[END_REF][START_REF] Bazzi | Electrogenerated Sm(II)-Catalyzed CO2 Activation for Carboxylation of Benzyl Halides[END_REF] The optimization study was conducted in acetonitrile using CO 2(g) (1 atm). Water was initially chosen as a proton source after the reported accomplishments using the SmI 2 -H 2 O system for the reduction of challenging functional groups. 18 Even though a large quantity of the starting material was recovered, the monocarboxylic acid 2a was isolated as a unique product with 21% yield using 20 equivalents of H 2 O (Table 1, entry 1). Water was then replaced by various alcohols and t-BuOH promoted the targeted transformation, providing the best result with up to 32% yield for 2a (Table 1, entries 2-4). The effect of the amount of t-BuOH turned out to be crucial, since 3 equivalents led to a lower yield of the desired product (Table 1, entry 5) but 10 equivalents of t-BuOH were enough to produce exclusively the carboxylic acid 2a with 37% yield (Table 1, entry 6). Finally increasing the quantity of TMSCl from 6 equivalents to 8 equivalents allowed to isolate the carboxylic acid with a maximal yield of 47% (entry 7). Eventually, we found that using dry ice as CO 2 source was beneficial since the yield is significantly improved to 65% without modifications in the operating conditions (entry 8). At this stage it was verified that the increase in the efficiency of the reaction was not due to a possible addition of water to the reaction medium in the presence of dry ice (entry 9). The drop in temperature linked to the addition of dry ice is not responsible for the bet-ter yield of the reaction, as revealed by an electrolysis carried out at -40°C in the presence of CO 2(g) (entry 10). The catalytic loading was also evaluated, and it was found that 10 mol% are necessary to obtain the best results (compare in Table 1 entries 7 and11). The electrochemical nature of the reduction was proven by a blank experiment with no current applied, all other things being equal, which did not lead to any conversion (entry 12). It was observed that the stainless-steel electrode is not sacrificially oxidized; instead, chloride oxidation is likely at the anode. Encouraged by these results, we set out to investigate the preparative scope of the Sm(II)-catalyzed regioselective βhydrocarboxylation of styrene derivatives (Scheme 2). Initially, different styrenes bearing various substituents on the aromatic moiety, were evaluated, and proved all (1b-1f) to be compatible with the electrochemical conditions, affording the corresponding carboxylic acids with a complete regioselectivity. Nevertheless, the chlorinated derivative 1d suffered a dramatic decrease in the isolated yield of the targeted product (22 %), probably due to undesired dehalogenation reaction. To our delight, a (hetero)aromatic reagent such as 2vinylbenzofuran 1g was also tolerated and gave 3-(1benzofuran-2-yl) propionic acid 2g with 52% isolated yield. These electrochemical conditions also accept substituents on the vinyl group of styrene, providing exclusively βhydrocarboxylated products. In the case of α-substituted styrenes 1h and 1i, the corresponding monocarboxylated products were produced in good yields. As shown in Scheme 2, the hydrocarboxylation of βsubstituted styrenes bearing a methyl substituent (1j-m, transconfiguration) or cyclic ones (1o and 1p) delivered also the corresponding carboxylic acids in moderate to excellent yields (36-95%). A stilbene derivative (1n) underwent the transformation smoothly and provided the desired carboxylic acid, although in a moderate yield, probably due to steric hindrance. Moreover, the more sterically demanding α,β-disubstituted styrene 1q was also reactive under these conditions. It was however found that the presence of a hydroxymethyl or a cyano group on the substrate (1r and 1s) fully inhibited the reaction and returned significant amounts of starting materials. This observation can be rationalized with the high tendency of samarium to strongly coordinate to such substituents, which may lead to catalyst quenching. In the case of substrate 1t bearing a nitro group, substantial conversion to degradation products was detected in the crude. These side reactions were attributed to the propensity of Sm species to reduce nitro functions. 15a Interestingly, vinyl bromides 1u and 1v were also prone to dehalogenation, furnishing exclusively 2a as final product with comparable yields to the one obtained from 1a.

We then investigated the mechanism of this electrocatalytic hydrocarboxylation. Our studies were first focused on assigning the role of each component present in the electrochemical cell. Without the catalyst or t-BuOH, the transformation of styrenes showed inertia with respect to direct electrocarboxylation; it led indeed to considerable degradation but without any formation of carboxylic acid. In the absence of TMSCl, only 8% of 2a were produced. Replacing the samarium cathode with a glassy carbon one in the presence of SmCl 3 also resulted in complete degradation of the substrate. This is in line with our previous studies, 15b in which screening of cathode materials for reduction of Sm(III) salts was found to be possible only with Sm as the cathode. These blank exper-

Sm (-) / SS (+) SmCl 3 Cat., 5 mA/cm 2 ROH, TMSCl nBu 4 NPF 6 , CH 3 CN, r.t., 4h 1a
+ CO 2 COOH 2a
iments indicate that, in our case, the samarium activation of CO 2 is mandatory to perform the electrocarboxylation of such unsaturated products. Deuterium labeling experiments were then conducted to elucidate the protonation step. We first explored the hydrocarboxylation of 1a followed by DCl quench but 2a was isolated without any deuterium fixation. Surprisingly, the addition of t-BuOD, supposed to be the proton donor, also delivered the deuterium-free product. Lastly, the reaction was performed in CD 3 CN and interestingly, 2a' was isolated with more than 99% deuterium incorporation on the benzylic position (Scheme 3). At this point, we hypothesized that this specific behavior of acetonitrile was triggered by its coordination at the Sm center, which makes the protons much more acidic and thus explains the observed proton-donating character. Noteworthy, this behavior was also reported with transition-metal based catalysts. [START_REF] Bissember | α-CyanoCarbanion Complexes and their Application in Synthesis[END_REF] We accordingly propose that after CH 3 CN deprotonation, the simple coordination of Sm(III) via the nitrogen atom (Sm-NCCH 3 ) is transformed into a strong Sm-CH 2 CN bond. At this stage, t-BuOH, known as noncoordinating alcohol 20 and activated by TMSCl, can therefore be deprotonated by the generated carbanion, thus leading to the dissociation of the Sm(III) species.

Scheme 2: Substrate Scope of Styrene Derivatives. Scheme 3: Deuterium Labeling Experiments.

To furtherly clarify the mechanism, attempts to quench a radical intermediate were made with indene 1p as starting material. In this case, the addition of a specific amount of 2,2,6,6tetramethylpiperidin-1-yl)oxyl TEMPO (2 equiv.) led to complete inhibition of the hydrocarboxylation. Extending the reaction time to 8 hours of electrocatalysis made it possible to restore the reactivity, and finally, the expected product 2p was isolated with the same yield as without TEMPO (see SI). As already described in our previous work, [START_REF] Bazzi | CO2 Activation by Electrogenerated Divalent Samarium for Aryl Halide Carboxylation[END_REF] this result shows that the radical scavenger did not deactivate the catalyst. We rather propose that it was initially neutralized by the CO 2  -radical anion formed to lead to an unstable, not isolable intermediate, to explain the reactivity found after complete consumption of TEMPO.

R 3 R 4 R 2 R 1 SmCl 3 (10 mol%) 5 mA/cm 2 CO 2 tBuOH, TMSCl R 3 R 4 R 2 R 1 CO 2 H nBu 4 NPF 6, CH 3 CN, r.t., 4h 1 a-v 2 a-v R 1 2a R 1 = H, 65% 2b R 1 = 4-Me, 61% 2c R 1 = 4-F, 42% 2d R 1 = 4-Cl, 22% 2e R 1 = 2-Me, 95% 2f R 1 = 2-OMe, 45% R 1 1r R 1 = CH 2 OH 1s R 1 = CN 1t R 1 = NO 2 No reaction CO 2 H CO 2 H 2p, 62% 2g, 52% O CO 2 H CO 2 H 2h, 60% 2i
To gain insight into the electrochemical behavior of the species present in the solution, a series of cyclic voltammetry experiments were carried out. These studies were initiated by determining the behavior of each reactant in the electrochemical medium. The reduction potentials of various styrene derivatives have been described, with potential values lower than -2.4 V vs Ag/Ag + . [START_REF] Kim | Electrochemical β-Selective Hydrocarboxylation of Styrene Using CO2 and Water[END_REF] These values have been nevertheless determined in our electrochemical conditions (see SI) confirming that all substrates are more difficult to reduce than the Sm(III) species. The cyclic voltammogram of SmCl 2 electrogenerated from SmCl 3 in CH 3 CN containing nBu 4 NPF 6 as supporting electrolyte is presented in Figure 1. It shows a quasi-reversible system with a redox potential around -1.5 V/SCE (Red curve (1) in Figure 1). Addition of CO 2 caused the loss of the oxidation wave of SmCl 2 while the reduction wave persisted with a slight cathodic shift to -1.6 V/SCE (Black curve (2) in Figure 1). This result indicates that a chemical reaction is taking place between CO 2 and Sm(II), releasing another Sm(III) complex. Moreover, when adding a solution (1 mL) containing styrene 1a (3.10 -3 M), t-BuOH (10 equiv.) and TMSCl (8 equiv.) in CH 3 CN, a massive reduction wave emerged (Dashed black curve (3) in Figure 1). This electrochemical behavior shows the existence of a catalytic current, proving that the hydrocarboxylation was catalyzed by SmCl 2 . 21 Consequently, we propose the following mechanism for the hydrocarboxylation of alkenes (Scheme 4). Firstly, the electrogenerated Sm(II) species reduces selectively the CO 2 and generates the corresponding radical anion A as a samarium carboxylate. 22 This latter undergoes an anti-Markovnikov addition onto the unsaturated substrate to produce the benzylic radical B which after transmetallation with TMSCl is rapidly reduced by a second equivalent of Sm(II) to the carbanion C.

In the mixture, the t-BuOH, activated by TMSCl, is essential for the reaction. Therefore, we suggest a mechanism displaying two successive proton donations: the first one involves the solvent CH 3 CN that after its activation by the catalyst transfers one proton to form the product D after hydrolysis. The CH 2 CN -anion extracts the nearest activated proton, from the t-BuOH-TMSCl adduct, to restore its original structure and dissociate the Sm(III) to be regenerated on the cathode. This mechanistic proposal is based in particular on the deuterium labeling experiments that were carried out. However, possible H/D exchanges between t-BuOH and acetonitrile could not be excluded under the reaction conditions. Scheme 4: Proposed Mechanism for the Catalytic β-Hydrocarboxylation of Alkenes.

CONCLUSION

In summary, we have developed the regioselective hydrocarboxylation of styrene derivatives via CO 2 activation, catalyzed by a reductive SmCl 2 complex in acetonitrile. This reaction showed remarkable anti-Markovnikov selectivity to give the aliphatic carboxylic acids in good to excellent yields. Several experimental investigations allowed identifying the role of each species present in this reaction. Foremost, after various blank tests, it was proven that SmCl 2 catalyzes this reaction assisted by acetonitrile and t-BuOH. Electrochemical measurements confirmed the existence of a catalytic process.

EXPERIMENTAL SECTION

General Procedure for the catalytic carboxylation of styrene derivatives An undivided cell charged with tetrabutylammonium hexafluorophosphate nBu 4 NPF 6 (1 mmol, 387 mg) in acetonitrile (40 mL), equipped with a samarium rod as the cathode and a stainless-steel as the anode, was used. The electrogeneration of Sm 2+ from SmCl 3 (0.1 mmol, 26 mg) was started by setting the chronopotentiometry mode for 15000 seconds with i = 5 mA/cm 2 . The dry ice was carefully added to the mixture in small pieces followed by the alkene (1.0 mmol, 104 mg in the case of styrene), t-BuOH (10 mmol, 741mg) and trimethylsilyl chloride (8 mmol, 869 mg). During the electrolysis, small pieces of dry ice were added each 15 min. After 4 hours of electrolysis, the reaction was quenched with diethyl ether Et 2 O (10 mL), and the solvent was evaporated. To the obtained solid, a solution of HCl (2 M) was added and the aqueous solution was extracted with Et 2 O (2 x 30 mL). The combined organic phase was washed with water and brine and dried over anhydrous MgSO 4 . The solvent evaporation under vacuo furnished the product that was purified by column chromatography on silica gel (90/10 then 50/50 PE/ EtOAc).

3-phenylpropanoic acid (2a): 97.5 mg (0.65 mmol, 65%). 1 H NMR (360 MHz, CDCl 3 ) δ 11.31 (br, 1H), 7.42-7.32 (m, 5H), 3.08 (t, J = 7.5 Hz, 2H), 2.80 (t, J = 7.6 Hz, 2H). [START_REF] Kim | Electrochemical β-Selective Hydrocarboxylation of Styrene Using CO2 and Water[END_REF] C NMR (75 MHz, CDCl 3 ) δ 177. 8, 140.1, 128.5, 128.2, 126.3, 35.3, 30.5.

The 1 H NMR and [START_REF] Kim | Electrochemical β-Selective Hydrocarboxylation of Styrene Using CO2 and Water[END_REF] C NMR spectra are in agreement with those reported in the literature. 9c 3-phenylpropanoic acid (2a): 90.0 mg (0.60 mmol, 60 %) was also prepared starting from 1u (183.0 mg, 1 mmol) or 97.5 mg (0.65 mmol, 65%) from 1v (183.0 mg, 1 mmol).

3-(p-tolyl)propanoic acid (2b): 100 mg (0.61 mmol, 61% 6, 140.1, 128.5, 128.2, 126.3, 35.5, 30.5.

The 1 H NMR and [START_REF] Kim | Electrochemical β-Selective Hydrocarboxylation of Styrene Using CO2 and Water[END_REF] C NMR spectra are in agreement with those reported in the literature. 9c 3-(o-tolyl)propanoic acid (2e): 156 mg (0.95 mmol, 95%). 1 H NMR (300 MHz, CDCl 3 ) δ 11.56 (br, 1H), 7.24 (m, 4H), 3.05 (t, J = 7.0 Hz, 2H), 2.80 -2.67 (t, J = 7.0 Hz, 2H), 2.42 (s, 3H). [START_REF] Kim | Electrochemical β-Selective Hydrocarboxylation of Styrene Using CO2 and Water[END_REF] C NMR (75 MHz, CDCl 3 ) δ 179. 8, 138.3, 136.0, 130.4, 128.5, 126.6, 126.2, 34.4, 28.0, 19.3. The 1 H NMR and [START_REF] Kim | Electrochemical β-Selective Hydrocarboxylation of Styrene Using CO2 and Water[END_REF] C NMR spectra are in agreement with those reported in the literature. [START_REF] Shabbi | Pd Nanoparticles on Reverse Phase Silica Gel as Recyclable Catalyst for Suzuki-Miyaura Cross Coupling Reaction and Hydrogenation in Water[END_REF] 3-(2-methoxyphenyl)propanoic acid (2f): 81 mg (0.45 mmol, 45%). 1 H NMR (300 MHz, CDCl 3 ) δ 7.30 -7.14 (m, 2H), 6.90 (dd, J = 14.3, 7.6 Hz, 2H), 3.85 (s, 3H), 2.98 (t, J = 7.7 Hz, 2H), 2.69 (t, J = 7.7 Hz, 2H). [START_REF] Kim | Electrochemical β-Selective Hydrocarboxylation of Styrene Using CO2 and Water[END_REF] C NMR (75 MHz, CDCl 3 ) δ 179. 8, 157.4, 129.9, 128.4, 127.7, 120.4, 110.2, 55.1, 34.0, 25.8. The 1 H NMR and [START_REF] Kim | Electrochemical β-Selective Hydrocarboxylation of Styrene Using CO2 and Water[END_REF] C NMR spectra are in agreement with those reported in the literature. [START_REF] Shabbi | Pd Nanoparticles on Reverse Phase Silica Gel as Recyclable Catalyst for Suzuki-Miyaura Cross Coupling Reaction and Hydrogenation in Water[END_REF] 3-(benzofuran-2-yl)propanoic acid (2g): 99 mg (0.52 mmol, 52%). 1 H NMR (360 MHz, CDCl 3 ) δ 7.52 -7.45 (m, 1H), 7.41 (d, J = 7.7 Hz, 1H), 7.20 (td, J = 14.1, 7.1 Hz, 2H), 6.45 (s, 1H), 3.13 (t, J = 7.5 Hz, 2H), 2.84 (t, J = 7.5 Hz, 2H). [START_REF] Kim | Electrochemical β-Selective Hydrocarboxylation of Styrene Using CO2 and Water[END_REF] C NMR (91 MHz, CDCl 3 ) δ 177.2, 156. 8, 154.6, 128.5, 123.4, 122.6, 120.5, 110.8, 102.6, 31.8, 23.7. The 1 H NMR and [START_REF] Kim | Electrochemical β-Selective Hydrocarboxylation of Styrene Using CO2 and Water[END_REF] C NMR spectra are in agreement with those reported in the literature. 9c 3-phenylbutanoic acid (2h): 94.5 mg (0.60 mmol, 60%). 1 H NMR (360 MHz, CDCl 3 ) δ 7.49 -7.13 (m, 5H), 3.41 -3.24 (m, 1H), 2.76 -2.59 (m, 2H), 1.37 (d, J = 7.0 Hz, 3H). [START_REF] Kim | Electrochemical β-Selective Hydrocarboxylation of Styrene Using CO2 and Water[END_REF] C NMR (91 MHz, CDCl 3 ) δ 178. 7, 145.4, 128.5, 126.7, 126.5, 42.6, 36.1, 21.8. The 1 H NMR and [START_REF] Kim | Electrochemical β-Selective Hydrocarboxylation of Styrene Using CO2 and Water[END_REF] C NMR spectra are in agreement with those reported in the literature. 9c 3,3-diphenylpropanoic acid (2i): 113 mg (0.50 mmol, 50%). 1 H NMR (360 MHz, CDCl 3 ) δ 7.55 -7.08 (m, 10H), 4.58 (t, J = 7.9 Hz, 1H), 3.14 (d, J = 7.9 Hz, 2H). [START_REF] Kim | Electrochemical β-Selective Hydrocarboxylation of Styrene Using CO2 and Water[END_REF] C NMR (75 MHz, CDCl 3 ) δ 178. 0, 143.1, 128.6, 127.5, 126.6, 46.6, 40.4. The 1 H NMR and [START_REF] Kim | Electrochemical β-Selective Hydrocarboxylation of Styrene Using CO2 and Water[END_REF] C NMR spectra are in agreement with those reported in the literature. 9c 2-methyl-3-phenylpropanoic acid (2j): 156 mg (0.95 mmol, 95%). 1 H NMR (360 MHz, CDCl 3 ) δ 10.70 (br, 1H), 7.50 -7.14 (m, 5H), 3.14 (dd, J = 13.3, 6.2 Hz, 1H), 2.82 (dq, J = 13.2, 6.8 Hz, 1H), 2.73 (dd, J = 13.3, 8.0 Hz, 1H), 1.23 (d, J = 6.9 Hz, 3H). [START_REF] Kim | Electrochemical β-Selective Hydrocarboxylation of Styrene Using CO2 and Water[END_REF] C NMR (91 MHz, CDCl 3 ) δ 182. 8, 139.1, 129.0, 128.5, 126.5, 41.3, 39.3, 16.5. 1 H NMR and [START_REF] Kim | Electrochemical β-Selective Hydrocarboxylation of Styrene Using CO2 and Water[END_REF] C NMR spectra are in agreement with those reported in the literature. 9c 3-(3,4-dimethoxyphenyl)-2-methylpropanoic acid (2k): 80 mg (0.36 mmol, 36%). 1 H NMR (360 MHz, CDCl 3 ) δ 6.76 (m, 3H), 3.85 (s, 6H), 3.01 (dd, J = 13.4, 6.5 Hz, 1H), 2.73 (dq, J = 13.5, 6.9 Hz, 1H), 2.63 (dd, J = 13.4, 7.8 Hz, 1H), 1.18 (d, J = 6.9 Hz, 3H). [START_REF] Kim | Electrochemical β-Selective Hydrocarboxylation of Styrene Using CO2 and Water[END_REF] C NMR (91 MHz, CDCl 3 ) δ 182. 3, 148.7, 147.5, 131.5, 121.0, 112.1, 111.1, 55.8, 55.7, 41.4, 38.9, 16.4. 1 H NMR and [START_REF] Kim | Electrochemical β-Selective Hydrocarboxylation of Styrene Using CO2 and Water[END_REF] C NMR spectra are in agreement with those reported in the literature. [START_REF] Cueva | Probing the Steric Space at the Floor of the D1 Dopamine Receptor Orthosteric Binding Domain: 7α-, 7β-, 8α-, and 8β-Methyl Substituted Dihydrexidine Analogues[END_REF] 3-(benzo [d][1,3]dioxol-5-yl)-2-methylpropanoic acid (2l): 93 mg (0.45 mmol, 45%). 1 H NMR (360 MHz, CDCl 3 ) δ 6.69 (m, 3H), 5.94 (s, 2H), 3.00 (dd, J = 13.4, 6.5 Hz, 1H), 2.71 (m, 1H), 2.62 (dd, J = 13.4, 7.8 Hz, 2H), 1.19 (d, J = 6.9 Hz, 3H). [START_REF] Kim | Electrochemical β-Selective Hydrocarboxylation of Styrene Using CO2 and Water[END_REF] C NMR (91 MHz, CDCl 3 ) δ 182. 4, 147.6, 146.1, 132.7, 121.9, 109.3, 108.1, 100.8, 41.4, 39.0, 16.4. 1 H NMR and [START_REF] Kim | Electrochemical β-Selective Hydrocarboxylation of Styrene Using CO2 and Water[END_REF] C NMR spectra are in agreement with those reported in the literature. [START_REF] Schulze | Synthesis of 2-Arylethylamines by the Curtius Rearrangement[END_REF] 3-(4-methoxyphenyl)-2-methylpropanoic acid (2m): 105 mg (0.54 mmol, 54%). 1 H NMR (360 MHz, CDCl 3 ) δ 7.14 (d, J = 8.6 Hz, 2H), 6.87 (d, J = 8.6 Hz, 2H), 3.83 (s, 3H), 3.05 (dd, J = 13.3, 6.3 Hz, 1H), 2.85 -2.71 (m, 1H), 2.67 (dd, J = 13.3, 7.8 Hz, 1H), 1.21 (d, J = 6.8 Hz, 3H). [START_REF] Kim | Electrochemical β-Selective Hydrocarboxylation of Styrene Using CO2 and Water[END_REF] C NMR (91 MHz, CDCl 3 ) δ 182. 4, 158.2, 131.1, 129.9, 113.9, 55.2, 41.4, 38.4, 16.4. 1 H NMR and [START_REF] Kim | Electrochemical β-Selective Hydrocarboxylation of Styrene Using CO2 and Water[END_REF] C NMR spectra are in agreement with those reported in the literature. [START_REF] Zhu | Pd-Catalysed Ligand-Enabled Carboxylate-Directed Highly Regioselective Arylation of Aliphatic Acids[END_REF] 2,3-diphenylpropanoic acid (2n): 158 mg (0.7 mmol, 70%). 1 H NMR (300 MHz, CDCl 3 ) δ 10.16 (br, 1H), 7.65 -6.97 (m, 10H), 3.94 (t, J = 7.7 Hz, 1H), 3.49 (dd, J = 13.8, 8.3 Hz, 1H), 3.11 (dd, J = 13.8, 7.1 Hz, 1H). [START_REF] Kim | Electrochemical β-Selective Hydrocarboxylation of Styrene Using CO2 and Water[END_REF] C NMR (75 MHz, CDCl 3 ) δ 179.6, 138.7, 137.9, 128.9, 128.7, 128.4, 128.1, 127.6, 126.5, 53.5, 39.3. 1 H NMR and [START_REF] Kim | Electrochemical β-Selective Hydrocarboxylation of Styrene Using CO2 and Water[END_REF] C NMR spectra are in agreement with those reported in the literature. [START_REF] Meng | Photocarboxylation of Benzylic C-H Bonds[END_REF] 1,2,3,4-tetrahydronaphthalene-2-carboxylic acid (2o): 126 mg (0.73 mmol, 73%). 1 H NMR (300 MHz, CDCl 3 ) δ 11.42 (br 1H), 7.38 -7.03 (m, 4H), 3.13 (d, J = 7.3 Hz, 2H), 3.01 -2.81 (m, 3H), 2.34 (m, 1H), 1.98 (m, 1H). [START_REF] Kim | Electrochemical β-Selective Hydrocarboxylation of Styrene Using CO2 and Water[END_REF] C NMR (63 MHz, CDCl 3 ) δ 181. 4, 135.6, 134.6, 129.1, 128.9, 126.0, 125.9, 39.7, 31.3, 28.4, 25.6. 1 H NMR and [START_REF] Kim | Electrochemical β-Selective Hydrocarboxylation of Styrene Using CO2 and Water[END_REF] C NMR spectra are in agreement with those reported in the literature. 9c 2,3-dihydro-1H-indene-2-carboxylic acid (2p): 100 mg (0.62 mmol, 62%). 1 H NMR (360 MHz, CDCl3) δ 7.35 -7.13 (m, 4H), 3.49 -3.23 (m, 5H). [START_REF] Kim | Electrochemical β-Selective Hydrocarboxylation of Styrene Using CO2 and Water[END_REF] C NMR (63 MHz, CDCl3) δ 182. 0, 141.3, 126.7, 124.4, 43.4, 36.0. 1 H NMR and [START_REF] Kim | Electrochemical β-Selective Hydrocarboxylation of Styrene Using CO2 and Water[END_REF] C NMR spectra are in agreement with those reported in the literature. 9c 2,3-diphenylbutanoic acid (2q): 166 mg (0.44 mmol, 44%). 1 H NMR (360 MHz, CDCl 3 ) δ 7.76 -6.87 (m, 10H), 3.72 (d, J = 11.2 Hz, H), 3.54 -3.33 (m, 1H), 1.03 (d, J = 7.0 Hz, 3H). [START_REF] Kim | Electrochemical β-Selective Hydrocarboxylation of Styrene Using CO2 and Water[END_REF] C NMR (91 MHz, CDCl 3 ) δ 178.2, 144.5, 137.0, 130.4, 128.4, 127.7, 127.3, 126.4, 59.1, 42.9, 19.9. HRMS (m/z) [M + Na]+ calculated 263.1048, found 263.0995.

Figure 1 .

 1 Figure 1. Electrochemical behavior of SmCl 3 with styrene 1a. Cyclic voltammetry performed using a GC electrode (20 mm 2 ) and a Pt wire as counter electrode with a scanning potential between -0.5 and -2 V vs. SCE in CH 3 CN with nBu 4 NPF 6 [0.1 M]. Scan rate: 100 mV/s. Red curve (1): 0.02 M SmCl 3 in 0.1 M nBu 4 NPF 6 in CH 3 CN; black curve (2): after introduction of CO 2 ; dashed curve (3): addition of 1 mL of t-BuOH/TMSCl/1a (10/8/1).

14 Scheme 1. Electrochemical β-Hydrocarboxylation of Styrenes with CO 2 .

Table 1 . Optimization of the Reaction Conditions

 1

	Entry	SmCl 3 mol%	ROH (equiv)	TMSCl equiv.	2a (%) a
	1	10	H 2 O (20)	6	21
	2	10	MeOH (20)	6	9
	3	10	EtOH (20)	6	13
	4	10	t-BuOH (20)	6	32
	5	10	t-BuOH (3)	6	21
	6	10	t-BuOH (10)	6	37
	7	10	t-BuOH (10)	8	47
	8 b	10	t-BuOH (10)	8	65
	9 10 c	10 10	t-BuOH (10) + H 2 O (10) t-BuOH (10)	8 8	45 -
	11	5	t-BuOH (10)	8	30
	12 d	10	t-BuOH (10)	8	-
	a Isolated yields.

b CO 2(g) was replaced by dry ice (1 atm). c re- action performed at -40 °C. d no current applied, 24h.

ACKNOWLEDGMENT

e thank the CNRS, the Minist re de l' nseignement Supérieur et de la Recherche, the China Scholarship Council (CSC) for a grant to LH and the Charm3at LABEX (ANR-11-Labex-0039) for financial support.

ASSOCIATED CONTENT

Supporting Information. The Supporting Information is available free of charge at https://..... Experimental procedures, cyclic voltammograms, compounds data and spectra (PDF).

AUTHOR INFORMATION Corresponding Author

* E-mail: mohamed.mellah@universite-paris-saclay.fr ORCID Sakna Bazzi: 0000-0003-0183-4819 Emmanuelle Schulz: 0000-0002-0844-8825 Mohamed Mellah: 0000-0002-8006-8149

Author Contributions

SB and LH collected the data and performed the analyses. SB, ES and MM conceived and designed the work and contributed to the writing of the manuscript.

Authors are required to submit a graphic entry for the Table of Contents (TOC) that, in conjunction with the manuscript title, should give the reader a representative idea of one of the following: A key structure, reaction, equation, concept, or theorem, etc., that is discussed in the manuscript. Consult the journal's Instructions for Authors for TOC graphic specifications.

Insert Table of Contents artwork here