Anh-Hoang Le

Marie Lefevre

Amélie Cordier

Hala Skaf-Molli

Collecting interaction traces in distributed semantic wikis

Keywords: C.2.4 [Computer-Communication Networks]: Distributed Systems-Distributed applications; H.5.3 [Information Interfaces and Presentation]: Group and Organization Interfaces-Collaborative computing, theory and models Design, Theory Distributed semantic wikis, interaction traces, model of trace, trace collection process, trace-based reasoning, user assistance

come

INTRODUCTION

The success of Wikipedia is just one of many examples of the fact that collaborative editing of Web resources has become common practice. Wikis are one of the main tools enabling collaborative editing of Web resources. Semantic wikis [START_REF] Krötzsch | Semantic wikipedia[END_REF][START_REF] Buffa | Sweetwiki: A semantic wiki[END_REF] introduce semantic annotations within wiki pages thus enabling knowledge construction through social interaction. Semantic wikis contribute to the development of the so-called "social semantic spaces", spaces enabling humans and machines to collaborate for producing knowledge usable by humans and by machines. Distributed semantic wikis [START_REF] Rahhal | Multi-synchronous Collaborative Semantic Wikis[END_REF][START_REF] Skaf-Molli | Peer-to-peer semantic wikis[END_REF][START_REF] Skaf-Molli | DSMW: a distributed infrastructure for the cooperative edition of semantic wiki documents[END_REF] enable offline work and multi-synchronous editing [START_REF] Dourish | The parting of the ways: Divergence, data management and collaborative work[END_REF]. They bring an additional dimension to collaboration tasks over the Web. Indeed, distributed semantic wikis draw inspiration from popular distributed version control systems (DVCS) [START_REF] Allen | ClearCase MultiSite: Supporting Geographically-Distributed Software Development[END_REF] such as Git1 and Mercurial. 2 Collaboration mechanisms in distributed semantic wikis are similar to mechanisms we can observe in DVCS though they involve more complex tasks such as knowledge management tasks.

The goal of the Kolflow project 3 is to design a social semantic space enabling humans and machines to collaborate as easily as possible in order to build knowledge understandable by humans and usable by reasoning engines. In this project, Distributed Semantic MediaWiki4 (DSMW) is used to provide a community of user with a distributed social semantic space enabling them to build a shared knowledge base. This environment is designed to provide users with numerous features similar to those we can find in DVCS: local copies, main repository, push and pull operations between users, conflict management tools, versioning, etc.

The Kolflow environment is complex and has numerous features. It is quite difficult for users to master all the features at once. Therefore, the environment includes an assistance engine responsible for providing a contextual help to users (automating complex actions, creating communication channels in the network of users, help during conflict resolution, etc.). This assistance engine is based on the paradigm of Trace Based Reasoning [START_REF] Cordier | Grand Challenges for reasoning from experiences[END_REF]. The main input of this assistance engine are interaction traces. Interaction traces are records of the events occurring when a user interacts with a system. These traces enable the assistance engine to gather information about the context in which the user is performing a task, and therefore to provide him with contextualized help. Indeed, as shown in previous work, interaction traces are a rich source of knowledge for building personalized and contextualized assistance in distributed semantic wikis [START_REF] Champin | User Assistance for Collaborative Knowledge Construction[END_REF]. The challenge of efficiently collecting relevant interaction traces is therefore of major importance.

In this paper, we tackle the problem of collecting interaction traces in a distributed environment such as DSMW. We introduce a new approach to collecting interaction traces in distributed wikis and we propose an original trace model taking into account collective and collaborative dimensions of traces. We present Collectra, a tool we have developed to collect interaction traces according to this model. Through experiments, we show how the performances of Collectra comply with the requirements of the assistance engine developed in the Kolflow project. We also show that the designed model allows us to fully collect elements needed for building assistance. Though the scope of this paper is to present Collectra, more broadly, we are interested in studying how the use of traces supports a dynamic and collaborative process of knowledge construction. We discuss the applicability of our approach to other areas at the end of this paper. It must be noted that Collectra is available as an open source plugin for DSMW. 5The paper is organized as follows. Section 2 describes the context of the Kolflow project and the motivation for our approach. Section 3 introduces background knowledge about traces and reviews related work. Section 4 describes the Collectra approach and the distributed trace collection methodology. Section 5 presents the implementation of Collectra. Section 6 reports on the experimentation performed on Collectra. Experimentation show that Collectra is efficient enough to support the assistance process. Results and future work are discussed in section 7.

BACKGROUND AND MOTIVATIONS

In the Kolflow project, DSMW is used as a distributed tool for collaboratively editing knowledge bases. DSMW is a tool difficult to master. This is the reason why we have decided to equip the Kolflow environment with an assistance engine. To better understand the requirements of this assistance engine, in this section, we present situations where assistance may be required. We give examples of some difficult tasks users have to address. We pinpoint difficulties arising from these tasks and we show how an assistance engine could be helpful.

Semantic MediaWiki (SMW) is the most popular semantic wiki developed by the semantic web community. It allows mass collaboration for creating and maintaining ontologies. In SMW, users add semantic annotations to wiki page texts to represent relations and properties available on the page. Users may choose their own vocabulary to type links. For instance, a link between the wiki pages "France" and "Paris" may be annotated by a user as "capital".

Annotations express semantic relationships between wikis pages. Semantic annotations are usually written in a formal syntax so they are processed automatically by machines and they are exploited by semantic queries.

Although successful, semantic wikis still have limitations such as they do not support a multi-synchronous work mode [START_REF] Rahhal | Multi-synchronous Collaborative Semantic Wikis[END_REF][START_REF] Skaf-Molli | Peer-to-peer semantic wikis[END_REF][START_REF] Skaf-Molli | DSMW: a distributed infrastructure for the cooperative edition of semantic wiki documents[END_REF]. Consequently, users cannot work in isolation or disconnected. Distributed semantic wiki [START_REF] Rahhal | Multi-synchronous Collaborative Semantic Wikis[END_REF][START_REF] Skaf-Molli | Peer-to-peer semantic wikis[END_REF][START_REF] Skaf-Molli | DSMW: a distributed infrastructure for the cooperative edition of semantic wiki documents[END_REF] has been designed to overcome this limitation. DSMW [START_REF] Rahhal | Multi-synchronous Collaborative Semantic Wikis[END_REF] is a distributed extension of Semantic MediaWiki that supports multi-synchronous collaborations. Multi-synchronous systems are different from synchronous and asynchronous ones by managing multiple streams of activities instead of giving the illusion of one stream. In standard collaborative applications, when a modification is made by a user, the modification is immediately visible by others. However, in multi-synchronous systems, modifications made by users are not immediately visible by others. In that case, modifications become visible only when users validate them (e.g. commit changes).

DSMW allows users to build their own cooperation network. The construction of the collaborative community is declarative, in the sense that users declare explicitly with whom they would like to cooperate. Users may have a DSMW server installed locally if they like. They may create and edit their own semantic wiki pages as in a normal semantic wiki system. Later, they may decide to share these semantic wiki pages, and choose with whom to share.

The replication of data and the communication between servers is made through channels (feeds). The channel usage is restricted to few servers with simple security mechanisms that require no login or complex access control. The key point is that channels are read-only and can be hosted by users themselves. When a semantic wiki page is updated on a DSMW server, the server generates a corresponding operation.

According to DSMW replication model, an operation is processed in four steps: (1) It is executed immediately against the current page, (2) it is published on the corresponding channels, (3) it is pulled by the authorized servers, and (4) it is integrated to their local replica of the page. If needed, the integration process merges this modification with concurrent ones, either generated locally or received from remote servers.

In practical, to exchange modifications, DSMW users have to set up communication channels using push-pull operations. They start by creating pushFeeds to send modifications performed on a set of semantic wiki pages on one server and pullFeeds to fetch these modifications on a remote server. Once the communication channels are created, Push and Pull operations are available to actually push and pull each modification. Figure 1 gives an example of a collaboration network built upon a network of DSMW. U ser3 is working on site3 and decides to share content with U ser4 who works on site4. U ser3 creates a pushF eed for U ser4 and selects exactly the pages that must be shared (using a set of semantic queries). U ser4 creates a pullF eed corresponding to the pushF eed of U ser3. Now, U ser4 can fetch modifications published by U ser3. In the same way, other users create their pushFeeds and pullFeeds to exchange modifications.

Even for experimented users, setting up communication channels and manipulating the environment can be tedious. The administration interface of DSMW is displayed on figure 2. This administration interface is quite difficult to use, especially for novice users. As we can see on that interface, administration tools for creating feeds are not user-friendly, and are difficult to understand for novice users. This is the first reason why we need to provide assistance to DSMW users. We want to help them using the tool. For example, we can automate complex actions, such as the creation of communication channels.

The second motivation to develop user assistance is to support collaborative activities in a community of users. Indeed, problems can arise very quickly in distributed collaborative activities. To illustrate this point, let us consider the following scenario. A community of cooks is using DSMW to share cooking knowledge. The DSMW consists of recipes, food ontologies and general cooking knowledge. A master version of DSMW, named DSMW-Cook, is available on the web. A community member, Bob, owns a DSMW instance on which he pulled all the resources available in DSMW-Cook. He has added his Melon Pie recipe. He has also enriched the ontology with new ingredients (melon, etc.). Alice also has an instance of DSMW based on DSMW-Cook. In her instance, Alice has added her own recipe of Melon Pie, and modified an existing recipe of Chocolate Pie. She also has modified the ontology, but, unfortunately, her modifications differ slightly from Bob's. Bob has put Melon in the category Tropical Fruit, while Alice has put them in the more general category Fruit. When Bob and Alice try to share the content of their wikis, conflicts arise (different recipes with identical names, different ontologies, etc.). Therefore, they have to face a new task: resolving conflicts. Conflict resolution is a complex task involving several sub-steps such as analysis of the provenance of the conflict, search for additional knowledge, negotiation with other users, etc. It is usually difficult for end-users to deal with these problems. An assistance system could help them negotiate the knowledge contained in their wikis and present them the steps to resolve conflicts, to show the change history of the resources involved in the conflict, etc.

