Kevin Carpentier
email: kevin.carpentier@hds.utc.fr

Domitile Lourdeaux
email: domitile.lourdeaux@hds.utc.fr

Generation of learning situations according to the learner's profile within a virtual environment

Keywords: virtual environment for training, adaptative, knowledge model

HAL is

Introduction

Nowadays' working contexts are getting more and more complex, they are composed of a wide range of situations. Training is a major issue in industry for different reasons. It prevents accident in domain where security is critical (high-risk industry, nannies training), it fosters productivity in high-performance industry (aeronautic assembly, submarine maintenance), it also prevents manufacturing defects where customer satisfaction is a key point. Most commonly, in a professional environment, operative attends a short training before getting on the site. They lack of experience and each new situation is difficult to handle because it is a whole new one. It is widely accepted that experience is the most important way to develop professional skills in these domains. By encountering various situations, apprentices may consolidate their knowledge and build their own effective mental representations of the task processing. Moreover, it is accepted that situated learning can offer an efficient learning framework. As such training is expensive and requires the material to be requistionned, virtual environment for training have been proven to be a good solution to provide learning in complex situations [START_REF] Amokrane | Virtual Reality Contribution to Training and Risk Prevention[END_REF].

By simulating the work context, these environments deliver a wide range of real situations. However, providing content is not enough to ensure an efficient learning. The content must be adapted to the learner's profile and historic : what has been learned? What needs to be learned next? Which errors are most commonly made? Besides, the content answering these questions must be provided in an engaging way. Our goal is to generate pedagogical content adapted to the learner level and presented through a story in which the learner will feel involved. The content proposed must enable learners to meet many and varied kinds of situations and keep their motivation at a high level. To fulfill this requirement, we propose to dynamically generate relevant learning situations with regard of the learner's trace and learning objectives. A relevant learning situation is a set of states of the world that will test a subset of skills and knowledge in a efficient and engaging way. As our works fits in the situated learning theory, we considered that each learner builds his own mental representation in disregard of an elicitation of knowledge and skills. Thus, it makes it difficult to control knowledge acquisition. Another issue is to ensure that the generated content is relevant, which means it fulfills both pedagogical and narrative requirements. This also raised the underlying question about the balance between narrative and motivational factors and pedagogical needs.

Seldon, standing for ScEnario and Learning situations adaptation through Dynamic OrchestratioN, aim to generate and control scenario within a virtual environment. As part of the Seldon model, we propose the Tailor model to generate a canvas which is a sequence of constraints on the state of the world, called situations, that should be met or prevented to facilitate knowledge learning and skills acquisition. The canvas is then used by the other part of Seldon, a scenario planner, Director [START_REF] Barot | Dynamic Scenario Adaptation Balancing control, Coherence and Emergence[END_REF] to constrain the simulation. This paper presents our contribution on activities selection based on belief about learner's aptitudes and pedagogical needs. In section 2 we present how our contribution positions in relation to different approaches on adaptive scenarisation. Then, we introduce the overall process of situation constraints generation and present a detailled method of selection of the constraints depending on pedagogical needs in section 3. Section 4 shows an illustration of this selection through the case of nannies training. Then we will present the perspectives we foresee to extend this work and conclude over the whole contribution.

RELATED WORKS

Adaptive scenarisation is the process of reacting to user's actions to provide content fitted to their need. In videogames, it might be used to adjust difficulty according to player's level without using typical discrete mode such as "Easy","Hard", etc. With adaptive features, players are always in the flow [START_REF] Csikszentmihalyi | Flow: The Psychology of Optimal Experience[END_REF]: the difficulty remains high enough to propose a suitable challenge, yet, players can overcome it so that they do not get bored or frustrated. Such a concept might be used to adapt difficulty in a training session so that learners keep a high level of motivation. The system can propose activities that are always difficult enough to challenge the learner but always manageable to prevent frustration and loss of motivation. Our objective is twofold: providing adapted content [START_REF] Amokrane | Virtual Reality Contribution to Training and Risk Prevention[END_REF] and presenting this content in such a manner it does not cut the user from the flow and, moreover, motivate him [START_REF] Barot | Dynamic Scenario Adaptation Balancing control, Coherence and Emergence[END_REF].

The adaptation can be made at different levels of granularity. A first approach is to have a global adaptation: a whole scenario has been written [START_REF] Marion | Modélisation de Scénarios Pédagogiques pour les Environnements de Réalité Virtuelle d'Apprentissage Humain[END_REF] or generated [START_REF] Niehaus | Automated Scenario Adaptation in Support of Intelligent Tutoring Systems[END_REF] and the outcomes of the events were scripted beforehand. This approach allows the building of a scaffolding scenario which present many advantages:

-Pedagogical coherence: the scenario ensures a progressive learning through the session, assistance can be given easily at relevant key points; -Narrative involvement: it is therefore possible to unfold the event as a story which will involve the learner.

A main drawback is the lack of reactivity of the system. As the whole session has been planned, the system cannot reorient the scenario to adapt to the very current learner's state. The only way to cope with it is to foresee each possible path which can represent a huge amount of work. An opposite approach is to provide reactive adaptation by controling the outcomes of learner's actions. It enables:

-Dynamic adaptation: the system triggers outcomes of learner's actions and provides assistances depending on pedagogical needs.

For example, in the application V3S [START_REF] Barot | V3S, a Virtual Environment for Risk Management Training[END_REF], the triggering of a hasardous matter leak is computed in real-time by Hera [START_REF] Amokrane | Pedagogical System in vVirtual Environment for High-Risk Sites[END_REF], an intelligent tutoring system, according to a learner's model.

The simulation where the adaptation takes place can be run with opposite approaches: the controlled approaches versus the emergent approaches.

The controlled approach aims to provide a very efficient learning by orchestrating each part of the simulation: state of the objects, virtual character's behaviours, possibilities of action the learner, etc. It permits:

-Pedagogical control : each element of the simulation serves the scenario and pedagogical needs.

This approach which is used in the Generic Virtual Training [START_REF] Gerbaud | GVT: a Platform to Create Virtual Environments for Procedural Training[END_REF] helps building pedagogically efficient scenarios but disables the possibility to encounter unintended -though relevant -situations. Moreover, such an approach demands an exhaustive modeling of the world functionment which handicaps the evolutivity of the system. The whole modeling has to be reconsidered to avoid incoherence each time an author adds new contents. Any attempt to interfere with the simulation can cause incoherence for the learner: virtual characters become unpredictible, states of objects changes with no coherent reason. As a result, there is no way to explain a posteriori the unfolding of events. These explanations are critical for the learner to understand causes and consequences of events and actions and they can be provided at the end of the session or reviewed by a teacher. By a clever modelling of small behaviors of the world, emergent approaches allow new situations to arise [START_REF] Shawver | Virtual Actors and Avatars in a Flexible User-determined-scenario Environment[END_REF]. It also enables:

-Freedom of action: learners are not framed by the task they are supposed to do, they can experiment and discover the outcomes of their actions; -Autonomous Virtual Characters: as they are not being controlled by a supervisor, virtual characters maintain their autonomy and their behaviours remain coherent throughout the simulation run.

The issue with emergent approaches is the lack of pedagogical control. The simulation runs itself according to initial parameters and there is no way to orchestrate the events to adapt the simulation to the current learner's state. Each of these approaches has attractive features but none of them fulfills our requirements as explained below.

3 Proposition

Approach

Our work aims to provide a relevant adaptation at different level of granularity. At the lowest level, adaptation should modulate the consequences of the actions of the learner, this means an even set of events might have different outcomes depending of the expertise of the learner. Then, the adaptation must work on a middle level basis by producing complex sequences of events leading to a specific learning in a session. Finally, skills development requires a learner to follow a path of different learning situations during different learning sessions, the adaptation should also provide information about the path to follow between different sessions. For this purpose, we will try to adopt a balanced approach which is both global and local.

Besides, learners should have a total freedom and the system must react as it would in reality to help them to develop skills from their mistakes. Technical, organisational and human systems are getting more and more complex in working context. An exhaustive explicitation of each possible scenarios beforehand would result in a combinatorial explosion. To adress the growing comlexity of such systems, we chose to model them through an emergent approach. However, as our purpose is to provide an efficient situated learning, we must ensure that relevant assistances are provided to learners as they would be provided in a working context. Moreover, we need to orchestrate dynamically the course of the training to adapt to current learner state.This can only be achieved by controlling the flow of events to some extent. We need to adopt an emergent approach to model the world but we want to provide pedagogical control over it.

