Christian Kahl

Stephen Crane

Markus Tschersich

Kai Rannenberg

Privacy respecting targeted advertising for social networks

Keywords: Communities, Identity Management, Mobile Advertising, Mobile Marketing, Mobile Social Networks, Privacy, Trust

Online Social Networks form an increasingly important part of people's lives. As mobile technologies improve accessibility, concerns about privacy and trust are more apparent as advertising becomes a critical component of most social network's economic model. In this paper we describe the PICOS project's research into privacy preserving advertising options for social networks. We introduce an architecture that includes new concepts and technologies specifically designed to improve privacy and trust as well as advertising opportunities within social networks.

Introduction

Online social networks1 such as Facebook, MySpace, and LinkedIn, provide communication services that support the activities of virtual and real world communities (cf. [START_REF] Nielsen | Critical Mass -Worldwide State of the Mobile Web[END_REF], [START_REF] Nielsen | Global Faces and Networked Places -A Nielsen report on Social Networking's New Global Footprint[END_REF], [START_REF] Liesebach | D2.4 Requirements. Public Deliverable of EU Project PICOS[END_REF]). Nowadays people spend increasing amounts of work and leisure time in using these services for professional and private collaboration and communication purposes. Mobile communication also allows the provision of services that make use of context information (e.g., location, time), thereby enabling a deeper integration of peoples' virtual (mobile) and real world communities (e.g., Loopt, Junaio, match2blue) 2 . Advertising, as a specific marketing activity, is an important way for social network providers to generate revenues, and is hence an integral part of many providers' business models. However, while classical online display advertising is focused on the more general target groups, with advertising activities in social networks often lacking success [START_REF] Nielsen | Global Faces and Networked Places -A Nielsen report on Social Networking's New Global Footprint[END_REF][START_REF]Study on Social Network Adertisements[END_REF][START_REF]Consumer Online Attitudes Survey Results, Part III: Social Networking[END_REF], advertisers are now looking for greater assurance that targeted audiences will be interested in their offerings. Social networks are especially attractive for targeted advertising and viral marketing campaigns [START_REF] Kotler | Principles of Marketing[END_REF].

However, the inclusion of personal information regarding users in these activities raises questions about user privacy and the use of their personal data. The desire by users for privacy within social networks on the one hand, and the need for advertising in these social networks on the other hand, creates a certain tension between the interests of the involved stakeholders. A balance needs to be achieved between these partially diverging interests of the involved parties, namely users, advertisers and the social network provider [START_REF] Liesebach | D2.4 Requirements. Public Deliverable of EU Project PICOS[END_REF].

Research question and approach

Consequently, a new approach to identity management in social networking services is required in order to meet the stakeholders' different needs. Within the PICOS project 3 , we had the goal to develop such a new approach to identity management that would enhance trust, privacy and identity management aspects of social networking services, while at the same time enabling 3 rd party services including marketing and advertising.

PICOS started with a phase of preliminary activities, including the analysis of related contemporary research and an investigation of the context of communities (e.g., legal, technical and economic aspects) (c.f. [START_REF] Schrammel | D2.2 Categorisation of Communities. Public Deliverable of EU Project PICOS[END_REF], [START_REF] Kosta | D2.3 Contextual Framework. Public Deliverable of EU Project PICOS[END_REF], [START_REF] Liesebach | D2.4 Requirements. Public Deliverable of EU Project PICOS[END_REF]). Based on requirements of three exemplary mobile communities (anglers, online gamers, taxi drivers), we designed a community platform architecture including concepts to address the gathered requirements [START_REF] Crane | D4.2 Architecture v2. Public Deliverable of EU Project PICOS[END_REF]. The developed concepts were implemented as prototype community platform and community applications, which we subsequently tested in user trials and evaluated with regard to trust, privacy, usability, ergonomics and legal issues (c.f. [START_REF] Kahl | How to enhance Privacy and Identity Management for Mobile Communities: Approach and User driven Concepts of the PICOS Project[END_REF]).

This paper reports on the PICOS community platform architecture [START_REF] Crane | D4.2 Architecture v2. Public Deliverable of EU Project PICOS[END_REF], focusing in particular on the targeted advertising component 4 . The following section provides a brief overview of the PICOS architecture and its concepts. Section 3 focuses on the advertising component, as a part of the architecture. Section 4 briefly provides details about the prototypical implementation of the architecture and the advertising component implementation in particular. Section 5 provides an overview of related work and section 6 concludes and indicates aspects for further research.

PICOS Architecture

The PICOS architecture has been designed to satisfy the needs of several stakeholders, and in so doing minimise the tensions around privacy and trust that would otherwise discourage contributions from any or all parties' involvement in the community. To address the users requirements, the architecture consists of components which provide different functionalities (concepts). PICOS functionality is delivered as a service. Services could be hosted locally, but in the case of PICOS they are hosted centrally. In this client-server topology, clients (e.g. smart phones) process local services but rely on the social network for shared services and for services that are too demanding (in terms of computing and storage resources) for the client to host.

Stakeholders

In situations where personal information is being shared, it is common for the various stakeholders to have different opinions about the use of the data. In social networks these stakeholders are:

 Members/users: The subject of the personal data  Community providers: Community service and/or communications provider  Community operators: The entity responsible for the operation of the community  3 rd parties: E.g. advertisers, regulators, external service providers.

Components & Concepts

The PICOS architecture comprises a number of new concepts designed to enhance user privacy. The overall intention is to provide users with tools that help them manage their visibility within and outside of the community. The three main categories of concepts are: Enhanced Identity Management. Based on the concept of mobile identity management [START_REF] Müller | Study on Mobile Identity Management, Public Deliverable of EU Project FIDIS[END_REF], the PICOS architecture supports users in managing the disclosure of their current position and mobile identity in communities. E.g. Sub-communities help users in selectively sharing personal information, as they represent a restricted area in which the sharing of content is limited to a sub-group of community members. Partial Identities [START_REF] Hansen | Privacy-Enhancing Identity Management[END_REF] allow users to create different identities for use in different contexts and purposes. With the help of Partial Identities users are able to have a set of several identities in a single community, and decide for each identity what personal information they want to disclose. User controlled Information Flows. A balance is needed between revealing (publishing) personal information in order to use functionalities provided by the community, and maintaining a degree of privacy [START_REF] Liesebach | D2.4 Requirements. Public Deliverable of EU Project PICOS[END_REF]. Location Blurring gives users the enhanced ability to hide their exact position without being completely invisible to others. It foresees the obfuscation of a user's position on a map at various levels. The users can control, who is able to see their exact and their blurred position. Privacy Policies enable users to selectively define policies that control who is allowed to see which kind of personal information. Privacy Awareness Support. Managing privacy by means of Partial Identities is a complex task. The Privacy Advisor component is designed to provide guidance on privacy related matters that may affect members as they interact with the community. Privacy (and trust) is subjective, and it is often difficult to find a single 'right answer' to questions and concerns about privacy. Hence, the Privacy Advisor is context sensitive and provides hints in specific situations that involve users' personal information (e.g. disclosure of location information, registration and profile management). It warns users when disclosure of information might place their privacy at risk.

The Advertising Component

The advertising component enables advertising activities to be carried out with due consideration of context and users' privacy preferences, managed by the aforementioned concepts. The foundation for this component was initially outlined in [START_REF] Kahl | Towards reasonable Revenue Streams through Marketing in Mobile Social Networks[END_REF]. Within PICOS we targeted an exemplary application that was extended to include this advertising approach, resulting in a concrete social network service solution that gives users control over the use of their personal data. This unique approach is part of our community platform architecture and within one of our community application prototypes (gaming community prototype).

Approach

Communication can be regarded as one of the main activities conducted in social networks [START_REF] Carroll | Success Factors of Online Social Networks[END_REF]. Hence, in order to include marketing (and in particular advertising) activities into social networks, these activities need to be integrated into the context of the communication processes, in order to be able to receive the attention of the participating users [START_REF] Kahl | Towards reasonable Revenue Streams through Marketing in Mobile Social Networks[END_REF][START_REF] Palmer | An experiential, social network-based approach to direct marketing[END_REF]. Advertising can contribute to the communication in two ways: First, advertisers can provide targeted communication (targeted advertising) to social network users (Business-to-Consumer communication (B2C)). Second, advertisers can support the communication between users (viral marketing) (Consumer-to-Consumer communication (C2C)). While the targeting of advertising activities provides a benefit to the targeted users [START_REF] Nielsen | Global Faces and Networked Places -A Nielsen report on Social Networking's New Global Footprint[END_REF][START_REF] Ho | The Attraction of Personalized Service for Users in Mobile Commerce: An Empirical Study[END_REF], at the same time viral marketing is used in existing social networks 5 to benefit from the intensive social interactions between users. By supporting both in a novel way, communication between marketers and users is tailored more to an individual user's needs and is consequently more relevant. Further, users are encouraged to communicate with each other about such relevant advertisements [START_REF] Schulz | Virales Marketing im Web 2.0[END_REF][START_REF] Dobele | Controlled infection! Spreading the brand message through viral marketing[END_REF].

Component Elements

To support B2C and C2C communication processes, the social network provider acts as an intermediary between advertisers and users. This ensures that personal data of users is neither given to 3 rd parties nor that 3 rd parties have any direct access to it.

Instead, the social network provider (e.g. a game developer in the case of the gaming community example) serves both the advertisers and the consumers, while respecting their specific interests (e.g. privacy of users). Support of B2C communication. In order to support direct communication between advertiser and user, the social network provider needs to identify the users for which a particular advertisement might be relevant. He thereby conducts a matching operation between the users (consumers) and advertisers (represented by advertisements), based on profile, context and communication information. More targeted advertisements generally receive more attention by users, especially with regard to mobile usage scenarios [START_REF] Ho | Opportunities and challenges of mobile personalization: An exploratory study[END_REF][START_REF] Beales | The Value of Behavioral Targeting (Study), Networked Advertising Initative[END_REF]. On the other hand, users can set their privacy preferences (e.g. using privacy policies and blurring settings) in response to the purpose of targeted advertising. This enables social network provider to respect privacy preferences and satisfy users' needs for relevant advertisements, while at the same time enabling advertisers' to fulfil their interests and reach their target audience. The whole process of supporting B2C communication can be divided into four steps, which are reflected in the design of the PICOS advertising component as follows (Figure 1). Configuration. The advertising component provides a graphical interface, which allows configuring different advertising activities. As similarly described in e.g. [START_REF] Albers | Prototypical Implementation of an Intermediary Platform for Context-sensitive Mobile Marketing Applications[END_REF][START_REF]Commercialisation of Context-sensitive Mobile Attention in Mobile Media Markets -Design Recommendations for Mobile Marketing Providers, Schriften zum Mobile Commerce und zum Mobilfunk[END_REF][START_REF] Hristova | Ad-me: Wireless Advertising Adapted to the User Location, Device and Emotions[END_REF] the advertiser can configure, which message he wants to deliver and whom he wants to target. Hence, the dimensions the advertiser needs to configure are the advertisement itself and the target profile. The form of an advertisement can be a selection of different types, e.g. banners, pop-up, etc. By defining the attributes of the target profile, the advertiser can describe his targeted users. Example: Target Profile: "male, 20-35 years, within 2 km around my shop, between 12 h and 18 h, key word in communication: 'lunch'" The advertiser can configure how many attributes need to be equal in order to achieve a "matching" of target profile and user profile. For each attribute, the advertiser can also configure if this attribute needs to match in every case. In such a situation, no matching can be achieved if these "necessary" attributes are not fulfilled. E.g., if a user needs to be at least 18 years of age in order to receive an advertisement. Analysis. In order to determine which advertisement might be relevant for which user, information about the user is needed, which is gathered from the user profile, the context and communications/interactions with other users [START_REF] Kahl | Towards reasonable Revenue Streams through Marketing in Mobile Social Networks[END_REF]. The user profile contains attributes such as age, interests and favourite locations. The context is mainly described by the current location of the user (as geo-coordinates) in combination with the time and information which might be derived from the location (e.g. current weather conditions at this location). Communications could be all kinds of interactions in which a user communicates with other users, e.g. directly (mailing or chatting) as well as indirectly (e.g. via contributions in sub-communities). Such additional information, which has not been combined in previous approaches in a similar way, allows a more precise characterization of users and to draw conclusions about what users are doing, in addition to who they are. The gathered information leads to a dynamic user profile, which contains the profile, the context and communication information about the user. Matching. The dynamic user profile characterises the user in his current context. In the "Matching" process the dynamic user profile and the target profiles are compared. There are different ways to realise such matching in an actual implementation, and which of these ways is chosen might depend on various economic, organisational or technical reasons. In our case a comparison of attributes is conducted. If a pre-defined number of attributes are equal, a match is given. In the approach described by [START_REF] Kahl | Towards reasonable Revenue Streams through Marketing in Mobile Social Networks[END_REF], the matching additionally contains a comparison between the communicating users. This is to identify similarities and common interests between them and present matching advertisements not only to one but to both of them. Display. In the final step of the process, the actual advertisement needs to be shown to the identified matching users. In practice this also includes further considerations regarding the users' device. It might be necessary to adapt the advertisement due to technical specifications or limitations of particular devices and/or operating systems.

Support of C2C communication.

The support of C2C communication is based on the principle of viral marketing, that is to initiate a marketing message and let it spread from one user to other users (who distribute it further) like a virus [cf. 18]. The goal here is to establish and support such a viral (marketing) process. In literature and practice there is a varying understanding about how viral marketing works in detail [START_REF] Phelps | Viral Marketing or Electronic Word-of-Mouth Advertising: Examining Consumer Responses and Motivations to Pass Along Email[END_REF]. In many social networks viral marketing is conducted by introducing a product or brand to the community (e.g. with a related profile or group on Facebook). The difference in our case is that viral marketing is designed to work in a targeted way, in order to address several opinion leaders who further spread the message [START_REF] Dobele | Why pass on viral messages? Because they connect emotionally[END_REF]. This process comprises the following steps:

Configuration. As in B2C support the advertiser has various options to configure an advertisement and to describe the targeted users, including targeted characteristics (e.g. age, interests). The configuration also includes options regarding the form of the delivery (e.g. pop-up, text message, etc.). The distinctiveness is that the advertiser defines the characteristics of the "key users", which should be addressed in order to further spread the advertisement. These users are regarded as opinion leaders, which have a stronger influence on their social surrounding [START_REF] Dobele | Controlled infection! Spreading the brand message through viral marketing[END_REF][START_REF] Phelps | Viral Marketing or Electronic Word-of-Mouth Advertising: Examining Consumer Responses and Motivations to Pass Along Email[END_REF]. Depending on the actual advertisement which shall be delivered, there are different definitions of who the "key users" are, e.g. users who are very active with regard to communication, or users who have many relationships to other users (friends) or certain characteristics (e.g. a certain age). The definition of key users might also be a combination of such different characteristics. Analysis & Matching. The analysis of user information (profile, context, communication) leads to a dynamic user profile, consisting of profile, context and communication information, as described previously. In the "matching" step, the characteristics of the key users (target profile) are compared to the dynamic profile of a user. The difference to the Matching process for targeted advertising is that only a limited number of matching users are addressed, namely the key users. These users are the users which match best with the target profile and fulfil the mentioned characteristics of key users. Seeding. This phase includes the actual delivery of the advertising message to the identified key users, the so-called "seeding", in order to allow them to pass on the delivered message. Depending on how an advertisement is configured the form of delivery may vary. To support the action of forwarding (spreading) of the delivered message, advertisements need to contain a possibility to immediately and easily share them with other users (e.g. context Link on a specific site, Banner with possibility to forward, etc.).

Triggering. The whole viral marketing process is intended towards the viral distribution of the advertisement. Hence, an important part in this approach is not only to identify adequate users and provide them with the advertising message, as described before, but also to provide or support a motivation to these Users to forward advertisements they receive [START_REF] Pousttchi | Mobile Viral Marketing -Ein State of the Art[END_REF]. One step to support this is already the targeting itself, considering that we aim to provide only highly relevant advertisements to users. Further, an already existing intrinsic motivation of users to forward advertised messages, can be supported by the availability of technical possibilities, which allow and simplify a further recommendation to other users (e.g. "forward" button).

Prototypical Implementation

The PICOS architecture is a service oriented architecture consisting of 1) access and user management features, and 2) service delivery features. The current J2ME 6 based embodiment consists of a set of hosted web-based services, which implement the described concepts.

