CN102693438A - Privacy protection radio frequency identification password protocol method and system - Google Patents

Abstract

The invention discloses a privacy protection radio frequency identification cryptographic protocol method, comprising: a reader generates a random number r ₁ ; a tag generates a random number r ₂ and calculates h(Ψ _{i , x} , c) and a, and sends them together with c To the reader; the reader looks up h(Ψ _{i , x} ,c) according to the value of c, and obtains the tag pseudonym Ψ _{i , x} and key k _i according to h(Ψ _{i , x} , c); calculates a' and judges Is a' equal to a, if yes, calculate _ki ', update _ki to _ki ', Ψ _{i, x} is Ψ _{i , x-1} , calculate b and d, send b and d to the label; the label calculates k _i ', b', judge whether b' is equal to b, if yes, calculate The pseudonym of the updated label is Ψ _{i , x-1} , the key is k _i ', and the counter value c is incremented by 1. The invention can solve the problem that the privacy protection radio frequency identification encryption protocol in the prior art cannot effectively protect the privacy.

Description

A privacy protection radio frequency identification cryptographic protocol method and system

technical field

The invention relates to the field of radio frequency identification, in particular to a privacy protection radio frequency identification cryptographic protocol method and system.

Background technique

In the prior art, radio frequency identification (RFID, Radio Frequency Identification) is one of many automatic identification technologies. Its basic principle is to use the transmission characteristics of radio frequency signals and space coupling (inductive or electromagnetic coupling) to realize automatic identification of identified objects. identify. Based on the many advantages of RFID, it has been widely used and attracted more and more attention. For example, the introduction of RFID technology in the supply chain can improve the visibility of the supply chain, improve the operational efficiency of the supply chain, provide efficient real-time information for the entire supply chain, and effectively prevent theft, loss and counterfeiting.

According to the general supply chain process, there are multiple node enterprises in a supply chain. Each node enterprise based on RFID supply chain controls a group of RFID readers and back-end database. When the logistics arrives, the supply chain node enterprise first uses the RFID reader to collect the product marks contained in the label, and then obtains detailed product information by searching the back-end database, and updates the label mark if necessary. The system model is shown in Figure 1. Among them, the RFID system is mainly divided into two parts, one is the part between the reader (Reader) and the back-end database (Backend Database), and the other is the part between the tag (Tag) and the read-write between the parts. The reader and the back-end database have strong storage and computing capabilities. It is generally believed that the reader and the back-end database can be regarded as a whole, and the communication channel between them can be assumed to be safe.

In the supply chain system, the goods with tags are processed in batches, and the processing volume of the reader is very large, so the performance requirements are the highest. If the reader is slow to process tags, the value of the supply chain will not be well reflected. Therefore, the cost of identifying a tag in the supply chain cannot increase significantly due to the increase in the number of tags, that is, it should have scalability requirements. At the same time, in the supply chain, privacy is more concerned because people cannot perceive the illegal reading of RF signals. We believe that there are two main types of privacy issues in RFID systems: one is the leakage of electronic tag information; the other is that attackers can maliciously track electronic tags through the information sent by electronic tags.

At present, the methods used to realize RFID privacy protection mainly fall into three categories: physical methods, cryptographic mechanisms, and a combination of the two. Using cryptographic mechanisms to encrypt and authenticate smart tags is a method that researchers are more concerned about. In recent years, in order to protect the security and privacy of RFID systems, many cryptographic protocols have been proposed. Although the contents of the protocols are different, they can be divided into three categories according to the time complexity of the authentication tag: linear time complexity, logarithmic A protocol with level time complexity and constant level time complexity. The advantages and disadvantages of the three types of protocols are compared in Table 1. It can be seen from Table 1 that only protocols with constant-level time complexity can meet the needs of the supply chain.

Table I

In the process of realizing the present invention, the inventors found that the cryptographic protocols in the prior art are mainly composed of protocols with constant-level time complexity, mainly including the following three representative methods, each with advantages and disadvantages, as follows:

The first scheme is a scheme called LAST, which is a challenge-response mechanism based on a weak privacy model, which claims to protect user privacy and has high query efficiency. The protocol flow is shown in Figure 2. The implementation process of the agreement includes:

1) The reader generates a random number r1, and sends it to the tag together with the authentication request Request;

2) The tag generates a random number r2, calculates V=H(r1, r2, ki), and then sends information U=(r2, Indexi, V) to the reader.

3) The reader forwards (r1, U) to the backend database. The back-end database searches Indexi, if it does not exist, then output false; otherwise, get ki according to (Ti, Indexi, ki) and calculate V'=H(r1, r2, ki), if V'≠V, output false; otherwise The identity of the reader authentication tag is Ti, and calculate Indexi'=H(r1, r2, Indexi, ki), ki'=H(r1, r2, ki), update (Ti, Indexi, ki) in the database as (Ti, Index i', ki'). Then send σ=H(r1, r2, ki') to the reader.

4) The reader sends σ to the tag. The label first calculates ki'=H(r1,r2,ki) and σ'=H(r1,r2,ki'), if σ=σ', the label updates (Indexi,ki) to (Indexi',ki') ; otherwise remain unchanged.

In this technology, although the protocol verifies the identity of the reader by comparing the information returned by the reader, the updated key information of the reader is the information sent to the reader by the tag in the previous step, so the attack The attacker can forge the return information of the legal reader through the information sent by the tag, so it cannot really authenticate the reader, and the next key of the tag is also known by the attacker, so it cannot satisfy the untraceability and anti-resistance. Synchronous attack.

The second scheme is the EA scheme, and the protocol flowchart of the EA scheme is shown in FIG. 3 . The implementation of the protocol is as follows:

1) The reader generates a random number r1 and sends it to the tag as an authentication request;

M2＝h(yi||r1||r2)，然后发送{r2，M1，M2}给读写器。2) The label generates another random number r2, and calculates

