Wael Kanoun

Nora Cuppens-Boulahia

Frédéric Cuppens

José Araujo

Automated Reaction based on Risk Analysis and Attackers Skills in Intrusion Detection Systems

Keywords: Intrusion detection system, attack scenario, countermeasure, risk analysis, potentiality, impact, skill and knowledge

Nowadays, intrusion detection systems do not only aim to detect attacks; but they go beyond by providing reaction mechanisms to cope with detected attacks, or at least reduce their effects. Previous research works have proposed several methods to automatically select possible countermeasures capable of ending the detected attack, but without taking into account their side effects. In fact, countermeasures can be as harmful as the detected attack. Moreover, sometimes selected countermeasures are not adapted to the attacker's actions and/or knowledge. In this paper, we propose to turn the reaction selection process intelligent by giving means to (i) quantify the effectiveness and select the countermeasure that has the minimum negative side effect on the information system by adopting a risk assessment and analysis approach, and (ii) assess the skill and knowledge level of the attacker from a defensive point of view.

Introduction

In intrusion detection approach, the main objective is to detect and identify attacks or intrusions; and then react to counter them, to block them, or to mitigate their impact on the information system (IS). There are two different approaches for the reaction perspective: hot reaction [START_REF] Cuppens | Selecting appropriate counter-measures in an intrusion detection framework[END_REF] and policy based reaction [START_REF] Debar | Enabling automated threat response through the use of a dynamic security policy[END_REF][START_REF] Cuppend-Boulahia | Specifying intrusion detection and reaction policies: An application of deontic logic[END_REF]. The first aims to launch a local action on the target machine to end a process, or on target network component to block a traffic, that are the cause of the launched alerts. The second acts on more general scope: it considers not only the threats reported in the alerts, but also constraints and objectives of the organization oper-ating the IS and this by modifying the access control policy. Therefore a trade-off can be established between security objectives, operation objectives and constraints. Whatever the adopted approach, each countermeasure can have negative or positive side effects. The same countermeasure capable of ending an attack could make the IS more vulnerable, expose it to other attacks, or even have an overall impact more disastrous than the attack itself. For instance, Firewall reconfiguration is effective against a denial of service (DoS) attack, but can be harmful if valuable connections to a critical server could be potentially lost.

Therefore many questions emerge: Is it better to stand still? Or is the attack harmful enough to react? In this case, which countermeasure must be selected with minimum negative side effects? To answer these questions, we adopt a risk assessment and analysis approach. This approach is already used to analyze and evaluate the risks that threaten organization assets. We aim to use the same approach to evaluate the effectiveness of each countermeasure in realtime, and improve the automated reaction mechanism. The first step of a risk analysis method is to collect data that describes the system state in real-time. The second step is analyzing them and finding the potential threats and their severity. The final step is to study the countermeasure effectiveness to eliminate these threats or reduce their severity: The goal is not always to block the attack, but to minimize the risk incurred by target IS. Therefore a risk assessment method is used to evaluate and quantify the risk of an attack and its countermeasures. The method is useful to decide when it is suitable to react, and which countermeasure should be activated.

Another important aspect is the Attackers Skills and Knowledge level (SK Level). Such data is useful for the automated reaction process. If a novice script kiddie attacker is trying to establish a remote session, a simple TCP reset will be enough to eliminate the detected threat. Otherwise, in the case of an experienced attacker, the TCP reset can be ineffective and a firewall reconfiguration may be needed. Therefore assessing the SK Level make the reaction deci-sion module more accurate and effective. We can assume that a risk assessment and analysis approach combined with the assessment of the attackers skill and knowledge level make the automated process of reaction and countermeasure selection more accurate, realistic, cost effective, and with minimum intervention of the human administrator.

The remainder of this paper is organized as follows. To determine when a reaction is required and which is the best countermeasure to activate, our solution using risk analysis and skill and knowledge assessment approaches will be presented in section II. The implementation of our model and the conducted tests are showed in section III. In section IV, other reaction models and risk analysis models from the literature are presented. Finally section V concludes the paper.

Solution

To react against attacks, an efficient diagnostic procedure to detect and identify the intrusions is needed. However, due to the limitation and unreliability of the intrusion detection probes like SNORT [START_REF]Snort official[END_REF], only low-level events can be detected with potentially high rates of false alarms. Therefore, to detect and recognize the current attack, an alert correlation procedure is required for proper reaction. The correlation procedure recognizes relationships between alerts in order to associate these alerts to a more global intrusion scenario, and the intrusion objectives that the attacker is seeking to accomplish. There are many approaches that can be used for this purpose: implicit [START_REF] Lippmann | Using key string and neural networks to reduce false alarms and detect new attacks with snifferbased intrusion detection systems[END_REF], explicit [START_REF] Huang | A large-scale distributed intrusion detection framework based on attack strategy analysis[END_REF][START_REF] Morin | Correlation of intrusion symptoms: an application of chronicles[END_REF], and semi-explicit [START_REF] Cuppens | Recognizing malicious intention in an intrusion detection process[END_REF][START_REF] Ning | Constructing attack scenarios through correlation of intrusion alerts[END_REF] correlations. The implicit approach tries to establish implicit relations, e.g. statiscal relations, between the observed alerts or events. On other hand, in the explicit approach, whole attack scenarii are defined using explicit relations between the alerts or events. This approach is static because it requires an exhaustive definition for all the known attacks, and it is not adapted to the nonautomated attacks. The semi-explicit approach is based on the description of the elementary intrusions corresponding to the alerts. The LAMBDA [START_REF] Cuppens | Lambda: A language to model a database for detection of attacks[END_REF] language can be used to describe these elementary steps by defining their preconditions and post-conditions. This approach then finds causal relationships between these elementary alerts and connects these elementary alerts when such a relationship exists.

The correlation procedure then consists in building a scenario that corresponds to an attack graph. The attack graph is a set of paths where the nodes are the elementary attack steps; the attacker choses a path and execute these elementary steps to achieve his intrusion objective. We have decided to use this approach due to its flexibility and dynamicity: we do not have to define static exhaustive relations between the elementary steps to construct the attack scenarii, but instead, these relations can be discovered dynamically in real-time.

Semi-Explicit Correlation Definition Two LAMBDA models A and B are correlated if the post-condition of A matches the pre-condition of B. This semi-explicit [START_REF] Cuppens | Recognizing malicious intention in an intrusion detection process[END_REF][START_REF] Ning | Constructing attack scenarios through correlation of intrusion alerts[END_REF] approach is more generic and flexible than the other correlation approaches, because only the elementary steps are defined as entities and not the whole attack scenarii. A short description of the LAMBDA model fields of an elementary step is presented; for a formal description interesting readers can refer to [START_REF] Cuppens | Lambda: A language to model a database for detection of attacks[END_REF]:

• Pre-conditions: This field describes the IS state required so that the attacker is able to perform the step.

• Post-conditions: This field describes the IS state after the execution of the step.

• Detection: This field is used for the mapping of a LAMBDA model to the appropriate alert.

• Verification: This field can be used to verify if a step is successfully executed.

In this paper, we will need mostly the first two fields (i.e. pre-conditions and post-conditions); examples will be given in section III.

Regarding reaction, this approach can provide a precise diagnosis of the ongoing intrusion scenario by construction the attack graph, predict the potential future steps and the intrusion objectives. Using an approach similar to the one used to describe elementary intrusions, elementary countermeasures can be specified. In this case, anti-correlation [START_REF] Cuppens | Anti-correlation as a criterion to select appropriate counter-measures in an intrusion detection framework[END_REF] can be used to find the countermeasures capable of ending a detected scenario.

Anti-Correlation Definition Two LAMBDA models A and B are anti-correlated if the post-condition of A matches the pre-condition negation of B. The anti-correlation [START_REF] Cuppens | Anti-correlation as a criterion to select appropriate counter-measures in an intrusion detection framework[END_REF] approach is based upon finding the appropriate countermeasure that turn an elementary future step of an attack unexecutable due to preconditions value modifications. Therefore, using the anti-correlation approach, the administrator knows which countermeasures from a predefined library are capable of blocking the threat.

Risk Assessment Model

