Universite Présenté À L'

Marie Pierre

Joaquin Garcia-Alfaro

Professeur Giuseppe Bianchi

Olivier Festor

Javier Lopez

Frédéric Cuppens

MEMOIRE D'HABILITATION A DIRIGER DES RECHERCHES

Background and

Table of Contents

Chapter 1 Introduction

This habilitation manuscript summarizes a selected list of research contributions in the area of Wireless Security. The selected list of contributions is by no means exhaustive. It shall be seen as a general outline to identify my research work methodology in the wider area of Network Security. In order to facilitate comprehension, citations of my own work are denoted using a plain, numerical style, e.g., [START_REF] Battistello | Transaction-based authentication and key agreement protocol for inter-domain voip[END_REF]; while other literature efforts are cited using alpha-numerical style, e.g., [START_REF] Penrose | A generalized inverse for matrices[END_REF].

The contributions presented in the manuscript are situated in the field of Network Security, with a special emphasis on areas related to wireless security, management of policies, detection of attacks, analysis of vulnerabilities, selection of defense countermeasures and enforcement of access and usage control models. Results are grounded on the use of algorithmics, set theory, software modeling, combinatorics, cryptography, and graph theory.

More specifically, the selected contributions rely on current work around the improvement of RFID (Radio Frequency Identification) security and privacy aspects. The focus in on RFID technologies associated to electronic labels under the EPC (Electronic Product Code) standard (hereinafter simply referred as RFID or EPC tags). The EPC is an international standard that proposes the use of RFID in the supply chain. EPC tags are minimalistic electronic devices that provide serial numbers to identify objects and people. They are designed to balance cost and functionality, and are becoming truly pervasive in wireless network applications, such as Mobile Wireless Ad Hoc Networks (MANETs), Wireless Sensor Networks (WSNs), and Vehicular Ad Hoc Networks (VANETs) [START_REF] Roussos | RFID meets the internet[END_REF]. Tags are potentially the targets of attack against their security and this raises major concerns. The objective of this dissertation is to evaluate some of these concerns and report some of our research solutions handling them.

The remainder chapters of the manuscript are organized as follows. Chapter 2 introduces some preliminary state-of-the-art background on the Electronic Product Code (EPC) standard. It also analyzes security threats to the RFID system of the EPC technology and surveys relevant defense countermeasures for major threats. The following two chapters (Chapters 3 and 4) deepen the analysis on the security of Pseudorandom Number Generators (PRNGs) and provide novel designs to address predictability problems on previous efforts in the related literature. Following chapters introduce new series of defense countermeasures based on suitable PRNG designs holding the unpredictability property. Chapter 5 introduces a proactive threshold cryptosystem for EPC tags. Three privacy-preserving solutions grounded on an anonymous secret sharing scheme are presented. The solutions aim at handling the problem of distributing secrets between manufacturers and vendors of EPC labeled objects. Chapter 6 goes further and tackles the problem of flawed designs on protocols that aim at establishing some security properties. A key establishment protocol is presented and verified using an automatic framework for the formal verification of security schemes. Chapter 7 concludes and gives directions for future work. and high-frequency (HF) bands (typically 125 kHz and 13.56 MHz) to ultra-high-frequency (UHF) bands (typically 868 MHz in Europe, 915 MHz in North America, and 950 MHz in Japan). Distances from which the RFID tags can be interrogated vary with the frequency band. It may vary from a few centimeters, while using LF and HF, to a few meters, while using UHF. Although no single technology is ideal for all applications [START_REF] Want | RFID explained: A primer on radio frequency identification technologies[END_REF], most of the modern RFID systems seem to be moving toward increasing the integration of longdistance passive tags into self-organizing wireless applications. This is the case with the modern Electronic Product Code (EPC) Gen2 tags.

The EPC technology originates from the MIT's Auto-ID Center (now called the Auto-ID Labs). It had been further developed by different working groups at EPCglobal Inc. [START_REF]The EPCglobal architecture framework[END_REF]. It is a layered service-oriented architecture to link objects, information, and organizations via Internet technologies. At the lowest layer, an identification system based on passive RFID tags and readers provides the means to access and identify objects in motion. This system possesses two primary interfaces: the Class 1 Generation 2 UHF Air Interface Protocol Standard (Gen2 for short) and Low Level Reader Protocol (LLRP).The former defines the physical and logical requirements for RFID readers (or interrogators) and passive tags (or labels). The latter specifies the air interface and interactions between its instances.

The next layer consists of a middleware composed of several services (such as filtering, fusion, aggregation, and correlation of events) that perform real-time processing of tag event data and collect the identifier of objects interrogated by RFID readers at different time points and locations. Data gathered by sensors, such as temperature and humidity, can also be aggregated at the middleware layer within tag events. The middleware forwards the complete set of events to a local repository where they are persistently stored (e.g., into a relational or XML database). The Reader Protocol (RP) and Reader Management (RM) interfaces define the interactions between a device capable of reading/writing RFID tags and the middleware. The middleware relies on a second interface called Application Level Event (ALE) for interaction with other applications (e.g., repository managers). At the top of the architecture, the EPC Information Services (EPCISs) offer the means to access the data stored in EPC network repositories. These EPCISs are implemented using standard Web technologies such as the Simple Object Access Protocol (SOAP) and Web Services Description Language (WSDL). Two additional services are defined for accessing the EPCIS of a given EPC network by external applications: a lookup service binding object identifiers and EPCISs, called the Object Name Service (ONS) [START_REF] Garcia-Alfaro | Evaluation of Anonymized ONS Queries[END_REF]; and a EPC discovery service (EPCDS) to perform searches with high-level semantics (i.e., similar to Web engines for Web page browsing).

Security attacks can target the different services of the EPC network architecture. They may succeed if weaknesses within the underlying technologies are not handled properly.

The exchange of information between EPC tags and readers, for example, is carried out via wireless channels that do not posses basic security attributes such as authenticity, integrity, and availability. This situation allows attackers to misuse the RFID service of an EPC network and perform unauthorized activities such as eavesdropping, rogue scanning, cloning, location tracking, and tampering of data. The attacker motivation for performing these activities is potentially high. The attacker can obtain financial gains (e.g., offering services for corporate espionage purposes).

Mechanisms at the RFID level of the EPC architecture must be applied to mitigate security risks. The implementation of new security features in EPC tags faces several challenges, the main one being cost. The total cost of an EPC tag was estimated in [START_REF] Sarma | Toward the 5 cent Tag[END_REF] to be less than 10 US dollar cents per unit. The goal is to maintain a low cost. Other challenges include compatibility regulations, power consumption, and performance requirements [START_REF] Sounderpandian | Models for cost-benefit analysis of RFID implementations in retail stores[END_REF].

Detecting and responding to security threats are becoming major concerns of information security researchers. However, and before going further in these activities, an evaluation of the threats in terms of importance must be done. In the sequel, we present such an evaluation. Our analysis of the threats is based on a methodology proposed by the European Telecommunications Standards Institute (ETSI) [START_REF] Etsi | Methods and protocols for security; part 1: Threat analysis[END_REF]. According to this methodology, we rank the threats in order of relevance. This assessment is intended to prioritize threats for future research on appropriate countermeasure mechanisms.

Remainder Outline: Section 2.2 outlines the methodology used for our analysis of threats.

Section 2.3 presents the identified threats and their risk assessments. Section 2.4 surveys traditional security defenses for RFID solutions. Section 2.5 concludes the chapter.

Threat Analysis Methodology

We define a threat as the objective of an attacker to violate security properties of a target system, such as authenticity, integrity, and availability. We define the attacker as an agent that is exploiting a vulnerability of the targeted system to carry out the threat. The exploitation of the vulnerability is defined as the attack. The security officer of the target system must put in place countermeasures to reduce the risk of the undesirable activities associated with all the threats. Given the difficulty of implementing countermeasures for every possible threat against a system, it is crucial for security officers to identify threats with potentially high impact and ensure the presence of countermeasures. This is indeed the objective of the threat analysis.

The methodology we use in this chapter is based on a framework proposed by the ETSI [START_REF] Etsi | Methods and protocols for security; part 1: Threat analysis[END_REF]. ETSI identifies three levels of threats: critical, major, and minor. Each level depends on estimated values for the likelihood of occurrence of the threat and its potential impact on a given system. The likelihood of a threat (cf. Figure 2.1(a)) is determined by the motivation for an attacker to carry out an attack associated to the threat versus the technical difficulties that must be resolved by the attacker to effectively implement the attack.

The three levels of likelihood are: (1) likely, if the targeted system is almost assured of being victimized, given a high attacker motivation (e.g., financial gains as a result of selling private information or disrupting network services) and lack of technical difficulties (e.g., a precedent for the attack already exists); (2) possible, if the motivation for the attacker is moderate (e.g., limited financial gains) and technical difficulties are potentially solvable (e.g., the required theoretical and practical knowledge for implementing the attack is available); and (3) unlikely, in case there is little motivation for perpetrating the attack (e.g., few or no financial gains resulting from the attack) or if significant technical difficulties and obstacles must be overcome (e.g., theoretical or practical elements for perpetrating the attack are still missing).

The impact of a threat evaluates the potential consequences on the system when the threat is successfully carried out. The following three categories are identified: (1) low, if the consequences of the attack can be quickly repaired without suffering from financial losses; (2) medium, if the consequences are limited in time but might result in few financial losses; and (3) high, if the attack results in substantial financial loss and/or law violations. The risk of a threat is ranked in [START_REF] Etsi | Methods and protocols for security; part 1: Threat analysis[END_REF] as minor, if it is unlikely to happen and it has low or medium potential impact, or if it is possible but with low potential impact. A threat is ranked as major if it is likely but has low potential impact, if it is possible and has medium potential impact, or if it is unlikely but has high potential impact. A threat is ranked as critical if it is likely and has high or medium potential impact, or if it is possible and has high potential impact. Through our experience with the ETSI methodology, we have observed that several threats are overclassified as major, when they would better be ranked as minor. We have slightly adapted the risk function in order to focus on truly critical or major threats. Figure 2.1(b) presents the adapted risk function. A threat is ranked as major when its likelihood is possible and its potential impact is medium. A threat is ranked as minor when it is unlikely to happen or when its potential impact is low. Minor risk threats typically require no countermeasures. Major and critical threats need to be handled with appropriate countermeasures. Moreover, critical threats should be addressed with the highest priority.

Evaluation of Threats

The communication channel between the components of the RFID system of an EPC network, that is, tags and readers, is a potentially insecure wireless channel. It is fair to assume that most of the threats on EPC configurations are going to target this level. We analyze threats targeting basic security features such as authenticity, integrity, and availability during the exchange of data between an RFID tag and a reader. We assume that attackers may only act from outside when trying to exploit the wireless channel between tags and readers, for example, the lack of authentication between these elements. We therefore assume that attackers do not have physical access neither to the components of the system nor to the organization itself. The reason we ignore direct physical access is because we assume the presence of other security mechanisms in the organization (e.g., physical access control and surveillance of workers). Attackers, however, may have access to information about the system and its components or services. We summarize in Table 2.1 the results of our evaluation.

Authenticity Threats

The EPC Gen2 standard is designed to balance cost and functionality [START_REF] Sarma | Toward the 5 cent Tag[END_REF]. However, security features on board Gen2 tags are minimal. They protect message integrity via 16bit Cyclic Redundancy Codes (CRC) and generate 16-bit pseudorandom strings. Their memory, very limited, is separated into four independent blocks: reserved memory, EPC data, Tag Identification (TID), and user memory. The absence of strong authentication on the tags opens the door to malicious readers that can impersonate legal readers and perform eavesdropping attacks. Figure 2.2 shows a simplified description of the steps of the Gen2 protocol for product inventory. In Step 1, the reader queries the tag and selects one of the following options: select, inventory, or access [START_REF]The EPCglobal architecture framework[END_REF]. Figure 2.2 represents the execution of an inventory query. It assumes that a select operation has been completed in order to single out a specific tag from the population of tags. When the tag receives the inventory query, it returns a 16-bit random string denoted as RN16 in Step 2. This random string is temporarily stored in the tag memory. The reader replies to the tag in Step 3 with a copy of the random string, as an acknowledgment. If the echoed string matches the copy of the RN16 stored in the tag memory, the tag enters the acknowledged state and returns the EPC identifier.

Observe that any compatible Gen2 reader can access the EPC. The traffic between tags and readers flows through non-authenticated wireless channels. Illegitimate collection of traffic might be slightly protected by reducing the transmission power or by sheltering the area. It is, although, theoretically possible to conduct eavesdropping attacks. We define forward eavesdropping as the passive collection of queries and commands sent from readers to tags; and backward eavesdropping as the passive collection of responses sent from tags to readers. Although the range for backward eavesdropping could be only of a few meters [START_REF]The EPCglobal architecture framework[END_REF], and probably irrelevant for a real eavesdropping attack, the distance at which an attacker can eavesdrop the signal of an EPC reader can be much longer. In ideal conditions, for example, readers configured to transmit at maximum output power, the signal could be received from tens of kilometers away. Analysis attacks inferring sensitive information from forward eavesdropping, for example, analysis of the pseudorandom sequences generated by the tags (denoted as RN16 in Figure 2.2), are hence possible. Replay attacks enabled by this inferred data are also possible. The absence of a strong authentication process also enables scanning attacks. Although, the distance at which an attacker can perform scanning is considerably shorter than the distance for forward eavesdropping. The use of special hardware (e.g., highly sensitive receivers and high gain antennas) could enable rogue scanning attacks.

We can conclude that outsiders equipped with Gen2 compatible readers and special hardware can theoretically eavesdrop the communication between readers and tags; or scan objects in motion if they successfully manage to place their readers at appropriate distances.

According to [START_REF]The EPCglobal architecture framework[END_REF], the information stored on an EPC tag is limited to an identification number. No additional data beyond the number itself is conveyed in the EPC. Additional information associated with the code must be retrieved from an EPCIS. However, an attacker accessing these data may determine types and quantities of items in a supply chain and sell the information to competitors or thieves. An attacker can obtain information from the EPC, that is, the manufacturer and product number. This information may be used for corporate espionage purposes by competitors, or for other attacks against other services of the EPC infrastructure. Clearly, the motivation of an attacker to carry out this threat must be rated as high, since attackers can sell their services to competitors, thieves, or any other individual looking for the objects tagged in the organization. The difficulties for performing both eavesdropping and rogue scanning, as shown by the example depicted by Figure 2.2, are solvable. This level of motivation and degree of difficulty lead to a likelihood that is possible. Regarding the potential impact of these threats (e.g., disclosure of information considered by the organization as confidential or trade secrets), it is high, since it may have serious consequences for an organization if an attacker offers the malicious service to competitors or to thieves. These threats are assessed as critical and need to be handled by appropriate countermeasures.

Using the codes eavesdropped or scanned by unauthorized readers, an attacker may successfully clone the tags by conducting, for example, skimming attacks. Indeed, an attacker can simply dump data and responses from a given tag, and program it into a different device. The objective of the attacker for performing the cloning of tags is the possibility for counterfeiting. The attacker may create fake EPC tags that contain data and responses of real tags and sell these counterfeit tags for profit. The forgery of legal tags can be performed without physical access to the organization. We rank the motivation of attackers to carry out the attacks associated with this threat as moderate since they can obtain some financial gain by offering this service to third parties. Current EPC specifications do not include any mechanism for Gen2 compatible readers to verify if they communicate with genuine or fraudulent tags. We thus rate the difficulties associated to this threat as solvable. This level of motivation and degree of difficulty lead to a likelihood that is possible. Regarding the potential impact of this threat, it is medium and thus the threat is assessed as major.

The lack of a strong authentication process in Gen2 tags also has consequences to the privacy of tagged object bearers. Indeed, interrogations of Gen2 tags give attackers unique opportunities for the collection of personal information (and without the consent of the bearer). This can have serious consequences, such as location tracking or surveillance of the object bearers. An attacker can distinguish any given tag by just taking into account the EPC number. Following a reasoning similar to the one used for the cloning threat leads to ranking the risk of the location tracking threat as major. This threat, as well as the cloning threat, must be handled by appropriate countermeasures.

Integrity and Availability Threats

Gen2 tags are required to be writable [START_REF]The EPCglobal architecture framework[END_REF]. They must also implement an access control routine, based on the use of 32-bit passwords, to protect the tags from unauthorized activation of the writing process. Other operations, also protected by 32-bit passwords, can be used in order to permanently lock or disable this operation. Although the writable feature of Gen2 tags is very interesting, it is also one of the least exploited features in current EPC scenarios (due probably to the lack of a strong authentication process, as reported in the previous section). Writable tags are hence locked in most of today's EPC applications. This option will, however, be extremely important in future EPC applications, especially on those self-organizing-based scenarios, where the addition of complementary information into the memory of the tags will require the unlocking of the writing process (e.g., to store routing parameters, locations, or time stamps). It is therefore important to analyze the risk of a tampering attack to the data stored by Gen2 tags, if they can be accessed in write mode from a wireless channel that does not guarantee strong authentication.

Figure 2.3 presents a simplified description of protocol steps for requesting and accessing the writing process that modifies the memory of a Gen2 tag.We assume that a select operation has been completed, in order to single out a specific tag from the population of tags.

It is also assumed that an inventory query has been completed and that the reader has a valid RN16 identifier (cf. apply the XOR operation to the contents of Steps 9 and 13. Other techniques to retrieve similar passwords have also been reported in the literature. For example, in [START_REF] Oren | Remote power analysis of RFID tags[END_REF] the authors present a mechanism to retrieve passwords by simply analyzing the radio signals sent from readers to tags. Although the proof-of-concept implementation of this technique is only available for Gen1 tags [START_REF]The EPCglobal architecture framework[END_REF], the authors state that Gen2 tags are equally vulnerable. The technical difficulties for setting up attacks to retrieve the password are therefore ranked as solvable. The likelihood of the tampering threat is classified as possible. Regarding the impact, it is ranked, because of some extreme scenarios, as high. For example, in the context of a pharmaceutical supply chain, corrupting data in the memory of EPC tags can be very dangerous: the supply of medicines with wrong information, or delivered to the wrong patients, can lead to situations where a sick person could take the wrong drugs. In these circumstances, the combination of likelihood and impact of the tampering threat lead to critical risk. The threat needs therefore to be addressed by appropriate countermeasures.

The aforementioned attacks enabled by retrieving the passwords, that protect both writing and self-destruction routines of Gen2 tags [START_REF]The EPCglobal architecture framework[END_REF], can be used as models to analyze the risk of threats like destruction of data or denial of service [START_REF] Han | New Security Problem in RFID Systems Tag Killing[END_REF]. Tag information can also be destroyed by devices that send strong electromagnetic pulses. Devices, such as the RFID-zapper [START_REF] Minime | RFID Zapper[END_REF], have been presented in the literature. We can also include here denial of service attacks consisting of jamming channels or flooding channels between tags and readers by sending a large number of requests and responses. For performing a jamming attack, the attacker uses powerful transmitters to generate noise in the range of frequencies used by readers and tags. In any case, the technical difficulties are ranked as solvable. The motivation of attackers to carry out these threats is rated as moderate, since they can obtain some financial gain by offering their malicious services. The likelihood of these two threats is hence classified as possible. However, since the impact of these threats represents to the victim temporal disruption of its operations rather than great financial losses, we rate the impact as medium, and so the risk of these two threats as major.

The final threat analyzed in this section, related to attacks to the integrity and availability of the back-end servers connected to RFID readers, was initially reported in [START_REF] Rieback | Is your cat infected with a computer virus? In Pervasive Computing and Communications[END_REF].

Rieback et al. uncover the possibility of using malware to attack back-end databases. Their approach classifies such malware into three categories: (1) exploits, (2) worms, and (3)

viruses. The exploits are attacks carried out within the information stored into RFID tags.

They target the security of middleware services connecting readers to back-end databases.

Worms and viruses are attacks that spread themselves over new RFID tags by using network connections (in the case of worms) or connectionless self-replication strategies (in the case of viruses). The malware reported in [START_REF] Rieback | Is your cat infected with a computer virus? In Pervasive Computing and Communications[END_REF] exploits the trust relationship between backend databases and the information sent by readers-obtained in turn from malicious tags. Rieback et al. consider that even if there is a very tiny window for storing information into an RFID tag, traditional attacks against information systems (e.g., buffer overflows and SQL injection attacks) might be condensed into a small string of bits harmful enough to break the security of a system. The authors present a proof-of-concept that uses tags carrying an SQL injection attack that compromises the security of the back-end layer of an ad hoc RFID setup. The work presented in [START_REF] Rieback | Is your cat infected with a computer virus? In Pervasive Computing and Communications[END_REF] is interesting and relevant. However, we think that the likelihood for those threats must be rated as unlikely, since no real-world vulnerabilities on the filtering and collection of middleware services specified by EPCglobal can be exploited at the moment. We conclude that even if the impact is potentially serious, due to its unlikely degree of likelihood, the threat is assessed as minor.

Survey of RFID Defense Countermeasures

Research on defense countermeasures for RFID technologies can be divided in two main categories: (1) hardware-based security primitives for RFID tags, and (2) security protocols using the hardware-based primitives. We review in this section a non-exhaustive list of contributions in both categories.

Hardware-Based Primitives

According to research presented in [START_REF] Sarma | Toward the 5 cent Tag[END_REF], the cost of passive EPC tags should not exceed 5 US dollar cents to successfully enable their deployment on worldwide scale. Of these 5 cents, only 1 or 2 should be used for the manufacturing of the integrated circuit (IC).

Another challenge is that the available layout area for the implementation of the IC is in the order of 0.25 mm2 which, considering current complementary metal-oxide-semiconductor (CMOS) technology, corresponds to a theoretical number of logic gates from 2000 to 4000.

Not all the barriers identified in [START_REF] Sarma | Toward the 5 cent Tag[END_REF] have been removed. Today, the EPC technology is more expensive than what it was originally anticipated (around 10 US dollar cents per unit in large quantities). The inclusion of additional features, especially for security purposes, may increase the total end-cost of tags up to 15 cents per unit or more. Although Moore's Law says that the cost of ICs will continue to decrease, cost of analogue devices (i.e., RF front-end of tags) is relatively stable and 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 clearly justified.

Since EPC tags are powered from the weak energy captured from a reader's electromagnetic waves, their current consumption also needs to be taken into account. This consumption varies according to the operation that is being performed (e.g., responding to a query or writing data into the memory) and other parameters such as the transmission rate, response delay, and memory technology. Most of the operations performed within the modern EPC tags consume about 5-10 µA (microamperes). Some special operations, such as write accesses, may consume more. The current consumption of new security primitives must be within this range to allow low-cost tag production. They must also work at the data rate of EPC applications. For example, some supply chain applications demand an average reading speed of about 200 tags/s. This leads to a data transmission rate from tag to reader, of about 640 kbps; and 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 refer the reader to [START_REF] Cole | Networked RFID Systems and Lightweight Cryptography -Raising Barriers to Product Counterfeiting[END_REF] for a more detailed description of aspects that must be considered during the design of new primitives.

Several security proposals aim at including cryptographic primitives on low-cost EPC tags.

However, not all the proposals meet the aforementioned constraints or guarantee secure designs. Existing implementations of one-way hash functions, such as MD4, MD5, and SHA-128/SHA-256, exceed cost constraints due to the required number of gates. According to [START_REF] Feldhofer | A case against currently used hash functions in RFID protocols[END_REF], this amounts of having from 7000 to over 10,000 logic gates. The use of cellular automata (CA) theory for the implementation of one-way functions [START_REF] Wolfram | Cryptography with cellular automata[END_REF] and encryption engines [SSC + 02] has been investigated for the implementation of cryptographic primitives on low-cost RFID tags. However, it has been proved that these implementations are insecure [START_REF] Bardell | Analysis of cellular automata used as pseudorandom patterngenerators[END_REF][START_REF] Blackburn | Comments on 'theory and applications of cellular automata in cryptography[END_REF].

The use of linear feedback shift registers and nonlinear feedback shift registers as underlying mechanisms for the implementation of low-cost one-way hash functions and pseudorandom number generators (PRNG), without appropriate measures that might make increase the cost, also lead to insecure implementations [START_REF] Meyer | Pseudorandom codes can be cracked[END_REF][START_REF] Menezes | Handbook of applied cryptography[END_REF]. Light-weight hardware implementations of standard block ciphers to implement one-way hash functions have been discussed. The use of elliptic curve cryptosystems (ECC) [START_REF] Menezes | Handbook of applied cryptography[END_REF] for the implementation of primitives for RFID tags has been discussed 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 [BGK + 06]. 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 3,500 gates with a current consumption of less than 9 µA at a frequency of 100 kHz. The encryption of each block of 128 bits requires about 1000 clock cycles. Although, it considerably simplifies previous implementations of the AES cryptosystem, for example, proposals presented in [START_REF] Mangard | A highly regular and scalable AES hardware architecture[END_REF][START_REF] Verbauwhede | Design and performance testing of a 2.29-GB/s Rijndael processor[END_REF] that require between 10,000 and over 100,000 gates, respectively, the design is still considered too complex for basic EPC setups [START_REF] Juels | RFID security and privacy: A research survey[END_REF].

More suitable encryption engine implementations can be found in [START_REF] Israsena | Securing ubiquitous and low-cost RFID using tiny encryption algorithm[END_REF][START_REF] Mace | ASIC Implementations of the Block Cipher SEA for Constrained Applications[END_REF]. The first reference presents the implementation of the tiny encryption algorithm (TEA) [START_REF] Wheeler | TEA, a Tiny Encryption Algorithm[END_REF].

It is implemented on an IC of about 3,000 gates with a current consumption of about 7 µA.

It fits the timing requirements of basic EPC setups where hundreds of tags must simultaneously be accessed by the same reader. For meeting the constraints, the implementation relies on very simple operators such as XOR, ADD, and SHIFT. 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 data encryption standard (DES) [START_REF] Menezes | Handbook of applied cryptography[END_REF]. Variants of the basic algorithm, such as eXtended TEA (XTEA), are however necessary for implementing one-way 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 scalable encryption algorithm (SEA). Given the relatively recent invention of these algorithms, their strength is not clear [START_REF] Cole | Networked RFID Systems and Lightweight Cryptography -Raising Barriers to Product Counterfeiting[END_REF].

There are other hardware-based security enhancements for RFID technologies not relying on the implementation of cryptographic primitives. Many signal-and power-based defenses, such as shielding of tags, use of noise and third-party blocker devices have been surveyed in [START_REF] Juels | RFID security and privacy: A research survey[END_REF]. 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], for example, Fishkin et al. propose the inclusion of low-cost circuitry on 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 in order to claim that a reader can be authorized to read a tag contents according to its physical distance. The use of trust [START_REF] Solanas | A distributed architecture for scalable private RFID tag identification[END_REF] and trusted computing [START_REF] Molnar | A scalable, delegatable pseudonym protocol enabling ownership transfer of RFID tags[END_REF] with similar purposes has also been discussed. the technical difficulties of performing attacks. However, due to the use of static identifiers embedded in the tags at manufacturing time, the location tracking issue is not solved.

