Joan Melià-Seguí

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

Jordi Herrera-Joancomartí

A Practical Implementation Attack on Weak Pseudorandom Number Generator Designs for EPC Gen2 Tags

Keywords: RFID, EPC Gen2, PRNG, Security, Eavesdropping, Attack implementation

The Electronic Product Code Generation 2 (EPC Gen2) is an international standard that proposes the use of Radio Frequency Identification (RFID) in the supply chain. It is designed to balance cost and functionality. As a consequence, security on board of EPC Gen2 tags is often minimal. It is, indeed, mainly based on the use of on board pseudorandomness, used to obscure the communication between readers and tags; and to acknowledge the proper execution of password-protected operations. In this paper, we present a practical implementation attack on a weak pseudorandom number generator (PRNG) designed specifically for EPC Gen2 tags. 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.

Introduction

The Electronic Product Code Generation 2 (EPC Gen2) is an international standard that proposes the use of Radio Frequency Identification (RFID) in the supply chain. It is designed to balance cost and functionality. The development of Gen2 tags faces, in fact, several challenging constraints such as cost, compatibility regulations, power consumption, and performance requirements. As a consequence, the computational capabilities of Gen2 tags are very simple. In this sense, the Gen2 specification only considers two basic on board security features: pseudorandom number generators (PRNGs) and password-protected operations. The pseudorandomness offered by on board PRNGs is, indeed, used to protect the password-protected operations. PRNGs are also used as an anti-collision mechanism for inventorying processes [START_REF] Epcglobal | EPC Radio-Frequency Identity Protocols Class-1 Generation-2 UHF RFID Protocol for Communications at 860-960 MHz[END_REF]; and to acknowledge other Gen2 specific operations (e.g., memory writing, decommission of tags, and self-destruction). PRNGs are, therefore, the crucial components that guarantee Gen2 security.

The use of weak PRNGs that allow the predictability of the outgoing sequences introduces important security flaws in EPC communications. For example, it allows an attacker to bypass the security of the password-protected commands defined in the Gen2 standard (e.g., the access and the kill commands [START_REF] Epcglobal | EPC Radio-Frequency Identity Protocols Class-1 Generation-2 UHF RFID Protocol for Communications at 860-960 MHz[END_REF]). The execution of these commands is processed by the tag if a 32-bit value, stored in the reserved memory of the tag, is provided by the reader. Therefore, if a compliant reader wants to request the execution of these special commands, it must provide an appropriate copy of the 32-bit password values. The security model of the EPC Gen2 specification considers that the reader-to-tag channel requires protection to handle an eventual eavesdropping of these values. For this reason, the reader must obscure the transmission of the 32-bit password values. To do so, the reader requests beforehand two 16-bit pseudorandom sequences to the tag. These two sequences are computed by the on-board PRNG of the tag, and sent as cleartext to the reader (notice that the EPC Gen2 specification does not require protection for the tag-to-reader channel). Once obtained the two pseudorandom sequences, the reader transmits the 32-bit password values in two steps: [START_REF] Epcglobal | EPC Radio-Frequency Identity Protocols Class-1 Generation-2 UHF RFID Protocol for Communications at 860-960 MHz[END_REF] it obscures the 16 lowest bits of the password by an exclusive OR (XOR) logical operation with the first pseudorandom sequence, and transmits the resulting first half-password; (2) it obscures the remainder 16 bits of the password by XORing them with the second pseudorandom sequence, and transmits the resulting second half-password. Since the attacker is not supposed to be capable of eavesdropping the tag-to-reader channel, the only (practical) way to retrieve the password values must come from the eavesdropping of the reader-to-tag channel. This is indeed possible if the on-board tag's PRNG is predictable. The attacker can apply, for instance, an active scanning of the tags, to analyze the predictability of their pseudorandom sequences; or a passive eavesdropping of reader-to-tag acknowledgments, with the same purpose of analyzing the predictability of tags' pseudorandom sequences. If either attack succeeds, it then suffices to apply a simple XOR operation with the predicted sequences and the contents of the messages transmitted over the reader-to-tag channel to decrypt the remainder ciphertext (e.g., the protected half-passwords).

In this paper, we analyze the proposal presented in [START_REF] Che | Chapter 16, A Random Number Generator for Application in RFID Tags[END_REF], in which the authors describe the construction of a cost-effective PRNG for EPC Gen2 devices. We demon-strate, by implementing a practical attack, that their approach is not secure. An attacker may obtain the PRNG configuration with very few observations and then he is able to derive the whole pseudorandom sequence. 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.

The paper is organized as follows. Section 2 discusses the challenges of designing PRNGs for EPC Gen2 tags, reviews some proposals and finally describes the suitability of using linear feedback shift registers (LFSRs) for the generation of pseudorandom sequences. The section also describes the proposal presented by Che et al. in [START_REF] Che | Chapter 16, A Random Number Generator for Application in RFID Tags[END_REF]. In Section 3, we present an 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 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. Finally, Section 5 concludes the paper and gives some ideas for further research.