As explained in the previous section, the anti-correlation approach can be used to generate a set of candidate countermeasure capable of ending the detected attack, but without assessing its impact nor the candidate countermeasure. Therefore, this reaction approach can be refined by combining it with the risk analysis model proposed in [START_REF] Kanoun | Advanced reaction using risk assessment in intrusion detection systems[END_REF]. This model is used to evaluate the total risk gravity of the IS once an attack is detected and after simulating the execution of the candidate countermeasure. Only the countermeasures that reduce the total risk gravity are kept and a new set of Risk Efficient Countermeasures (Risk Eff CM) is instantiated. The total risk gravity can be assessed after evaluating the Potentiality (Pot) and the Impact (Imp) of the detected attacks. The structure of the model is described in Figure 1. The total risk gravity of the IS is derived from the risk gravities of the detected attack scenarii. Each scenario risk gravity depends on its potentiality and impact factors. Interested readers can refer to [START_REF] Kanoun | Advanced reaction using risk assessment in intrusion detection systems[END_REF] for more details.

Potentiality P ot

The major factor Potentiality P ot measures the probability of a given scenario to take place and achieve its objective with success. To evaluate P ot, we must first evaluate its minor factors: natural exposition Expo and dissuasive measures Diss and we have to take into account classification of the attack also. These minor factors can be evaluated after the appropriate audit clusters are calculated. These clusters are questions-tests that aim to evaluate the system state (active services, existent vulnerabilities, etc.). The value zero indicates that the studied scenario is impossible, and the value MAX VALUE indicates that the occurrence and the successful execution of the scenario are inevitable.

Impact Imp

The second major factor to evaluate Risk Gravity of an attack scenario is Impact Imp.

--→ Imp is defined as a vector with three elements that correspond to the three fundamental security properties: Availability Avail, Confidentiality Conf and Integrity Integ. Therefore, with each Intrusion Objective, a vector --→ Imp is associated and should be evaluated. Actually, it is not possible to statically evaluate --→ Imp of a scenario (or more precisely the --→ Imp of the scenario's intrusion objective) directly because it depends on several dynamic elements. The impact depends on the importance of the target assets ---→ Class, and the impact reduction measures level -→ IR that are deployed on the system to reduce and limit the impact once the attack was successful.

Risk Gravity of an Attack Scenario or a Countermeasure Grav

For each detected attack, the risk gravity must be evaluated to estimate the danger level of this attack. The risk is the combination of potentiality and impact using a predefined function f . An attack that occurs frequently with little impact may have the same risk level as another rare attack that have significant impact. If a scenario has P ot or Imp equal to zero, the scenario's gravity risk Grav will be null. To assess the risk Gravity of a candidate countermeasure CM u , the same function f is used to assess the risk as shown in the following equation:

G CMu = f (P ot = MAX VALUE, Imp = CM u .Impact)
(1) The use of MAX VALUE for the Pot parameter is justified by the fact that countermeasures, contrary to detected attack scenarii, do not have intrinsic potentiality. This can be explained by the fact that once a countermeasure is selected, it must be activated successfully in the IS and therefore its impact must be considered with maximum potentiality. For the attack scenarii, each one has a proper potentiality that must be combined with the attack scenario impact to deduce the risk gravity.

Total Risk Gravity T otal Grav and T otal Grav u

In most situations, the correlation and reaction modules do not deal with one specific scenario. Instead, these modules have to take into account many candidate and even simultaneous scenarii. Therefore, before estimating the total gravity of risk, we must evaluate the gravity of risk of each scenario in the attack graph separately. Then we define the total gravity as an ordered vector containing the values of gravity risk of each candidate scenario. An order relation can be defined between the different instances of --------→ T otal Grav using the lexicographic comparison. Thus, we are able to judge which attack graph has the highest risk gravity. We define also ---------→ T otal Grav u similarly to --------→ T otal Grav, where the difference is that ---------→ T otal Grav u is assessed with the new state of the IS after the simulated execution of the countermeasure CM u , in other words using the new generated attack graph that takes into account the activation of the CM u .

Risk Efficient Countermeasures Set

Once for each countermeasure u, G CMu and ---------→ T otal Grav u are evaluated, -------------→ T otal Grav CM u can be evaluated :

-------------→ T otal Grav CM u = ---------→ T otal Grav u ∪ G CMu ( 2
)
where ∪ is a concatenation operator. Now, only the countermeasures from Anticorrelated CM that decrease the total risk gravity are kept and a new set Risk Ef f CM is defined that contains only risk efficient countermeasures:

∀CM u ∈ Anticorrelated CM ; -------------→ T otal Grav CM u ≤ --------→ T otal Grav (3)
⇒ CM u ∈ Risk Eff CM

Skill and Knowledge Assessment

To react properly against a detected attack scenario, the countermeasure selection process must take into account the observed skill and knowledge of the attacker. To end an attack executed by a novice, a simple close connection can be effective, which it is not the case when facing an expert attacker who can easy counter this reaction and a firewall reconfiguration is needed. In general, it could be useless to activate a complex countermeasure against a beginner; or to activate a simple countermeasure against an expert attacker who can easily bypass it. Therefore, the assessment of the attacker's skill and knowledge level would be very useful to tune our reaction model. Another point is that the attacker can have internal knowledge of the IS. For instance, a remote attacker that have the proper credentials, and thus is able to connect from the first attempt, must be taken in consideration that he/she has internal knowledge and/or high level of expertise. Another example is the case of or an attacker that is able to predict the tcp sequence of a connection that uses a complex algorithm (and not use the standard tcp sequence number incremental algorithm). As we explained before, each complex attack scenario can be modeled with an attack graph where the nodes are the elementary action steps. These elementary steps can be more or less difficult to be performed, dependently on the attacker's skills and target IS internal knowledge.

SK Level Label

To assess the attacker's skill and knowledge, a defensive point of view is adopted. From the point of view of the target IS, the only information about attacker's actions lays the generated alerts that instantiates steps of the attack graph. Each step is described with a specific language like LAMBDA [START_REF] Cuppens | Lambda: A language to model a database for detection of attacks[END_REF]. We propose to add a new label called Skill and Knowledge level SK Level. For the attack actions, this label indicates the minimum level of skill and knowledge required to execute this action-step successfully. For the countermeasure, it indicates the value of this level that the attacker can not bypass once it is activated. This new label can have the values shown in Table 1. Using the SK Level values of the executed steps retrieved from the attack graph, it is possible to assess the attacker's level of skills and determine if he/she has already internal knowledge of the target IS. Another interesting approach consists of not only considering the SK Level values, but also their sequence with taking into account the time dimension; however this approach will not be considered in the present paper. The correlation engine by determining the executed attack steps by an attacker, is capable of assessing the attacker's level of skill and knowledge Attacker SK Level. The first approach to evaluate Attacker SK Level can be done using the following equation:

Attacker SK Level = M ax i (SK Level i )
where SK Level i = Attack Step i .SK Level, (4) and Step i ∈ Executed Steps A possible method is to set honeypots [START_REF] Krasser | The use of honeynets to increase computer network security and user awareness[END_REF][START_REF] Yin | Honeypot and scan detection in intrusion detection system[END_REF] and redirect the attacker to execute his/her attack steps on them. This will be used to collect the maximum number of executed steps to assess accurately his/her SK Level.

Once the Attacker SK Level had been assessed, only the countermeasures from Risk Eff CM such that the SK Level is higher than Attacker SK Level are kept, and a new set called SK Eff CM (see Figure 2) can be defined and instantiated countermeasures:

∀CM u ∈ Risk Eff CM; Attacker SK Level ≤ CM u .SK Level (5) ⇒ CM u ∈ SK Eff CM

Countermeasure Selection Procedure

Once the Risk Eff CM and SK Eff CM have been instantiated, a clear automatic procedure can be applied to select the most appropriate countermeasure :

If SK Ef f CM = ∅ Select(M in SK Level (CM u )) If Risk Ef f CM = ∅ Select(M in Risk (CM u )) Select(None)
As suggested in this algorithm, countermeasures that belong to SK Eff CM set has the highest priority because they are adapted to the attacker's skill and knowledge level, and they are capable of reducing the overall risk gravity. If no such countermeasure could be found, the search moves to the Risk Eff CM, and the selected countermeasure is able to reduce the overall risk without being adapted to SK Level of the attacker. Finally, where Risk Eff CM is empty, no countermeasure will be selected because all the candidate countermeasures are not risk aware; in other words they will increase overall risk.

3 Implementation of the Solution CRIM (Correlation and Recognition of Malicious Intentions) [START_REF] Autrel | CRIM : un module de corrélation d'alertes et de réaction aux attaques[END_REF] is a prototype that has been developed by TELE-COM Bretagne. It implements the fusion, semi-explicit correlation and anti-correlation features using the LAMBDA language [START_REF] Cuppens | Lambda: A language to model a database for detection of attacks[END_REF]. It collects the generated alerts and aggregates them. Then CRIM visualizes the detected attacks in real time, the future steps that can be executed by the attacker using the semi-explicit correlation principle, and the candidate countermeasure using the anti-correlation principle. As a proof of concept, a new module has been created to validate our proposal briefly described in the previous sections.

As shown in Figure 3, this module is used to assess the Risk Gravity of the detected attack scenarii and the candidate countermeasures, then it instantiates the Risk Eff CM countermeasure set. A first version of this module has been developed, but no public version is yet released. Another module takes in charge of assessing the attackers SK Level and compare it to the SK Level of the countermeasures that belong to the Risk Eff CM, then it instantiates the SK Eff CM set. Once the two sets are instantiated, the selection procedure can be applied to activate the most appropriate and effective countermeasure. Works are in progress to develop a first version of this module. Early tests had been performed using a LAMBDA library containing 25 step actions, 5 countermeasures, and 4 main scenarii: Code-Red attack, Trinoo attack, Sapphire attack, and Mit- The Figure 3 shows the output of the CRIM prototype corresponding to the detection of the Mitnick attack. The Mitnick attack aims to gain remote illegal shell by causing a denial of service on a legal machine and then stealing its pre-established tcp connection with the target machine. Thus, the attack graph generated by CRIM using the LAMBDA language is composed of four elementary steps: syn flood, tcp sequence prediction, ip spoofing, spoofed remote shell. The intrusion objective is illegal remote shell We suppose that the attacker was capable to execute successfully the first three steps. Therefore one final step remains before the attacker achieves his or her intrusion objective Illegal Remote Shell on a critical machine. Dark green (or gray in white and black version) circles represent elementary steps of the intrusion scenario, light yellow lozenges correspond to candidate reaction and boxes are intrusion objectives. The attacker has executed successfully the first three steps, and thus only one step remains. Therefore the potentiality and therefore the Total Risk Grav have high values (=4). In other hand, the attacker's SK Level = Max(1,3,2) = 3.

There are two candidate countermeasures capable of reducing the total gravity risk from 4 to 1 (see Total Risk CMx in Figure 3), therefore the two countermeasures are in the Risk Eff CM. The attacker's skill and knowledge level is 3 and that indicates the fact he or she is not a novice. Thus, a block connection that has a SK Level = 2 could be not efficient and a firewall reconfiguration that has a SK Level = 3 is needed. Hence, only the second countermeasure is in SK Eff CM and recommended to be launched.

Related Works

Intrusion detection systems with reaction capabilities like SNORT [START_REF]Snort official[END_REF] already exist. SNORT offers reflex reaction when a given attack is detected like blocking packets, sending visible warning and logging. No advanced reasoning on the reaction consequence is conducted, and side effects could appear with devastating consequences. Many industrial solutions exist like IBM Internet Security [7] and Cisco Secure IDS [START_REF]Cisco secure systems official[END_REF]. These solutions are efficient in intrusion prevention and offer protection against well known attacks with the corresponding impact using database like CVSS [START_REF]National vulnerabilities database[END_REF]. The main drawback is that there is no following up and no monitoring of the detected attacks to assess their risks and impacts in real time once they bypassed the security and prevention measures, dependably on the target organizations and assets. Another limitation is that these solutions handle vulnerabilities exploit without considering the complete scenarii. On other hand, there are several Risk Assessment methods like EBIOS [6, 2], MARION [4], MEHARI [5], etc. These methods are used to manage system assets and evaluate the risk that threatens these assets; they are unfortunately abstract, informal and incompatible with intrusion detection and computer systems: Many elements and parameters are related to physical and nature disasters (fire, earthquake, failure, etc.). There are also elements that need redefinition to be compatible with the intrusion detection systems like potentiality and impact of a threat. As suggested in [START_REF] Sauvé | On the risk exposure and priority determination of changes in it service management[END_REF], the risk exposure can be evaluated in terms of business perspective by using financial metrics. Another problem is that these methods are not adapted to be used in real-time. Our goal is to evaluate the system and the available countermeasure actions in real-time to help the administrator to chose the best countermeasure, and even make the reaction process automatic with minimum human intervention.

Conclusion and Future works

A first version of the risk analysis module has been implemented, and current works is being conducted to develop the Skill and Knowledge Assessment module. Further Series of tests will be conducted to evaluate the effectiveness and the performance of these added modules.

In the future, attack and countermeasure will be modeled with LAMBDA models, and attacks simulations will be conducted for VoIP services: CRIM will control and supervise the VoIP services status, detect and recognize attacks in real time, then conduct a Risk analysis and Skill and Knowledge assessment to propose to the administrator, or to the automated reaction module, the most effective countermeasure. This will be conducted in the ReD (REaction after detection) project [START_REF] Araujo | Reaction after Detection) project website[END_REF] with other industrial partners. ReD proposes an auto adaptive model (see Figure 4) that starts from the security policy management of the monitored IS. The low level tools including intrusion detection and access control mechanisms that are implemented locally to monitor the IS are configured according to the high level security specifications. Then, according to the different alerts generated, the alerts are forwarded to the upper level whenever it is necessary, after crossing the different reaction levels, to evaluate the current system state where either direct responses are launched or the whole security policy is changed according to the detected threat. We define three levels of reaction; (1) low level reaction, (2) intermediate level reaction, and (3) high level reaction. Each level considers particular security requirements and deploys appropriate security components and mechanisms to react against the detected threats.