The assistance engine developed in Kolflow makes use of interaction traces to provide contextualized assistance. Therefore we need to collect interaction traces. The collection process has to match some specific requirements to make sure that the assistance will be efficient. These requirements are as follows. Firstly, collected traces have to match a model depending on the task at hand. For the Kolflow project, this model is described hereafter. Secondly, the collection process has to be fast enough not to slow down users' activities. Thirdly, collected traces have to be stored using a decent memory space, thus ensuring that tracing all the users' activities will not overload servers. Lastly, the retrieval time of collected traces must be fast enough to ensure that assistance can be provided real-time. Evaluations presented at the end of this paper assess the efficiency of the collecting process implemented in Collectra with regard to these requirements.

RELATED WORK

In a previous work, we made a review of various assistance strategies and we demonstrated why trace-based assistance is relevant for the Kolflow project [START_REF] Champin | User Assistance for Collaborative Knowledge Construction[END_REF]. The goal of the work described in this paper is to collect traces of interaction in distributed environments in order to provide the assistance engine with traces. In this section, we introduce briefly the trace theory, in order to better explain requirements that the trace collection process must fullfil. Then, we review related work on trace collection. We compare these methods against the criteria that the collection process must satisfy in order to make the assistance possible.

Trace Theory

In this paragraph, we briefly recall the trace theory presented in [START_REF] Settouti | A trace-based systems framework : Models, languages and semantics[END_REF]. We also provide some basic definitions about traces.

A trace is defined as a set of observed elements, called obsels. Obsels are timestamped within traces. A trace model defines the structure and the types of obsels that are contained in the trace, as well as the relationship between these obsels. A modeled trace (M-Trace) is a trace together with its trace model. A Trace-Base Management System (TBMS) is a knowledge based system enabling storage and management of traces. All the traces are stored in a Trace-Base Management System.

There are two types of M-Traces in a TBMS: primary trace and transformed trace. A primary trace is collected from external sources and stored as an M-Trace. M-Traces created after performing transformation operations on existing traces are called transformed traces. A TBMS has three main components:

• Collecting system: collects the observed data from different input sources (i.e. log files, video records, interface events, server messages, etc.) and stores them into traces as obsels.

• Transformation system: performs several transformations such as filtering, rewriting, merging obsels in one or more M-Traces. Transformations can be applied on any existing M-Trace, called source trace. The result of a transformation is a new trace, called transformed trace.

• Querying system: executes queries on traces. Queries enable us to compute various results from existing traces (number of obsels, frequency of an obsel type, frequency of a pattern, etc.). Queries also enable us to produce rich output resources such as documents, other traces, episodes (sub-parts of existing traces), etc.

Each resource in a TBMS is identified by a unique URI (Uniform Resource Identifier6 ). Through these URIs, users and other systems (e.g. trace-based application, collecting system) can manipulate and process TBMS resources.

A complete formalization and semantics of trace models, traces, queries, and transformations can be found in [START_REF] Settouti | A trace-based systems framework : Models, languages and semantics[END_REF]. In the following, we focus on the collection process.

Tracking interaction on web applications: a review

In the context of the Kolflow project, we need to collect traces of user interactions in a distributed environment (namely, DSMW). As a consequence, we must not only collect traces of multiple users, but also traces of exchanges between servers.

Based on the requirements of the assistance engine, we have defined a set of criteria that the collection process has to satisfy. These criteria are presented in columns on table 1.

The collection module must collect all the users actions (key and mouse actions). It must also track requests on servers and enable sharing of elements between servers. The module also must enable collection of traces of multi-users. Lastly, we seek for a module providing formalized traces so that they can be easily reused in a pre-existing system. Thereafter, we study various approaches to collecting traces from user actions in web environments with regards to these criteria. We summarize our observations in table 1 and we provide a synthesis illustrating the main problems related to our environment.

The collection of interactions between users and a website can be performed manually by human observers, semi-automatically by external equipments (i.e. video and audio captures) or automatically through tracing system implemented within the application or the tool. We briefly review these different approaches and we give several examples of tracing systems.

Manual collection is performed by human observers who observe users live or from a distance with the help of information tools (i.e. text editor, text notes, etc.). The result of the collection process usually takes the form of a set of notes in natural language.

Collection with external equipments requires the use of cameras or audio recording devices. This approach produces audiovisual traces.

These two approaches give detailed information about endusers, but are not well formalized. Consequently, the exploitation of collected information often requires complex processing systems like human operations (i.e. text processing, image processing). Therefore, these two approaches are not suitable for building an online assistant based on interactive traces.

Tracing systems implemented within existing applications allow obtaining formalized traces. These traces are then processable by reasoning engines. In the context of websites, tracing systems can be located on client side (i.e. browser plugin) or scripts integrated in the traced application on server side. Tracing on client side produces very finegrained observations but has important limitations (portability, speed, compatibility). Tracing on server side does not produce such detailed observations, but is usually more generic and simpler to implement. In the following, we give several examples of these automatic tracing systems.

Web browser: a Web browser is in itself a tracing system. Information about user activity can be recorded into the logs of Web browsers. This information generally focuses on the links that users have visited [START_REF] Oh | Advanced evidence collection and analysis of web browser activity[END_REF].

Web browser extension: may be implemented to obtain more detailed information than in the logs of Web browsers. These extensions are often known as key-loggers. They are capable of capturing key events and mouse events as well as retrieving information related to user actions. These extensions are used for several purposes such as facilitating the repetitive tasks (i.e. input assistance in search engine).

However, these extensions have to be installed before being used. This may be considered as a disadvantage because the sensitive data can be observed and recorded.

Local Web proxy: web activities of users can be recorded through a specialized tracing system called local Web proxy [START_REF] D'aquin | Personal Monitoring of Web Information Exchange: Towards Web Lifelogging[END_REF], running on the local computer of the user. This HTTP logging mechanism allows observing all requests going out of the user's computer from local Web agents (not limited to a particular browser). This approach has benefits in monitoring and analysing various aspects of personal web activities. However, its traces are not suitable for use by an assistance system. Because, while technically on the client side, this method collects the same kind of information as server side techniques.

Web server: Like Web browsers, Web servers (e.g. Apache) also have tracing systems, which are capable of generating log files containing information about user actions. These log files follow predefined formats(i.e. Common Log Format 7 ). They usually consist of the address of the client, date and time of request, executed request, status code returned to client, size of document returned to client. These traces can be used as inputs of assistants for navigation of Web [START_REF] Yang | Mining web logs for actionable knowledge[END_REF]. However, like browser log files and local Web proxy, the Web server log files do not contain enough detailed information about user actions (i.e. actions performed on client side).

Web server extension: collecting traces on both client side and server side raises problems. However, these problems can be solved with the aid of server extensions. For example, [START_REF] May | Tracking, analyzing, and visualizing learners' activities on discussion forums[END_REF] proposed an extension which allows tracing discussion forums. This extension consists of a collector in JavaScript on client side associated with a collector on server side. However, the proposed extension is limited to the observation of a single server and its users.

The analysis of table 1 shows that there are various types of tracing systems implemented on Web applications. These tracing systems allow obtaining traces which have various contents and representations. This analysis also shows that in order to have detailed information about actions of users on a website, we should develop extensions on server side, connected to tools on client side.

In the context of distributed servers (i.e. distributed semantic wikis), the collaboration between servers must be traced and shared. Existing tracing system seldom enable sharing of traces between tracing components. Moreover, they are

AN APPROACH FOR COLLECTING DIS-TRIBUTED TRACES

In this section, we describe our approach for designing a plug-in for collecting interaction traces in DSMW and for storing collected traces in a Trace-Base Management System. The main characteristic of our approach is to implement a trace collecting module on each SMW server in order to observe and record a maximum of users' actions with satisfactory performances. A Trace-Base Management System (TBMS) is associated to each SMW. Traces are shared between the different servers through a specific sharing protocol. To implement this protocol, we had to enrich the pre-existing features of the TBMS (see section 3.1). Thus, in order to design our collection module, we had to work at two levels: implementation of an independent collection module and extension of the existing programming interface of the TBMS.

Architecture

Figure 3 illustrates our architecture for collecting and sharing traces in DSMW. In this architecture, each Semantic MediaWiki (SMW) server is used by a group of users and is connected with a TBMS which stores the collected traces and shares them with other servers. The collecting module acts as an interface between DSMW and the TBMS. The collecting process implemented in DSMW sends messages to this module. The module parses the messages in order to build obsels that are stored in a trace managed by the TBMS.

To get shared traces from other servers, we use an Inter-TBMS communication ("Sharing traces" on the figure) that can be established through a special method allowing the collection of traces from external sources. These external sources can be other TBMS. This special method is an extension of standard methods of the TBMS.

The collected traces stored in the TBMS can be reused by any trace-based application. In our project, we will use these traces as knowledge sources for our trace-based assistant for DSMW. With this architecture, we can collect both individual and collaborative traces. Collaborative traces are described in details in the next section. In Kolflow, we use kTBS8 (Kernel for Trace-Based Systems) [START_REF] Champin | kTBS: Kernel for Trace-Based Systems[END_REF] to store traces. kTBS is a TBMS implementation in Python. It provides all the required features of a TBMS (primary trace, transformed trace, trace model, obsel types, attribute types and relation types of obsel types). Section 5 give details about the implementation of our collection plug-in and shows how we connect to the kTBS.

