Radio frequency label identification

The present invention relates to radio frequency identification systems based on radio frequency labels or RFID chips ("Radio Frequency Identification"), and in particular to the protection of data exchanged in such identification systems.

Figure 1 shows a radio frequency identification system comprising a radio frequency label reader 101 that can communicate by means of radio waves with a plurality of radio frequency labels 102. Radio frequency label generally consists of a paper or plastic substrate, an integrated circuit, and an antenna. This radio frequency label is activated when receiving the activation signal sent by the radio frequency label reader. Such RFID systems can operate using either low frequency signals or high frequency signals.

In such a radio frequency identification system, each radio frequency label is assigned a unique identifier. The reader is then able to identify the label based on information sent from said label and depending on the list of label identifiers 102 operating on the radio frequencies of the system.

For this RFID system to be reliable, a level of secrecy should be maintained between the reader and the corresponding labels 102 operating on radio frequencies, each with the identifier of the radio system. In such a system, the identifier of a given label is transmitted between the label and the reader. The reliability of such an identification system is therefore based in particular on the means of securing the corresponding label identifiers operating on radio frequencies during some such exchanges of information between the label reader and read labels operating on radio frequencies.

Thus, in order to avoid a situation in which another entity could appropriate the identifier assigned to one of the system labels and thus cheat the RFID system, these data exchanges may be encrypted.

When activated by a radio activation signal, a radio frequency label can connect to a radio frequency label reader that is available to those skilled in the art according to various protocols. For example, the HB protocol ('Hopper, Blum') allows such communication between the reader and the label operating on radio frequencies. According to this protocol, the secret identifier x is known only to the reader and the label operating on radio frequencies.

changes the connection between the reader and on the waves

Figure 2 with radioactive label in accordance with the HB protocol.

Note that in the examples below, the numbers aj are used. and x are k-bit binary numbers, with k being an integer.

According to the HB protocol, the identification of the label by the reader is done by repeating N times the encryption step of the identifier of the given label. During this encryption stage, stage i, for i being an integer between 1 and N, the reader transmits message 103 intended for the label operating on radio frequencies, giving a random number ai belonging to the set marked {0, l}^k, k-bit binary numbers. Then, the radio frequency label encrypts its secret identifier using the aj random number sent by the reader.

To implement such encryption, the label generates a random number v ± and obtains the value of an encrypted identifier according to the following formula:

Zi = ai.x®vi (1) in which Vi is generated in such a way that it belongs to the set {0,1}, with the specified probability η such that vi is equal to 1.

It should be noted that the sign '®' means the operation 'negative alternative' and the sign '.' means the operation of 'alternative' excluding various results of operations of 'logical product' carried out bit by bit on both numbers ai and x.

This step is therefore repeated N times. Accordingly, the label reader operating on radio waves receives N values ​​of z, wherein, for each of them, the values ​​of the random number ai and the second random number Vi change.

The radio frequency label reader knows the specific probability value η that characterizes the random number generation νχ. Therefore, based on the N values ​​of the z, encrypted identifier, received in messages 104 and based on the list of assigned frequencies of secret identifiers, respectively, labels operating on the radio system and the first N and such protocol HB identifier x second random numbers, the reader of labels operating on radio frequencies can determine the secret identifier x of a given label, checking if equation (1) is false for more than one number corresponding to η.Ν.

However, active attack makes it possible to determine the secret assigned to a given label. So, when it comes to the input between the label reader and the label operating on radio waves, in such a way that the label operating on radio frequencies will be provided the same number in place of random numbers a ^ provided by the reader, information about x can be determined.

The communication protocol for the radio identification system, marked HB +, offers protection against such an active attack by introducing an additional random value when encrypting the secret identifier of the label operating on radio frequencies. Such a protocol and possible attacks are described in the document "Active attack against HB +: a probably secure lightweight authentication protocol" Electronics Letters, IEE Sterenage, vol. 41, No. 21, October 13, 2005.

Figure 3 shows such an HB + protocol, based on a repetition of the encryption step, with only step i being shown.