To be able to have both global and local adaptation with pedagogical control over an emergent simulation, we propose to orient dynamically the simulation towards specific situations which are consistant with the current state of the world, without breaking the coherence of neither object states nor the behaviour of virtual characters. This is the purpose of Seldon, standing for ScEnario and Learning situation adaptation through Dynamic OrchestratioN), which is a part of the Humans platform described below.

HUMANS Framework

The HUman Models-based Artificial eNvironments Software platform is dedicated to the simulation of virtual environments within complex domains where human factors are critical. humans platform allows high cognitive virtual characters and learners to coexist in a simulation.

humans uses three models which were designed to be informed by domain experts (ergonomists, didacticians,etc.):

-Domain (figure 1) describes the world in a static way, the object, physical or abstract, that exists in the world and the relations between them through an ontology. It also includes a dynamic description: possible actions, the behaviours these actions trigger and events that might occur through rules; These models manipulate common entities and each unit (Entity in Domain, Task in Activity and Event in Causality) can be tagged to specify something to which a unit is related (skills, risks, performance criteria.etc.). Tailor is the first of two parts constituting Seldon. It produces constraints for the second part, Director, whose role is to apply this constraints to the simulation. Second part computes this model to determine a set of situation constraints that fulfill pedagogical needs along with metrics on these situations. They describe if situations shoud be avoided or should be met. Situation constraints describe states of the world which should bring learners to discover/develop/use specific skills and knowledge. One of these situation contraints defines a goal situation toward the simulation should be leading. This situation is not the end of the scenario but merely one of its key points.

In a third part, key points are then framed into common narrative patterns to generate a story and modulate the dramatic tension. The canvas is the succession of situations constraints build upon time. The description of the metrics and of the narrative framing is beyond the scope of this paper.

We present in the following subsection a model for selecting a goal situation according to a uncertain learner's model. -Learner's inputs: each session of training the learner follows is recorded through a trace based on HERA model [START_REF] Amokrane | Pedagogical System in vVirtual Environment for High-Risk Sites[END_REF]. As the model is based on activity analysis, traces identify previous situations encountered, errors, causes and consequences, risk produced. Traces are also enriched with activity traces of virtual characters as well as the tracking of causal chains within the environment; -Teacher's inputs: the teacher can influence the simulation beforehand at different levels: he can select situations which should be encounter during the session in the causality model, task to be performed in activity model and performance criteria to favour.

Diagnosis. On this purpose, the first matter is to establish and maintain a diagnosis of learner's current level of knowledge. As seen in [START_REF] Brusilovsky | User Models for Adaptive Hypermedia and Adaptive Educational Systems[END_REF], most systems use an elicitation of knowledge, of the influences they have between each other and of the events which are clues of learning. Actually, we fit our work in the paradigm of situated learning, it would be paradoxal to build a model of skills and knowledge acquisition. Moreover, we want to produce a progressive learning individualized to each learner. Vygotsky proposes the model of Zone Proximal of Development (ZPD) [START_REF] Vygotsky | Mind in Society[END_REF] for the context of education in which a student can develop skills inside its confort zone and enlarge it by the help of the teacher. We think the ZPD can be used in a more general learning context than education and that the teacher, which is responsible of the scaffolding, might be played by virtual scaffolding and by an dynamic scenarisation of events. To operationnalize this approach, we choose to deal with a belief the system has in the capabilities of a learner to handle a certain class of situations depicted by constraints. This constraints include all the variable of a situations as observed on site. First, tasks to perform are an obvious variable of situation. Then, constraints are also the cognitive variables which are the parameters to take into account to perform the tasks successfully. We finally choose to add "tags", which are meta-information about task. They help defining if a task is related to some domain-dependant concept such as Quality, Safety, Cleanness, etc. All this variables and there meanings are informed by pedagogical experts of the domain within the models presented in 3.2. These constraints "mold" a space where each situation is described by is component for each variable. Situations encountered by the learner are reported with a belief on whether the he/she handled it successfully or unsucessfully. This space is designed so that two points in space are representative of semantically close situations in the simulation. Beliefs are propagated around each point to estimate a belief on the capabilities of a learner to handle a situation matching another set of constraints semantically close. The Transferable Belief Model and the conjunctive rule of combination (CRC) described in [START_REF] Smets | The Transferable Belief Model[END_REF] are used to represent and udpate these beliefs.

For each point of this space, describing a class of situations, we have four values:

a -Belief on the ability to handle this situation, d -Belief on the disability to handle this situation, i -Ignorance, either ability or disability c -Conflict between belief of ability and disability With a

+ d + i + c = 1
Tailor parses traces produced by the trace-based system called monitor that exists within the humans framework. Based on activity and causality models, monitor aims to record every action agents makes whether they are real learners or virtual characters. These actions are linked to task and high-level tasks in the activity hierarchy and are associated to a potentiality to trigger an error, a risk or affecting a performance criteria. Each trace is used as a source of information to update the beliefs about a class of situations. New values are compute according to the application of the conjunctive rule of combination as shown in 1,2,3,4.

a new = a cur * a source + i cur * a source + i source * a cur ( 1
)
d new = d cur * d source + i cur r * d source + i source * d cur (2)
i new = i cur * i source (3)
c new = 1 -h new -d new -i new (4)
Where h cur , d cur , i cur are the current values, h source , d source , i source are values provided by the trace and h new , d new , i new , c new are the updated values.

The association between beliefs and the multidimensionnal space described above draws our ZPD we call zpd-space.

Pedagogical Selection of Activities.

As the learner progresses throughout activities and sessions, the space is filled with points and associated beliefs are updated thanks to the monitoring module.

Tailor will then select a set of points in this space to generate a new situation. The difficulty lies in determining which points will produce an efficient learning. The selection is made based on the 4 values aforementionned using pedagogical rules.

-Points where belief has a high ignorance-value are not likely to be interesting; -Points where belief has a high ability-value are not interesting to produce new learning, but they can be used in the beginning of the session to make the learner at ease; -Points where belief has a high disability-value are interesting, because they are the proof of an error, a violation and more generally a misconception. Depending on specific pedagogical rules, the situation will be avoided or, on the contrary, a learning situation will be generate to break the misconception through an assistance; -Points where belief has a high conflict-value are interesting. Mathematically, it means the different sources of information are contradictory. In our case, it means the learner is able to handle a situation in a specific context but a misconception prevent him from using the same skills in another context.

A set of pedagogical rules helps selecting relevant points according to these values and pedagogical objectives. After this filtering, Tailor compute Domain, Activity and Causality model to determine which events and which activities responds to these constraints.

Output Data. At each iteration, Tailor generates a set of situation constraints associated to a desirability which represent how desired this state of the world is (see Table 1). A negative value describe a situation that should be avoid. One situation is tagged as the goal situation. A situation is depicted by a subset of triple describing a specific state of the world using the formalism of Domain. [START_REF] Pastré | La Conceptualisation dans l'Action : Bilan et Nouvelles Perspectives[END_REF]. We use this information to design a zpd-space. For the sake of the example, we will only focus on two dimensions of the zpd-space. The first dimension we consider, named Material, depicts the different materials on which the learner has to work. These include common alloy but also composite material which requires special care. The second dimension, named Time Pressure, depicts the level of time which is set upon the operative to perform his work. The pedagogical objective has arbitrarily been set to Material = Composite. In the following example M stand for the Material axis and TPL for the Time Pressure Level axis. Step 1 : Initialisation. In this example we consider there is no conflict, and that the learner has successfully handled situation S 1 (figure 6). The darker the color the surer the system knows that the learner will be able to handle a situation generated from this point. Blank areas express the lack ok knowledge about the learners habilities. The ZPD is where the belief on the ability of the learner is beyond a threshold (0.4 in this case).

Step 2. In regard of the pedagogical objectives, which here emphasize on M = Composite, the system selects points to privilege this kind of situation. The point Fig. 7. Situations generation (M = Composite1, T P L = 1) is selected (figure 7). By computing the Activity model, Tailor determines tasks requiring a (M = Composite1, T P L = 1) set of skills. The task "Drilling the front bark on the A3YY" is an activity that fulfills this requirement. In regard with this, the scene is initialized with a bark of an A3YY where the learner would be asked to fix a support on the bark.

Situations

Goal Desirability:1 States: (?prescription :has-task ?Fix_piece) (?Fix_piece :has-support Support01) (?Fix_piece :has-bark ?Bark01) (Bark01 :has-type :composite) (?prescription :has-delivering-delay ?time) (?time :has-hour "24")