Model of Collaborative Trace

DSMW is a multi-synchronous collaborative editing system allowing a group of users to perform editing activities on semantic wiki pages and to synchronize their semantic wiki pages. Therefore, we are interested in collecting traces of collaborative activities. We call these traces collaborative traces.

In order to manipulate collaborative traces, we start by dividing user's activities in DSMW into two main activity types: individual activity and collaborative activity. An individual activity defines an activity that is performed by the user on his server and that does not require awareness of activities performed on other servers. A collaborative activity defines an activity performed by a user on the network and that requires awareness of other users and other servers.

This distinction allows us to define two types of traces: individual trace and collaborative trace. At the semantic level, an "individual trace" is a term used to indicate traces that reflect individual activities of a semantic wiki user. The term "collaborative trace" is used for traces reflecting collaborative activities. At the design level, an individual trace is identified by one user, and is called a private trace. A trace reflecting a part of the individual activity that is shared with others is called a shared trace. A fusion of shared traces is called a group-shared trace. The objective of this organization is to facilitate the process of building shared traces from individual traces. Thereafter, we describe the elements of our model of collaborative traces.

Obsel Classification

Considering the specific context of a collaborative work as it is in Kolflow, we propose a simple categorization of obsels. This categorization allows us to model users' activities in DSMW. In order to build this categorization, we have listed the most frequent actions in DSMW. At this stage, we have not focused on other interactions (such as log on/log off) but obsels corresponding to these actions can easily be built by combining basic obsels. A description of the collected obsels The categorization consists of three meaningful levels: low level, medium level and high level. At the low level, obsels reflect a single action (basic unit of interaction) performed by a user on the system. Usually, obsels at this level reflect events that occur on the user's interface, i.e. key events and mouse events. At the medium level, obsels characterize a set of single actions which are associated with a subtask. For example, a text modification ("ChangeText") can be made by mouse or/and keyboard and it is often a part of a search or a page editing. At the high level, the obsels characterize a set of subtasks which are necessary for the realization of a general task (i.e. search, edit, access a page).

These three levels constitute a hierarchical model of obsels (low: interaction, medium: subtask, high: task) in which any obsel can be represented by obsels in the lower levels ("a part of" semantic relation). Technically speaking, there could be many more levels, depending on the complexity of the obsels. In the context of Kolflow, these three levels appeared to be the most suitable to describe the objects we were interested in.

Trace Model

Figure 4 presents the organization of our trace model for modelling activities in DSMW (obsels and relationships between obsels). This trace model describes the structure and types of obsels which are contained in primary trace and which are collected directly from the target application. In this trace model, we use the obsels at the different levels in order to provide different inputs for the TBMS and to evaluate the suitability of the model. Results of the experiment (see section 6.2) show that using obsels at the intermediate level (change text) instead of obsels at the low level (key events) in some cases (page editing) can improve the performance of collecting trace while still ensuring action replay feature of obsels at high level (wrt. information loss).

There are two groups of obsels in the trace model: obsels only used for private traces (save page, change text, search, mouse event, key event) and obsels used for shared traces, called shared obsels (user presence, create PushFeed, create PullFeed, on push, on pull, remove PushFeed, remove PullFeed). Our trace model is extensible, meaning that it can be enriched to take into account unforeseen elements. For example, it can be extended for integrating new obsels for other entities (pages, patches, etc.) and other activities (create new account, view log history, etc.). Attribute types and relation types of obsels also can be modified or added, depending on the specific needs of trace-based applications. In the same way, it can be simplified in order to be better adapted to specific needs and to provide better performances.

Transformation Model

Transformations enable us to manipulate traces (filtering, merging, etc.). Here, we use transformations to build collaborative traces from individual traces. In the following, we distinguish three types of traces:

• Private trace: it is the trace of an individual user on a single wiki.

• Shared trace: for each private trace, a shared trace is built. Shared traces are shared with other wikis through the Inter-TBMS sharing protocol.

• Group shared trace: when several shared traces are merged in a single trace, this single trace is called a group shared trace. It reflects the collaborative activity of users in the group.

A first transformation is applied on a private trace, and the result of this transformation is a new trace that only contains shared obsels. A second transformation is applied on all shared traces, and the result of this transformation is a new trace which contains all shared obsels. Both transformations are performed automatically at run-time. In order to create a shared trace for user1, we use a filter method F1. This method is used to find shared obsels in the trace T1 and to copy them into a new trace (trace T3) sequentially. The new trace links to the model M2 which contains only shared obsels. In order to create a group shared trace for the three users, we use a fusion method F2. This method is used to copy all obsels in the shared traces of three users into a new trace (trace T5) sequentially. The new trace also links to the model M2 because it only contains shared obsels.

COLLECTRA: A TRACE COLLECTION MODULE FOR DSMW

We implemented the architecture described in the previous section in a collection module named Collectra. It has a server-side part (as a DSMW plug-in) and a client side part (embedded in the pages by the plug-in). The role of Collectra is to collect elements to characterize user interactions with DSMW. Collected data (obsels) are stored into a specific TBMS (kTBS), which stores and transforms collected traces.

In addition, Collectra has another important features that enables the creation of traces in its kTBS and the update of shared traces from other servers in DSMW. Collectra also handles creation and management of new resources that are not handled by default in the TBMS. For example, when a new user is created, a new private trace must be created in the TBMS.

Figure 6 shows the main features of Collectra. These features are detailed bellow. First, users' actions on client side (browsers) and their consequences on server side are captured and collected by Collectra [START_REF] Allen | ClearCase MultiSite: Supporting Geographically-Distributed Software Development[END_REF]. The user's actions (i.e. key event, mouse event, change text) are recorded live on client side. These actions are then serialized in XML and sent to the server at regular time intervals by using AJAX 9 9 http://en.wikipedia.org/wiki/Ajax_(programming)

technique. Next, they are synchronized with elements collected on server side. For example, a mouse event "click on the search button" causes a search event on the server. In Collectra, the collected objects (obsels) are serialized in a format accepted by the TBMS. When new obsels are collected, Collectra retrieves the trace of the current user from TBMS. If no trace is found for the user, a new trace is created automatically for him [START_REF] Avouris | Logging of fingertip actions is not enough for analysis of learning activities[END_REF]. Then, the formatted obsels are added into their traces (3).

In addition, Collectra has features allowing it to synchronize with the other servers on the network. When traces are modified on the network, servers update their statuses to reflect these changes. Collectra synchronizes itself at regular time intervals in order to take into account these changes (4).

Lastly, we implemented a simple visualization tool to observe the effects of collaborative traces visualization on the awareness of DSMW users (5).

EXPERIMENTS

To ensure that the collection module meets the requirements of the assistance engine, we conducted several experiments. These experiments focused on performances and stability of the collection module. The objectives were twofold. First, experiments demonstrate that it is possible to collect, in real-time, traces matching the model we have defined. Next, experiments show that it is possible to perform queries on collected traces with a good response time. These experiments and their evaluations are described in this section.

Experimental protocol

In order to establish a data set to evaluate our approach, we set up an experiment involving two teachers. Teachers were to collaborate through DSMW in order to create a web programming course. Different stages of collaboration were predefined. The experiment consists of two main parts.

Before the experiment, a web server was set up, and DSMW, Collectra and kTBS were installed on this server. The server ran on a personal computer (Processor: Intel Core 2 Duo CPU E6550 2.33GHz x 2, RAM: 3.8GB, OS: Ubuntu 11.10 64 bits). Three instances of wikis were installed on the server: wiki1 for user1, wiki2 for user2 and wiki3 to integrate the productions of the previous two wikis.

The first part of the experiment was designed to evaluate the trace collection process. This part consisted of two stages.

During the first stage, user1 and user2 worked on their own wikis to create their own parts of course (single-user mode). This stage lasted 45 minutes and involved all types of operations (creation of pages, push, pull). During the second stage, both users published their content on wiki3. Both users pulled their wiki pages created from wiki1 and wiki2 (content of pages from wiki1 and wiki2 is different) and continued working simultaneously during 25 minutes (two-users mode). In particular, they had to collaborate in order to create the introduction page. During these 70 minutes, Collectra collected all interactions, defined in our traces model, between user1, user2 and server, on the three wikis.

The second part of the experiment was designed to evaluate the trace exploitation process. For that purpose, we

Results

With regard to collection of traces, Table 3 shows the number of obsels associated with each wiki. The 45 minutes of activity produce about 1200 obsels (approx. 3 seconds/obsel), among which a majority are obsels used for editing (KeyEvent and ChangeText, approx. 91%). The number of obsels is relatively low, but the main problem lies in the number of attributes obsels, as we discussed below.

Table 4 shows that the average number of attributes of obsels is about 12 and the average size of an obsel is about 6 KB (uncompressed). And after compression of trace files, the average size of an obsel is reduced to 2 KB. We analysed this problem and we found that the cost of building the structure of obsels (i.e. properties with the long name or the repetition of RDF tags) is bigger than the memory space used for actual information. The average creation time is approx. 0.04 s (capable of handling up to 25 obsels/s) and the average retrieving time is approx. 0.0067 s, which is sufficient for real-time retrieval of parts of traces.

On graphs 7(a) and 7(b), lines represent the time taken by the creation of each one of the three types of obsels with the highest occurrence: KeyEvent(K), ChangeText(C) and MouseEvent(M). Obsels are ordered by identifier. We observe that the time of creation of obsels depends on the number of attributes of that obsel (C=11, K=13 and M=17; the number of attributes is defined in the trace model). and the number of simultaneous users (the creation time in twousers mode is slightly higher than in single-user mode). In addition, graphs show that there is no strong correlation between time of creation and number of obsels in the trace. In other words, the creation time of obsels does not increase with the number of previously created obsels in the same trace.