Moreover, brute force attacks can break the secrets shared between readers and tags.

The use of public key cryptography and digital signatures is discussed in [START_REF] Juels | Squealing euros: Privacy protection in RFIDenabled banknotes[END_REF]. The authors address the protection of banknotes embedding the RFID tags. Their approach includes the possibility of deploying cryptographic protocols in RFID applications, but avoids the need to embed cryptographic primitives within the tags. The scheme consists of a public-key cryptosystem used by a central bank aiming to avoid banknote forgery and a law enforcement agency that aims at tracking banknotes. Both authorities, that is, central bank and law enforcement agency, 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. The central bank authority, using its private key, signs the unique serial number. The unique serial number of the banknote and its corresponding digital signature are printed on the banknote as optical data. In addition, the law enforcement agency encrypts with its public key 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 ciphertext 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. Now, a merchant that receives a banknote must verify first the digital signature, printed in the banknote as optical data, using the public key of the central bank. Second, the merchant must also verify the validity of the ciphertext stored in the banknote's tag.To do so, the merchant encrypts the digital signature, serial number, and random number stored in the tag's memory, 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, Juels and Pappu propose the use of a reencryption process that can be performed by the merchant without the necessity of accessing the private keys of the law enforcement authority. Indeed, based on the algebraic properties of the ElGamal cryptosystem [START_REF] Menezes | Handbook of applied cryptography[END_REF], the initial ciphertext can be transformed into a new unlinkable ciphertext only using the public key of the law enforcement authority [START_REF] Juels | RFID security and privacy: A research survey[END_REF]. This reencryption process is performed outside the tags. Integrity issues of this approach are discussed and fixed in [START_REF] Zhang | Integrity improvements to an RFID privacy protection protocol for anti-counterfeiting[END_REF]. However, the whole process and requirements for implementing the approach in [START_REF] Juels | Squealing euros: Privacy protection in RFIDenabled banknotes[END_REF][START_REF] Zhang | Integrity improvements to an RFID privacy protection protocol for anti-counterfeiting[END_REF] based on PUFs proposed in [START_REF] Gassend | Physical Random Functions[END_REF][START_REF] Gassend | Silicon physical random functions[END_REF], consists of a challenge-response scheme that probabilistically ensures unique identification of RFID tags. A back-end system 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 only ensured probabilistically. The exposition of tag identifiers to eavesdroppers and lack of randomness in tag responses, make the approach vulnerable to the location tracking threat.

Moreover, the great number of challenges that are necessary in the identification process increases the tag response delay and power consumption. Hence, this approach might not meet the constraints and requirements of the EPC technology.