The risk analysis and attacker's Skill and Knowledge Assessment approach proposed in this paper will be integrated in ReD framework, and more precisely in the ACE (Alert Correlation Engine) and RDP (Reaction Decision Point) modules. The first is responsible for attack identification and diagnosis by constructing ongoing attack scenarii ac-cording to the alerts generated by the sensors. The second module decides which reactions should be triggered according to the attack scenarii received from the ACE. The selected reaction will be deployed by the REP (Reaction Enforcement Point) and PEP (Policy Enforcement Point). Our approach will turn these two modules more intelligent and risk-aware, by assessing the attacks and reaction induced risks on the entire IS. Therefore the intermediate level and high level reactions will be adapted with the organization policy and take in consideration impact and risks constraints compliantly with the organization needs and strategy. Moreover, another is being developed to communicate the attack graph, candidate countermeasures, risk analysis results, and skill and knowledge assessment results to the security console. This console will visualize graphically these data. Interested readers can refer to [START_REF] Araujo | Reaction after Detection) project website[END_REF] for more details about ReD architecture.

In ReD framework, when the Mitnick attack (see section III) is detected, three reactions levels will be activated:

• Low level reaction: At this level, reflex measures like logging the attacker activity and the incoming packets, or dropping spoofed IP packets, can be activated. The activation of these reaction measures does not require high intelligence level.

• Intermediate level reaction: As presented in section III, the most efficient countermeasure will be selected to end the ongoing attack. At this level, the reaction procedure selection is more intelligent.

• High level reaction: This reaction level aims not only to end the detected attack, but also prevents the occurrence of this attack in the future by activating or redefining the security policy. In ReD project, the Or-Bac model [START_REF] Miège | Définition d'un environnement formel d'expression de politiques de sécuérité: Modèle OrBAC et extensions[END_REF] has been chosen as a security policy model. In OrBac, special contexts can be defined and activated when an attack is detected. In the case of Mitnick attack, the proper security policy context will be selected, and the activated security policy rules will be deployed on PEPs (e.g. firewalls, files and account rights, etc.).