In the second part of the experiment, we focused on the exploitation of traces. Retrieving a trace consists of two basic phases: (1) Search and compute obsels of the trace, and (2) Serialize the trace in a given format (i.e. RDF, JSON, etc.).

In the last column of table 4, we observe that the average retrieving time is approx. 0.0067 s. This retrieval time is satisfactory. To give an idea, it allows to fetch approximately 150 obsels per second.

Graph 8(a) shows the comparison of serialization times of traces in single-user mode and two-users mode. We can see that the serialization times of traces in single-user mode and two-users mode are similar. The serialization time (t) is proportional to the number of obsels (n) in trace: t ≈ n × α, α = 0.0066 s.

Graph 8(b) shows the comparison of computation time of transformed traces (fusion and filter) in single-user and twousers mode. The computation time for filtering traces is longer than the one for merging traces. Indeed, for filtering traces, searching successive obsels in source traces is time consuming, whereas there is no need to do it for fusion. The search and computing is incremental. This means that the search and computation time(t ) only depends on the number of unprocessed obsels(n ): t ≈ n × β, β = 0.026 s. 10The previously processed (transformed) obsels are omitted in this phase thanks to an incremental counter which ensures that an obsel is processed only once. Thus, at run-time, the retrieving time almost reaches the serialization time because the number of unprocessed obsels is often small.

Discussion on the results

Thereafter, we analyse the results with regard to the four requirements described in section 2.

The first requirement is to collect traces matching a model depending on the task. In Collectra, we have defined a trace model suitable for the tasks conducted in Kolflow. This first requirement is then met.

The second requirement is about time performances. On graph 7(b), we observe a peak during the creation of the six hundredth obsel. This sharp increase in the time of creation is explained by simultaneous actions of two users in the same page of the wiki3. Indeed, wiki are not designed to support simultaneous edition of pages. When user1 and user2 edit a page at the same time, Collectra sends the same obsel twice to the kTBS. Therefore, creation time is necessarily higher. Apart from this peak, we observe that the creation time of obsels remains stable over time and do not slow down users' activities.

The third requirement is about memory space used to store collected traces. Results presented in section 6.2 show that our approach works satisfactorily on a local scale. Furthermore, due to the distributed nature of the approach, response time is linear and therefore scales well. However, simple estimations show that memory space quickly becomes an issue. For example, collecting traces of a single user during 4500 hours produces 500GB of data. The same amount of data is collected when observing 2 users during 3000 hours. For 12 users working during 21 days, we also collect 500GB of data. Such performances are satisfactory in the context of the Kolflow project, but for a bigger application (such as Wikipedia), they could rapidly become an issue. These results also show that the required memory space depends on the number of attributes of each obsel. To obtain satisfactory performance on a large scale, it is therefore important to carefully choose the attributes to be stored in each obsel. In this project, we have decided to provide a complete model. However, if one is interested in improving performances, the best thing to do is to simplify the collect model in order to reduce the number of attributes per obsel.

The last requirement is to ensure that retrieval time of collected traces is fast enough to enable online assistance. Results on the second part of the experiment show that retrieval time is satisfactory. However, further experiments in real conditions with the assistance engine are required to better evaluate this point.

CONCLUSION

In this paper, we presented an architecture and a tool, Collectra, to collect interaction traces of multi-user in distributed environments. Collected interaction traces are intended to be used by the assistance engine developed in the Kolflow project. To guaranty the success of the assistance, we must ensure that both the collection process and the retrieval of collected traces are performed in satisfactory response times.

We conducted experiments to evaluate Collectra with respect to these issues. Experiments show that our architecture ensures satisfactory response times in real-world situations. However, memory space remains an issue. Memory usage is not a problem for small scale problems, but it can become an issue on the long run. This result raises new issues regarding memory management, storage methods and forgetting policy in trace-base management systems. We consider this aspect as a major research question for this work.

Now that we can rely on efficient collection module, we can focus on the next step for providing assistance to Kolflow users. This step is to continue developing the assistance engine, and its interface. This interface will be built on top of requests that we already have designed and experimented.

Based on user feedback, we will assess the quality and relevance of the different modes of assistance provided by the assistance engine.

More broadly, we want to study the relevance of our framework in other contexts than the one of the Kolflow project. At the moment, Collectra has been implemented as a plug-in for DSMW and has been experimented in this context. The trace model has been designed in order to collect interaction traces of DSMW users. In order to apply our model to other application domains, two important steps have to be accomplished. Firstly, a new trace model has to be defined, with respect to the chosen application. Secondly, slight modifications have to be made to the Collectra API in order to connect it to the observed application. In future work, we will experiment our approach with other distributed and collaborative activities, in order to identify strengths and weaknesses of our approach.

Figure 1 :

 1 Figure 1: Collaboration network in DSMW.

Figure 2 :

 2 Figure 2: Screenshot of DSMW administration interface.

Figure 3 :

 3 Figure 3: Collecting and sharing traces in DSMW.

Figure 4 :

 4 Figure 4: Trace model of primary traces in DSMW.

Figure 5 :

 5 Figure 5: Transformation model for collaborative traces.

Figure 6 :

 6 Figure 6: Features implemented in Collectra.

Figure 5

 5 Figure 5 shows an example of our transformation model applied to a situation involving three users (user1, user2 and user3). User1 works on wiki1. User2 and user3 work on different servers, but share their traces with user1. The figure represents the TBMS of wiki1. We can see that the TBMS stores the private trace of user1 (T1) and two shared traces collected from user2 (T2) and user3 (T4). The model of the trace T1 is M1. It contains a description of the obsel types of the trace T1. It is the same for all the stored traces.

  (a) Time to create obsels in single-user mode (b) Time to create obsels in two-users mode

Figure 7 :

 7 Figure 7: Time to create obsels.

Figure 8 :

 8 Figure 8: Experimental results.

Table 1 :

 1 Type of collection process and observable information. (K) Key action, (M) Mouse action, (Rq) Server request, (Sh) Sharing between servers, (Mu) Multi-users, (F) Formalized trace.

	Trace sources	K	M	Rq	Sh	Mu F	Example
	Manual collection External equipment Web browser Web browser extension Local Web proxy	√ √ ∅ √ ∅	√ √ ∅ √ ∅	√ √ √ √ √ √ √ ∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅ √ ∅ ∅ √ ∅ ∅ ∅ √ √	Heraud et al., 2005 [10] Avouris et al., 2005 [2] Oh et al., 2011 [13] Bell et al., 2012 [3] May et al., 2007 [12]

  Common_Log_Format not suited to multi-user traces collection. Thus, we propose a new tracing system which enables trace collection in a distributed Web environment. This model, presented in section 4.2.2, is based on a trace theory that we have introduced before.

7

http://en.wikipedia.org/wiki/

Table 2 :

 2 Description of collected obsels.

	Type of Obsel	Description
	KeyEvent	Key and character code that a user pressed
	MouseEvent	Element on the interface that a user clicked (but-
		ton, link, etc.)
	ChangeText	Text and changes that a user made
	Search	Search information collected when a user per-
		formed a search
	SavePage	Inputs and revision numbers of the saved wiki
		page and its type of action ("new", "edit", "undo"
		or "rollback")
	UserPresence	Root obsel created when the system creates a
		new session for a user. Contains information
		about the user and his session
	CreatePushFeed	Name and URL of PushFeed and its semantic
		query designed when a user created a PushFeed
	Push	Push operations including the published changes
	RemovePushFeed	Removed PushFeed
	CreatePullFeed	URLs of the PullFeed and the PushFeed associ-
		ated with it
	Pull	Pull operation including the downloaded changes
		and pages related to those changes
	RemovePullFeed	Removed PullFeed

is given in table 2. Note that each obsel has a timestamp set by the collection module.

Table 3 :

 3 Number of obsels created on each wiki.

	Obsel type	Number of obsels
			Wiki1 Wiki2 Wiki3
	Key event	799	927	680
	Change text	409	518	404
	Mouse event	49	98	130
	Created page	4	3	10
	Modified page	1	1	1
	Search	7	3	1
	Pushfeed	5	3	3
	Pullfeed	3	2	8
	Push		5	5	4
	Pull		0	1	7
	Others	1	1	1
	Total		1283	1562	1249
		Size Number of Creation Retrieving
		(kB) attributes time(s)	time(s)
	Min	6.2	9	0.02741	0.00394
	Max	6.7	17	0.20917	0.01586
	Average 6.3	12.6	0.04100	0.00672

Table 4 :

 4 Characteristics of obsel.performed various transformations on collected traces (i.e. filter by date, by type, by property and fusion). Then, we displayed transformed traces on the visualization interface of Collectra. Transformations and visualization interfaces are integrated in each wiki in DSMW, through the Collectra plug-in. This enables us to evaluate response time from the server (computation of the result and transfer).

http://git-scm.com

http://mercurial.selenic.com

http://kolflow.univ-nantes.fr

http://www.mediawiki.org/wiki/Extension:DSMW

http://sourceforge.net/projects/silexcollectra/

http://en.wikipedia.org/wiki/Uniform_resource_ identifier

http://liris.cnrs.fr/sbt-dev/ktbs/

Alpha (α) is the linear regression coefficient of serialization time on the number of obsels in a trace. Beta (β) is the linear regression coefficient of search and computation time on the number of unprocessed obsels in source traces. These two values depend on the process capability of the server.

Acknowledgment