The advertising component is implemented based on the example of "commercial points of interest" (CPOI), e.g. cafés, shops, etc. For these CPOI's, a target user profile can be defined for some exemplary attributes (e.g. age). A matching is realised by comparing the attributes between this profile and profiles of users within a certain proximity of the CPOI. Under consideration of users' privacy preferences, advertisements are provided to matching users. The PICOS Privacy policies enable users to select the information which may be used for advertising. A recommendation mechanism further allows supporting user-to-user communication (C2C). Therefore a recommendation button is directly integrated in an advertisement.

Related Work

The aspect of privacy in online social networks is discussed intensively in the research area (cf. e.g. [START_REF] Chew | Undermining Privacy in Social Networks[END_REF][START_REF] Adu-Oppong | Social Circles: Tackling Privacy in Social Networks[END_REF][START_REF] Hiltz | Trust and Privacy Concern Within Social Networking Sites: A Comparison of Facebook and MySpace[END_REF]), but there with focus on online social networks usually not considering the special aspects of mobile social networking services.

Other projects, such as PRIME 7 , PrimeLife 8 , PEPERS 9 and DAIDALOS 10 , have carried out work in this area. However, their work was focused on different aspects, e.g. on privacy and identity management in general (PRIME, PEPERS, DAIDALOS) or privacy in communities but not with regard to a specific application domain (PrimeLife). There are also some concepts in theory and practice which aim to help the user with regard to privacy. For instance, the "Privacy Bird" from AT&T 11 advises users on the privacy of website, using a P3P 12 policy matching algorithm. The Trustguide 13 research confirmed that openness backed up by education, which together provide enhanced understanding and awareness, engenders trust. This is particularly true when applied to situations involving privacy.

Regarding work in relation to the advertising approach, there are a few publications that focus on this aspect with regard to social networks. While some address general aspects, such as business models [START_REF] Hoegg | Overview of business models for Web 2.0 communities[END_REF][START_REF] Palmer | An experiential, social network-based approach to direct marketing[END_REF], many focus on the application of viral marketing in the context of communities (e.g. [START_REF] Leskovec | The Dynamics of Viral Marketing[END_REF][START_REF] Kempe | Maximizing the Spread of Influence through a Social Network[END_REF][START_REF] Hartline | Optimal Marketing Strategies over Social Networks[END_REF][START_REF] Subramani | Knowledge Sharing and Influence in Online Social Networks via Viral Marketing[END_REF]). As mentioned, [START_REF] Kahl | Towards reasonable Revenue Streams through Marketing in Mobile Social Networks[END_REF] is concerned with a deeper integration of marketing into the communication processes within social networks, and provides the basis for the advertising approach described in this paper.

Conclusion

The PICOS Architecture serves as a basis for integrating privacy enhancing concepts and advanced advertising into (mobile) community infrastructures. The architecture enables providers, users and involved 3rd party stakeholders to provide and use privacy enhancing social networking features. The advertising approach adopted by the architecture shows how a deeper integration of advertising is possible in (mobile) social networks and how the tension between diverging interests of the involved stakeholders can be addressed. The prototypical implementation of the PICOS architecture has further shown the feasibility of enclosed concepts such as those focused on in this paper. The currently ongoing analysis and evaluation of the PICOS user trial results will give additional insights on this. Nevertheless, further research on the integration, usage and benefits of the concepts, and in particular advertising in social networks, remains a challenge for advertisers and social network providers. Much research in this area considers specific aspects of marketing or advertising. However, holistic approaches are needed in order to consider the different stakeholders in social networks and the factors which influence the success of marketing activities. In one of our next steps our research activities will focus on specific application scenarios, considering the diversity of social networks and as well the diversity of products and brands which are subject to marketing.

Fig. 1 .

 1 Fig.1. The process to support targeted advertising (B2C) (Based on[START_REF] Kahl | Towards reasonable Revenue Streams through Marketing in Mobile Social Networks[END_REF]).

Also referred to as "social communities". If not stated otherwise, both terms are used synonymously in this paper.

www.loopt.com, www.junaio.com, www.match2blue.com

The research leading to these results has received funding from the European Community's Seventh Framework Programme (FP7/2007-2011) under grant agreement n° 215056

For a more general overview of the PICOS architecture, see further[START_REF] Kahl | How to enhance Privacy and Identity Management for Mobile Communities: Approach and User driven Concepts of the PICOS Project[END_REF].

See e.g. Facebook Advertising (www.facebook.com/advertising)