Step 3. The learner reacted well to the previously generated situation by making good quality drilling and taking into account specificities of composite material, the ZPD-space is updated. The point SG(M = Composite1, T P L = 3) is now selected (figure 8)., the system has a belief of 0.4 for the learner to handle this class of situations. This class of situations will allow the evaluation of the capacities of the learner to work with composite material with a time pressure. By computing the Activity model, Tailor determines that time pressure is induced when the delivering delay is reduces and the foreman ask for a quicker delivering (which is an action called AskForHaste ). But, a "rush" in work may cause an overcrowded workspace by virtual agent which will react to the new state of the world, yet this is not the kind of situation that has to be encountered.

Final

Step. In order to deal with the time pressure, the learner choose not to do some specific tasks. These task are allowed not to be done when handling common material. But, these task are mandatory when handling composite material. This shows a lack in the knowledge of the learner. The ZPD-space is updated accordingly (figure 9).. In order to prevent future mistake, Tailor propose to trigger crack in the panel. Thus, the learner will likely understand that more care were needed. In the ZPD-Space, the information of a remediation has been recorded for this class of situations (M = Composite1, T P L = 3) . The effectiveness of the remediation will be tested in a further training session.

Perspectives and future works

The ZPD-space we are currently using are designed by-hand according to the knowledge models informed by didacticians and ergonomists, i.e, we choose the axis, their scale and their meaning. Future works will explore how to generate those axis automatically by parsing our knowledge models. The issue is that some variables migh correlated which may add a flow on our process. We may use data analysis method such as principal component analysis [START_REF] Pearson | On Lines and Planes of Closest Fit to Systems of Points in Space[END_REF] to build a new space with uncorrelated variables. Selection of activities is the first part of our work. To provide adapted content is essential but to involve the learner, we need to use motivational factors. Modulating the dramatic tension is a possible solution. To create tension, a story must be built upon the events and the world depicted within the simulation. The aim is to provide an interest for the learner by showing the virtual characters as story characters who can be helpers or opponents, the events as plot points that will increase or decrease the tension. We plan to use narrative pattern, as described by [START_REF] Campbell | The Hero With a Thousand Faces[END_REF], [START_REF] Propp | Morphology of the Folktale[END_REF] or [START_REF] Greimas | Sémantique structurale: recherche et méthode[END_REF] to extends current pedagogicial situations. The element described by the situations will be fitted with element from a pattern such as location, helpers, opponents, goal,etc. For one pedagogical situation, many narrative configurations are possible. We will use a measure of the narrative utility based on earlier events in the simulation. The utility will maximize if it furthers the development of the story depicted in past events without disrupting the whole coherence.

Conclusions

We proposed in this paper a model to dynamically generate scenarios in a virtual environment regarding learner's capacities. The process uses a phase of diagnosis which compute traces at the initialisation and in real time. It operationnalizes the theory of zone of proximal development through a multidimensionnal space of beliefs, updated at each task performed by the learner within the virtual environment. Then the system computes current world state to determine which situation can take place to answer ZPD and pedagogical objectives requirements. We build a first prototype within the Humans platform working on the example of aeronautics assembly. Our future works will focus in the narratives consideration by framing the successive situations in a narrative pattern to relate a story. Besides, we are exploring new method to build the zpd-space.

Fig. 1 .

 1 Fig. 1. Part of an ontological representation of DOMAIN

Fig. 2 .Fig. 3 .

 23 Fig. 2. Hierarchical representation of ACTIVITY

Fig. 4 .

 4 Fig. 4. General Overview

Fig. 5 .

 5 Fig. 5. A screenshot of NIKITA -Aeronautics training simulator

Fig. 6 .

 6 Fig. 6. ZPD-space initialisation in aeronautics training simulator

Fig. 8 .

 8 Fig. 8. ZPD-space udpate and new activities selection

Fig. 9 .

 9 Fig. 9. End of training session

Table 1 .

 1 Situations and desirability.

	Situation constraints Desirability
	Sit1	D1 ∈ [-1, 1]
	...	...
	Sitn	Dn ∈ [-1, 1]
	Sit Goal	1

4 Example: Training in aeronautics assembly

Acknowledgements

This work is part of the ANR project: NIKITA (Natural Interaction, Knowledge and Immersive systems for Training in Aeronautic). Partners are: Heudiasyc, Paris Descartes University, CEA-LIST, Emissive, EADS, AEROLIA and the technical school Henry Potez . We want to thank Catherine Delgoulet and Vincent Boccara from the LATI for their torough analysis which enable us to build our use-case.


Jean-Christophe Audru

Does

Does Science Improve The General Public Information? The Example of Preparedness Actions

Does Science Improve The General Public Information? The Example of Preparedness Actions

For The Seismic Risk in Martinique (FWI).

In 2006, Martinican scientists and stakeholders involved in seismic safety formed the "Réplik" working group ("aftershock" in French). This poster presents a mid-term appraisal of the seismic awareness campaign organized by "Réplik" from 2006 to 2011, and how it has modified, or not, local preparedness.

Jean-Christophe AUDRU BRGM (French Geological Survey) 97200 Fort-de-France, Martinique Is. jc.audru@brgm.fr www.brgm.fr However, people show little interest in science because it does not help them in practical prevention actions (family/office preparedness, home/car rescue kits, fastening of furniture, construction techniques, etc.). Moreover, with years, a growing discrepancy is noted between the self-evaluated awareness and the actual preparedness.

  To remain attractive and efficient, and to respond to the public's expectations, educational actions must anchor into Martinican culture: reconsideration of cultural beliefs and religion, use of Creole language, comprehensive messages on TV and radio, participatory experiences in seismic or tsunami drills… and only a little bit of science! Martinique Island within the Caribbean-Atlantic plate-boundary setting & local effects of the Nov.2007 (7.4) earthquake. Evolution of awareness and of several preparedness topics among successive polls from 1999 to 2010 within the Martinique population. "Réplik" educational supports: magnets, posters, leaflets, mouse pads, spots (for TV, cinema or radio stations), websites, travelling theatre skits, scientific conferences, art exhibitions, information in fairs or hardware stores, toll-free phone number, participation in Carnival paradestee-shirts, caps, whistles, etc. "Réplik" actions target residents and non-residents preparedness. Science produces local studies dealing with earthquakes or tsunamis damage simulations: these encouraged local authorities to organize a successful 24hsimulation drill in 2008. Science also promotes up-to-date scientific ideas instead of fakes and rumors disseminated by local beliefs or by the internet. Much more detail in: Audru J.C, Vernier J.L., Capdeville, B., Salindre, J.J. and Mouly É. (2013) -Preparedness actions towards seismic risk mitigation for the general public in Martinique, French Lesser Antilles: a mid-term appraisal. Natural Hazards and Earth System Sciences 13, pp. 2031-2039 (doi:10.5194/nhess-13-2031-2013) Notoriety of Réplik actions Perception of prevention and preparedness actions


Guilherme Perin

Laurent Imbert

Lionel Torres

Philippe Maurine

Attacking Randomized Exponentiations Using Unsupervised Learning

Keywords: RSA, Randomized Exponentiation, Electromagnetic Analysis, Unsupervised Learning, Clustering Algorithms, Single-Execution Attacks

Countermeasures to defeat most of side-channel attacks on exponentiations are based on randomization of processed data. The exponent and the message blinding are particular techniques to thwart simple, collisions, differential and correlation analyses. Attacks based on a single (trace) execution of exponentiations, like horizontal correlation analysis and profiled template attacks, have shown to be efficient against most of popular countermeasures. In this paper we show how an unsupervised learning can explore the remaining leakages caused by conditional control tests and memory addressing in a RNS-based implementation of the RSA. The device under attack is protected with the exponent blinding and the leak resistant arithmetic. The developed attack combines the leakage of several samples over the segments of the exponentiation in order to recover the entire exponent. We demonstrate how to find the points of interest using trace pre-processing and clustering algorithms. This attack can recover the exponent using a single trace.

Introduction

Not only designers of cryptographic devices have to implement the algorithms efficiently, they also have to ensure that sensible information that leaks through several side-channels (time, temperature, power consumption, electromagnetic emanations, etc.) during the execution of an algorithm, remains unexploited by an attacker. If not sufficiently protected, both symmetric and asymmetric cryptographic implementations are vulnerable to these so-called side-channel attacks (SCA). For public-key algorithms such as RSA, the main operation to be armoured consists of a multi-digit exponentiation over a finite ring. In this paper, we present an improved single-execution attack on a randomized implementation of RSA. However, the ideas and tools that we exploit would also apply in the context of CRT-RSA and (hyper)elliptic curves.