We are grateful to Pierre-Antoine Champin, Emmanuel Desmontils for their comments on this work. This work is supported by the French National Research agency (ANR) through the Kolflow project (code: ANR-10-CONTINT-025), part of the CONTINT research program. More information about Kolflow is available on the project website: http://kolflow.univ-nantes.fr/


Michel Agoyan

Sylvain Bouquet

Jean-Max Dutertre

Jacques Fournier

Jean-Baptiste Rigaud

Bruno Robisson

Assia Tria

Design & characterisation of an AES chip embedding countermeasures

Keywords: Advanced Encryption Standard, Side channel analysis, Circuit duplication, Dual representation, Fault detection and propagation, Fault attacks. Fault injected

In critical communication infrastructures, hardware accelerators are often used to speed up cryptographic calculations. Their resistance to physical attacks determines how secure the overall infrastructure is. In this paper, we describe the implementation and characterisation of an AES accelerator embedding security features against physical attacks. This AES chip is implemented in HCMOS9gp 130nm STM technology. The countermeasure is based on duplication and works on complemented values in parallel. The chip was tested against side channel attacks showing the efficiency of the proposed countermeasure against such attacks. Fault injection tests based on the use of local laser shoots showed that the fault detection mechanism did indeed react as expected. However, using clock set-up time violations, 80% of the secret key were retrieved in less than 40 hours, thus illustrating the limits of the duplication counter-measure against a global fault attack which was published after the chip was designed.

Introduction

Security in communication systems has become mandatory in many ubiquitous communication infrastructures. Whether it is for the confidentiality, authenticity and integrity of electronic financial transactions or e-government or for the privacy of the end-users, security tools are being massively deployed in equipments like mobile phones or laptops. Moreover, "civil" communication infrastructures are growingly being eyed for the deployment of critical infrastructures: for example in the EU SECRICOM initiative [SECRICOM (2008)], a secure communication infrastructure is developed over existing "civil" technologies for cross-border crisis management. In such secure infrastructures, the use of a hardware module to manage secret keys, accelerate cryptographic algorithms and manage access rights has been defined. As the security of the system depends on the security of its weakest link, the security of such hardware modules against physical attacks has become a critical feature for the successful deployment of the secure communication infrastructure.

In this article, we focus on the design of embedded cryptographic accelerators, specially on the countermeasures that can be used to increase their resistance against physical attacks and ways and methods to evaluate the efficiency of such countermeasures. Our case study is based on the implementation and security characterisation of a hardware accelerator for the Advanced Encryption Standard. We propose a new design approach to thwart both side-channel and fault attacks, two of the most dangerous physical attacks against cryptographic implementations. We then describe the physical tests done to evaluate the resistance of the fabricated chip to illustrate the efficiency (against attacks that were known at design time) and limits (against attacks which were not yet published at design time) of the proposed countermeasures. We then discuss about the analysis made out of the test results.

2 Cryptography, physical attacks and counter-measures

Cryptographic algorithms

Cryptography, as used in protocols like TLS [OpenSSL (2000)], can be described as the art of transforming input data, called a message, into an output, called a cipher, sometimes using a secret key: knowing the cipher, no information can be inferred about the message. There are several types of cryptographic functions. Hash functions transform data of arbitrary length into a hash of fixed length [ NIST (2002)]. Secret Key algorithms use a secret key to encrypt a message and the same key to decrypt the corresponding cipher : the message and cipher are of same length which is defined arbitrarily in Stream ciphers (where each bit is encrypted individually) or as blocks of fixed sizes as in Block ciphers (examples of Block ciphers are the DES (Data Encryption Standard) [ NIST (1993)] or the AES (Advanced Encryption Standard) [NIST (2001)]). Asymmetric cryptography or Public Key algorithms use two keys: a public one used for encryption and a private one used for decryption. Examples of PK algorithms are the RSA [START_REF] Rivest | A method for obtaining digital signatures and public-key cryptosystems[END_REF]] and Elliptic Curve Cryptography (ECC) [START_REF] Blake | Elliptic Curves in Cryptography[END_REF]].

Attacks & counter-measures

Even though cryptographic algorithms like AES or RSA are mathematically robust, their implementation can be subjected to physical attacks when the attacker has physical access to the security device. We first have invasive attacks where the attacker tries to directly observe the signals from within the chip (through techniques like micro-probing) or read the bits from within the memories themselves or to use tools like a FIB (Focussed Ion Beam) to short-circuit some of the security sensors of the circuit or re-connect some other parts which had intentionally been disconnected for security purposes [START_REF] Walker | Using FIB to hack security chips, European Focused Ion Beam Users Group (EFUG 2004) presentation[END_REF]; [START_REF] Anderson | Low Cost Attacks on Tamper-Resistant Devices[END_REF]]. Such attacks, due to their prohibitive cost and destructive nature are of lesser interest to us. We mainly focussed on non-invasive or "semi-invasive" attacks like side channel attacks and fault attacks.

For attacks based on side channel information leakage, information about the internal processes of the chip and the data manipulated can be derived by observing external physical characteristics of the chip (like the power consumed or the electromagnetic waves emitted or the time taken by a given process). In Timing Attacks [START_REF] Kocher | Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS and other systems[END_REF]; [START_REF] Dhem | A Practical Implementation of the Timing Attack[END_REF]], by observing the time taken by a "naïve" implementation of a cryptographic algorithm (say RSA), one can determine the bit values of the secret key manipulated. In another class of attack called Simple Power Analysis, by observing the power profile of the chip during such a calculation, one can derive information about the secret key bits used. Power Analysis attacks were first published in [START_REF] Kocher | Differential Power Analysis[END_REF]] and since then side channel attacks have been a major concern to the hardware security world. Differential Power Analysis mainly targets secret key algorithms based on the fact that for each bit of the secret key, the power consumed by a 0 is different from the power consumed by a 1 (corresponding to the "Hamming Weight", i.e. the number of ones, leakage model). Later, researchers showed that electromagnetic radiation from a chip could also be used as a source of side-channel [START_REF] Gandolfi | Electromagnetic Analyis: Concrete Results[END_REF]; [START_REF] Quisquater | Electromagnetic Analysis (EMA): Measures and coutermeasures for smart cards, Smart Card Programming and Security (e-smart[END_REF]]. Different leakage models have further been proposed when doing differential side channel analysis. For example, "Hamming Distance" (i.e. the number of positions for which the bits have "flipped") models have been put forward in [START_REF] Mayer-Sommer | Smartly analyzing the simplicity and the power of simple power analysis on smartcards[END_REF]]. Correlation Power Analysis or Mutual Information Analysis have been proposed to quantitatively test the dependency between the side channel measured and the data being manipulated by a security device [START_REF] Brier | Correlation Power Analysis with a leakage model[END_REF]; [START_REF] Gierlichs | Mutual Information Analysis -A Generic Side-Channel Distinguisher[END_REF]].

Another class of attacks are fault attacks where an attacker will try to modify the data handled by a chip or corrupt the processor's execution flow at a specific time of a cryptographic calculation. From the results of a correct execution and those of a corrupted execution, the attacker then tries to retrieve part or all of the secret key by using techniques like Differential Fault Analysis (DFA) [START_REF] Biham | Differential Fault Analysis of Secret Key Cryptosystems[END_REF]]. Such attacks have particularly been tested on block ciphers like AES as described in [START_REF] Piret | A Differential Fault Attack Technique against SPN Structures, with Application to the AES and KHAZAD[END_REF]; [START_REF] Giraud | DFA on aes[END_REF]]. Another class of attacks called safe error attacks consists in the extraction of secret keys from the behaviour of the chip in the presence of a fault [START_REF] Yen | Checking before output may not be enough against faultbased cryptanalysis[END_REF]; [START_REF] Robisson | Differential behavioral analysis[END_REF]]. To inject faults, an attacker can for example generate glitches on the power supply, cause clock set-up time violations on the input clock [Removed for Review ] or irradiate the chip with a laser or light source [START_REF] Skorobogatov | Optical Fault Induction Attacks[END_REF]]. Fault attacks can also be used to corrupt the correct flow of a program in order to make it take a given branch of the program [START_REF] Choukri | Round Reduction Using Faults, in 2 nd Workshop on Fault Diagnosis and Tolerance in Cryptography (FDTC 05)[END_REF]] or to cause memory dumps.

Several countermeasures have been proposed in the literature. Those which target side channel attacks consist in either reducing the informative signal (i.e. the physical characteristics which are correlated with the sensitive data), or adding noise to blur the measurements. The informative signal has been reduced, for example, by using power filters or electromagnetic shields or by using "balanced" logic. Balancing may consist in rendering the Hamming Weight (HW) of sensitive internal data constant. The 1-out-of-N encoding of these data is a widespread technique to achieve this. The encoding obtained with N=2 is called "dual-rail" encoding. This countermeasure approximately doubles the size of chip. Balancing may also consist in rendering the Hamming Distance (HD) of sensitive internal computations constant, for example, by using both the 1-out-of-N encoding and a dedicated communication protocol between the different parts of the circuit. The more widespread ones insert spacers (i.e. a constant value which does not carry information) between values. When the spacer is equal to zero, the protocol is called "return-to-zero" (RTZ). Roughly, this countermeasure halves the performances of the chip by a factor 2. Many implementations attempting to balance HW and HD have been proposed at different levels of abstraction ( [START_REF] Tiri | Securing Encryption Algorithms against DPA at the Logic Level: Next Generation Smart Card Technology[END_REF]; [START_REF] Soares | Evaluating the robustness of secure triple track logic through prototyping[END_REF]] at gate level, [START_REF] Ambrose | Multiprocessor information concealment architecture to prevent power analysis-based side channel attacks[END_REF]] at the architecture level and even at software level [START_REF] Chen | Implementing virtual secure circuit using a custom-instruction approach[END_REF]). The last step consists in physically balancing the propagation of the encoded values between the different parts of the circuit, for example, by using ad hoc Place and Route (P&R) techniques [START_REF] Guilley | The "backend duplication" method[END_REF]]. A fair comparison between some balancing techniques is proposed in [START_REF] Guilley | Evaluation of power constant dual-rail logics countermeasures against DPA with design time security metrics[END_REF]]. Moreover noise can be added, for example, by randomizing the order of the instructions, by adding dummy operations or by masking the internal computations that can be predicted by the attacker [START_REF] Akkar | An Implementation of DES and AES, Secure against Some Attacks[END_REF]; [START_REF] Tokunaga | Secure aes engine with a local switched-capacitor current equalizer[END_REF]].