M2=h(yi||r1||r2), and then send {r2, M1, M2} to the reader.

3) The reader forwards {r1, r2, M1, M2} to the backend database.

后端数据库计算

发送M3给读写器并且设置xold←xi，xi←xi*，yold←yi，yi←yi*。4) Back-end database calculation And search for x and xold stored in the database. If it matches, the database uses the corresponding yi in the table and checks if M2 is equal to h(yi||r1||r2). If they are equal, the database authenticates the tag Ti, otherwise an error message is sent to the reader to terminate the session. The reader calculates a new key

Back-end database computing

Send M3 to the reader and set xold←xi, xi←xi*, yold←yi, yi←yi*.

5) The reader forwards M3 to the tag.

如果相等，则标签认证了读写器且设置xi*＝M3，新密钥

并且xi←xi*，yi←yi*。否则xi，yi保持不变。6) The tag checks if M3 is equal to

If equal, the tag authenticated the reader and sets xi*=M3, the new key

And xi←xi*, yi←yi*. Otherwise xi, yi remain unchanged.

In this scheme, in order to shorten the time for identifying tags and change the time complexity of identifying tags from linear to constant level, all tags share a key. Therefore, as long as one tag is captured, the key information of other tags will also be captured by the attacker. Know, so this protocol also cannot satisfy untraceability.

The third scheme is the ACJR scheme, in which each tag has an internal counter c, and a secret pseudonym Ψ and a key k are stored in advance. After a successful session, the pseudonym and key are updated. However, the counter value is incremented by 1 after each authentication failure. The specific flow chart is shown in Figure 4. The implementation of the protocol is as follows:

1) The reader generates a random number r and sends it to the tag as an authentication request;

2) After receiving r, the tag calculates h(Ψ, c) and a=h(0, Ψ, c, k, r), and then adds 1 to the counter value.

和h(2Ψ’，k，a)。3) According to h(Ψ, c), the reader accesses the back-end database to identify the tag, and obtains the tag information, including pseudonym Ψ, key k, and new pseudonym Ψ', and authenticates the tag according to a. Once the tag is authenticated, the reader replies

and h(2Ψ', k, a).

4) pass The label extracts its new pseudonym Ψ'. By h(2, Ψ', k, a), the tag authenticates the reader and verifies the received Ψ'. If the reader is authenticated, the tag resets its counter to 0 and updates its key k'=h(k) and pseudonym Ψ'. Otherwise the agreement is terminated.

In this solution, the back-end database still needs to identify the identity of the tag according to the hash value returned by the tag, but it reduces the time to identify the tag to a constant level by using a three-layer hash table data structure. However, in this scheme, the pseudonym of the label and all possible values of the counter are hashed, and the hash value of the new pseudonym and all possible values of the counter must be recalculated after each update of the pseudonym, so the calculation amount of the back-end database is quite large. In addition, in this scheme, as long as the tag receives a request, it increases the value of c in the counter. In order to resist desynchronization attacks, when c reaches the maximum value, the counter is reset to 0, which causes problems. Attackers can use the same value to track tags.

Therefore, there are loopholes that can be exploited by attackers in the schemes in the prior art that implement RFID privacy protection by encrypting and authenticating smart tags using a cryptographic mechanism, and cannot effectively implement RFID privacy protection.

Contents of the invention

In order to solve the problem that the privacy protection radio frequency identification cryptographic protocol in the prior art has loopholes that may be exploited by attackers and cannot effectively protect privacy, the embodiment of the present invention provides a privacy protection radio frequency identification cryptographic protocol method and system. Described technical scheme is as follows:

A privacy protection radio frequency identification cryptographic protocol method, the method comprising:

The reader sends an authentication request to the tag, generates a random number r ₁ and sends it to the tag;

The tag generates a random number r ₂ and calculates the value of h(Ψ _{i, x} , c) and a=h(r ₁ , r ₂ , k _i ), and sends it to the reader along with c; wherein, the Ψ _{i, x} is the pseudonym of the tag, c is the value of the counter, and k _i is the key corresponding to the tag;

The reader looks up h(Ψ _{i, x} , c) in the back-end database according to the value of c, if h(Ψ _{i, x} , c) does not exist in the back-end database, the protocol is terminated, and the process ends; otherwise, according to the search Get h(Ψ _{i, x} , c) to get the corresponding tag pseudonym Ψ _{i, x} and key k _i ;