According to this HB + protocol, the secret identifier of a given label, known to the reader and said label, is denoted as (x, y) where x and y are binary binary numbers. At each stage and previously described, the label sends to the label reader operating on radio frequencies a message 201 containing the first random number bi. When receiving this first random number bi, the label reader sends via radio frequency a message 202 containing the second random number aj. Then, based on the first and second random numbers, the radio frequency label sends a message 203 to the label reader, in which the value of its secret encrypted identifier is given, which satisfies the following equation:

Zi = ai.x®bi.y®Vi (2) in which Vi belongs to the set {0,1}, with the specified probability η that Vi is equal to 1, the said probability η being known to the reader and the label operating on radio frequencies .

During N repetitions of this encryption step, the label provides the label reader with N values ​​from and a secret encrypted identifier.

Certainly, communication in accordance with this HB + protocol turns out to be better protected against some attacks than communication in accordance with the HB protocol. In any case, an active attack of entering between the reader and the label operating on radio waves and sending, while broadcasting message 201, a message 202 changed in such a way as to replace the second random number ai generated by the reader with the number a / satisfying the following equation:

ai '= ai® £ (3) where δ is a k-bit number that has a constant value throughout the period of N repetitions of the encryption stage, stage

and.

In this case, message 203 passes the number z and that meets the following equation:

Zi = ai '.x®bi .y®Vi = (ai® £). x®bi.y®vi (4)

In this context, if the reader is able to identify the label, he deduces that with a high probability δ. x is 0. In the opposite case, it is deduced from the fact that δ. x is equal to 1. So, depending on the inability or the ability to identify the radio frequency label by the reader, it can be deduced from the information about the secret identifier x. Then, such a deduction method can be transposed into bi and Y numbers ·

There is therefore an active attack that allows detecting the secret identifier (x, y) of a radio frequency label in communication between the reader and the label in accordance with the HB + protocol. Such an attack is described in the document Άη active attack against HB + 'by Henri Gilbert, Matthew Robshaw and Herve Sibert.

The object of the present invention is to improve the security of communication in the RFID system against attacks aimed at detecting secret identifiers of labels operating on radio frequencies.

In a first aspect of the present invention, a method for identifying a radio frequency label is proposed in a radio frequency label identification system comprising a radio frequency label reader and a plurality of radio frequency labels, with a unique and secret identifier (x, y, x ' , y ') is assigned to each of these radio-operating labels.

The method may include the following steps:

/ a / sending the first random number from the radio frequency label to the radio frequency label reader;

/ b / sending a second random number from a radio frequency label reader to a radio frequency label;

/ c / at the level of said radio frequency label, encrypting the label identifier by performing the following steps consisting of:

- generating the third and fourth random numbers according to the principle of probability;

- transforming said first and second random numbers according to a particular function and obtaining the transformed first and second random numbers, respectively;

- obtaining the value of the encrypted identifier by combining the label identifier with the first and second random numbers, with the first and second transformed numbers and with the third and fourth random numbers;

/ d / sending from the label operating on radio frequencies to the label reader operating on radio frequencies the value of the encrypted identifier originating from stage / c /;

/ e / repeating N times steps / a / to / d /, where N is an integer;

/ f / identify on the list of label identifiers, at the level of the label reader, a label operating on radio frequencies by specifying the assigned identifier in a function depending on the N value of the encrypted identifier obtained, from a specific function, from the first and second random numbers and the principle of probability.

When the first and second random numbers are k-bit binary numbers, where k is an integer, the specified function f is the permutation of a set of k-bit binary numbers and this function fulfills, in the case of any pair of binary binary numbers δ, λ, where δ is non-zero, the following equation only for the number of d values ​​that is less than the threshold value:

f (d®6) = f (d) ® λ

The specific function f preferably has a complexity level below the complexity threshold.

When the label identifier contains the first, second, third and fourth k-bit binary number, then, at the / c / stage, you can get the first part from the value of the encrypted identifier according to the following equation:

z = a. x®b. y®v where bia are the first and second random numbers in k-bit binary respectively;

where x and y are the first and second binary numbers of the identifier, respectively; and where v is a third random number;

and you can get the second part from the value of the encrypted identifier according to the following formula:

z '= f (a) .x' © f (b) .y '© v' where x 'iy' are the third and fourth binary numbers of the identifier, respectively;

where f is a specific function and where f (b) and f (a) are the first and second transformed numbers, respectively; and where ν 'is the fourth random number.

It may be considered at the stage / c / to send the first part from the value of the encrypted identifier in the first message (403) and the second part from the 'value of the encrypted identifier in the second message (404).

The probability rule for generating random numbers can be determined in such a way that a specific number is generated with a probability having a certain value.

In a second aspect of the present invention, a radio frequency label is proposed in a radio frequency label identification system comprising a radio frequency label reader, said radio frequency label being assigned a unique and secret identifier. The label may contain:

- a storage unit adapted to store the identifier of said label;

- a randomly generated unit adapted on one side to generate the first random number, according to random numbers; a unit on the other hand for generating with a transform probability principle adapted to transform the number according to a particular function and providing the transformed number; an encryption unit adapted to encrypt the radio frequency label identifier by combining the identifier with the first random number and the second random number obtained from the label reader, with the third and fourth random numbers provided by the generating unit according to the principle of probability, and with the first and second transformed numbers provided by a transformation unit based on the first and second random numbers;

a reader interface management unit operating at frequencies adapted to send the first random number to the label reader, receive the second random number from the label reader, and send the encrypted label identifier value provided by the encryption unit.

The specific function f on which the transformation unit (503) is based, when the first and second random numbers are k-bit binary numbers, where k is an integer, can be a permutation of a set of kbit binary numbers and this function fulfills the radio labels of any case pairs of k-binary binary numbers δ, λ, where δ is non-zero, the following equation only for the number of d values ​​that is lower than the threshold value:

f (d®8) = f (d) ® λ

When the label identifier includes the first, second, third and fourth k-bit binary numbers, the encryption unit may provide on the one hand the first part of the value of the encrypted identifier according to the following equation:

z = ax®by®v where bia are the first and second random numbers in k-bit binary respectively;

where x and y are the first and second binary numbers of the identifier, respectively; and where v is a third random number;

and can provide the other part with 'the value of the encrypted identifier according to the following equation:

z '= f (a) .x'®f (b) .y'®v' where x 'and y' are the third and fourth binary numbers of the identifier, respectively;

where f is a specific function and where f (b) and f (a) are the first and second transformed numbers, respectively; and where ν 'is the fourth random number.

The interface management entity may send to the label reader the first part of the encrypted identifier value in the first message and the second part of the encrypted identifier value in the second message.

In a third aspect of the present invention, a device for identifying radio frequency labels in a radio frequency label identification system comprising a plurality of radio frequency labels is proposed, a unique and secret identifier being associated with each of said radio frequency labels. The device may include:

a random generation unit adapted to generate a random number;

an interface control unit with said radio frequency labels adapted to receive a first random number from a radio frequency label, to send a second random number generated by said random frequency generation unit to said radio frequency label and to receive the value of an encrypted identifier, resulting from the combination of the identifier of said label with the first and second random numbers, with the first and second transformed numbers derived from the transformation of said first and second random numbers according to a particular function, and with the third and fourth random numbers generated according to the principle of probability by said label; a storage unit adapted to store a particular function, probability rule, and list of identifiers assigned to system labels; an identification unit adapted to identify said radio frequency label by specifying the assigned identifier as a function of the N value of the encrypted identifier obtained from the label by the interface control unit, from the specified function, from the probability rule, from the first N and second random numbers used to provide the encrypted storage identifiers.

mentioned N identifier and stored in the value from the list of jnnostce

