Sylvie Claeysen

Michèle Sebben

Carine Becamel

Marie-Laure Parmentier

Aline Dumuis

Joël Bockaert

Carine Bécamel

Constitutively active mutants of 5-HT 4 receptors are they in unique active states?

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

INTRODUCTION

Recent models describing activation of G-protein coupled receptors (GPCRs) propose the existence of an equilibrium between two functionally distinct states of [R]: the inactive R and the active R* states governed by the allosteric constant J = [R]/[R*]. This two-state allosteric model was introduced by [START_REF] Monod | On the nature of allosteric transitions: a plausible model[END_REF] and applied to GPCRs by [START_REF] Samama | A mutation-induced activated state of the β2-adrenergic receptor. Extending the ternary complex model[END_REF] and [START_REF] Leff | The two-state model of receptor activation[END_REF]. In the absence of agonists, the equilibrium between R and R* determines the level of basal receptor activity. The efficacy of a ligand is thought to be a function of its relative affinity for R and R*. Neutral antagonists have equal affinity for both states, agonists have a higher affinity for R*, whereas inverse agonists have a higher affinity for R [START_REF] Kjelsberg | Constitutive activation of the α1B-adrenergic receptor by all amino acid substitutions at a single site[END_REF][START_REF] Samama | A mutation-induced activated state of the β2-adrenergic receptor. Extending the ternary complex model[END_REF][START_REF] Kenakin | The classification of seven transmembrane receptors in recombinant expression systems[END_REF]. In the absence of agonists, it can therefore be expected that the percentage of GPCRs in the R* state is low due to important conformational constraints that are released upon activation [START_REF] Scheer | Constitutively active mutants of the α1B-adrenergic receptor: role of highly conserved polar amino acids in receptor activation[END_REF][START_REF] Gether | Structural instability of a constitutively active G protein-coupled receptor. Agonist-independent activation due to conformational flexibility[END_REF][START_REF] Gether | G protein-coupled receptors. II. Mechanism of agonist activation[END_REF]. Previously, we have experimentally determined the J constant for wild type (WT) 5-HT4 receptors (5-HT4Rs) expressed in COS-7 cells, and found it to be equal to 6.15, thus indicating that 14% of receptors were in the R* state in the absence of ligands [START_REF] Claeysen | Pharmacological properties of the 5-hydroxytryptamine4 receptor antagonists on constitutively active wild-type and mutated receptors[END_REF]. However, a large series of mutated GPCRs have been found to have a high constitutive activity in the absence of agonists. When naturally occurring, these mutations initiate human diseases such as retinitis pigmentosa, toxic hyperthyroid adenomas, precocious puberty and neonatal severe hypercalcaemia [START_REF] Van Sande | Somatic and germline mutations of the TSH receptor gene in thyroid diseases[END_REF][START_REF] Spiegel | Defects in G protein-coupled signal transduction in human disease[END_REF]. In this context, the molecular changes underlying the conversion of R to R* are of particular importance, which despite the progress made in this direction using the information provided by the functional analysis of mutated receptors and from molecular dynamic analysis [START_REF] Scheer | Constitutively active mutants of the α1B-adrenergic receptor: role of highly conserved polar amino acids in receptor activation[END_REF][START_REF] Bockaert | Molecular tinkering of G protein-coupled receptors: an evolutionary success[END_REF] are still poorly understood. One fundamental question is to know whether activating mutations results from an alteration of the J constant, as generally thought [START_REF] Tiberi | High agonist-independent activity is a distinguishing feature of the dopamine D1B receptor subtype[END_REF][START_REF] Scheer | Constitutively active mutants of the α1B-adrenergic receptor: role of highly conserved polar amino acids in receptor activation[END_REF], or if different R* conformations are generated.

We have shown recently that two constitutively active 5-HT4Rs, an i3 loop mutant (A258L) and a C-terminal truncated mutant (Δ327), are characterized by a modification of the J constant [START_REF] Claeysen | Pharmacological properties of the 5-hydroxytryptamine4 receptor antagonists on constitutively active wild-type and mutated receptors[END_REF]. The J constant modification led to an increase of the relative concentration of R* from 14% in WT to 56% in the mutants [START_REF] Claeysen | Pharmacological properties of the 5-hydroxytryptamine4 receptor antagonists on constitutively active wild-type and mutated receptors[END_REF].

The aim of this study was to compare and analyse the thermal denaturation kinetics of a series of constitutively active mutated 5-HT4Rs, and to determine whether they can be described by a simple change in the J constant, or if they reveal an additional change in the R* conformation.

RESULTS AND DISCUSSION

We first compared the structural stability of WT 5-HT4Rs to that of two mutated 5-HT4Rs, the truncated C-terminal 5-HT4R (Δ327) and the i3 (third intracellular loop) 5-HT4R (A258L) mutant [START_REF] Claeysen | Pharmacological properties of the 5-hydroxytryptamine4 receptor antagonists on constitutively active wild-type and mutated receptors[END_REF]. All three receptors were expressed at similar expression density in COS-7 cells (2000-3000 fmol/mg). The mutated 5-HT4Rs had a high constitutive activity, as previously described [START_REF] Claeysen | Pharmacological properties of the 5-hydroxytryptamine4 receptor antagonists on constitutively active wild-type and mutated receptors[END_REF] and illustrated in Figure 1A.

The WT receptor was particularly stable, such that after a 3 h incubation period at 45°C, no significant denaturation was observed (Figure 1B). However, over the same time period, a 50% denaturation was obtained with the mutated receptors, indicating that the constitutive activation of the 5-HT4Rs was associated with thermal instability, as previously shown for β2-adrenergic receptors and histamine H2 receptors [START_REF] Gether | Structural instability of a constitutively active G protein-coupled receptor. Agonist-independent activation due to conformational flexibility[END_REF][START_REF] Alewijnse | The effect of mutations in the DRY motif on the constitutive activity and structural instability of the histamine H(2) receptor[END_REF]. Experiments were then performed to compare the t1/2 of denaturation of WT and mutated receptors at 55°C. A 3 h incubation period led to 75% of denaturation of WT and an almost complete denaturation of the mutated receptors (Figure 1B andC).

Western blot analysis of WT and truncated 5-HT4R (Δ327) indicated that denaturation at 55°C was not associated with a significant proteolysis of receptor proteins (Figure 1E). We also verified that WT, 5-HT4 (Δ327) and 5-HT4 (A258L) receptors were similarly targeted to the plasma membranes, as indicated by immunofluorescence observations and [3H]GR 113808 binding measured in intact cells at 4°C (see Figure 2A andB). Note that the ratio between the number of [ 3 H]GR 113808 binding sites determined in intact cells and in particulate fractions was identical, regardless of the nature of the receptor expressed, WT or mutated (Figure 2).

Although we may have expected a higher proportion of mutated receptors in intracellular domains, either due to desensitization and internalization of constitutively active receptors or to misfolding, this was not the case in the present study.

The denaturation kinetics of WT, 5-HT4 (Δ327) and 5-HT4 (A258L) mutant receptors were clearly different (Figure (Figure1C).1C). As expected, the denaturation rates were also independent of receptor density, such that no significant differences were observed when denaturation was carried out on membranes prepared from COS-7 cells expressing low or high levels of receptors (data not shown).