Intrusion detection systems aim to detect attacks, however such detection is not quite useful without reaction. Against given attacks, there could be many possible countermeasures. Our approach will help administrators taking their decisions and selecting the proper countermeasure(s) by assessing the impact of both detected attacks and the candidate countermeasures, and taking in consideration the attacker's skill and knowledge level. As we know, no similar approach exists in the literature. We are even conducting further research and tests to turn the reaction selection and activation process fully automated.

Figure 1 .

 1 Figure 1. Risk assessment structure

Figure 3 .

 3 Figure 3. CRIM output: Attack graph, Intrusion objectives, Attack risk gravity, reaction risk gravity, Attacker's SK Level

Figure 4 .

 4 Figure 4. ReD Reaction workflow deployment

Table 1 . SK Level label values

 1

	SK Level	Skill	Internal Knowledge
	0	Low	No
	1	Medium	No
	2	Medium	Yes
	3	High	No
	4	High	Yes

2.2.2 Attacker's SK Level and Skill and Knowledge

Efficient Countermeasure Set

We consider that an attacker, capable of executing an attack step that has a high SK Level, is an expert attacker; Figure 2. Risk Eff CM and SK Eff CM sets and thus a more sophisticated countermeasure is required. The attacker's skill and knowledge Level (SK Level) must be evaluated to refine the countermeasure selection. A first approach to assess the attacker's SK Level is to retrieve the SK Level maximum value among the successfully executed attack steps. The use of Max function might not be enough accurate, and further advanced approaches could be explored. Once the attacker's SK Level is assessed, only the countermeasures that have a SK Level greater than the attacker's one will be kept. Hence, the selected countermeasure is adapted to the attacker's Level and a new set called Skill and Knowledge Efficient countermeasures (SK EFF CM) can be instantiated.

Acknowledgment

This work was partially supported by the European CELTIC ReD project.


Joaquin Garcia Alfaro

Michel Barbeau
email: barbeau@scs.carleton.ca

Evangelos Kranakis
email: kranakis@scs.carleton.ca

Joaquin Garcia-Alfaro
email: joaquin.garcia-alfaro@acm.org

Security threat mitigation trends in low-cost RFID systems

Keywords: Radio Frequency Identification (RFID), Electronic Product Code (EPC), Wireless Security, IT Security, Security Threats, Privacy Threats

The design and implementation of security threat mitigation mechanisms in RFID systems, specially in low-cost RFID tags, are gaining great attention in both industry and academia. One main focus of research interests is the authentication and privacy techniques to prevent attacks targeting the insecure wireless channel of these systems. Cryptography is a key tool to address these threats. Nevertheless, strong hardware constraints, such as production costs, power consumption, time of response, and regulations compliance, makes the use of traditional cryptography in these systems a very challenging problem. The use of low-overhead procedures becomes the main approach to solve these challenging problems where traditional cryptography cannot fit. Recent results and trends, with an emphasis on lightweight techniques for addressing critical threats against low-cost RFID systems, are surveyed.

Introduction

Radio Frequency Identification (RFID) is a wireless communication technology, based on analog and digital components, used to identify and track goods and people. Even though it has been used for more than seventy years (e.g., RFID was used in World War II for identifying enemy aircrafts), it is only now that this technology is re-emerging as an important communication paradigm that claims to revolutionize inventory and automation processes [START_REF] Roussos | Enabling RFID in retail[END_REF]. Examples are the use of RFID for supply chain inventory, health care management, animal identification, and anti-counterfeiting. However, while this technology is gaining importance with industrial suppliers, security and privacy concerns are raising, especially, among RFID consumers and end users.

An example is the introduction of low-cost RFID technology in the supply chain of the retail industry by means of the Electronic Product Code (EPC) concept. The EPC is a unique code associated to a passive RFID tag that is placed on shipment pallets. The ability to identify and track these pallets, and their associated products, raise security and privacy concerns. These concerns become critical as retailers and manufacturers contemplate moving from pallet tagging to individual item tagging [START_REF] Roussos | Enabling RFID in retail[END_REF]. The possibility of rogue monitoring of people carrying these items is stimulating security and privacy research in both industry and academia. The insertion of cryptographic mechanisms in low-cost RFID tags is a promising solution to address the aforementioned concerns. However, current state-of-the-art solutions in cryptography must face significant challenges before being deployed in RFID technologies.

According to a research presented by Sarma in [START_REF] Sarma | Toward the 5 cent tag[END_REF], the maximum cost of passive EPC tags should not exceed five cents to enable successful deployment on a world wide scale. This research also states that of these five cents, only one or two cents should be used for the manufacturing of the Integrated Circuit (IC). It is assumed that the available layout area for the implementation of the IC is in the range of 0.25mm 2 which, considering current CMOS technology, translate to a theoretical number of logic gates from two to four thousand. Not all the barriers investigated in [START_REF] Sarma | Toward the 5 cent tag[END_REF] have been removed. The lowcost RFID technology of today is more expensive than what it was anticipated -around ten cents in large quantities. The inclusion of additional RFID features, especially for authentication and privacy purposes, may increase the total end-cost of tags up to fifteen cents or more per unit. Although Moore's Law predicts that digital devices fabricated on ICs will continue decreasing in price, cost of analogue devices (i.e., RF front-end of tags) will remain a constraint [START_REF] Cole | Networked RFID Systems and Lightweight Cryptography -Raising Barriers to Product Counterfeiting[END_REF]. The inclusion of new elements must therefore be well planned.

Since the power used by low-cost RFID (passive) tags is derived from the signal received from readers, power restrictions also apply. The power consumption of a tag varies according to the nature of the operation being performed (e.g., responding to a query or writing data into the memory) and other parameters like the transmission rate, response time, and memory technology. Most of the operations performed in EPC tags require about five to ten microamps -although some special operations, such as writing operations, may require higher power. The power consumption of new security primitives must be within this range in order to allow low-cost tag production.

New security primitives must also work at the data rate of EPC applications. Current EPC applications demand an average reading speed of about two hundred tags per second. That leads to a data transmission rate requirement from tag to reader, of about 640 kbps; and a transmission rate from reader to tag of about 120 kbps. Delays associated to new security mechanisms (e.g., time to perform encryption or random number generation) may also affect the global performance. Delays must hence be taken into account and minimized. We can find in the literature several solutions that provide authentication and privacy mechanisms while meeting these challenging constraints. Most of the solutions can be classified in the following three categories: (1) lightweight cryptography based on the use of one-way hash-like primitives implemented in tags;

(2) low-overhead and ultra-lightweight cryptography relying on the single use of ontag pseudorandomness and simple arithmetic operations; and (3) alternative solutions avoiding the execution of cryptographic processes within tags. We survey, in the sequel, recent contributions and trends according to these three categories. Our work aims at increasing the awareness of available security threat mitigation methods among RFID researchers and developers.

Paper organization. Section 2 surveys one-way hash-like solutions. Section 3 surveys proposals based on the single use of on-tag pseudorandomness and simple arithmetic operations. Section 4 surveys alternative approaches not requiring the necessity of ontag cryptographic processes. Section 5 concludes the paper.

Lightweight Cryptographic Approaches

MAC (Message Authentication Code) based security protocols are among the first solutions discussed in the literature for securing low-cost RFID applications. In [START_REF] Takaragi | An ultra small individual recognition security chip[END_REF], for example, Takaragi et al. present a simple MAC-based approach that uses a static unrewritable 128-bit identifier stored, at manufacturing time, in every tag. The identifier is generated by the manufacturer using a unique secret key for each tag and a keyed hash function that accepts as input the secret key and a specific message. The secret key, hash function, and specific messages are communicated by the manufacturer to the client. Then, this information is shared among the clients' readers, to verify the integrity and authenticity of the exchanged messages. Therefore, this mechanism increases the technical difficulties of performing attacks against the integrity and authenticity of the messages. The main drawback is the use of static identifiers embedded in the tags at manufacturing time. Therefore, brute force attacks can break the secrets shared between readers and tags.