The countermeasures against fault attacks consist either in detecting errors during the computation and then taking actions to protect data or in making the circuit less sensitive to fault injections. The detection of error is mainly based on information redundancy either in space (doing the same computation several times in parallel) or in time (repeating the same computation several times) [START_REF] Bertoni | A parity code based fault detection for an implementation of the advanced encryption standard[END_REF]; [START_REF] Karri | Parity-Based Concurrent Error Detection of Substitution-Permutation Network Block Ciphers[END_REF]; [START_REF] Karpovsky | Robust protection against fault injection attacks on smart cards implementing the Advanced Encryption Standard[END_REF]]. Several sensors have also been proposed to detect abnormal modifications of the chip's environment (voltage, temperature, clock frequency, light, etc.). Once a fault has been detected, one reaction may consist in temporarily stopping the communication with the outside (the chip "mutes") and/or resetting parts of the running software. The ultimate reaction consists in permanently destroying all the (sensitive) data stored in the chip. In order to render the circuit less sensitive to faults, redundancy is mainly used (one thus speaks of "error correction"). But the required level of redundancy is high: the computation has to be performed at least three times.

However, few attempts have been made to propose a solution that thwarts both classes of attacks. Asynchronous design techniques [START_REF] Moore | Balanced selfchecking asynchronous logic for smart card applications[END_REF]; [START_REF] Kulikowski | Automated design of cryptographic devices resistant to multiple side-channel attacks[END_REF]; [START_REF] Bastos | Comparing transient-fault effects on synchronous and on asynchronous circuits[END_REF]] have been touted as offering pro-tection to side-channel and fault attacks because "by construction" they embed RTZ and dual-rail encoding and because the handshake protocol of communication between the different parts of the circuit decrease the susceptibility to fault attacks. The limits of such countermeasures have been reported in [START_REF] Fournier | Security Evaluation of Asynchronous Circuits[END_REF]].

In our paper, we handle both side channel and fault attacks by proposing an architecture based on duplicated-complemented (also called 'dual') data paths applied to the AES algorithm. The dual data paths balance the Hamming Weight and are also used to detect faults.

3 Design of the AES accelerator -SUB-BYTES is a non-linear transformation working independently on individual bytes of the matrix consisting of a Galois Field inverse calculation followed by an affine transformation. -SHIFT ROWS is a simple rotation operation on each row of the data matrix.

3.1 The Advanced Encryption Standard SUB-BYTES SHIFT_ROWS MIX_COLUMNS SUB-BYTES SHIFT_ROWS MIX_COLUMNS SUB-BYTES SHIFT_ROWS Input MESSAGE RND_EXE 1 RND_EXE 9 Output CIPHER M0 M1 M2 M3 C0 C1 C2 C3 Input KEY K0 K1 K2 K3 K0 T3 K1 K'0 K2 K'1 K3 K'2 K'0 K'1 K'2 K'3 TRANSFORM K3 -->T3 KEY_EXPANDER #1 KEY_EXPANDER #10
-MIX COLUMNS is a linear matrix multiplication working on each column where multiplications are done in GF(2 8 ). -ADD-RND-KEY, illustrated in Figure 1 by the XOR symbol, consists of a bytewise XOR between the data matrix and the corresponding sub-key matrix.

Independently from these, the KEY EXPANDER module iteratively calculates sub-keys for the ADD-RND-KEY function. The KEY EXPANDER for a key size of 128 bits is shown in the right part of Figure 1. The TRANSFORM operation done on the forth column of the key (K3) is detailed in [NIST ( 2001)]. Our design (which we shall call the Tamper Resistant AES, TR-AES) aims to protect against both DFA and side channel attacks. In our case, performance prevails over surface as the module was originally designed to encrypt data transfers between two devices. The countermeasure against DFA consists first in detecting errors and then reacting in case of detection. In order to obtain a reasonable fault-coverage for an acceptable surface penalty, we chose, as suggested in [START_REF] Malkin | A comparative cost/security analysis of fault attack countermeasures[END_REF]], to detect errors by using spatial duplication: the AES-128 is executed twice in parallel. At each step (or round) of the algorithm, the consistency between the results of the two instances of the algorithm is checked. Several reactions in case of attacks have been analysed. For example, we could have returned a constant value instead of the faulty cipher or to return a random value. We have excluded the first solution because we considered that it could open a breach to safe-error attacks and the second because we have no available true random number generator. In order to mimic the effect of such random generator, the chosen strategy of reaction consists in blurring the erroneous cipher-text with the scrambled value of the detected error, as explained in [START_REF] Joye | Strengthening Hardware AES Implementations against Fault Attack[END_REF]]. In order to counter side channel attacks, the two different instances of the algorithm are designed such that when a bit of each intermediate value is computed in one instance, the other instance computes the complemented values. This trick creates dual data channels when considering the two instances. One is called the 'original path', the other is called the 'complemented or dual path'. The logic gates used in the two instances are also "complemented", i.e. the XOR gates from the original path are replaced by XNOR gates. Note also that, because we did not want to reduce the performance of the circuit, we did not insert spacers for balancing the HD. No particular constraints have also been applied during the P&R step.

Architecture of the TR-AES

The resulting architecture is shown in Figure 2. To obtain the best performances, the RND EXE function, the KEY EXPANDER are computed in parallel with 128-bit data paths. Each round is executed in one clock cycle. As the consistency of data is tested on the outputs of the SUB-BYTES module (the upper part of Figure 4), the latency of detection of error is also of one clock cycle. Figure 3 details the error detection and propagation. Further spreading of the errors is achieved by cross-changing wires between the original and the dual data paths at the level of the SHIFT ROWS module. Figure 4 illustrates what happens when an error is generated at the beginning of the last round on one of the data paths.

The final AES chip

The TR-AES was designed with the standard cells of the HCMOS9gp 130nm STM technology. The TR-AES typically works at 1.20V and its maximum frequency is 50MHz at 27 • C. The resulting die is 1336µm × 1411.8µm in size, due to the limitation by the 52 pads of the ring (Figure 5). The AMBA APB interface consists of 32 bidirectionnal I/Os and 4 bits of address. The AES functional block itself uses 27000 gates corresponding to an area of 0.165mm 2 (including the communication interface) which represents an overhead of 67% when compared to a non-secure AES in the same technology (16500 gates). Different analyses have been performed to detect potential security flaws at design-time. The method used to detect weaknesses against side-channel attacks and the results obtained for the TR-AES are described in [START_REF] Laabidi | Méthodologie de conception de composants intégrés protégés contre les attaques par corrélation[END_REF]]. We have verified that, thanks to the search for correlations between bits in the RTL description of the TR-AES, each bit in the original path is balanced by its dual counterpart.

m ij m ij ⊕ e M i M i a ij M i ⊕ M i a ij = 0 ou a ij = e Error State E e ij r i = j=0..3 a ij c j = i=0..3 a ij e ij = r i + c j
Inv bits

E inv 0 e e inv

Fig. 3. Error Matrix Calculation

But thanks to this method, we have also detected some very slight differences in the structure of the two instances of the algorithm when they are described at gate level. In order to estimate the associated threat, side channel attacks have been performed on the simulations of the power consumption (obtained with simple toggle counts). These simulations showed that the tiny difference which may appear on the power consumption of the two instances of the algorithm are mainly due to the difference of delay of propagation of a bit and its dual counterpart. Manual modifications of the design at gate level have been done in order to suppress these differences: for example we made sure the entities of both data paths were synthesized using the same types of logic gates.

Side-channel analysis of the AES

We first tested the TR-AES chip against side channel attacks. To start with, we took a quick look at what the standard deviation of the measured side-channel curves looked like: Figure 6 shows that while we have significant variations during the data transfers (that of the cipher for example), the variations seen during the AES calculation itself is close to "noise" levels. This was the first hint that our design choices reduced side channel information leakage. We observed both the power consumed and the EM waves emitted by the TR-AES during an encryption process and we tried to carry correlation analysis (CPA/CEMA) [START_REF] Brier | Correlation Power Analysis with a leakage model[END_REF] When the attack works (on a non protected AES implementation for example), the correct sub-key byte is thus obtained for the correlation curve which has the highest peak compared to the other ones (Figure 7). On the TR-AES, despite using a large number of curves (approximately 1,000,000 acquisitions), no significant data dependant leakage has been found (Figure 8).

Concerning the EM measurements, they were done in a more localised way, providing curves with better signal-to-noise ratios than for power measurements. We used a horizontal probe with a diameter of 150µm. We first identified the regions of the chip where the most significant data dependant variances were seen in the measured EM waves. For each of those regions, we carried Correlation EMA attacks.