Java 2 Platform, Micro Edition (http://www.oracle.com/technetwork/java/javame/overview)


Yumi Sakemi

Tetsuya Izu
email: izu@labs.fujitsu.com

Masahiko Takenaka
email: takenaka@labs.fujitsu.com

Masaya Yasuda
email: myasuda@labs.fujitsu.com

Solving DLP with Auxiliary Input over an Elliptic Curve Used in TinyTate Library

The discrete logarithm problem with auxiliary input (DLP-wAI) is a problem to find α from G, αG, α d G in an additive cyclic group generated by G of prime order r and a positive integer d dividing r -1. The infeasibility of DLPwAI assures the security of some cryptographic schemes. In 2006, Cheon proposed a novel algorithm for solving DLP-wAI. This paper shows our experimental results of Cheon's algorithm by implementing it with some speeding-up techniques. In fact, we succeeded to solve DLPwAI in a group with 128-bit order in 45 hours with a single PC on an elliptic curve defined over a prime finite field with 256-bit elements which is used in the TinyTate library.

Introduction

Let G be an additive cyclic group generated by G of prime order r. The discrete logarithm problem with auxiliary input (DLPwAI) is a problem to find α from G, αG, α d G ∈ G and a positive integer d dividing r -1. The infeasibility of DLPwAI assures the security of some cryptographic schemes including Boneh-Boyen's ID-based encryption scheme [START_REF] Boneh | Efficient Selective-ID Secure Identity-based Encryption without Random Oracles[END_REF] and Boneh-Gentry-Waters' broadcast encryption scheme [START_REF] Boneh | Collusion Resistant Broadcast Encryption with Short Ciphertext and Private Keys[END_REF]. In 2006, Cheon proposed a novel algorithm for solving DLPwAI [START_REF] Cheon | Security Analysis of Strong Diffie-Hellman Problem[END_REF][START_REF] Cheon | Discrete Logarithm Problems with Auxiliary Inputs[END_REF]. The time complexity of Cheon's algorithm (with KKM improvement) is O (r -1)/d + √ d , and especially when d ≈ √ r, the complexity becomes O( 4 √ r), which is much efficient than that for solving DLP in general groups (which requires O( √ r)).

This paper implements Cheon's algorithm combined with the baby-step giantstep algorithm [START_REF] Shanks | Class Number, a Theory of Factorization, and Genera[END_REF] as a sub-algorithm and some speeding-up techniques. Then, this paper reports experimental results of our implementation. In fact, we have successfully solved a DLPwAI in 45 hours with a single PC in a group with 128-bit order defined on an elliptic curve over a prime finite field with 256bit elements, which is used in the TinyTate library [START_REF] Oliveira | TinyTate: Identity-Based Encryption for Sensor Networks[END_REF] for implementing pairing cryptosystem in the embedded devices (see also Table 1. Note that Jao-Yoshida's result was not dedicated to an efficient implementation. Also note that Izu et al.'s result was implemented over a finite field with characteristics 3). Here, solving Table 1. Required time for solving DLPwAI Size of r Required Time Jao, Yoshida [START_REF] Jao | Boneh-Boyen Signatures and the Strong Diffie-Hellman Problem[END_REF] 60 bit 3 hours Izu et al. [START_REF] Izu | Experimental Results on Cheon's Algorithm[END_REF] 83 bit 14 hours This paper 128 bit 45 hours DLP on the elliptic curve is regarded to be infeasible (since the order is 128-bit).

As a feedback of our experimental results, it is better to avoid such elliptic curve when some cryptographic schemes are implemented. We also estimated the required time and memory for solving DLPwAI with larger r. According to our estimations, it would be difficult to solve DLPwAI with larger r by the same approach, namely, Cheon's algorithm combined with the baby-step giant-step algorithm.

Preliminaries

This section introduces the discrete logarithm problem with auxiliary input (DLPwAI) and Cheon's algorithm for solving DLPwAI [START_REF] Cheon | Security Analysis of Strong Diffie-Hellman Problem[END_REF][START_REF] Cheon | Discrete Logarithm Problems with Auxiliary Inputs[END_REF]. Implications of DLPwAI and Cheon's algorithm on cryptographic schemes are also explained.

Discrete Logarithm Problem with Auxiliary Input (DLPwAI)

Let G = G be an additive group generated by G of prime order r. The discrete logarithm problem (DLP) in G is to find α ∈ Z/rZ on input G, αG ∈ G. In the general setting, the most efficient algorithms for solving DLP require O( √ r) in time. In fact, Shanks' baby-step giant-step (BSGS) algorithm [START_REF] Shanks | Class Number, a Theory of Factorization, and Genera[END_REF] requires O( √ r) group operations in time and O( √ r) group elements in space. On the other hand, Pollard's λ-algorithm also requires O( √ r) in time, but much smaller elements in space.

In 2006, Cheon defined the discrete logarithm problem with auxiliary input (DLPwAI) as a variant of DLP [START_REF] Cheon | Security Analysis of Strong Diffie-Hellman Problem[END_REF][START_REF] Cheon | Discrete Logarithm Problems with Auxiliary Inputs[END_REF], where DLPwAI is a problem to find α on input G, αG, α d G and an integer d dividing r -13 . At the same time, Cheon proposed a novel algorithm for solving DLPwAI [START_REF] Cheon | Security Analysis of Strong Diffie-Hellman Problem[END_REF][START_REF] Cheon | Discrete Logarithm Problems with Auxiliary Inputs[END_REF]

Input: : G, G1 = αG, G d = α d G ∈ G, d ∈ Z dividing r -1 Output: : α ∈ Z/rZ 1: Find a generator ζ ∈ (Z/rZ) * 2: Set ζ d ← ζ d , d1 = (r -1)/d 3: [Step 1] Find 0 ≤ k1 < (r -1)/d such that G d = ζ k 1 d G 4: Find 0 ≤ u1, v1 < d1 such that ζ -u 1 d G d = ζ v 1 d 1 d G 5: k1 ← u1 + v1d1 6: Set ζe ← ζ (r-1)/d , d2 ← √ d , Ge ← ζ -k 1 G1 7: [Step 2] Find 0 ≤ k2 < d such that Ge = ζ k 2 e G 8: Find 0 ≤ u2, v2 < d2 such that ζ -u 2 e Ge = ζ v 2 d 2 e G 9: k2 ← u2 + v2d2 10: Output ζ k 1 +k 2 (r-1)/d

Cheon's Algorithm

A goal of Cheon's algorithm is to find an integer k ∈ Z/rZ such that α = ζ k for a generator of the multiplicative group ζ ∈ (Z/rZ) * (Note that finding the generator ζ is easy). Here, such k is uniquely determined. To do so, Cheon's algorithm searches two integers

k 1 , k 2 such that k = k 1 + k 2 (r -1)/d satisfying 0 ≤ k 1 < (r -1)/d, 0 ≤ k 2 < d in the following two steps (see Algorithm 1).
Step 1 searches an integer k 1 such that

α d = ζ k1 d for ζ d = ζ d , or equivalently, searches two integers u 1 , v 1 such that α d ζ -u1 d = ζ v1d1 d satisfying 0 ≤ u 1 , v 1 < (r -

G.

In Cheon's algorithm, searching u 1 , v 1 in Step 1 and searching u 2 , v 2 in Step 2 require another sub-algorithm. Since these problems are very similar to DLP in the general setting, the baby-step giant-step algorithm or the λ-algorithm can be used as a subroutine. Since this paper is interested in Cheon's algorithm combined with the baby-step giant-step algorithm only, the next section briefly describes its outline.

Baby-step Giant-step Algorithm

The baby-step giant-step (BSGS) algorithm was introduced by Shanks in 1971 for solving DLP [START_REF] Shanks | Class Number, a Theory of Factorization, and Genera[END_REF]. Instead of finding α directly, on input G and G 1 = αG, BSGS searches two integers i, j such that α = i + jm and 0 ≤ i, j < m = ⌈ √ r⌉. Here, such i, j are uniquely de-

termined. Since αG = (i + jm)G = iG + jG ′ for G ′ = mG, we have a relation G 1 -iG = jG ′ .
BSGS consists of two steps: in the 1st step (the baby-step), we compute

G 1 , G 1 -G, G 1 -2G, . . . , G 1 -(m -1)G
successively and store them in a database. In the 2nd step (the giant-step), we compute When BSGS algorithm is used in Step 1 of Cheon's algorithm, we establish two databases Let us describe KKM improvement for a scalar multiplication γP (γ ∈ Z/rZ, P ∈ G) in the followings. For a fixed integer c (which will be optimized later) and n = ⌈ c √ r⌉, obtain the n-array expansion of the scalar γ = c-1 i=0 γ i n i (0 ≤ γ i < n). For all 0 ≤ i < c and 0 ≤ j < n, compute S(i, j) = jn i P and store them in a table in advance to the scalar multiplication. Then, the scalar multiplication γP is computed by the following way:

G ′ , 2G ′ , . . . , (m -1)G ′
ζ 0 d G d , ζ -1 d G d , ζ -2 d G d , . . . , ζ -d1 d G d and ζ 0 d G, ζ d1 d G, ζ 2d1 d , . . . , ζ
γP = γ 0 P + γ 1 nP + • • • + γ c-1 n c-1 P = S(0, γ 0 )+S(1, γ 1 )+• • •+S(c -1, γ c-1 ). ( 1
)
Since the precomputation table can be computed by at most c scalar multiplications and cn additions, KKM improvement reduces the time complexity of Cheon's algorithm by a factor of log r.

Complexity of Cheon's Algorithm

As a summary of this section, when Cheon's algorithm is combined with the baby-step giant-step algorithm and KKM improvement, the time complexity T and the space complexity S are evaluated by the followings:

T = O (r -1)/d + √ d (group operations), S = O max (r -1)/d, √ d (group elements).

DLPwAI in Cryptographic Schemes

In recently proposed cryptographic schemes, new mathematical problems have been proposed and the infeasibility of such problems assure the security of the schemes. For example, ℓ-BDHE problem was introduced in Boneh-Gentry-Waters' broadcast encryption system [START_REF] Boneh | Collusion Resistant Broadcast Encryption with Short Ciphertext and Private Keys[END_REF]. Here, ℓ-BDHE problem is a problem to find e(G, Ĝ) α ℓ+1 for a given bilinear map e : G × Ĝ → G T on input G, αG, . . . , α ℓ G, α ℓ+2 G, . . . , α 2ℓ G ∈ G and Ĝ ∈ Ĝ, where G = G , Ĝ = Ĝ , and G T is a multiplicative group with order r. When ℓ > d, Cheon's algorithm can be applied to the scheme: by finding α as DLPwAI, an answer of ℓ-BDHE problem is obtained. Thus, Cheon's algorithm is an attacking algorithm for such cryptographic schemes. Note that there are many other recently proposed problems to which Cheon's algorithm can be allied such as ℓ-SDH problem [START_REF] Boneh | Short Signatures without Random Oracles[END_REF], ℓ-sSDH problem [START_REF] Boneh | Hierarchial Identity Based Encryption with Constant Size Ciphertext[END_REF], ℓ-BDHI problem [START_REF] Boneh | Efficient Selective-ID Secure Identity-based Encryption without Random Oracles[END_REF].

Implementation

This section describes our strategy for implementing Cheon's algorithm. We adopted the baby-step giant-step (BSGS) algorithm as a subroutine, and KKM improvement for the speeding-up.

BSGS Algorithm

Databases In step 1 of Cheon's algorithm, when BSGS algorithm is used, two databases

DB 1,B = {ζ 0 d G d , ζ -1 d G d , . . . , ζ -i d G d , . . . , ζ -d1 d G d } and DB 1,G = {ζ 0 d G, ζ d1 d G, . . . , ζ jd1 d G, . . . , ζ
|| LSB 64 (MD5(x(ζ -i d G d )||y(ζ -i d G d ))) 8-byte
where i is assumed to be 4-byte, LSB 64 (•) represents the least 64-bit (8-byte) of the data, MD5 is the hash function, and x(G), y(G) represent x-and ycoordinate values of a point G on an elliptic curve. In the following, i is identified as the index part and the rest is as the data part. Similarly, in the database DB ) is inefficient, we used the following bucket-sort like algorithm [START_REF] Aoki | Sieving Using Bucket Sort[END_REF].

1. Divide each database into 64 sub-databases depending on the most significant 6-bit of the index part. When the most significant 6-bit of data

ζ -i d G d in DB 1,B is ℓ (0 ≤ ℓ ≤ 63), it is stored in the sub-database DB (ℓ) 1,B . Similarly, when the most significant 6-bit of data ζ jd1 d G in DB 1,G is ℓ (0 ≤ ℓ ≤ 63), it is stored in the sub-database DB (ℓ) 1,G . 2. Sort all sub-database DB (ℓ)
1,G (ℓ = 0, . . . , 63). by the comb-sort algorithm [START_REF] Box | A Fast Easy Sort[END_REF], which sorts N elements in O(log N ). If a collision is found in step 3 for a certain ℓ, then, their indexes are what we required: set u 1 ← i and v 1 ← j.

For each ℓ, search a collision among DB

KKM Improvement

In our implementation, KKM improvement is also used for speeding-up Cheon's algorithm. Since our target group G is on an elliptic curve defined over a prime finite field with a mediate size, the affine coordinate system is used rather than the projective coordinate system. In the affine coordinate, every elliptic curve addition requires an inversion computation in the finite field. In order to avoid heavy operations, we used the Montgomery trick [START_REF] Montgomery | Speeding the Pollard and Elliptic Curve Methods of Factorization[END_REF], which converts N inversion computations into 1 inversion and 3(N -1) multiplication computations. When the Montgomery trick is used in KKM improvement, only O(log 2 c) inversions are required.

Experimental Results

This section describes our experimental results of Cheon's algorithm for an elliptic curve used in the TinyTate library [START_REF] Oliveira | TinyTate: Identity-Based Encryption for Sensor Networks[END_REF]. We successfully solved DLPwAI by our implementation in a group G with 128-bit order. Strongly note that DLP has been believed to be secure in the same group.

Parameters

We used an addition cyclic group G = G with order r on an elliptic curve y 2 = x 3 + x defined over a prime finite field F p used in the TinyTate library [START_REF] Oliveira | TinyTate: Identity-Based Encryption for Sensor Networks[END_REF] where #E denotes the number of points in E(F p ). In our implementation of Cheon's algorithm, we used the following parameters:

d = 12682136550675316736 (64-bit) = 2 60 • 11 ζ = 5 ζ d = ζ d = 1243133183 1021416944 7902414199 634645036 d 1 = (r -1)/d = 3662760472 (32-bit) d 2 = √ d = 3561198752 (32-bit)
Here, d is chosen to minimize the time complexity of Cheon's algorithm, and it is estimated that our implementation requires about O(2 32.75 ) group operations

Results

In the experiment, our implementation of Cheon's algorithm successfully found the solution α = 3 in about 45 hours and 246 GByte by using a single PC (other environmental information are summarized in Table 2). KKM Improvement In our implementation, the Montgomery trick is used for KKM improvement part. By experimental optimizations, we used parameters n = 2 16 and c = 8. The precomputation requires about 4 seconds, and each scalar multiplication requires about 27 µseconds. About 1.03 mseconds is required for a multiplication without KKM improvement, about 38 times speedup was established. Also, about 54 µseconds is required with KKM improvement but without the Montgomery trick, about 2 times speed-up was established.

Step 1 Two databases DB 1,B and DB 1,G are generated in about 14.5 hours and 82 GByte memory with 4 parallel computations. Then, 1 hour is required to divide these databases into 64 sub-databases DB 1,G required about 2 minutes. In our experiment, we found a collision when ℓ = 39 and obtained u 1 = 2170110422 and v 1 = 846301393. Thus, we found a partial solution

k 1 = u 1 + v 1 d 1 = 3099799291849047918 in about 22.1 hours.
Step 2 Similarly to Step 1, the database generation required about 14.2 hours and 80 GByte. Dividing databases required about 1 hour and 80 × 3 = 240 GByte. Sorting a sub-database required about 7 minutes and searching a collision among sub-databases required about 2 minutes. We found a collision when ℓ = 52 and obtained u 2 = 1609744154 and v 2 = 718704617. Thus, we found a partial solution

k 2 = u 2 + v 2 d 2 = 2559449986726782138 in about 23.2 hours.
Consequently, we successfully obtained

k = k 1 + k 2 (r -

Estimations

Based on our experimental results described in the previous section, we estimate required time (in the worst case) and memory for solving DLPwAI with larger r.

Here, we do not consider the parallel processing. We assume that the parameter d can be chosen as large as √ r, namely, required time in Step 1 and Step 2 are almost same.

Let T C be the required time for generating databases. Since a scalar multiplication is computed in 27 µseconds, T C can be evaluated by Then, let us evaluate the required time T S for the database search. Since the sorting are dominant procedures, we neglect time for other parts. In our implementation, the comb-sort algorithm requires O(log N ) for sorting N elements, and a sort in a sub-database requires 8 minutes for 128-bit r, T S can be evaluated by

T C = 2 × 27 × 10 -6 × 2 4 √ r [Seconds]. (2)
T S = 2 × 64 × (8 × 60) × ( 4 √ r) log ( 4 √ r/64) (2 32 ) log (2 26 ) [Seconds].
On the other hand, the required memory S C can be evaluated by

S C = 12 × 4 √ r × 3 × 2 [Bytes].
By using these evaluations, estimated required time and memory for various sizes of r are summarized in Table 3.

According to Table 3, solving DLPwAI seems to be feasible even if r is 140bit since the required time is about 50 days. However, the required memory is beyond 2 TByte in this case. In the computational environment we used, and in most environments, dealing with such huge memory is too difficult to proceed. Thus, it is concluded that solving DLPwAI with 140-bit r is infeasible by Cheon's algorithm combined with BSGS algorithm. In order to solve such larger problems, Cheon's algorithm combined with the λ-algorithm or the kangaroo algorithm would be employed.

Next, let us compare our results to the previous experiments (summarized in Table 1) when r is 128-bit by the extrapolation. According to the time complexity of Cheon's algorithm, Jao and Yoshida's implementation4 would require 3 × 2 64 /2 30 = 393216 hours (16384 days) and Izu et al.'s implementation would require 14 × 2 64 /2 42 = 28672 hours (1195 days) (Table 4). Even if the parallel computation is applied, solving DLPwAI is infeasible with 128-bit r by these implementations.

Concluding Remarks

This paper succeeded to solve a discrete logarithm problem with auxiliary input (DLPwAI) in 45 hours with a single PC in a group with 128-bit order defined on Table 4. Estimated Time for 128-bit r Estimated Time Jao, Yoshida [START_REF] Jao | Boneh-Boyen Signatures and the Strong Diffie-Hellman Problem[END_REF] 16384 Days Izu et al. [START_REF] Izu | Experimental Results on Cheon's Algorithm[END_REF] 1195 Days This paper 7 Days

an elliptic curve over a prime finite field with 256-bit elements, which are used in TinyTate library for implementing pairing cryptosystem in the embedded devices. If cryptographic schemes based on problems such as ℓ-BDE problem, ℓ-SDH problem, ℓ-sSDH problem or ℓ-BDHI problem are implemented, TinyTate library should avoid using such weak parameters. However, there are pairingbased cryptographic schemes which are not effected by Cheon's algorithm such as Boneh-Franklin's ID-based encryption scheme.

  1)/d. Here, such u 1 , v 1 are uniquely determined. In practice, Step 1 searches u 1 , v 1 such that ζ -u1 d G d = ζ v1d1 d G. Then, Step 2 searches an integer k 2 such that α = ζ k1 ζ k2 e for ζ e = ζ (r-1)/d in the similar way, or equivalently, searches integers u 2 , v 2 such that αζ -k1 ζ -u2 e = ζ v2d2 e satisfying 0 ≤ u 2 , v 2 < √ d (where G e = ζ -k1 G). Here, such u 2 , v 2 are uniquely determined. In practice, Step 2 searches u 2 , v 2 such that ζ -u2 e G 1 = ζ v2d2 e

  successively and store them in another database. Then, we search a collision G 1 -iG = jG ′ among these databases and thus a solution α = i + jm is obtained. Since O(m) group operations and O(m) group elements are required in both steps, the time and space complexity of BSGS are O( √ r) group operations and O( √ r) group elements, respectively.

  and searches a collision satisfying ζ -u1 d G d = ζ v1d1 d G among these databases. Thus, Step 1 in Cheon's algorithm combined with BSGS algorithm requires 2d 1 = 2 (r -1)/d elements in space. Similarly, Step 2 requires 2d 2 elements in space. KKM Improvement Cheon's algorithm requires the number of scalar multiplications for fixed elements G, G 1 and G d . In 2007, Kozaki, Kutsuma and Matsuo introduced a precomputation table for such multiplications and reduced the time complexity of Cheon's algorithm from O log r (r -1)/d + √ d to O (r -1)/d + √ d .

d 2 1 d

 1 G} should be established. In our implementation, an element ζ -i d G d in the database DB 1,B is expressed by the following 12-byte representation i 4-byte

  . To do so, pick up an element ζ jd1 d G from the sub-database DB (ℓ) 1,B and check whether the same element is in DB (ℓ) 1,G by the binary search algorithm.

2

 2 which was developed by Oliveria et al. for implementing the pairing-based cryptosystem in the embedded devices. Concrete values of these parameters are summarized in the following: p = 0x5387a1b6 93d85f28 8f131dd5 e7f9305c f4436019 a00f3181 168d7b20 8934d073 (256-bit) = • 3 2 • 1227703 • 5024295160706223327986689772851 • r r = 0x80000040 00000000 00000000 00000001 (128-bit) = 1701411885 3107163264 4604909702 696927233 r -1 = 0x80000040 00000000 00000000 00000000 (128-bit) = 2 102 • 3 • 11 • 251 • 4051

  and elements for solving DLPwAI. The generator ζ is chosen as the minimum generator of the multiplicative group (Z/rZ) * .A base point G is randomly chosen from points in E(F p ) with order r. Then, coordinate values of G, G 1 = αG, G d = α d G for our solution α = 3 are as follows:

  (0 ≤ ℓ ≤ 63). Since the parent databases DB 1,B and DB 1,G , and their cache are stored in this divisions, 82 × 3 = 246 GByte are required.Sorting a sub-database DB

  α = ζ k mod r = 3 in about 45.3 hours and 246 GByte memory.

  Thus, the databases DB 1,B and DB 1,G requires 12d 1 bytes, respectively.

	1,G , an element ζ jd1 d G is expressed by the following 12-byte representation
	j	|| LSB 64 (MD5(x(ζ jd1 d G)||y(ζ jd1 d G)))	.
	4-byte	8-byte
	Database Search Then, in step 1 of Cheon's algorithm, it is needed to find two integers u 1 , v 1 satisfying ζ -u1 d G d = ζ v1d1 G among the databases DB 1,B and d DB 1,G . Since a straight-forward search (namely, compare all ζ -i d G d in DB 1,B and ζ jd1 d G in DB 1,G

Table 2 .

 2 Computational Environment

	CPU Intel(R) Core TM i7 2.93 GHz
	OS	Ubuntu 10.04
	Compiler	gcc 4.2.2
	Library	GNU MP 4.1.2 [9]

Table 3 .

 3 Cost Estimations

	r	TC	TS	T = TC + TS	SC
	128 bit 6 Days 17 Hours	7 Days	288 GByte
	132 bit 11 Days 35 Hours 13 Days	576 GByte
	136 bit 22 Days 74 Hours 25 Days 1152 GByte
	140 bit 45 Days 6 Days	51 Days 2304 GByte

There are many possible variations of DLPwAI. However, this paper only deals with this type.

Note that Jao-Yoshida's result was not dedicated to an efficient implementation.

Acknowledgements

The authors would like to thank Yoshitaka Morikawa and Yasuyuki Nogami in Okayama University for their supports on this research.


Zheng Gong

Marc X Makkes
email: m.x.makkes@kr85.org

P Uf

Hardware Trojan Side-Channels Based on Physical Unclonable Functions

The separation design and fabrication process in the semiconductor industry leads to potential threats such as trojan side-channels (TSCs). In this paper we design a new family of TSCs from physical unclonable functions (PUFs). In particular, a dedicated attack on the PRESENT block cipher is described by using our PUF-based TSCs. Finally we analyze the performance of our PUF-based TSCs and discuss other potential applications.

Introduction

With the rapid developments of semiconductor technology, integrated circuits (ICs) are fast becoming an overwhelming presence in our daily lives. Since information security attracts more and more concerns, security chips are widely used to provide hardware support of cryptographic algorithms and obtain trust computing bases. In most cases, it becomes theoretically infeasible to directly attack a well-analyzed cryptographic algorithm (e.g., AES) within a security chip by using traditional cryptanalysis. Although a security chip can resist the attacks at the algorithm level, the weaknesses in the implementation level might be analyzed for practical attacks. For instance, the side-channel information, such as differential time or power analysis, is widely investigated to break the security protection of embedded systems [START_REF] Paar | Keeloq and sidechannel analysis-evolution of an attack[END_REF][START_REF] Popp | Practical attacks on masked hardware[END_REF].

The original ideas of trojan side channel attacks and covert channels were first proposed by Simmons [START_REF] Simmons | The prisoners' problem and the subliminal channel[END_REF]. As an aggressive example of side-channel attacks, Lin et al. [START_REF] Lin | Trojan side-channels: Lightweight hardware trojans through side-channel engineering[END_REF] introduced the concept of trojan side channels (TSCs). A TSC can be viewed as a malicious circuit that can compromise information from an embedded crypto core, afterwards it can send out the information via side-channel signals. Only the attacker who implements the TSC can decode the information. Although TSCs require extra hardware costs, it is hard to detect since they usually occupy a negligible amount of area in the genuine IC. The current IC supply chain, such as outsourced manufacturing, also provides great opportunities to implant malicious circuits into the genuine IC to compromise their security. Nevertheless, many governments and agencies require that companies who use encrypted communications systems (e.g., mail services from Blackberry) to allow these institutions to recover encrypted information with a feasible effort. Normally this requirement leads to two options for vendors: either choose key escrow or weak design of cryptography. Implementing TSCs can match this requirement without relying on the above options.

On the other side, detecting flaws in the lithography process is usually done with extra hardware supports and it is often used to check if the functionality is correct. Verification of the functionality is often with some extra hardware attached to the IC. Recent developments showed that it is possible for an attacker to modify chip designs and add malicious circuits without changing the functionality. In the literature, many approaches have been proposed for trojan hardware detection, such as visual inspections, test patterns to find unexpected behavior, side-channel and path delay profiles [START_REF] Chakraborty | Mero: A statistical approach for hardware trojan detection[END_REF]. Currently, it is still infeasible to detect a large amount of security chips whether they have been affected by a trojan hardware with very small gate counts. In order to keep the TSC undetectable, it is also crucial to blind the side-channel information for other parties except the original attacker. In [START_REF] Lin | Trojan side-channels: Lightweight hardware trojans through side-channel engineering[END_REF], Lin et al. suggest to use a LFSR for encoding. This results a practical problem that every chip implemented with the same LFSR will output the same stream. Therefore, if anyone resolves the polynomial that constructs the LFSR, it will be straightforward to decode the information from every TSC based on this LFSR.

In 2001, Pappu et al. [START_REF] Pappu | Physical One-Way Functions[END_REF] introduced the concept of physical unclonable functions (PUFs, also known as physical random functions). Since it is practically impossible to model, copy, or control the IC manufacturing process variations, PUFs can make chips unique and effectively unclonable. In this paper we propose a new familty of TSCs based on PUFs. The advantages of using a PUF-based TSC are two-fold: 1) for every TSC, it is unnecessary to be implemented with different LFSRs (or keys) but a PUF with the same circuits to blind its side-channel information. The one-wayness of the PUF protects the side-channel information can only be decoded by the attacker who implemented the TSC. 2) An attacker can trace the side-channel information from a certain chip by using the physical unclonable property of PUFs. It also means mathematically modeling one chip for recovery will be useless to other chips. We propose a PUF-based TSC attack on the PRESENT block cipher to show the relatively negligible hardware implementation cost compared to genuine ICs.