An enhanced solution relies on the use of hash-lock schemes for implementing access controls. In [START_REF] Weis | Security and privacy aspects of low-cost radio frequency identification systems[END_REF], Weis et al. propose a way to prevent unauthorized readers from reading tag contents. A secret is sent by authorized readers to tags using a trusted environment. Tags, equipped with an internal hash function, perform a hash on this secret and store it within their internal memory. Then, tags enter into a locked state in which they answer to any possible query with the computed hash. Weis et al. also describe proper ways of unlocking tags, if such an action is needed by authorized readers (i.e., to temporarily release private data). Regarding privacy threats, Ohkubo et al. propose in [START_REF] Ohkubo | Efficient hash-chain based RFID privacy protection scheme[END_REF] the use of hash chains for the implementation of on-tag security mechanisms with evolving RFID identities. Avoine and Oechslin discuss in [START_REF]A scalable and provably secure hash based RFID protocol[END_REF] some limitations of the approach. They propose an enhanced hash-based RFID protocol to address both authentication and privacy by using timestamps. Similarly, Henrici and Müller discuss in [START_REF] Henrici | Hash-based enhancement of location privacy for radio-frequency identification devices using varying identifiers[END_REF] some weaknesses in the hash-lock scheme presented in [START_REF] Weis | Security and privacy aspects of low-cost radio frequency identification systems[END_REF] and propose a new hash-based scheme intended to enhance privacy and authentication. Several other improvements and hash-based protocols, most of them inspired on lightweight cryptography research for devices with higher hardware capabilities such as smart cards, can be found in [START_REF] Molnar | Privacy and security in library RFID: Issues, practices, and architectures[END_REF][START_REF] Dimitriou | A lightweight RFID protocol to protect against traceability and cloning attacks[END_REF][START_REF] Lee | RFID mutual authentication scheme based on synchronized secret information[END_REF][START_REF]An efficient authentication protocol for RFID systems resistant to active attacks[END_REF].

Hardware Challenges and Limitations

Let us note that the aforementioned approaches require the implementation of one-way hash primitives within low-cost RFID tags. The requirement of reliable hash primitives implemented at the tag level is the main challenge associated with these proposals. Gate requirements of implementations based on standard one-way hash functions, such as MD4, MD5, and SHA-128/SHA-256, exceed the constraints pointed out in Section 1. The implementation of these functions require from seven thousand to over ten thousand logic gates; and from six hundred to over one thousand two hundred clock cycles [START_REF]An efficient authentication protocol for RFID systems resistant to active attacks[END_REF].

The complexity of standard one-way hash functions is therefore an impediment for their deployment on low-cost RFID tags.

The use of standard encryption engines for the construction of hash operations has been discussed in the literature. For example, the use of Elliptic Curve Cryptosystems (ECC) [START_REF] Menezes | Handbook of Applied Cryptography[END_REF] for the implementation of one-way hash primitives on RFID tags has been studied in [START_REF] Wolkerstorfer | Is Elliptic-Curve Cryptography Suitable to Secure RFID Tags? Handout of the Ecrypt Workshop on RFID and Lightweight Crypto[END_REF]. Its use of small key sizes is seen as very promising for providing an adequate level of computational security at a relatively low cost [START_REF] Cole | Networked RFID Systems and Lightweight Cryptography -Raising Barriers to Product Counterfeiting[END_REF]. An ECC implementation for low-cost RFID tags can be found in [START_REF] Batina | An elliptic curve processor suitable for RFID-tags[END_REF]. In [START_REF] Feldhofer | Strong authentication for RFID systems using the AES algorithm[END_REF], Feldhofer et al. present a 128-bit implementation of the Advanced Encryption Standard (AES) [START_REF] Daemen | The Design of Rijndael: AES-the Advanced Encryption Standard[END_REF] on an IC of about three thousand five hundred gates with a power consumption of less than nine microamps at a frequency of 100 kHz. Although this implementation is considerably simpler than previous implementations of the AES algorithm, its requirements are still too high for low-cost RFID tags.

Alternative hash functions based on non-standard low-cost encryption engines is a third candidate. In [START_REF] Israsena | Securing ubiquitous and low-cost RFID using tiny encryption algorithm[END_REF], Israsena presents a hardware implementation of the Tiny Encryption Algorithm (TEA) [START_REF] Wheeler | TEA, a Tiny Encryption Algorithm[END_REF] on an IC of about three thousand gates and with a consumption of about seven microamps. It fits the timing requirements of basic EPC setups where hundred of tags must simultaneously be accessed by the same reader. The implementation relies on very simple arithmetic and bitwise operators. The authors of TEA [START_REF] Wheeler | TEA, a Tiny Encryption Algorithm[END_REF] claim that, despite its simplicity and ease of implementation, the complexity of the algorithm is equivalent to the one of DES (Data Encryption Standard) [START_REF] Menezes | Handbook of Applied Cryptography[END_REF]. Variants of the TEA algorithm are, however, necessary for implementing hash functions. Mace et al. discuss in [START_REF] Mace | ASIC implementations of the block cipher sea for constrained applications[END_REF] some of the vulnerabilities of TEA, such as linear and differential cryptanalysis attacks, and present SEA (Scalable Encryption Algorithm). The strength of this proposal, due to its novelty, is not clear [START_REF] Cole | Networked RFID Systems and Lightweight Cryptography -Raising Barriers to Product Counterfeiting[END_REF].

Other low-cost alternatives are the single use of Linear and Non Linear Feedback Shift Registers (LFSR & NLFSR). However, the simple use of LFSR & NLFSR as underlying mechanisms for the implementation of low-cost one-way hash functions -without further measures that add cost of extra hardware -lead to insecure implementations. For example, the use of the Cellular Automata (CA) model [START_REF] Wolfram | A new kind of science[END_REF] for the implementation of one-way functions -typically built upon LFSR & NLFSR -has been proved to lead to insecure implementations [START_REF] Blackburn | Comments on 'theory and applications of cellular automata in cryptography[END_REF][START_REF] Cole | Networked RFID Systems and Lightweight Cryptography -Raising Barriers to Product Counterfeiting[END_REF].

Physical One-Way Functions

The design of Physically Unclonable Functions (PUFs) and Physical Obfuscated Keys (POKs) is promising for the implementation of hash-like protocols on low-cost EPC tags. Half way between traditional cryptography and physical protection defenses, the ideas behind PUFs and POKs originated in [START_REF] Pappu | Physical One-Way Functions[END_REF] with the conception of optical mechanisms for the construction of Physical One-Way Functions (POWFs). Its use to securely store unique secret keys, in the form of fabrication variations, was proposed as a silicon prototype in [START_REF] Gassend | Silicon physical random functions[END_REF]. The ideas were later improved in [START_REF] Lim | Extracting secret keys from integrated circuits[END_REF]. A coating PUF proposed in [START_REF] Skoric | Secret key generation from classical physics[END_REF] claims an implementation that requires less than one thousand gates. The designs exploit the random variations in delays of wires and logic gates of an IC. For example, the silicon PUF presented in [START_REF] Gassend | Silicon physical random functions[END_REF] receives input data, as a challenge, and launches a race condition within the IC: two transitions signals start propagating along different paths and are compared to determine which one comes first. To decide which signal comes first, a special controller produces a binary value.

The implementation of these proposals seems to have clear advantages at a cost of less than one thousand logic gates [START_REF] Skoric | Secret key generation from classical physics[END_REF]. This technology provides a cost effective and reliable solution that successfully meet the constraints and requirements mentioned in Section 1. However, it also has several drawbacks. The difficulty of successfully modeling the circuits and their reliability is one of the obstacles that this technology must to face. The effects of environmental conditions and effects of the power supply voltage have also raised some concerns [START_REF] Cole | Networked RFID Systems and Lightweight Cryptography -Raising Barriers to Product Counterfeiting[END_REF]. Some alternative proposals try to solve the drawbacks. Holcomb et al. propose in [START_REF] Holcomb | Initial SRAM State as a Fingerprint and Source of True Random Numbers for RFID Tags[END_REF] an approach based on the CMOS SRAM memory of an electrical to generate physical fingerprints. The key idea is the usage of SRAM startup values as seeds of pseudorandomness. The authors claim that the use of 256 bytes of SRAM can yield 100 bits of true randomness each time the memory is powered up. While sound in theory, this technique is limited by memory space of current low-cost tags.