The specified function f, when the first and second random numbers are k-bit binary numbers, where k is an integer, can be a permutation of a set of k-bit binary numbers and this function fulfills, in the case of any pair of binary binary numbers δ, λ , where δ is non-zero, the following equation only for a number of d values ​​that is below the threshold value:

f (d®6) = f (d) ® λ

The specified function f has a complexity level below the complexity threshold.

When the label identifier includes the first, second, third and fourth k-bit binary numbers, the value of the encrypted identifier may contain the first part with the following equation:

z = ax®by®v where bia are the first and second random numbers in k-bit binary respectively;

where x and y are the first and second binary numbers of the identifier, respectively; and where v is a third random number; and may contain the second part of 'satisfying the following equation:

z '= f (a) .x'®f (b) .y'®v' where x 'and y' are the third and fourth binary numbers of the radio frequency identifier respectively;

where f is a specific function and where f (b) and f (a) are the first and second transformed numbers, respectively; and where ν'is the fourth random number.

The interface management entity may receive a first portion of the encrypted identifier value in the first message and a second portion of the encrypted identifier value in the second message.

In a fourth aspect of the present invention, a radio frequency label identification system is proposed comprising a device for identifying labels according to the third aspect of the present invention and a plurality of radio frequency labels according to the second aspect of the present invention.

Other aspects, objects, and advantages of the invention will be shown in the description of one embodiment thereof.

The invention will also be better understood by means of drawings in which:

- figure 1 shows the architecture of a radio frequency label identification system according to an existing method;

- figure 2 shows the exchange of messages in the radio frequency identification system according to the existing method;

reader architecture on frequencies

- figure 3 shows another message exchange in the radio frequency identification system according to the existing method;

- figure 4 shows the exchange of messages in an radio frequency identification system according to one embodiment of the present invention;

- figure 5 shows the architecture of a radio frequency label according to one embodiment of the present invention; and

- figure 6 shows radio operating labels according to one embodiment of the present invention.

In one embodiment of the present invention, each label 102 of the radio frequency label identification system shown in Figure 1 is associated with one secret identifier containing four binary numbers x, y, x 'and y', where k is an integer. Figure 4 shows such an embodiment. Label 102 is initially activated by an activation signal being a high frequency signal, or being a low frequency signal that can be emitted by a label reader operating on radio frequencies 101.

According to such an embodiment, the identification of the label is carried out by repeating N times the encryption step described in the following paragraphs.

Thus, during the encryption step, step i, the label initially sends a message 401 to the reader to provide it with the first random number bi preferably generated by said label. In response to this message 401, the reader sends a message 402 to the label giving a second random number ai generated preferably by said reader 101. Next, the label attempts to encrypt its identifier in such a way as to secure its transmission to the reader 101.

Preferably, the label combines the first part, x and y, of its identifier with a first and second random number, a ±, and bi, and with a third random number Vi generated by the label according to a probability rule. This combination provides the first part of the encrypted value

<td>identifier that can</td><td>e.g</td><td>fulfill</td><td>following</td>

<td>equation:</td><td></td><td></td><td></td>

<td>Zi = ai. x®bi. y®vi</td><td></td><td></td><td> (5)</td>

<td>In addition, he combines</td><td>become the second one</td><td>Hello,</td><td>x 'and y',</td>

<td>Label ID</td><td colspan="2">on the one hand, from</td><td>first and</td>

a second transformed number derived from the transformation of the first and second random numbers according to the function f known to the label reader operating on radio waves 101 and the label operating on radio frequencies 102, and on the other hand with the fourth random number vi 'generated by the label according to the rule of probability.

Preferably, the second portion of the encrypted identifier value resulting from this combination satisfies the following equation:

zi '= f (ai) .x'®f (bi) .y'®Vi' (5)

Thus, in message 403, the radio frequency label sends the result of the combination of the first part value of the encrypted identifier, and in message 404, the radio frequency label sends the result of the combination of the second part of the value of the encrypted label identifier operating on the raid frequencies.