A semi-logarithmic transformation of the time-courses (Log[Rt]/[Rt0] as the function of t with

[Rt]= [R] + [R*] and [Rt0] = [R0] + [R*0]
being the total R concentration [ 3 H]GR 113808 labeled receptors at t and t = 0 respectively, allowed the calculation of the t1/2 of denaturation. For the WT, 5-HT4 (Δ327) and 5-HT4 (A258L) mutant receptors they were equal to 70 ± 4 (n = 10), 17 ± 4 (n = 6) and 48 ± 5 (n = 6) min, respectively (Figure 1D).

We then measured the t1/2 of denaturation of other constitutively active mutants (Figure 3). Some were truncated within the end of C-terminal tail (Δ358, Δ346) but have kept the two putatively palmitoylated cysteines (C328, C329), which are likely to anchor 5-HT4 receptors to the membrane, as shown for many GPCRs. These cysteines are certainly of crucial structural importance since, in addition to being palmitoylated, they have been found to be at the Cterminus of an additional helix (helix VIII) in the crystal structure of rhodopsin [START_REF] Palczewski | Crystal structure of rhodopsin: A G protein-coupled receptor[END_REF]. In two others constitutively active mutants, one (C329S) or two (C328-329S) of these cysteines have been substituted with a serine (Figure 3A andB). In many GPCRs, including the β2-adrenergic receptors, mutation of palmitoylated cysteines leads to constitutively active receptors [START_REF] Moffett | Palmitoylated cysteine 341 modulates phosphorylation of the β2-adrenergic receptor by the cAMP-dependent protein kinase[END_REF].

The classification of these mutants in order of increasing levels of constitutive activity, were as 3B). The corresponding t1/2 of denaturation determined as described in Figure 1 The denaturation kinetics displayed only one slope, indicating that the denaturation of only one protein conformation was followed (Figures 1D and3C). One could argue that we followed the denaturation of R* rather than that of R since R* is the more unstable structure. It is likely that, following denaturation of R*, the R→R* equilibrium was shifted to the R* form at a much faster rate than the denaturation rate of R*. Therefore, under our experimental conditions, the observed denaturation kinetic was mainly governed by the denaturation rate of R*. Thus, equation 2 becomes: (equation 3) and (equation 4).