Challenge-response protocols are commonly used to implement security mechanisms in low-cost RFID tags using PUFs. An initial approach presented in [START_REF] Ranasinghe | Low-cost RFID systems: Confronting security and privacy[END_REF], and based on PUFs proposed in [START_REF] Gassend | Silicon physical random functions[END_REF], consists of a challenge-response scheme that probabilistically ensures unique identification of RFID tags. The back-end system of this approach must learn challenge-response pairs for each PUF/tag. It then uses these challenges (hundreds of them) at a time, to identify and authenticate tags. Unique identification of tags is probabilistic. The exposition of tag identifiers to eavesdroppers, and lack of state and randomness in tag responses, make the approach vulnerable to tracking and location threats. Moreover, the great number of challenges that are necessary between readers and tags for the completion of the identification process increases tag response delay and power consumption.

An alternative protocol is presented in [START_REF] Tuyls | RFID-tags for anti-counterfeiting[END_REF]. Tuyls and Batina discuss an off-line PUFbased mechanism for verifying the authenticity of tags using the PUF technology presented in [START_REF] Skoric | Secret key generation from classical physics[END_REF]. Similarly to the traditional approaches presented in [START_REF]Strengthening EPC tags Against Cloning[END_REF][START_REF] Juels | Authenticating pervasive devices with human protocols[END_REF], where readers and tags define ad hoc secrets, the PUF-based approach uses instead the physical structure embedded within tags to generate unique keys. A key extraction algorithm from noisy (binary) data is presented in [START_REF] Tuyls | RFID-tags for anti-counterfeiting[END_REF]. The usage of PUF-based keys simplifies the process of verifying tag authenticity. The combination of unique keys generated onboard together with public key cryptography techniques (e.g., use of signatures) avoid leaking the static single identifier and hence increase the technical difficulties for an attacker to carry on location tracking threats. The main drawback of the approach is the need of large storage space and reliable searching processes on back-end servers in order to link readers with PUF/tag identifiers. The use of public key and digital signatures, based on Elliptic Curve Cryptography (ECC), is another important constraint of the approach.

Bolotnyy and Robins propose in [START_REF] Bolotnyy | Physically unclonable function-based security and privacy in RFID systems[END_REF] a complete set of adapted MAC protocols based on PUFs aiming to simplify the challenge-response communication scheme of previous proposals, and the requirement of traditional cryptographic primitives. Each tag generates multiple identifiers based on embedded PUFs. The approach only addresses static identification and is vulnerable to location tracking attacks. The approach does not solve the necessity of huge lists of challenge-response pairs for each PUF/tag which must be stored on back-servers connected to the readers. Indeed, once a given pair is sent, it must not be used anymore. Otherwise, the protocol cannot guarantee that an adversary eavesdropping data will not gain advantage by performing a replay attack.

Low-overhead and Ultra-lightweight Solutions

The use of on-tag Pseudo Random Numbers Generators (PRNGs) to enhance the security and privacy of RFID systems is another candidate. In fact, most of the approaches, if not all, presented in Section 2 require the use of PRNGs to guarantee correctness. For example, the enhanced hash-lock scheme presented by Weis et al. in [START_REF] Weis | Security and privacy aspects of low-cost radio frequency identification systems[END_REF] relies on the use of on-tag PRNGs and efficient pseudorandomness for mitigating privacy threats like location tracking. Another example is the need of combining PRNGs and hash chains to enable the proposal of Ohkubo et al. presented in [START_REF] Ohkubo | Efficient hash-chain based RFID privacy protection scheme[END_REF]. More recently, a protocol presented in [START_REF] Tsudik | YA-TRAP: Yet another trivial RFID authentication protocol[END_REF], called YA-TRAP, reduces the need of hash-based protocols by combining pre-computed hash-tables for tag verification processes with timestamps and generation of pseudorandom numbers. Similar requirements apply on all the other protocols surveyed in Section 2 -in order to address location tracking problems. From a hardware point-of-view, the insertion of robust one-way hash functions and PRNGs in the constrained environment of low-cost RFID tags makes the implementation of those proposals very challenging and, unrealistic for real world applications.

The use of pseudorandomness for increasing low-cost RFID security is often questioned because robust designs are complex to implement on low-cost RFID devices. The complexity of the implementation of robust PRNGs is equivalent to the complexity of the implementation of robust one-way hash-functions and/or equivalent encryption engines [START_REF] Menezes | Handbook of Applied Cryptography[END_REF]. However, since the ratification of the EPCglobal standard EPC Class-1 Generation-2 (Gen2 for short) [START_REF]EPC Radio-frequency identity protocols Class-1 Generation-2[END_REF] and ISO standards ISO/IEC 18000-6C [28] for the usage of on-tag PRNGs on low-cost RFID devices, the number of single PRNG-based solutions has increased in the industry and academia research. The existence of PRNG hardware already deployed on most of the low-cost RFID tags justifies the convenience of this second category of security threat mitigation mechanisms. Juels and Weis present in [START_REF] Juels | Authenticating pervasive devices with human protocols[END_REF] an unidirectional authentication protocol based on the secure human identification protocol series proposed by Hopper and Blum [START_REF] Hopper | Secure human identification protocols[END_REF]. The new protocol, called by the authors HB+, aims at preventing active attacks against the authenticity of low-cost RFID systems. The resistance of HB+ against active adversaries is proved by the authors using an statistical conjecture [START_REF] Crawford | The Minimal Disagreement Parity Problem as a Hard Satisfiability Problem[END_REF] to bound the difficulty of learning a secret (e.g., ID of the tag) given a sequence of randomly chosen vectors with embedded noisy information. The authors claim that the protocol can be implemented on low-cost tags since it only requires PRNG primitives in tags and implementation of very simple operations, such as bitwise-and and xor. Some security issues of the HB+ protocol were reported in [START_REF] Katz | Parallel and concurrent security of the HB and HB + protocols[END_REF][START_REF] Piramuthu | HB and related lightweight authentication protocols for secure RFID tag/reader authentication[END_REF]. They propose enhancements to address active attacks. However, neither the original HB+ protocol nor its sequels consider authentication of the readers and location tracking attacks. Regarding these issues, we can find in [START_REF] Karthikeyan | RFID security without extensive cryptography[END_REF] a new low-overhead protocol by Karthikeyan and Nesterenko for mutual authentication of tags and readers. The requirements of this protocol are modular algebra operations, such as multiplication of matrices, and on-tag PRNG primitives. Based on similar requirements, such as on-tag PRNG and matrix algebra operations, Dolev et al. present in [START_REF] Dolev | Secure communication for RFIDs proactive information security within computational security[END_REF] two low-overhead proactive unidirectional protocols, called PISP (Proactive Informational Secure Protocol) and PCSP (Proactive Computationally Secure Protocol), with evolving on-tag secrets that expands indefinitely over time. Both PISP and PCSP are compared and contrasted in a joint publication appeared in [START_REF] Dolev | Low Overhead RFID Security[END_REF]. The security of these protocols relies on the difficulty of recovering the operands used on both sides (tags and readers) to synchronize shared secrets. Memory space on current low-cost tags is another limitation to the security of these approaches. An enhanced version of the PCSP protocol, presented in [START_REF] Dolev | RFID Authentication Efficient Proactive Information Security within Computational Security[END_REF], aims at preventing active attacks against the protocol while keeping similar requirements, i.e., on-tag PRNG primitives and matrix operations.

Burmester, Le, and de Medeiros proposed in [START_REF] Burmester | Provably secure ubiquitous systems: Universally composable RFID authentication[END_REF] a new low-overhead protocol, called O-TRAP (Optimistic Trivial RFID Authentication Protocol). Like other protocols surveyed in this section, O-TRAP relies on the use of PRNG primitives in tags and some other simple bitwise operations. O-TRAP is specially designed to prevent privacy attacks while guaranteeing anonymous authentication. The protocol behaves in a manner similar to the hash-lock approach introduced in Section 2. Common secret, shared between readers and tags, are proposed in their scheme to update pseudonyms stored within tags. Like in the hash-lock approach introduced by Weis et al. in [START_REF] Weis | Security and privacy aspects of low-cost radio frequency identification systems[END_REF], readers must access back-end databases to map pseudonyms to true identities. The security of the protocol is proved using the universal composability (UC) model [START_REF] Canetti | Universally composable security: A new paradigm for cryptographic protocols[END_REF]. It is shown that the O-TRAP protocol meets the UC definition of anonymous authentication and anonymous key exchange. However, the O-TRAP protocol fails to satisfy the stronger privacy definitions, such the one stated by Juels and Weis in [START_REF]Defining Strong Privacy for RFID[END_REF] establishing that privacy countermeasures must guarantee both anonymity and untraceability. Juels and Weis point out the possibility of attacking the O-TRAP protocol by de-synchronizing tags. This allow active attacker to uniquely identify them and carry on location tracking attacks. An attack against the untraceability of the O-TRAP protocol is presented in [START_REF] Ouafi | Privacy of Recent RFID Authentication Protocols[END_REF].