The remainder of the paper is organized as follows: Section 2 reviews the preliminaries for TSCs and PUFs, Section 3 first describes a generalized model for PUF-based TSC attacks, after which propose a PUF-based TSC attack on the PRESENT block cipher, Section 4 discusses other applications of PUF-based TSCs, and Section 5 concludes the paper.

Preliminaries

The Trojan Side-Channel Model

It is widely accepted that a well-defined model must be formalized on the system that requires analysis. In [START_REF] Lin | Trojan side-channels: Lightweight hardware trojans through side-channel engineering[END_REF], Lin et al. introduces the parties and activities that are involved with the Trojan Side-Channel (TSC) model. Here we will refine the TSC model from a more general perspective of the TSC scenario.

Entities & Activities. A TSC can be used either by a malicious attacker or by an anti-counterfeiting analyzer. Without loss of generality, we call the party who implants the Trojan hardware into the circuits tracer T , and the party who attempts to detect those TSCs evaluator E. For malicious applications, T will try to hide the usage of TSCs, while E will try to verify the correctness and integrity of circuits. For anti-counterfeiting usages, T will try to expose the sidechannel information of TSCs, while E will try to discover and hinder the leakage by TSCs. Except for the implanted TSCs, we assume that the genuine ICs are tamper-resistant and no other side-channels can be found by T . E can extensively test the functionality of the genuine ICs and capture the signals leaked out by TSCs.