follows: WT = Δ358 < C329S < Δ346 < C328-329S < Δ327 < A258L (Figure
We had previously determined the J constant for the WT and two constitutively active mutants [5-HT4R (Δ327) and 5-HT4R (A258L)] [START_REF] Claeysen | Pharmacological properties of the 5-hydroxytryptamine4 receptor antagonists on constitutively active wild-type and mutated receptors[END_REF]. Similar experiments allowed us to determine in this study the J constants for the other mutants described (see Figure 3 legend).

Therefore, we plotted t1/2 against (1 + J) for the WT receptor and the different constitutively active mutants (Figure 3D).

We could see that all the points, except the i3 mutant (A258L), could be fitted by a linear regression (Figure 3D). Indeed, for these points, the regression t1/2= a (1 + J) was positive and significant (a = 9.7 ± SE 0.46, p <0.0001). Moreover, neither the inclusion of an non-zero intercept (t1/2 = a (1 + J) + b) nor the inclusion of a quadratic term (t1/2 = a (1 + J) 2 + b(1 + J) + c) significantly improved the fit of the regression (F1,5 = 0.66, NS and F1,4 = 0.41, NS). Therefore, for the set of WT and C-tail mutants, t1/2 was proportional to (1 + J) as predicted by the model. The denaturation constant k1 of these receptors can be estimated as 0.071 min -1 (with equation 4). However, the i3 mutant (A258L) had clearly a different denaturation rate. Indeed, for a same level of constitutive activity (1 + J) as compared to the mutant Δ327, its k1 was very different and equal to 0.026 min -1 assuming that equation 4 is true for this mutant as it was for the other mutants.

In conclusion, these data show that the WT receptor and the C-tail mutant receptors share the same denaturation constant, whereas the i3 mutant has a clearly different denaturation constant.

This indicates that constitutively active mutations can result either from a change in J without any change in the R* conformation or from both a change in J and a change in the R* conformation.

In addition, these results constitute a strong indication that the increase in thermal instability of these mutant receptors was not due to point mutations or truncations per se, but instead, to the intensity of structural changes associated with the release of structural constraints.

To further support this conclusion, we hypothesized that, if the R* form of the receptor is more unstable, due to a release in constraints, the mutations stabilizing the receptor in the R form, could be expected to produce mutant receptors that are more stable than the WT. In family A GPCRs, a conserved Asp residue in TMDII has been shown to be crucial for signal transduction, agonist affinity, allosteric regulation by Na + , pH and guanyl nucleotides. Substituting this Asp in TMDII for Asn or Ala in the WT receptor (in various family A GPCRs), leads to a silent receptor, unable to trigger the R to R* conformational change [START_REF] Wang | Site-directed mutagenesis of α2A-adrenergic receptors: identification of amino acids involved in ligand binding and receptor activation by agonists[END_REF][START_REF] Sealfon | Related contribution of specific helix 2 and 7 residues to conformational activation of the serotonin 5-HT2A receptor[END_REF][START_REF] Fanelli | Activation mechanism of human oxytocin receptor: a combined study of experimental and computer-simulated mutagenesis[END_REF]. This observation is consistent with a stabilization of the receptor in the R form. Indeed, introducing this mutation (D66N) in the 5-HT4R led to a particularly silent receptor with no constitutive activity, regardless of receptor density (Figure 4A).

Compared with the WT, this D66N mutated receptor had a similar affinity for the antagonist [ 3 H]GR113808 and for the agonist 5-HT (not shown), and was insensitive to 5-HT (not shown).

This indicates that this mutation increases the structural constraints of receptors, thus reducing their spontaneous transition to R*. We were expecting that such an augmentation of the structural constraints of the D66N mutant should increase its t1/2 of denaturation (decrease its denaturation rate). This was indeed the case (t1/2 = 102 ± 9, n = 5, Figure 4B). This is the first experimental evidence to show that a mutation which hinders GPCRs from undergoing the R→R* transition, increases their structural stability.

The 'two-state' formalism has been recently recognized to be a simplification of a more general concept of allosteric equilibrium. According to this concept, the receptor undergoes transitions from a large population of allosteric states [START_REF] Kenakin | Agonist-specific conformations[END_REF][START_REF] Onaran | Agonist efficacy and allosteric models of receptor action[END_REF] with different agonists able to stabilize varying populations of active states. Similarly, we can propose that different mutations will stabilize different active states as previously proposed by Parma et al. on different experimental basis [START_REF] Parma | Somatic mutations causing constitutive activity of the thyrotropin receptor are the major cause of hyperfunctioning thyroid adenomas: identification of additional mutations activating both the cyclic adenosine 3′,5′-monophosphate and inositol phosphate-Ca 2+ cascades[END_REF]. We had previously speculated on the existence of structurally, and therefore pharmacologically different active R* on the following basis: PACAP receptors expressed in LLCPK1 cells can be stimulated by PACAP-38 and PACAP-27, whereas PACAP-27 is consistently more potent in stimulating cAMP formation, compared to PACAP-38, with the latter being more potent in stimulating inositol phosphate accumulation [START_REF] Spengler | Differential signal transduction by five splice variants of the PACAP receptor[END_REF]. This is indirect evidence demonstrating that different R* entities can exist having different G protein coupling specificity. This, and other similar observations have led to the notion of agonist stimulus trafficking, whereby different agonists, by stabilizing different R* conformations, steer those receptors toward different G protein pathways [START_REF] Kenakin | Agonist-receptor efficacy I: mechanisms of efficacy and receptor promiscuity[END_REF][START_REF] Gudermann | Diversity and selectivity of receptor-G protein interaction[END_REF].

The present data constitute direct experimental evidence for the existence of such different R* conformations.

In conclusion, constitutive activation of mutated 5-HT4Rs, classical family A GPCRs, can result from a change in the allosteric J constant, as we have shown previously [START_REF] Claeysen | Pharmacological properties of the 5-hydroxytryptamine4 receptor antagonists on constitutively active wild-type and mutated receptors[END_REF], and also to the formation of structurally distinct R*.

METHODS

Construction of truncated 5-HT4(a) receptor cDNA and epitope-tagged mutated and WT

5-HT4(a) receptors. Constructs were obtained as described [START_REF] Claeysen | Pharmacological properties of the 5-hydroxytryptamine4 receptor antagonists on constitutively active wild-type and mutated receptors[END_REF]. Sense primer used for D66N: 5′-CTCGCCTTTGCTAACCTGCTGGTT-3′

Construction

Sense primer used for C329S: 5′-ATCATCCTCTGCAGTGATGATGAGCG-3′

Sense primer used for C328-329S: 5′-ATCATCCTCAGCAGTGATGATGAGCGCTAC-3′.

Cell culture and transfection. The cDNA subcloned into pRK5, were introduced into COS-7 cells by electroporation, as described [START_REF] Claeysen | Pharmacological properties of the 5-hydroxytryptamine4 receptor antagonists on constitutively active wild-type and mutated receptors[END_REF].

Determination of cAMP production in intact cells. Six hours after transfection, cells were incubated overnight in DMEM without dialyzed fetal bovine serum (dFBS), but with 2 µCi [ 3 H]adenine/ml to label the ATP pool and cAMP accumulation was measured as described by [START_REF] Dumuis | Pharmacology of 5-hydroxytryptamine1A receptors which inhibit cAMP production in hippocampal and cortical neurons in primary culture[END_REF].

Membrane preparations and radioligand binding assay. Membranes were prepared from transiently transfected cells plated on 15 cm-dishes and grown in DMEM with 10% dFBS for 6 then 20 h in DMEM without dFBS as previously described [START_REF] Ansanay | Pharmacological comparison between [ H]-GR113808 binding sites and 5-HT4 receptors coupled to adenylyl cyclase in mouse colliculi neurons[END_REF]. Protein concentration in the samples was determined using the Bio-Rad protein assay [START_REF] Bradford | A rapid and sensitive method for the quantitation of microgram quantities of protein utilising the principle of protein-dye binding[END_REF].

Binding studies on intact cells. To measure binding in intact cells, transiently transfected COS-7 cells were plated into 12-well clusters (5 × 10 5 cells/ml) and grown in DMEM with 10% dFBS for 6 and 20 h in DMEM without dFBS. Experiments were performed in HBS (20 mM HEPES, 150 mM NaCl, 4.2 mM KCl, 0.9 mMCaCl2, 0.5 mMMgCl2, 0.1% glucose, 0.1% BSA).The reaction mixture (250 µl) contained 0.4 to 0.6 nM [ 3 H]GR 113808 and 0.5 µM 5-HT was used to determine non-specific binding. Incubation lasted 2 h at 4°C and was terminated by rapid aspiration of the incubation buffer, followed by three washings in ice-cold HBS. Cells were then lysed in 0.1 N NaOH. Radioactivity was measured in 8 ml scintillation liquid PCS (Amersham).

Determination of receptor stability in membranes. Membranes (at 0.250 mg protein/ml) were incubated in binding buffer at 45 or 55°C. At t = 0 and after different periods of incubation, an aliquot (100 µl) was removed and used for a binding assay at a saturation concentration of [ 3 H]GR 113808 (0.4-0.6 nM), as described. We also made sure that the concentration of WT or mutated receptors was similar within a given experiment (see legends to figures).

Membrane preparations, gel electrophoresis and immunoblotting. Membranes were prepared from transiently transfected COS-7 cells expressing WT or mutated 5-HT4 receptors as previously described [START_REF] Claeysen | Pharmacological properties of the 5-hydroxytryptamine4 receptor antagonists on constitutively active wild-type and mutated receptors[END_REF]. The c-Myc antibodies were used at a dilution of 1:500 in the blocking buffer. The immunocomplexes were detected by enhancement using the chemiluminescence method (Renaissance Plus, NEN).

Immunocytochemical fluorescence labeling of epitope-tagged 5-HT4Rs in cells. 5-HT4Rs on intact cells were visualized using the anti-c-Myc primary antibody and a rhodamine conjugated secondary anti-mouse antibody. Cells were grown on coverslips and fixed 24 h after transient transfection in 4% paraformaldehyde diluted in PBS pH 7.4 for 30 min at room temperature, washed three times in a glycine buffer (0.1 M, pH 7.4) and incubated for 2 h at 37°C with the monoclonal antibody 9E10, ascitic fluid was diluted 1:250 in PBS-gelatin 0.2%.

The cells were then washed and incubated for 1 h with a rhodamine-conjugated secondary antimouse antibody 1:40 in PBS-gelatin 0.2%. Coverslips were washed and mounted on glass slides using a gel mount (Biomeda Corp., Foster City, CA). Cells were viewed on a Bio-Rad CLSM 1024 confocal laser-scanning microscope. Rhodamine was exited at 568 nm.

All experiments have been done at least four times and data are expressed as the mean ± SEM. and df is the degree of freedom. The significance was assessed by comparing F to an F-distribution with 1 and dferr,(β) degrees of freedom. A similar procedure was used to compare models (β) and (γ).

FIGURE LEGENDS

Figure 1. Constitutively active mutated 5-HT4 receptors showed thermal instability compared with WT receptors. WT, 5-HT4R (Δ327) and 5-HT4R (A258L) mutant [START_REF] Claeysen | Pharmacological properties of the 5-hydroxytryptamine4 receptor antagonists on constitutively active wild-type and mutated receptors[END_REF] receptors were transiently expressed in COS-7 cells at 2800 ± 340, 2560 ± 180 and 2900 ± 320 fmol/mg protein, respectively. (A) Basal and 5-HT-stimulated activation of WT, 5-HT4R (Δ327) and 5-HT4R (A258L) were evaluated by measuring the accumulation of cAMP over a period of 20 min. The percentage conversion of Δ358, Δ346, Δ327, C329S and C328-329S, A258L). (C) WT, Δ358, Δ346, Δ327, C329S, C328-329S, A258L receptors were transiently expressed in COS-7 cells at 1750 ± 140, 1980 ± 180, 1670 ± 120, 2070 ± 210, 1980 ± 120, 2130 ± 160 fmol/mg protein, respectively. cAMP formation was evaluated by measuring the accumulation of cAMP over a period of 20 min and expressed as a percentage of mock transfected cells. The percentage conversion of [ 3 H]ATP to [ 3 H]cAMP in mock transfected COS-7 cells was 0.15 ± 0.03. (D) Relationship between the t1/2 of denaturation of WT and mutated 5-HT4 receptors and the allosteric J constant. The t1/2 of the WT and different mutants were determined as in Figure 1. The J constants of WT, Δ327, A258L receptors have been determined previously [START_REF] Claeysen | Pharmacological properties of the 5-hydroxytryptamine4 receptor antagonists on constitutively active wild-type and mutated receptors[END_REF] and were equal to 6.12 ± 0.48, 1.22 ± 0.25 and 0.78 ± 0.05, respectively. Those of Δ358, Δ346, C328-329S, C329S were calculated as described previously [START_REF] Claeysen | Pharmacological properties of the 5-hydroxytryptamine4 receptor antagonists on constitutively active wild-type and mutated receptors[END_REF] and were equal to 5.95 ± 0.35, 2.18 ± 0.26, 2.36 ± 0.24, 3.64 ± 0.18, respectively. The regression t1/2= a (1 + J) is positive and significant when A258L is excluded (a = 9.7 ± SE 0.46, p <0.0001).

  were equal to 70 ± 4 (n = 10), 68 ± 5 (n = 4), 50 ± 4 (n = 5), 35 ± 3 (n = 4), 23 ± 3 (n = 5), 17 ± 4 (n = 6), 48 ± 5 (n = 6) (Figure 3C). We propose the following model, where the denaturation of R and R* is governed by the schema: , in which Rd and R*d are the denaturated receptors. By measuring the total [ 3 H]GR 113808 binding, we are following the evolution of [Rt] = [R] + [R*]. The evolution of [R] + [R*] = [Rt] is described by: (equation 1) Assuming that the equilibrium between R and R* still exists during dt, i.e. we have J = [R]/[R*], the integration of equation 1 between t and t = 0 gives: (equation 2) Our model predicts that the observed t1/2 of denaturation depends on the denaturation constants of the receptors (k1, k2) and on the values of J.

  of mutated m5-HT4(a) receptor cDNA: mutants A258L, D66N, C329S and C328-329S. Mutants were obtained by exchanging the endogenous amino acids in the m5-HT4(a)R cDNA sequence, using the QuikChange™ Site-Directed Mutagenesis Kit (STRATAGENE).

  Statistical analysis. We used least-square regressions to fit three models to the data: (α) linearwithout intercept t1/2 = a (1 + J), (β) linear with intercept t1/2 = a (1 + J) + b, (γ) quadratic t1/2 = a (1 + J) 2 + b(1 + J) + c.The improvement of model fit between (α) and (β) and between (β) and (γ) provided a way for us to test the significance of the intercept and quadratic terms, respectively. The improvement between (α) and (β) was quantified as , where SSerr,(α) and SSerr,(β) are, respectively, the error sums of squares of models (α) and (β)

  [ 3 H]ATP to [ 3 H]cAMP in mock was 0.12 ± 0.04. (B) Membranes were incubated at 45 or 55°C for 3 h. Data are given as remaining [ 3 H]GR 113808 binding as a percentage of maximum specific binding at t = 0. (C) Membranes expressing receptors were incubated at 55°C for indicated periods of time. The remaining [ 3 H]GR 113808 binding (B) is given as a percentage of maximum binding at t = 0 (Rt0). (D) Semi-logarithmic plot of the curve showing the evolution of the Rt/Rt0 ratio as a function of time. (E) Western blot analysis of c-myc epitope tagged WT and Δ327 5-HT4R before and after incubation at 55°C for 180 min. The WT receptor is shown at a 42 kDa band, the Δ327 receptor at a 34 kDA band. The non-specific labeled band at 45 kDa indicates that nearly the same amount of proteins has been applied on the gel.