Similar attacks exploit existing vulnerabilities in the state-of-the-art of the ultra-lightweight series of authentication protocols. Ultra-lightweight authentication protocols, such as [START_REF]LMAP: A real lightweight mutual authentication protocol for low-cost RFID tags[END_REF][START_REF]M2AP: A minimalist mutual-authentication protocol for low-cost RFID tags[END_REF][START_REF]EMAP: An efficient mutual authentication protocol for low-cost RFID tags[END_REF][START_REF] Chien | SASI: A new ultralightweight RFID authentication protocol providing strong authentication and strong integrity[END_REF], try to eliminate the necessity of hash and PRNG primitives, and involve only simple bitwise and modular arithmetic on-tag operations. The computation of costly operations, such as the generation of pseudorandom numbers, is done at the reader side. Although this fact benefits the implementation of such countermeasures on the constrained environment of low-cost RFID tags, none of these proposals seems to be resistant to either active or passive attacks. The set of authentication techniques presented by Peris-Lopez et al. in [START_REF]LMAP: A real lightweight mutual authentication protocol for low-cost RFID tags[END_REF][START_REF]M2AP: A minimalist mutual-authentication protocol for low-cost RFID tags[END_REF][START_REF]EMAP: An efficient mutual authentication protocol for low-cost RFID tags[END_REF] were reported to be vulnerable by Li and Wang, and Li and Deng to, respectively, the de-synchronization attacks and full-disclosure attacks. Improvements of these techniques, presented by Chien in a new protocol called SASI [START_REF] Chien | SASI: A new ultralightweight RFID authentication protocol providing strong authentication and strong integrity[END_REF] have recently been reported as vulnerable by Cao, Bertino, and Lei in [START_REF] Cao | Security Analysis of the SASI Protocol[END_REF]. These recent cases show how challenging it is to design adequate procedures given the low-cost requirement of the RFID paradigm.

Avoidance of On-tag Cryptographic Processes

Several results, such as [START_REF] Juels | Squealing euros: Privacy protection in RFID-enabled banknotes[END_REF][START_REF] Kinosita | Nonidentifiable anonymous-ID scheme for RFID privacy protection[END_REF][START_REF] Juels | Minimalist cryptography for low-cost RFID tags[END_REF][START_REF]Strengthening EPC tags Against Cloning[END_REF], are not relying on the execution of cryptographic algorithms in tags. One of the earliest proposals is the re-encryption scheme of Juels and Pappu presented in [START_REF] Juels | Squealing euros: Privacy protection in RFID-enabled banknotes[END_REF]. It provides privacy and security for banknotes embedding RFID tags. The approach uses public key cryptography and digital signatures. The operations are, although, performed outside the tags. The scheme consists of a public-key cryptosystem and two authorities: a central bank and a law enforcement agency. Both authorities hold an independent pair of public and private keys associated to each banknote. The central bank authority assigns a unique serial number to each banknote. To do so, the bank uses its private key to sign the unique serial number. The signature and the serial number of the banknote are printed on the banknote as optical data. Then, by using the public key of the law enforcement agency, the bank encrypts the digital signature, unique serial number, and a random number. The resulting ciphertext is stored into a memory cell of the RFID tag. This memory cell is keyed-protected. The tag only grants write access to this memory cell if it receives an access key derived from the optical data. The random number used to create the ciphetext is also stored into a separated memory cell of the tag. This second memory cell is also keyed-protected. The tag only grants read or write access to this memory cell if it receives an access key derived from the optical data.

By using this previous approach, banknote bearers must verify first the digital signature, printed in the banknote as optical data, using the public key of the central bank. Second, they must also verify the validity of the ciphertext stored in the RFID tag. To do so, the bearer encrypts the digital signature, serial number, and random number stored in the memory of the tag, using the public key of the law enforcement agency and the optical data. If one of these two verification processes fails, the authorities must be warned. To avoid using the same ciphertext on every interaction, the authors propose the use of a re-encryption process that can be performed by banknote bearers without the necessity of accessing the private keys of the law enforcement authority. Based on the algebraic properties of the El Gamal cryptosystem [START_REF] Menezes | Handbook of Applied Cryptography[END_REF], the initial ciphertext is transformed into a new unlinkable ciphertext, using the public key of the law enforcement authority [START_REF] Juels | Squealing euros: Privacy protection in RFID-enabled banknotes[END_REF]. This re-encryption process is performed outside the tags. Although the whole process is too complex for use in low-cost RFID scenarios, it is one of the first solutions that appeared in the literature for deploying cryptographic protocols in RFID applications without the need to embed cryptographic primitives in tags.

The work presented by Kinosita et al. in [START_REF] Kinosita | Nonidentifiable anonymous-ID scheme for RFID privacy protection[END_REF] consists of an anonymous ID scheme, in which a tag contains only a pseudonym that is periodically rewritten. Similarly, the approach of Juels in the work Minimalist Cryptography for Low-Cost RFID Tags [START_REF] Juels | Minimalist cryptography for low-cost RFID tags[END_REF] suggests a very light-weight protocol for mutual authentication between tags and readers based on one-time authenticators. Both solutions rely on the use of pseudonyms and keys stored within tags and back-end servers. Pseudonyms are used instead of real identifiers (e.g., instead of the EPC codes in supply chain RFID applications). Each tag contains a small collection of pseudonyms, according to the available memory. A throttling process, is used to rotate these pseudonyms. Each time a tag is interrogated by a reader, a different pseudonym selected at random is returned. Authorized readers have access to the complete list of pseudonyms of each tag and can correlate the identity of the responses they receive. Without the knowledge of this list, unauthorized readers are unable to infer any information about the numerous occurrences of the same tag. The process also forces tags to slow their transmissions when queries come too quickly, as a defense to brute-force attacks. The memory space in current low-cost tags is the main limitation of this approach. Although enhancements can be used to update the list of pseudonyms, communication costs and integrity threats still remain as main drawbacks. A similar, though lighter-weight, protocol for mutual authentication between readers and tags is presented by Juels in [START_REF]Strengthening EPC tags Against Cloning[END_REF]. This time, the Personal Identification Number (PIN), associated to the kill command of EPC Gen2 tags [START_REF]EPC Radio-frequency identity protocols Class-1 Generation-2[END_REF], is used to implement the protocol. The main idea is that even if the EPC data of a tag is skimmed, the PIN remains secret. This way, cloned tags can be detected by testing, without killing the tag, if the kill password matches the original one stored in a back-end database. The risk of exposing the kill PIN of a given tag is however an important drawback of this approach.