Requirements. To evaluate its implementation quality, a TSC must obey the following conditions.

-Circuit properties:

• Imperceptibility. Compared to the genuine IC, a TSC must only increase a negligible area of logic gates to reduce the possibility of detections by evaluators. • Conformity. A TSC must not affect the correctness and integrity of the genuine ICs. Moreover, the timing properties of the genuine ICs (e.g., cycles for an encryption/decryption) will not be affected overtly by an implanted TSC. -Signal properties:

• Blindness. Except for tracers who implanted the TSC, side-channel information leaked out by a TSC must be blind to other parties. That is to say, evaluators cannot distinguish the difference between information leaked out by TSCs and bits from a pseudorandom number generator. • Latency. To avoid the detection, a TSC will be latent unless it is triggered with a certain condition predefined by tracers. The trigger must be imperceptible from extensive functionality testing of the genuine ICs.

Physical Unclonable Functions

It is known that PUFs exploit the physical characteristics of the silicon and the IC manufacturing process variations to uniquely characterize each and every silicon chip. The unclonability property comes from the fact that a PUF consists of a finite number of random components, which is infeasible to exactly control over the manufacturing process. Each PUF uses these random components to map challenges to responses (CRPs). A challenge is a stimulus that is applied to the PUF and a response is the reaction of the PUF obtained through measurements. Due to the complex interaction of the stimulus with the physical microstructure of the device, each PUF will trigger a response that is highly unpredictable and unique. PUFs are often used to setup secure channels between devices. At the manufacturing process the manufacturer creates a set of CRPs with a PUF and hands them over to user. Therefore, a user can set a secure channel using the CRP by sending a challenge C to the PUF. Since the response R of the PUF is also known to the user, it can be used as a shared secret key for secure communication.

In the literature, many types of PUFs have been proposed based on different physical properties. By using the position of light as the challenge, Pappu et al. [START_REF] Pappu | Physical One-Way Functions[END_REF] proposed a PUF based on the scattering of light when shining a laser on a bubble-filled transparent epoxy wafer. In [START_REF] Lim | Extracting secret keys from integrated circuits[END_REF], Lim et al. introduced a new family of PUFs based on arbiters (APUF). An APUF consists of two identically configured delay paths that includes a number of switches. The switches are set by the stimulus and determine a unique path that signals have to travel. In order to generate response bits for an APUF, a signal is activated simultaneously on both delay paths. At the end of the delay paths there is an edge triggered flip-flop which determines the fastest signal by outputting a signal bit.

PUF-based TSC Attacks

A Paradigm on PRESENT

The key objective of a TSC is to compromise key information from a crypto engine without altering or delaying the process of the genuine IC. Altering or delaying might reveal the existence of the TSC to evaluators. When a tracer T exploited the side-channel information, T will first decode the information to the original message. By retrieving the saved CRPs of the implanted PUFs, T can identify which IC leaked out the side-channel information, and then recover the compromised key information. In [START_REF] Lin | Trojan side-channels: Lightweight hardware trojans through side-channel engineering[END_REF], Lin et al. adapted the concepts from spreads-spectrum communications (also known as code-division multiple access (CDMA)) to distribute the compromised bits as a covert channel to T . For simplicity, we also choose it as the leakage circuit for PUF-based TSCs. Figure 1 depicts a generalized model for PUF-based TSC attacks.

Since TSCs also require signal blindness, traditional PUFs are not resourceefficient for ensuring the randomness of long length CRPs. Here we propose a new variant of PUF which is suitable for TSCs. Basically, our design (see Figure 2) is constructed from a combination of a feedback shift register (FSR) and a number of APUFs. The FSR can store a bit string with the length C and shift P bits in every cycle. Each APUF consists of C switch elements, and the number of APUFs is P . The FSR provides each APUF with an identical challenge, as the output of the APUFs is inserted back in the FSR and is sent out over the Initially, the FSR is loaded with a unique identifier (ID). To prevent the detection caused by the power usage, the PUF-based TSC processes and transmits key information (Key) at the same time as encryption occurs. In order to transmit the side-channel information, we suggest the following format for the covert channel.

PUF(ID)||PUF(Key)|| • • • PUF(ID)||PUF(Key) • • •

Using this format T can first decode the signal and retrieve the PUF(ID) which can be looked up in the list of devices. Afterwards, T can decode the PUF(Key) because the CRPs of each APUF are stored (to a database) beforehand. The length of an APUF (i.e., the number of switches) determines the storage requirement per device.

For a PUF-based TSC, the security and performance of a given structure determine its area costs. The first parameter is the length of the APUF which regulates the security of the structure. The second parameter is the number of APUFs which determine the performance of a PUF-based TSC by clock cycles. The gate equivalents (GE) of the PUF-based TSC also relies on the implementation of the cryptosystem. In [START_REF] Ozturk | Physical unclonable function with tristate buffers[END_REF], Ozturk et al. showed that a PUF with a 64-bit challenge and a single bit response using a tri-state APUF can be implemented in 351 gates. We will consider smaller challenges in our PUF-based TSCs for the imperceptibility.

PRESENT. At CHES 2007, Bogdanov et al. proposed an ultra-lightweight block cipher which is named PRESENT [START_REF] Bogdanov | Present: An ultra-lightweight block cipher[END_REF]. PRESENT is an example of an SPnetwork and consists of 31 rounds. The block length is 64 bits and two key lengths of 80 and 128 bits are supported. The hardware requirements for PRESENT are competitive. Using the Virtual Silicon (VST) standard cell library based on UMC L180 0.18µm 1P6M Logic Process (UMCL18G212T3), PRESENT-80 and PRESENT-128 are estimated to require 1570 and 1886 gate equivalents, respectively [START_REF] Bogdanov | Present: An ultra-lightweight block cipher[END_REF]. Since Bogdanov et al. do not expect the 128-bit key version to be used until a rigorous analysis is given, the term PRESENT means the 80-bit key version in hereafter. A high-level algorithm of the round function of PRESENT is depicted in Figure 3.

generateRoundKeys(k) → {k1, k2, • • • , k32}; for i = 1 to 31do
addRoundKey(STATE, ki); sBoxLayer(STATE); pLayer(STATE); end for addRoundKey(STATE, k32).