Figure 2 .

 2 Figure 2. Comparison between cellular distribution of mutated A258L and Δ327 and WT 5-HT4 receptors. (A) cDNA (300 and 150 µg) coding for epitope-tagged mutated and WT 5-HT4(a) receptors respectively, were transiently transfected in COS-7 cells to obtain nearly similar expression receptor levels. Confocal microscopic images show that rhodamine-conjugated secondary anti-mouse antibody fluorescence was predominantly confined to the plasma membranes. These images are representative of four independent experiments. (B) cDNA coding for WT, A258L and Δ327 receptors [same concentration as in (A)], were transiently transfected in COS-7 cells. Receptor density was measured both in COS-7 cells, in membranes and on intact cells using [ 3 H] GR 113808 at saturating concentrations. A/B is the ratio between the number of [ 3 H] GR 113808 binding sites/cell determined in intact cells and particulate fractions.

Figure 3 .

 3 Figure 3. Thermal instability of a series of 5-HT4R mutants: evidence for the existence of different R* conformations. (A) Schematic representation of the mutated 5-HT4(a) receptors used in this study. (B) Basal and 5-HT-stimulated cAMP formation in COS-7 cells expressing WT and different truncated and mutated 5-HT4Rs in C-terminal tail and in the i3 loop (WT,

Fig. 4 .

 4 Fig. 4. Mutation of the conserved Asp residue in TMDII of GPCRs (family 1) leads to a particularly silent receptor, structurally more stable than the WT receptor. (A) WT and D66N basal activities were plotted as a function of receptor expression levels. WT and D66N receptors were transiently expressed at variable levels by transfecting increasing amounts of specific plasmid. Basal activities were evaluated by measuring the accumulation of cAMP over a period of 20 min and expressed as a percentage of mock transfected cells. The percentage conversion of [ 3 H]ATP to [ 3 H]cAMP in mock transfected COS-7 cells was 0.18 ± 0.03. (B) Semilogarithmic representation of the curve showing the evolution of the Rt/Rt0 ratio as a function of incubation time at 55°C.

Figure 1 Figure 2 Figure 3 Figure 4

 1234 Figure 1

ACKNOWLEDGEMENTS

We are grateful to J.-P. Pin, O. Manzoni, and L. Fagni for valuable discussions and to P. David for the statistical analysis. A.L. Turner-Madeuf and F. Carroll are acknowledged for their help in the writing of the manuscript and M. Passama for preparation of figures.


Christophe Clavier

Benoit Feix

Georges Gagnerot

Mylène Roussellet

Vincent Verneuil

Horizontal Correlation Analysis on Exponentiation

Keywords: Public Key Cryptography, Side-Channel Analysis, Horizontal and Vertical Power Analysis, Exponentiation, Arithmetic Coprocessors

Power Analysis has been widely studied since Kocher et al. presented in 1998 the initial Simple and Differential Power Analysis (SPA and DPA). Correlation Power Analysis (CPA) is nowadays one of the most powerful techniques which requires, as classical DPA, many execution curves for recovering secrets.

We introduce in this paper a technique in which we apply correlation analysis using only one execution power curve during an exponentiation to recover the whole secret exponent manipulated by the chip. As in the Big Mac attack from Walter, longer keys may facilitate this analysis and success will depend on the arithmetic coprocessor characteristics. We present the theory of the attack with some practical successful results on an embedded device and analyze the efficiency of classical countermeasures with respect to our attack. Our technique, which uses a single exponentiation curve, cannot be prevented by exponent blinding. Also, contrarily to the Big Mac attack, it applies even in the case of regular implementations such as the square and multiply always or the Montgomery ladder. We also point out that DSA and Diffie-Hellman exponentiations are no longer immune against CPA. Then we discuss the efficiency of known countermeasures, and we finally present some new ones.

Introduction

Securing embedded products from Side-Channel Analysis (SCA) has become a difficult challenge for developers who are confronted with more and more analysis Full version of the paper published in the proceedings of ICICS 2010.

techniques as the physical attacks field is studied. Since the original Simple Side-Channel Analysis (SSCA) -which include Timing Attacks, SPA, and SEMAand Differential Side-Channel Analysis (DSCA) -including DPA and DEMAhave been introduced by Kocher et al. [START_REF] Kocher | Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems[END_REF][START_REF] Kocher | Differential Power Analysis[END_REF] many improvements and new SCA techniques have been published. Messerges et al. were the first to apply these techniques to public key implementations [START_REF] Messerges | Power analysis attacks of modular exponentiation in smartcards[END_REF]. Later on, original DSCA has been improved by more efficient techniques such as the one based on the likelihood test proposed by Bevan et al. [START_REF] Bevan | Ways to Enhance Differential Power Analysis[END_REF], the Correlation Power Analysis (CPA) introduced by Brier et al. [START_REF] Brier | Correlation Power Analysis with a Leakage Model[END_REF], and more recent techniques like the Mutual Information Analysis (MIA) [START_REF] Gierlichs | Mutual Information Analysis[END_REF][START_REF] Prouff | Theoretical and Practical Aspects of Mutual Information Based Side Channel Analysis[END_REF][START_REF] Standaert | Partition vs. Comparison Side-Channel Distinguishers: An Empirical Evaluation of Statistical Tests for Univariate Side-Channel Attacks against Two Unprotected CMOS Devices[END_REF]. A common principle of all these techniques is that they require many power consumption or electromagnetic radiation curves to recover the secret manipulated. Hardware protections and software blinding [START_REF] Coron | Resistance against differential power analysis for elliptic curve cryptosystems[END_REF][START_REF] Kocher | Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems[END_REF] countermeasures are generally used and when correctly implemented they counteract these attacks.

Among all those studies the so-called Big Mac attack is a refined approach introduced by Walter [START_REF] Walter | Sliding Windows Succumbs to Big Mac Attack[END_REF][START_REF] Walter | Longer keys may facilitate side channel attacks[END_REF] from which our contribution is inspired. This technique aims at distinguishing squarings from multiplications and thus recovering the secret exponent of an RSA exponentiation with a single execution curve. This can be achieved by averaging and comparing the cycles of a device multiplier during long integer multiplications.

We present in this paper another analysis which uses a single curve. We named this technique horizontal correlation analysis, which consists of computing classical statistical treatments such as the correlation factor on several segments extracted from a single execution curve of a known message RSA encryption. Since this analysis method requires only one execution of the exponentiation as the Big Mac attack, it is then not prevented by the usual exponent blinding countermeasure.

The paper is organized as follows. Section 2 gives an overview of asymmetric algorithms and the way to compute long integer multiplication in embedded implementations. Section 3 reminds the reader of previous studies on power analysis techniques discussed in this article. The horizontal correlation analysis is presented in Section 4 with some practical results and a comparison between our technique and the Big Mac attack. Known and new countermeasures are discussed in Section 5. In Section 6 we deal with horizontal side channel analysis in the most common cryptosystems. Finally we conclude this paper in Section 7.

Public Key Embedded Implementations

RSA is well known to be currently the most used public key cryptosystem in smart devices. Other public key schemes such as DSA [START_REF]Digital Signature Standard[END_REF], Diffie-Hellman key exchange [START_REF] Diffie | New Directions in cryptography[END_REF] protocols, and their equivalent in Elliptic Curve Cryptography (ECC) -namely ECDSA and ECDH [START_REF]Digital Signature Standard[END_REF] -are also often involved in security products. Interestingly, all of them are based on the modular exponentiation or the scalar multiplication and in both cases the underlying operation is modular long integer multiplication. Heavy efficiency constraints thus lie on this opera-tion, especially in the context of embedded devices. Many methods such as the Montgomery multiplication [START_REF] Montgomery | Modular multiplication without trial division[END_REF] and interleaved multiplication-reduction with Knuth, Barrett, Sedlack or Quisquater methods [START_REF] Dhem | Design of an efficient public-key cryptographic library for RISC-based smart cards[END_REF] can be applied to perform efficient modular multiplications. Most of them have in common that the long integer multiplication is internally done with a loop of one (or more) smaller multiplier(s) operating on t-bit words. An example is given in Alg. 2.1 which performs the schoolbook long integer multiplication using a t-bit internal multiplier giving a 2t-bit result. The decomposition of an integer x in t-bit words is given by x = (x l-1 x l-2 . . . x 0 ) b with b = 2 t and l = log b (x) . Other long integer multiplication algorithms may also be used such as Comba [START_REF] Comba | Exponentiation cryptosystems on the ibm pc[END_REF] and Karatsuba [START_REF] Karatsuba | Multiplication of multidigit numbers on automata[END_REF] methods.

Algorithm 2.1 Long Integer Multiplication

Input: x = (x l-1 x l-2 . . . x0) b , y = (y l-1 y l-2 . . . y0) b Output: LIM(x, y) = x × y Step 1. for i from 0 to 2l -1 do wi = 0 Step 2. for i from 0 to l -1 do c ← 0 for j from 0 to l -1 do (uv) b ← (wi+j + xi × yj) + c wi+j ← v and c ← u w i+l ← c Step 3. Return(w)
We consider in this paper that a modular multiplication x × y mod n is performed using a long integer multiplication followed by a Barrett reduction denoted by BarrettRed(LIM(x,y),n).

Algorithm 2.2 Square and Multiply Exponentiation

Input: integers m and n such that m < n, v-bit exponent d = (dv-1dv-2 . . . d0)2 Output: Exp(m, d, n) = m d mod n Step 1. a ← 1 Step 2. Process Barrett reduction precomputations Step 3. for i from v -1 to 0 do a ← BarrettRed(LIM(a,a), n) if di = 1 then a ← BarrettRed(LIM(a,m), n) Step 4. Return(a)
Alg. 2.2 presents the classical square and multiply modular exponentiation algorithm using Barrett reduction. More details on Barrett reduction can be found in [START_REF] Avanzi | Handbook of Elliptic and Hyperelliptic Curve Cryptography[END_REF][START_REF] Menezes | Handbook of Applied Cryptography[END_REF] and other methods can be used to perform the exponentiation such as Montgomery ladder [START_REF] Montgomery | Speeding the Pollard and elliptic curve methods of factorization[END_REF] and sliding window techniques [START_REF] Kaya | Analysis of sliding window techniques for exponentiation[END_REF].

We assume in the following of this paper that Alg. 2.2 is implemented in an SPA resistant way, for instance using the atomicity principle [START_REF] Chevallier-Mames | Low-cost solutions for preventing simple side-channel analysis: side-channel atomicity[END_REF].

While we have chosen to consider modular multiplication using Barrett reduction, and square and multiply exponentiation, the results we present in this paper also apply to the other modular multiplication methods, long integer multiplication techniques and exponentiation algorithms mentioned above.

Side-Channel Analysis

We have chosen to introduce in this paper the terms of vertical and horizontal side-channel analysis to classify the different known attacks. The present section deals with known vertical and horizontal power analysis techniques. Our contribution, the horizontal correlation analysis on exponentiation is detailed in Section 4.

Background

Side-channel attacks rely on the following physical property: a microprocessor is physically made of thousands of logical gates switching differently depending on the executed operations and on the manipulated data. Therefore the power consumption and the electromagnetic radiation, which depend on those gates switches, reflect and may leak information on the executed instructions and the manipulated data. Consequently, by monitoring the power consumption or radiation of a device performing cryptographic operations, an observer may recover information on the implementation of the program executed and on the secret data involved.

Simple Side-Channel Analysis In the case of an exponentiation, original SSCA consists in observing that, if the squaring operation has a different pattern from the one of the multiplication, the secret exponent can be read on the curve. Classical countermeasures consist of using so-called regular algorithms like the square and multiply always or Montgomery ladder algorithms [START_REF] Montgomery | Speeding the Pollard and elliptic curve methods of factorization[END_REF][START_REF] Joye | The Montgomery Powering Ladder[END_REF], atomicity principle which leads to regular power curves as presented in Appendix A Fig. 9.

Differential Side-Channel Analysis Deeper analysis such as DSCA [START_REF] Messerges | Power analysis attacks of modular exponentiation in smartcards[END_REF] can be used to recover the private key of an SSCA protected implementation. These analyses make use of the relationship between the manipulated data and the power consumption/radiation. Since this leakage is very small, hundreds to thousands of curves and statistical treatment are generally required to learn a single bit of the exponent. Usual countermeasures consist of randomizing the modulus, the message, and/or the exponent.

Correlation Power Analysis

This technique is essentially an improvement of the Differential Power Analysis. Initially published by Brier et al. [START_REF] Brier | Correlation Power Analysis with a Leakage Model[END_REF] to recover secrets on symmetric implementations, CPA is also successful in attacking asymmetric algorithms [START_REF] Amiel | Power Analysis for Secret Recovering and Reverse Engineering of Public Key Algorithms[END_REF] with much fewer curves than classical DPA. The power consumption of the device is supposed to vary linearly with H(D ⊕ R), the Hamming distance between the data manipulated D and a reference state R. The consumption model W is then defined as W = µ • H(D ⊕ R) + ν, where ν captures both the experimental noise and the non modelized part of the power consumption. The linear correlation factor ρ C,H = cov(C,H) σ C σ H is then used to correlate each power curve C with H(D ⊕ R). The maximum correlation factor being obtained for the right guess of secret key bits, an attacker can try all possible secret bits values and select the one corresponding to the highest correlation value.

In [START_REF] Amiel | Power Analysis for Secret Recovering and Reverse Engineering of Public Key Algorithms[END_REF], Amiel et al. apply the CPA to recover the secret exponent of public key implementations. Their practical results show that the number of curves necessary to an attack is much lower compared to DPA: less than one hundred of curves is sufficient. It is worth noticing that the correlation is the highest when computed on t bits, t being the bit length of the device multiplier.

The authors shows the details [2, Fig. 8] of the correlation factor obtained for every multiplicand t-bit word A i during the squaring operation A × A using a hardware multiplier. Interestingly a correlation peak occurs for H(A i ) each time a word A i is involved in a multiplication A i × A j .

We present in the next section our horizontal correlation analysis which takes advantage of this observation.

Collision Power Analysis

The Doubling attack from Fouque and Valette [START_REF] Fouque | The Doubling Attack -why upwards is better than downwards[END_REF] is the first collision technique published on public key implementations. It is originally presented on elliptic curve scalar multiplication but can be applied on exponentiation algorithms. It recovers the whole secret scalar (exponent) with only a couple of curves. Other collision attacks have been presented in [START_REF] Amiel | On the BRIP Algorithms Security for RSA[END_REF][START_REF] Homma | Collision-based power analysis of modular exponentiation using chosen-message pairs[END_REF][START_REF] Yen | Power Analysis by Exploiting Chosen Message and Internal Collisions -Vulnerability of Checking Mechanism for RSAdecryption[END_REF]. They all require at least two power execution curves, therefore the classical exponent randomization (blinding) countermeasure counterfeits those techniques.

Notations Let C k denote the portion of an exponentiation curve C corresponding to the k-th long integer multiplication, and C k i,j denote the curve segment corresponding to the internal multiplication

x i × y j in C k .
Big Mac Attack Walter's attack needs, as our technique, a single exponentiation power curve to recover the secret exponent. For each long integer multiplication, the Big Mac attack detects if the operation processed is either a × a or a × m. The operations x i × y j -and thus curves C k i,j -can be easily identified on the power curve from their specific pattern which is repeated l 2 times in the long integer multiplication loop. A template power trace T 1 m is computed (either from the precomputations or from the first squaring operation) to characterize the message value m manipulation during the long integer multiplication. The Euclidean distance between T 1 m and each long integer multplication template power trace is then computed. If it exceeds a threshold the multiplication trace is supposed to be a squaring, and a multiplication by m otherwise. An example of such calculation is given in the following: for each t-bit word m i of the message m, compute

T 1 mi = 1 l l-1 j=0 C 1 i,j by averaging the l subcurves C 1 i,0 . . . C 1 i,l-1 . Then the template curve T 1 m is the concatenation of curves T 1 m0 ...T 1 m l-1 .
In the exponentiation loop, at each k-th long integer multiplication, the curve T k is computed in the same manner. The Euclidean distance between T k and T 1 m is computed. If it exceeds a threshold the multiplication is supposed to be a squaring, and a multiplication by m otherwise. The attack is innovative and has been presented by Walter with theoretical and simulation results. The efficiency of the attack increases with the key length and decreases with the multiplier size. [START_REF] Messerges | Power analysis attacks of modular exponentiation in smartcards[END_REF] to try to recover the secret exponent in a single curve. However the cross correlation curve obtained by the authors did not allow distinguishing a multiplication from a squaring. More generally no successful practical result for cross correlation using a single exponentiation power curve has been yet published.

Cross-Correlation Cross correlation technique has been used in

Vertical and Horizontal Attacks Classification

We refer to the techniques analyzing a same time sample in many execution curves -see Fig. 1 -as vertical side-channel analysis. The classical DPA and CPA techniques thus fall into this category. We also include in the vertical analysis class the collision attacks mentioned above. Indeed even if many points on a same curve are used by those techniques, they require at least two power execution curves and manipulate them together. All those attacks are avoided with the exponent blinding countermeasure presented by Kocher [18, Section 10]. We propose the horizontal side-channel analysis denomination for the attacks using a single curve. First known horizontal power analysis is the classical SPA. Single curve Cross-correlation and Big Mac attacks are also horizontal techniques.

Our attack, we present in the next section, computes the correlation factor on many curve segments extracted from a single consumption/radiation curve as depicted in Fig. 2. It thus contrasts with vertical attacks which target a particular instant of the execution in several curves. The exponent blinding is not an efficient countermeasure against horizontal attacks.

Horizontal Correlation Analysis

We present hereafter our attack on an atomically protected RSA exponentiation using Barrett reduction.

Recovering the Secret Exponent with One Known Message Encryption

As in vertical DPA and CPA on modular exponentiation, the horizontal correlation analysis reveals the bits of the private exponent d one after another. Each exponent bit is recovered by determining whether the processing of this bit involves a multiplication by m or not (cf. Alg. 2.2). The difference with classical vertical analysis lies in the way to build such hypothesis test. Computing the long integer multiplication x × y using Alg. 2.1 requires l 2 t-bit multiplier calls. The multiplication side-channel curve thus yields l 2 curve segments C k i,j

available to an attacker. Assuming that the first s bits d v-1 d v-2 . . . d v-s of the exponent are already known, an attacker is able to compute the value a s of the accumulator in Alg. 2.2 after processing the s-th bit. The processing of the first s bits corresponds to the first s long integer multiplications with s = s + H(d v-1 d v-2 . . . d v-s ) known from the attacker. The value of the unknown (s + 1)-th exponent bit is then equal to 1 if and only if the (s + 2)-th long integer multiplication is a s 2 × m.

a s 1 P P P q dv-s-1= 1 dv-s-1= 0 a s × a s a s × a s -a s 2 × m - dv-s-2= 0,1 a s 2 × a s 2 • • • • • • C s +1 C s +2
At this point there are several ways of determining whether the multiplication by m is performed or not.

First, one may show that the series of consumptions in the set of l 2 curve segments is consistent with the series of operand values m j presumably involved in each of these segments. To this purpose the attacker simply computes the correlation factor between the series of Hamming weights H(m j ) and the series of curve segments C s +2 i,j -i.e. taking D = m j and R = 0 in the correlation factor formula. In other words we use the curve segments as they would be in a vertical analysis if they were independent aligned curves. A correlation peak reveals that d v-s-1 = 1 since it occurs if and only if m is actually handled in this long multiplication.

Alternatively one may correlate the curves segments with the intermediate results of each t-bit multiplication x i ×y j , cf. Alg. 2.1, with x = a s and y = m, or in other words take D = a i × m j . This method may also be appropriate since the words of the result are written in registers at the end of the operation. Moreover in that case l 2 different values are available for correlating the curve segments instead of l previously. This diversity of data may be necessary for the success of the attack when l is small. Note that other intermediate values may also lead to better results depending on the hardware leakages.

Another method consists of using the curve segments

C s +3 i,j
of the next long integer multiplication and correlating them with the Hamming weight of the words of the result a s 2 × m. If the (s + 2)-th operation is a multiplication by m then the (s + 3)-th operation is a squaring a s+1 2 , manipulating the words of the integer a s 2 × m in the t-bit multiplier. As pointed out by Walter in [START_REF] Walter | Longer keys may facilitate side channel attacks[END_REF] for the Big Mac attack, the longer the integer manipulated and the smaller the size t of the multiplier, the larger the number l 2 of curve segments. Thus longer keys are more at risk with respect to horizontal analysis. For instance in an RSA 2048 bit encryption, if the long integer multiplication is implemented using a 32-bit multiplier we obtain (2048/32) 2 = 4096 segments C k i,j per curve C k . In Appendix B Table 1 proposes examples of values for l and l 2 for different sizes of the modulus n and different sizes t of the multiplier. Remark The series of Hamming weights H(m j ) is not only correlated with the series of curve segments in C s +2 (provided that d v-s-1 = 1), but also with the series of curve segments in each and any C k corresponding to a multiplication by m. Defining a wide segment C * i,j as the set of segments C k i,j for all k on the curve C and correlating the series of H(m j ) with the series of wide segments C * i,j (instead of the series of segments C s +2 i,j ) will produce a wide segment correlation curve with a peak occurring for each k corresponding to a multiplication by the message. It is thus possible to determine in one shot the exact sequence of squarings and multiplications by m, revealing the whole private exponent with only one curve and only one correlation computation.

Practical Results

This section presents the successful experiments we conducted to demonstrate the efficiency of the horizontal correlation analysis technique. We used a 16bit RISC microprocessor on which we implemented a software 16 × 16 bits long integer multiplication to simulate the behavior of a coprocessor. We aim at correlating a single long integer multiplication with one or both operands manipulated -i.e. y j or x i × y j .

The measurement bench is composed of a Lecroy Wavepro oscilloscope, and homemade softwares and electronic cards were used to acquire the power curves and process the attacks.

Firstly we performed a classical vertical correlation analysis to characterize our implementation and measurement bench, and to validate the correlation model; then we processed with the horizontal correlation analysis previously described. Vertical Correlation Analysis This analysis succeeded in two cases during the operation x × y. We obtained correlation peaks by correlating power curves with values x i and y j and also by correlating the power curves with the result value of operation x i × y j . Fig. 4 and Fig. 5 show the correlation traces we obtained for both cases with 500 power curves. This suggests that one can perform horizontal correlation as explained previously either using y i values or using result values x i × y j for correlating with segment curves of the long integer multiplication.

Horizontal Correlation Analysis

We have chosen to test our technique within a 512-bit multiplication LIM(x, y). This allows us to obtain 1024 curve segments C k i,j of 16-bit multiplications to mount the analysis, which should be enough for the success of our attack regarding the vertical analysis results. From the single power curve we acquired, we processed the signal in order to detect each set of cycles corresponding to each t-bit multiplication x i × y j and divide the single power curve in 1024 segments C k i,j as depicted in Fig. 3. We performed horizontal correlation analysis as explained in Section 4 for the two cases D = a i × m j and D = m j and recovered the operation executed as shown in Fig. 6 and Fig. 7. In each figure, the grey trace shows a greater correlation than the black one and thus corresponds to the correct guess on the operation.

Since our attack actually enabled us to distinguish one operation from another, it is then possible to identify a squaring a × a from a multiplication a × m in the Step 3 of Alg. 2.2. The secret exponent d used in an exponentiation can thus be recovered by using a single power trace, even when the exponentiation is protected by an atomic implementation. We have presented here a technique to recover the secret exponent using a single curve when the input message is known and have proven this attack to be practically successful. Although the attack is tested on a software implementation, results obtained by Amiel et al. [START_REF] Amiel | Power Analysis for Secret Recovering and Reverse Engineering of Public Key Algorithms[END_REF]Fig. 8] prove that correlation techniques are efficient on hardware coprocessors (with multiplier size larger than 16 bits), and enable to locate each little multiplication involved in a long integer multiplication. We thus consider that our attack can also threaten hardware coprocessors.