Attacking an exponentiation consists of identifying the bits of the exponent, a value that is often to be kept secret (it is either a secret key or a random secret value). Simple side-channel attacks [START_REF] Kocher | Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems[END_REF], which uses a single trace of execution, are easily protected using so-called constant-time algorithms such as square-andmultiply-always [START_REF] Coron | Resistance against differential power analysis for elliptic curve cryptography[END_REF], the Montgomery ladder [START_REF] Montgomery | Speeding the Pollard and elliptic curve methods of factorization[END_REF] or atomicity [START_REF] Chevallier-Mames | Low-Cost Solutions for Preventing Simple Side-Channel Analysis: Side-Channel Atomicity[END_REF]. However, these constant-time algorithms are not sufficient to defeat the more powerful differential [START_REF] Kocher | Differential Power Analysis[END_REF] and correlation attacks [START_REF] Brier | Correlation power analysis with a leakage model[END_REF]. Although very efficient on not sufficiently protected implementations, these attacks suffer from the very large number of traces to be collected in order to recover (part of) the secret. Collision attacks proposed by Fouque in 2003 [START_REF] Fouque | The doubling attack -why upwards is better than downwards[END_REF] are very efficient; they only require two traces of execution on well chosen inputs. All these attacks are generally protected using exponent and/or message blinding using elementary algebraic manipulations. For example, randomization of an RSA exponent relies on the fact that m d ≡ m d+rϕ (n) mod n for any (random) value r (see Section 5). Apart from these well known tricks, randomization can also take place at the arithmetic level. The LRA concept [START_REF] Bajard | Leak resistant arithmetic[END_REF], based on the Residue Number System, seems to be a robust, yet efficient [START_REF] Guillermin | A coprocessor for secure and high speed modular arithmetic[END_REF][START_REF] Perin | Electromagnetic Analysis on RSA Algorithm Based on RNS[END_REF] alternative to more expensive (hardware) countermeasures.

Novel attacks [START_REF] Clavier | Horizontal Correlation Analysis on Exponentiation[END_REF][START_REF] Clavier | ROSETTA for Single Trace Analysis[END_REF][START_REF] Bauer | Horizontal and Vertical Side-Channel Attacks against Secure RSA Implementations[END_REF][START_REF] Bauer | Correlation Analysis against Protected SFM Implementations of RSA[END_REF] have recently emerged. Unlike the well studied family of differential [START_REF] Kocher | Differential Power Analysis[END_REF] and correlation attacks [START_REF] Brier | Correlation power analysis with a leakage model[END_REF], these so-called horizontal correlation attacks (HCA), aim at correlating the Hamming Weight HW(m) of a known message m, with a set of well-chosen sample points t i from one single trace. Some of them [START_REF] Clavier | ROSETTA for Single Trace Analysis[END_REF][START_REF] Bauer | Correlation Analysis against Protected SFM Implementations of RSA[END_REF] are indeed efficient in the presence of message blinding. They exploit the very high regularity of multi-digit exponentiation algorithms and represent a very serious threat against classical randomization countermeasures. A major advantage of single-trace-based attacks is their natural immunity to exponent blinding, since, in many cases, recovering a random exponent is sufficient to break the cryptosystem (see Section 5).

Profiled template attacks can recover the exponent using few traces. As the original template attack [START_REF] Chari | Template Attacks", Cryptographic Hardware and Embedded Systems[END_REF] suggests, the attacker must have full control of the device. In particular, he must be able to send plain-texts of his choice to a known key device. In the case of public-key algorithms, the public-key is known and also can be used in the profiling phase. In this case, the pre-computations whose objective is to build the template set is refereed to as supervised learning. In [START_REF] Hanley | Using templates to distinguish multiplications from squaring operations[END_REF] supervised template attacks are successfully applied on modular exponentiations in order to differentiate squarings from multiplications. More recently, a template attack on constant-time exponentiation algorithms was presented in [START_REF] Herbst | Using Templates to Attack Masked Montgomery Ladder Implementations of Modular Exponentiation[END_REF], while [START_REF] Bauer | Attacking Exponent Blinding in RSA without CRT[END_REF] suggests a technique to attack the exponent blinding. A template attack targeting the memory addressing was presented in [START_REF] Dyrkolbotn | Modified Template Attack Detecting Address Bus Signals of Equal Hamming Weight[END_REF]. All those methods fall into the class of supervised attacks, i.e., a learning phase is required during which the adversary constructs templates by exploring the statistical characteristics of various types of operations.