Fig. 3. The round function of PRESENT

The key schedule. PRESENT uses a hardware-efficient key schedule to avoid the scheduling weaknesses, which may be used for the related-key attack and the slide attack. The user-supplied key is stored in a key register K and represented as k 79 k 78 • • • k 0 . At the i-th round, the leftmost 64-bit of the current key register becomes the subkey K i = k 79 k 78 • • • k 16 . Subsequently, the key register K is updated as follows.

-Cycling left shift 61 bits such that [ Based on the key schedule of PRESENT, we can design a lightweight TSC as follows. For each round, TSC will try to leak out the rightmost 4 bits of K. Since the key register is cycling left shift 61 bits, the rightmost 4 bits will not repeat themselves within 21 rounds (as illustrated in Figure 4). Thus we can obtain the whole key bits after 21 rounds of PRESENT. Since only the leftmost 64 bits in the key register will be used in the addRoundKey algorithm, compromising the rightmost 4 bits will not imply any unexpected behavior or path delay on PRESENT.

k 79 k 78 • • • k 0 ] = [k 18 k 17 • • • k 20 k 19 ], -
Round 1 : k79k78k77k76 • • • k3k2k1k0 Round 2 : k18k17k16k15 • • • k22k21k20k19 Round 3 : k37k36k35k34 • • • k41k40k39k38 Round 4 : k56k55k54k53 • • • k60k59k58k57 • • • Round 11 : k29k28k27k26 • • • k33k32k31k30 • • • Round 21 : k59k58k57k56 • • • k63k62k61k60 Fig. 4. Key Scheduling of PRESENT
Instead of recovering a full-length key, a parameterized approach can be used to lower the length of sending bits via side channels. Similar to the above attack on PRESENT, one can carefully choose a combination of key bits and rounds for a TSC. For instance, we can make a TSC that leaks 4 bits in each round and stops after 11 rounds. After 11 rounds of PRESENT, we can obtain 40 bits of the original key and execute an exhaustive search for the rest of 40 bits key. The exhaustive search only requires a time complexity of about O(2 40 ), which can be executed in minutes on current PCs. Consequently, a PUF-based TSC attack on PRESENT can be implemented as follows.

1. Send a pre-distributed identifier ID as the challenge to the PUF, obtain the response r 1 = PUF(ID). 2. Eavesdrop each of the rightmost 4 bits of 11 rounds subkeys from the underlying PRESENT encryption/decryption. Input the compromised bits C to PUF, obtain the response r 2 = PUF(C). 3. Encode the complete message R = r 1 ||r 2 , which will be sent by the covert channel.

Although the key scheduling algorithm of PRESENT has no security problems so far under cryptanalysis, our proposed attack endangers its security in practical implementations. We note that the above attack on PRESENT can also be extended to other ciphers designed with a "simple" key scheduling algorithm.

If a key scheduling algorithm has a low non-linear complexity (i.e., mainly relies on linear operations such as bit shifts), a TSC attacker can easily recover the entire secret key by eavesdropping a few bits of the subkey in each round. If TSC attacks are considered in the adversary model, the non-linearity of the key schedule should be carefully strengthened by algorithm designers.

Performance Analysis

To estimate the lower-bound GE of our PUF-based TSC, we take the formula P • (5 • C + 4) + 4 • C) where C is the length of the challenge and P is the number of the APUFs. Our lower-bound GE estimation is based on the implementation of PUF-based TSC in Xilinx ISE Design Suite 12.2. If we consider a 24-bit challenge for the PRESENT implementation where 4 key bits are snooped per cycle, the lower-bound of GE of the PUF-based TSC can be 592 gates. It is possible to lower the GE by lowering the number of APUFs. Table 1 gives an overview of the performance of implementations that are derived from different parameters of the PUF-based TSC. The results start with a low-area and lowperformance implementation (serial PUF-based TSC), to a high-area and high performance implementation (TSC with 4 APUFs). It is obvious from the results that performance comes at a cost in area and storage while the length of APUF only significantly results in storage requirements.

Evaluation

The Imperceptibility of a PUF-based TSC heavily depends on the size of the genuine chip. If a chip only contains gates nearly or below a thousand level, the TSC can be easily spotted. Our proposed TSC requires 592 gates, where as PRESENT requires 1570-1886 gates. This is almost 30-40% of the area of the attacked cipher. In [START_REF] Agrawal | Trojan detection using IC fingerprinting[END_REF], Agrawal et al. comments the that hardware trojans are detectable if the size of the trojan is more than 0.01% of the floorplan. But if a chip has thousands of gates, or a million chips need to be examined, spotting the TSC becomes increasingly difficult. Moreover, we recognize that it is a possible and clever way to hide this type of TSC in a protection mesh, such as in smartcards. In [START_REF] Rührmair | Modeling attacks on physical unclonable functions[END_REF] Ruhrmair et al. presented a modeling attack on PUFs by using linear regression to a mapping a large amount of challenges to responses and deriving a model of the PUF. But in our PUF-based TSC attacks, the challenge for the PUF is derived form the round key. For an attacker to construct an key such that specific bits are set in the round key, it is infeasible to build a modeling attack on such CRPs of a PUF. Besides that PUFs are well known and easily implementable in FPGAs [START_REF] Merli | Improving the quality of ring oscillator pufs on fpgas[END_REF][START_REF] Morozov | An analysis of delay based puf implementations on fpga[END_REF], Devadas et al. showed in [START_REF] Devadas | Design and implementation of PUF-based unclonableRFID ICs for anti-counterfeiting and security applications[END_REF] how PUFs can be practically implemented in ASICs. Since our PUF-based TSC heavily relies on the implementation of PUFs, it can also be feasibly implemented even on a large scale. Although its feasibility and imperceptibility still require deeper investigation, our PUF-based TSC has many advantage over the TSC presented by Lin et al. [START_REF] Lin | Trojan side-channels: Lightweight hardware trojans through side-channel engineering[END_REF]. Firstly, our PUF-based TSC can provide unpredictable outputs that are related to physical unclonability, which increases the blindness and the uniqueness of side-channel information. Secondly, PUF-based TSCs can be parameterized by the consideration of performance and resource limitations. This gives a high level of adaptability as shown with the attack on PRESENT. Note that our PUF-based TSC attack on PRESENT can be extended for other block ciphers with a similar bit-shifting key schedule.

Although Lin et al. [START_REF] Lin | Trojan side-channels: Lightweight hardware trojans through side-channel engineering[END_REF] have not described how to activate the TSC in their proposal, here we provide a possible design for triggering the PUF-based TSC. Since PRESENT has a round counter for 31 rounds key schedule, while our proposed attack only requires the leakage bits of 11 rounds, a possible trigger can start the PUF-based TSC between 0 ≤ i < 20 where i is the round counter. The number i is variable and can be selected attacker at the manufacturing stage. This trigger requires some additional administration (i.e., 4 bits per PUF-based TSC) as the attacker needs to know which key bits of which round are sent.

Other Applications

Except direct attacks on key recovery, PUF-based TSCs can be used in many other applications. Two interesting examples are described as follows.

Personal communication eavesdropping. Nowadays, mobile devices are widely secured with cryptographic algorithms. If a PUF-based TSC is implanted to a certain user's device, a tracer can not only eavesdrop side-channel information, but can also identify such signals sent from a certain device that belongs to a certain user.

Parameterized backdoor. Some countries have restrictive regulations on the exporting of security chips, which impose that only chips lower than a certain security level can be shipped. Our parameterized TSC on PRESENT shows it can also be used as a factor to lower the security level of a tamper-resistant chip and therefore matches those exporting limitations.

In this paper we introduced a new type of flexible TSC based on PUFs. A dedicated PUF-based TSC has been proposed for attacking PRESENT. Compared to Lin et al.'s original proposal, our PUF-based TSCs cleverly uses the physical unclonability to obtain the blindness of side-channel information. The implementation results support that PUF-based TSCs can also be lightweight in logic gates, which is an important factor for the imperceptibility of TSC circuits. In future, we are interested in designing PUF-based TSCs on other cryptographic primitives that are practically used in security chips.

Fig. 1 .Fig. 2 .

 12 Fig. 1. PUF-based TSC attacks.

  The leftmost 4 bits are passed through the PRESENT S-box such that [k 79 k 78 k 77 k 76 ] = S[k 79 k 78 k 77 k 76 ], -The round counter value is XORed with bits k 19 k 18 k 17 k 16 k 15 .

Table 1 .

 1 The performance our PUF-based TSCs

		TSC width (bit)	FSR length (bit)	CRPs storage Performance in cycles Area in GE
	Serial PUF-based TSC	1	24	16MB	68	220
	TSC with 2 APUFs	2	24	32MB	34	344
	TSC with 4 APUFs	4	24	64MB	17	592
	Serial PUF-based TSC	1	36	420MB	80	328
	TSC with 2 APUFs	2	36	840MB	40	512
	TSC with 4 APUFs	4	36	1.68GB	20	880

Acknowledgement. We would like to thank many anonymous reviewers for their valuable comments. The first author is supported by NSFC (No.6170217), National "863" Program of China (No. 2009AA01Z418) and National "973" Program of China (No.2007CB311201).


Michael Tunstall
email: tunstall@cs.bris.ac.uk

Debdeep Mukhopadhyay
email: debdeep@cse.iitkgp.ernet.in

Subidh Ali
email: subidh@cse.iitkgp.ernet.in

Differential Fault Analysis of the Advanced Encryption Standard using a Single Fault

Keywords: Differential Fault Analysis, Fault Attack, Advanced Encryption Standard

In this paper we present a differential fault attack that can be applied to the AES using a single fault. We demonstrate that when a single random byte fault is induced at the input of the eighth round, the AES key can be deduced using a two stage algorithm. The first step has a statistical expectation of reducing the possible key hypotheses to 2 32 , and the second step to a mere 2 8 .

Introduction

The Advanced Encryption Standard (AES) [START_REF]Advanced Encryption Standard (AES)[END_REF] has been a de-facto standard for symmetric key cryptography since October 2000. Smart cards and secure microprocessors, therefore, typically include implementations of AES to protect the confidentiality and the integrity of sensitive information. To satisfy the high throughput requirements of such applications, these implementations are typically VLSI devices (crypto-accelerators) or highly optimized software routines (crypto-libraries).

Several applications of DFA to AES have been reported in the literature. In [START_REF] Giraud | DFA on AES[END_REF], authors describe an analysis based on faults induced in one byte of the ninth round of AES that requires 250 faulty ciphertexts. An attack reported in [START_REF] Blömer | Fault based cryptanalysis of the advanced encryption standard (AES)[END_REF] allows an attacker to recover the secret key with around 128 to 256 faulty ciphertexts. In [START_REF] Dusart | Differential fault analysis on A[END_REF], Dusart et al. show that using a fault which affects one byte anywhere between the eighth round MixColumn and ninth round MixColumn, an attacker would be able to derive the secret key using 40 faulty ciphertexts. The authors of [START_REF] Piret | A differential fault attack technique against SPN structure, with application to the AES and KHAZAD[END_REF] describe an attack on AES with single byte faults that requires two faulty outputs, where a fault is induced in the input of the eighth or ninth round, extended to one 32-bit fault in the ninth round in [START_REF] Moradi | A generalized method of differential fault attack against AES cryptosystem[END_REF].