Comparing our Technique with the Big Mac Attack

We now compare our proposed horizontal CPA on exponentiation with the Big Mac attack which is the most powerful known horizontal analysis to recover a private exponent. A common property is that both techniques counteract the randomization of the exponent.

A first difference between both methods is that the Big Mac templates are generated by averaging the leakage dependency from a not targeted argument.

It is thus implicitly accepted to lose the information brought by this auxiliary data. On the other hand, horizontal correlation exploits the knowledge of both multiplication operands a and m (under assumption on the exponent bit) to correlate it with all l 2 segments C k i,j . This full exploitation of the available information included in the l 2 curve segments tends us to expect a better efficiency of the correlation method particularly when processing noisy observations. But the main difference is not there. What fundamentally separates the Big Mac and correlation methods is that the former deals with templates -which the attacker tries to identify -while the later rather consider intermediate results -whose manipulation validates a secret-dependent guess. With the Big Mac technique an attacker is able to answer the question Is this operation of that particular kind? (squaring, multiplication by m or a power thereof) while the correlation with intermediate data not only brings the same information but also answers the more important question Is the result of that operation involved in the sequel of the computation? The main consequence is that horizontal CPA is effective even when the exponentiation implementation is regular with respect to the operation performed. This is notably the case of the square and multiply always4 and the Montgomery ladder exponentiations which are not threaten by the Big Mac attack. In this respect we can say that our horizontal CPA combines both the advantage of classical CPA which is able to validate guesses based on the manipulation of intermediate results (but which is defeated by the randomization of the exponent) and that of horizontal techniques which are immune to exponent blinding.