An alternative approach 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 through the PUF technology presented in [START_REF] Skoric | Secret key generation from classical physics[END_REF]. Similar to the results presented in [START_REF] Juels | Minimalist cryptography for low-cost RFID tags[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 the internal physical structure of 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 on-board together with the use of signatures avoid leaking of a single identifier and increases the technical difficulties for an attacker to carry out the location tracking threat. The main drawback is the need of large storage space and reliable searching processes on back-end servers 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.

Following the trend of combining PUFs together with traditional cryptographic primitives and encryption engines, a modification of the tree-based hash protocols proposed in [START_REF] Molnar | Privacy and security in library RFID: Issues, practices, and architectures[END_REF] is presented in [START_REF] Bringer | Improved Privacy of the Tree-Based Hash protocols using Physically Unclonable Function[END_REF]. Using the notion of POKs introduced in [START_REF] Gassend | Physical Random Functions[END_REF] (i.e., application of a fixed hard-wired challenge to the PUF to obtain a unique secret), the authors guarantee the existence of internal keys in basic tree-based hash protocols, now physically obfuscated. They cannot be cloned by unauthorized parties. among all the other parties. Authentication is therefore achieved though the dispersion of secrets. The dispersion 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 readers to obtain the EPCs assigned to a pallet, for example, a situation where the number of shares obtained by readers is not sufficient to reach the threshold protects the tags from unauthorized scanning (i.e., unauthorized readers that cannot obtain the sufficient number of shares cannot obtain the EPCs either). The approach can be implemented on EPC Gen2 tags without requiring any change to the current tag specification. A limitation is the amount of tag memory space required for storing the shares. However, the shrinking of shares can allow the application of the scheme to current EPC tags. A more important problem is that the location tracking threat is not addressed. Indeed, the shares used in the approach are static. This problem must be solved before deployment of the scheme.

Concluding Summary and Remarks

At the beginning of this chapter we presented an analysis of threats to the RFID system of the EPC architecture. We identified different groups of threats that we consider relevant for further research. We ranked the eavesdropping, rogue scanning, and tampering threats as critical; and cloning, tracking, and denial of service threats as major. We concluded that they must be handled by appropriate countermeasures. We then surveyed in the sequel practical and theoretical security defenses that can be useful to reduce the risk of the identified threats. We looked at the different defenses from two different research perspectives. On the one hand, we surveyed research on hardware-based defenses that aim at providing additional security primitives on tags such as one-way hash functions, encryption engines, and physically unclonable functions (PUFs). On the other hand, we surveyed research on software protocols that make use of these new on-tag primitives for designing and implementing reliable algorithms for dealing with security and privacy issues.

We have also seen that the implementation of well-known cryptographic primitives is possible and allows the design of software protocols to reduce the risk of threats ranked as critical or major. The cost and requirements of these proposals are the main difficulties.

Indeed, they are too expensive for their deployment in supply chain scenarios based on the EPC technology. We have also surveyed the combination of cryptographic primitives together with the use of PUFs for the design of cost-effective solutions. These solutions present drawbacks, such as the sensitivity of PUFs to physical noise and the difficulty to model and analyze them. They are, however, promising solutions that successfully meet the implementation constraints and requirements for handling the set of threats reported in our work. For the second group, we conclude that the avoidance of on-tag cryptographic processes on current algorithmic solutions seems to lead the future directions of research in RFID security. In this sense, the use of secret-sharing schemes present clear advantages for the management of keys in the design of authentication protocols and to deal with privacy issues. The main drawback is the use of static shares, limiting the use of this approach for addressing the location tracking threat.

Chapter 3

Weak EPC Pseudorandom Generators

In Chapter 2 we have seen that the EPC Gen2 is an international standard that proposes the use of Radio Frequency Identification (RFID) in ubiquitous environments. It has been designed to balance cost and functionality. As a consequence, security on-board of EPC tags is often minimal. In fact, the security of EPC Gen2 tags is mainly based on the use of onboard Pseudorandom Number Generators (PRNGs), used to obfuscate the communication exchanges requested by RFID readers. It is also used to acknowledge the proper execution of password-protected operations. In this chapter we deepen our analysis on PRNGs as main security tool for low-cost RFID. Cryptographic suitable PRNG designs must satisfy unpredictability characteristics. Otherwise, an external adversary who eavesdrops the communication between readers and tags can compute the PRNG internal state when enough outputs of the generator are observed. If this happens, it might allow the adversary to bypass the security of the password-protected commands defined in the EPC Gen2 standard (e.g., the access and the kill commands). We report a weak PRNG designed specifically for EPC Gen2 tags in [CHTW08, CCY + 11]. We show that it is feasible to eavesdrop a small amount of pseudorandom values by using standard EPC commands and using them to determine the PRNG configuration that allows to predict the complete output sequence.

We conclude by drawing some ideas to solve the linearity problem found in the analysis section. Parts of this chapter have been previously published in [START_REF] Garcia-Alfaro | Practical Eavesdropping of Control Data from EPC Gen2 Queries with a Programmable RFID Toolkit[END_REF][START_REF] Melia-Segui | Analysis and improvement of a pseudorandom number generator for EPC Gen2 tags[END_REF][START_REF] Melia-Segui | A practical implementation attack on weak pseudorandom number generator designs for EPC Gen2 tags[END_REF].

Pseudorandom Number Generators for EPC Gen2

The design of PRNGs for EPC Gen2 tags is not an easy task due to the computational and memory restrictions that these tiny devices imply. Capabilities of this type of tags are so small that security features for the EPC Gen2 standard are expected to be implemented with a small amount of equivalent logic gates (GE), defined in the literature between 2,000 and 5,000 [START_REF] Ranasinghe | Networked RFID Systems and Lightweight Cryptography, Chapter 8, chapter An Evaluation Framework[END_REF]. This is a extremely small value if we consider that a standard hash function (the most simple cryptographic transformation), like SHA1, needs at least 8,120 GE (equivalent logic gates) to be implemented [START_REF] Feldhofer | A case against currently used hash functions in RFID protocols[END_REF].

Existing Proposals

Existing commercial Gen2 tags do implement a PRNG, as it is an EPC standard mandatory, but companies are often reluctant to present the design of their PRNGs. Some statistical artifacts on the PRNGs of commercial Gen2 tags have been reported in [START_REF] Melia-Segui | On the similarity of commercial EPC Gen2 pseudorandom number generators[END_REF]. Manufacturers simply refer to testbeds that show the accomplishment of some expected requirements, most of them for compatibility purposes. They fail to offer convincing information about the PRNGs designs [START_REF] Peris-Lopez | LAMED a PRNG for EPC Class-1 Generation-2 RFID specification[END_REF]. This is mostly security through obscurity, which is always ineffective in security engineering, as it has been shown with the disclosure of the PRNG used in the MIFARE Classic chip [GKM + 08] that has shown a vulnerable PRNG. for low-cost RFID tags. The shrinking generator is a well studied cryptographic design that combines two clocked linear feedback shift registers (LFSRs) [START_REF] Menezes | Handbook of applied cryptography[END_REF]. The output sequence of the first LFSR is used to discard some bits from the output sequence of the second LFSR. Some techniques presented in [START_REF] Meier | The self-shrinking generator[END_REF] can be used to attack the scheme.

Moreover, there are no evidences of how the proposal in [START_REF] Lee | The tag authentication scheme using selfshrinking generator on RFID system[END_REF] controls the irregularities of the generator output rate. This is an important drawback inherent to any shrinking generator scheme, since it can hint at the state of the main LFSR, and so breaking the security of

LFSR-based Pseudorandom Number Generators

Linear feedback shift registers (LFSRs) are an important tool for designing PRNG for EPC Gen2 tags. They lead to extremely efficient and simple hardware implementations. For instance, a 16-cell LFSR can be implemented with only 192 GE. An LFSR is a digital circuit that contains a shift register and a feedback function. The shift register is composed of n binary cells that share the same clock signal. Each time a bit is needed, the content of the register is shifted one cell, obtaining the most significant bit of the register in the previous state. The feedback function computes a new bit using some bits of the register, obtaining the less significant bit to be filled in the new state of the register. The feedback function of an LFSR is basically an exclusive OR logical operation of some cells content, named taps.

Although LFSRs can be implemented efficiently, their main drawback is that their sequences are high predictable [START_REF] Herlestam | On functions of linear shift register sequences[END_REF][START_REF] Chen | Linear dependencies in linear feedback shift registers[END_REF]. For example, let s k+1 , s k+2 , • • • , s k+2n be a sequence of 2n consecutive bits generated from an LFSR.

Let B = (b n , b n-1 , • • • , b 1 ) be
the feedback function of the LFSR. Then, the feedback function can be easily computed by solving the following equation system:

         s k+1 s k+2 • • • s k+n s k+2 s k+3 • • • s k+n+1 . . . . . . . . . . . . s k+n-1 s k+n • • • s k+2n-2 s k+n s k+n+1 • • • s k+2n-1                   b n b n-1 . . . b 2 b 1          =          s k+n+1 s k+n+2 . . . s k+2n-1 s k+2n          (3.1)
By solving Equation (3.1) we obtain the feedback polynomial coefficients. Despite the 2 n -1 period length generated by a n LFSR, the full sequence can be determined only with 2n consecutive bits due to the linearity of the system. This linearity must be handled before using LFSRs to build robust PRNGs. Several basic constructions can be used to hide linearity, while maintaining suitable statistical properties and long output periods. One of these techniques are filters. Filters use a non-linear feedback function as an input to the register. The filter should not be too simple to be weak but neither too complex, otherwise it would become the bottleneck of the generator. However, recent attacks to the MIFARE PRNG [GKM + 08] have demonstrated the vulnerability of this kind of generators when the non-linear function is not taken carefully.

Another approach to handle the linearity of an LFSR is to use a non-linear combination of multiple LFSRs to generate a unique output. Generally the output of one LFSR is used to select or combine the output of one or more LFSRs, in the same or different clock times.

Known examples of this approach are the Geffe, A5 or the Shrinking generator [START_REF] Schneier | Applied Cryptography[END_REF].

The output generated from these constructions is statistically weak, being vulnerable to correlation or side-channel attacks [START_REF] Joux | Algorithmic cryptanalysis[END_REF]. Moreover, the irregular output data rate from some of these constructions (e.g., the shrinking generator) is not suitable for PRNG used in security environments. Finally, generators with memory are another alternative. Additional memory can be used to add some non-linear information in between the clock steps of the LFSR. Besides the memory, also binary adders and carry registers should be used to complete this approach.

The different techniques of deterministic modifications of LFSRs explained so far are useful for keystream generators where sender and receiver can share a secret k as a key for the PRNG one-time pad communications. However, the specific communication model of EPC Gen2 systems uses another paradigm where sender and receiver cannot share any secret k. Instead of this, the low-power tag-to-reader communication is used to transmit in plain text the nonces to be used as a keystream for the reader-to-tag communication. This scenario allows other strategies for the linearity avoidance of LFSRs.

A first straightforward strategy is to suppress the LFSR itself and use a true random data source as a random number generator. Although this approach is theoretically sound, implementations of true random number generators obtain their randomness from the device energy and such energy is very scarce in an EPC Gen2 tag. As a result, the generator throughput cannot reach the minimal requirements of the EPC communication standard.

Having this problem in mind, Che et al. propose in [CHTW08, CCY + 11] the combination of true random numbers (trn) extracted from physical effects on tag, and LFSRs to increase the throughput of the generator while decreasing the predictability of the output sequence.

In the sequel, we deepen our analysis on the Che et al. proposal and show that it fails at handling the linearity of the LFSR output sequence.

The Che et al. Proposal

In [CHTW08, CCY + 11], Che et al. present a new PRNG for application in RFID tags.

Their system relies on an oscillator-based Truly RNG (TRNG), and exploits the thermal noise of two resistors to modulate the edge of a sampling clock and generate the true random bits (trn). Authors state the final system prevents potential attackers to perform any effective prediction about the generated sequence (even if the design is known) thanks to the white noise based cryptographic key generation.

After describing its TRNG oscillator-based core, the authors focus on design considerations specially regarding power consumption and output data rates trade-offs. Knowing the fact that the higher the frequency oscillation of the system, the higher the current (thus also power) consumption, the authors look for system level optimization in order to reduce the power consumption due to the low-power restrictions of RFIDs.

The optimization proposed by Che et al. relies on the combination of the TRNG and an LFSR (cf. Figure 3.1). Adding an LFSR to the TRNG lets the system reduce the clock frequency proportionally to the number of cells of the LFSR. Specifically, exploiting the initial state of a 16-bit LFSR combined with the addition of the generated truly random number (trn) for each cycle ring, allows the system to decrease the clock frequency with a 1 16 factor. Authors claim that [START_REF] Che | Networked RFID Systems and Lightweight Cryptography[END_REF]: "If we add 1-bit truly random number in the cycle ring as a random number seed, the output sequence of the LFSR will also be unpredictable and irreproducible as a TRNG.". We show in the next section that this claim does not hold.

Analyzing and Exploiting the Che et al. Proposal

Since the main property of a PRNG is to ensure the forward unpredictability of its generated sequence, the correctness of a PRNG can be measured with statistical tests applied to the output sequence.

We take the National Institute of Standards and Technology (NIST) suit test for checking the randomness deviations of a binary random sequence [START_REF]Random number generation[END_REF]. NIST testing algorithms NIST tests produce P-values summarizing the strength of the hypothesis. If P-values ≥ α, H 0 is accepted. It is not necessary that strictly all P-values hold this bound for the sequence to be considered as a good pseudorandom sequence. In fact, the NIST recommends that the proportion of test over the significance level, must fit in the interval

p ± 3 p(1 -p) m (3.2)
where p = 1α, and m is the sample size. A common value used in cryptography [START_REF]Random number generation[END_REF] to statistically confirm the randomness of the analyzed data would be α = 0.01, that means gives a clear evidence of a non-randomness due to linearity problems.

Exploiting the Linearity Weaknesses of the Scheme

As we have pointed out in Section 3.2, the main vulnerability of a PRNG based on a linear feedback shift register comes from its easy predictability due to its linearity properties.

Results presented in Table 3.1 show that the Binary Matrix Rank Test from the NIST statistical test suite fails for the Che et al scheme, providing information that the scheme does not succeed in avoiding the linearity of the underlying LFSR. A specific attack to break the Che et al. PRNG based on the inherent linearity of the LFSR was presented in [START_REF] Melia-Segui | Analysis and improvement of a pseudorandom number generator for EPC Gen2 tags[END_REF] and is next briefly described.

Notice that in the Che et al. scheme the pseudorandom sequence is produced by an LFSR XORed in its first cell with a truly random bit (cf. Figure 3.1). That means we can find a 2n pseudorandom output sequence of the proposed scheme identically equal to the one of the n-bit LFSR (without of the XORed true bit) in case that 2 consecutive random bits are 0. Such event will occur with probability 1/4 assuming bits are true random.

Attack description

Our scenario is composed by a Che et al. system that produces pseudorandom bits. Only a part of the pseudorandom output sequence, denoted by s a is known to the attacker, besides the size n of the LFSR. On the other hand, the seed (initial state) and the feedback polynomial coefficients remain secret to the attacker. The attack will succeed if the attacker can provide the LFSR feedback polynomial (cf. Figure 3.2). To generalize the attack, we also assume that the attacker cannot determine the first bit of the sequence, that means he has no information if a given s a sequence, with |s a | = 2n (the length of the sequence), has been affected by exactly two trn values (that means the attacker finds two exact LFSR rounds)

or the sequence has been modified by three trn values.

With probability 1 n , the sequence, s a with |s a | = 2n has been affected by exactly two trn and, in this case, the probability to obtain the 2n values of the LFSR despite the XORed trn is 1 4 (two consecutive zeros). That means that, with probability 1 4n , we can obtain 2n values of the LFSR that composes the system and with this sequence we are able to compute the feedback polynomial and the whole pseudorandom sequence. Now, assume that |s a | = 3n -1. If the sequence is divided into n subsequences of length 2n, we can ensure that one of these subsequences has been affected by exactly two trn.

P (B i = B 0 ) = n + 1 8n trn ⊕ LFSR(B 0 ) s 2 s 2n+1 s 4 s 3 ... s n s 3n-1 s n+2 s n+1 ... s 1 s 2n s 3 s 2 ... |2n|
Eq. 1

Eq. 1

Eq. 1 The remainder n -1 subsequences, are affected by three trn. However, notice that if the three trn are zeros, the n vectors of length 2n will give the same feedback polynomial.

B 1 B 2 B n (∀i = 1 . . . n)
The probability of such event is 1 8 . Then, from this fact, we can derive Equation 3.3 which provides the probability of success of an attack that analyzes a sequence with |s a | = 3n-1:

P success (3n -1) = 1 4 1 n + 1 8 n -1 n = n + 1 8n (3.3)
Obviously, the probability of success increases with |s a | since increasing the |s a | implies that more trn bits affect the sequence and then the probability of finding three consecutive zeros also increases. Figure 3.3 shows the probability of success of an attack with s a length for a particular system with an LFSR of length n = 16. Notice that only 160 bits (10n) are enough to perform a successful attack with probability higher than 50%, and 464 bits (29n) implies more than a 90% of success probability.

Obtained Results

To test the correctness of the theoretical evaluation, the described attack is implemented over the same ten pseudorandom sequences (T i ) used to execute the NIST tests (cf. Section

3.3.1).

The first analysis validates that the probability of finding the feedback polynomial matches the one described in Equation 3.3. In this case, the algorithm takes |s a | = 3n -1 bits from T i starting at a random position and tries to attack the system by finding n equal feedback polynomials. The operation is repeated one thousand times for each test sequence T i . Attack success rates are reported in Table 3.2. Notice that they are close to the theoretic value (n+1) 8n with n = 16 ≈ 0, 132.

The second analysis provides the number of bits needed to achieve a successful attack.

Ten different attacks are performed for every T i data sequence taking the first bit of s a at random. Results presented in Table 3.3 show the number of bits for a successful attack in the worst case, that is the attack that needs a major number of bits. Notice that, although taking the worst case, the number of bits is significantly lower than the whole period 2 16 -1.

Attack Implementation and Empirical Results

In this section, we present an empirical version of our proposed attack on a real EPC Gen2 setup. We describe the RFID devices used to implement the attack, the techniques used to eavesdrop the PRNG from the RFID communication, and the obtained results.

Background on the IAIK UHF Demo Tag

The IAIK UHF demo tag [SIC07] is a programmable device intended for developing new commands or functionalities to the EPC Gen2 standard. It allows, moreover, to verify the new functionality using compliant EPC Gen2 readers. We use this prototype to demonstrate and validate the concepts discussed in the previous sections.

The demo tag consists of four main components: an antenna, a radiofrequency (RF) frontend, a programmable microcontroller, and a firmware library. The antenna captures the energy emitted by the reader and powers up the RF front-end of the tag. The RF frontend demodulates the information encoded in the signal. The resulting data feeds the programmable microcontroller which, in turn, computes a response. To compute the response, the programmable microcontroller executes a software implementation of the EPC Gen2 protocol, implemented as a firmware library. The response is then modulated by the RF front-end and backscattered to the reader. We present in the sequel a condensed background on these four components. More details can be obtained in [SIC07, APF + 07].

Antenna and RF Front-end

The antenna connected to the RF front-end consists of a 17cm dipole antenna. The RF front-end utilizes a two-stage charge-pump rectifier to perform amplitude-shift keying (ASK)

demodulation. It demodulates the information stored in the signal transmitted on the readerto-tag channel. It does, indeed, rectification, voltage multiplication, and envelope detection all at once [APF + 07]. The power extracted by the rectifier from the RF field emitted by the reader from most compliant EPC Gen2 readers amounts to about 2.4mW. Since this is not enough to power the microcontroller, the demo tag adopts a semi-passive approach, meaning that although the analog parts are powered by the energy harvested from the reader, the digital parts (e.g., the programmable microcontroller) are powered by an external power supply or by an on-board battery. The backscattering of the information computed by the programmable microcontroller consists of the reflected power of the antenna. This power is indeed generated according to the transmitted data. The RF front-end of the demo tag combines both ASK and PSK (phase-shift keying) to modulate information. The backscattering components used by the demo tag to modulate the tag-to-reader signals consist of a resistor, a capacitor, and a fast-switching transistor placed close to the antenna. These components are controlled by the programmable microcontroller.

Programmable Microcontroller and Firmware Library

The programmable microcontroller connected to the RF front-end of the demo tag consists of an Atmel AVR ATmega128 (cf. http://www.atmel.com/). It contains all the logic and memory necessary for the demo tag. The ATmega128 is an 8-bit microcontroller based on the AVR architecture. The memory banks of the microcontroller, 128KB of flash memory and 4KB of data memory, can be addressed by three independent 16-bit registers.

In addition, the ATmega128 has 32 registers of 8-bits. All 32 registers can act as the destinations of the ATmega128 arithmetic operations. The microcontroller operates exactly one instruction per clock cycle, at frequencies up to the order of 16MHz. An external crystal oscillator connected to the demo tag provides the 16MHz signal to the microcontroller. Three

Eavesdropping of Control Sequences and Practical Results

Due to the Gen2 RF power range characteristics, a realistic attack should only consider reader-to-tag queries because they are much easier to be eavesdropped [START_REF] Peris-Lopez | LAMED a PRNG for EPC Class-1 Generation-2 RFID specification[END_REF].

Some reader-to-tag queries include pseudorandom sequences (hereinafter denoted as RN16s)

that are computed from the on-board PRNG included on the EPC tags. Table 3.4 shows the mandatory operations for Gen2 reader-to-tag protocol and the minimum number of RN16s involved in each operation. Notice that the write command generates a minimum of eight RN16s for its proper execution. For a full EPC code writing, up to six RN16s must be generated to cover the reader-to-tag communication, besides the two previously generated pseudorandom sequences for the inventory query and the handle descriptor [START_REF] Epcglobal | EPC Radio-Frequency Identity Protocols Class-1 Generation-2 UHF RFID Protocol for Communications at 860-960 MHz[END_REF]. is enough to obtain the feedback polynomial of the LFSR with a confidence of about 42%.

Operation

This value is consistent with the analytical results we anticipated in the previous section, and that are depicted in Figure 3.3. The complete set of experiments that we summarize in Figure 3.6 consists of ten series of write commands. Each of these series generates a total of 1,000 write challenges from the A829EU reader to the demo tag. As a result, 8,000 RN16s, i.e., 128,000 pseudorandom bits, are captured in total. These pseudorandom bits are computed from the

Concluding Summary and Remarks

Pseudorandom Number Generators (PRNGs) are the crucial components that guarantee the confidentiality of EPC Gen2 [START_REF] Epcglobal | EPC Radio-Frequency Identity Protocols Class-1 Generation-2 UHF RFID Protocol for Communications at 860-960 MHz[END_REF] RFID communications. In this chapter, we have described the problems of using linear feedback shift registers (LFSRs) as underlying mechanisms for the implementation of low-cost PRNGs. Without appropriate measures that increase their cost, the linearity of LFSR-based PRNGs lead to insecure implementations.

We have analyzed a cost-effective PRNG proposal for EPC Gen2 devices presented by Che [START_REF] Garcia-Alfaro | A Multiple-Polynomial LFSR based Pseudorandom Number Generator Design for EPC Gen2 Systems[END_REF][START_REF] Melia-Segui | Multiplepolynomial LFSR based pseudorandom number generator for EPC Gen2 RFID tags[END_REF][START_REF] Melia-Segui | J3Gen: A PRNG for Low-Cost Passive RFID[END_REF].

Chapter Outline: Section 4.1 presents a high-level description of the J3Gen proposal.

Section 4.2 presents a sample execution of J3Gen based on a 16-bit LFSR-based version.

Section 4.3 determines an optimal selection of parameters to satisfy the EPC Gen2 requirements while guaranteeing a proportional degree of security. Section 4.4 evaluates the statistical properties of the proposed setup for EPC Gen 2, and evaluates its hardware complexity and power consumption. Section 4.5 discusses on the benefits and limitations of our proposal with regard to related work. Section 4.6 closes the chapter.

Proposal Design

The main challenge to obtain an efficient PRNG is how to guarantee the generation of sequences with (almost) true random properties, while also addressing efficiency and computational complexity. Indeed, the low power, chip area and output rate (among other constraints) of the EPC Gen2 technology makes the task of improving security harder. This is the case of true random number generator (TRNG) designs based on, e.g., thermal noise, high frequency sampling or fingerprinting, whose requirements of power consumption or computational complexity for full-length real-time generation of random sequences fall out of EPC Gen2 standards [START_REF]The EPCglobal architecture framework[END_REF]. We propose to address this problem by combining a physical source of true randomness and a deterministic linear feedback shift register (LFSR). That is, leveraging the physical source system requirements with the efficiency of LFSRs for hardware implementations.

Sample PRNG Execution

Once described the logic components of the system, we depict now a sample execution round with our proposal. Table 4.1 shows a sample selection of parameters to construct a 16-bit version of J3Gen. Table 4.2 specifies as well a possible selection of feedback polynomials. The LFSR size n has been fixed to 16 and the total number of different feedback polynomials m has been set to 8. We take as the initial LFSR state the value v 0 = 0x1 (hexadecimal notation that represents a logical 1 in the less significant bit). S 16 S 15 S 14 S 13 S 12 S 11 S 10 S 9 S 8 S 7 S 6 S 5 S 4 S 3 S 2 S 1 Tx v 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 Coeff. x 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10 x 11 x 12 x 13 x 14 x 15 x 16 p 1 (x) 1 0 0 0 1 1 1 0 0 0 1 0 0 0 0 1 1: 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2: 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3: 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4: 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 5: 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 6: 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 7: 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 8: 1 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 9: 0 1 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 10: 1 0 1 0 0 1 1 1 1 1 0 0 0 0 0 0 0 11: 1 1 0 1 0 0 1 1 1 1 1 0 0 0 0 0 0 12: 1 1 1 0 1 0 0 1 1 1 1 1 0 0 0 0 0 13: 1 1 1 1 0 1 0 0 1 1 1 1 1 0 0 0 0 14: 1 1 1 1 1 0 1 0 0 1 1 1 1 1 0 0 0 15: 0 1 1 1 1 1 0 1 0 0 1 1 1 1 1 0 0 Coeff. x 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10 x 11 x 12 x 13 x 14 x 15 x 16 p 2 (x) 0 0 0 1 1 1 1 0 0 0 1 0 0 0 0 1 16: 0 0 1 1 1 1 1 0 1 0 0 1 1 1 1 1 0 17: 1 0 0 1 1 1 1 1 0 1 0 0 1 1 1 1 1 18: 1 1 0 0 1 1 1 1 1 0 1 0 0 1 1 1 1 19: 1 1 1 0 0 1 1 1 1 1 0 1 0 0 1 1 1 20: 1 1 1 1 0 0 1 1 1 1 1 0 1 0 0 1 1 21: 0 1 1 1 1 0 0 1 1 1 1 1 0 1 0 0 1 22: 1 0 1 1 1 1 0 0 1 1 1 1 1 0 1 0 0 23: 0 1 0 1 1 1 1 0 0 1 1 1 1 1 0 1 0 24: 0 0 1 0 1 1 1 1 0 0 1 1 1 1 1 0 1 25: 0 0 0 1 0 1 1 1 1 0 0 1 1 1 1 1 0 26: 0 0 0 0 1 0 1 1 1 1 0 0 1 1 1 1 1 27: 1 0 0 0 0 1 0 1 1 1 1 0 0 1 1 1 1 28: 1 1 0 0 0 0 1 0 1 1 1 1 0 0 1 1 1 29: 1 1 1 0 0 0 0 1 0 1 1 1 1 0 0 1 1 30: 0 1 1 1 0 0 0 0 1 0 1 1 1 1 0 0 1 Coeff. x 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10 x 11 x 12 x 13 x 14 x 15 x 16 p 3 (x) 1 0 1 1 1 1 1 0 0 0 1 0 0 0 0 1 31: 1 0 1 1 1 0 0 0 0 1 0 1 1 1 1 0 0

Coeff. x 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10 x 11 x 12 x 13 x 14 x 15 x 16 p 4 (x) 0 0 1 0 1 1 0 0 0 1 1 0 0 0 0 1 32: 1 1 0 1 1 1 0 0 0 0 1 0 1 1 1 1 0

Selection of Parameters

Although J3Gen can be used as a security tool in multiple lightweight ubiquitous computing scenarios, we look for compatibility with the EPC Gen2 requirements. The EPC standard [START_REF]The EPCglobal architecture framework[END_REF] does not define any hardware requirement for the generation of the 16bit pseudorandom sequences, nor any other hardware security features regardless of the CRC which shares the LFSR scheme with our proposal (cf. Section 4.1). Authors in the literature do not agree about the implementation area which can be devoted to security.

Using logical gates equivalence (GE) to measure the implementation size (regardless of the manufacturing process), some authors defend that only 2,000 GE can be used for security [START_REF] Juels | RFID security and privacy: A research survey[END_REF][START_REF] Weis | Security and Privacy Aspects of Low-Cost Radio Frequency Identification Systems[END_REF], while others increase the range from 2,000 to 5,000 [START_REF] Ranasinghe | Networked RFID Systems and Lightweight Cryptography, Chapter 8, chapter An Evaluation Framework[END_REF]. In this chapter, the worst case is assumed. Hence, J3Gen looks for a suitable trade-off between security and hardware implementation cost, that is, maximizing the security inside the proposed implementation area of 2,000 GE. This implementation area is approximately 10, 400 µm 2 using current 130 nm process for static CMOS designs.

Hardware

The size and design of each component of J3Gen implies a specific hardware implementation, being the LFSR size (n) and the number of implemented feedback polynomials on tag (m) the parameters that most significantly impact on the hardware complexity of our design. Furthermore, both parameters are also the key parameters from the security point of view. Hence, we shall look for the different combinations of n and m within the hardware implementation boundaries to find the best security implementation for this purpose. The As shown in Table 4.4, the Polynomial selector module implementation hardly depends on the total number of polynomials m that will be used as a pool of feedback polynomials.

Furthermore, the exact selection of the m polynomials also affects the total number of GE needed for the implementation. To determine the GE number for this module, a first approach could be to analyze all combinations of the m possible polynomials and take the combination that needs the minimum GE. Although this strategy seems to be the best one regarding the implementation purposes for its efficiency (it will end up with the simplest implementation possible), it is not a good choice regarding security needs. As we will describe in the next section, the exact value of the m polynomials (not the value m itself) can be seen as a security key (since, together with the trn values, it determines the output of the pseudorandom sequence). Then, an attacker could determine the exact combination of the used polynomials simply by finding the combinations that produce the optimal implementation in GE. To avoid that, we compute the GE needed in this module by analyzing all the possible polynomial combinations and then take the worst possible case. Since any chosen combination of the m polynomials is equally probable, an attacker cannot discard any of them regarding its implementation suitability. Based on this strategy, we show in Table 4.4 the resulting GE upper bound values.

We then provide the physical source of randomness assumed for our generator. For the gate equivalence of this component, we based our estimations on previous works presented in [START_REF] Ranasinghe | Networked RFID Systems and Lightweight Cryptography, Chapter 8, chapter An Evaluation Framework[END_REF] and [START_REF] Paar | New Designs in Lightweight Symmetric Encryption[END_REF]. The physical source of randomness that we assume consists of the thermal-noise oscillator presented by Che et al. in [CHTW08, CCY + 11], but specified and modeled in our work as proposed in [START_REF] Petrie | Modeling and simulation of oscillatorbased random number generators[END_REF] and [START_REF] Zhou | An ultra-low power CMOS random number generator[END_REF].

From Table 4.4, it can be extracted that implementations using up to 32 cells for the LFSR are roughly EPC Gen2 suitable from the hardware perspective. Also, a combination of large LFSR with a small pool of polynomials (e.g., n = 64 and m = 8) offers a possible solution, regarding hardware constrains (bold values in the Total row). In the next subsection, we overview the security properties of our scheme for those parameters that fit the hardware constrains, discarding implementations surpassing the available implementation area, established in 2,000 GE.

Security

EPC Gen2 security relies on the PRNG utilization, and how the PRNG ciphers the Access or Kill operations [START_REF]The EPCglobal architecture framework[END_REF] to avoid eavesdroppers to obtain the cleartext of the transmitted sequences. That is, the security of an EPC Gen2 PRNG is based on the unpredictability of its output. In J3Gen, such unpredictability is based on the non-linearity module that depends on the combination of the selected m feedback polynomials, and the feedback polynomial update rate . In our scenario, assuming that n, the length of the LFSR, is a public value, the knowledge of the exact combination of m feedback polynomials would allow to an attacker to predict the output sequence. In that context, since such polynomials are kept secret, they may be considered as the secret key of our PRNG. Then, the security strength of J3Gen can be measured as a key length, understanding each key as every different possible m feedback polynomial combination. In order to achieve the best statistical properties, feedback polynomials of LFSRs shall be primitive [START_REF] Menezes | Handbook of applied cryptography[END_REF]. Table 4.5 shows, for each LFSR length n, the total number of existing primitive polynomials. Given such value, each possible number of m chosen feedback polynomials determines the total available combinations that can be taken to implement our scheme. Each combination represents a possible key, so the powers of the values of the fourth column (labeled as Possible combin.) in Table 4.5 determines the length of the key (in bits). At this point, it is worth mentioning that different authors point out that a security of 80 bits is adequate for low-cost RFID [PPR09, BKL + 07], then all our combinations (except the first one) provide sufficient key length. and m = 32. For that reason, we determine the best parameters to choose in terms of GE efficiency with respect to the key length. Taking that measure, we obtain that the best parameter configuration is n = 32 and m = 16, where the ratio between the key length and GE is maximized (last column of Table 4.5). That is, using an LFSR register with 32 cells (n = 32) and 16 feedback polynomials (m = 16) implemented on the tag.

LFSR

Remarks

Regardless the parameters values, the core of the J3Gen generator is an LFSR with multiple polynomials (instead of a single one). The polynomial generator from a simple n-cell LFSR with period 2 n -1 can be determined with only 2n bits due to the linearity of this method, by using a system of n equations or the Berlekamp-Massey algorithm [START_REF] Massey | Shift-register synthesis and BCH decoding. Information Theory[END_REF]. The linearity of J3Gen is avoided with the following technique. The parameter described in Section 4.1 avoids the generation of more than consecutive bits from each LFSR polynomial.

Depending on the level of desired security, can be bounded by 1 ≤ ≤ n -1. Moreover, each n-bits pseudorandom sequence is generated by at least two different polynomials.

An attacker aiming to predict the J3Gen output, has to synchronize its output with the beginning of a feedback polynomial generated sequence, obtain the feedback polynomial from 2n using the method described above, and repeat the same operation for each m feedback polynomials. Here, the attacker has to face with the uncertainty added by the feedback update rate ( ). For example, using the selected parameters n = 32 and m = 16, if = 31 it means there would be up to 4 possible solutions for each system of equations, that is, up to 4 possible feedback polynomials generating that sequence. If = 25 then the possible solutions are up to 16,384, for = 21 the possible solutions increase to 4,194,304, etc. The extreme case would be = 1 where all 67 million primitive feedback polynomials would be equally probable (cf. Table 4.5). Thus, the smaller the polynomial update cycle , the harder the attack because more bits would be needed to disclose all m feedback polynomials. For instance, a = 31 needs about 1,400 bits to obtain all primitive polynomials, = 25 needs about 134,000 bits, and = 21 needs about 33 million bits. Hence, depending on the desired level of security, the attack will need a longer output sequence of consecutive bits. Equation 4.1 bounds the probability of success of each attack to 2n bits, where p i (x) are the obtained polynomials and P sel are the m implemented polynomials on the generator.

1 2 n-+1 ≤ P (p i (x) ∈ P sel ) ≤ 1 (4.1)
If further security is desired, the pool of polynomials can include non primitive polynomials besides primitive polynomials (avoiding those leading to absorbing states), increasing the complexity of the system and decreasing the success odds of a brute force attack.

EPC Gen2 Suitability

Once the parameters have been fixed based on the hardware constraints and the security requirements discussed in previous sections, we now evaluate the proposed scheme for its implementation, and the restrictions imposed by the EPC standard. We analyze two important parameters of J3Gen: statistical requirements stated by the EPC Gen2 standard for pseudorandom sequence generation, and power consumption.

Statistical Performance

Detailed in the EPC Gen2 standard [START_REF]The EPCglobal architecture framework[END_REF], the requirements for the pseudorandom sequence generation can be summarized as follows:

1. Any single 16-bit sequence s drawn from the generator shall confirm Equation 4.2.

P min = 0.8 2 16 < Prob(S) < P max = 1.25 2 16 (4.2)
2. Among a tag population of up to ten thousand tags, the probability that any two tags simultaneously generate the same 16-bit sequence shall be less than 0.1%.

3. The chance of guessing the next 16-bit sequence generated by a tag shall be less than 0.025% even if all previous outputs are known to an adversary.

To confirm the suitability of the current design of J3Gen for handling the statistical and randomness requirements defined above, different pseudorandom sequences using the parameters defined in Section 4.3 shall be generated. The three EPC Gen2 statistical requirements tests are presented. To accomplish these tests, 30 million 16-bit pseudorandom sequences are generated using an implementation of the J3Gen design. This dataset size is chosen since it is the minimum necessary for a truly generated random sequence to accomplish the proposed requirement [START_REF] Melia-Segui | Multiplepolynomial LFSR based pseudorandom number generator for EPC Gen2 RFID tags[END_REF].

First, the probability of occurrence of any given value shall lie between probabilities defined in Equation 4.2. The results shown in Figure 4.3 confirm that, after analyzing 30 million 16-bit sequences, the probability of occurrence of any given value lies between the defined boundaries. Furthermore, J3Gen achieves similar statistical results with Random.org true random sequences [START_REF] Haahr | True random number service[END_REF], based on its frequency properties.

The second property for building an EPC Gen2 compliant PRNG requires that two simultaneous identical sequences must not appear with more than 0.1% probability for a population up to 10,000 tags. To test this property, 10,000 instances of J3Gen, initialized at random, are used to simulate the test scenario. We conducted ten tests, running 1,000 iterations per Finally, to statistically confirm the fulfillment of the third property, we computed the degree of dependence of the ongoing bits regarding their predecessors, using the same pseudorandom sequences. Based on the results shown in Table 4.6, we can confirm that the generated sequences are not predictable within the requested correlation of 0.025%.

Power Consumption

The energy used for a (cryptographic) operation depends on the average power and the duration of the computation. For passively powered devices such as RFID tags, the average power transmitted from the reader to the tag is relatively small (although, in general terms, the reader can supply the power during all the operation time [START_REF] Feldhofer | Hardware Implementation of Symmetric Algorithms for RFID Security[END_REF]). Standard CMOS transistors is the current choice of most digital circuit designs built for low power consumption and robustness [START_REF] Ranasinghe | Networked RFID Systems and Lightweight Cryptography, Chapter 8, chapter An Evaluation Framework[END_REF]. Feldhofer et al. have estimated the average power budget for cryptographic operations in 4 µW at five meters to the reader [START_REF] Feldhofer | Hardware Implementation of Symmetric Algorithms for RFID Security[END_REF]. Therefore, it is important for the implementation of J3Gen to not surpass the available power budget.

Analytical methods for estimating the CMOS dynamic power dissipation can be adapted to the design of J3Gen [START_REF] Ranasinghe | Networked RFID Systems and Lightweight Cryptography, Chapter 8, chapter An Evaluation Framework[END_REF]. Indeed, using custom values adapted to the J3Gen design, the average power consumption is estimated in P avg = 178 nW (readers can refer to [START_REF] Melia-Segui | Multiplepolynomial LFSR based pseudorandom number generator for EPC Gen2 RFID tags[END_REF] for details).

After defining the design of the digital core of J3Gen based on GEs (cf. Section 4.3), we conduct an electronic circuit simulation of the proposed J3Gen construction, using verylarge scale integration (VLSI). The simulation language SPICE1 is used to simulate the circuit, and the LTSpice IV software is used to represent the circuit using logical gates. The resulting simulation also allows us to demonstrate the fundamental concepts of the current construction of J3Gen and confirm its validity as a stand-alone device.

Power dissipation is one of the most important factors in VLSI design and its technology choice. Therefore, accurate simulation of CMOS power dissipation using languages such as SPICE is highly desirable [START_REF] Kang | Accurate simulation of power dissipation in VLSI circuits[END_REF]. To precisely evaluate the power consumption of our design it is necessary to provide libraries with parameter models of the specific technology which is simulated. These libraries include a variety of CMOS parameters modeling the transistor behavior and parasitic circuit elements. Using library models, which can be theoretically modeled or hardware measured, the precision of the calculations is improved The analysis targets the average power consumption of J3Gen, in order to evaluate its implementability in a real EPC Gen2 tag. Figure 4.4 depicts the PRNG power consumption during one 16-bit sequence, generated with LTSpice IV and the PTM libraries.

The simulated average power consumption for the 16-bit sequence generation is 156.3 nW, which is consistent with the aforementioned dynamic CMOS power estimation. The simulated power consumption is also under the average power consumption requirements for cryptographic operations in RFID tags proposed by Feldhofer et al. [START_REF] Feldhofer | Hardware Implementation of Symmetric Algorithms for RFID Security[END_REF].

Discussion on Related Work Results

Although RFID is becoming an active research field, very few PRNG designs for lightweight The design in [START_REF] Lee | The tag authentication scheme using selfshrinking generator on RFID system[END_REF] is an optimized variant of the shrinking generator [START_REF] Coppersmith | The shrinking generator[END_REF], a well studied cryptographic design that combines two clocked linear feedback shift registers (LF-SRs) [START_REF] Menezes | Handbook of applied cryptography[END_REF]. The output sequence of the first LFSR is used to discard some bits from the output sequence of the second LFSR. However, it is worth pointing out that some techniques presented in [START_REF] Meier | The self-shrinking generator[END_REF] can be used to attack the scheme. Moreover, there are no evidences of how the proposal in [START_REF] Lee | The tag authentication scheme using selfshrinking generator on RFID system[END_REF] controls the irregularities of the generator output rate. This is an important drawback inherent to any shrinking generator scheme, since it can hint at the state of the main LFSR, and so breaking the security of the generator.

The design in [START_REF] Peris-Lopez | LAMED a PRNG for EPC Class-1 Generation-2 RFID specification[END_REF] is based on a software engineering programming methodology, to automatically derive a set of routines that build a 32-bit PRNG. The hardware implementation of the resulting design is estimated by the authors to 1566 logic gates.

An exhaustive statistical analysis confirms that the proposal successfully satisfies the EPC Gen2 statistical expectations. However, no evidences of further achievements other than hardware complexity and statistical behavior are provided. A complete security analysis is missing. Moreover, the inherent peculiarity of their construction methodology obscures potential comparison with other designs in the cryptographic literature.

The last example, presented in [CHTW08, CCY + 11], is also a variant of the shrinking generator discussed above, but based on a physical source of randomness that handles the linearity of an underlying LFSR. However, the work presented in [START_REF] Melia-Segui | Analysis and improvement of a pseudorandom number generator for EPC Gen2 tags[END_REF][START_REF] Melia-Segui | A practical implementation attack on weak pseudorandom number generator designs for EPC Gen2 tags[END_REF], and summarized in Chapter 3, proves that the generator scheme can be successfully attacked with very few observations. Indeed, and assuming a 16-bit version of the generator, it was proved that the feedback polynomial can be predicted with a probability higher than 50% by simply capturing 160 bits; and 90% by capturing 464 bits. Therefore, the scheme does not meet any security standard.

The PRNG design presented in this chapter can be applied to current lightweight security proposals in wireless sensor networks, like the one-time-pad encryption scheme by Dolev et Liu and Peng [START_REF] Liu | True random number generator in RFID systems against traceability[END_REF], and Tounsi et al. [START_REF] Tounsi | KEDGEN2: A key establishment and derivation protocol for EPC Gen2 RFID systems[END_REF]. Since the proposed PRNG combines an LFSR with a non-linear technique (multiple polynomials) which was not used before in security scenarios, no references or previous security analysis can be provided. and m (number of polynomials). The proposed architecture results in a security equivalentkey size of 372 bits, in opposition to the linearity of a single LFSR generator. We have validated the hardware complexity of the design and its suitability with regard to the EPC Gen2 standard. Furthermore, we have considered the randomness requirements through a statistical analysis and the power consumption through an evaluation based on CMOS parameters and SPICE language simulation. Besides EPC Gen2 compatibility presented in this chapter, stronger security can be obtained by adapting the main parameters of J3Gen.

Concluding Summary and Remarks

Chapter 5

Proactive Threshold Cryptosystem for

EPC Gen2 Tags

We present a second series of EPC Gen2 defense countermeasures, in addition to the PRNG presented in Chapter 4. The countermeasures aim at protecting the distribution of secrets between EPC readers and tags, e.g., passwords required to unlock the operation that protects a tag from unauthorized activation of the writing process. Our proposal can be used as a data-preserving mechanism to exchange the secrets from manufacturers to vendors. It relies on the use of a proactive anonymous threshold cryptosystem. The scheme allows onboard self-renewal of shares with secret preservation between asynchronous parties. The renewal process is based on the randomness provided by the on-board PRNG of a tag. Parts of this chapter have been previously published in [START_REF] Garcia-Alfaro | Proactive threshold cryptosystem for epc tags[END_REF][START_REF] Garcia-Alfaro | A Proactive Threshold Secret Sharing Scheme Handling Gen2 Privacy Threats[END_REF].

Chapter Outline: Section 5.1 surveys related work. Section 5.2 presents the formalization of our proposal. With regard to the list of threats reported in Chapter 2, three solutions are presented. The first two solutions address the eavesdropping and rogue scanning threats.

The third solution mitigates as well tracking threats. Section 5.3 provides some simulation and experimental details. Section 5.4 concludes the chapter.

Secret Sharing Schemes for EPC Gen2

We have seen in previous chapters that the hardware and power constraints of EPC Gen2 tags makes very challenging the use of solutions based on traditional cryptography. The adoption of low-overhead procedures becomes the main approach to problems where traditional cryptography cannot be accommodated. In Chapter 2, we introduced the use of secret sharing schemes [START_REF] Karnin | On secret sharing systems. Information Theory[END_REF] as a promising foundation for the management of keys for the design of authentication protocols and for dealing with privacy issues.

Secret sharing for RFID technologies was initially proposed by Langheinrich and Martin in [START_REF] Langheinrich | RFID privacy using spatially distributed shared secrets[END_REF] as an evolution of the minimalist cryptography approach presented by Juels in [START_REF] Juels | Minimalist cryptography for low-cost RFID tags[END_REF]. Instead of using lists of pseudonyms, the use of secret-sharing schemes is proposed to address authentication in scenarios such as supply chain applications of the retail industry. Indeed, the work presented by Langheinrich and Martin simplifies the lookup process performed on back-end databases for identifying tags, while guaranteeing authentication.

Tag Identifiers (TIDs), seen in Langheinrich and Martin's work as the secrets that must be shared between readers and tags, are encoded as a set of shares, and stored in the internal memory of tags. To do so, a Perfect Secret Sharing (PSS) scheme is proposed, in which the size of the shares is equivalent to the size of the secret, based on the (t,n)-threshold secret sharing scheme introduced by Shamir in [START_REF] Shamir | How to share a secret[END_REF]. The combination of shares at the reader side leads to the reconstruction of original TIDs. 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 can quickly identify tags. In [START_REF] Langheinrich | Practical minimalist cryptography for RFID privacy[END_REF], Langheinrich and Martin adapt the (t,n)-threshold secret sharing scheme of Shamir to allow the exchange of secret shares across multiple tags. The idea is to encode the TIDs associated to an item tagged with multiple RFID devices by distributing it as multiple shares stored within the tags. Authentication is achieved by requiring readers to obtain and combine the set of shares. Still, the work in [START_REF] Langheinrich | RFID privacy using spatially distributed shared secrets[END_REF][START_REF] Langheinrich | Practical minimalist cryptography for RFID privacy[END_REF] cannot protect from information leaks due to the interaction between readers and tags, i.e., there is still the possibility of tracking tagged objects, since tags are always be emitting the same shares.

An alternative use of secret sharing schemes is presented by Juels et al. in [START_REF] Juels | Unidirectional Key Distribution Across Time and Space with Applications to RFID Security[END_REF]. The authors propose the use of a dispersion of secrets strategy, rather than the aggregation strategy used by Langheinrich and Marti. In this new approach, a secret used to encrypt Gen2 TIDs is split into multiple shares and distributed among multiple tagged items. Construction and recombination of shares is based on a Ramp Secret Sharing (RSS) scheme, in which the size of each share is considerably smaller than the size of the secret, at the price of leaking out secret information for unqualified sets of shares. To identify the tags, a reader must collect a number of shares above a threshold. At the manufacturer facility, large quantities of items of the same product, initially tagged together with shares of the same secret, guarantee that authorized readers can always reconstruct the secret and, therefore, decrypt the TID of the tagged items. At the consumer side, the items get isolated. Without the space proximity of other items holding the remainder shares of the secret, an unauthorized reader cannot obtain the sufficient number of shares to reconstruct the key that allows identifying the TID. Privacy is, therefore, achieved though the dispersion of secrets and encrypted identifiers. Moreover, the proposed scheme helps to improve the authentication process of tags. Assuming that t shares are necessary for readers to obtain the EPC data assigned to a pallet, a situation where the number of shares obtained by readers is below t leads to conclude that unauthorized tags are present in the pallet. The main limitation of this approach is that a critical privacy threat to consumers, i.e., the tracking threat defined in Chapter 2, is not addressed. It is a requirement stated by most authors, such as Juels and

Weis in [START_REF] Juels | Defining strong privacy for RFID[END_REF]. Privacy-preserving solutions for RFID applications must guarantee both anonymity and untraceability.

In the sequel, we show that it is possible to improve the above limitations. We construct a novel threshold cryptosystem that provides, in addition to authentication and confidentiality, tracking protection. The approach allows share renewal with secret preservation.

Renewal of shares does not require synchronization of the share holders. We show that the size of the shares can be reduced to less than 528 bits, as suggested by EPCglobal in [START_REF] Epcglobal | EPC Radio-Frequency Identity Protocols Class-1 Generation-2 UHF RFID Protocol for Communications at 860-960 MHz[END_REF]. This way, the approach is compact enough to fit into the inventory responses of low-cost EPC Gen2 tags. We prove that our construction guarantees strong security, and that the reconstruction of the secret does not require the identity of the shareholders.

Construction of our Cryptosystem Scheme

The construction of our proactive (t,n)-threshold cryptosystem relies on the computation of the Moore-Penrose pseudoinverse of a homogeneous system of n linear equations with t unknowns (where t < n) over a finite field Z p ,

a 11 x 1 + a 12 x 2 + a 13 x 3 + • • • + a 1t x t = 0 (mod p), a 21 x 1 + a 22 x 2 + a 23 x 3 + • • • + a 2t x t = 0 (mod p), . . . a n1 x 1 + a n2 x 2 + a n3 x 3 + • • • + a nt x t = 0 (mod p),
in which t and n are positive integers, and p is a prime number. The vector columns of the coefficient matrix A associated to the system of linear equations are linearly independent, i.e., matrix A has rank t and so the vector columns of A span an inner-product subspace in

Z n×t p of dimension t.
The Moore-Penrose pseudoinverse (also called the generalized inverse) of a non-square matrix A ∈ Z n×t p , hereinafter denoted as A † , is the closest representation that A can get to its inverse (since non-square matrices, i.e., n = t, do not have an inverse). Let us notice that if rank(A) = t = n, i.e., A is a full rank square matrix, the Moore-Penrose pseudoinverse of A is certainly equivalent to the inverse matrix A -1 , i.e.,

A † = A -1 | A ∈ Z n×t p ∧ rank(A) = t = n (5.1)
Otherwise, the Moore-Penrose pseudoinverse of a rectangular matrix A exists if and only if the subspaces Ker A (null space of matrix A) and Im A (range space of matrix A) have trivial intersection with their orthogonals. In the case that A ∈ Z n×t p has rank(A)= t, it can be proved that A † exists and it can be computed as follows:

A † = (A ⊥ A) -1 A ⊥ ∈ Z t×n p | A ∈ Z n×t p ∧ rank(A) = t = n, (5.2)
in which A ⊥ denotes the transpose of matrix A. It can also be proved, cf. [START_REF] Meyer | Matrix analysis and applied linear algebra book and solutions manual[END_REF], that if

A ∈ Z n×t p | rank(A) = t,

Basic (t,n)-Threshold Secret Sharing Scheme Based on the Invariance Property of Orthogonal Projectors

Orthogonal projectors have already been used for the construction of threshold secret sharing schemes. In [START_REF] Bai | A reliable (k, n) image secret sharing scheme[END_REF][START_REF] Bai | A strong ramp secret sharing scheme using matrix projection[END_REF], for example, the invariance property of orthogonal projectors is used for the redundant storage of computer images. Indeed, an asynchronous proactive (t,n)-threshold secret sharing scheme can be constructed based on the same observation -meaning that the invariance property of orthogonal projectors can be used to allow shareholders to renew their share without synchronization with other parties and without altering the secret. The key idea of the proposed approach is that the orthogonal projector P A computed from Equation (5.4) and a random matrix A ∈ Z n×t p with rank t is always equivalent to the projector P B obtained from the same equation and any t independent random range images spanned from A.

Before going any further, let us start with a simple example that depicts the basic idea of our approach. It exemplifies the construction of a (2, 3)-threshold, non-proactive yet, cryptosystem; and the reconstruction process by three independent reconstruction processes. such that A is a random matrix composed of two linearly independent column vectors a 1 , a 2 ∈ Z 3×1 31 , i.e., rank(A) is equal to 2; and X is a random matrix composed of three linearly independent column vectors x 1 , x 2 , x 3 ∈ Z 2×1 31 , i.e., rank(X) is equal to 3. Note that we simplify the notation, assuming A = [a 1 , a 2 , . . . , a t ], where each a i is the i-th column vector of matrix A; and X = [x 1 , x 2 , . . . , x n ] where each x i is the i-th column vector of matrix X. Let

Given two matrices

A ∈ Z 3×2 31 , X ∈ Z 2×3 31 , A =     7
A ∈ Z 3×3 31 =    
19 15 27 20 28 2 16 16 24

   
be the resulting matrix obtained by multiplying matrices A and X. We assume hereafter that the column vectors a 1 , a 2 , and a 3 in matrix A are indeed the shares of our cryptosystem; and that P A ∈ Z 3×3 31 is the secret of the cryptosystem, in which P A is the orthogonal projector obtained by applying Equation (5.4) to matrix A.

Let us now assume that a distribution process δ disseminates the shares a 1 , a 2 , a 3 ∈ A to three independent shareholders α, β, and γ. We define the following three column vectors:

V α =     19 20 16     , V β =     15 28 16     , V γ =     27 2 24    
as the corresponding shares held respectively by α, β, and γ. We also assume that a reconstruction process ρ 1 requests to shareholders α and β their respective shares (notice that our example describes a (2, 3)-threshold cryptosystem and so only two shares suffice to reconstruct the secret). A second reconstruction process ρ 2 requests to shareholders α and γ their respective shares. Finally, a third reconstruction process ρ 3 requests to shareholders γ and β their shares. Processes ρ 1 , ρ 2 , and ρ 3 build, independently, three reconstruction matrices B 1 , B 2 , and B 3 (by simply joining the share vectors they collected from each shareholder): Therefore, the three processes ρ 1 , ρ 2 , ρ 3 may successfully reconstruct the secret (i.e., P A ) by performing the same operation described by Equation (5.4). The following theorem establishes the correctness of the approach for the general case.

B 1 =    
Theorem 1 Let A ∈ Z n×t p be a random matrix of rank t. Let A ∈ Z n×n p be the result of multiplying matrix A with a set of n linearly independent column vectors x 1 , x 2 , . . . , x n ∈

Z t×1 p , i.e., A = Ax i (mod p) ∀x i ∈ [x 1 , x 2 , . . . , x n ].
Let B be any submatrix from A with exactly t column vectors. Then, the orthogonal projectors P A and P B derived from Equation (5.4) are identical.

Proof Note that P A = A A † and P B = B B † are the orthogonal projectors obtained by applying Equation (5.4) to both A and B. Since B is any submatrix derived from A with exactly t column vectors, we can also denote B as the resulting matrix obtained by multiplying A ∈ Z n×t p times a given matrix X ∈ Z t×t p . Therefore, P B = B B † is equal to P B = (A X)(A X) † and so to P B = A X X † A † . We know from Equation (5.1) that X † = X -1 when X is a square matrix. Therefore, P B = A X X -1 A † . Since matrix X gets canceled, we obtain that P B = A A † and so identical to P A .

Efficiency or the Proposal

The efficiency of a secret sharing scheme can be evaluated in terms of the information entropy of its shares and secret of the cryptosystem [START_REF] Iwamoto | Strongly secure ramp secret sharing schemes for general access structures[END_REF]. A secret sharing scheme is said to be perfect if it holds that the entropy of the shares is greater than or equal to the entropy of the secret. As a consequence, the size of each share of a perfect secret sharing scheme must be equal or greater than the size of the secret. This is an inconvenient to the hardware limitations of the EPC Gen2 model discussed in Chapter 2. Ramp Secret Sharing (RSS) may considerably improve this efficiency, by allowing a trade-off between security and size of the shares [START_REF] Blakley | Security of ramp schemes[END_REF]. This is the case of the approach presented in this section.

Notice that the size of each share a i ∈ A of our construction is considerably smaller than the size of the secret P A . More precisely, every share a i is a column vector in Z n×1 p , while the size of the secret is a matrix in Z n×n p , i.e., the size of every share is n times smaller than the secret.

To analyze the robustness of a RSS scheme, in terms of its security, it is necessary to quantify the amount of information about the secret that an intermediate set of shares, smaller than the threshold t, may leak out. This leakage of secret information represents the size of the ramp, in which a small ramp provides stronger security to the scheme than a larger ramp. Yakamoto proposed in [START_REF] Yamamoto | On secret sharing systems using (k,l,n)-threshold scheme[END_REF] to quantify the exposure of secret information from each share by defining a second threshold t , where 0 < t ≤ t. By definition, a qualified coalition of t shares may reconstruct the secret. An unqualified coalition of tt shares cannot reconstruct the secret, but leaks out information about it. Less than t shares may not reconstruct the secret and does not reveal any information about the secret. The amount of information leaked out from the secret by an unqualified coalition of t-t shares can be quantified in terms of information entropy. Yakamoto proved in [START_REF] Yamamoto | On secret sharing systems using (k,l,n)-threshold scheme[END_REF] that the security of a ramp secret sharing scheme is strong enough when the following equivalence applies:

H(S|C) = t -t t H(S), (5.5)
in which H(S) is the information entropy of the secret, and C is an unqualified coalition of tt shares. We prove in the sequel that the security of the threshold cryptosystem presented in this section is, according to [START_REF] Yamamoto | On secret sharing systems using (k,l,n)-threshold scheme[END_REF], strong enough.

Theorem 2 Let A ∈ Z n×t p be a random matrix of rank t. Let P A ∈ Z n×t p be the orthogonal projector obtained by applying Equation (5.4) to matrix A. Let A ∈ Z n×n p be the result of multiplying matrix A with a set of n linearly independent column vectors x 1 , x 2 , . . . , x n ∈ Z t×1 p . Then, the basic (t, t , n)-threshold secret sharing scheme constructed from the invariance property of the orthogonal projector P A , in which matrix P A is the secret of the cryptosystem, and the column vectors a 1 , a 2 , . . . , a n ∈ A are the shares of the cryptosystem, is equivalent to Equation (5.5).

Proof Since the information provided by matrix A derives P A by simply applying Equation (5.4), we know that H(P A |A) = 0. Using some information entropy algebra manipulation, we can use this result to decompose H(P A ) as

H(P A ) = H(P A |A) + H(A) -H(A|P A ) = H(A) -H(A|P A ) (5.6)
Notice that matrix A is any full rank matrix chosen uniformly at random from the sample space in Z n×t p . It is proved in [START_REF] Migler | Weight and rank of matrices over finite fields[END_REF] that there are exactly t-1 i=0 (p np i ) random matrices of rank t in Z n×t p . Therefore, we can compute H(A) as follows:

H(A) = log 2 t-1 i=0 (p n -p i ) (5.7)
Knowing A and P A easily leads to H(A|P A ). From Equations (5.3) and (5.4), we have that P A times A is equivalent to A, meaning that A is an eigenvector matrix of P A . Hence, the

We can quantify the amount of information about P A provided by A , i.e., H(P A |A ), using the results from Equations (5.9), (5.10), and (5.11):

H(P A |A ) = H(P A ) -H(A ) + H(A |P A ) = log 2 t-1 i=0 (p n -p i ) -log 2 t-1 i=0 (p t -p i ) - log 2 t -1 i=0 (p n -p i ) + log 2 t -1 i=0 (p t -p i ) (5.12)
When p is a large number, we can simplify the logarithmic expressions in Equations (5.9) and (5.12) to derive H(P A ) and H(P A |A ) as the following approximations:

H(P A ) ≈ t(n -t) log 2 p H(P A |A ) ≈ (t -t )(n -t) log 2 p
We observe that the information entropy of P A , knowing A , is approximatively t-t t times the information entropy of P A :

H(P A |A ) ≈ t -t t H(P A ), (5.13)
which, according to Equation (5.5) provided in [START_REF] Yamamoto | On secret sharing systems using (k,l,n)-threshold scheme[END_REF], guarantees that the security of the ramp threshold secret sharing scheme is strong enough.

Let us conclude this section by determining a value of t, in terms of n, that guarantees that t -1 shares cannot reconstruct the secret. Given that the secret is the orthogonal projection P A derived from the computation of Equation (5.4) and matrix A, and observing again that the projection of A onto the subspace spanned by its range space remains in the same place, i.e., P A • A = A, it is trivial that the projection of any share onto the same subspace does not change either. This effect can be used by a malicious adversary in order to discover P A by solving n consecutive equations of (t -1) shares. Since, by definition, a (t, n)-threshold secret sharing scheme must prevent any coalition of less than t shares from reconstructing the secret, the parameter t of our construction shall be bounded in terms of n as follows:

(t -1)n < n(1 + n) 2 , t < 3 + n 2 (5.14)
From Theorems 1 and 2, we conclude that if t < 3+n 2 , the scheme presented in this section is a strong ramp threshold secret sharing scheme in which exactly t shares may reconstruct the secret, but t -1 or fewer shares cannot.

Pseudoproactive Threshold Secret Sharing Scheme Based on the Invariance Property of Orthogonal Projectors and Multiplicative Noise for the Renewal of Shares

We significantly improve in this section the results presented in Section 5.2.1 by showing that the introduction of multiplicative noise in the coefficients of matrix A does not affect the reconstruction phase. By multiplicative noise we assume independent scalar multiplication of column vector shares a i ∈ A and scalar random numbers r 1 , . . . , r k for stretching these vectors. Indeed, we show that the introduction of multiplicative noise into the column vectors of any reconstruction matrix B i obtained from t column vectors in A does not affect the results.

The following example shows the key idea of this new version. Assuming again a (2, 3)threshold secret sharing scheme based on the orthogonal projectors of matrices A ∈ Z 3×2 31 , X ∈ Z 2×3 31 , and A = AX ∈ Z 3×3 31 : If we generate now three matrices B 1 , B 2 , and B 3 as combinations of vector columns from A = [a 1 , a 2 , a 3 ] and multiplicative noise, such as Theorem 1 also applies in the general case of this new approach. Notice that if A ∈ Z n×t p is a random matrix of rank t, and A ∈ Z n×n p is the result of multiplying matrix A with n linearly independent column vectors x 1 , x 2 , . . . , x n ∈ Z t×1 p , i.e., A = Ax i (mod p) ∀x i ∈ [x 1 , x 2 , . . . , x n ]; then, any submatrix B derived from exactly t column vectors in A , but stretched by multiplicative noise, can still be factorized as B = A X , where X ∈ Z t×t p is a square random matrix resulting from the set of t linearly independent column vectors in X, but stretched by a specific scaling random number r modulo p. We know from Equation (5.1) that (X ) † = (X ) -1 when X is square. Therefore, X gets canceled during the reconstruction phase, i.e., P B = A X (X ) -1 A † , and we obtain that P B = P A = A A † .

A =    
B 1 ∈ Z 3×2 31 = [5 • a 1 , 17 • a 2 ] (mod 31), B 2 ∈ Z 3×2 31 = [7 • a 1 , 13 • a 3 ] (mod 31), and B 3 ∈ Z 3×2 31 = [9 • a 3 , 22 • a 2 ] (mod 31): B 1 =     2 7 7 11 18 24     , B 2 =     9 10 16 26 19 2     , B 3 =     26

Proactive Threshold Secret Sharing Scheme Based on the Invariance Property of Orthogonal Projectors and Both Multiplicative and Additive Noise for the Renewal of Shares

As shown in the previous section, every share in the set of shares derived from matrix A can be independently transformed by adding multiplicative noise. This allows generating numerically different shares while guaranteeing the invariance property of orthogonal projectors to reconstruct the initial secret (i.e., the orthogonal projector P A derived from matrix A). However, even if the new shares are numerically different, any malicious adversary can successfully observe that the shares are always linearly dependent, since the transformation process is simply stretching the initial share by some scaling random factor r.

We solve this problem by combining both multiplicative and additive noise in the transformation process. The only requirement is to provide to the process in charge of reconstructing the secret a reference used in the transformation process. We assume that this reference is the last column vector in matrix A . We also assume that the generation process in charge of the construction of A guarantees that the last column vector is an unordered collection of distinct elements. Then, shareholders are given access to this reference to renew their shares with a linear combination of this reference column. Note that this reference column must be also known a priori by the reconstruction process, but not by any malicious adversary that has access to the renewed shares. Let us illustrate with an example the key idea of this version. Assuming a (2, 3)-threshold secret sharing scheme based on matrices Every shareholder is given column a 3 and either column a 1 or column a 2 . Let us assume two shareholders α and β in the system, each holding one of the following two share pairs V α and V β :

A ∈ Z 3×2 31 , X ∈ Z 2×3 31 , and A ∈ Z 3×3 31 = Ax i (mod p) ∀x i ∈ X: A =     7
V α =     19 27 20 2 16 24     , V β =     15
b α ∈ Z 3×1 31 = 5 • v α1 + v α2 to process ρ 3 . Shareholder β returns b β ∈ Z 3×1 31 = 19 • v β1 + v β2 to process ρ 2 ,
B 1 =     2 20 23 22 20 0     , B 2 =     9 18 1 10 17 2     , B 3 =     30 24 28 15 20 27    
We observe that the orthogonal projectors obtained by applying Equation (5.4) to matrices B 1 , B 2 , and B 3 are identical to the orthogonal projector obtained by applying Equation (5.4) to matrix A:

P A =     27
B i = [r α • a 1 + a 3 , r β • a 2 + a 3 ] = [r α • Ax 1 + Ax 3 , r β • Ax 2 + Ax 3 ] = [A (r α • x 1 + x 3 ) , A (r β • x 2 + x 3 )] = [A x 1 , A x 2 )] = A X i (5.15)
in which r α and r β are the random factors introduced by each shareholder on every interrogation as multiplicative noise; and X i ∈ Z 2×2 31 is a random full rank square matrix derived from A , and so from A X, plus the multiplicative and additive noise introduced by the shareholders on every interrogation. Since matrix X i is a square matrix, the equivalence defined in Equation (5.1) applies, i.e., X † i = X -1 i . Therefore, the computation of any orthogonal projector P Bi based on Equation (5.4) cancels matrix X i and so P Bi is always identical to matrix P A . This establishes the general case of the new approach based on the proof of Theorem 1.

Let us also observe that if processes ρ 1 , ρ 2 , and ρ 3 are executed by a qualified entity Ψ 1 with knowledge of reference a 3 , the returned set of column vectors b α , b α , b α , and so forth, are clearly linked:

b α =     2 23 20     , b α =     9 1 17     = r 1 b α +     27 2 24     , . . .
Conversely, if we assume that processes ρ 1 , ρ 2 , and ρ 3 were executed by a malicious adversary Ψ 2 who is trying to link the shares returned by either α or β, for tracking purposes, but not having access to the column vector reference a 3 , the returned set of column vectors

Simulation and Experimental Results

In Section 5.2, we have seen the formalization of our proposal for the reconstruction of a predistributed secret once a sufficient number of shares are collected. We present in this section the results obtained with an experimental setup that simulates EPC Gen2 adapted shares generation and reconstruction of secrets. Our prototype system allows to experiment the exchange of shares with a regular EPC Gen2 reader and simulated Gen2 tags. The objective of this setup is to demonstrate the practical viability of our proposal.

Figure 5.2 pictures our experimental setup. It is based on the execution of standard EPC Gen2 inventory queries, but enabled with TIDs that are enhanced by our proposed threshold cryptosystem, between a regular EPC Gen2 reader and several Gen2 tag instances simulated by the IAIK UHF demo tag [START_REF] Sic | UHF RFID Demo Tag[END_REF]. As we have seen in Chapter 3, the IAIK UHF demo tag is a programmable device intended for developing new extensions to the EPC Gen2 standard. The demo tag consists of an antenna, an RF front-end, a programmable microcontroller, and a firmware library. The antenna captures the energy emitted by the reader and powers up the RF front-end of the tag. The RF front-end demodulates the information encoded in the signal. The encoded data is processed by the programmable microcontroller to compute a response. To compute the response, the programmable microcontroller executes a software implementation of the EPC Gen2 protocol, implemented in the firmware library. The response is then modulated by the RF front-end and backscattered to the reader.

More details on our experimental setup are reported in [START_REF] Garcia-Alfaro | Practical Eavesdropping of Control Data from EPC Gen2 Queries with a Programmable RFID Toolkit[END_REF].

The share renewal scheme has been implemented in ANSI C using the Crossworks IDE for AVR from Rowley Associates [START_REF] Crossworks | Crossworks v1.4 and v2.0 for AVR[END_REF]. The theoretical construction detailed in Section 5.2 has been adapted to be executed over the Atmel AVR ATmega128 [Cor09] microcontroller of the IAIK UHF demo tag. The ATmega128 is an 8-bit microcontroller based on the AVR architecture. It has 32 registers of 8-bits that can act as the destinations of standard arithmetic operations. In addition, the ATmega128 microcontroller contains 128KB of flash memory and 4KB of data memory that can be addressed by three independent registers of 16-bits. Since the response of inventory queries is a mandatory operation specified in the EPC Gen2 protocol, an existing response function implemented for the ATmega128 microcontroller is already included in the original firmware stored on the IAIK UHF demo tag. By using the Crossworks IDE, we code and merge the new functionality with the general firmware library to adapt the existing inventory response process to the renewal scheme of shares. The AVR JTAG MKII programmer [START_REF]The AVR ATmega128 processors[END_REF] is used to transfer and to debug the updated firmware merged with the adapted inventory routine. On the reader side, the short-range reader CAEN A829EU [START_REF] Caen Rfid | The A829EU RFID reader[END_REF] emits the inventory queries. The reader is controlled by a back end computer over a USB serial port and a Java application.

The Java application is in charge of generating the inventory queries and processing the reconstruction of secrets.

Collection of Shares and Reconstruction Rates

Four different populations of EPC Gen2 tags are simulated and tested. All four simulations are built according to the item-level inventory scenarios reported in [START_REF]EPC Item Level Tagging Joint Requirements Group[END_REF][START_REF] Juels | Unidirectional Key Distribution Across Time and Space with Applications to RFID Security[END_REF]. Our objective is to show how our construction can be used in order to maximize the item traceability rate at the upper levels of a supply chain, i.e., at the manufacturer, distributor and retailer sides, while minimizing the traceability rate at the lower levels of a supply chain, i.e., at the consumer side. The study presented in [START_REF]EPC Item Level Tagging Joint Requirements Group[END_REF] shows that items that are initially assembled and tagged together within large collections at the manufacturer side, i.e., top level of the supply chain, get progressively dispersed into very small subsets when they reach the bottom level of the supply chain, i.e., the consumer side. Two appropriate item examples analyzed in [START_REF]EPC Item Level Tagging Joint Requirements Group[END_REF] are personal hygiene tools and pharmaceuticals products.

According to [START_REF]EPC Item Level Tagging Joint Requirements Group[END_REF], personal hygiene tools like, for instance, razor blades, are initially assembled and tagged together at the manufacturer side of the supply chain in large populations of more than 6,000 tagged items. They are later dispersed in the supply chain until being picked up by consumers in groups of less that five items. Similarly, for pharmaceutical items assembled initially in large quantities of more than 7,000 tagged items at the manufacturer side, we should only expect that no more than six items from the initial population can end in possession of a single consumer at the same time. In accordance with these observations, we simulate four different populations of EPC Gen2 tagged items. The tags of each population are initialized with four independent sets of secret sharing schemes constructed according to our proactive threshold secret sharing scheme in GF(2 5 -1). More precisely, we initialize the tags of the first population with a (13, 24) scheme that produces tag inventory responses of 120 bits; the tags of the second population with a (10, 18)

scheme that produces tag inventory responses of 90 bits; the tags of the third population with a (7, 12) scheme that produces tag inventory responses of 60 bits; and the tags of the fourth population with a (5, 8) scheme that produces tag inventory responses of 40 bits. tion. We recall that these simulations take into account the evaluation reported in [START_REF]EPC Item Level Tagging Joint Requirements Group[END_REF].

We, therefore, consider the upper bounds of five to thirteen items as the sizes of groups of items picked up by consumers (i.e., lower level of a supply chain). Above these bounds, it is straightforward that authorized readers at the store, warehouse or manufacturer facilities will always reach the necessary threshold to reconstruct the secret and access the appropriate TIDs. For each experimental test of each population, the inventory query emitted by the EPC Gen2 reader is responded by exactly m random tags, where 35 < m < 0. We recall that the use of a (t,n) scheme means that of the n available shares, we need to collect, at least, t different shares to successfully reconstruct the distributed secret. Each population of tags is initialized by randomly allocating shares from each of threshold scheme. Each interrogation is executed 100 times with random series of simulated tags. Results show the average and 95% confidence intervals computed after each series of interrogations.

The results confirm that while the reconstruction rate minimizes the traceability of tagged items as soon as these items get dispersed in small quantities on the consumer side (amount of tagged items below quantities of less than twenty tags), it guarantees the identification of these items at the upper levels of the supply chain (amount of tagged items above quantities of more than thirty tags). From these results, we may also conclude that the compact size of shares of all four schemes are appropriate enough to fit on the inventory responses suggested on the EPC standard. Note that the resulting inventory responses that are containing the shares (i.e., 120 bits for the first population; 90 bits for the second population; 60 bits for the third population; and 40 bits for the fourth population) do successfully fit within the maximum response size of 528 bits suggested by EPCglobal in [START_REF]The EPCglobal architecture framework[END_REF].

Concluding Summary and Remarks

We presented a proactive secret sharing procedure to provide consumer privacy and distribution of secrets. Our solution addresses the eavesdropping, rogue scanning, and tracking threats. The main properties of our approach are: (1) low-cost share renewal with secret preservation and without a need of synchronization; (2) compact size of shares; (3) secret sharing construction that guarantees strong security; (4) reconstruction of a secret does not require the identity of the shareholders. We have also presented the implementation of a practical experiment with our proposed cryptosystem in a real EPC Gen2 scenario. By means of a compatible Gen2 reader, and a programmable Gen2 tag [START_REF] Sic | UHF RFID Demo Tag[END_REF] implementing our proactive share renewal process, we have shown that a standard EPC Gen2 reader can reconstruct an appropriate predistributed secret dispersed over a set of Gen2 tags. The set of tags communicate the renewed shares to the reader by using a standard inventory response operation, enhanced by our proposed proactive share renewal.

Chapter 6

Formal Verification of Defense

Countermeasures

Defenses countermeasures reported in the RFID literature often lack of strong security foundations. Chapter 3 already reported this problem on a hardware-based security primitive for EPC tags. Security RFID protocols seem to be even much more error-prone. Note that a great number of protocols surveyed in Chapter 2 were reported insecure few time after their publication. These cases show the lack of formality during the verification phase of new security techniques for low-cost RFID technologies. In this chapter, we deepen on this problem and illustrate how a sample protocol for the EPC Gen2 technology shall be formally specified with regard to its security requirements. We define a key establishment protocol, and formally verify conformity to some security properties such as authenticity and secrecy. The verification is conducted by using automatic tools from the AVISPA framework [ABB + 05]. Parts of this chapter have been previously published in [START_REF] Tounsi | Formal Verification of a Key Establishment Protocol for EPC Gen2 RFID Systems: Work in Progress[END_REF][START_REF] Tounsi | KEDGEN2: A key establishment and derivation protocol for EPC Gen2 RFID systems[END_REF].

Chapter Outline: Sections 6.1 to 6.3 present the security assumptions, the security properties, and the protocol. Section 6.4 specifies the protocol and properties using the specification formalism of the AVISPA framework. Section 6.5 presents the obtained results. Section 6.6 surveys related work. Section 6.7 concludes the chapter.

Security Assumptions Pseudorandomness Model

The security model of the EPC relies on the communication of one-time sequences used to encrypt sensitive data that must be sent over the insecure RFID channel. The purpose of generating one-time sequences for security is typically that both entities participating on the communications are able to repeat the sequence. However, this is not the case with the EPC technology, where only the tags have access to the sequence generation function.

Therefore, the generated sequences cannot be reconstructed at the reader side, and must be sent as clear text over the insecure channel (i.e., tag-to-reader channel) [START_REF] Garcia-Alfaro | Practical Eavesdropping of Control Data from EPC Gen2 Queries with a Programmable RFID Toolkit[END_REF]. Most RFID security protocols in the literature use the traditional model, and assume the use of a Pseudorandom Number Generator (PRNG) whose algorithm is known at both sides (i.e., known by readers and tags). This is also the model we assume in this chapter.

PRNG Schemes

A PRNG is seen in this chapter as a pseudorandom bit generator whose output is partitioned into blocks of a given length n. Each block defines a random-looking n-bit number said to be derived from the PRNG. The derived numbers are random-looking bits (statically independent and unbiased binary digits). The PRNG takes a single input called state (seed, if it is the initial state) and outputs a next state in addition to the output. All states are assumed to be hidden at all times. There are many nuances of PRNGs used in practice that are often more complicated. For example, some of them are associated to auxiliary inputs such as timestamps or counters which also can be controlled by the adversary. There have been numerous works on constructing PRNGs for symmetric encryption schemes. Common PRNGs consist of two components: (1) a generation function that taking an internal state, generates the next output and then updates the internal state accordingly; and (2) a seed generation function that generates the initial state (and/or key) of the system. While some designers propose a model that combines the internal state and the key of the PRNG (cf. [START_REF] Barak | A model and architecture for pseudo-random generation with applications to/dev/random[END_REF] and [START_REF] Bellare | Forward-security in private-key cryptography[END_REF]), others aim at separating them. Our assumed PRNG meets the model cited in [START_REF] Desai | A practice-oriented treatment of pseudorandom number generators[END_REF] and considers state and master key separately. Indeed, the role played by the key and our concept of internal state are quite different. The key typically has a much longer lifetime and may be repeatedly used for different invocations of the PRNG.

The internal state has an ephemeral nature, since it is usually updated during every iteration of the generation algorithm. Our construction concludes a solution to refresh the master key every N interactions as it is shown in Section 6.3.1.

PRNGs can be based on a wide range of cryptographic primitives.

Adversary Model

We assume an active adversary A who controls the communication channel shared between tags and readers. Therefore, A can eavesdrop, store, analyze, redirect, and reuse intercepted messages. A always knows the non-secret data and the functions that each part execute, as well as the inner working of the system (e.g., algorithms and environment associated with the protocol). Additionally, A can impersonate a reader or a tag, and inject new messages by such controlled entities. However, A cannot modify those messages already sent by a non-controlled entity, nor can he prevent non-controlled entities from receiving a message already sent. Finally, A is motivated by any possible scenario leading to the disclosure of secret information used in the protocol. Therefore, we expect from A the application of the following scenarios:

• Protocol exposure. A can try to find any protocol flaw to decrypt the derived keys relying on its a priori knowledge of the system. Therefore, A can try to find any link between captured messages to correlate two or more protocol outputs. The aim is to obtain information about the derived keys.

• Master key recovering. Using the derived keys, A can try to detect, at least, a valid pair of internal state plus derived key. The aim is to conduct afterwards an exhaustive key search attack to derive the master key.

Security Properties

The protocol shall provide secrecy of the master and derived keys in addition to assuring that mutual authentication is done between honest participants preventing impersonation attacks. Strong notions of secrecy such as forward and backward secrecy must also be guaranteed even if adversary A corrupts the whole system by obtaining the session master key and the internal state of the key generation function by external means (e.g., by physically exposing the data of the tags). Therefore, our protocol shall guarantee the security properties defined below.

• Mutual Authentication: We define mutual authentication by the agreement of the reader and the tag on the value of a negotiated master key in each session. When this key is also proved to be secret (i.e., nobody except the intended parties knows the key), this strong agreement excludes potential man-in-the-middle and replay attacks in which the adversary could impersonate one of the two parties.

• Secrecy of the master key: At any time period, A cannot recover the master key from the derived keys used in a given session and within the valid period of generation (i.e., before reaching a given threshold N ).

• Forward secrecy: After the exposure of a given master key, A cannot compute previous master keys used in the system once the master key is refreshed. In other words, let Km i be the i th master key negotiated between the tag and the reader, t i be the last instant of the time interval during which Km i is in use, and t C be the instant of the total compromise event of the tag and the reader. Let K t be the knowledge of A at an instant t, such that t comes after t C . Then A cannot deduce Km i from K t . Equation 6.1 summarized this property.

t i < t C < t then K t Km i (6.1)
• Backward secrecy: After the exposure of a given master key, A cannot compute future master keys used in the system after the master key is refreshed. In other words, let Km i be the i th master key negotiated between the tag and the reader, t i be the first instant of the time interval during which Km i is in use, and t C be the instant of the total compromise event of the tag and the reader. Let K t be the knowledge of A at an instant t, such that t comes after t C . Then A cannot deduce Km i from K t . Equation 6.2 summarized this property.

t C < t i < t then K t Km i (6.2)

Proposed Protocol Scheme

Our protocol, hereinafter referred as KEDGEN2, and inspired by previous efforts such as [START_REF] Battistello | Transaction-based authentication and key agreement protocol for inter-domain voip[END_REF], assumes dynamic key establishment based on key transportation techniques [START_REF] Menezes | Handbook of applied cryptography[END_REF].

This rationale is used since parties in our system have not the same capabilities. Indeed, RFID readers are expected to have enough computational resources to calculate robust keys. Once computed, the master keys are communicated to the tags, assumed to be resource constrained components.

Key Generation Function

Let BS = (Kd, En, Dc) be the base symmetric encryption scheme of our protocol, specified by its key generation Kd, encryption En and decryption Dc algorithms. Let Gen = (S, G) be the PRNG based on a block cipher primitive whose block size is the length of the derived key of the base scheme.

Kd i , St i ← G(Km, St i-1
). We associate with our PRNG a re-keyed encryption scheme, which establishes a new key in every new session. The re-keying function can rely on a one way function that is responsible for changing the keys for each session.

An encryption process of the model we propose is pictured in Figure 6.1. The objective is to encrypt every secret message with a new derived key Kd using En. Thus, the derived keys are used once in each transaction while the master key Km has a longer life time.

Notice that our aim is to minimize the advantage (i.e., the likelihood) of the adversary to compromise the security of G using the data he recovered in each transaction. A potential attack that can take advantage of the weaknesses of the encryption under block ciphers is the birthday attack [START_REF] Bellare | A concrete security treatment of symmetric encryption: Analysis of the DES modes of operation[END_REF]. To safely encrypt more data, a practical solution is to enlarge the limited threshold leading to birthday attacks. Thus, we can use the results in [START_REF] Abdalla | Increasing the lifetime of a key: a comparative analysis of the security of re-keying techniques[END_REF] by introducing a master key re-keying every N = 2 n/3 encryptions, where n is the block length. The solution increases the encryption threshold from N = 2 n/2 to N ≈ 2 2n/3 . This solution requires less resources than the data dependent re-keying. In addition, it follows the basic protocol design in refreshing the keys every new session. With the re-keying function, our encryption scheme is divided into several stages (in a given session). In stage i, all encryptions are performed using the base scheme with Km In addition to the key generation function, we also assume the following elements:

• Tag. A passive constrained device that communicates with readers via a radio interface. The tag is able to give access to its memory only with one reader at a time. It holds the function G of the generator Gen and is able to derive keys according to its secret master key and state.

• Reader. An active entity communicating with the tags and a back-end server. It implements (1) a radio interface to communicate with the tags; and (2) a trusted interface to communicate with the server. It holds the functions G and S and is responsible for refreshing master keys when necessary.

• Back-end server. A trusted entity that stores in its database all tags and readers information. It is responsible for setting up the initial keys either in the tag or in the reader. It also operates to reset the system when problems arise.

• Channels. There are a reader-to-server channel and a reader-to-tag channel. The readers and the server are related with a high-level security channel. They are assumed to be secured with common security protocols (e.g., SSL/TLS). Reader-to-tag channel is the vulnerable channel that captures our interest.

• Sessions. We separate each execution of the protocol by a process named session.

For each communication session between a pair of reader and tag, a different master key is established. Session key ensures the independence across sessions to avoid long-term storage of shared keys and to limit the number of ciphertexts available for cryptanalysis.

Protocol Description

We describe now the steps of the protocol. For simplicity, the reader and the server refer to one entity named sensor, since (i) readers do not store locally secret information related to tags, and (ii) the linking channels to the server are assumed to be secure.

Each tag and sensor store a generation algorithm G (cf. Section 6.3.1) with a synchronized process. G is deterministic. Thus, given Km i and St i,j-1 in the i th session and (j -1) th derivation, G always outputs the same derived key Kd i,j and State St i,j . The function of initialization S is performed once, i.e., the first time the protocol is executed. It can be re-called if the system has to be reinitialized. The sensor stores in its database all the tag information. For each tag, it records the tag pseudonym (or identifier) TagID, its current state St i , the master keys (Km i-1 , Km i ) to recover the last key in case of desynchronization, a generator counter cnt (cf., Section 6.3.1) and an encryption token tkn. The token tkn can be a counter or a timestamp. In our scheme, we are using a counter since tags are not usually connected to a server that can synchronize their clocks. We assume in all transactions that tkn guarantees that sent messages will be different from the ones sent in the previous transactions. It is meant to ensure the message integrity.

In case of loss in the transmission due to interference or noise, the messages are assumed to be resent with the same counters cnt and tkn. That is, if the reader or the tag do not receive the acknowledgment of the last message, the message can be retransmitted with a bit set to Request TagID M=(Km i ॥ tkn i,1 ) ⊕ Kd i,1

(Ack ॥ tkn i,2 ) ⊕ Kd r i,1
Tag Identification Mutual Auth./ Key establish.

Sensor Tag

॥: Concatenation; ⊕: eXclusive OR (Resp ॥ tkn i,4 ) ⊕ Kd r i,3
Tag Access

(Rcmd ॥ tkn i,3 ) ⊕ Kd r i,2
Reading operation

(Wcmd ॥ tkn i,3 ) ⊕ Kd r i,2 (Ack ॥ tkn i,4 ) ⊕ Kd r i,3
Writing operation Stages: In each new session, three stages are required. One stage for identification and another for authentication and key establishment. The third stage is a consequence of the successful authentication which means the access to the internal memory of the tag. These stages are shown in Figure 6.2. We briefly summarize them as follows:

Kd i,1 = (Km i-1 ,St i,1 ); Kd r i,2 = (Km i ,St i,2 ); Kd r i,3 = (Km i ,St i,3 ) G G G
• 1. Tag identification stage. The sensor starts by sending successive requests to the tag until it obtains the TagID. The sensor checks in its database the received TagID.

If there is a match, the sensor associates the TagID with the database identification and the related secret information (i.e., the master key and the state previously negotiated). Both sides must have the same secrets. Otherwise, the next authentication process will fail. The sensor calculates the response including the derived key (by using G with the valid previous master key Km i-1 and St i-1 ) to prove that it recognizes the tag and XORes the result with the new established master key Km i . The sensor stores both the current and previous master keys to handle desynchronization.

• 2. Mutual authentication and refreshment stage. Upon receiving the message M , the tag checks the derived key used for encryption. Then, it calculates a new session key Kd i,1 (i for current session) and decrypts M by applying an XOR operation as follows: Op = (Km i , tkn i,1 ) ⊕ Kd i,1 ⊕ Kd i,1 . If the decrypted suffix of Op is equal to the predefined token tkn i,1 , then the tag authenticates the sensor and accepts Km i as a new master key. It returns an acknowledgment Ack associated with a new derived key Kd r i,1 (r for refreshed key) set from the refreshed values. Otherwise, the tag does not accept the sensor's key and aborts the communication. Upon receiving the value of Kd r i,1 , the sensor verifies it and authenticates the tag, in case of validity.

• 3. Tag access stage. After a successful authentication, the sensor is authorized to access the tag. Thus, it has the ability to execute privileged commands like reading or writing on it. The same process of authentication is used to perform an access operation. Instead of sending the master key, the sensor sends the data to be written on the tag or the tag sends the data required by the sensor encrypted with a fresh derived key:

-Writing operation: the sensor starts by sending the write command W cmd concatenated with the token and XORed with a new session key Kd r i,2 . The tag verifies the key and accepts the command if the value is valid. Then, it acknowledges the reception with session key Kd r i,3 . Otherwise, the tag aborts the communication.

-Reading operation: the sensor starts by sending the read command Rcmd XORed with the new generated key Kd r i,2 . If the tag accepts the request, by checking Kd r i,2 , then it sends the response Resp XORed with Kd r i,3 .

Concurrent Executions: In an EPC environment, a large number of tags can be interrogated at the same time. Thus, it is important for participants to separate concurrent protocol executions. This issue is usually handled by adding a session ID field to the exchanged messages. In our protocol, we assume that each protocol session is associated with an initial internal state, a secret Km, and a token tkn that differentiate all the tags in the system.

The sensor can run concurrently many protocol sessions at a time since it maintains a set of tag information. In contrast, the tag cannot run concurrently many protocol sessions at a time, particularly when it needs to update its secrets simultaneously (e.g., the secrets have to be updated before starting a new session). We consider that the tag can respond to several identification requests by sending its TagID. For password-protected requests (e.g., reading and writing access operations), the tag does not respond to simultaneous queries, nor is it able to increment its internal state and token two times simultaneously. Finally, for synchronization reasons, the tag has to run each session for a small period of time, and then switches off automatically -even if the session has not ended.

Formal Specification and Verification of the Protocol

We use model checking techniques to specify and verify the security of the KEDGEN2 protocol using finite state machine theory. The goal is to dicover logical flaws and attacks against the protocol, w.r.t. the security assumptions provided in Section 6.1. Automated reasoning is highly desirable to avoid errors associated with hand-written proofs [Kre11, SBCC + 07]. We start by presenting the verification framework, as well as some preliminary notions about the specification language and the structure of the expected results.

The AVISPA Framework

There is a number of successful protocol verification tools that are supporting algebraic reasoning, e.g., the extended ProVerif (3) deciding whether some security property has been violated up to this point. CL-AtSe does not limit the protocol execution in any way except for bounding the maximal number of times the protocol execution can be iterated -in case such a number of iterations is specified by the user. Otherwise, the analysis process could never end. In our case, we specify three consecutive series of protocol execution iterations. This number is indeed representative of the different steps of our protocol, i.e., it is sufficient to check the security properties we aim at verifying.

The HLPSL Specification Language

Our protocol and the security assumptions defined in Section 6.1 are specified in the High Level Protocol Specification Language (HLPSL) [CCC + 04]. HLPSL is a specification language for formalizing protocols and security goals based on Lamport's Temporal Logic of Actions (TLA) [START_REF] Lamport | The temporal logic of actions[END_REF]). The language, developed in the context of the AVISPA project [ABB + 05], is a role-based language. Roles can be basic (e.g., agent roles) describing the action of a legitimate participant during the execution of the protocol; or composed (e.g., session and environment roles) describing scenarios of basic roles to model an entire protocol run. The HLPSL language is also used to specify the knowledge and powers of the adversary. Next, we elaborate in detail these aforementioned elements.

Basic roles. Security properties. HLPSL provides an independent section to declare the security properties required, named goal. The goal declaration can be done either by using predefined macros of the predefined security properties (secrecy, weak authentication, strong authentication) or by using Linear Temporal Logic formulas [START_REF] Lamport | The temporal logic of actions[END_REF]. We are interested in the predefined secrecy and strong authentication properties. We use the predefined secrecy property to check whether the secrecy of the key is maintained in a given session and to check (with a slight change of the specification) whether the forward and backward secrecy properties defined in Section 6.2 are guaranteed in the next sessions. We also use the authentication property to validate the goals defined in Section 6.2.

• Secrecy is modeled by means of the goal predicate secret(Km,sec km,Sensor,Tag), meaning that for the value of term Km is a secret shared only between agents Sensor and Tag. The secrecy property is violated every time the adversary learns a value that is considered as secret and that he is not allowed to know (i.e., Km).

• Authentication is modeled by means of the goal predicates witness(A, B, id, T 1), request(B, A, id, T 1) and wrequest(B, A, id, T 1). These predicates are used to check if an instance of a role is right in believing that its peer is present in the current session. This is done by agreeing on a certain value (e.g., T 1) which is typically fresh. The predicates always appear in pairs and have in common the third parameter. This third parameter id is the identifier of the authentication goal and it is used in the goal section of the HLPSL code. There exists two definitions of authentication:

weak and strong authentication.

1. witness(A, B, id, T 1) for the strong or weak authentication properties of A by B on T 1, declares that agent A is witness for information T 1. This goal will be identified by the constant id in the goal section;

2. request(B, A, id, T 1) for a strong authentication property of A by B on T 1, declares that agent B requests a check of the value T 1. This goal will be identified by the constant id in the goal section;

3. wrequest(B, A, id, T 1) similar to request, but for the weak authentication property. It is used to specify an authentication goal with no replay protection.

Strong authentication is an extension of the weak authentication which precludes replay attacks. We can thus conclude that, if strong authentication is achieved, then T 1 has not been previously received by B in a given session.

Each property is added to the honest role and to the goal section. It is identified by the protocol id type. Figure 6.4 shows a declaration of a strong authentication property of the sensor by the tag on the value of Kd 1 = keygen(KM , succ(KM , InState ))

declaring that agent sensor is witness for the value of Kd 1 and that agent tag requests a check of the value Kd 1 . This goal is identified by the constant sensor tag kd1 in the goal section.

Format of the Output Results

After the verification process, the output describes the results, and under what conditions they have been obtained (e.g., Figure 6.7 shows the verification results of the KEDGEN2 protocol). The output format is nearly common to all tools of the AVISPA framework. In the SUMMARY section, it is indicated if the protocol is safe, unsafe, or if the analysis is not conclusive. In a second section titled DETAILS, the output shows conditions under what the protocol is declared safe/unsafe/inconclusive. If a security property of the input specification is violated, then the tools output a warning, some details about the analysis (e.g., whether the considered model is typed or untyped), the property that was violated (e.g., authentication), statistics on the number of explored states, and, finally, an ATTACK TRACE that gives a detailed account of the attack scenario. If no attack was found, then similar information is provided without announcing any violation and attack trace.

HLPSL Specification of our Protocol

The specification of both the protocol and the security goals is described into four HLPSL sections: the sensor, the tag, the environment roles and the goal. Figure 6.5 shows the specification with mutual authentication and secrecy of the master key goals. The generation function G is specified by two functions keygen and succ. The first function generates the derived keys and the second one generates the new state (i.e., InState). Figure 6.6 shows the specification of the protocol to handle the forward secrecy property as well. Note that Figure 6.6: Modified HLPSL specification of our protocol, to handle forward secrecy for the cases of forward and backward secrecy, we slightly change the specification (compared to Figure 6.5) as the AVISPA tool only supports a single execution trace. Thus, we modeled the execution of consecutive iterations in order to show whether leaking a secret during session i helps the adversary to obtain secrets, e.g., from session i-1 for forward secrecy or session i+1 for backward secrecy. In the sequel, we detail the evaluation results.

Evaluation of the Results

For each security property defined in Section 6.2 and specified in Section 6.4, we show in this section the results obtained after the evaluation of our protocol specifications under the CL-AtSe tool.

Mutual authentication: Figure 6.7(a) shows the results of the evaluation of the mutual authentication property. To obtain these results, we specify an iteration of the protocol with legitimate roles and give to the adversary the knowledge of the generation functions, roles and standard commands used in the KEDGEN2 protocol communication (cf., Figure 6.5).

In the HLPSL language, the authentication property is specified using the witness/request predicates. These predicates are used to check if an instance of a role is right in believing that its peer is present in the current session. We use the HLPSL strong authentication definition to require that a given value is accepted by the sensor in exactly the same session in which it was proposed by the tag. We add these predicates to the tag and sensor transactions to evaluate the authentication of each of the two roles and prevent man-in-the-middle and replay attacks. The tool finds no attack violation of the strong authentication property. This strong property guarantees the resilience to man-in-the-middle and replay attacks in which the adversary could impersonate one of the two parties.

Secrecy of the Master Key: Figure 6.7(a) shows, as well, the results of the secrecy property evaluation. We recall that the secrecy of the master key when shared securely between the tag and the sensor is mathematically maintained since the security threshold N of distinguishability is not reached. In other words, the adversary is not able to detect correlations between the outputs of G, named the derived keys. The model checker is used in our evaluation to confirm that the adversary is not able to desynchronize the two participants and replay some messages to reconstruct the master key (and with that, the secret messages encrypted using such a key). To verify the secrecy of the master key, we specify with HLPSL a single instance of the protocol with legitimate roles and give the adversary the knowledge of inner working of the system (cf., Figure 6.5). Secrecy is modeled using the goal predicate secret(Km, sec km, Sensor, T ag) standing for the value of term Km is a secret shared only between agents Sensor and Tag. The secrecy property would be violated if the adversary could learn the value Km. Results show that this does not happen.

Forward Secrecy: Figures 6.7(b) and 6.7(c) show the forward secrecy evaluation results.

To prove forward secrecy, we consider a setting in which the tag and the sensor try to establish a new master key N ewKm using the previous master key Km. Once N ewKm has been established, we reveal to the adversary the internal states N ewKm, InState, and T kn of both the tag and the sensor. Our goal is to prove that this knowledge is not sufficient to enable the adversary to compute the previous Km. We prove first that the original specification of our protocol (cf. Figure 6.5) does not provide forward secrecy. This is shown with the results in Figure 6.7(b). The analysis of the attack trace shows that after establishing and sending the new master key to the tag (i.e., M = (N ewKm||T kn) ⊕ Kd 1

where Kd 1 = G(Km, InState 1 )), the adversary obtains Km in the next generation of InState (InState 2 = G(N ewKm, InState 1 )) relying on the knowledge of N ewKm and Kd 1 . The countermeasure is to hide the generation of InState 2 by values which are not deduced by the adversary. This way, the adversary cannot obtain the key Km. In fact, by changing G(N ewKm, InState 1 ) to G(N ewKm, G(Km, InState 1 )), we use a double generation of the initial state depending on values that cannot be computed by the adversary (i.e., Km). This modification is shown in Figure 6.6. The evaluation results in the use of a game-based approach to prove the robustness of an RFID protocol against a man-in-the-middle adversary. They do not propose a new protocol to be applied on constrained tags but a new method to prove the security of the OSK protocol [OSK03] that they combine with a mechanism to synchronize the internal state of the tag and reader.

The resulted protocol can be applied on RFID tags supporting hash functions. The security of the protocol is proved using the computational model of CryptoVerif verification tool combined with some handwritten proofs to overcome the limitations of the tool regarding desynchronization and forward privacy verification.

Work in [START_REF] Brusò | Formal Verification of Privacy for RFID Systems[END_REF], [KOK + 08] and [START_REF] Mahdi | A Privacy-friendly RFID Protocol using Reusable Anonymous Tickets[END_REF] use the symbolic model to formally verify the security properties. These are the closest efforts to ours. The advantage of using the symbolic model, as our work does, is its ease to automatically prove the security of cryptographic protocols and to clarify complex protocols with provided definitions of formal languages. Brusò et al. propose in [START_REF] Brusò | Formal Verification of Privacy for RFID Systems[END_REF] the use of the applied pi calculus language with the ProVerif automated verification tool and apply their proposed techniques to the OSK protocol [START_REF] Ohkubo | Cryptographic Approach to Privacy-Friendly Tags[END_REF] in order to formally prove the untraceability and forward privacy properties. The proposed technique, which consists in the concept of frame independence between sessions, meets our security goals. However, the proposed verification technique is applied only on one class of protocols that Brusò et al. refer as single step identification. This technique is applied in protocols with two distinct hash functions. This is only possible on tags computationally strong enough to use such functions. These two criteria make the solution different from our proposal, i.e., our proposal uses more steps for both identification and authentication in the context of Gen2 tags (i.e., without hashing capabilities). To conclude, Table 6.1 shows the different aspects that differentiate our protocol to those aforementioned efforts. We prove the security properties of our protocol using the AVISPA framework, and the CL-AtSe (Constraint-Logic based Attack Searcher) automated verification tool. This allows us to conduct the verification process based on an attack construction methodology, i.e., by attempting to find vulnerabilities using the algebraic properties of our protocol. Differently from all those aforementioned work, the proposal presented in this chapter is expected to be applied on highly constrained RFID tags based on based on pseudorandomness. We assume that the use of hash functions is beyond the capabilities of our system. KEDGEN2 achieves mutual authentication, and forward and backward secrecy in different conditions. Only the work of Burmester et al. in [START_REF] Burmester | Lightweight RFID authentication with forward and backward security[END_REF][START_REF] Van Le | Universally composable and forward-secure RFID authentication and authenticated key exchange[END_REF] approaches a similar verification problem also for the EPC Gen2 technology. Their work builds upon the universal composability framework, which is based on the computational model.

Concluding Summary and Remarks

We presented in this chapter the specification and verification of a key establishment and derivation protocol for EPC Gen2 systems. The goal was to illustrate the appropriate way of ensuring the achievement of security requirements when specifying a security protocol for the EPC technology. Our proposed protocol is proven to achieve secure data exchange between tags and readers, based on a key generation model adapted to Gen2 RFID tags.

The generated keys are used in the proposed protocol as one time encryption keys. To guarantee the security of the protocol, the generation function has to respond to a number of properties, including the resilience against key recovery and the indistinguishability of the derived keys. We described the steps of our protocol and verified the expected properties under the presence of an active adversary. The current version of the protocol guarantees the properties of mutual authentication and forward secrecy. Backward secrecy is also verified under weaker adversary assumptions (consistent with typical RFID environments).

Perspectives for future work include a more deep evaluation of security primitives for EPC, such as specific on-board hardware add-ons. As we have seen in previous chapters, lightweight primitives are often reported in the literature as insecure (see, for instance, flawed designs in [CHTW08, KYWG10, CCY + 11] reported, e.g., in [START_REF] Melia-Segui | Analysis and improvement of a pseudorandom number generator for EPC Gen2 tags[END_REF][START_REF] Melia-Segui | A practical implementation attack on weak pseudorandom number generator designs for EPC Gen2 tags[END_REF] and [START_REF] Bianchi | Revisiting an RFID Identification-Free Batch Authentication Approach[END_REF][START_REF] Elkhiyaoui | ROTIV: RFID ownership transfer with issuer verification[END_REF]. Major weaknesses are related to the linearity achievement of knowledge with regard to eavesdropped messages (often authentication is linearly linked to the amount of exchanged messages) and desynchronization. An interesting question would be to address this issue using proof construction methodologies. Conversely to the work presented in this chapter, proof construction methodologies are suitable for proving correctness and completeness rather than finding vulnerabilities in a security protocol. In addition, verification frameworks able to quantify weaknesses of security protocols with regard to dictionary and guessing attacks might also help to enhance the validity of new security primitives. Some existing work in the literature on protocols verification, such as [Del03, GM09, GM11], as well as extensions of the AVISPA framework in the AVANTSSAR [AAA + 12] project, seem to head in this direction, and might be interesting to explore.

Chapter 7 Perspectives for Future Work

In this habilitation thesis I have summarized a selection of results I obtained in the last few years while working on Wireless Security. In every chapter, a list of conclusions per contribution has already been presented. In this final chapter, some directions for future work are outlined. These research directions aim at establishing research on security, dependability, and privacy management in Ambient Intelligence (AmI) environments following the methodology and know-how reported in this dissertation.

Towards Ambient Intelligence

Ambient Intelligence (AmI) environments refer to ubiquitous computing systems in which a wide range of heterogeneous devices, with a vast variety of sensing and reactive capabilities, are expected to assist human activities. Sample AmI environments include smart home health services for elderly and people with disabilities, management of next generation power grid services, and surveillance infrastructures for military and civil defense forces. AmI is a fascinating research field which faces numerous challenges. The provision of security, dependability and privacy in AmI environments is a crucial one. AmI leads to complex security and safety scenarios that not only require the management of traditional communication systems, but also the cooperation among a myriad of autonomous devices that conform the underlying control layers. Moreover, AmI applications allow the collection of vast amounts of data that may contain personal and sensitive characteristics that must be protected. AmI systems require from new solutions to report and anticipate threats and to provide efficient mechanisms to cope with such threats. My proposal aims at establishing a scientific framework to investigate and handle these challenges.

In a nutshell, Ambient Intelligence (AmI) integrates a wide variety of technologies, such as sensors, Radio-Frequency Identification (RFID) labels, human implants, software agents, biometrics, and affective computing. The combination of all these technologies is expected to lead to fully autonomous systems, capable of acting on behalf of human beings. In the AmI paradigm, the concepts of architecture, system or application, as we know them today, evolve to what is known as AmI ecosystems, where complex self-organizing entities coexist and cooperate with each others for achieving operational effectiveness, notably environmental, economical and technical. In general, AmI aims at contributing to personal communications, intelligent highways, wildlife tracking, military battlefield networks, aircraft satellite communication, industrial control systems and outer-space networks. Some more specific examples also include:

• Smart Home health services for elderly and people with disabilities: Within the so-called Smart Home scenario, in which AmI devices are deployed to enable a more intelligent surrounding environment at home, expectations lead to monitoring scenarios that must foster the autonomy of, e.g., elderly or cognitively impaired people [START_REF] Najera | Real-time location and inpatient care systems based on passive RFID[END_REF], [START_REF] Tounsi | Securing the communications of home health care systems based on RFID sensor networks[END_REF]. In general, AmI technologies deployed at home aim at allowing daily activities of patients to be supervised without the necessity of imposing them to leave their homes or to be permanently supervised by a real presence of nurses or close relatives. Some systems based on the use of wireless sensor nodes and RFID (Radio-Frequency IDentification) systems drastically reduce the deployment costs of traditional surveillance cameras [PSJ + 05], as well as reducing the response time for decision-making situations and granting users access to the necessary knowledge when interacting with such an increased level of intelligence [CRS + 04].

• Management of next generation power grid services: AmI is the key component for dealing and complementing the next generation power grid, known as smart grid [START_REF] Valocchi | Switching Perspectives -Creating new business models for a changing world of energy[END_REF]. The smart grid scenario is an "upgraded electricity network to which twoway digital communication between supplier and consumer, intelligent metering and monitoring systems have been added" [START_REF]Smart Grids: from Innovation to Deployment -Communication from the Commission to the European Parliament, the Council, the European Economic and Social Committee and the Committee of the Regions[END_REF]. The European Union is expecting from its member states an 80% adoption of AmI enhanced energy meters (the socalled smart meters) by 2020. In this context, the concept of AmI ecosystems will definitively emerge as intelligent electronic autonomous networks, vertically integrated within power suppliers; and lead to the adoption of sensing infrastructures, information management, storage, transmission and consumption devices present in urban spaces, buildings and homes.

• Surveillance infrastructures for military and civil defense forces: The adoption of AmI-based monitoring and surveillance technologies is starting to be deployed by the military and state defense departments, to assist the protection of critical or strategical infrastructures. Examples include intruder detection and barrier coverage in geographic delimiters, state borders or SCADA systems [START_REF] Kumar | Barrier coverage with wireless sensors[END_REF]. In such scenarios, mobile autonomous sensors are getting control and look over crossing paths within specified regions so as to prevent threats or illegal activity. The construction of smart, virtual, fences for replacing traditional barriers is a reality along the U.S.-Mexico border [START_REF] Hu | Virtual Fence along borders, The Washington Post[END_REF], in order to monitor large and unprotected areas. Similar solutions are likely to be deployed on the occasion of civil events of great magnitude, such as the World Cup and the Olympic Games, in which world-class personalities and athletes require rigorous protection [TT08, VALMGC + 10].

Research Goals and Expected Contributions

The aim is to establish a consolidated scientific framework that benefits from the expertise acquired during my last ten years of research work, in order to handle crucial challenges introduced by the AmI paradigm. AmI environments create significant research problems, especially with respect to the management of information. Indeed, AmI requires from sophisticated structures and models to represent the huge amounts of events and interactions that will be generated, stored, exchanged and consumed. In this regard, evaluation and validation of AmI-based systems is increasingly difficult. The provision of security, dependability and privacy management in AmI is even harder [START_REF] Deswarte | Sécurité, protection de la vie privée et disponibilité[END_REF]. With this in mind, I elaborate next some sample research topics in which my scientific background can help successfully to contribute.

Provision of Security and Dependability in AmI. Security and dependability solutions for AmI must handle the autonomous and openness nature of this computing paradigm. This implies that the entities of the AmI ecosystem must be aware of the hostile actions that the environment can perpetrate against them, in order to preempt such actions, or mitigate them. In this regard, our main goal will be the definition and implementation of a complete framework that formally handles the concept of security and self-protection in AmI. It shall be interesting to explore trade-offs and the interaction of different protection models allowing the representation of the properties that the different entities are obliged to guarantee, and study the necessary mechanism to enforce the associated degrees of security and protection that the whole system must provide. The concept of autonomous reaction shall be handled as well. Autonomous reaction must be seen as the series of system updates required to handle threats and faults without the necessity of human intervention [START_REF] Badonnel | Self-configurable fault monitoring in ad-hoc networks[END_REF]. This should happen not only whenever attacks and malfunctions target the system, but also when system vulnerabilities are detected, prior their exploitation.

Privacy Management of AmI Information Flows. Beyond traditional security and dependability properties, AmI is considered to be a very invasive technology in terms of privacy. Tools and resources related to ubiquitous computing models and computer-assisted services raise a huge rate of data flows with personal and sensitive characteristics that must be protected [START_REF] Friedewald | Privacy, identity and security in ambient intelligence: A scenario analysis[END_REF]. The goal of privacy management is to provide efficient and effective solutions for releasing such data, while providing scientific guarantees that the identities and other sensitive information of the individuals, who are the subjects of the data, are protected. While data security ensures that a given entity has the authority to receive a given piece of information, privacy addresses disclosures based on inferences that can be drawn from released data. Our main action in the related AmI area is to propose new paradigms for privacy management by means of exploration and development of methods and models for advancing the field of privacy preservation. This shall include, among others, advancing in terms of privacy metrics and prioritization of requirements. Right now, very few AmI-based metrics required to guarantee a flexible degree of privacy preservation have been studied in the literature. We propose to start the work by fostering new knowledge on contextual metrics, measurements of utility and risk functions, and metrics upon unstructured data such as e-health reports, energy audits, and monitoring alarms. With respect to requirements prioritization, the action that we propose is in terms of aggregation operators and multi-criteria techniques. The former relies on retrieving data based only on aggregate statistics, e.g., based on Bayesian theory, and providing subsets of entities represented in a given knowledge database. The latter relies on decision-making techniques to handle disclosures [START_REF] Triantaphyllou | Multi-criteria decision making methods[END_REF]. Given the cooperative nature of the problem domain, our work will be driven by handling phenomena such as rank reversals (i.e., adding or deleting decision alternatives may cause a reversal in the ranking of the old ones) and coherence measures for preference divergences (i.e., to avoid conflicts or redundant decision making processes). The use of probabilistic programming [START_REF] Prékopa | Probabilistic programming[END_REF] is envisioned to define models, compute metrics and solve conflicts.

Conciliation of Security and Privacy in AmI.

A final goal would be to conduct research towards establishing the foundations of Privacy by Design in terms of AmI technologies. This is directly related with the enforcement of the privacy by design principle [START_REF] Cavoukian | Privacy by design[END_REF], which relies on the philosophy of proactively embedding privacy management aspects into the technologies themselves, while guaranteeing the expected degree of security and dependability. Broadly speaking, it tackles a series of general principles that must be considered in the phases of the development process, from the analysis to the final implementation of the technology itself, as well as finding the necessary tradeoff to make possible to enhance both security and respect for privacy. This way, the design of privacy management technologies shall not only target particular privacy aspects at some specific stages of the development process. They should be integrated as if it was a unique, single procedure. In light of these issues, we plan to study the assimilation of the principle into the distributed monitoring mechanism expected from the sensing devices of those AmI scenarios identified in this chapter, and contribute in terms of automatic verification of privacy and data protection requirements.

Concluding Summary and Remarks

The provision of security and dependability in AmI (Ambient Intelligence) ecosystems, as well as security and privacy conciliation in AmI, is a crucial open problem. Perspectives outlined in this chapter are centered on modeling and analysis techniques. The research agenda aims at establishing a science of security and privacy techniques for AmI environments, driven by foundational approaches and methodologies that have proven valid to handle traditional IT problems. The experience and knowledge in related areas reported in this habilitation thesis, from standards and organizational security to technical implementations and practical skills, acquired while working with respected researchers in the field, guarantees the fulfillment of the proposed agenda. My experience supervising and guiding graduate and doctoral students, as well as organizing and leading research projects and scientific animation activities, shall also guarantee guidance for fostering further investigations programs.

  -cost RFID and the Electronic Product Code . . . . . . . . . . . . . . 2.2 Threat Analysis Methodology . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Evaluation of Threats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.1 Authenticity Threats . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.2 Integrity and Availability Threats . . . . . . . . . . . . . . . . . . 2.4 Survey of RFID Defense Countermeasures . . . . . . . . . . . . . . . . . . 2.4.1 Hardware-Based Primitives . . . . . . . . . . . . . . . . . . . . . 2.4.2 Security Protocols . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 Concluding Summary and Remarks . . . . . . . . . . . . . . . . . . . . . 3 Weak EPC Pseudorandom Generators 3.1 Pseudorandom Number Generators for EPC Gen2 . . . . . . . . . . . . . .

Figure 2

 2 Figure 2.1: Likelihood and risk functions: (a) likelihood of a threat, (b) risk evaluation function.

Figure 2

 2 Figure 2.2: Inventory protocol of a Gen2 tag.

Figure 2 . 3 :

 23 Figure 2.3: Writing protocol of a Gen2 tag.

  Figure2.2, Steps 2 and 3) to communicate and request further operations from the tag. Using this random sequence (cf. Figure2.2, Step 5), the reader requests a new descriptor (denoted as Handle in the following steps). This descriptor is a new random sequence of 16 bits that is used by the reader and tag. Indeed, any command requested by the reader must include this random sequence as a parameter in the command. All the acknowledgments sent by the tag to the reader must also include this random sequence. Once the reader obtains the Handle descriptor in Step 6, it acknowledges by sending it back to the tag as a parameter of its query (cf. Step 7). To request the execution of the writing process, the reader needs first to be granted access by supplying the 32-bit password that protects the writing routine. This password is actually composed of two 16-bit sequences, denoted in Figure2.3 as PIN 31:16 and PIN 15:0 .To protect the communication of the password, the reader obtains in Steps 8 and 12, two random sequences of 16 bits, denoted in as RN16' and RN16". These two random sequences RN16' and RN16" are used by the reader to blind the communication of the password toward the tag. In Step 9, the reader blinds the first 16 bits of the password by applying an XOR operation (denoted by the symbol ⊕ in Figure2.3) with the sequence RN16'. It sends the result to the tag, which acknowledges the reception in Step 10. Similarly, the reader blinds the remaining 16 bits of the password by applying an XOR operation with the sequence RN16", and sends the result to the tag in Step 13. The tag acknowledges the reception in Step 14 by sending a new Handle to the reader. By using the latter, the reader requests the writing operation in Step 15, which is executed and acknowledged by the tag in Step 16. Notice that an attacker can find the 32-bit password that protects the writing routine. It suffices to intercept sequences RN16' and RN16", in Steps 8 and 12, and to

Few

  PRNG proposals have been presented in the scientific literature specifically designed for EPC Gen2 tags. Peris-Lopez et al. present in [PLHCETR09] a deterministic algorithm that relies on the use of 32-bit keys and pre-established initial states. The set of functions mainly consists of bit rotations, bitwise operations, and modular algebra, building a 32bit PRNG. The authors also propose an alternative 16-bit version of their PRNG for EPC Gen2 compatibility. To reduce the output length from 32 to 16 bits, Peris et al. divide the 32-bit output in two halves and XOR them to obtain the 16-bit output sequence. No evidences of further achievements other than hardware complexity and statistical behavior are provided. Moreover, the inherent peculiarity of their construction methodology obscures potential comparison with classical designs in the security literature. On a different vein,Lee and Hong present in[START_REF] Lee | The tag authentication scheme using selfshrinking generator on RFID system[END_REF] an optimized variant of the shrinking generator[START_REF] Coppersmith | The shrinking generator[END_REF]

  the generator. Che et al. describe in [CHTW08, CCY + 11] another variant of the shrinking generator design, but based on a physical source of randomness that aims at handling the linearity of an underlying LFSR. In the sequel, we deepen our knowledge on LFSR-based PRNGS, and show that the linearity of the Che et al. proposal can be attacked with high probability. Remainder Outline: Section 3.2 describes the suitability of using linear feedback shift registers (LFSRs) for the generation of pseudorandom sequences. Section 3.3 describes the proposal presented by Che et al. in [CHTW08, CCY + 11], and provides a security analysis of the Che et al. scheme. We give the details of a statistical analysis performed over the output data based on the National Institute of Standards and Technology (NIST) statistical test for pseudorandomness. Based on the weakness detected by the NIST test, we also detail an attack that, given a small number of output bits, can determine the whole sequence. Section 3.4 provides the details of the attack implementation. The section provides information about the tools used to implement the attack and the empirical results obtained in the attack of the Che et al. scheme. Section 3.5 concludes the chapter and draws some ideas to handle the linearity problem found in [CHTW08, CCY + 11].

Figure 3

 3 Figure 3.1: PRNG scheme based on the Che et al. specifications

  one would expect 1 in 100 sequences to be rejected. P-values passing α give a confidence of 99.9% of the randomness of the evaluated sequence (if 100 sequences are evaluated, results should pass 0.9615 as defined in Equation 3.2). In order to evaluate the randomness quality of the sequence produced by the Che et al. scheme, we used matlab and generated 230 MB of output data from an implementation of their proposed PRNG. Such data is divided in ten different data sequences (T i ) that are independently analyzed using the NIST suit tests. NIST test results for the Che et al. random generated data are presented in

Figure 3 . 2 :

 32 Figure 3.2: Attack scheme to the Che et al. PRNG

Figure 3

 3 Figure 3.3: Reliability on the Che et al. attack regarding |s a |

  main signals connect the microncontroller to the RF front-end. A first signal, called DE-MOD, provides the demodulated ultra high frequency (UHF) signal from the reader-to-tag channel. A second signal, called MOD, allows the ATmega128 to control the backscatter used to generate the tag-to-reader responses. Finally, a third signal, called RF ON, provides a boolean value to detect the presence of the RF field.The original IAIK UHF demo tag already provides an appropriate implementation of the EPC Gen2 protocol for the ATmega128. The protocol is implemented as a firmware library stored in the flash memory of the microcontroller. This library contains all the functions necessary to process the readers' standard queries and to compute the appropriate responses. The microcontroller is connected, via an UART module, to a serial-interface connector. This serial interface allows to interact with the demo tag, to provide basic operations such as memory mapping, EPC Gen2 values' configuration, visualization of queries and responses exchanged with compliant readers, and execution of user defined operations. This latter allows to complement the original protocol implementation with new functionalities defined at a user level. By using the JTAG connector provided by the demo tag, it is possible to upload new functionalities to the flash memory of the microcontroller, as well as to perform program debugging. A combination of C code and assembly code can be used to complement or modify the original firmware library. A JTAG download cable allows the transfer of new functionalities or firmware updates. Some other modules connected to the demo tag allow more complex programming possibilities, such as FPGA-based UHF protocol implementations. We refer the reader to [SIC07, APF + 07], and citations thereof, for more information.

3.4. 1

 1 Figure 3.4: Experimental setup. In (a), we can see a CAEN A829EU UHF RFID Reader, the AVR JTAG MKII Programmer, and the IAIK Graz UHF Demo Tag. In (b), we can see the Crossworks IDE GUI for AVR, uploading the updated firmware over the demo tag

  Figure 3.5(b) shows a simple example where six write cycles are captured. These captures allow us to collect 96 pseudorandom bits generated from the on-board Che et al. PRNG. The sequences are parsed from the matlab code that we feed with the serial interface output of the demo tag. Only reader-to-tag challenges are shown. The reader writes the EPC identification to 0 (EP C 96b = 0 i b...(i+16) b ⊕ RN 16), to obtain the RN16s directly from the ciphered data field of the write challenges.

  et al. [CHTW08, CCY + 11]. The proposal combines thermal noise signal modulation and an underlying LFSR. We have demonstrated that the proposal does not handle properly the inherent linearity of the resulting PRNG. We have described an attack to obtain the feedback polynomial function of the LFSR. This allows us to synchronize and to predict the resulting sequences generated by the Che et al. PRNG. We have presented the implementation of a practical attack in a real EPC Gen2 scenario. By means of a compatible Gen2 reader, and a programmable Gen2 tag [SIC07] implementing the Che et al. PRNG, we have shown that an attacker can obtain the PRNG configuration with a confidence of 42% by only eavesdropping 128 bits of pseudorandom data. Although the attack implementation has been applied to a specific PRNG proposal, the procedure used to obtain the data is based on standard EPC commands and it can be applied to any EPC tag communication to eavesdrop the output of the PRNG. A solution to handle the linearity problem of the Che et al. PRNG is adapting its architecture towards a Multiple-Polynomial LFSR construction. By adding multiple feedback polynomials to the LFSR, and by feeding the selection of polynomials with the same physical source of randomness proposed by Che et al. in [CHTW08, CCY + 11], we can successfully avoid the inherent linearity of LFSR based PRNGs and satisfy the security requirements. A sample construction based on this idea is presented in the following chapter. Statistical analysis of the sequences generated by such a generator confirmed the validity of the proposed technique. An electronic circuit simulation confirmed, moreover, that the proposal has a simpler hardware implementation than previous schemes reported in the literature. Chapter 4 Multiple-Polynomial LFSR based Pseudorandom Generator We address in this chapter the linearity issues of the Che et al. PRNG reported in Chapter 3. We present a novel design, named J3Gen. J3Gen is based on a linear feedback shift register (LFSR) configured with multiple feedback polynomials. The polynomials are alternated during the generation of sequences via a physical source of randomness. A concrete hardware implementation of J3Gen is presented and evaluated with regard to different design parameters, defining the key-equivalence security and the achievement of the EPC Gen2 requirements. The results of a SPICE simulation confirm the power-consumption suitability of the proposal. Parts of this chapter have been previously published in

Figure 4 .

 4 Figure 4.1 depicts a block diagram of the J3Gen proposed design. It gets inspiration from a dynamic LFSR-based testing selection scheme presented by Hellebrand et al. in [HRT + 95, RAHN03]. Indeed, it substitutes the static feedback polynomial configuration of an LFSR by a multiple feedback primitive polynomials configuration architecture. The different feedback primitive polynomials are connected to the LFSR by a decoding matrix that selects each single feedback polynomial. After a given number of LFSR cycles, the Polynomial Selector Module shifts its position towards a new configuration. The number of shifts, i.e., the corresponding selection of each primitive polynomial at a certain LFSR cycle, is determined by a true random bit (hereinafter denoted as trn) that is obtained from a physical source of randomness. Next, the four main design modules are described. A detailed step by step sample execution of our construction is shown in Section 4.2.

Figure 4 . 1 :

 41 Figure 4.1: Block diagram of J3Gen

  remainder GEs mainly consist on the necessary extra circuitry for controlling the different states of the generator. Logic gates considered in this implementation count are basic two-input gates, except for the decoder (Polynomial Selector) where (log(m)/log(2))-input NAND gates are used depending on the number of implemented polynomials m. For the LFSR implementation purpose, we use the D-flip-flop (DFF) model specified at [Bak07] composed by 18 CMOS transistors. Hence, a DFF can be measured with approximately 4.5 GE.

Figure 4 .

 4 Figure 4.2 depicts the equivalent-key size regarding the necessary logic GE for the implementation of J3Gen. An implementation with n = 32 and m = 32 slightly exceeds the 2,000 available GE for security purposes. Using less feedback polynomials reduces the implementation area in exchange for smaller key sizes. This is the case of combining n = 32 and m = 16, which can be implemented with 1,191 logic GE giving a key of 372 bits.

Figure 4 .Figure 4

 44 Figure 4.2 shows that, although GE and key bit length grows in parallel, such relation is not uniform, since with 98 GE we can increase 138 bits in key length when moving from

  to effectively simulate the circuit like a real fabricated device. Current UHF RFID products are fabricated on 180 and 130 nm CMOS processes[START_REF] Feldhofer | Hardware Implementation of Symmetric Algorithms for RFID Security[END_REF]. For our simulation we use the Predictive Technology Model (PTM) libraries 2 provided by the Nanoscale Integration and Modeling Group from the Arizona State University, which provides CMOS models for 130 nm processes.

Figure 4 . 4 :

 44 Figure 4.4: LTSpice power consumption simulation. Power dissipation is concentrated around the internal clock cycles.

RFID technologies have been

  disclosed in the related literature. For instance, PRNG implementations in [HBF07, LVHH11, AAKBD12], although efficient in their implementations, cannot be applied to UHF technologies due to the state-of-the-art technologies reported by their authors, or given the power consumption criteria of the EPC Gen2 specification. Manufacturers of existing EPC Gen2 commercial solutions are reluctant to provide their designs [PLHCETR09]. Finally, some of the designs that do appear in the literature, and that claim to be both secure and lightweight enough to fit the EPC Gen2 restrictions, fail to provide convincing proofs of such claims. Some proper examples are [LH07, PLHCETR09, CHTW08, CCY + 11].

  al. [DGK + 11], the proactive threshold cryptosystem for EPC Tags by Garcia-Alfaro et al. [181, 177], and the security protocols proposed by Delgado-Mohatar et al. [DMFSS11],

A

  pseudorandom number generator (PRNG) design for EPC Gen2 RFID technologies, named J3Gen, has been presented. The generator is based on a linear feedback shift register (LFSR) configured with a multiple-polynomial tap architecture fed by a physical source of randomness. It achieves a reduced computational complexity and low-power consumption as required by the EPC Gen2 standard. It is intended for security, addressing the onetime-pad cipher unpredictability principle. J3Gen is configurable for other purposes and scenarios besides EPC Gen2 RFID technologies through its main parameters n (LFSR size)

Figure 5

 5 Figure 5.1: Orthogonal Projection of a Vector v onto the Subspace Spanned by the Column Vectors of Matrix A.

  We can now observe that the orthogonal projector obtained by applying Equation (5.4) to either B 1 , B 2 , or B 3 is equivalent to the orthogonal projector obtained by applying Equation (5.4) to matrix A: B 1 = P B 2 = P B 3 =

  can still observe that the orthogonal projectors obtained by applying Equation (5.4) to either B 1 , B 2 , or B 3 are certainly equivalent to the orthogonal projector obtained by applying Equation (5.4) to matrix A: B 1 = P B 2 = P B 3 =

  Let us assume that a reconstruction process ρ 1 requests to each shareholder their share combination. Both α and β return to ρ 1 a linear transformation from the column vectors in their share pairs. Shareholder α generates a random value r α = 15, transforms v α1 into v α1 •15 (mod31), and returns b α ∈ Z 3×1 31 = v α1 +v α2 . Similarly, β generates a random value r β = 14, transforms v β1 into v β1 •14 (mod31) and returns b β ∈ Z 3×1 31 = v β1 +v β2 . Two other reconstruction processes ρ 2 and ρ 3 request to each share holder their shares. Shareholders α and β return to ρ 2 and ρ 3 two different linear combinations from the column vectors in their share pairs. Shareholder α returns b α ∈ Z 3×1 31 = 28 • v α1 + v α2 to process ρ 2 , and

  and b β ∈ Z 3×1 31 = 21 • V β1 + V β2 to process ρ 3 . Finally, the process ρ 1 assembles with b α , b β the reconstruction matrix B 1 ∈ Z 3×2 31 ; the process ρ 2 builds with b α , b β the reconstruction matrix B 2 ∈ Z 3×2 31 ; and the process ρ 3 produces with b α , b β the reconstruction matrix B 3 ∈ Z 3×2 31 :

  B 1 = P B 2 = P B 3 = Notice that each matrix B i = [b i1 , b i2 ], s.t. i ∈ {1 . . . 3}, can be decomposed as follows:

  b α , b α , and b α , as well as column vectors b β , b β , and b β , are viewed as unlinked.

Figure 5

 5 Figure 5.2: Experimental Setup. In (a), we can see the CAEN A829EU Reader, the AVR JTAG MKII Programmer, the IAIK Graz UHF Demo Tag, and some regular EPC Gen2 tags. In (b), we can see the Java graphical front end that summarizes the process of collecting the secret shares and reconstruction of secrets.

Figure 5

 5 Figure 5.3(a)-(d) pictures the average and the 95% confidence intervals of the reconstruction rates obtained with the collection of less than 35 shares from each simulated popula-

Figure 5 . 3 :

 53 Figure 5.3: Simulation results. (a) First population results with a (13,24) proactive threshold secret sharing scheme of shares; (b) second population results with a (10,18) scheme; (c) third population results with a (7,12) scheme; (d) fourth population results with a (5,8) scheme.

Figure 6 . 1 :

 61 Figure 6.1: Proposed encryption scheme.

Figure 6 . 2 :

 62 Figure 6.2: Main stages of the protocol.

  [START_REF] Küsters | Reducing Protocol Analysis with XOR to the XOR-Free Case in the Horn Theory Based Approach[END_REF], Maude-NRL Protocol Analyzer[START_REF] Escobar | Maude-NPA: Cryptographic Protocol Analysis Modulo Equational Properties[END_REF],On the Fly Model Checker (OFMC)[START_REF] Basin | OFMC: A symbolic model checker for security protocols[END_REF] and Constraint-Logic based Attack Searcher (CL-AtSe)[START_REF] Charu | Validating Integrity for the Ephemerizer's Protocol with CL-Atse[END_REF]. They use different models and verification techniques. For example, extended ProVerif is based on tree automata and Horn clauses techniques. MaudeNPA is based on rewriting techniques and backward search of bad states. OFMC is based on a state space exploration and CL-AtSe is based on a constraint solving technique. Each tool has some strengths and weaknesses[START_REF] Cremers | Comparing State Spaces in Automatic Security Protocol Analysis[END_REF]. We use the CL-AtSe protocol analyzer, refereed as the most mature tool using the constraint solving technique[START_REF] Kremer | Modelling and analyzing security protocols in cryptographic process calculi[END_REF].The tool is part of the AVISPA project [ABB + 05]. It has recently been extended by the AVANTSSAR [AAA + 12] project. We use the latest version of CL-AtSe[START_REF] Charu | Validating Integrity for the Ephemerizer's Protocol with CL-Atse[END_REF] to verify our protocol. The AVISPA platform is a suite of applications commonly used for formal specification and automated validation and verification of cryptographic protocols. It is composed of several modules: (1) a translator called HLPSL2IF[START_REF] Chevalier | Rule-based Programs Describing Internet Security Protocols[END_REF], used to transform from a high-level language specification to a low-level language specification; and (2) a suite of verification tools to analyze the low-level language specifications. From the suite of verification tools, we only use one, the CL-AtSe tool. The reason is that this tool can verify protocols that use algebraic properties of operators like XOR or exponentiation. It also allows running many consecutive, concurrent, sessions. Such features allow us the verification of our protocol.The CL-AtSe tool (from Constraint-Logic based Attack Searcher) runs the protocol in all possible ways, and generates families of traces with positive or negative constraints on the adversary knowledge, variable values, and many other aspects. Each protocol run consists in (1) adding new constraints on the current adversary and environment state, (2) reducing these constraints down to a normalized form for which satisfiability is easily decidable, and

Figure 6

 6 Figure 6.3: HLPSL main elements. (a) Basic role structure. (b) Session role structure. (c) Environment role structure. (d) Secrecy in the goal section.

  Figure 6.3(a) shows how a basic role is generally structured. Each basic role declares its name (A), its initial information or parameters (param) and the agent playing the role (ag). The basic role can declare a set of local variables (L). The init section assigns the initial values to the local variables, if required. The transition section describes changes of the agent state. It consists of a trigger (e.g., evt.2) and an action (e.g., act.2) to be performed when the triggered event occurs. The = | > operator separates the two phases. Composed roles. Composed roles combine basic roles, either in parallel or in sequence. HLPSL defines two composed roles: the session role and the environment role. Actions, in composed roles, are not defined in a transition section like for the basic roles. Rather, a composition section is defined to instantiate other roles Ri or Si, with sets of parameters param-i, that run in parallel (cf. Figures 6.3(b) and 6.3(c)). The session role, referred by S in Figure 6.3(b), instantiates in its composition section the basic roles and the different channels relating them while the environment role instantiates in its composition section all the sessions to be run (Si). The environment role is called the main role, as it declares the global constants (C) and defines the adversary knowledge denoted by IN (from INtruder).

Figure 6

 6 Figure 6.4: Strong authentication property definition.

Figure 6

 6 Figure 6.7(c) show that the modified version satisfies the forward secrecy property even under the hypothesis of a complete compromise in the following sessions.

  In [KOK + 08], Kim et al. use an automated verification tool called FDR (Failure Divergence Refinement). The work can be compared to ours as it also uses a model checking tool to verify the secrecy and authentication of an RFID protocol. However, the use of a hash based scheme added to a pseudorandom number generator to implement the protocol presents a different solution model. As opposed to our proposal, Kim et al. do not consider √ by the authors -Not checked by the authors 1 A different definition of forward secrecy is checked named forward untraceability 2 Checked under the same adversary used for verifying the forward secrecy 3 Checked under a weaker adversary used for verifying the forward secrecy 4 PRNG: Pseudorandom Number Generator Table6.1: Comparison between recent related work using various models of formality in their work strong secrecy notions such as forward and backward secrecy that handle linkability between the sessions. In[START_REF] Mahdi | A Privacy-friendly RFID Protocol using Reusable Anonymous Tickets[END_REF], Mahdi and Mohammad propose a new protocol that assures mutual authentication and privacy which they define as anonymity and forward untraceability. The verified property of forward untraceability is different from forward secrecy. Mahdi and Mohammad define the protocol as attacked when the adversary detects twice the same hash result, which means detecting the same tag. Whereas in our case, an attack is shown when an adversary obtains the secret keys of last sessions of communicated keys for a given tag.

Table 2

 2

.1: Evaluation of Threats.

Table 3

 3

.1: Che et al. results for the NIST statistical test suite true random source [Haa98]. Each row refers to a test included in NIST test suite. The first nine tests are represented with the numerical value of the uniformity of P-values. The last five tests are in fact a set of different tests thus in order to represent each of the values, an achievement ratio is represented following the same decision rule of the first tests (Equation 3.2). Tests refusing randomness hypothesis are denoted with bold letters in the table

.

For tests consisting on a set of tests, an asterisk is added when some of the tests are not successfully achieved. In fact, results show a statistical evidence of non randomness for the Binary Matrix Rank Test (cf. Table

3

.1). Such test constructs binary matrices from the analyzed data and checks for linear dependence among the rows or columns of the constructed matrices. The fact that the Binary Matrix Rank Test fails for all the sequences,

Table 3 .

 3 3: Value of |s a | for a successful attack in the worst case after 10 tests

	Sequence	T 1	T 2	T 3	T 4	T 5	T 6	T 7		T 8	T 9	T 10
	attack success (%) 0.132 0.137 0.131 0.126 0.139 0.137 0.129 0.137 0.138 0.128
		Table 3.2: Attack success rate for |s a | = 3n -1
	Sequence T 1	T 2	T 3	T 4	T 5	T 6	T 7	T 8	T 9 T 10
	|s a |	238 254 254 190 510 158 254 286 238 222

  The queries are generated from a standard RFID reader according to EPC Gen2. The RFID reader we use is a short-range reader CAEN A829EU (cf. http://www.caen.it/rfid). The reader is controlled by a desk computer over a USB serial port. For the generation of queries, we use a .NET application that controls the communication process with the reader. This application enables us to generate the set of queries required to proceed with the eavesdropping attack. We use matlab to decode the set of responses generated over the demo tag. This operation enables us to iso-

scheme with the general firmware library to replace the existing PRNG. The JTAG programmer that we use to transfer and to debug the updated firmware merged with the new PRNG implementation is an AVR JTAG MKII programmer (cf. http://www.atmel.com/). late the pseudorandom queries computed at the demo tag. When the number of sequences collected by the application reaches an appropriate threshold, it proceeds to execute the implementation of the attack we presented in Section 3.3.2. We provide in the sequel further details about the collection of pseudorandom sequences and the practical results.

Table 5

 5 EPC = 0 Write sequence generated with C write operation is an access command used to modify specific areas of a Gen2 tag memory. The reader first identifies the tag with select and inventorying commands (what shifts the tag from ready to acknowledged state). Once the tag is acknowledged (meaning that the tag has sent its EPC identification) the reader requests a new RN16 to the tag for establishing an access session. The new RN16 (denoted as handle) acts as a session key, and must be used to link all the access actions to a specific tag. Observe that all access commands can be executed both in the open or secured tag state[START_REF] Epcglobal | EPC Radio-Frequency Identity Protocols Class-1 Generation-2 UHF RFID Protocol for Communications at 860-960 MHz[END_REF]. If the accessed tag is in the secured state, it means a 32-bit password (exchanged as two 16-bit half-passwords XORed with two RN16s) is necessary to allow the reader to access the tag. In our experiments,

	=> QUERY ... => ACK ... => Req RN RN:14438 => Req RN RN:44282 => Write (data) 27698 => Req RN RN:44282 => Write (data) 47380 => Req RN RN:44282 => Write (data) 44282 => Req RN RN:44282 => Write (data) 60868 => Req RN RN:44282 => Write (data) 32656 => Req RN RN:44282 => Write (data) 34674
	bits. The attack consists on the analysis of
	ated data, trying to find the feedback polyn
	success is 41.5% (cf. Fig. 4), very close to
	Thus we are able to confirm the vulnerabilit

(a) EPC Gen2 write protocol. (b) Real capture of six write cycles.

Figure 3.5: Write process for EPC Gen2 and the PRNG utilization. In (a), we can see the six cycles of the EPC Gen2 write command. In (b), we can see a real sample of six write cycles captured from the reader-to-tag channel Figure 3.6: Che et al. PRNG attack success for real Gen2 environment A we assume that the tag is in the open state, i.e., we do not consider the capture of PRNGs derived from the exchange of the two half-passwords. This way, an inventoried tag transitions directly to the access mode. For a write operation once the reader gets the handle, it initiates a round of writes of 16-bit data sequences (obscured with previously requested RN16s) to the tag. Thus, if a new EPC identification is written to the tag, six write cycles are performed, as we picture in Figure 3.5(a). The eight generated RN16s represent 128 consecutive bits generated from the PRNG of an EPC Gen2 tag, as specified in the standard [EPC08b]. As we pointed out in Section 3.3.2, the Che et al. scheme can be predicted with a reasonable small amount of data. We can now demonstrate this property in our real Gen2 environment, by simply performing an appropriate series of write challenges to the adapted Che et al. PRNG implemented over the demo tag, and analyzing the resulting RN16s. More precisely, we show that by simply collecting 128 bits (generated from a series of eight RN16s associated to each write challenge)

  Che et al. PRNG implementation deployed over the demo tag. Once stored, the pseudorandom sequences are processed by the matlab code that contains the attack implementation. Let us recall that the attack applies the analysis of the linearity relation for each single write challenge. We show that the attack finds the appropriate feedback polynomials of the LFSR each 128 bits with a total ratio of success of 41.5%. This result is very close to the 42%

that we predicted in Section 3.3.2 (Figure

3

.3). Therefore, we are able to confirm the vulnerability of the Che et al. PRNG for Gen2 environments.

Table 4

 4 The system starts with p(x) 1 and outputs = 15 bits until the TRNG module transfers a bit with value r 0 = 0 to the Decoding Logic module. Then, a consecutive (but different) feedback polynomial is selected in the Polynomial Selector module, that is, p 2 (x). This generates the next = 15 LFSR shifts with p 2 (x) until the next trn is obtained. The trn value for this PRNG update is r 1 = 1, hence, the Decoding Logic rotates the Polynomial

	.1: Design parameters summary
	Size of LFSR (bits)	n = 16
	Number of feedback polynomials on tag m = 8
	trn sampling period Polynomial Selector update period	f r = 16 = 15
	Table 4.2: Feedback polynomials (n = 16)
	Primitive polynomials
	p

1 (x) : 1 + x + x 5 + x 6 + x 7 + x 11 + x 16 p 2 (x) : 1 + x 4 + x 5 + x 6 + x 7 + x 11 + x 16 p 3 (x) : 1 + x + x 3 + x 4 + x 5 + x 6 + x 7 + x 11 + x 16 p 4 (x) : 1 + x 3 + x 5 + x 6 + x 10 + x 11 + x 16 p 5 (x) : 1 + x 5 + x 6 + x 11 + x 16 p 6 (x) : 1 + x 5 + x 6 + x 10 + x 11 + x 13 + x 16 p 7 (x) : 1 + x 4 + x 5 + x 6 + x 10 + x 11 + x 16 p 8 (x) : 1 + x + x 3 + x 4 + x 5 + x 6 + x 10 + x 11 + x 16 Table

4

.3 details each LFSR state for 32 shift cycles (rows) providing 32 outputted PRNG bits (column Tx) consisting in two 16-bit sequences. Since the trn sampling frequency is f r = 16 cycles, this 32 shift cycles need two true random values, that in the example have been set to r 1 = 0 and r 2 = 1.

Selector one position at shift 31, and another position at shift 32. Then, p 2 (x) is used 14 cycles, p 3 (x) is used one cycle, and p 4 (x) is used one cycle in this PRNG update and 14 cycles in the next PRNG update (not included in Table

4

.3).

Table 4 .

 4 4 represents the different implementation counts (based on GE area), depending on the main PRNG parameters n and m, as described in Section 4.1. The n-bit register is in-

	LFSR size (n)		16			24			32			64
	Feedback polynomials (m)	8	16	32	8	16	32	8	16	32	8	16	32
	LFSR module	72.0 72.0 72.0 108.0 108.0 108.0 144.0 144.0 144.0 288.0 288.0 288.0
	Polynomial Selector module 209.3 396.6 774.1 305.1 577.6 1,125.3 401.0 758.6 1,476.5 784.3 1,482.4 2,881.3
	Decoding Logic module	48.3 48.3 48.3 53.3 53.3	53.3 53.3	53.3	53.3	61.3	61.3	61.3
	TRNG	22.0 22.0 22.0 22.0 22.0	22.0 22.0	22.0	22.0	22.0	22.0	22.0
	Additional Control	87.5 125.0 182.1 114.9 169.3 279.9 141.2 212.7 356.3 249.3 387.9 667.7
	TOTAL	439.1 663.9 1092.5 603.3 930.2 1,602.8 761.5 1,190.6 2,052.1 1,419.3 2,241.6 3,920.3
		Table 4.4: Logical GE Count for J3Gen

cluded in the LFSR module, the LFSR feedback and decoder are included in the Polynomial Selector module, and the cycle clock, TRNG and PRNG output are included in the Decoding Logic module. These three elements add up to the most representative amount of GEs.

  The PRNGs that are in relevant use today, are typically based on hash function or block cipher designs. Given the limited computing power of EPC Gen2 tags, we consider in our work PRNGs built from block cipher designs with low-resource hardware constraints. Existing implementations of block cipher based designs for passive RFID tags, such as the 65nm implementation of the Advanced Encryption Standard (AES) in[START_REF] Feldhofer | AES Implementation on a Grain of Sand[END_REF], could be adapted for our purpose with a hardware complexity of about 5,000 equivalent logic gates. Other plausible solu-

	tions could be adapted from HIGHT [HSH + 06], Grain [HJM07], Trivium [DP08], LAMED
	[PLHCETR09], and J3Gen [193] (cf. Chapter 4), with even lower complexity. Such de-
	signs can be adapted to implement pseudorandom permutations (i.e., whose permutations
	are dependent of a key k) designed to approximate, as closely as possible, a random permu-
	tation function, in the sense that if the key k is not known and only input/output examples
	of executions based on k are captured, then, these should appear like input/output examples
	of random permutations.

  Gen consists of two algorithms. The first algorithm S is a probabilistic algorithm which outputs an initial state St 1 and a master key Km 1 . It takes no input values. The second algorithm is an iterative deterministic generation function G, computing in each iteration from three inputs (a master key Km, a state St, a counter cnt) an output Kd and a new state St i . The counter avoids cases where the same state and key are used. It is a replay defense. For i 1, the generation algorithm G takes as input the key Km and the current state St i-1 (including the cnt) to generate Kd i and St i as:

Available at http://bwrc.eecs.berkeley.edu/classes/icbook/spice/.

Available at http://ptm.asu.edu.

equations defined by Penrose in [START_REF] Penrose | A generalized inverse for matrices[END_REF]:

For our specific construction, we are interested in showing that the resulting matrix A † keeps the orthogonal projection property required in [START_REF] Penrose | A generalized inverse for matrices[END_REF]. Indeed, we are interested in showing that the resulting matrix P A computed as

is indeed an orthogonal projector that satisfies the idempotent property (meaning that P k A = P A for all k ≥ 2. Certainly, if P A = A A † , then P 2 A = (A A † ) (A A † ), i.e., P 2 A = (A A † A) A † ). From Equation (5.3), we obtain that P 2 A = A A † , i.e., P 2 A = P A , and so P k A = P A for all k ≥ 2. Therefore, if A ∈ Z n×t p and rank(A)= t, then A A † ∈ Z n×n p is an orthogonal projector. Figure 5.1 shows how the orthogonal projector P A can be used to project a vector v onto the column space of matrix A.

The Moore-Penrose pseudoinverse is a very useful technique used in many engineering fields such as error correction, identification, control design, and structural dynamics. For an over-determined system of linear equations without solution, the Moore-Penrose pseudoinverse finds the least squares solution (i.e., projection of the solution onto the range space of the coefficient matrix of the system). It is also helpful to find the infinite set of solutions in the range space of under-determined set of equations (i.e., fewer constraints than unknowns). The computation of the Moore-Penrose pseudoinverse of a homogenous system of t linear equations with n unknowns (e.g., the computation of the pseudoinverse of matrix A ⊥ ∈ Z t×n p ) is hence a valid alternative for the construction of our proactive threshold secret sharing.

provides information about A. More precisely, matrix A can be obtained from V by using a transformation matrix W ∈ Z t×t p . Since the sample space from which matrix W can be uniformly chosen is exactly of size t-1 i=0 (p tp i ), we have that H(A|P A ) can be obtained as follows:

Using Equations (5.7) and (5.8) we can now compute H(P A ) = H(A) -H(A|P A ):

Let us now quantify, in terms of entropy, the information about P A provided by an unqualified coalition A of t shares, s.t., A = [a 1 , a 2 , . . . , a t ], and where 0 < t < t. Since matrix A can be seen as a random matrix of rank t chosen uniformly from the sample space t -1 i=0 (p np i ), we have that H(A ) can be denoted as follows:

Matrix A is also an eigenvector matrix of P A . The decomposition of P A into t eigenvectors

provides information about A . Indeed, matrix A can be obtained from V by using a transformation matrix W ∈ Z t×t p . Since the sample space from which matrix W can be uniformly chosen is exactly of size t -1 i=0 (p tp i ), we have that H(A |P A ) can be obtained as follows:

indicate that it is a duplicate. Hence, the receiver accepts only one validated message.

The master key Km is sent to the destination whenever the key generator G needs to be refreshed. G has to be refreshed in the two following situations :

1. When a new session starts. In this case, the new master key becomes the session key.

2. When the key generator counter cnt reaches the threshold N . When this happens,

G is rekeyed with a new master key to extend its lifetime. The new master key is provided to the destination. The new key is used by both parties to replace the actual session key.

In the sequel, we present the different steps and elements of the protocol in detail.

Sessions: A set-up phase is required for initializing the state and the master key Km. In this phase, authentic and secret initial keying material is distributed by a trusted third party over a secure channel.

• First session. The tag and the sensor agree on an initial secret composed of an initial master key Km, an initial internal state seed and a shared token tkn. The cnt associated to function G is also initialized.

• i th session. At the beginning of the i th session (i.e., before refreshment), the sensor and the tag share the function G with the same properties as those used in the i -1 th session meaning that they use Km i-1 for generating derived keys. The period of generation is assumed to be still valid for unpredictable derived keys. After the establishment of the master key, the tag and the sensor share: (1) a secret master key Km i , (2) an internal state St i associated with a new counter cnt and (3) a token tkn i which are newly refreshed.

Refreshing G during the same session: When the generation counter cnt reaches the N value, the sensor sends a query for refreshing G as follows: the sensor sends to the tag Backward Secrecy: Figure 6.7(d) shows the results of the backward secrecy property evaluation. We consider two executions of the sensor. One execution in which the tag and the sensor establish a master key Km and where the last secrets of both the tag and the sensor (i.e., Km, State, T kn) are revealed to the adversary. The goal is to verify if this knowledge is sufficient to enable the adversary to compute the new master key N ewKm related to this execution. The results show that the protocol is insecure. CL-AtSe finds an attack on the secrecy of the new master key. Indeed, if the adversary follows all the messages sent in the network, it is possible to reconstruct the following master key N ewKm because the new derived key used to encrypt the message of refreshment (i.e., 3 rd pass in the Figure 6.2) can be computed. The new derived keys are based on the previous secrets that the adversary has already gained, and once obtaining these secrets, the adversary takes all the power of the target tag itself. He can trace it at least during the authentication immediately following the attack. This attack can be avoided by changing the adversary capacities. If the adversary does not eavesdrop on the tag continuously after the time of corruption, i.e., missing the master key establishment transaction, then it will not be possible to predict the next refreshed derived keys. This notion is known to restricted backward security through key insulation [START_REF] Song | RFID authentication protocol for low-cost tags[END_REF][START_REF] Lim | Strong and robust RFID authentication enabling perfect ownership transfer[END_REF]. This assumption has been assumed in previous efforts, like in [START_REF] Dolev | Rfid authentication efficient proactive information security within computational security[END_REF]. The assumption is realistic since in typical RFID system environments, tags and readers operate only at a short communication range and for a short periods of time.

Related Work