We can note that when the assumptions are on the value of a byte (either it being faulty or uncorrupted) the number of faulty pairs is quite small. However, it is difficult to be able to affect a given value with any certainty. When numerous faulty ciphertexts are required this problem is amplified, since an attacker needs to find a method of determining which faulty ciphertexts correspond to the desired model. We can, therefore, state that the attacks that are most likely to be realizable require the least faulty ciphertexts and assumptions on the effect of the fault.

In [START_REF] Mukhopadhyay | An improved fault based attack of the advanced encryption standard[END_REF] a fault attack against AES was proposed, which suggested that a secret key can be derived using a single byte fault induction at the input of the eighth round. The attack exploited the inter-relations between the fault values in the state matrix after the ninth round MixColumn operation and reduced the number of possible keys to around 2 32 . However it may be noted that this work, like the previous fault attacks on AES does not use the effect of the fault maximally in an information theoretic sense [START_REF] Li | An information theoretic perspective on the differential fault analysis against aes[END_REF]. The work proposed in this paper improves the previous fault analysis on AES-128 and reduces the key space to its minimal possible set of hypotheses attainable using a single byte fault. In this paper, we describe the extended version of this attack, where an attacker could reduce the exhaustive search to 2 8 .

Notation

In this paper, multiplications are considered to be polynomial multiplications over F 2 8 modulo the irreducible polynomial x 8 + x 4 + x 3 + x + 1. It should be clear from the context when a mathematical expression contains integer multiplication.

Organization

The paper is organized as follows: In Section 2 we describe the background to this paper. In Section 3 we describe an attack based on one of the fault models given in Section 2. In Section 3 we extend this attack. In Section 4 we compare this paper to work described in the literature, and we conclude in Section 5.

Background

The Advanced Encryption Standard

The structure of the Advanced Encryption Standard (AES) , as used to perform encryption, is illustrated in Algorithm 1. Note that we restrict ourselves to considering AES-128 and that the description above omits a permutation typically used to convert the plaintext P = (p 1 , p 2 , . . . , p 16 ) (256) and key K = (k 1 , k 2 , . . . , k 16 ) (256) into a 4 × 4 array of bytes, known as the state matrix. For example, the 128-bit plaintext input block P which produces fault free (CT ) and faulty ciphertexts (CT ′ ) are arranged in the following fashion Algorithm 1: The AES-128 encryption function.

Input: The 128-bit plaintext block P and key K. Output: The 128-bit ciphertext block C. X ← AddRoundKey(P, K)

for i ← 1 to 10 do X ← SubBytes(X) X ← ShiftRows(X) if i = 10 then X ← MixColumns(X) end K ← KeySchedule(K) X ← AddRoundKey(X, K) end C ← X return C P =     p1 p5 p9 p13 p2 p6 p10 p14 p3 p7 p11 p15 p4 p8 p12 p16     CT =     x1 x5 x9 x13 x2 x6 x10 x14 x3 x7 x11 x15 x4 x8 x12 x16     CT ′ =     x ′ 1 x ′ 5 x ′ 9 x ′ 13 x ′ 2 x ′ 6 x ′ 10 x ′ 14 x ′ 3 x ′ 7 x ′ 11 x ′ 15 x ′ 4 x ′ 8 x ′ 12 x ′ 16    
where xi ∈ {0, . . . , 255} ∀i ∈ {1, . . . , 16}. We also define the key matrix for the subkeys used in the ninth and tenth round as K10 = {k1, . . . , k16} and K9 = {k ′ 1 , . . . , k ′ 16 } that are arranged in a state matrix as described above.

The encryption itself is conducted by the repeated use of a number of round functions:

-The SubBytes function is the only non-linear step of the block cipher. It is a bricklayer permutation consisting of an S-box applied to the bytes of the state. Each byte of the state matrix is replaced by its multiplicative inverse, followed by an affine mapping. Thus the input byte x is related to the output y of the S-Box by the relation, y = A x -1 + B, where A and B are constant matrices. In the remainder of this paper we will refer to the function S as the SubBytes function and S -1 as the inverse of the SubBytes function. -The ShiftRows function is a byte-wise permutation of the state.

-The KeySchedule function generates the next round key from the previous one.

The first round key is the input key with no changes, subsequent round keys are generated using the SubBytes function and XOR operations. This is shown in Algorithm 2 which shows how the r th round key is computed from the (r -1) th round key. The value hr is a constant defined for the r th round, and << is used to denote a bitwise left shift. -The MixColumn is a bricklayer permutation operating on the state column by column. Each column of the state matrix is considered as a 4-dimensional vector where each element belongs to F(2 8 ). A 4×4 matrix M whose elements are also in F(2 8 ) is used to map this column into a new vector. This operation is applied on all the 4 columns of the state matrix. Here M and its inverse M -1 are defined as: Algorithm 2: The AES-128 KeySchedule function.

M =     2 3 1 1 1 2 3 1 1 1 2 3 3 1 1 2     M -1 =     14
Input: (r -1) th round key (X = xi for i ∈ {1, . . . , 16}).

Output: r th round key X.

for i ← 0 to 3 do x (i<<2)+1 ← x (i<<2)+1 ⊕ S(x (((i+1)∧3)<<2)+4 ) end x1 ← x1 ⊕ hr for i ← 1 to 16 do if (i -1) mod 4 = 0 then xi ← xi ⊕ xi-1 end end return X

The Fault Model

The implementation of AES we target is an iterative one, i.e. where a round function is executed in a loop as described in Algorithm 1. An attacker can typically predict at what point in time certain events take place, e.g. when a particular round commences. Moreover, the time certain events take can often be determined by analyzing a suitable side channel.

The fault model that we consider is the same as that used in many other papers, for example [START_REF] Mukhopadhyay | An improved fault based attack of the advanced encryption standard[END_REF], where we assume that the effect of an induced fault is to change one byte to a random value.

For example, an attacker could attempt to use a glitch in the clock to create a fault at the input of a particular round with a certain probability. An iterative design helps in this regard, as the attacker is able to control the timing of fault induction by simply counting the number of clock edges from the start of an encryption.

The Fault Analysis

The First Step of the Fault Attack

If a fault is induced in a byte of the state matrix, which is then input to the eighth round, the MixColumn operation at the end of the round propagates this fault to the entire column of the state. The ShiftRow operation at the beginning of the following round will then shift these bytes to occupy different columns. The next MixColumn operation will then propagate the fault to the remaining twelve bytes.

This process is shown in Figure 1 where we show the diffusion of a byte fault induced at the input of the eighth round. The XOR difference of the state matrices of the two results, one fault free and the other faulty, is shown. This is what we use as basis for a differential fault analysis.

A 1 A 2 A 3 A 4 A 5 A 6 A 7 A 8 A 9 A 10 A 11 A 12 A 13 A 14 A 15 A 16 A 1 A 2 A 3 A 4 A 6 A 7 A 8 A 5 A 10 A 9 A 11 A 12 A 13 A 14 A 15 A 16 1 F F 4 F 2 F 3 Round Shift Row Eighth F 3 F 3 F 1 1 2F F 1 3 F 4 F 4 F 1 F 4 3 4 F 2 F 2 F 3 2 F 3 2 F 3 3 F 2 2 F 2 F 1 F 4 F 3 F 2 2f' f' f' 3f' Round Mix Column Eighth Round Byte Sub f' f Eighth Ninth Round Byte Sub Tenth Round Byte Sub Tenth Round Shift Row Ninth Round Mix Column Ninth Round Shift Row f'
Fig. 1: Propagation of Fault Induced in the input of eighth round of AES.

If, given a fault in the input to the eighth round, we consider the state of the differences after the ninth round shift row, we can obtain the following set of equations that include the values of the key bytes k1, k8, k11 and k14, thus giving an expression for 32 bits of K10.

2 δ1 = S -1 (x1 ⊕ k1) ⊕ S -1 (x ′ 1 ⊕ k1) δ1 = S -1 (x14 ⊕ k14) ⊕ S -1 (x ′ 14 ⊕ k14) δ1 = S -1 (x11 ⊕ k11) ⊕ S -1 (x ′ 11 ⊕ k11) 3 δ1 = S -1 (x8 ⊕ k8) ⊕ S -1 (x ′ 8 ⊕ k8) ,
Where δ1, k1, k8, k11 and k14 are all unknown values ∈ {0, . . . , 255}.

The above system of equations can be used to reduce the possibilities for these 32 bits of the key. An attacker would select a value for δ1 and determine which values of k1, k8, k11 and k14 satisfy the equations using four independent exhaustive searches. Each equation will return 0, 2, or 4 hypotheses [START_REF] Nyberg | Differentially uniform mappings for cryptography[END_REF]. If any of the four equations cannot be satisfied, i.e. there is an impossible differential [START_REF] Knudsen | Deal -a 128-bit block cipher[END_REF], then any hypotheses for that value of δ1 can be discarded.

As noted in [START_REF] Giraud | Piret and Quisquater's DFA on AES revisited[END_REF][START_REF] Moradi | A generalized method of differential fault attack against AES cryptosystem[END_REF] one can apply the same technique to recover information on the remaining bytes of the last sub key. That is, information on the remaining key bytes can be derived by using the following sets of equations: In order to obtain information on k2, k5, k12 and k15 an attacker can use

3 δ2 = S -1 (x5 ⊕ k5) ⊕ S -1 (x ′ 5 ⊕ k5) 2 δ2 = S -1 (x2 ⊕ k2) ⊕ S -1 (x ′ 2 ⊕ k2) δ2 = S -1 (x15 ⊕ k15) ⊕ S -1 (x ′ 15 ⊕ k15) δ2 = S -1 (x12 ⊕ k12) ⊕ S -1 (x ′ 12 ⊕ k12)
.

In order to obtain information on k3, k6, k9 and k16 an attacker can use the following equations:

δ3 = S -1 (x9 ⊕ k9) ⊕ S -1 (x ′ 9 ⊕ k9) 3 δ3 = S -1 (x6 ⊕ k6) ⊕ S -1 (x ′ 6 ⊕ k6) 2 δ3 = S -1 (x3 ⊕ k3) ⊕ S -1 (x ′ 3 ⊕ k3) δ3 = S -1 (x16 ⊕ k16) ⊕ S -1 (x ′
16 ⊕ k16) Finally, in order to obtain information on k4, k7, k10 and k13 an attacker can use the following equations:

δ4 = S -1 (x13 ⊕ k13) ⊕ S -1 (x ′ 13 ⊕ k13) δ4 = S -1 (x10 ⊕ k10) ⊕ S -1 (x ′ 10 ⊕ k10) 3 δ4 = S -1 (x7 ⊕ k7) ⊕ S -1 (x ′ 7 ⊕ k7) 2 δ4 = S -1 (x4 ⊕ k4) ⊕ S -1 (x ′ 4 ⊕ k4)
It can be noted that the equations have an identical structure, and, therefore, the solutions are of similar nature. An evaluation of each set of equations will be expected to return 2 8 unique hypotheses for the key bytes concerned. Therefore, an attacker would expect to have 2 32 key hypotheses for the secret key used.

Analysis of the first step of the fault attack

The first step of the fault attack uses four sets of equations to reduce the key space of AES. In this section we determine the expected number of key hypotheses that an attacker will have at each stage of an attack.