On the other hand the limitation of the Big Mac attack -its ignorance of the intermediate results -is precisely the cause of its noticeable property to be applicable also when the base of the exponentiation is not known from the attacker. The Big Mac attack thus applies when the message is randomized and/or in the case of a Chinese Remainder Theorem (CRT) implementation of RSA. While the horizontal correlation technique does not intrinsically deals with message randomization, we give in the next section some hints that allow breaking those protected implementations when the random bit-length is not sufficiently large.

Horizontal Analysis on Blinded Exponentiation

To protect public key implementations from SCA developers usually include blinding countermeasures in their cryptographic codes. The most popular ones on RSA exponentiation are:

-Additive randomization of the message and the modulus: -Multiplicative randomization of the message: m = r e • m mod n with r a random value and e the public exponent, -Additive randomization of the exponent:

m = m + r 1 • n mod r 2 • n = m + u • n with r 1 ,
d = d + r • φ(n) with r a random value.
All these countermeasures prevent from the classical vertical side-channel analysis but the efficiency of the implementations is penalized as the exponent and modulus are extended of the random used bit lengths.

Guessing the randomized message m In this paragraph we consider that the message has been randomized by an additive (or multiplicative) method, the secret exponent has also been randomized and the message is encrypted by an atomic multiply always exponentiation. We analyze the security of such implementation against horizontal CPA. The major difference with vertical sidechannel analysis is that the exponent blinding has no effect since we analyze a single curve and recovering d is equivalent to recovering d.