We further tried different leakage models (for example targeting bits or bytes of the secret keys) but in vain. Those results illustrate the efficiency of the "dual" data representation of the TR-AES against power and EM attacks which have been proven to work on non-secure implementations of the AES. We also tested the TR-AES against fault attacks. The first injection means used is a green laser source whose wavelength (532nm) has proven to be efficient for front-side injections [Agoyan et al. (2010a)]. Preliminary tests were done with the energy set close to its minimum available value in the nano-Joule range to avoid damaging the chip and also to try to generate the least number of errors. The spot size was set around 50µm to allow a quick inspection of the chip area. Depending on the spatial and the temporal location of the laser shoot, different behaviours were observed. When the state machines of the AES module itself or the communication interface were affected, the communication with the chip was lost. Hitting the RND EXE or KEY EXPANDER modules lead to the output of massively faulted cipher-texts. To gain more insight into how to fine-tune precisely the laser energy and spot size to obtain faults restrained to a single byte, we targeted the last round. Even though there are, to our best knowledge, no published attacks on faults injected during the last AES round, these experiments allowed us to obtain the settings enabling the injection of single byte faults (a spot size of 6 -12µm and an energy between 0.2 and 5 nJ) and the location of the design's sensitive areas. To establish the efficiency of the detection mechanism, the laser pulses were operated in the time range of the penultimate AES round and on areas of the die corresponding to the ADD-RND-KEY and to the input registers of the SUB-BYTES module (see Figure 2).

We practically produced the effect illustrated in Figure 4: fault detection and error spreading. The laser injected faults (even single bit faults in some cases) during the AES calculation but the error was spread by our mechanism: given round are spread across at least seven other bytes at the end of the same round. However, the actual implementation suffers from a flaw: six out of the seven faulty bytes will reveal the original fault itself (in reverse bit order) when XORing with the correct cipher-text. That information leakage may ease the recovery of the secret key. Nevertheless, as stated in Section 3.2, what we intended to validate is the efficiency of the detection mechanism. To proceed, more than 5, 000 injection experiments were carried out on the RND EXE and KEY EXPANDER modules during the ante-penultimate and penultimate rounds. None of the obtained faults was able to defeat the detection mechanism. This validates the efficiency of our countermeasure's detection mechanism against laser induced faults.

Global clock-glitch-based fault injection attacks

Since the TR-AES chip works with an external clock, we chose to stress-test the circuit using the clock set-up time violation fault injection technique described in [START_REF] Agoyan | When clocks fail: on critical paths and clock faults[END_REF]]: we decrease the clock period at a targeted cycle in order to corrupt the execution of one particular round of the AES. This faulty clock is generated using the embedded Delay Locked Loop (DLL) of a Xilinx Virtex 5 FPGA. Two clocks (clkd1 and clkd2) with programmable skews are generated from the original 50MHz clock (clk) and the resulting faulty period is a combination of clkd2's rising edge and clkd1's falling edge (Figure 9). The generated clock's skew ∆T varies from 0 to ∆T max = 9804ps by steps of δT = 76ps (the DLL's smallest elementary delay). Hence, the period of the faulty In order to exploit the generation of single bit faults on AES, we used two differential fault cryptanalysis techniques where bytes of the 10 th sub-key were found. In the first one described in [START_REF] Giraud | DFA on aes[END_REF]], the attacker has to inject only one bit error at the end of the 9 th (one before last) round of the AES. Then by using the expected cipher-text and the corrupted one, bits of the secret keys can be found. For a given byte, with 3 corrupted cipher-texts, the corresponding sub-key byte is found with a probability of 99%. The second technique is given in [START_REF] Piret | A Differential Fault Attack Technique against SPN Structures, with Application to the AES and KHAZAD[END_REF]]. There, a single byte fault has to be injected at the end of the 8 th round of the AES such that the correct cipher-text and the faulty one differ by four bytes. With two faulty cipher-texts (resulting from the same intermediate state corrupted by faults injected on the same column), there are 97% chances of retrieving the corresponding column's secret sub-key. The TR-AES's error detection and spreading mechanism was initially designed to defeat these two differential cryptanalysis schemes.

For those two techniques to work on the TR-AES, we need to 'bypass' the error detection. To achieve this, corresponding "dual" errors have to be generated on the 'original' and the 'dual' data paths as shown in Figure 10. quently the error matrix is null, the error is not detected and at the end of the attacked round, only one byte is corrupted. A fault is hence generated and yet not detected by the countermeasure. We used the DLL-based clock set-up time violation board to inject the desired faults. The attack scenario used is given in Figure 11: for each of the different N random messages M, the skew on a 'specific' clock cycle (corresponding to a round) is increased until the 'attack condition' is satisfied. In the case of Giraud's attack, the clock skew is inserted during the 9 th round and the 'attack condition' corresponds to having a faulty cipher-text with only one corrupted byte. Out of N=60,000 executions, done in 36 hours, 235 cipher-texts had one faulty byte and among these, 6 different bytes locations were impacted. This approach revealed bytes 5, 7, 8, 9 and 10 of the AES 10 th sub-key and reduced to 3 the number of possibilities for the 1 st one. For the Piret-Quisquater's attack, the skew is inserted during the 8 th round and the 'attack condition' corresponds to having an entire column of the cipher-text impacted. We played 20,000 scenarios (in 13 hours), 9 of which induced four-byte errors on a column but only six were exploitable for the attack. We hence found bytes 2, 3,4,5,6,7,9,10,12,13,15 and 16 of the 10 th sub-key. By combining the results from both attacks we got 13 bytes of the 10 th sub-key and had only 3 possibilities for a 14 th one. The remaining sub-key bits could then be found using 3 × 2 8 × 2 8 brute force searches. With the 10 th sub-key, the original secret key can be calculated by executing the iterative KEY EXPANDER in the reverse order.

Discussion

The TR-AES's error detection and spreading mechanism was supposed to offer a full fault resistant countermeasure. It was based on the assumption that it was impossible to inject simultaneously the same fault (to be more specific, complemented faults) on the 'original' data path and on the 'dual' one. A first set of experiments, with a laser as a fault injection means, proves this assumption to be correct. This result was due to the nature of the laser beam we used, which had only a local effect on the AES chip. However, our detection mech- anism was defeated by the use of a fault injection means with a global effect: glitching the clock to induce timing constraint violations. We originally thought that it was impossible to inject the same fault in both paths. Nevertheless, we have obtained, with a success rate of 4 in 10000, faulty cipher-texts where the detection mechanism did not work. These faulty cipher-texts were successfully used to recover the secret key according the aforementioned DFA schemes. As a consequence, a new series of experiments was conducted to monitor the propagation delays (i.e. the critical times) of the original and dual data paths. The experimental scheme was based on the one described in Figure 11, with the following differences: at each iteration, both the plain-text and key were changed randomly, the 'attack condition' corresponding to the appearance of the first single bit fault, N was set to 50,000, and the clock glitch was injected during the penultimate round. Knowing the TR-AES architecture and both the key and the plain-text, we were able to calculate from the resulting cipher-texts the faults actually induced and their locations. Among them, 27,715 were single bit faults, and as a consequence, their corresponding times of occurrence gave the critical times corresponding to the handled data. The critical times of both original (left part) and dual (right part) data paths are reported in the bar diagrams of Figure 12.

In both diagrams, the critical times are distributed on the same time range of 11,500 to 13,100 ps. These distributions almost follow a Gaussian law. These The two distributions appearing on the same time range, it appears obvious that we were able to inject single bit faults simultaneously on both data paths. Then, from a statistical point of view, part of these faults had to be injected on the same bytes locations (one draw out of 16) and actually to be the same (one draw out of 255). This also reveals that the design of both data paths benefits from a good timing equilibrium. We think that this observation can account for the resistance of the chip to side channel attacks.

However, we call the reader's attention to the scales of the y-axis: that of the original data path is 10 times that of its dual counterpart (Figure 12). We expected them to be identical if the critical times of the two paths were the same. The critical time was reached 25,353 times in the 'original' path and 2,362 times in the 'dual' one.We explain this by a shadowing effect from the original data path on its complemented counterpart while measuring the critical time experi-mentally, the latter path having smaller critical times. We have mathematically tested this hypothesis by considering that both data paths have Gaussian distributions. Figure 13 illustrates a model of the critical times distributions that correspond to the results of Figure 12. This figure was drawn assuming that we were able to measure both data paths' propagation delays without suffering from the shadowing effect. The critical times' Gaussian distribution of the original data path has a mean of 12,400 ps, whereas the dual one has a mean of 11,850 ps. Their standard deviations are also different: 226 and 350 ps respectively for the original and dual data paths. The difference of their means, which is 550 ps, explains the shadowing effect.

The countermeasure would have been efficient against 'global' fault attacks if the two distributions did not intersect. However, such a modification would break the equilibrium between the propagations delays, and as a consequence would probably make side channel attacks feasible. This shows that there is here a contradiction between hardening a design against 'global' fault injection and protecting it against side channel attacks.

Conclusion

This paper describes an ASIC AES chip having a complemented duplicated implementation which constitutes a countermeasure against both fault attacks (detection via duplicated data paths and spreading of errors rendering the faulty cipher-text useless to DFA) and side-channel attacks (working on complemented data in parallel). Other design techniques like asynchronous circuits or Dual-Rail (DR) encoding have tried to tackle both kinds of attacks in the same way. Our approach is more cost efficient (only 67% overhead in our case on the whole chip) and our tests show significant robustness to attacks (against side-channel attacks and against 'local' laser fault attacks), which is not the case for the others when referring to [START_REF] Fournier | Security Evaluation of Asynchronous Circuits[END_REF]]. However, using clock set-up time violations, we showed that such a counter-measure is not enough to protect against fault injections. With Giraud's and Piret-Quisquater's techniques, 13 out of 16 secret key bytes were retrieved in less than 40 hours. It is, to our best knowledge, the first reported practical results on an AES ASIC chip showing that fault detection based on duplication can be defeated using low cost techniques. This counter-measure was designed to resist to a laser beam fault injection, which has a local effect, as opposed to a stress induced by a clock glitch which has a global effect on both data paths. In the light of the data retrieved from the fault attacks described in this paper, we believe that combined side-channel and fault attacks can be carried on such a design as further investigation.