When the adversary does not have a full control of the device, unsupervised methods are necessary. In [START_REF] Heyszl | Clustering Algorithms for Non-Profiled Single-Execution Attacks on Exponentiations[END_REF], unsupervised learning has been presented to demonstrate the efficiency of localized EM attacks on exponentiations using a kmeans clustering algorithm to differentiate the attacked samples. Their attack is performed on an ECC [START_REF] Hankerson | Guide to Elliptic Curve Cryptography[END_REF] implementation over a binary field using Lopez-Dahab coordinates [START_REF] Lopez | Fast multiplication on elliptic curves over GF(2 m ) without precomputation[END_REF]. The scalar is recovered using leakages collected during the execution of a single scalar multiplication (k ∈ Z,

P ∈ E(F 2 m ) -→ [k]P ∈ E(F 2 m ).
However, their attack relies on the ability to acquire several simultaneous EM traces from different probe positions1 . The leakages obtained from these multimeasurement sources are then combined together in order to reduce the signalto-noise ratio. By doing so, they managed to classify the sampled points into two distinct sets which correspond to the zero bits (resp. non-zero bits) of the scalar k.

In this paper, we present a single-trace, single-probe unsupervised attack, i.e. the side-channel data is collected from one EM probe only. In the next sections, we present the setting and statistical tools that we used to recover the entire exponent of a constant-time, randomized RSA implementation. Our attack is unsupervised because it does not require any a priori knowledge of the device, in particular we did not use the public key or send any chosen messages in order to learn the characteristics of the device. The chip under attack is a constant-time, RNS-based FPGA implementation of RSA protected with the Leak Resistant Arithmetic [START_REF] Bajard | Leak resistant arithmetic[END_REF] and exponent blinding. Since all manipulated data is randomized, we explore the remaining leakages due to control instructions and memory activities. As previously demonstrated in the literature [START_REF] Itoh | Address-Bit Differential Power Analysis of Cryptographic Schemes OK-ECDH and OK-ECDSA[END_REF], memory and register addresses leak information related to the secret key. Instead of using simultaneous measurements as in [START_REF] Heyszl | Clustering Algorithms for Non-Profiled Single-Execution Attacks on Exponentiations[END_REF], we combine the cluster classifications of several samples from each bit of the exponent. We thus process the probabilities obtained from this first phase to recover the entire exponent. Our attack requires four phases: trace pre-processing, points of interest identification, fuzzy k-means clustering, and exponent recovery. For this final phase, we present results obtained with three different statistical techniques (majority rule, normal probability density function and Bayesian classifier).

The paper is organized as follows: Section 2 gives details about the randomized exponentiation and the device under attack. The unsupervised learning based on clustering algorithms is detailed in Section 3. Section 4 presents the attack in details and the results that we obtained with the three statistical tools mentioned above. Possible countermeasures are suggested in Section 6.

The Randomized Exponentiation and the Device Under Test

The device under attack is a RNS-based implementation of RSA mapped onto a Spartan-3E xc3s1600 FPGA. For demonstration purposes, we considered a very weak 512-bit RSA. The modular exponentiation is computed with the regular and SPA-protected Montgomery ladder [START_REF] Joye | The Montgomery powering ladder[END_REF] using two sets of RNS bases A and B [START_REF] Bajard | An RNS Montgomery Modular Multiplication Algorithm[END_REF]. The atomic square-and-multiply [START_REF] Chevallier-Mames | Low-Cost Solutions for Preventing Simple Side-Channel Analysis: Side-Channel Atomicity[END_REF] is also a regular and faster exponentiation. However as proposed in [START_REF] Clavier | ROSETTA for Single Trace Analysis[END_REF], randomized exponentiations can be explored through horizontal correlation attacks (HCA) if one of the intermediate operands, in the case the randomized input message, is used in several modular multiplications.

According to the leak resistant arithmetic (LRA) concepts [START_REF] Bajard | Leak resistant arithmetic[END_REF], the RNS moduli can be randomized before each exponentiation. This countermeasure acts as a message blinding technique because and offers a high degree of randomization to the data. Furthermore, HCA exploits the regularity of long-integer multiplication (or squaring). The parallel RNS arithmetic is then a very limiting factor for this attack. Moreover, our hardware is protected with exponent blinding. Alg. 1 shows the randomized exponentiation.

Algorithm 1: LRA-RNS Montgomery Powering Ladder [START_REF] Bajard | Leak resistant arithmetic[END_REF] Data:

x in A ∪ B, where A = (a1, a2, ..., a k ), B = (b1, b2, ..., b k ), A = ∏ k i=1 ai, B = ∏ k i=1 bi, gcd(A, B) = 1, gcd(B, N ) = 1 and d = (d ℓ ...d2d1)2. Result: z = x d mod N in A ∪ B 1 Pre-Computations: |AB mod N |A∪B 2 randomize(A, B) 3 dr = d + r.ϕ(N ) 4 A0 = M M (1, AB mod N, N, A, B) (in A ∪ B) 5 A1 = M M (x, AB mod N, N, A, B) (in A ∪ B) 6 for i = ℓ to 1 do 7 A dr i = M M (A dr i , A dr i , N, B, A) (in A ∪ B) 8 A dr i = M M (A dr i , A dr i , N, B, A) (in A ∪ B) 9 end 10 A0 = M M (A0, 1, N, B, A) (in A ∪ B)
The operation M M (x, y, N, B, A) returns xyB -1 mod N in the two RNS bases A and B. Both squarings and multiplications are computed with the same number of clock cycles.

First, as the exponent is randomized, single-trace attack was the only option. Further, because the manipulated data is randomized with LRA, the target information of our unsupervised attack is not the data contribution in the EM traces. By data, we mean the intermediate variables which depend on the randomly selected RNS bases and the input message. Exponent-dependent decisions are taken by the architecture's control in order to determine the memory address for reading or writing operands before, during and after the modular multiplications. These conditional tests, as well as the accessed memory addresses, cause subtle leakages of information. These are the only sources of leakages that we exploit in the present unsupervised attack. We present the details of our attack in the next sections.

Unsupervised Learning and the Clustering Algorithms

Clustering is one of the most frequently used data mining techniques, which is an unsupervised learning process for partitioning a data set into sub-groups so that the instances within a group are similar to each other and are very dissimilar to the instances of other groups. That is, we shall see what can be done when the collected samples are unlabelled and must be grouped in homogeneous clusters. Two different clustering methods are used in this work: the k-means and the fuzzy k-means algorithms [START_REF] Duda | Pattern Classification[END_REF].

The k-means algorithm is a geometric procedure for finding c means or centers (µ 1 , . . . , µ c ) considering a set of n samples x j , where 1 ≤ j ≤ n. The initialization phase consists in defining the number of clusters c and setting a random sample to each mean µ i . Thereafter, the algorithm computes the Euclidean distances ED i,j =∥ x jµ i ∥ 2 for all n samples to obtain the maximum-likelihood estimation of the means µ i . The k-means algorithm is shown in Alg. 2. The k-means algorithm iterates until no changes in µ i are verified. In all iterations each sample is assumed to be in exactly one cluster. The fuzzy kmeans algorithm relaxes this condition and assumes that each sample x j has some membership with different clusters ω i , rather than belonging completely to just one cluster.

Algorithm 2: K-Means Clustering Algorithm

Initially, the probabilities of cluster membership for each point x j of a n sample vector x are normalized according to all clusters ω i as:

c ∑ i=1 P (ω i |x j ) = 1 (1)
where P (ω i |x j ) is the probability that the sample x j is in the cluster ω i . At each iteration of the fuzzy k-means algorithm, the means (or centers) µ i are recomputed according to the following equation:

µ j = ∑ n j=1 [P (ω i |x j )] b x j ∑ n j=1 [P (ω i |x j )] b (2)
and the new probabilities are recomputed:

P (ω i |x j ) = (1/ED ij ) 1/(b-1) ∑ c r=1 (1/ED rj ) 1/(b-1) , ED ij =∥ x j -µ i ∥ 2 (3)
where b > 1 is a free parameter chosen to adjust the "blending" of different clusters. Its appropriate choice can improve the cluster classification if the analyzed data set is too much noisy. In this work, this parameter is set to 2. Alg. The next section describes the unsupervised attack in four phases. The kmeans algorithm is used in the search for the points of interest. The fuzzy kmeans is employed in the cluster classification after having selected the points of interest.

The Unsupervised Attack

In a realistic assumption for single-execution attacks on exponentiations, the adversary works in a noisy environment and, as already stated in [START_REF] Bauer | Attacking Exponent Blinding in RSA without CRT[END_REF], "single bits are never known with certainty [. . . ] and an SPA attacker [. . . ] can only give a probability that any particular operation is a squaring or a multiplication", if the attacked device executes the square-and-multiply algorithm. If a singleexecution attack is able of recovering 98% of the 1024 exponent bits and the adversary does not know the wrong bit positions inside the exponent, a brute force attack requires ∑ 21 j=0 C 1024 j = 2 144 steps to retrieve the incorrect bits. Therefore, the number of wrong bits in the recovered exponent must be at least very low, otherwise a single-execution attack is impracticable.

When applying non-profiled attacks on a single trace of an exponentiation, the adversary has no knowledge about the operation features (mean µ, variance σ 2 ). All information must be recovered in a unsupervised manner. Regular binary algorithms [START_REF] Joye | The Montgomery powering ladder[END_REF][23] compute the exponentiation iteratively and for each bit of the exponent (or segment) same operations are performed. Thus, a initial partitioning step is applied to the measured electromagnetic exponentiation trace in order to have ℓ segments, each one representing one exponent bit interpretation. The segments are aligned and compressed to reduce the noise and clock jitter effects. Thereafter, as proposed in this attack, several points of interest are identified in each segment by computing an estimated and approximated difference of means. The cluster classification using the fuzzy k-means algorithm is applied in each set of compressed samples, each set representing a selected point of interest and providing an estimated exponent. The last step consists in retrieving the randomized exponent using all estimated exponents obtained with the cluster classification. The proposed attack, divided in four phases, is detailed below.

Phase 1: Trace Pre-processings

The attack starts by acquiring a single execution exponentiation trace from the device, considering the k-th randomized exponent d 1:ℓ,k , where ℓ is the length of the exponent. In our case, the exponentiation is computed using the regular Montgomery ladder algorithm. The EM trace, with size L, is sliced in ℓ operations of multiplications and ℓ operations of squarings, as depicted in Fig. 1. Each multiplication (M i ) or squaring (S i ) in the acquired EM trace contains 74 clock cycles. The oscilloscope sampling rate was set to 20GS/s during the acquisition step and the hardware computes the exponentiation at a clock frequency of 50MHz, resulting in 59200 samples per exponent bit interpretation (M i S i ). The device under attack does not feature any hardware countermeasure, e.g., time disarrangement, dummy cycles or frequency dividers. Therefore, the ℓ segments of multiplication-squarings M i S i , can be easily identified and combined to explore the leakage of information. However, the clock jitter effect is still present in the acquired EM trace and must be suppressed using a trace alignment procedure.

time amplitude M M M M S S S S ... L l 1 1 2 2 3 3 l d 1,k d 2,k d 3,k d ... l,k d 1: ,k l =
Another important role in unsupervised single-execution attacks is to identify the points of interest which present greater leakages. A simple solution consists in averaging the 400 samples of one clock cycle into 1 sample and taking each averaged sample as a point of interest. Here, in order to preserve the information over smaller windows, the trace is compressed by averaging 100 samples into 1 sample. Then, this allows reducing the amount of data from 59200 to 592 compressed samples during an exponent bit interpretation d i,k (denoted by operation ⟨MS⟩ i in the sequel). Now, the ℓ operations are represented by a matrix T :

T =      ⟨MS⟩ 1 ⟨MS⟩ 2 . . . ⟨MS⟩ ℓ      =      t 1,1 t 1,2 • • • t 1,592 t 2,1 t 2,2 • • • t 2,592 . . . . . . . . . . . . t ℓ,1 t ℓ,2 • • • t ℓ,592      (4)
Each row of the matrix T is a set of compressed samples ⟨MS⟩ i = {t i,j } representing an exponent bit interpretation d i,k . The term ℓ is the exponent bit length and, of course, is the iterations number in the algorithm 1 (steps 6 to 9). After the trace pre-processing, the attack enters in the second phase that consists in finding the points of interest.

Phase 2: Finding the Points of Interest

The success of the attack depends on the choice of the points of interest. With profiling or supervised attacks, these points can be found by computing a difference of means and observing the highest peaks of amplitude. In such a case, the adversary has a known key d and computes averaged traces Tr 0 and Tr 1 representing the truncated windows of sampled points when the exponent bit is zero and one, respectively and according to:

Tr 0 = ∑ i ⟨MS⟩ di=0 Tr 1 = ∑ i ⟨MS⟩ di=1 ( 5
)
Because the presented attack aims at revealing the exponent through an unsupervised manner, the attacker should be considered as having minimal knowledge about the target implementation to identify the points of interest. Because all data are randomized, the remaining leakage is related to addressing and control executions. Therefore, by observing and studying the collected EM trace, the attacker can, for instance, localize the time points where the device performs such operations and discard the points that clearly show no compromising information.

Our unsupervised analysis needs a set of points of interest in each segment ⟨MS⟩ i to retrieve the exponent. A basic idea is to initially apply a clustering algorithm over each set of compressed samples {t 1:ℓ,j } (each column of matrix T ) and find 592 approximated exponents d 1:ℓ,j , for 1 ≤ j ≤ 592. In our practical experiments, this leads to the recovery of around 93% of the entire exponent on the most leaking set of compressed samples {t 1:ℓ,j }. It is insufficient. However, this result can be used for calculating approximated and averaged traces Tr 0 and Tr 1 from the approximated exponent d 1:ℓ,j . For this initial step, we considered the k-means clustering algorithm because it is a simple and fast technique. for the real randomized exponent running in the device, is depicted in Fig. 2(c).

Note that the results in Fig. 2(b) and (c) are quite similar and the adversary can select points of interest observing the highest peaks of amplitude in D. In a worst case, the adversary would try to compute approximated difference of mean traces, and selecting points of interest, from each one of the 592 possibilities.

It is clear that the selection of the most leaking point of interest reduces the computational time of the unsupervised attack. Besides, we observed (see Fig. 2) that the highest percentages of correct exponent recovery match with the highest peaks of amplitude in the approximated difference of means D. We used this observation as a heuristic in order to select the points of interest.

Phase 3: Cluster Classification

After computing the approximated difference of mean traces from the set of compressed samples {t 1:ℓ,465 }, let us suppose the selection of u points of interest P = {p j }, for 1 ≤ j ≤ u, among the 592 possibilities. Observing the approximated difference of means D in Fig. 2 A clustering is computed for all set of compressed samples {t 1:ℓ,pj }, for 1 ≤ j ≤ u by applying the fuzzy k-means algorithm. Thus, a classification for these samples in two classes (bits zeros and ones), which leads to one estimated exponent d 1:ℓ,pj per set of samples {t 1:ℓ,pj }, is obtained. Because real attacks work on noisy environments, the clustering over each point of interest p j contains errors of classification. Fig. 3 illustrates the cluster classification error for the set of compressed samples {t 1:ℓ,169 }. Fig. 3(a For each point of interest p j , the fuzzy k-means clustering algorithm returns two centers µ 1 and mu 2 and two groups of clustered samples. A common problem would be to identify what class or operation (exponent bit zero or one) each cluster center represents. With u = 17 cluster classifications into two classes, there will be 2 17 = 131072 different possibilities. The identification of the classes can be performed in two different ways:

1. Instead of selecting random samples to initialize the values µ 1 and µ 2 in the Alg. 3, we select the minimum and maximum samples from the set {t 1:ℓ,pj } according to their amplitudes. The initialization in Alg 3 is done by assigning µ 1 = min{t 1:ℓ,pj } and µ 2 = max{t 1:ℓ,pj }. It ensures that µ 1 < µ 2 after the clustering. Then, comparing the resulting cluster means µ 1 and µ 2 with the amplitude of the approximated difference of means D, and also Tr 0 and Tr 1 , it is straightforward to identify the classes. exponent classified exponent bits d i,k correct d1:40,p 1 1 0 0 0 0 0 0 1 0 0 0 0 1 0 1 1 1 0 0 1 0 1 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 76.02% d1:40,p 2 1 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 1 1 1 1 1 1 0 0 1 0 1 1 0 0 0 1 0 0 0 0 0 1 1 76.42% d1:40,p 3 1 1 0 0 0 1 0 1 1 0 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 1 1 0 1 0 0 1 1 0 0 0 0 0 1 76.42% d1:40,p 4 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 1 0 1 1 1 1 1 1 0 0 1 1 1 0 1 0 0 1 1 1 1 0 0 1 0 76.42% d1:40,p 5 1 1 0 0 0 0 0 1 0 1 0 1 1 0 0 1 0 1 1 1 1 1 0 0 0 1 1 1 1 1 0 0 1 0 0 1 0 0 0 1 78.86% d1:40,p 6 1 0 1 1 0 0 0 0 1 0 0 0 1 0 1 1 0 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 0 1 0 0 1 0 1 79.27% d1:40,p 7 1 0 0 0 0 0 0 1 0 0 0 1 1 0 1 1 0 1 1 1 1 1 1 0 0 1 1 1 0 1 0 0 1 0 0 1 0 0 0 1 78.86% d1:40,p 8 1 1 0 1 0 0 0 1 0 0 0 0 1 0 1 1 0 1 1 1 0 1 1 0 1 1 1 1 0 1 1 1 1 0 0 0 0 0 0 1 80.08% d1:40,p 9 1 0 0 0 0 0 1 1 0 1 0 0 1 1 1 1 0 0 1 1 0 1 1 0 1 1 0 1 0 0 0 0 1 0 0 0 1 0 0 0 80.08% d1:40,p 10 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 1 1 1 1 1 0 0 1 1 1 0 1 1 0 0 1 0 0 0 1 1 1 80.89% d1:40,p 11 1 0 1 0 0 0 0 1 1 0 1 0 1 0 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 0 0 1 0 0 0 0 0 0 1 82.52% d1:40,p 12 1 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 1 1 1 1 0 0 1 1 1 0 1 1 0 1 1 0 0 0 0 0 1 82.52% d1:40,p 13 1 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 0 1 0 0 0 0 1 0 1 83.74% d1:40,p 14 1 0 0 0 0 1 0 1 0 0 0 0 1 0 1 1 0 1 0 1 1 1 1 1 1 1 1 1 0 0 0 0 1 0 0 0 0 0 0 1 89.43% d1:40,p 15 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 1 0 1 1 1 0 1 1 1 1 0 1 0 0 1 0 0 0 0 0 0 1 90.65% d1:40,p 16 1 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 1 1 1 1 1 1 0 1 1 1 1 0 1 0 1 1 0 0 0 0 0 0 1 91.25% d1:40,p 17 1 0 0 0 0 0 0 1 0 0 0 0 1 0 1 1 0 0 1 1 1 1 1 0 1 1 1 0 0 1 0 0 1 0 0 0 0 0 0 1 93.06% d 1:40,k 1 0 0 0 0 0 0 1 0 0 0 0 1 0 1 1 0 1 1 1 1 1 1 0 1 1 1 1 0 1 0 0 1 0 0 0 0 0 0 1 100% d 1:40,k 1 0 0 0 0 0 0 1 0 0 0 0 1 0 1 1 0 1 1 1 1 1 1 0 1 1 1 1 0 1 0 0 1 0 0 0 0 0 0 1 100% Table 1. Cluster classification of the (first 40) exponent bits and the recovery of d 1:ℓ,k using the majority rule.

2. As all selected leaking points may lead to more than 50% of exponent recovery, we take one recovered exponent d 1:ℓ,v from one point of interest v, v ∈ {p j }, and compute the bitwise XOR between this exponent and the other estimated exponent values. Let ℓ be the size of the exponent, d 1:ℓ,pj all the recovered exponents for 1 ≤ j ≤ u, p j ̸ = v, and the bitwise results h 1:ℓ =XOR( d 1:ℓ,pj , d 1:ℓ,v ) for p i ̸ = v. If ∑ ℓ i=1 h i < ℓ/2 then returns NOT( d 1:ℓ,pj ), otherwise keep unchanged.

After the cluster classifications and respective association of the classes, the attack enters in the last step in order to combine all estimated exponents into one final exponent.

Phase 4: Exponent Recovery

The recovery of the final randomized exponent is computed through three different statistical techniques: majority decision, probability density function (pdf) and Bayesian classifier. 1 shows the cluster classification results for the first 40 bits of each estimated exponent d 1:ℓ,pj considering the u = 17 points of interest. Using the majority decision we can retrieve a randomized exponent

Majority Decision: Table

d 1:ℓ,k .
Because the majority rule is a simple statistical procedure, it requires more points of interest for achieving the correct exponent if compared to the next two adopted techniques, as will be demonstrated at the end of this section.

Probability Density Function: In [START_REF] Bauer | Attacking Exponent Blinding in RSA without CRT[END_REF], the probability density function, which is based on the normal distributions parameters N (µ 0 , σ 0 ) and N (µ 1 , σ 1 ), where µ and σ are the mean and the standard deviation, returns the likelihood that a sample t i,j is the operation when the exponent bit d i,k = 0. As the presented analysis is unsupervised, we do not know µ 0 and µ 1 . However, the fuzzy k-means cluster classification returns two means or centers µ 1 and µ 2 for each set of compressed samples {t 1:ℓ,pj } which can be used in place of the means. The standard deviation σ is computed from all the set of samples {t 1:ℓ,pj }, considering the evaluated point of interest p i . Then, the likelihood that a sample t i,pj is an operation when d i,k = 0 is given by the equation below:

p(t i,pj , µ 1 ) = e -1 2 (ti,p j -µ1) 2 /2σ 2 e -1 2 (ti,p j -µ1) 2 /2σ 2 + e -1 2 (ti,p j -µ2) 2 /2σ 2 , 1 ≤ i ≤ ℓ, 1 ≤ j ≤ u (6)
Following, the defined sum of probabilities gives the likelihood that a set of points of interest {t i,p1:u }, representing the operation ⟨MS⟩ i , is an operation performed when the randomized exponent bit d i,k = 0 and is computed by:

S 0,1:u = 1 u u ∑ j=1 p(t i,pj , µ 1 ) 1 ≤ i ≤ ℓ (7)
Then, for 1 ≤ i ≤ ℓ, the following decision returns the estimated randomized exponent bit d i,k :

d i,k = { 0, if S 0,1:u ≥ 0.5) 1, if S 0,1:u < 0.5) (8)
Table 2 shows the final sum of probabilities S 0,1:u and the exponent decision from Eq. 8 considering the 20 first exponent bits d 1:20,k (for space in Table 2) and u = 17 points of interest.

Bayesian Classifier:

The Bayesian decision theory makes the assumption that the decision problem is posed in probability terms. The classifier lies on the computation of the posterior probabilities P (µ c |t i,pj ) which is computed from the prior probabilities P (µ c ) and the probability density function for normal distributions p(t i,pj , µ c ), where c = {0, 1} and p(t i,pj , µ c ) ∈ [0, 1]. Thus, the classification starts by obtaining the pdf estimation for each point of interest t i,pj of each operation i. Again, this analysis considers the two cluster centers µ 1 and µ 2 in the place of means and the standard deviation is computed from all the set of compressed samples {t 1:ℓ,pj }: point probabilities p(ti,p j , µ1) correct d1:20,p 1 0.1 1.0 0.5 0.6 0.7 0.9 0.9 0.4 1.0 0.7 0.6 0.9 0.0 0.8 0.0 0.2 0.3 0.7 0.5 0.1 76.02% d1:20,p 2 0.3 1.0 0.8 0.6 0.8 0.5 0.4 0.1 0.9 0.7 0.9 0.5 0.7 0.9 0.5 0.2 0.8 0.4 0.1 0.2 76.42% d1:20,p 3 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 76.83% d1:20,p 4 0.2 0.9 0.9 0.8 0.6 0.3 0.5 0.2 0.5 0.3 0.7 0.9 0.6 0.2 0.1 0.2 0.8 0.2 0.1 0.1 76.42% d1:20,p 5 0.5 0.5 0.9 0.9 0.9 0.6 0.8 0.3 0.9 0.1 0.8 0.3 0.2 0.6 0.7 0.1 0.8 0.0 0.3 0.3 78.86% d1:20,p 6 0.1 0.7 0.5 0.4 0.8 0.7 0.7 0.9 0.5 1.0 0.8 0.6 0.2 0.9 0.5 0.3 0.9 0.6 0.7 0.4 78.86% d1:20,p 7 0.5 0.8 0.9 0.8 0.9 0.8 0.8 0.0 0.9 0.6 0.9 0.5 0.1 0.6 0.2 0.1 0.9 0.0 0.3 0.1 78.86% d1:20,p 8 0.3 0.4 0.8 0.5 0.6 0.9 0.7 0.0 0.7 0.5 1.0 0.8 0.2 0.8 0.4 0.1 0.8 0.3 0.0 0.2 80.08% d1:20,p 9 0.4 0.7 1.0 0.9 0.9 0.5 0.4 0.1 0.8 0.2 1.0 0.8 0.1 0.4 0.3 0.1 0.7 0.7 0.1 0.4 80.08% d1:20,p 10 0.2 0.9 0.8 0.5 0.7 0.8 1.0 0.4 0.7 1.0 0.8 0.7 0.2 0.5 0.8 0.3 0.6 0.5 0.4 0.1 80.89% d1:20,p 11 0.1 0.7 0.3 0.9 0.7 0.7 0.7 0.2 0.5 0.9 0.3 0.8 0.1 0.5 0.0 0.2 0.2 0.3 0.0 0.2 82.52% d1:20,p 12 0.1 0.6 1.0 0.8 0.6 0.9 0.8 0.2 0.8 0.9 0.9 0.8 0.1 0.9 0.3 0.6 0.8 0.2 0.5 0.1 82.52% d1:20,p 13 0.1 0.8 0.7 1.0 0.7 0.9 0.8 0.7 0.5 0.8 0.9 1.0 0.1 0.2 0.2 0.6 0.6 0.3 0.2 0.3 83.74% d1:20,p 14 0.3 0.7 0.7 1.0 0.9 0.3 0.8 0.2 0.9 0.7 0.9 0.6 0.2 0.6 0.4 0.1 0.9 0.1 0.6 0.2 89.43% d1:20,p 15 0.1 0.7 0.7 0.9 0.7 0.7 0.7 0.6 0.7 0.9 0.6 0.9 0.2 0.9 0.2 0.4 0.8 0.4 0.2 0.7 89.43% d1:20,p 16 0.2 0.8 1.0 0.8 1.0 0.9 0.9 0.3 0.5 0.9 0.7 0.7 0.0 0.

The probability density functions p(t i,pj , µ 1 ) and p(t i,pj , µ 2 ) are obtained for 1 ≤ i ≤ ℓ and 1 ≤ j ≤ u. Considering P (µ c ) as the prior probabilities for the points of interest p j-1 , where c = {0, 1}, by Bayes's formula we obtain the posterior probabilities P (µ c |t i,pj ) for the operations i and points of interest p j : P (µ 1 |t i,pj ) = p(t i,pj , µ 1 )P (µ 1 ) p(t i,pj , µ 1 )P (µ 1 ) + p(t i,pj , µ 2 )P (µ 2 ) (11)

P (µ 2 |t i,pj ) = p(t i,pj , µ 2 )P (µ 2 ) p(t i,pj , µ 1 )P (µ 1 ) + p(t i,pj , µ 2 )P (µ 2 ) (12)
The Bayes's formula is repeated for all points of interest p j over the same operation i. At the end, this estimation returns the probabilities that a certain operation ⟨MS⟩ i is being executed when the exponent bit d i,k = 0. Table 3 shows the evolution of posterior probabilities P (µ 1 |t i,pj ) over all points of interest t i,pj , for 1 ≤ j ≤ u, and the respective percentage of correct exponent bits. Again, in this example we consider the first 20 exponent bits. point probabilities P (µ1|t1:20,p j ) correct P (µ1|t1:20,p 1 ) 0.7 0.4 0.6 0.8 0.7 0.8 0.6 0.4 0.8 0.8 0.9 0.8 0.4 0.7 0.4 0.3 0.6 0.2 0.4 0.6 75.23% P (µ1|t1:20,p 2 ) 0.5 1.0 0.8 0.9 0.7 0.9 0.4 0.2 1.0 1.0 0.9 0.8 0.2 0.9 0.0 0.0 0.8 0.2 0.1 0.6 82.89% P (µ1|t1:20,p 3 ) 0.5 1.0 0.8 0.9 0.7 1.0 0.5 0.1 1.0 1.0 0.9 0.8 0.1 0.9 0.0 0.1 0.9 0.3 0.1 0.6 89.02% P (µ1|t1:20,p 4 ) 0.1 1.0 0.9 1.0 0.7 0.9 0.9 0.0 1.0 1.0 1.0 0.8 0.0 1.0 0.0 0.0 1.0 0.1 0.0 0.1 93.45% P (µ1|t1:20,p 5 ) 0.4 1.0 1.0 1.0 0.9 1.0 0.8 0.0 0.9 1.0 1.0 0.6 0.0 1.0 0.0 0.0 1.0 0.0 0.0 0.3 96.34% P (µ1|t1:20,p 6 ) 0.4 1.0 1.0 1.0 0.9 1.0 0.8 0.0 0.9 1.0 1.0 0.6 0.0 1.0 0.0 0.0 1.0 0.0 0.0 0.3 97.56% P (µ1|t1:20,p 7 ) 0.4 1.0 0.9 1.0 1.0 1.0 0.7 0.0 1.0 1.0 1.0 1.0 0.0 1.0 0.0 0.0 1.0 0.0 0.0 0. For the three presented methods, we showed the cluster classification results for u = 17 points of interest. Fig. 4 demonstrates the evolution of the exponent recovery related to the number of points. In Fig. 4(a), it was considered the evolution from the least to the most leaking point. Note that using the Bayesian classifier are necessary 11 points to recovery the entire exponent. The same result can be observed in Table 3. On the other hand, in Fig. 4(b), if the evolution is from the most to the least leaking point, the Bayesian classifier achieves 100% of the exponent using only 4 points of interest per exponentiation segment.

Obtaining the Private Key from Randomized Exponents

For decryption and message signing, the retrieval of the randomized exponent d r = d + r.ϕ(N ) is the same as retrieving d. Therefore, a single-execution attack is sufficient to break the target device. However, for non-CRT implementations of RSA and in the case when the recovered randomized exponents present few error bits, the adversary can also improve the procedure using a step-by-step attack, as proposed in [START_REF] Bauer | Attacking Exponent Blinding in RSA without CRT[END_REF]. In this case, the recovering of several blinding factors r in the exponent randomization is used to derive the exponent d.

Approximately the ℓ/2 most significant bits of the exponent d are exposed when the public key e is small (3, 17 or 2 16 + 1). In this procedure, the term ϕ(N ) is approximated by N and the approximated exponent is given by, k ∈ Z:

d = ⌊ 1 + kN e ⌋
Consequently, the adversary can obtain the ℓ/2 most significant bits of all the possible randomized exponents by computing dri = d + r i .N , for all i and r i ∈ [0, 2 32 -1]. Considering λ as being the bit length of the blinding factor r, the λ most significant bits of d + r.ϕ(N ) are equivalent to the most significant bits of d + r.N . Then, the adversary can compute all possible values for r and by observing the recovered randomized exponent d r , he can deduce r. Finally, he constructs the attack on exponentiation traces containing possibly known blinding factors.

Countermeasures

The efficiency of single-execution attacks on exponentiations are related to the signal-to-noise ratio (SNR) of acquired traces. Theoretically, the Alg. 1 is SPAprotected because it is regular and all manipulated data are randomized due to algorithmic (exponent blinding) and arithmetic (leak resistant arithmetic) countermeasures. If different operands are read and written depending on the exponent bits, in a practical implementation of the Montgomery ladder the memory accesses cause addressing related leakages, as demonstrated through the unsupervised attack.

Hardware countermeasures as the insertion of time disarrangement, dummy cycles or frequency dividers reduce the SNR. Balancing the power consumption is an alternative to avoid the leakage of information due conditional tests or control decisions.

If the leakage is related to memory access, a possible solution is the randomization of the RAM addresses during the exponentiation. By doing so, the unsupervised attack was unable to entirely recover the randomized exponent. By selecting the same points of interest P = {p j }, we applied the fuzzy k-means clustering algorithm and recovered approximately 80% of the exponent using the Bayesian classifier technique. This paper presented an unsupervised attack on randomized exponentiations. The explored leakages are based on control executions and memory addressing. We proposed to combine the cluster classification for several points of interest over each exponent bit interpretation in order to derive the randomized exponent using a single EM trace. The results were presented through three different statistical techniques and specifically for the probability density function and Bayesian Classifier techniques, we showed the likelihood for the randomized exponent bits.

The presented unsupervised attack demonstrated the efficiency of clustering algorithms against single execution of exponentiations even in the presence of algorithmic and arithmetic countermeasures. The obtained results show the importance of employing hardware countermeasures in public-key architectures.

1 2 do 3 recompute µi 4 until no change in µi 5 return

 2345 begin initialize x, n, c, µ1, . . . , µc classify n samples xj according to nearest µi by computing EDi,j µ1, . . . , µc 6 end

Fig. 1 .

 1 Fig. 1. Exponentiation trace and the segmentation in multiplications and squarings.

Fig. 2 (

 2 a) shows the relation between the percentage of success recovery of the exponent and the analyzed set of compressed samples {t 1:ℓ,j }, for 1 ≤ j ≤ 592. If the adversary selects the most likely exponent (in the case the set {t 1:ℓ,465 }) he computes the averaged traces Tr 0 and Tr 1 . Fig. 2(b) shows the approximated difference of mean traces D = Tr 0 -Tr 1 . The difference of means D = Tr 0 -Tr 1 ,

Fig. 2 .

 2 Fig. 2. (a) Percentage of correct exponent bits. (b) Approximated difference of mean traces D = Tr0 -Tr1 (c) Difference of mean traces D = Tr0 -Tr1.

Fig. 3 .

 3 Fig. 3. Errors of cluster classification: (a) Correct classification. (b) Fuzzy k-means classification.

1

 1 3 99.59% P (µ1|t1:20,p 8 ) 0.0 1.0 1.0 1.0 1.0 1.0 0.7 0.0 1.0 1.0 1.0 1.0 0.0 1.0 0.0 0.0 1.0 0.0 0.0 0.0 99.59% P (µ1|t1:20,p 9 ) 0.0 1.0 1.0 1.0 1.0 1.0 0.8 0.0 1.0 1.0 1.0 1.0 0.0 1.0 0.0 0.0 1.0 0.0 0.0 0.0 99.59% P (µ1|t1:20,p 10 ) 0.0 1.0 1.0 1.0 1.0 1.0 0.9 0.0 1.0 1.0 1.0 1.0 0.0 1.0 0.0 0.0 1.0 0.0 0.0 0.0 99.18% P (µ1|t1:20,p 11 ) 0.0 1.0 1.0 1.0 1.0 1.0 1.0 0.0 1.0 1.0 1.0 1.0 0.0 1.0 0.0 0.0 1.0 0.0 0.0 0.0 100.00% P (µ1|t1:20,p 12 ) 0.0 1.0 1.0 1.0 1.0 1.0 1.0 0.0 1.0 1.0 1.0 1.0 0.0 1.0 0.0 0.0 1.0 0.0 0.0 0.0 100.00% P (µ1|t1:20,p 13 ) 0.0 1.0 1.0 1.0 1.0 1.0 1.0 0.0 1.0 1.0 1.0 1.0 0.0 1.0 0.0 0.0 1.0 0.0 0.0 0.0 100.00% P (µ1|t1:20,p 14 ) 0.0 1.0 1.0 1.0 1.0 1.0 1.0 0.0 1.0 1.0 1.0 1.0 0.0 1.0 0.0 0.0 1.0 0.0 0.0 0.0 100.00% P (µ1|t1:20,p 15 ) 0.0 1.0 1.0 1.0 1.0 1.0 1.0 0.0 1.0 1.0 1.0 1.0 0.0 1.0 0.0 0.0 1.0 0.0 0.0 0.0 100.00% P (µ1|t1:20,p 16 ) 0.0 1.0 1.0 1.0 1.0 1.0 1.0 0.0 1.0 1.0 1.0 1.0 0.0 1.0 0.0 0.0 1.0 0.0 0.0 0.0 100.00% P (µ1|t1:20,p 17 ) 0.0 1.0 1.0 1.0 1.0 1.0 1.0 0.0 1.0 1.0 1.0 1.0 0.0 1.0 0.0 0.0 1.0 0.0 0.0 0.0 100.00% d

Fig. 4 .

 4 Fig. 4. Relation between the exponent recovery and the number of points of interest: (a) from the least to the most leaking point and (b) from the most to the least leaking point (this Figure is represented in a different scale).

Table 2 .

 2 Cluster classification of the (first 20) exponent bits and the recovery of d 1:ℓ,k using the probability density function for normal distributions.

	p(t i,pj , µ 1 ) =	σ	1 √ 2π	e -	(t i,p j 2σ 2 -µ 1 ) 2	(9)
	p(t i,pj , µ 2 ) =	σ	1 √ 2π	e -	(t i,p j 2σ 2 -µ 2 ) 2

Table 3 .

 3 Cluster classification of the (first 20) exponent bits and the recovery of d i:ℓ,k using the Bayesian classifier.

	% of Correct Exponent Bits	70 75 80 85 90 95 100 1	2	3	4	5	6	7	8	9	10	11	12 Majority Decision 14 16 Normal PDF Bayesian Classifier (a) 13 15	17	% of Correct Exponent Bits	1 90 95 100 85	2	3	4	5	6	7 Majority Decision 8 Normal PDF Bayesian Classifier (b)
								Points of Interest						Points of Interest

Their setting simulates the use of 9 probes uniformly positioned over the chip under attack.