Assuming that the entropy of u is λ bits, there are 2 λ possible values for the message m knowing m and n. The first step of an attack is to deduce the value of the random u. This is achieved by performing one horizontal CPA for each possible value of u on the very first multiplication which computes (m ) 2 . Since this multiplication is necessarily computed, the value of u should be retrieved as the one showing a correlation peak. Once u is recovered, the randomized message m is known and recovering the bits of the exponent d is similar to the non blinded case using m instead of m. Consequently, the entropy of u must be large enough (e.g. λ ≥ 32) to make the number of guess unaffordable and prevent from horizontal correlation analysis.

The actual entropy of the randomization In the case of additive randomization of the message, m depends on two λ-bit random values r 1 and r 2 . Obviously, the actual entropy of this randomization is not 2λ bits, and interestingly it is even strictly less than λ bits. The reason is that m = m + u • n with u = r 1 mod r 2 , and thus smaller u values are more probable than larger ones.

Assuming that r 1 and r 2 are uniformly drawn at random in the ranges 0, . . . , 2 λ -1 and 1, . . . , 2 λ -1 respectively, statistical experiments show that the actual entropy of u is about λ -0.75 bits 5 .

A consequence of this bias on the random u is that an attacker can exhaust only a subset of the smaller guesses about u. If the attack does not succeed, then he can try again on another exponentiation curve. For λ = 8 guessing only the 41 smaller u will succeed with probability 1 2 . An extreme case, which optimizes the average number of correlation curve computations, is to guess only the value u = 0 6 . This way, only 38 and 5352 correlation curve computations are needed in the mean when λ is equal to 8 and 16 respectively.

These observations demonstrate that the guessing attack described in the previous paragraph is more efficient than may be trivially expected. This confirms the need to use a large random bit length λ.

Countermeasures

Having detailed the principle and the threats of our horizontal side-channel analysis on exponentiation, We now study the real efficiency of the classical side channel countermeasures and propose new countermeasures.

Hardware Countermeasures

Classical countermeasures consisting in perturbing the signal analysis e.g. clock jitters, frequency clock dividers or dummy cycles, may considerably complicate the analysis but should not be the only countermeasures since efficient signal processing could bypass them depending on their real efficiency.

Techniques consisting in balancing the power consumption of the chip with dual rail, precharge logics or other methods, if really efficient, could be a better solution. However they are expensive countermeasures from the chip surface point-of-view.

Blinding

All SSCA resistant algorithms that can be used to implement the exponentiation -either those protected with atomicity principle or regular ones as square and multiply always and Montgomery ladder -are threatened by the horizontal analysis. It is then necessary to randomize the data manipulated during the computation. As said previously the blinding of the exponent is not an efficient countermeasure here, it is thus highly recommended to implement a resistant and efficient blinding method on the data manipulated , for instance by using additive message randomization with random values larger or equal to 32 bits. As regard to the previous analysis on the actual entropy of u, an additional solution consists in eliminating the bias on u by setting r 2 to a constant value, for instance 2 λ -1.

New Countermeasures

We suggest protecting sensitive implementations from this analysis by introducing blinding into the t-bit multiplications, by randomizing their execution order or by mixing both solutions. These countermeasures are presented on modular multiplication using the Barrett reduction.

Blind Operands in LIM A full blinding countermeasure on the words x i and y j consists in replacing in Alg. 2.1 the operation (w i+j + x i × y j ) + c by (w i+j + (x i -r 1 ) × (y j -r 2 )) + r 1 × y j + r 2 × x i -r 1 × r 2 + c with r 1 and r 2 two t-bit random values. For efficiency purposes, the values r 1 × x i , r 2 × y j , r 1 × r 2 should be computed once and stored. Moreover, these precomputations must also be protected from correlation analysis. For example, performing them in a random order yields (2l + 1)! different possibilities. In this case the LIM operation requires l 2 + 2l + 1 t-bit multiplications and necessitates 2(n + 2t) bits of additional storage.