Fig. 1 .

 1 Fig. 1. Structure of the 128-bit AES

Fig. 2 .

 2 Fig. 2. Architecture of the secure AES chip

Fig. 4 .

 4 Fig. 4. Fault on one 'data path' is generated & propagated

Fig. 5 .

 5 Fig. 5. Picture of the fabricated AES chip

Fig. 6 .

 6 Fig. 6. Standard deviation on power curves for 1000 different messages

Fig. 7 .

 7 Fig. 7. Correlation curves obtained from a CPA on a non-protected AES

Fig. 9 .

 9 Fig. 9. Faulty clock generation

Fig. 10 .

 10 Fig. 10. Faults generated on both paths without detection nor propagation

Fig. 11 .Fig. 12 .

 1112 Fig. 11. Attack scheme for Giraud's & Piret-Quisquater's attacks

Fig. 13 .

 13 Fig. 13. Rebuild of the distributions of the critical times of the original (dark grey) and dual (light grey) data paths according a Gaussian law (without shadowing effect).

;

  [START_REF] Gandolfi | Electromagnetic Analyis: Concrete Results[END_REF]]: for each byte

	M 9	M 9
	Sub-Bytes	Error Matrix Detection
	Error Matrix Calculation
	Shift-Rows
	K 10	K 10
	Faulted byte

Acknowledgements

This work was funded by the SECRICOM project (EC FP7-SEC-2007 grant 218123).


M Agoyan

S Bouquet

M Doulcier-Verdier

J.-M Dutertre

J Fournier

J.- B Rigaud

B Robisson

A Tria

Design of a duplicated fault-detecting AES chip and yet using clock set-up time violations to extract 13 out of 16 bytes of the secret key

Introduction

The secret keys manipulated by cryptographic circuits can be extracted using fault injections associated with differential cryptanalysis techniques [START_REF] Biham | Differential fault analysis of secret key cryptosystems[END_REF]. Such faults can be induced by different means such as lasers, voltage glitches, electromagnetic perturbations or clock skews. Several counter-measures have been proposed such as random delay insertions, circuit duplications or error correcting codes. In this paper, we focus on an AES chip in which the circuit duplication principle has been implemented to detect fault injection. We show that faults based on clock set-up time violations can nevertheless be used to defeat the implemented counter-measure.

Circuit description

The Tamper-Resistant (TR) AES chip is an ASIC implementation of a secure version of the 128-bit-key AES [START_REF]Announcing the Advanced Encryption Standard (AES)[END_REF] algorithm as described in [START_REF] Doulcier-Verdier | A side-channel and fault-attack resistant AES circuit working on duplicated complemented values[END_REF]. The chip is implemented in HCMOS9gp 130nm STM technology and works at 50 MHz. The algorithm is an iterative one consisting of rounds where the input data and intermediate values are represented as 4x4 matrices of bytes. Each round, which is executed in 1 clock cycle, uses a different round-key which is iteratively derived from the input secret key. The security strategy used is to detect induced errors and to spread them so that the resulted erroneous cipher-text can no longer be used for differential cryptanalysis [START_REF] Joye | Strengthening hardware AES implementations against fault attack[END_REF]. Error detection is achieved by duplicating the data paths of the RND_EXE and KEY_EXPANDER blocks in a dual manner (as shown in Fig. 1), thus creating an 'original data path' working on the input message and key and a 'dual data path' working on complemented values of the input message and key. The error detection is implemented in the SUB-BYTES module (the upper part of Fig. 2) whereby an Error Detection Matrix (EDM) is derived by comparing both data paths. Then, an Error Propagation Matrix (EPM) is built as shown in Fig. 3 before being injected on the data paths to obtain a spreading of the errors (the grey bytes in Fig. 2). Further diffusion of the errors is achieved by cross-changing wires between the original and the dual data paths in the SHIFT_ROWS module. Fig. 2 shows what happens when an error is generated on one of the data paths at the start of the last round: the resulting cipher-text has too many faulty bytes to be exploited by any differential cryptanalysis technique. The resistance of this TR-AES chip against sidechannel (due to the dual representations) and local laser fault (due to the error propagation mechanism) attacks is demonstrated in [START_REF] Doulcier-Verdier | A side-channel and fault-attack resistant AES circuit working on duplicated complemented values[END_REF].

The attack scenario

Since the TR-AES chip works with an external clock, we chose to stress-test the circuit using the clock set-up time violation fault injection technique described in [START_REF] Agoyan | When clocks fail: on critical paths and clock faults[END_REF]: we decrease the clock period at a targeted cycle in order to corrupt the execution of one particular round of the AES. This faulty clock is generated using the embedded Delay Locked Loop (DLL) of a Xilinx Virtex 5 FPGA (Fig. 5). ∆T max =9804ps by steps of δT=76ps (the DLL's smallest elementary delay). Hence, the period of the faulty clock cycle varies between 20ns and 10.196ns. In [START_REF] Agoyan | When clocks fail: on critical paths and clock faults[END_REF], the authors generated single bit faults on a non-secure FPGA implementation of the AES by monitoring the duration of the skew.

In order to exploit the generation of single bit faults on an AES, we used two differential fault cryptanalysis techniques where bytes of the 10 th round-key can be retrieved. In the first one, described by Giraud [START_REF] Giraud | DFA on AES[END_REF], the attacker has to inject only one bit error at the end of the 9 th (one before last) round of the AES. Then by using the expected cipher-text and the corrupted one, bits of the secret keys can be found. For a given byte, with 3 corrupted cipher-texts, the corresponding sub-key byte is found with a probability of 99%. The second technique is given by Piret & Quisquater in [START_REF] Piret | A differential fault attack technique against SPN structures, with application to the AES and Khazad[END_REF].

There, a single bit fault has to be injected at the end of the 8 th round of the AES such that the correct cipher-text and the faulty one differ by four bytes (one column). With two faulty cipher-texts corrupted on the same column, there are 97% chances of retrieving the corresponding column's secret round-key.

For those two techniques to work on the TR-AES, we need to 'bypass' the error detection. To achieve this, the same error is generated on the 'original' and the 'dual' data paths as shown in Fig. 6. Consequently the error matrix is null, the error is not detected and at the end of the round, only one byte is corrupted. A fault is hence generated and yet not detected by the counter-measure. The attack scenario used is given in Fig. 7: for each of the different N random messages M, the skew on a 'specific' clock cycle (corresponding to a round) is increased until the 'attack condition' is satisfied. In the case of Giraud's attack, the clock skew is inserted during the 9 th round and the 'attack condition' corresponds to having a faulty cipher-text with only one corrupted byte. Out of N=60000 executions, done in 36 hours, 235 cipher-texts had one faulty byte and among these 6 different bytes locations were impacted. This approach revealed bytes 5, 7, 8, 9 and 10 of the AES 10 th round-key and reduced to 3 the number of possibilities for the 1 st one. For the Piret-Quisquater's attack, the skew is inserted during the 8 th round and the 'attack condition' corresponds to having an entire column of the cipher-text impacted. We played 20000 scenarios (in 13 hours), 9 of which induced four-byte errors on a column but only six were exploitable for the attack. We hence found bytes 2, 3, 4, 5, 6, 7, 9, 10, 12, 13, 15 and 16 of the 10 th round-key. By combining the results from both attacks we got 13 bytes of the 10 th round-key and had only 3 possibilities for a 14 th one. The remaining round-key bits could then be found using 3×2 8 ×2 8 brute force searches. With the 10 th round-key, the original secret key can be calculated by executing the iterative round-key derivation algorithm in the reverse order.

Conclusion

The TR-AES chip is a secure cryptographic circuit having a complemented duplicated implementation designed to resist to fault attacks and to reduce the effect of side channel information leakage [START_REF] Doulcier-Verdier | A side-channel and fault-attack resistant AES circuit working on duplicated complemented values[END_REF]. Using clock set-up time violations, we showed that such a counter-measure is not enough to protect against fault injections. With Giraud's and Piret-Quisquater's techniques, 13 out of 16 secret key bytes were retrieved in less than 40 hours. It is, to our best knowledge, the first reported practical results on an AES ASIC chip showing that fault detection based on duplication can be defeated using low cost techniques. This counter-measure was designed to resist to a laser beam fault injection [START_REF] Doulcier-Verdier | A side-channel and fault-attack resistant AES circuit working on duplicated complemented values[END_REF], which has a local effect, as opposed to a stress induced by a clock glitch which has a global effect on both data paths. In the light of the data retrieved from the fault attacks described in this paper, we believe that combined side-channel and fault attacks can be carried on such a design.

Fig. 1 : 2 :

 12 Fig. 1: TR-AES block diagram Fig. 2: Fault generated on one path with detection and propagation

Fig. 3 : 4 :

 34 Fig. 3: Error Matrix calculation Fig. 4: Picture of the TR-AES chip

Fig. 5 :

 5 Fig. 5: Faulty Clock Signal Generation

Fig. 6 : 7 :

 67 Fig. 6: Faults generated on both paths Fig. 7: Attack scheme for Giraud's or without detection nor propagation Piret-Quisquater's attacks

Acknowledgements

This work was funded by the SECRICOM project (EC FP7-SEC-2007 grant 218123).