From what has been stated previously, it is easy to deduce other embodiments of the present invention. Thus, for example, the results of the combination of the first and second parts of the label identifier can be sent in one and the same message. The present invention includes all methods of transmitting these different values ​​of the encrypted identifier to the label reader.

The previously described step thus provides the value of the encrypted label identifier. This step is repeated N times. Therefore, the radio frequency label reader receives N values ​​of the encrypted identifier, each originating on the one hand from the first combination of identifier with the first and second random numbers and with the third random number, and on the other hand from the other combination of identifier with the first and the second transformed number obtained by applying the function f on the first and second random numbers, and with the fourth random number.

It should be noted that the third and fourth random numbers are preferably generated according to a generation rule that applies a specific probability rule known to both the label and the reader. Thus, for example, this probability rule may allow the generation of a specific binary number with a specified one

This value value is the probability equation with the value η. the likelihood of η is known to the reader and the label.

Therefore, the probability rule used is determined by the fact that the generated third and fourth random numbers correspond to the binary number 1 with the specified probability η. However, the invention is not limited to such a probability rule.

The label reader operating on radio waves thus receives N values ​​of the encrypted label identifier operating on radio frequencies 102. In one embodiment of the present invention, the value of the encrypted identifier consists of two parts that can be processed by the reader in different ways. The first part Zj, respectively the second part zZ, of the value of the encrypted identifier received by the reader results from the first combination, respectively from the second combination previously described.

Regardless of the method used to transfer both parts N of the value of the encrypted identifier, from the label to the label reader, the reader is able to determine the first and second of the 'part of the same encrypted identifier and reconstruct the encrypted identifier (z, z').

In one embodiment of the present invention, in order to identify the first part of the label identifier, the reader attempts to determine, for the N encrypted identifier received, whether the following value met in accordance with the rule value is a probability:

Zi = ai. x®bi. y (6)

The reader determines part of the label identifier (x, y) if equation (6) is met with a probability clearly equal to 1-η.

Then, the reader tries to determine the second part of the label identifier. It therefore considers the values ​​of the encrypted identifier, and determines whether the following equation, regarding the second part of the value z and 'of the encrypted identifier, is satisfied with a probability clearly equal to 1-η:

Zi '= f (ai) .x'®f (bi) .y' (7)

If this is the case, then the second part of the label is also determined and so the reader has identified the label operating on radio frequencies.