In order to analyze the number of valid hypotheses in the first stage of the attack we consider the first set of equations given in Section 3.1. In this set of equations δ1 is ∈ {1, . . . , 255}. If δ1 is equal to zero then one could say that the expected fault has not been injected. If δ1 is zero it would imply that x1 is equal to x ′ 1 and all 256 key hypotheses are possible. Let us first consider the first equation in this set:

2 δ1 = S -1 (x1 ⊕ k1) ⊕ S -1 (x ′ 1 ⊕ k1)
We know the values of x1 and x ′ 1 from the correct and faulty ciphertexts respectively. For a given value of 2 δ1 there will 0, 2 or 4 valid key hypotheses. The mean hypotheses for all δ1 ∈ {1, . . . , 255} is approximately one, and, therefore, 256 key hypotheses when all δ1 ∈ {1, . . . , 255} are considered.

The same can be said for each of the four equations in the set given above. However, for a given value of δ1 each of the four equations would be expected to return approximately one hypothesis for a key byte. These values will give one hypothesis for the quartet of key bytes {k1, k8, k11, k14}. Given that an attacker will have to take into account all the values in {0, . . . , 255} there will be 256 possible values for the quartet {k1, k8, k11, k14}. After an attacker has analyzed the four equations defined in Section 3.1 there would be an expected 2 32 key hypotheses.

The Second Step of the Fault Attack

In order to further reduce the key hypotheses we use the relationship between the ninth round key and the tenth round key.

We consider the key-scheduling algorithm (see Algorithm 2), the ninth round key, K9, generates the tenth round key, K10. The key schedule is invertible and K9 can be expressed in terms of elements of K10. The value of K9 can be expressed as

    k1 ⊕ S(k14 ⊕ k10) ⊕ h10 k5 ⊕ k1 k9 ⊕ k5 k13 ⊕ k9 k2 ⊕ S(k15 ⊕ k11) k6 ⊕ k2 k10 ⊕ k6 k14 ⊕ k10 k3 ⊕ S(k16 ⊕ k12) k7 ⊕ k3 k11 ⊕ k7 k15 ⊕ k11 k4 ⊕ S(k13 ⊕ k9) k8 ⊕ k4 k12 ⊕ k8 k16 ⊕ k12     .
We can observe that the fault values in the first column of the state matrix at the output of the eighth round MixColumn is (2 f ′ , f ′ , f ′ , 3 f ′ ), where f ′ is a non-zero arbitrary value in F 2 8 . Using the InverseMixColumn operation and using the interrelations between the fault values, we can define the following equation:

2 f ′ = S -1 (14 (S -1 (x1 ⊕ k1) ⊕ ((k1 ⊕ S(k14 ⊕ k10) ⊕ h10))) ⊕ 11 (S -1 (x8 ⊕ k8)⊕ (k2 ⊕ S(k15 ⊕ k11))) ⊕ 13 (S -1 (x11 ⊕ k11) ⊕ (k3 ⊕ S(k16 ⊕ k12))) ⊕ 9 (S -1 (x8 ⊕ k8) ⊕ (k4 ⊕ S(k13 ⊕ k9)))) ⊕ S -1 (14 (S -1 (x ′ 1 ⊕ k1) ⊕ ((k1 ⊕ S(k8 ⊕ k10) ⊕ h10))) ⊕ 11 (S -1 (x ′ 8 ⊕ k8) ⊕ (k2 ⊕ S(k15 ⊕ k11)) ⊕ 13 (S -1 (x ′ 11 ⊕ k11) ⊕ (k3 ⊕ S(k16 ⊕ k12))) ⊕ 9 (S -1 (x ′ 8 ⊕ k8)⊕ (k4 ⊕ S(k13 ⊕ k9))))
Similarly, we can define the following equations:

f ′ = S -1 (9 (S -1 (x13 ⊕ k13) ⊕ (k13 ⊕ k9)) ⊕ 14 (S -1 (x10 ⊕ k10) ⊕ (k10 ⊕ k14)))⊕ 11 (S -1 (x7 ⊕ k7) ⊕ (k15 ⊕ k11)) ⊕ 13(S -1 (x4 ⊕ k4) ⊕ (k16 ⊕ k12))) ⊕ S -1 (9 (S -1 (x ′ 13 ⊕ k13) ⊕ (k13 ⊕ k9)) ⊕ 14 (S -1 (x ′ 10 ⊕ k10) ⊕ (k10 ⊕ k14)))⊕ 11 (S -1 (x ′ 7 ⊕ k7) ⊕ (k15 ⊕ k11)) ⊕ 13 (S -1 (x ′ 4 ⊕ k4) ⊕ (k16 ⊕ k12))) f ′ = S -1 (13 (S -1 (x9 ⊕ k9) ⊕ (k9 ⊕ k5)) ⊕ 9 (S -1 (x6 ⊕ k6) ⊕ (k10 ⊕ k6))) ⊕ 14 (S -1 (x3 ⊕ k3) ⊕ (k11 ⊕ k7)) ⊕ 11 (S -1 (x16 ⊕ k16) ⊕ (k12 ⊕ k8))) ⊕ S -1 (13 (S -1 (x ′ 9 ⊕ k9) ⊕ (k9 ⊕ k5)) ⊕ 9 (S -1 (x ′ 6 ⊕ k6) ⊕ (k10 ⊕ k6)))⊕ 14 (S -1 (x ′ 3 ⊕ k3) ⊕ (k11 ⊕ k7)) ⊕ 11 (S -1 (x ′ 16 ⊕ k16) ⊕ (k12 ⊕ k8))) 3 f ′ = S -1 (11 (S -1 (x2 ⊕ k2) ⊕ (k2 ⊕ k1)) ⊕ 13 (S -1 (x5 ⊕ k5) ⊕ (k6 ⊕ k5)))⊕ 9 (S -1 (x12 ⊕ k12) ⊕ (k10 ⊕ k9)) ⊕ 14 (S -1 (x15 ⊕ k15) ⊕ (k14 ⊕ k13))) ⊕ S -1 (11 (S -1 (x ′ 2 ⊕ k2) ⊕ (k2 ⊕ k1)) ⊕ 13 (S -1 (x ′ 5 ⊕ k5) ⊕ (k6 ⊕ k5))) ⊕ 9 (S -1 (x ′ 12 ⊕ k12) ⊕ (k10 ⊕ k9)) ⊕ 14 (S -1 (x ′ 15 ⊕ k15) ⊕ (k14 ⊕ k13)))
The second stage of the attack is coupled with the first stage, and can be used to further reduce the number of key hypotheses.

Analysis of the second step of the fault attack

The expected number of hypotheses produced by the second step of the attack follows a similar reasoning to the analysis of the first step, given in Section 3.2.

If we consider the second equation defined in Section 3.3, it can be rewritten as

f ′ = A ⊕ B ,
where A and B are defined as

A = S -1 (9 (S -1 (x13 ⊕ k13) ⊕ (k13 ⊕ k9)) ⊕ 14 (S -1 (x10 ⊕ k10) ⊕ (k10 ⊕ k14))) ⊕ 11 (S -1 (x7 ⊕ k7) ⊕ (k15 ⊕ k11)) ⊕ 13 (S -1 (x4 ⊕ k4) ⊕ (k16 ⊕ k12)))
and

B = S -1 (9 (S -1 (x ′ 13 ⊕ k13) ⊕ (k13 ⊕ k9)) ⊕ 14 (S -1 (x ′ 10 ⊕ k10) ⊕ (k10 ⊕ k14))) ⊕ 11 (S -1 (x ′ 7 ⊕ k7) ⊕ (k15 ⊕ k11)) ⊕ 13 (S -1 (x ′ 4 ⊕ k4) ⊕ (k16 ⊕ k12)))
.

We can consider A and B to be random values in F 2 8 . For a given values of f ′ the difference between A and B will be equal to f ′ with a probability of 1 2 8 . Using the same reasoning, the probability of all four equations being valid is 1 2 8 4 = 1 2 32 . We have to consider all the possible values of f ′ , i.e. {0, . . . , 255}. A given key hypothesis will, therefore, be valid for some arbitrary value of f ′ with a probability of 2 8 × 1 2 32 = 1 2 24 . The first step of the attack is expected to return 2 32 hypotheses each of which still be under consideration at the end of the second step with a probability of 1 2 24 . One would, therefore, expect the second step of the attack to produce 2 8 possible key hypotheses.

Attacking Other Bytes

In the previous sections we describe an attack where we base our Differential Fault Analysis on the knowledge that a fault has been induced in the first byte of the state matrix. However, we can note that the analysis returns a very small number of hypotheses. We can, therefore, conduct 16 independent analyses under the assumption that a fault is induced each of the 16 bytes of of the state at the beginning of the eighth round. An attacker would expect this to produce 2 4 × 2 8 = 2 12 valid key hypotheses, which is still a trivial exhaustive search.

There are several versions of fault-based differential cryptanalysis that are able to reduce the number of key hypotheses from two faults injected into an implementation of AES, as described in [START_REF] Kim | New differential fault analysis on aes key schedule: Two faults are enough[END_REF][START_REF] Mukhopadhyay | An improved fault based attack of the advanced encryption standard[END_REF][START_REF] Piret | A differential fault attack technique against SPN structure, with application to the AES and KHAZAD[END_REF]. However, the analysis proposed in this paper is more effective, since the resulting exhaustive search can be reduced to a trivial size using one fault. The number of key hypotheses returned by previous work would be somewhat time consuming. The advantage of the proposed attack is that it does not need to reproduce a successful attack in order to able to determine a secret key. Acquiring multiple faulty ciphertexts can be problematic as faults are only successful with a certain probability, and the effect cannot always be predetermined. This would mean that an attacker could potentially have to search among numerous faulty ciphertexts to find a pair that both have the desired fault.

Conclusion

This paper proposes a fault-based differential cryptanalysis of AES, that is an extended version of the attack described in [START_REF] Mukhopadhyay | An improved fault based attack of the advanced encryption standard[END_REF]. An attacker would expect to be able to reduce the number of key hypotheses from 2 128 to 2 8 with one well placed fault. As noted in [START_REF] Moradi | A generalized method of differential fault attack against AES cryptosystem[END_REF], these attacks can be conducted without any knowledge of the plaintext being enciphered, as an attacker would just need to know the plaintexts were the same.

There are many descriptions of a fault-based differential cryptanalysis of AES that could be prevented by repeating the last two or three rounds of an implementation of AES, to verify that no exploitable fault has been inserted [1-3, 12, 13]. However, to prevent the attack described in this paper the last four rounds would need to be repeated to check no fault was injected. Moreover, given how much information can be gleaned from one fault, one would expect there are attacks that require more faulty ciphertexts that would be able to make use of faults in earlier rounds. One would, therefore, suggest that in order to protect an implementation of AES the last five rounds should be protected against fault injection.

  All the elements in M and M -1 are elements of F(2 8 ) expressed as a decimal digit.-AddRoundKey: Each byte of the array is XORed with a byte from a corresponding array of round subkeys.

Acknowledgements

The work described in this paper has been supported in part by the European Commission IST Programme under Contract ICT-2007-216676 ECRYPT II and EPSRC grant EP/F039638/1 "Investigation of Power Analysis Attacks". The second author would like to acknowledge the support of Department of Science and Technology (DST) India under the Fast Track Proposals for Young Scientists for the proposal entitled "Design and Analysis of Side Channel Attack Resistant Symmetric Key Cryptosystems".'