将b和d发送给标签；其中，所述Ψ_i，x＝h(Ψ_i，x-1)；Calculate a'=h(r ₁ , r ₂ , k _i ), and judge whether a' is equal to a, if not, terminate the agreement and the process ends; otherwise, calculate k' _i =h(r ₁ , r ₂ , Ψ _{i, x} , k _i ), update _ki as k' _i , Ψ _{i , x} as Ψ _{i, x-1} , calculate b=h(r ₁ , r ₂ , k' _i ) and

Send b and d to the tag; wherein, the Ψ _{i, x} = h(Ψ _{i, x-1} );

更新标签假名Ψ_i，x为Ψ_i，x-1、密钥k_i为k’_i，同时计数器值c增1。Label calculation k' _i = h(r ₁ , r ₂ , Ψ _{i, x} , _ki ), b' = h(r ₁ , r ₂ , k' _i ), judge whether b' is equal to b, if not, then Terminate the agreement, the process ends; otherwise, calculate

Update the label pseudonym Ψ _{i , x} to Ψ _{i , x-1} , key k _i to k' _i , and increase the counter value c by 1.

The method also includes:

Set a total of n tags in the privacy protection system, and the number of each tag i, where 1≤i≤n;

The backend database selects a random number Ψ _i,0 for each label, and precomputes Ψ i _,1 = h(Ψ _i,0 ), Ψ _i,2 =h(Ψ _i,1 ),...,Ψ _{i , m-1} = h(Ψ _{i, m-2} );

The backend database saves Ψ _i,x for each tag, and these values will be assigned to tags in reverse order as their pseudonyms.

The method also includes:

Each label has an internal counter, and the value of the counter is c, where 0≤c≤m-1;

The back-end database pre-calculates the hash value h(Ψ _{i, x} , c) of the tag pseudonym and the value c of the counter;

When authenticating a tag, the pseudonym of the tag starts from the last value of the hash chain, and the value of the counter starts from 0, where x+c=m-1, that is, the hash values to be calculated are: h(Ψ _{i, 0} , m-1), h(Ψ _{i, 1} , m-2), ..., h(Ψ _{i, x} , m-1-x), ..., h(Ψ _{i, m-1} , 0 ).

The method also includes:

Use the value c of the counter as an index, and sort h(Ψ _{i, x} , c) with the same c value and different labels according to size, thereby generating a linked list and saving it in the back-end database; when querying the label corresponding to h( Ψ _{i, x} , c), use binary search for h(Ψ _{i, x} , c) with the same c value and different labels.

The method also includes:

All pseudonyms of each label correspond to the same key and other information. When the pseudonym is updated, the key of the label pointed to by the updated pseudonym is updated, while the key of the label pointed to by the previous pseudonym remains unchanged.

The method also includes:

When the value c of the counter reaches the maximum m-1, the backend database selects another random number for the tag, generates another hash chain as the pseudonym Ψ _{i, x} for the next round of the tag, and resets c to 0;

The back-end database pre-calculates the hash value h(Ψ' _{i, x} , c) of the tag pseudonym and the counter value.

The method also includes:

Each tag stores its current pseudonym Ψ _{i, x} , counter value c and key k _i , where 1≤i≤n;

Initially, c=0, and the pseudonym of the label is Ψ _i,m-1 .

A privacy protection radio frequency identification cryptographic protocol system, the system includes a reader and a tag, wherein,

The reader is used to send an authentication request to the tag, generate a random number r ₁ and send it to the tag; look up h(Ψ _{i, x} , c) in the back-end database according to the c value; according to the found h(Ψ _{i, x} , c) Obtain the corresponding tag pseudonym Ψ _{i, x} and key k _i ; calculate a'=h(r ₁ , r ₂ , k _i ), and judge whether a' is equal to a; calculate k' _i = h(r ₁ , r ₂ , Ψ _{i, x} , k _i ), update _ki to k' _i , Ψ _{i, x} to Ψ _{i, x-1} , calculate b=h(r ₁ , r ₂ , k' _i ) and send b and d to the label;

更新标签假名Ψ_i，x为Ψ_i，x-1、密钥k_i为k’_i，同时计数器值c增1。The tag is used to generate a random number r ₂ and calculate the value of h(Ψ _{i, x} , c) and a=h(r ₁ , r ₂ , k _i ), and send it to the reader along with c; calculate k ' _i ＝h(r ₁ , r ₂ , Ψ _{i, x} , ki ₎ , b'=h(r ₁ , r ₂ , k' _i ), judge whether b' is equal to b; calculate

Update the label pseudonym Ψ _{i , x} to Ψ _{i , x-1} , key k _i to k' _i , and increase the counter value c by 1.

The reader/writer further includes an authentication unit, a first random number unit, a backend database, a first judgment unit and a first calculation unit, wherein,

The authentication unit is configured to send an authentication request to the tag;

The first random number unit is used to generate a random number r ₁ ;

The back-end database is used to store and query tag pseudonyms, keys, random numbers and counter information;

The first judging unit is used to judge whether h(Ψ _{i, x} , c) exists in the back-end database; judge whether a' is equal to a;

The first calculation unit is used to calculate a'=h(r ₁ , r ₂ , _ki ), k' _i =h(r ₁ , r ₂ , Ψ _{i, x} , _ki ), b=h( r ₁ , r ₂ , k' _i ) and $d={\mathrm{\Ψ}}_{i,x}\⊕{\mathrm{\Ψ}}_{i,x-1}.$

The tag further includes a second random number unit, a second calculation unit, a counter unit, a pseudonym key unit and a second judging unit, wherein,

The second random number unit is used to generate a random number r ₂ ;

The second calculation unit is used to calculate h(Ψ _{i, x} , c), a=h(r ₁ , r ₂ , k _i ), k' _i =h(r ₁ , r ₂ , Ψ _{i, x} , k _i ) and b'=h(r ₁ , r ₂ , k' _i );

The counter unit is used to generate and update the value c of the counter;

The pseudonym key unit is used to store and update the pseudonym and key of the tag;

The second judging unit is used to judge whether b' is equal to b.

The beneficial effects brought by the technical solution provided by the embodiments of the present invention are:

Different random numbers are generated by the reader and the tag respectively, and the tag is encrypted and transmitted according to its own pseudonym, the value of the counter and two random numbers through a hash function, and the reader searches the back-end database for information corresponding to the corresponding tag pseudonym And check whether the relevant information is accurate, the reader updates the tag key and pseudonym through calculation, and encrypts and sends it to the tag through the hash function. After the tag is verified, it updates its own pseudonym and key, and updates the value of the counter. In the solution provided by the embodiment of the present invention, the key of the label is encrypted and transmitted by the hash function every time, and the hash function is confused by different random numbers r ₁ and r ₂ each time, and the key information of each label There is no correlation, and it is difficult for an attacker to obtain the key information of the tag, thus ensuring information security. At the same time, the tag's pseudonym and key information are transmitted with different values each time, so even if the attacker sends requests to the two tags continuously, he cannot distinguish the two tags. Each label only needs to store 3 secret information, and the pseudonym of the label is actually only hashed with a value of the counter, which greatly improves the efficiency of the operation. Therefore, the solution provided by the embodiment of the present invention greatly improves the security and quickness of the cryptographic protocol, and can effectively realize RFID privacy protection.

Description of drawings

In order to more clearly illustrate the technical solutions in the embodiments of the present invention, the drawings that need to be used in the description of the embodiments will be briefly introduced below. Obviously, the drawings in the following description are only some embodiments of the present invention. For those skilled in the art, other drawings can also be obtained based on these drawings without creative effort.

FIG. 1 is a schematic diagram of a privacy protection system model in the prior art;

Fig. 2 is a flow chart of the LAST scheme protocol in the prior art;

Fig. 3 is the flow chart of EA scheme protocol in the prior art;

Fig. 4 is the ACJR scheme protocol flowchart in the prior art;

Fig. 5 is a flowchart of the principles of the privacy protection radio frequency identification cryptographic protocol method provided by Embodiment 1 of the present invention;

Fig. 6 is a schematic diagram of label pseudonym allocation in the embodiment of the present invention;

FIG. 7 is a schematic flow diagram of a cryptographic protocol scheme provided by Embodiment 2 of the present invention;

FIG. 8 is a schematic flow diagram of a cryptographic protocol scheme provided by Embodiment 3 of the present invention;

FIG. 9 is a schematic structural diagram of the reader/writer provided by Embodiment 5 of the present invention;

Fig. 10 is a schematic diagram of the label structure provided by Embodiment 6 of the present invention.

Detailed ways

In order to make the object, technical solution and advantages of the present invention clearer, the implementation manner of the present invention will be further described in detail below in conjunction with the accompanying drawings.

For the privacy protection RFID system, the embodiment of the present invention designs a lightweight protocol LSP that only needs to perform XOR and hash operations. Its recognition efficiency is O(1), which meets the scalability requirements of the supply chain. At the same time, the LSP protocol It can well meet the four privacy protection requirements of confidentiality, untraceability, forward security, and authenticated readers at the same time, and can resist desynchronization attacks.

In order to prevent the problems existing in the prior art 1 described in the background technology, so that the attacker cannot infer the secret information of the tag through the information sent by the tag, in this solution, we strictly pay attention to the tag updated by the reader The key, pseudonym information, and the information sent by the reader are not the same as the information sent by the tag obtained by the attacker, which also prevents the attacker from counterfeiting the reader.

In order to prevent the problems existing in the second prior art described in the background art, all tags in this solution do not share a key, but the time for us to identify tags is still at a constant level.

In order to prevent desynchronization attacks, this solution also resets the value of the counter to 0 when the value of the counter reaches the maximum, but the difference from the prior art 3 described in the background technology is that when c is reset to 0, the backend database is The tag selects another random number and generates another hash chain as the pseudonym of the next round of the tag, that is, the hash value of the counter and pseudonym is different from the previous round.

In this solution, the label pseudonym is actually only hashed with a value of the counter, and it is recalculated after the current round of pseudonym is used up, which greatly reduces the calculation amount of the back-end database.

In the embodiments of the present invention, the principles and solutions of the embodiments of the present invention are described by taking the privacy protection encryption protocol in the supply chain environment as an example. In fact, the solutions provided by the embodiments of the present invention can be applied in various privacy protection environments , not limited to the supply chain environment.

Example 1

As shown in Figure 5, Embodiment 1 of the present invention provides a privacy-protecting radio frequency identification cryptographic protocol method, which specifically includes the following steps:

Step 10, the reader sends an authentication request to the tag, generates a random number r ₁ and sends it to the tag.

The reader-writer referred to in the embodiment of the present invention actually includes a back-end database. In practical applications, the reader-writer and the back-end database are not the same, but need to be connected through a communication link. Since the connected communication link can be considered safe, for the sake of simplicity of description, the embodiment of the present invention ignores the problem of connection security between the reader-writer and the back-end database, and regards the two as a whole.

When the reader sends an authentication request to the tag, it needs to generate a random number r ₁ by itself, and send the random number to the tag.

Step 20, the tag generates a random number r ₂ and calculates the value of h(Ψ _{i, x} , c) and a=h(r ₁ , r ₂ , ki ₎ , and sends it to the reader along with c.

After the tag receives the authentication request, it generates a random number r ₂ , performs hash function calculation according to its own pseudonym Ψ _{i, x} and the value c of the counter, and obtains the hash value. The tag further combines its own key _ki and two random numbers r ₁ and r ₂ to obtain a through hash calculation, and a will be used for subsequent authentication calculations.

In fact, in the design principle of the embodiment of the present invention, it is first assumed that there are n tags in the privacy protection system, where 1≤i≤n, and i is the number of each tag. The backend database selects a random number Ψ _i,0 for each label, and precomputes Ψ i _,1 = h(Ψ _i,0 ), Ψ _i,2 =h(Ψ _i,1 ),...,Ψ _{i , m-1} = h(Ψ _{i, m-2} ). The back-end database saves the Ψ _i,x of each tag, and these values will be assigned to the tags in reverse order as their pseudonyms, as shown in Figure 6.

Meanwhile, each tag has an internal counter where 0≤c≤m-1. The back-end database pre-calculates the hash value h(Ψ _{i, x} , c) of the tag pseudonym and the value c of the counter. This can greatly reduce the time to identify tags. Because when authenticating a tag, the tag pseudonym starts from the last value of the hash chain, and the value of the counter starts from 0, so here x+c=m-1, namely h(Ψ _{i, 0} , m-1), h (Ψi _,1 ,m-2),...,h(Ψi _,x ,m-1-x),...,h(Ψi _,m-1,0 ). The backend database structure is shown in Table 2 below.

Table II

h(Ψ ₁ , 0 , m-1) … h(Ψi _,0 ,m-1) … h(Ψn _,0 ,m-1) h(Ψ ₁ , 1 , m-2) … h(Ψi _,1 ,m-2) … h(Ψn _,1 ,m-2) ... … ... … ... h(Ψ _{1, m-1} , 0) … h(Ψi _{, m-1} , 0) … h(Ψn _{, m-1} , 0)

In order to speed up the identification of labels, we use the value c of the counter as an index, and sort h(Ψ _{i, x} , c) of different labels with the same c value according to the size, thus generating a linked list, as shown in Figure 6 Show. Then use binary search for h(Ψ _{i, x} , c) of different labels with the same c value, which can further speed up the identification of labels.

What needs to be explained here is that at the beginning, all pseudonyms of each label correspond to the same key and other information. When the pseudonym is updated, the key of the label pointed to by the updated pseudonym is updated, while the previous pseudonym The key does not change.

When the value c of the counter reaches the maximum m-1, the backend database selects another random number for the label, and generates another hash chain as the pseudonym Ψ' _{i, x} for the next round of the label, and c is reset to 0 at the same time. The back-end database pre-calculates the hash value h(Ψ' _{i, x} , c) of the tag pseudonym and the counter value, and the other steps are the same as above.

Each tag T _i stores its current pseudonym Ψ _{i, x} , counter value c and key _ki , where 1≤i≤n. Initially, c=0, and the pseudonym of the label is Ψ _i,m-1 .

Step 30, the reader searches for h(Ψ _{i, x} , c) in the back-end database according to the value of c, if h(Ψ _{i, x} , c) does not exist in the back-end database, the protocol is terminated, and the process ends; otherwise , obtain the corresponding tag pseudonym Ψ i, _x and key k _i according to the searched h(Ψ _{i, x} , c).

After the reader receives the content sent by the tag, it looks up h(Ψ _{i, x} , c) in the back-end database according to the received c value. In fact, the back-end database includes the pseudonyms of all tags, corresponding hash values, keys, and corresponding counter values. Here, according to the received c value, you can search in the back-end database to see if you can find it. If it can be found, it means that the received tag information is correct and has not been attacked. Otherwise, if there is no information about the tag in the backend database, it is likely to be attacked. Therefore, the protocol needs to be terminated and the process ends.

If the same value of c can be found, the reader further obtains the corresponding tag pseudonym Ψ i, _x and key k _i according to the found h(Ψ _{i, x} , c). Here, the corresponding information of the tag is found from the back-end database for subsequent comparison and authentication.

将b和d发送给标签；其中，所述Ψ_i，x＝h(Ψ_i，x-1)。Step 40, calculate a'=h(r ₁ , r ₂ , k _i ), and judge whether a' is equal to a, if not, terminate the agreement and the process ends; otherwise, calculate k' _i =h(r ₁ , r ₂ , Ψ _{i, x} , k _i ), update _ki to k' _i , Ψ _{i, x} to Ψ _{i, x-1} , calculate b=h(r ₁ , r ₂ , k' _i ) and

Send b and d to the tag; where, the Ψ _i,x =h(Ψ _i,x-1 ).

The reader/writer further calculates a'=h(r ₁ , r ₂ , _ki ) according to the found tag information, and compares this a' with the a sent by the received tag to determine whether they are equal. If they are equal, it means that the information is correct; otherwise, it means that the information of the received tag has been changed or an error has occurred, and it is likely to be attacked. Therefore, the protocol needs to be terminated and the process ends.

The reader continues to calculate k' _i = h(r ₁ , r ₂ , Ψ _{i, x} , _ki ), that is, according to the Ψ _{i, x} , _ki stored in the back-end database and the r sent by the received tag ₁ , r ₂ get k' _i through the hash algorithm, and then update k _i to k' _i , Ψ _{i, x} to Ψ _{i, x-1} .

将k’_i、Ψ_i，x-1、b和d发送给标签。Compute b=h(r ₁ , r ₂ , k' _i ) and

Send k' _i , Ψ _{i , x-1} , b and d to the label.

更新标签假名Ψ_i，x为Ψ_i，x-1、密钥k_i为k’_i，同时计数器值c增1。Step 50, the label calculates k' _i = h(r ₁ , r ₂ , Ψ _{i, x} , k _i ), b' = h(r ₁ , r ₂ , k' _i ), and judges whether b' is equal to b, if If not, the agreement is terminated and the process ends; otherwise, the calculation

Update the label pseudonym Ψ _{i , x} to Ψ _{i , x-1} , key k _i to k' _i , and increase the counter value c by 1.

After receiving _the information sent by the reader, _the tag calculates k' _i = h( _{r 1} , r _{2 ,} Ψ _{i, x} , _ki ), and calculate b'=h(r ₁ , r ₂ , k' _i ). Then, b' is compared with the received b to see if they are equal. If they are equal, it means that the received information is correct, otherwise, it means that the received information is wrong and may be attacked, the protocol needs to be terminated, and the process ends.

然后更新标签假名Ψ_i，x为Ψ_i，x-1、密钥k_i为k’_i，同时计数器值c增1。Further, continue to calculate

Then update the label pseudonym Ψ _{i , x} to Ψ _{i , x-1} , key k _i to k' _i , and increase the counter value c by 1.

At this time, a complete cryptographic protocol process is completed. Compared with the existing cryptographic protocols, the whole process has the following characteristics:

Confidentiality: In the protocol provided by the embodiment of the present invention, the key of the tag is encrypted and transmitted by the hash function each time, and the hash function is confused by different random numbers r ₁ and r ₂ each time. Due to the irreversibility of the hash function, it is difficult for an attacker to know the key information of the tag. At the same time, in this protocol, the key information of each tag is not associated, so even if a tag is captured, it is difficult for an attacker to know the information of other tags. In addition, after the tag is successfully authenticated, the key information of the tag needs to be updated. Therefore, the item information of the tag will not be known by the illegal reader, which satisfies the confidentiality.

Untraceability: In the protocol provided by the embodiment of the present invention, the tag’s pseudonym and key information are transmitted with different values each time, so even if the attacker continuously sends requests to the two tags, he cannot distinguish between the two tags. Label. Therefore, the attacker cannot track the tag according to the response information of the tag and obtain the location information of the tag.

Forward security: Assuming that the attacker knows the current key k' _i of the tag, according to the irreversibility of the hash function, he cannot pass k' _i =h(r ₁ , r ₂ , Ψ _{i, x} , k _i ) to get the previous key _ki of the tag. Therefore, an attacker can never link the label's existing state with its previous state.

Authentication reader: the tag will update its information only after checking b'=b. Due to the irreversibility of the hash function, h(r ₁ , r ₂ , _ki ') can only be calculated by knowing _ki ', and _ki '=h(r ₁ can only be calculated by knowing Ψ _{i, x} and _ki , r ₂ , Ψ _{i, x} , k _i ). Since only legitimate readers can know Ψ _{i , x} and _ki , the tag authenticates the reader.

In the protocol provided by the embodiment of the present invention, each tag only needs to store 3 secret information, and there is no additional burden compared with similar protocols, but compared with other existing protocols whose identification time is not constant, the tag The storage advantage is quite obvious. The storage capacity of the back-end database is O(mn). Assuming n=10 ⁶ and m=10 ⁶ , the memory required by the back-end database will not exceed 12TB. With the continuous improvement of the circuit manufacturing process, this is also very easy to achieve of. The most basic operation in this protocol is the hash function. For each authentication, the tag only needs to perform 4 hash operations, and the reader only needs 3 hash functions. Compared with similar protocols, the LSP protocol does not increase the calculation amount of the tag, and the calculation amount of the reader is also equivalent to other similar protocols. At the same time, the time complexity of identifying tags in the back-end database is O(1), which meets the scalability requirements of the privacy protection system.

In other schemes, all possible values of the tag’s pseudonym and the counter are hashed, and the hash value of the new pseudonym and all possible values of the counter must be recalculated after each update, so the calculation amount of the back-end database is quite large. In this solution, the label pseudonym is actually only hashed with a value of the counter, and it is recalculated after the current round of pseudonym is used up, which greatly reduces the calculation amount of the back-end database.

Example 2

并发送给标签。标签在接收到信息后，首先计算k’i＝h(r₁，r₂，Ψ_i，x，k_i)、b’＝h(r₁，r₂，k’_i)，如果b’≠b，则终止协议，否则计算

更新假名Ψ_i，x为Ψ_i，x-1、密钥k_i为k’_i，同时计数器值c增1。As shown in FIG. 7 , in the solution provided by Embodiment 2 of the present invention, the reader/writer sends an authentication request to the tag, generates a random number r ₁ and sends it to the tag. The tag generates a random number r ₂ and calculates the values of h(Ψ _{i, x} , c) and a=h(r ₁ , r ₂ , ki ₎ , and sends these values together with the value c of the counter to the reader. After receiving the information sent by the tag, the reader first finds out h(Ψ _{i, x} , c) according to the value of c, and if it does not exist, the protocol is terminated; otherwise, the pseudonym Ψ _{i, x} and key k _i corresponding to the tag are obtained . Calculate whether a'=h(r ₁ , r ₂ , k _i ) is equal to a, if not, terminate the protocol, otherwise calculate k' _i =h(r ₁ , r ₂ , Ψ _{i, x} , k _i ), Update _ki to k' _i , Ψ _{i , and x} to Ψ _{i, x-1} . Compute b=h(r ₁ , r ₂ , k' _i ) and

and sent to the label. After the tag receives the information, it first calculates k'i=h(r ₁ , r ₂ , Ψ _{i, x} , k _i ), b'=h(r ₁ , r ₂ , k' _i ), if b'≠ b, then terminate the agreement, otherwise calculate

Update pseudonym Ψ _{i , x} is Ψ _{i , x-1} , key k _i is k' _i , and counter value c is incremented by 1.

Example 3

As shown in FIG. 8 , in the solution provided by Embodiment 3 of the present invention, the value of the counter is changed in step 17 only after a round of protocol is successfully completed. The advantage of this is that it can prevent tracking attacks caused by resetting the counter value to be the same as the previous value. In this solution, the reverse hash chain is used to update the pseudonym of the label, so that since the back-end database knows the pseudonym of the label in advance, the pseudonym of the label can only be hashed with a value of the counter, and it will be restarted after the pseudonym of the current round is used up. Calculation, which greatly reduces the calculation amount of the back-end database. In addition, even if the attacker knows the current pseudonym of the tag, he cannot know the next pseudonym of the tag. In step 6, the value c of the counter is used as an index, and h(Ψ _{i, x} , c) with the same c value and different labels are sorted by size, thereby generating a linked list. Then use binary search for h(Ψ _{i, x} , c) of different labels with the same c value, which can further speed up the identification of labels. In step 10, when the pseudonym is updated, the tag key pointed to by the updated pseudonym is updated, while the tag key pointed to by the previous pseudonym remains unchanged. In this way, even after the back-end database updates the pseudonym and key of the tag, the tag itself does not update the information due to other reasons, our scheme can still resist the desynchronization attack. Because it is assumed that the tag has not received the third step of the protocol, that is, the tag information has not been successfully updated. Then what is stored in the label is still the previous secret information (Ψ _{i, x} , c, k _i ), but it has been updated to (Ψ _{i, x-1} , c+1, k _i ') in the back-end database . In the next run of the protocol, the tag generates a random number r ₂ and calculates the values of h(Ψ _{i, x} , c) and a=h(r ₁ , r ₂ , ki ₎ , and sends these values together with the value c of the counter to the reader. After receiving the information, the reader can still find out h(Ψ _{i, x} , c) from the back-end database according to the value of c, and get the corresponding pseudonym Ψ _{i, x} , because all the pseudonyms of the tag are stored in the back-end in the database. And because when the pseudonym is updated in the previous agreement, only the new pseudonym will update its corresponding key, so the label key k _i can still be obtained. From the above analysis, it can be seen that even if the tag does not successfully update the secret information, there will be no desynchronization problem between the reader and the tag. Conversely, since the tag only updates the status of the tag after successfully authenticating the reader, there will be no situation where the tag has updated its information but the back-end database has not. In summary, our protocol can resist desynchronization attacks very well.

Example 4

Embodiment 4 of the present invention provides a privacy protection radio frequency identification cryptographic protocol system, including a reader 100 and a tag 200, wherein,

将b和d发送给标签200。The reader 100 is used to send an authentication request to the tag 200, generate a random number r ₁ and send it to the tag 200; look up h(Ψ _{i, x} , c) in the back-end database according to the value of c; according to the found h( Ψ _{i, x} , c) Obtain the corresponding tag pseudonym Ψ _{i, x} and key k _i ; calculate a'=h(r ₁ , r ₂ , k _i ), and judge whether a' is equal to a; calculate k' _i = h(r ₁ , r ₂ , Ψ _{i, x} , k _i ), update _ki to k' _i , Ψ _{i, x} to Ψ _{i, x-1} , calculate b=h(r ₁ , r ₂ , k ' _i ) and

Send b and d to tag 200 .

更新标签假名Ψ_i，x为Ψ_i，x-1、密钥k_i为k’_i，同时计数器值c增1。The tag 200 is used to generate a random number r ₂ and calculate the value of h(Ψ _{i, x} , c) and a=h(r ₁ , r ₂ , k _i ), and send it to the reader 100 together with c; calculate k ' _i ＝h(r ₁ , r ₂ , Ψ _{i, x} , ki ₎ , b'=h(r ₁ , r ₂ , k' _i ), judge whether b' is equal to b; calculate

Update the label pseudonym Ψ _{i , x} to Ψ _{i , x-1} , key k _i to k' _i , and increase the counter value c by 1.

Example 5

As shown in FIG. 9 , the reader/writer 100 provided by Embodiment 5 of the present invention further includes an authentication unit 101, a first random number unit 102, a backend database 103, a first judging unit 104, and a first computing unit 105, wherein,

An authentication unit 101, configured to send an authentication request to the tag 200;

A first random number unit 102, configured to generate a random number r ₁ ;

The back-end database 103 is used to store and query the pseudonym, key, random number and counter information of the tag 200;

The first judging unit 104 is used to judge whether h(ψi _{, x} , c) exists in the back-end database 103; judge whether a' is equal to a;

The first calculation unit 105 is used to calculate a'=h(r ₁ , r ₂ , _ki ), k' _i =h(r ₁ , r ₂ , Ψ _{i, x} , _ki ), b=h(r ₁ , r ₂ , k' _i ) and

Example 6

As shown in Figure 10, the tag 200 provided by Embodiment 6 of the present invention further includes a second random number unit 201, a second calculation unit 202, a counter unit 203, a pseudonym key unit 204, and a second judging unit 205, wherein,

The second random number unit 201 is used to generate a random number r ₂ ;

The second calculation unit 202 is used to calculate h(Ψ _{i, x} , c), a=h(r ₁ , r ₂ , k _i ), k' _i =h(r ₁ , r ₂ , Ψ _{i, x} , k _i ) and b'=h(r ₁ , r ₂ , k' _i );

The counter unit 203 is used to generate and update the value c of the counter;

Pseudonym key unit 204, for storing and updating the pseudonym and key of tag 200;

The second judging unit 205 is used to judge whether b' is equal to b.

To sum up, in the solutions provided by the various embodiments of the present invention, different random numbers are generated by the reader-writer and the tag respectively, and the tag transmits the encryption according to its own pseudonym, the value of the counter, and two random numbers through a hash function, and reads and writes The reader searches the back-end database for the information corresponding to the tag pseudonym and checks whether the relevant information is accurate. The reader updates the tag key and pseudonym after calculation, and encrypts and transmits it to the tag through the hash function. After the tag is verified, it updates its own pseudonym and key, and update the value of the counter. In the solution provided by the embodiment of the present invention, the key of the label is encrypted and transmitted by the hash function every time, and the hash function is confused by different random numbers r ₁ and r ₂ each time, and the key information of each label There is no correlation, and it is difficult for an attacker to obtain the key information of the tag, thus ensuring information security. At the same time, the tag's pseudonym and key information are transmitted with different values each time, so even if the attacker sends requests to the two tags continuously, he cannot distinguish the two tags. Each label only needs to store 3 secret information, and the pseudonym of the label is actually only hashed with a value of the counter, which greatly improves the efficiency of the operation. Therefore, the solution provided by the embodiment of the present invention greatly improves the security and quickness of the cryptographic protocol, and can effectively realize RFID privacy protection.

Those of ordinary skill in the art can understand that all or part of the steps for implementing the above embodiments can be completed by hardware, and can also be completed by instructing related hardware through a program. The program can be stored in a computer-readable storage medium. The above-mentioned The storage medium mentioned may be a read-only memory, a magnetic disk or an optical disk, and the like.

The above descriptions are only preferred embodiments of the present invention, and are not intended to limit the present invention. Any modifications, equivalent replacements, improvements, etc. made within the spirit and principles of the present invention shall be included in the protection of the present invention. within range.

Claims (10)

1. A privacy protection radio frequency identification cryptographic protocol method, is characterized in that the method comprises: The reader sends an authentication request to the tag, generates a random number r ₁ and sends it to the tag; The tag generates a random number r ₂ and calculates the value of h(Ψ _{i, x} , c) and a=h(r ₁ , r ₂ , k _i ), and sends it to the reader along with c; wherein, the Ψ _{i, x} is the pseudonym of the tag, c is the value of the counter, and k _i is the key corresponding to the tag; The reader looks up h(Ψ _{i, x} , c) in the back-end database according to the value of c, if h(Ψ _{i, x} , c) does not exist in the back-end database, the protocol is terminated, and the process ends; otherwise, according to the search Get h(Ψ _{i, x} , c) to get the corresponding tag pseudonym Ψ _{i, x} and key k _i ; Calculate a'=h(r ₁ , r ₂ , k _i ), and judge whether a' is equal to a, if not, terminate the agreement and the process ends; otherwise, calculate k' _i =h(r ₁ , r ₂ , Ψ _{i, x} , k _i ), update _ki as k' _i , Ψ _{i , x} as Ψ _{i, x-1} , calculate b=h(r ₁ , r ₂ , k' _i ) and

Send b and d to the tag; wherein, the Ψ _{i, x} = h(Ψ _{i, x-1} ); Label calculation k' _i = h(r ₁ , r ₂ , Ψ _{i, x} , _ki ), b' = h(r ₁ , r ₂ , k' _i ), judge whether b' is equal to b, if not, then Terminate the agreement, the process ends; otherwise, calculate

Update the label pseudonym Ψ _{i , x} to Ψ _{i , x-1} , key k _i to k' _i , and increase the counter value c by 1. 2. The method of claim 1, further comprising: Set a total of n tags in the privacy protection system, and the number of each tag i, where 1≤i≤n; The backend database selects a random number Ψ _i,0 for each label, and precomputes Ψ i _,1 = h(Ψ _i,0 ), Ψ _i,2 =h(Ψ _i,1 ),...,Ψ _{i , m-1} = h(Ψ _{i, m-2} ); The backend database saves Ψ _i,x for each tag, and these values will be assigned to tags in reverse order as their pseudonyms. 3. The method of claim 1, further comprising: Each label has an internal counter, and the value of the counter is c, where 0≤c≤m-1; The back-end database pre-calculates the hash value h(Ψ _{i, x} , c) of the tag pseudonym and the value c of the counter; When authenticating a tag, the pseudonym of the tag starts from the last value of the hash chain, and the value of the counter starts from 0, where x+c=m-1, that is, the hash values to be calculated are: h(Ψ _{i, 0} , m-1), h(Ψ _{i, 1} , m-2), ..., h(Ψ _{i, x} , m-1-x), ..., h(Ψ _{i, m-1} , 0 ). 4. The method of claim 3, further comprising: Use the value c of the counter as an index, and sort h(Ψ _{i, x} , c) with the same c value and different labels according to size, thereby generating a linked list and saving it in the back-end database; when querying the label corresponding to h( Ψ _{i, x} , c), use binary search for h(Ψ _{i, x} , c) with the same c value and different labels. 5. The method of claim 1, further comprising: All the pseudonyms of each label correspond to the same key and other information. When the pseudonym is updated, the key of the label pointed to by the updated pseudonym is updated, while the key of the label pointed to by the previous pseudonym remains unchanged. 6. The method of claim 1, further comprising: When the value c of the counter reaches the maximum m-1, the backend database selects another random number for the label, and generates another hash chain as the pseudonym Ψ' _{i, x} for the next round of the label, and c is reset to 0; The back-end database pre-calculates the hash value h(Ψ' _{i, x} , c) of the tag pseudonym and the counter value. 7. The method of claim 1, further comprising: Each tag stores its current pseudonym Ψ _{i, x} , counter value c and key k _i , where 1≤i≤n; Initially, c=0, and the pseudonym of the label is Ψ _i,m-1 . 8. A privacy-protecting radio frequency identification cryptographic protocol system, characterized in that the system includes a reader-writer and a tag, wherein, The reader is used to send an authentication request to the tag, generate a random number r ₁ and send it to the tag; look up h(Ψ _{i, x} , c) in the back-end database according to the c value; according to the found h(Ψ _{i, x} , c) Obtain the corresponding tag pseudonym Ψ _{i, x} and key k _i ; calculate a'=h(r ₁ , r ₂ , k _i ), and judge whether a' is equal to a; calculate k' _i = h(r ₁ , r ₂ , Ψ _{i, x} , k _i ), update _ki to k' _i , Ψ _{i, x} to Ψ _{i, x-1} , calculate b=h(r ₁ , r ₂ , k' _i ) and send b and d to the label; The tag is used to generate a random number r ₂ and calculate the value of h(Ψ _{i, x} , c) and a=h(r ₁ , r ₂ , k _i ), and send it to the reader along with c; calculate k ' _i ＝h(r ₁ , r ₂ , Ψ _{i, x} , ki ₎ , b'=h(r ₁ , r ₂ , k' _i ), judge whether b' is equal to b; calculate

Update the label pseudonym Ψ _{i , x} to Ψ _{i , x-1} , key k _i to k' _i , and increase the counter value c by 1. 9. The system according to claim 8, wherein the reader/writer further comprises an authentication unit, a first random number unit, a backend database, a first judgment unit and a first calculation unit, wherein, The authentication unit is configured to send an authentication request to the label; The first random number unit is used to generate a random number r ₁ ; The back-end database is used to store and query tag pseudonyms, keys, random numbers and counter information; The first judging unit is used to judge whether h(Ψ _{i, x} , c) exists in the back-end database; judge whether a' is equal to a; The first calculation unit is used to calculate a'=h(r ₁ , r ₂ , _ki ), k' _i =h(r ₁ , r ₂ , Ψ _{i, x} , _ki ), b=h( r ₁ , r ₂ , k' _i ) and $d={\mathrm{\Ψ}}_{i,x}\⊕{\mathrm{\Ψ}}_{i,x-1}.$ 10. The system according to claim 8 or 9, wherein the tag further comprises a second random number unit, a second computing unit, a counter unit, a pseudonym key unit and a second judging unit, wherein, The second random number unit is used to generate a random number r ₂ ; The second calculation unit is used to calculate h(Ψ _{i, x} , c), a=h(r ₁ , r ₂ , k _i ), k' _i =h(r ₁ , r ₂ , Ψ _{i, x} , k _i ) and b'=h(r ₁ , r ₂ , k' _i ); The counter unit is used to generate and update the value c of the counter; The pseudonym key unit is used to store and update the pseudonym and key of the tag; The second judging unit is used to judge whether b' is equal to b.

Images