Pseudorandom number generators for EPC Gentag

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 | Chapter 8, 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 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. 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 | Lightweight Cryptography in Radio Frequency Identification (RFID) Systems[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 [START_REF] Garcia | Dismantling MIFARE Classic[END_REF] that has shown a vulnerable PRNG.

Few PRNG proposals have been presented in the scientific literature specifically designed for EPC tags. To the best of our knowledge, only three papers explicitly propose PRNG for EPC tags. On one hand, Peris-Lopez et al. present in [START_REF] Peris-Lopez | LAMED A PRNG for EPC Class-1 Generation-2 RFID specification[END_REF] 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 32-bit PRNG. The authors also propose an alternative 16bit 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 other designs in the literature. On the other hand, Che et al. describe in [START_REF] Che | Chapter 16, A Random Number Generator for Application in RFID Tags[END_REF] a hybrid approach that combines the use of Linear Feedback Shift Registers (LFSR) and physical properties to build random sequences (see Section 2.3 for a detailed description of their scheme). A similar idea has been also used in [START_REF] Melia-Segui | Analysis and Improvement of a Pseudorandom Number Generator for EPC Gen2 Tags[END_REF] to design a PRNG. In this case the authors handle the inherent linearity of LFSRs by means of a multiple-polynomial approach. The authors present a secure PRNG design suitable to the current EPC Gen2 technology, providing evidences of statistical and hardware compatibility.

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. A 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 a LFSR is basically an exclusive OR logical operation (XOR) 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 s k+n+1 • • • s k+2n-1           b n b n-1 . . . b 1      =      s k+n+1 s k+n+2 . . . s k+2n      (1)
By solving Equation (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 [START_REF] Garcia | Dismantling MIFARE Classic[END_REF] have demonstrated the vulnerability of this kind of generators when the non-linear function is not taken carefully. Another approach to break the linearity of a 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 this constructions is statistically weak, being vulnerable to correlation or side-channel attacks [START_REF] Joux | Algorithmic Cryptanalysis[END_REF]. Also 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-totag 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 [START_REF] Che | Chapter 16, A Random Number Generator for Application in RFID Tags[END_REF] 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. However, as we review later in this paper, their approach does not achieve the objective to break the linearity of the output sequence. In [START_REF] Melia-Segui | Analysis and Improvement of a Pseudorandom Number Generator for EPC Gen2 Tags[END_REF], authors also combine true random data and LFSRs to create a PRNG.

A part of these two proposals, there are not many references in the literature that combine true random data and LFSR to obtain a good PRNG. The main reason, as we already stated, is that the obtained PRNG cannot be used as an additive stream cipher for a standard sender-receiver communication model due to the infeasibility of reproducing the same sequence at both communication parts since the cipher sequence will be affected by a true random source.

The Che et al. proposal

In [START_REF] Che | Chapter 16, A Random Number Generator for Application in RFID Tags[END_REF], 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 a LFSR (cf. Figure 1). Adding a 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 | Chapter 16, A Random Number Generator for Application in RFID Tags[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

In this section, we present an analysis of the PRNG proposal presented by Che et al. described above. We give the details of a statistical analysis, performed over the output data, based on the NIST statistical test for pseudorandomness. Based on these results, we detail an attack that, given a small number of output bits, can determine the whole sequence.

Che et al. statistical analysis

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 use a hypothesis test considering the randomness of the sequence as the null hypothesis H 0 , and the non-randomness as the alternative hypothesis, H a . Tests are performed regarding a level of significance or critical value, denoted as α hereinafter.

NIST tests produce P-values summarizing the strength of the hypothesis. If Pvalues ≥ α, 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 (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 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 2).

In order to evaluate the randomness quality of the sequence produced by the Che et al. scheme, we have generated 230 MB of output data from an implementation of their proposed PRNG. Such data has been divided in ten different data sequences (T i ) that have been independently analyzed using the NIST suit tests.

NIST test results for the Che et al. random generated data are presented in Table 1. Each column represents 23 MB of pseudorandom data generated with different seed and true random source. 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 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.

Results show a statistical evidence of non randomness for the Binary Matrix Rank Test (cf. Table 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, 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 2.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 Section 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 breaking the linearity of the underlying LFSR. In fact, a specific attack to break the Che et al. PRNG based on the inherent linearity of the LFSR has been 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 a LFSR XORed in its first cell with a truly random bit (cf. Figure 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 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.

|2n|

Eq. 1

Eq. 1

Eq. 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. The remainder n -1 subsequences, have been 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. The probability of such event is 1 8 . Then, from this fact, we can derive Equation 3 which provides the probability of success of an attack that analyzes a sequence with |s a | = 3n -1:

B 1 B 2 B n (∀i =1. . . n)
P success (3n -1) = 1 4 1 n + 1 8 n -1 n = n + 1 8n (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 shows the probability of success of an attack with s a length for a particular system with a 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 has been implemented over the same ten pseudorandom sequences (T i ) used to execute the NIST tests (cf. Section 3.1).

The first analysis validates that the probability of finding the feedback polynomial matches the one described in Equation 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 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 have been performed for every T i data sequence taking the first bit of s a at random. Results presented in Table 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 the RFID devices used to implement the attack. We also describe the implementation scenario and the techniques used to eavesdrop the PRNG from the RFID communication. Finally the practical results are presented.

Background on the IAIK UHF demo tag

The IAIK UHF demo tag [START_REF]UHF RFID Demo Tag[END_REF] 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) 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 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 [START_REF]UHF RFID Demo Tag[END_REF][START_REF] Aigner | BRIDGE -Building Radio frequency IDentification for the Global Environment[END_REF].

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 reader-to-tag channel. It does, indeed, rectification, voltage multiplication, and envelope detection all at once [START_REF] Aigner | BRIDGE -Building Radio frequency IDentification for the Global Environment[END_REF]. 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 [16]. 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 main signals connect the microncontroller to the RF front-end. A first signal, called DEMOD, 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 [START_REF]UHF RFID Demo Tag[END_REF][START_REF] Aigner | BRIDGE -Building Radio frequency IDentification for the Global Environment[END_REF], and citations thereof, for more information.

Che et al. implementation and experimental setup

In Section 3.2, we have seen how to attack the pseudorandom number generator proposed by Che et al. once a sufficient number of pseudorandom values are collected. We show in this section the results of a practical attack against the vulnerable scheme on a real Gen2 setup. The attack is based on the eavesdropping of the communication between a standard EPC Gen2 reader and the demo tag. Indeed, we show how it is possible to obtain an appropriate set of random queries generated by an on-board PRNG, based on the Che et al. scheme, to eventually predict the generation of pseudorandom sequences that will be generated later over the demo tag. Figure 4 shows our experimental setup.

The Che et al. 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 original scheme provided in [START_REF] Che | Chapter 16, A Random Number Generator for Application in RFID Tags[END_REF] has been adapted into a code-optimized EPC Gen2 version that can be executed over the microcontroller of the IAIK UHF demo tag. Arithmetic efficient functions such as bit shifts, logic operators (AND, OR and XOR) and modulo 2, are used to implement the LFSR in the demo tag [START_REF] Schneier | Applied Cryptography[END_REF]. The trn addition is extracted from the less significant bits of the analogical to digital conversion in the demo tag's microcontroller. Since the generation of pseudorandom sequences is a mandatory operation specified in the EPC Gen2 protocol, an existing PRNG function is already included in the original firmware. By using the Crossworks IDE, we code and merge the PRNG based on the This application enable us to generate the set of queries required to proceed with the eavesdropping attack. Finally, we use Matlab to decode the set of responses generated over the demo tag. This operation enable us to isolate 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.2. We provide in the sequel further details about the collection of pseudorandom sequences and the practical results.

Eavesdropping of pseudorandom 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 | Lightweight Cryptography in Radio Frequency Identification (RFID) Systems[END_REF]. Some reader-to-tag queries include pseudorandom sequences (hereinafter denoted Fig. 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 as RN16s) that are computed from the on-board PRNG included on the EPC tags. Table 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].

A 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. Let us 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, 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. In 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 5 consecutive bits generated from the PRNG of an EPC Gen2 tag, as specified in the standard [START_REF] Epcglobal | EPC Radio-Frequency Identity Protocols Class-1 Generation-2 UHF RFID Protocol for Communications at 860-960 MHz[END_REF].

As we pointed out in Section 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) is enough to obtain the feedback polynomial of the LFSR with a confidence of about 42%. This value is consistent with the analytical results we anticipated in the previous section, and that are depicted in Figure 3. The complete set of experiments that we summarize in Figure 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 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.2 (Figure 3). Therefore, we are able to confirm the vulnerability of the Che et al. PRNG for Gen2 environments.

Conclusions

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 paper, 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 et al. [START_REF] Che | Chapter 16, A Random Number Generator for Application in RFID Tags[END_REF]. The proposal combines thermal noise signal modulation and an underlying LFSR. We have indeed 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 [START_REF]UHF RFID Demo Tag[END_REF] 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. Future work goes towards designing an efficient and robust PRNG that fulfills the specific restrictions of EPC Gen2 tags, following the work presented in [START_REF] Melia-Segui | Analysis and Improvement of a Pseudorandom Number Generator for EPC Gen2 Tags[END_REF].

Fig. 1

 1 Fig. 1 PRNG scheme based on the Che et al. specifications

Fig. 2

 2 Fig. 2 Attack scheme to the Che et al. PRNG

Fig. 3

 3 Fig. 3 Reliability on the Che et al. attack regarding |sa|

Fig. 4

 4 Fig. 4 Experimental setup. In (a), we can see the CAEN A829EU 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 5 (

 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.

Table 1

 1 Che et al. results for the NIST statistical test suite

	Sequence	T 1	T 2	T 3	T 4	T 5	T 6	T 7	T 8	T 9		T 10
	Frequency	0.99 0.98 0.96 1.00 1.00 0.97 0.97 0.99	0.96	0.97
	BlockFrequency	1.00 1.00 0.97 0.98 1.00 0.98 1.00 0.99	0.98	0.99
	Runs	0.98 1.00 1.00 0.99 0.99 0.99 0.96 0.98	0.98	1.00
	LongestRun	0.96 0.96 0.98 0.97	0.94	0.96 0.95 0.98	0.99	0.94
	Binary Matrix Rank	0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00	0.00	0.00
	OverlappingTemplate	0.96	0.94 0.99 0.98 0.98	0.93 0.97 0.98	0.98	0.95
	Universal	1.00 0.99 0.98 0.99 1.00 0.97 0.99 0.99	0.99	0.98
	ApproximateEntropy	0.99 0.97 1.00 0.99 0.98 0.98 0.99 1.00	1.00	1.00
	LinearComplexity	0.99 1.00 0.99 0.99	0.95	1.00 1.00 0.99	0.99	1.00
	CumulativeSums	2 2	2 2	2 2	2 2	2 2	2 2	2 2	2 2	2 2		2 2
	NonPeriodicTemplate	148 148	148 148	148 148	148 148	148 148	148 148	148 148	148 148	147 148	⋆	148 148
	RandomExcursions	7 8	⋆	7 8	⋆	8 8	7 8	⋆	8 8	7 8	⋆	8 8	6 8	⋆	8 8		8 8
	RandomExcursionsVariant	18 18

Table 2

 2 Attack success rate for |sa| = 3n -1

	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

 3 Value of |sa| 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
	|sa|	238	254	254	190	510	158	254	286	238	222

Table 4

 4 Minimum number of RN16s involved in EPC Gen2 operations

	Operation	Inventory		Access
	Command	Identification	Read Write	Lock Kill
	Number of RN16s	1	2	8	2	4

(a) EPC Gen2 write protocol.

(b) Real capture of six write cycles.

  (a). The eight generated RN16s represent 128 Che et al. PRNG attack success for real Gen2 environment

		46%
	Attack success (%)	40% 42% 44% 38%							Theoretical rate
									Attack rate
		36%
		T 1	T 2	T 3	T 4	T 5	T 6	T 7	T 8	T 9	T 10
			Demotag generated sequences (1000 write challenges)
	Fig. 6

Acknowledgements This work has been supported by the Spanish Ministry of Science and Innovation, the FEDER funds under the grants TSI2007-65406-C03-03 E-AEGIS, CONSOLIDER CSD2007-00004 ARES, an IN3-UOC doctoral fellowship, and the Institut TELECOM through its Futur et Ruptures program.


Stere Boulahia

Preda

J Garcia-Alfaro

F Cuppens

N Cuppens-Boulahia

S Preda

MIRAGE: a

Keywords: {1.0.1.[0, 255]:any, 2.0.12.[0, 255]:any} → false C1{R2}: {1.0.2.[0, 255]:any, 2.0.12.[0, 255]:any} → false C1{R3}: {1.0.3.[20, 33]:any, 1.0.1.[20, 30]:any} → false C1{R4}: {1.0.3.[60, 80]:any, 1.0.1.[20, 30]:any} → false C1{R5}: {2.0.11.[0, 30]:any, 1.0.2.[10, 30]:any} → false C1{R6}: {2.0.9.[10, 20]:any, 1.0.1.[0, 255]:any} → true C1{R7}: {2.0.11.[0, 255]:any, 1.0.1.[10, 12]:any} → true C3{R1}: {1.0.3.[20, 33]:any, 2.0.1.[20, 30]:any} → false C3{R2}: {1.0.3.[60, 80]:any, 2.0.1.[20, 30]:any} → false C6{R1}: {1.0.4.[0, 255]:any, 2.0.6.[0, 255]:any} → true C6{R2}: {1.0.5.[18, 20]:any, 2.0.6.[0, 255]:any} → true C6{R3}: {1.0.3.[10, 20]:any, 1.0.1.[0, 255]:any} → true C6{R4}: {1.0.3.[21, 70]:any, 1.0.1.[0, 255]:any} → true C6{R5}: {1.0.4.[0, 255]:any, 2.0.3.[0, 255]:any} → true C6{R6}: {1.0.5.[18, 20]:any, 2.0.3.[0, 255]:any} → true C6{R7}: {1.0.3.[10, 23]:any, 2.0.1.[0, 255]:any} → true C6{R8}: {1.0.3.[24, 60]:any, 2.0.1.[0, 255]:any} → true C2{R1}: {2.0.8.[15, 17]:any, 1.0.1.[0, 255]:any} → false C2{R2}: {2.0.10.[0, 70]:any, 2.0.7.[0, 255]:any} → false C2{R3}: {2.0.10.[0, 70]:any, 1.0.2.[0, 255]:any} → false C2{R4}: {2.0.11.[0, 255]:any, 1.0.1.[0, 255]:any} → false C2{R5}: {2.0.10.[0, 70]:any, 2.0.4.[0, 255]:any} → false C2{R6}: {1.0.[1.0, 2.255]:any, 2.0.12.[0, 255]:any} → false C4{R1}: {2.0.10.10:any, 2.0.4.[0, 255]:any} → true C4{R2}: {2.0.10.[60, 80]:any, 2.0.4.[0, 255]:any} → true C4{R3}: {1.0.4.[15, 30]:any, 2.0.3.[0, 255]:any} → true C4{R4}: {1.0.5.[0, 255]:any, 2.0.3.[0, 255]:any} → true C4{R5}: {1.0.3.[18, 20]:any, 2.0.5.[0, 255]:any} → true C5{R1}: {2.0.10.10:any, 2.0.7.[0, 255]:any} → true C5{R2}: {2.0.10.[60, 80]:any, 2.0.7.[0, 255]:any} → true C5{R3}: {1.0.4.[15, 30]:any, 2.0.6.[0, 255]:any} → true C5{R4}: {1.0.5.[0, 255]:any, 2.0.6.[0, 255]:any} → true C5{R5}: {1.0.3.[18, 20]:any, 2.0.8.[0, 255]:any} → true

Introduction

Despite the advances in the field of network security technologies, such as filtering of traffic, use of encrypted communications, and deployment of authentication mechanisms, there may always be errors or flaws that can be exploited by unauthorized parties. The use of firewalls, NIDSs (network intrusion detection systems), and VPN (Virtual Private Network) routers, is still the dominant method to survey and guarantee the security policy in current corporate networks. The configuration of these components is based on the distribution of security rules that state what is permitted and what is prohibited in a system during normal operations. This configuration must be consistent, addressing the same decisions under equivalent conditions, and not repeating the same actions more than once. Otherwise, the existence of anomalies in their configuration rules may lead to weak security policies (potentially easy to be evaded by unauthorized parties). The update of the component configurations can also introduce new anomalies. There is, therefore, a clear need of support tools to guide the operators when performing such tasks.

Our research work has studied the combination of two main strategies in order to manage this problem. The first strategy is the use of an audit mechanism that analyzes already deployed configurations, signals inconsistencies, and yields consistent configurations. Through this mechanism, moreover, we can fold existing policies and create a consistent and global set of rules -easy to maintain and manage by using a single syntax [START_REF] Garcia-Alfaro | Aggregating and Deploying Network Access Control Policies[END_REF]. The second strategy is the use of a refinement mechanism that guarantees the proper deployment of such rules into new systems, yet free of inconsistencies. These two research strategies have been implemented into a software prototype called MIRAGE (which stands for MIsconfiguRAtion manaGEr).

Developed as a web service, MIRAGE can autonomously be executed under the control of several operators in order to offer the system with the following functions:

(1) an intra-component analysis which detects inconsistencies between rules within single security component policies [START_REF] Cuppens | Misconfiguration management of network security components[END_REF]; [START_REF]The B-Book -Assigning Programs to Meanings[END_REF] an inter-component analysis of rules to detect inconsistencies between configurations of different devices [START_REF] Garcia-Alfaro | Complete Analysis of Configuration Rules to Guarantee Reliable Network Security Policies[END_REF]; [START_REF] Adiseshu | Detecting and resolving packet filter conflicts[END_REF] an aggregation mechanism to fold all the existing policies into a single, and consistent, global set of rules [START_REF] Garcia-Alfaro | Aggregating and Deploying Network Access Control Policies[END_REF]; and (4) a refinement process to properly deploy the global set of rules over new security components [START_REF] Preda | A Semantic Context Aware Security Policy Deployment[END_REF][START_REF] Preda | Model-driven Security Policy Deployment: Property Oriented Approach[END_REF]. In all four cases, MIRAGE utilizes a description of the topology of the whole security architecture.

The use of MIRAGE can highly benefit the maintenance of multihomed autonomous systems. It might remain connected to the network and provide assistance to the complete set of component in the event of configuration maintenance or redeployment of configuration to face events such as detection of malicious activity or failures. In this sense, the refinement mechanism offered by MIRAGE guarantees that the set of rules deployed over the different components of a system is always consistent, not redundant, and optimal [START_REF] Preda | Architecture-Aware Adaptive Deployment of Contextual Security Policies[END_REF].

Paper Organization -Section 2 reviews recent results implemented in the MI-RAGE prototype for guaranteeing correctness and consistency on single and distributed network security policies. Section 3 compares these approaches implemented in MIRAGE with other solutions proposed in both the science and the industry community. Section 4 closes the paper.

MIRAGE Prototype

MIRAGE is a management tool for guaranteeing the correctness and the consistency of configuration rules on single and distributed network security policies. It implements an analysis of components' configurations (i.e., configurations of firewalls, NIDSs, and VPN routers) to detect anomalies on their deployment. To do so, MIRAGE implements four main functions: intra-component analysis for the detection of inconsistencies between configuration rules within single security component policies; inter-component analysis of rules to detect inconsistencies between configurations of different devices; aggregation of policies for the creation of a consistent and global set of rules; and refinement mechanism for the deployment of global policies over the different components of new systems. We address in the sequel the key aspects of some of these functionalities implemented in the current version of our prototype.

Bottom-Up Analysis of Network Configurations

We assume here that a security policy has been empirically deployed into the network based on security administrator expertise and flair. It is then advisable to analyze the security rules deployed to detect and correct policy inconsistencies. These inconsistencies are often the origin of security holes exploited by dishonest parties. MIRAGE addresses this process and provides a discovery of inconsistencies and redundancies from component configurations. This process is presented based on two different schemes: (1) single-and (2) multi-component analysis.

Single-component Analysis

MIRAGE provides a deterministic process to detect inconsistencies in the configuration of security components. It considers that these devices are configured in a standalone manner, using a set of configuration rules (e.g., filtering rules in the case of a firewall; and alerting rules in the case of a NIDS). A general configuration rule is defined as follows:

R i :

{condition i } → decision i (1)
Regarding the previous expression, i is the relative position of a rule in the set, {condition i } is a conjunctive set of condition attributes such that {condition i } equals A 1 ∧ A 2 ∧ ... ∧ A p -being p the number of attributes of the given rule -and decision is a boolean value in {true, f alse}. For example, the decision of a filtering rule is positive (true) when it applies to a specific value related to deny the traffic it matches; and negative ( f alse) when it points to accept the traffic it matches. Similarly, the decision field of an alerting rule is positive (true) when it applies to a specific value related to alert about the traffic it matches; and negative ( f alse) when it applies to a specific value related to ignore the traffic it matches. Based on the sample scenario depicted by Figure 1, and its associated set of rules, we define the following set of anomalies detected by the intra-component audit process.

• Intra-component Shadowing -A configuration rule R i is shadowed in a set of configuration rules R when such a rule never applies because all the packets that R i may match, are previously matched by another rule, or combination of rules, with higher priority. E.g., rule R 6 is shadowed by the overlapping of rules R 3 ∪R 5 .

• Intra-component Redundancy -A configuration rule R i is redundant in a set of configuration rules R when the following conditions hold: (1) R i is not shadowed by any other rule or set of rules; (2) when removing R i from R, the security policy does not change. E.g., rule R 4 is redundant to R 3 ∪ R 5 .

• Intra-component Irrelevance -A configuration rule R i is irrelevant when (1) source and destination addresses are within the same zone or (2) the component does not appear in the minimal route that connects the source zone (i.e., the rule matches traffic that never reaches the component). E.g., rule R 1 is irrelevant since both source and destination are in network 1.0.1.0/24. Rule R 2 is also irrelevant since the filtering device is not part of the minimal route between networks 1.0.2.0/24 and 1.0.3.0/24.

The reader can find in [START_REF] Cuppens | Misconfiguration management of network security components[END_REF][START_REF] Garcia-Alfaro | Complete Analysis of Configuration Rules to Guarantee Reliable Network Security Policies[END_REF] the algorithms that enable MIRAGE the detection of the inconsistencies presented in this section, as well as correctness and computational complexity of the algorithms. Although we show that the theoretical complexity of the algorithms is very high, we show with a series of experimentations (cf. [START_REF] Garcia-Alfaro | Complete Analysis of Configuration Rules to Guarantee Reliable Network Security Policies[END_REF], Section 6) that we are always very far from the worst case. Indeed, only few attributes, such as source and destination addresses, may significantly overlap and exercice a bad influence on the algorithms complexity. Other attributes, such as the protocol or the port numbers, are generally equal or completely different when combining configuration rules. Moreover, when anomalies are discovered, some rules are removed -which significantly reduces the algorithms complexity.

Multi-component analysis

MIRAGE provides a second audit process to analyze multi-component setups (e.g., distributed architectures with firewalls and NIDSs in charge of multiple network security policies). In this sense, it can assume, for instance, that the role for detecting and preventing network attacks is assigned to several components. It will, then, look for inconsistencies hidden in their configurations. The detection process is based on the similarity between the parameters of configuration rules such as filtering an alerting rules. It checks, indeed, if there are errors in the configurations by comparing the policy deployment over each component that matches the same traffic. Based on the sample scenario depicted by Figure 2, we show in the sequel an example of the kind of inconsistencies detected by the inter-component audit process of MIRAGE.

• Inter-component Shadowing -A shadowing anomaly occurs between two components when the following conditions hold: (1) The component that is located closest to the origin of the traffic is a filtering device (e.g., a firewall); (2) The component where the anomaly is detected does not block or report (completely or partially) traffic that is blocked (explicitly, by means of positive rules; or implicitly, by means of its default policy), by the first component in the path (closest to the source). The following table shows some examples.

Rules Anomaly C 6 {R 7 } ∪C 6 {R 8 } shadows C 3 {R 1 } full shadowing C 6 {R 8 } partially shadows C 3 {R 2 } explicit partial shadowing Close policy of C 2 shadows C 1 {R 5 } implicit full shadowing
• Inter-component Redundancy -A redundancy anomaly occurs between two components when the following conditions hold: (1) The component that is located closest to the origin of the traffic is a filtering device (e.g., a firewall); [START_REF]The B-Book -Assigning Programs to Meanings[END_REF] The component where the anomaly is detected, blocks or reports (completely or partially) traffic that is already blocked by the first component. This kind of redundancy is often introduced by network officers expressly. It is important, however to alert about it, to warn the administrator that the rule has a special meaning (e.g., a message warning that if the rule applies, the upstream filtering devices are not working properly). The following table shows some examples. The reader can find in [START_REF] Garcia-Alfaro | Complete Analysis of Configuration Rules to Guarantee Reliable Network Security Policies[END_REF] the algorithms that enable MIRAGE the detection of the inconsistencies presented in this section, as well as correctness profs, computational complexity, and experimental results. The complete set of analyzed configuration can be aggregated into a single, and consistent, global set of rules by using the aggregation mechanism presented in [START_REF] Garcia-Alfaro | Aggregating and Deploying Network Access Control Policies[END_REF]. This global policy is, in fact, the main source of information used by the refinement mechanism presented in the sequel.

Rules Anomaly C 6 {R 1 } is redundant to C 5 {R 3 } full redundancy C 6 {R 5 } is redundant to C 4 {R 3 } full redundancy C 6 {R 2 } is redundant to C 5 {R 4 } partial redundancy C 6 {R 6 } is redundant to C 4 {R 4 } partial redundancy

Top-Down Refinement of Global Policies

A second approach to address the management of consistency and correctness of network policies is the use of refinement mechanisms. In this way, we can perform a downward deployment of rules by unfolding a global set of security policies into the configurations of several components and guaranteeing that the deployed configurations are free of anomalies. In [START_REF] Cuppens | A formal approach to specify and deploy a network security policy Second Workshop on Formal Aspects in Security and Trust[END_REF], for example, we presented a refinement mechanism that uses a formal model for the generation of filtering rules by transforming general rules into specific configuration rules. We address in this section some functionalities addressed by MIRAGE in this sense.

Model-driven Policy Deployment

If manually carried out, the process of deploying network security policies is often errorprone. In fact, without the right structural knowledge of the policy, the deployment of conflicting security requirements becomes very likely. This highlights the necessity of a more structured policy expression, i.e., only a formalized expression of the security policy may guarantee an error-free security policy to be deployed, with no ambiguities, no inconsistencies, no redundancies and no unnecessary details. Thus MIRAGE considers that an access control model and a formalized security policy is the first step toward enforcing by refinement the security of the system. MIRAGE takes full advantage of the OrBAC model (Organization Based Access Control) [START_REF] Abou El Kalam | Organization Based Access Control[END_REF] which is an extension of RBAC [START_REF] Sandhu | Role-Based Access Control Models[END_REF]. OrBAC presents a high abstraction level and covers a large panel of security policies since it natively provides means to express both static requirements (i.e., they are enforced once and for all) and contextual requirements (i.e., dynamic requirements). The OrBAC notions of role, activity, and view and also context prove very useful: the complexity of both the system (tens of firewalls, NIDSs, and VPN routers) and the policy (static and dynamic security requirements) is no longer an issue. The role regroups subjects (concrete network entities), the activityactions (network services), the viewobjects (e.g., IP packets, network entities) on which the same rules apply respectively. The notion of context confers the possibility to address a larger variety and also a finer granularity of security requirements, it captures the conditions (e.g., environmental factors) in which the security requirements are enforced and met. The OrBAC context allows the specification of these conditions directly at an abstract policy level.

The policy refinement mechanism of MIRAGE is in fact a set of deployment algorithms which constitutes the downward process: an OrBAC error-free security policy is refined into packages of rules for each security device in the given network. The aim is the correct deployment of a security policy, and this is achievable if some specific security properties are verified at the end. Such properties guarantee that no intra-nor inter-component anomalies are introduced (cf. Section 2.1). The formal frame to design the refinement mechanism of MIRAGE is presented in [START_REF] Preda | Model-driven Security Policy Deployment: Property Oriented Approach[END_REF]. The policy deployment algorithms are developed using the B Method [START_REF]The B-Book -Assigning Programs to Meanings[END_REF], a theorem proving method. The B Method offers the means to cope with the issue of stating the interesting security properties: besides an appropriate modeling language for both the OrBAC policy and the system/network specifications, it allows a formal expression of the properties related to the management of the intraand inter-configuration anomalies during the downward process. This is ensured by some B invariants. Thus, from the early stage of their B development (i.e., abstract B specification), the policy deployment algorithms of MIRAGE target the interesting security properties. Examples of security properties we took into account, and expressed as B invariants, in [START_REF] Preda | Model-driven Security Policy Deployment: Property Oriented Approach[END_REF] are:

• Completeness -This property states that if the network path from a subject to an object is correctly computed (i.e., it exists and the security components belonging to this path have the right functionalities with respect to the current context i ) the security OrBAC rule Is permitted(subject, action, object, context i ) may and will be deployed. Clearly, this property is closely related to the network's architecture and the assumption of connectedness in the network architecture is required.

• All traffic are regulated by filtering components -This property is verified if there is, at least, exactly one firewall or one IPS on the path between the current subject and object.

• Integrity and confidentiality -These two properties are related to the establishment of VPN tunnels. The verification starts at higher levels: the current OrBAC security rule should be defined with a protected context -meaning that the trafic filtered by the associated rules must be protected by the VPN tunnels. Then, if a path is computed between the subject and the object and a VPN tunnel can be established on this path, the integrity and confidentiality properties are verified.

The work in [START_REF] Preda | Model-driven Security Policy Deployment: Property Oriented Approach[END_REF] presents a complete analysis of security properties. Some may be specified at higher levels [START_REF] Benaissa | Integration of Security Policy into System Modeling[END_REF] and some may be identified from specific security requirements. The MIRAGE deployment algorithms were formally proved with the assumption of a conflict-free OrBAC policy and of a correct system architecture, i.e., no lack of security functionalities in the security components placed on the shortest-paths. Hence, as long as the system embeds all necessary security functionalities, there are no concerns in deploying the policies. The refinement provided by MIRAGE is a certified algorithm for a reliable and automatic security policy deployment. It is, however, realistic to consider that sometimes the system lacks some necessary security functionalities. Our proposed solutions to this problem are presented in the sequel.

Context Aware Policy Deployment

The security policies become more and more contextual. (Re)deploying a contextual security policy depends on the security device functionalities: either (1) the devices include all functionalities necessary to handle a context and the policy is consequently deployed to ensure its automatic changes or (2) the devices do not have the right functionalities to interpret a contextual requirement in its entirety. MIRAGE proposes two solutions to cope with the issue of the (re)deployment of access control policies in a system that lacks the necessary functionalities to deal with contexts:

1. Dynamic deployment: MIRAGE considers a central entity (hereafter called PDP -Policy Decision Point) which (partially) manages some contexts. 2. Optimization deployment: if the previous solution does not stand.

Obviously, the OrBAC formalism is maintained. These two solutions presented in [START_REF] Preda | A Semantic Context Aware Security Policy Deployment[END_REF] and [START_REF] Preda | Architecture-Aware Adaptive Deployment of Contextual Security Policies[END_REF] respectively can then be jointly used whenever the security devices (hereafter called PEPs -Policy Enforcement Points) are not rich enough in functionalities so as to manage all contexts by themselves. In this way, a complete deployment of the (contextual) policy may be achieved.

The Methodology

Let SR = (Decision, Role, Activity, View, Ctx) be a security rule of the OrBAC policy P (SR ∈ P) and SR ′ = (Decision, Role, Activity, View, Ctx ′ ) with Decision ∈ {Permission, Prohibition}. We call SR ′ the SR contextual version over the context Ctx ′ . Let PEP i be an enforcement point able to manage only the context Ctx ′ and SR be the security rule PEP i must enforce. We investigate how SR ′ can be deployed and thus enforced by PEP i even if Ctx ′ is not equal to the context Ctx of the initial rule SR to be deployed. The final aim is to deploy the SR rule and one of the following situations appears:

• Case 1 -The PEP i manages the entire Ctx context. The rule SR is directly deployed over PEP i and the PDP does not manage SR anymore. Otherwise, the PDP has to manage a part of the Ctx context.

• Case 2 -The PEP i manages only Ctx 2 , a part of the Ctx context. We note this case as Ctx 1 = Ctx -Ctx 2 . The deployment is dynamic and the PDP manages Ctx 1 : the PDP must deploy SR ′ , the SR contextual version over Ctx 2 on the PEP i when Ctx 1 becomes active. Once Ctx 1 is deactivated, the PDP must be able to retrieve the deployed SR ′ from PEP i . For example and as suggested in [START_REF] Preda | A Semantic Context Aware Security Policy Deployment[END_REF], Ctx 1 may represent a threat context activated by the detection of some intrusion. Thus, Case 2 provides means to dynamically redeploy the policy to face this intrusion. This represents the dynamic deployment solution.

• Case 3 -Neither the PEP i , nor the PEP i and the PDP working together manage the Ctx context. Then, two solutions are possible: (I) there may be a context closely related with Ctx which is still managed by the system as described in Case 2 (in fact, we refer to the OrBAC context hierarchies); or (II) if the system does not provide hierarchies, the last option is to find a security functionality closely-equivalent to the one necessary to handle the Ctx context. Both (I) and (II) represent the best deployed policy solution.

Dynamic Deployment

The formalization of this solution is based on the use of ECA (Event Condition Action) [START_REF] Baral | Formal Characterization of Active Databases[END_REF]. The algorithms running at the PDP level deploy (or retrieve) security rules over the PEPs when the contexts are activated (or deactivated). To be effective, this solution requires a specific communication protocol between the PDP and the PEPs. Actually our method uses the Netconf (cf. http://www.ops.ietf.org/netconf/) protocol with the Yencap (cf. http://ensuite.sourceforge.net/) open-source implementation which we adapted accordingly. Several performance tests were realized and presented in [START_REF] Preda | A Semantic Context Aware Security Policy Deployment[END_REF]. The results proved to be satisfactory.

Best Deployed Policy

There are scenarios in which the PDP and/or PEPs cannot entirely handle the Ctx context related to an SR rule. Instead of skipping such rules (with the result of, for example, a too restrictive deployed policy at the end), MIRAGE proposes the following solutions of: (1) finding a closely related context to the unmanaged one and which may be managed by the PDP and/or PEP and/or (2) finding a close enough functionality to deal with the unmanaged context if solution (1) does not apply. OrBAC proves very effective for the first solution since OrBAC provides context hierarchies. Thus, it is enough to find either the more specialized context than Ctx (to deploy permissions) or less specialized ones (to deploy prohibitions).

The second solution is solved with an optimization approach. The system presents no optimal functionality to manage the Ctx context but only closely-equivalent ones. We declare these functionalities with the Close Fs() predicate. A notion of cost of using a given functionality to deploy certain rules in the Ctx context is introduced and the deployment problem is transformed into an optimization one. The result is a bipartite graph where the optimization solution is obtained with linear programming. Figure 3 depicts a proper example. Notice that, globally, the cost of deploying the SR rules over the Ctx contexts is minimized. The optimal functionalities necessary to handle the Ctx context will be substituted by closely-equivalent ones.

Related Works

A significant amount of work has been reported in the area of security management at network level in order to analyze and fix existing configurations. The most significant approach to firewall policy analysis is the one by Al-Shaer et al. (e.g., approaches presented in [START_REF] Al-Shaer | Discovery of Policy Anomalies in Distributed Firewalls[END_REF][START_REF] Al-Shaer | Taxonomy of Conflicts in Network Security Policies[END_REF]) which provides efficient solutions to detect policy anomalies in both single-and multi-firewall configuration setups. Their detection algorithms are based on the analysis of relationships between rules two by two. Therefore, errors due to the union of rules are not explicitly considered (as our approach does). Some workarounds can be provided to solve this situation. For instance, it is possible to break down the initial set of rules into an equivalent set of rules free of overlaps between rules. However, no specific algorithms were provided in [START_REF] Al-Shaer | Discovery of Policy Anomalies in Distributed Firewalls[END_REF][START_REF] Al-Shaer | Taxonomy of Conflicts in Network Security Policies[END_REF] to manage this solution. Another related work is the proposal presented in [START_REF] Yuan | FIREMAN: a toolkit for FIREwall Modeling and ANalysis[END_REF], which uses a model checking formalism for detecting inconsistencies and redundancies in single firewall configurations. This proposal handles the limitation pointed out in the works by Al-Shaer et al., by addressing directly the way how traffic is handled by the components. The complete set is divided in three main sets: traffic that is permitted, traffic that is prohibited, and traffic for which no rules apply. The proposal in [START_REF] Yuan | FIREMAN: a toolkit for FIREwall Modeling and ANalysis[END_REF], as well as other similar approaches, such as [START_REF] Liu | Complete Redundancy Detection in Firewalls[END_REF], only address intra-component analysis. Moreover, none of them have presented specific mechanisms for verifying policies other than filtering ones.

Regarding the analysis of VPN routers' configurations, the most significant approach compared to ours is proposed in [START_REF] Fu | IPSec/VPN Security Policy: Correctness, Conflict Detection and Resolution[END_REF]. The authors propose a technique that simulates VPN tunneling processing and reports any violation of the security policy requirements. In their approach, if an access rule concerning a protected traffic between two points is implemented by configuring more than one VPN overlapping tunnel, the risk is that in some network zones the IP packets circulate without any protection. The authors present a discovery process to detect such situations and propose a high-level language to deal with VPN policies. Although this approach can discover some violations in a certain simulation scenario, there is no guarantee that it discovers every possible violation that may exist. In addition, the proposed technique only discovers VPN conflicts resulting from incorrect tunnel overlap, but does not address the other types of conflicts. Another attempt to deploy VPN configurations free of anomalies is [START_REF] Baek | Policy based Hybrid Management Architecture for IP-based VPN[END_REF] where the authors propose a centralentity approach with high level language conflict resolution techniques also -the algorithms remained however unevaluated. However, a significant aspect is ignored in both previous approaches: the security policy cannot be seen as two independent sets of requirements (i.e., VPN tunnels and firewalls modeled separately). The use of a single access control model in our approach solves this limitation and allows us to deal with a global set of security requirements and to address inter-mechanisms anomalies (e.g., firewall vs. VPN conflicts) at the same time.

Another significant approach compared to ours is the RBAC-based proposal presented in [START_REF] Bartal | Firmato: A Novel Firewall Management Toolkit[END_REF], called Firmato. This new solution aims at configuring filtering devices following an approach of separation between the security policy model and the technology specifications. It, therefore, ensures policy deployment independently of the network topology. The tool is based on an Entity -Association model (abstract level) which takes into account the network topology as a role. The instantiation of the model is based on a specific language that allows a downward transformation of the global policy into a set of firewall configurations. However, the use of the role concept used in Firmato, which defines the network capabilities, becomes ambiguous in its semantics. The authors use the notion of group to handle this situation. A group can identify, in fact, a set of hosts but also a role or a set of roles. Its use does not ensure, indeed, a clear separation between the network level and the security policy, making difficult the use of this tool to model complex networks. The authors use, moreover, privilege inheritance through group hierarchies in order to derive permissions. If permission inheritance is related to the so-called open group, prohibitions are inherited through a close group. The notion of group clearly introduces ambiguities and seems to be useless at this abstraction level.

Support tools can also be used to assist administrators in their task of configuring security devices. Proper examples are the LogLogic Security Change Manager (cf. http://loglogic.com/products/), formerly known as Solsoft Policy Server and Network Security Policy Server, the Firewall Builder (cf. http://fwbuilder.org/), CheckPoint SmartCenter (cf. http://checkpoint.com/products/smartcenter/), Juniper Network and Security Manager (cf. http://www.netutils.com/), and the Cisco Security Manager (cf. http://cisco.com/go/csmanager). In a relatively high level language, these support tools allow the configuration of different vendors' devices and support the security administrators in the deployment of large configurations on heterogeneous networks. We observe the following problems when using such tools. First, they do not offer a semantic model rich enough to express a global security policy. Although it is possible to define variables, and thus to define access rules involving such variables, the administration tasks are not much simplified. The security officer always needs a global view of the topology in order to correctly assign each rule to network devices; then, there is no automatic discovery of security devices that optimally implement an access rule involving an IP source and a destination. Furthermore, the lack of a real downward approach like ours is partially replaced by other tools (e.g., Cisco conflict discovery tools) that need the security officer's assistance and that unfortunately only guarantee conflict resolution for local configurations.

Conclusions

We addressed the managing of network security policies free of anomalies or inconsistencies. Two main approaches were presented: (1) the use of bottom-up process to detect and fix configuration errors over components already deployed; and (2) the use of a top-down process to perform an automatic deployment of component configurations free of inconsistencies. The implementation of these two approaches in a software prototype demonstrates the practicability of our work. We finally compared the functionality of MIRAGE with some other solutions proposed in both the science and the industry community, and showed some advantages of our approaches. As future work, it is expected to add new a feature in MIRAGE to manage the update of components' configurations. This new feature will guide the operators to determine the impact that the removal or the addition of new configuration rules in the system might suppose. It is also expected to give support to determine dynamic tuning of configurations. In this case, the new feature is expected to compare and test the equivalence between different configurations. For example, the security operator can verify whether the new settings of a new configuration setup will perform well enough, and in compliance with the global security policy. Finally, it is also intended to complement the upward and the downward approaches offered by MIRAGE with an automatic discovery of roles associated with different security components already deployed in the system. It is planned the use of role mining techniques, for example, to analyze existing access control roles associated to the components (to derive, after the analysis, the appropriate rules of the global configuration).

R 1 :Fig. 1

 11 Fig. 1 Single filtering policy scenario.

∑

  i ∈ (1...m) x j = 0 or 1, j ∈ (1...n) where x j = 1 if j is in FS, x j = 0 otherwise; and d ij = 1 if SR i could be deployed using the functionality F j , d ij = 0 otherwise. = 1, i ∈ (1...m) x j = 0 or 1, j ∈ (1...n) where x j = 1 if j is in FS, x j = 0 otherwise; and d ij = 1 if SR i could be deployed using the functionality F j , d ij = 0 otherwise. (b) The LP Solutions.

Fig. 3

 3 Fig. 3 LP Problem and Solutions.

•

  Inter-component Misconnection -A misconnection anomaly occurs between two components when the first one, located closest to the source, is a firewall that permits (explicitly, by means of negative rules; or implicitly, through its default policy) all the traffic, or just a part of it, that is then denied by the component where the anomaly is detected. The following tableshowssome examples. {R 1 } and C 2 {R 2 } are misconnected full explicit misconnection C 5 {R 2 } and C 2 {R 2 } are misconnected partial explicit misconnection C 1 {R 5 } and policy of C 2 are misconnected full implicit misconnection C 1 {R 6 }, C 2 {R 1 }, and policy of C 2 partial implicit misconnection

	Rules	Anomaly
	C 5

Acknowledgments -This work has been supported by a grant from the Brittany region of France and by the following projects: POLUX ANR-06-SETIN-012, SEC6 Project, TSI2007-65406-C03-03 E-AEGIS, and CONSOLIDER CSD2007-00004 "ARES".