In the following we improve this countermeasure by mixing the data blinding with a randomization of the order of the internal loops of the long integer multiplication.

Randomize One Loop in LIM and Blind This countermeasure consists in randomizing the way the words x i are taken by the long integer multiplication algorithm. In other words it randomizes the order of the lines of the schoolbook multiplication. Then computing correlation between x i and C k i,j does not yield the expected result anymore. On the other hand it remains necessary to blind the words of y. An example of implementation is given in Alg. 5.3.

The random permutation provides l! different possibilities for the execution order of the first loop. For example, using a 32-bit multiplier, a 1024-bit long integer multiplication has about 2 117 possible execution orders of the first loop and with 2048-bit operands it comes to about 2 296 possibilities. Compared to the previous countermeasure, Alg. 5.3 requires only l 2 + l t-bit multiplications and 2t bits of additional storage.

Remark One may argue that in the case of very small l values such a countermeasure might not be efficient. Remember here that if l is very small, the horizontal correlation analysis is not efficient either because of the small number of curve segments.

Randomize the Two Loops in LIM

We propose a variant of the previous countermeasure in which the execution order of the both internal loops of the long integer multiplication are randomized. This means randomizing both lines and columns of the schoolbook multiplication. The main advantage is that none of the operands x i or y j needs to be blinded anymore. The number of possibilities for the order of the l 2 internal multiplication is increased to (l!) 2 . An example of implementation is given in Alg. 5.4.

Unlike the two previous countermeasures, Alg. 5.4 requires no extra t-bit multiplication compared to LIM. It is then an efficient and interesting countermeasure, while the remaining difficulty for designers consists in implementing it in hardware.

Algorithm 5.4 LIM with lines and columns randomization

Input: x = (x l-1 x l-2 . . . x1x0) b , y = (y l-1 y l-2 . . . y1y0) b Output: MatrixRandLIM(x,y) = x × y Step 1. Draw two random permutation vectors α, β in [0, l -1] Step 2. for i from 0 to 2l -1 do wi = 0 Step 3. for h from 0 to l -1 do i ← α h for j from 0 to 2l -1 do cj = 0 for k from 0 to l -1 do j ← β k (uv) b ← wi+j + xi × yj wi+j ← v and ci+j+1 ← u u ← 0 for s from i + 1 to 2l -1 do (uv) b ← ws + cs + u ws ← v Step 4. Return(w)

Concerns for Common Cryptosystems

We presented our analysis on straightforward implementations of the RSA signature and decryption algorithms which essentially consist of an exponentiation with the secret exponent. In the case of an RSA exponentiation using the CRT method our technique cannot be applied since the operations are performed modulo p and q which are unknown to the attacker. On the other hand DSA and Diffie-Hellman exponentiations were until now considered immune to DPA and CPA because the exponents are chosen at random for each execution. Indeed it naturally protects these cryptosystems from vertical analysis. However, as horizontal CPA requires a single execution power trace to recover the secret exponent, DSA and Diffie-Hellman exponentiations are prone to this attack and other countermeasures must be used in embedded implementations. It is worth noticing that ECC cryptosystems are theoretically also concerned by the horizontal side-channel analysis. However since key lengths are considerably shorter -for instance ECC 224 bits is considered having equivalent mathematical resistance than RSA 2048 -very few curves per scalar multiplication will be available for the attack. On the other hand, scalar multiplication involves point doublings and point additions instead of field multiplications and squarings. Each point operation requires about 10 modular multiplications and thus correlation computation could take advantage of all the corresponding curves. Nevertheless, a factor of about 10 should not balance the key length reduction which has a quadratic influence on the number of available curve segments.

Conclusion

We presented in this paper a way to apply classical power analysis techniques such as CPAon a single curve to recover the secret key in some public key implementations -e.g. non CRT RSA, DSA or Diffie-Hellman -protected or not by exponent randomization. We also applied our technique in practice and presented some successful results obtained on a 16-bit RISC microprocessor. However even with bigger multiplier sizes (32 or 64 bits) this attack can be envisaged depending on the key size, cf. Section 4.1. We discussed the resistance of some countermeasures to our analysis and introduced three secure multiplication algorithms.

Our contribution enforces the necessity of using sufficiently large random numbers for blinding in secure implementations and highlights the fact that increasing the key lengths in the next years could improve the efficiency of some side-channel attacks. The attack we presented threatens implementations which may have been considered secure up to now. This new potential risk should then be taken into account when developing embedded products.

Further work could target the use of other values and distinguishers for the horizontal correlation analysis and then improve its efficiency. Possible ideas include: using more intermediate values, some likelihood tests, guessing simultaneously many bits of the secret exponent to increase the number of available curves for the analysis, using different models like the bivariate one for correlation factor computation on curves. Considering that l ≥ 500 should be enough to perform the horizontal correlation analysis, many implementations may be subject to this attack.

Fig. 1 . 2 .

 12 Fig. 1. Vertical Side Channel Analysis Fig. 2. Horizontal side-channel analysis

Fig. 3 .

 3 Fig. 3. Beginning of a long integer multiplication power curve, lines delimitate each C k i,j

Fig. 4 .Fig. 5 .

 45 Fig. 4. Vertical CPA on value yj. Fig. 5. Vertical CPA on value xi × yj.

Fig. 6 . 7 .

 67 Fig. 6. Horizontal CPA on value ai × mj. Fig. 7. Horizontal CPA on value mj.

r 2

 2 being λ-bit random values different each time the computation is executed, and u = r 1 mod r 2 .

Algorithm 5 . 3 Step 1 .

 531 LIM with lines randomization and blinding Input: x = (x l-1 x l-2 . . . x1x0) b , y = (y l-1 y l-2 . . . y1y0) b Output: LinesRandLIM(x,y) = x × y Draw a random permutation vector α = (α l-1 . . . α0) in [0, l -1] Step 2. Draw a random value r in 1, 2 t -1 Step 3. for i from 0 to 2l -1 do wi = 0 Step 4. for h from 0 to l -1 do i ← α h , ri ← r × xi and c ← 0 for j from 0 to l -1 do (uv) b ← (wi+j + xi × (yj -r) + c) + ri wi+j ← v and c ← u while c = 0 do uv ← wi+j + c wi+j ← v, c ← u and j ← j + 1 Step 5. Return(w)

Fig. 8 .Fig. 9 .

 89 Fig. 8. Power curve of a leaking square and multiply algorithm

Table 1 .

 1 Examples of n, t, and l values with the number of available segments l 2

	length n in bits multiplier size t	l	l 2
	2048	32	64 4096
	2048	64	32 1024
	1536	32	48 2304
	1536	64	24	576
	1024	16	64 4096
	1024	32	32 1024
	1024	64	16	256
	512	16	32 1024
	512	32	16	256

Referring to the description given in 4.1 the method using the curve segments C s +3 i,j validates that the value produced by the multiplication by m is involved or not in the next squaring operation. A similar technique also applies to the Montgomery ladder.

The loss of 0.75 bits of entropy is nearly independent of λ for typical values (λ ≤

64).[START_REF] Kaya | Analysis of sliding window techniques for exponentiation[END_REF] Or u = 1 if the implementation does not allow u = 0.

Acknowledgments

The authors would like to thank Christophe Giraud and Sean Commercial for their valuable comments and advices on this manuscrit.

A Square and Multiply Power Curves Examples

The following figures illustrate the SPA as described in Section 3.1. Fig. 8 corresponds to the power curve execution of a classical square and multiply algorithm. We can observe that the multiplication operation has a different pattern from the squaring one. The multiplications can then be identified and the secret exponent be recovered.

On Fig. 9, the implementation analysed uses the atomicity principle. It allows the exponentiation to be SSCA resistant since we cannot distinguish anymore the squarings from the multiplications.

B Examples of l and l 2 values

In this paragraph, we illustrate with examples the property: the longer the keys, the more efficient the horizontal correlation analysis. The following table pro-