Many signal-, power-, and blocking-based defenses, such as shielding of tags, use of noise, and third party guardians, can be found in the literature. The use of distance measurements to detect rogue readers has been discussed in [START_REF] Fishkin | Some methods for privacy in RFID communication[END_REF]. Fishkin et al. propose the inclusion of low-cost circuitry in tags to use the signal-to-noise ratio of readers as a metric for trust. In [START_REF] Hancke | Noisy carrier modulation for HF RFID[END_REF], a similar assumption is used to determine if a reader is authorized to read the tag contents according to its physical distance. Castelluccia and Avoine propose in [START_REF] Castelluccia | Noisy tags: a pretty good key exchange protocol for RFID tags[END_REF] the use of additional tags with better hardware capabilities than low-cost RFID hardware capabilities, to generate noise on the communication channel between readers and low-cost tags. The objective is to thwart possible eavesdroppers. Similar software-based blocking strategies can be found in [START_REF] Juels | The blocker tag: Selective blocking of RFID tags for consumer privacy[END_REF][START_REF]Keep on blockin'in the free world: Personal access control for low-cost RFID tags[END_REF]. Third party compo-nents with cryptographic features to perform authentication and acting as intermediaries between readers and tags have been proposed in [START_REF] Rieback | RFID Guardian: A Battery-Powered Mobile Device for RFID Privacy Management[END_REF][START_REF] Juels | High-Power Proxies for Enhancing RFID Privacy and Utility[END_REF]. The management of these components in real world scenarios like the supply chain of the retail industry is a problem and the main drawback of these proposals. Finally, the use of radio fingerprinting to detect characteristic properties of transmitted signals has also been considered in the literature. Cole and Ranasinghe [START_REF] Cole | Networked RFID Systems and Lightweight Cryptography -Raising Barriers to Product Counterfeiting[END_REF] consider, however, that this technique is difficult to develop in RFID applications and that the benefits of using it, regarding performance, price and required implementation surface in tags, are unclear. Avoine and Oechslin discuss in [START_REF] Avoine | RFID Traceability: A multilayer problem[END_REF] the prevention of traceability attacks via radio fingerprinting. They also conclude that obtaining radio fingerprints of tag is very expensive and difficult. The myriad of tags in circulation in future RFID scenarios would make impracticable the distinction of tags.

Towards Secret-Sharing Strategies

As an evolution of the minimalist cryptography approach presented by Juels in [START_REF] Juels | Minimalist cryptography for low-cost RFID tags[END_REF], and using lists of pseudonyms, the use of secret-sharing schemes is proposed by Langheinrich and Martin in [START_REF] Langheinrich | Practical Minimalist Cryptography for RFID Privacy[END_REF][START_REF]RFID privacy using spatially distributed shared secrets[END_REF] for solving authentication and privacy threats in low-cost RFID scenarios (e.g., supply chain applications of the retail industry). The work presented in [START_REF] Langheinrich | Practical Minimalist Cryptography for RFID Privacy[END_REF] simplifies the lookup process performed from readers to back-end databases for identifying tags, while guaranteeing authentication and tracking resistance. Tag identifiers, seen in this work as the secrets, are encoded as a set of shares and stored in the internal memory of tags. The mechanism used by the authors to encode the shares is based on the (t-n)-threshold schemes of Shamir [START_REF] Shamir | How to share a secret[END_REF]. When the shares are cryptographically combined at the reader side, original tag identifiers are reconstructed. To prevent brute-force scanning from unauthorized readers -trying to obtain the complete set of shares -the authors propose a time-limited access that controls the amount of data sent from tags to readers. At the same time, a cache based process ensures that authorized readers quickly identify tags. Langheinrich and Martin extended the previous proposal to spread the set of shares across multiple tags [START_REF]RFID privacy using spatially distributed shared secrets[END_REF]. Still based on the Shamir's secret sharing schemes, this approach encodes the indentifier of an item tagged with multiple RFID devices by distributing it into multiple shares stored within its tags. Authentication and privacy are enforced by requiring readers to obtain and combine the set of shares.

In [START_REF] Juels | Unidirectional Key Distribution Across Time and Space with Applications to RFID Security[END_REF], Juels, Pappu, and Parno present another secret-sharing based approach, but based on a dispersion of secrets strategy rather than an aggregation strategy -as used by Langheinrich and Marti in [START_REF] Langheinrich | Practical Minimalist Cryptography for RFID Privacy[END_REF][START_REF]RFID privacy using spatially distributed shared secrets[END_REF]. Two different schemes are discussed: dispersion of secrets across space and dispersion of secrets across time. In both schemes, a secret that is used to encrypt RFID identifiers (e.g., the EPC codes) is split in multiple shares and distributed among multiple parties. The construction and recombination of shares are based on the use of error-correcting codes. In order to identify a tag, a party must collect a number of shares. Privacy is achieved by the dispersion of secrets and encrypted identifiers. The dispersion approach helps to improve the authentication process between readers and tags, as tags move through a supply chain. Assuming that a given number of shares is necessary for a reader to obtain the EPC codes assigned to a pallet, for example, a situation where the number of shares obtained by a reader is not sufficient to reach the threshold leads to conclude that unauthorized tags are present on the pallet. The approaches presented in [START_REF] Juels | Unidirectional Key Distribution Across Time and Space with Applications to RFID Security[END_REF] increase the resistance of tags against unauthorized scanning by dispersing tag populations outside the supply chain. Without the space proximity to other tags with equivalent shares, an unauthorized reader cannot obtain the sufficient number of shares required to recover the original identifier of tags and items. A clear advantage of this approach is that it can be implemented on low-cost RFID tags, such as EPC Gen2 [START_REF]EPC Radio-frequency identity protocols Class-1 Generation-2[END_REF] tags, without requiring changes to the current specifications. Only an upgrade of readers is necessary. No real-world tests of the proposals have been conducted. The authors claim, although, that experiments for pharmaceutical products in a closed-loop supply chain are going to be conducted in the future. The main drawback of this approach is the amount of tag memory space required for storing the shares. A shrinking of key shares must be performed a priori in order to apply the scheme on current EPC tags. Other problems, such as tracking and information leaks due to the interaction between authorized readers and tags, must also be solved before deploying the schemes.

Conclusions

The constrained environment and threat model associated to low-cost RFID tags have stimulated the creation of a vast number of proposals to provide low-overhead security threat mitigation mechanisms in these devices. Vulnerable designs appeared in recent literature, such as the lightweight authentication protocols presented by Vajda and Buttyán in [START_REF] Vajda | Lightweight authentication protocols for low-cost RFID tags[END_REF] (whose vulnerabilities were recently reported by Defend, Fu, and Juels in [START_REF] Defend | Cryptanalysis of two lightweight RFID authentication schemes[END_REF]), the set of ultra-lightweight authentication techniques presented by Peris-Lopez et al. in [START_REF]LMAP: A real lightweight mutual authentication protocol for low-cost RFID tags[END_REF][START_REF]M2AP: A minimalist mutual-authentication protocol for low-cost RFID tags[END_REF][START_REF]EMAP: An efficient mutual authentication protocol for low-cost RFID tags[END_REF] (which were reported as vulnerable to passive [START_REF] Barasz | Breaking LMAP[END_REF] and active [START_REF] Li | Vulnerability analysis of EMAP -an efficient RFID mutual authentication protocol[END_REF] attacks), and enhancements of these proposals, like the SASI protocol [START_REF] Chien | SASI: A new ultralightweight RFID authentication protocol providing strong authentication and strong integrity[END_REF] (recently reported by Cao, Bertino, and Lei in [START_REF] Cao | Security Analysis of the SASI Protocol[END_REF] as vulnerable), show how challenging it is to design adequate procedures given the constraints. We surveyed lightweight defenses that can be useful to reduce the risk of threats. We addressed the methods according to three different perspectives: (1) one way hash-like defenses, (2) solutions relying on the single use of on-tag pseudorandomness and simple arithmetic operations; and (3) mechanisms not requiring the execution of cryptographic processes in the tags.

Regarding the first perspective, we pointed out the hardware challenges which to the best of our knowledge, are important obstacles for deployment in real world low-cost RFID scenarios like the supply chain of the retail industry. Physical One-Way Functions (POWFs) and Physically Unclonable Functions (PUFs) are a promising evolution of traditional hash-based protocols, but at a feasible production cost. Their sensitivity to physical noise, the large number of challenges and training session between readers and tags to guarantee adequate identification, and the difficulty to model and analyze, are open lines of research. In the second perspective, we pointed out the memory space and de-synchronization flaws as main limitations. The evolution of these solutions toward strategies that avoid the execution of on-tag cryptographic processes is heading recent researches. We pointed out the use of secret sharing strategies as a promising foundation for the management of keys for the design of authentication protocols and for dealing with privacy issues. Main drawbacks are the management of information leaks due to the interaction between readers and tags, and tracking of tags.

Acknowledgments -The authors graciously acknowledge the financial support received from the following organizations: Natural Sciences and Engineering Research Council of Canada (NSERC), Mathematics of Information Technology and Complex Systems (MITACS), Spanish Ministry of Science and Education (TSI2007-65406-C03-03 "E-AEGIS" and CONSOLIDER CSD2007-00004 "ARES" grants), and La Caixa (Canada awards).