This method of encrypting the label identifier (x, y, x ', y^from) advantageously allows protection against active attacks when the transform function used to transform the first and second random numbers has some specific characteristics.

For this purpose, you can specify such a transform function f specifying that f is the permutation of the set {0, l}^k and that, for any pair of k-binary binary numbers (δ, λ) where δ is non-zero, the maximum number M of the value d of the set {0, l}^k for which the function f satisfies the following equation is relatively small:

f (d®6) = f (ά) Φλ (8)

Thus, it can be determined that the maximum number M is smaller than the threshold value, which makes it possible to state that equation (8) is rarely met in the set {0, l}^k, in the case of a constant pair of values ​​(δ, λ).

Thus, when the function f satisfies these probability properties, an active attack, such as the attack described in the previously cited document 'An active attack against HB +', turns out to be ineffective.

In a situation where the active attack consists in replacing the second random number ai with a / satisfying equation (3), in which δ is a constant number during the repetitions of the encryption stage, the reader receives the values ​​of the encrypted identifier having the second part satisfying the following equation:

zU = f (βί®δ) .x'®f (bi) .y '© Vi' (9)

In this situation, regardless of whether the reader identifies the label or not, the attack does not allow reaching the identifier value.

So, because the function f has the above-mentioned properties, that is, there are relatively few values ​​of ai, which in the case of any pair (δ, λ) meet the equation (8), such an attack does not allow deducing the value of the label identifier depending on the identification or the label is not identified by the reader.

It follows that, in one embodiment of the present invention, the exchange of messages between the reader and the label operating at radio frequencies to identify the label is resistant to active attacks against the secret identifier of the label read by radio frequency.

In addition, such a conversion function preferably has a relatively low level of complexity. Due to the fact that radio labels generally do not have very high computational capabilities, remember to limit the computing power required to encrypt radio frequency label identifiers.

Many transforming functions that meet the parameters listed in relation to equation (8) and have a relatively low level of complexity can be created and used in a radio frequency identification system in accordance with one embodiment of the present invention.

Such functions can easily be created based on various methods. The next sections describe an example of creating such a transform function.

For a given number k, the function f is the permutation of the set {0, l}^k. Two min numbers are determined so that the following equation is met:

k = mn (11)

Then, you can create the function f defined based on the integer n of the function g and g_n each of which is specified in the set of binary numbers (0, l}^m. These n functions g_x to g_n are low-complex permutations. In addition, each of these functions has a limited and small maximum number G, in the case of p elements of the set {0, l}^m, in which the following equation is met, for and from 1 to n:

gi (ρΦδ) = g ± ​​(p) ®λ (12) where δ is non-zero and δ, λ are elements of the set {0.l}^m

To use a specific function fo the properties of the functions g and g_n, mentioned in connection with equation (12) and in relation to the level of complexity, can advantageously be formed according to the following equation:

f (q) = (gi (go—, gm-l), 32 (gm / -, g2m-l) z - z 9n (gk-mz · · z qk-l)) (13) where g = (q₀, . . , q_k-i) in set {0, l}^k.

In this situation, the values ​​for the number of min and functions from g and g are determined_n, depending on the maximum number M and the threshold level of complexity to be maintained for the function specified f.

For example, in the case of the odd number m, it is possible to select the function gi in the case i between 1 and an, in such a way that they transform the element p into element p³ in finite set L o 2^melements, where L is in bijection with the set {0, l}^m. In this case, for each of the functions gi, the maximum number of G values ​​of p satisfying equation (12) is obtained, which is equal to 2.

Therefore, a maximum number M of 2 is obtained^k'^{m + 1} values ​​of the set {0, l}^k satisfying equation (8).

Figure 5 shows a radio frequency label according to one embodiment of the present invention. It has a storage unit 505 adapted to store the label identifier. It also has a random generation unit 501 adapted to generate the first random number bi transmitted to the reader in message 401, this generation being carried out according to a uniform rule. Such a unit is also adapted to generate a third and fourth random number according to a defined probability rule. It also has a transformation unit 503 adapted to be transformed numbers in accordance with a particular function f and to provide the transformed number. This transformation unit thus provides the first and second converted numbers, which are then combined with the label identifier to obtain the second part of the value of the encrypted identifier.

The label according to one embodiment of the present invention further has an encryption unit 504 adapted to encrypt the label identifier operating at radio frequencies by a combination of this identifier, with a first random number provided by the random generation unit 501 and a second random number obtained from the label reader, with the third and fourth random number, and with the first and second random numbers transformed by transformation unit 503.

Then, this label 102 has an interface management unit 506 for communicating with a radio frequency label reader adapted to send the first random number bi to the label reader, to receive the second random number a ^ from the label reader and to send the values ​​of z, zN encrypted identifier label.

Figure 6 shows a radio frequency label reader according to one embodiment of the present invention. Such a reader 101 has an interface control unit 601 for communicating with labels operating on the raid frequencies of the RFID system. Such a unit is adapted to receive the first random number Jbj from the label 102 operating on radio frequencies, to send the second random number to the label operating on radio frequencies and to receive the value of the encrypted identifier resulting from the combination of the label identifier with the first and second random numbers and with the first and second a random number transformed by a specific function, and with the third and fourth random numbers generated according to the probability rule.

Such a reader further has a storage unit 602 adapted to store a particular function f, a generation probability rule, and a list of identifiers assigned to the system labels. It also has an identification unit 603 adapted to identify the label operating on radio frequencies by specifying the assigned identifier, depending on the N value of the encrypted identifier obtained from the label to be identified, from a specific function f, from the rule of probability of generation, from the first and second N random numbers and from a list of identifiers stored in storage unit 602. It also has a random number generation unit.