JP2007189643A - Method, system, device, and program for communication - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To provide a communication method which can attain untraceability of a tag to be accessed through a reader with less processing volume than the conventional volume. <P>SOLUTION: A managing device 7 searches k' which satisfies a formula of ST8 from among items K and Klast of table data TD, and specifies an ID of the searched entry. When a predetermined value k' is searched from the item K in the search, the managing device 7 copies the value of the item K of the entry into the item Klast of the entry. A hash value of the k' is set to the item K. <P>COPYRIGHT: (C)2007,JPO&INPIT

Description

  The present invention relates to a communication method, a communication system, a communication device, and a program for performing secure communication between a tag and a management device via a reader between the tag and the management device.

For example, RFID (Radio Frequency Identification) is used to store identification information in a microchip, detect it with a radio frequency, and automatically detect information about a managed object.
RFID technology is more convenient than optical bar codes because it can instantly identify a large number of tags by radio frequency without making physical or visual contact. RFID systems can be used in many automation fields and are useful in ubiquitous computer environments.
However, while RFID technology is convenient, it also has security problems. For example, there is a problem that information about a company or an individual leaks because an RFID transmits it to a party who wants to know the information.
For example, if a tag possessed by a certain user is detected in response to a reader (reader / writer) at point A and then detected at point B, then an attacker (wiretapping) indicates that the user has moved from point A to point B. And the privacy of the user is infringed. In addition, even when confidential information in a tag is leaked, it is necessary to make it impossible to trace the processing related to the tag.
In order to solve such a problem, a system with untraceability that cannot track communication between a tag and a reader has been proposed. Even if the attacker physically attacks (tampers) the tag and obtains the secret information of the memory, the system identifies the one with which this tag was involved in the communication between many past tags and readers. It cannot be forward security. A system having these properties is disclosed in Non-Patent Document 1 below.
Miyako Ohkubo, Koutarou Suzuki, and Shingo Kinoshita. “Cryptographic approach to privacy-friendly 'tag.” In RFID Privacy Workshop, MIT, MA, USA, November 2003.

  In the system of Non-Patent Document 1, the total number of tags in the system is m, and the maximum number of interactions with the reader allowed for each tag is n, and the server has a hash of m * n times for each interaction. There is a problem that it is necessary to perform calculation of a function and a processing load is large.

  The present invention has been made in view of the above-described prior art, and a communication method, a communication system, a communication apparatus, and a communication method, which can achieve non-traceability of a tag accessed via a reader with a smaller processing amount than in the past. The purpose is to provide a program.

In order to solve the above-described problems of the prior art and achieve the above-described object, a communication method according to a first aspect of the present invention is a communication method performed between a tag, a reader, and a management device. , A first step of transmitting the random number s to the tag, and a hash value obtained by the tag using the first secret data r _i and the second secret data k _j as arguments, the first secret data r _{i + 1} As a second step to be transmitted to the management device via the reader, the random number s received by the tag in the first step, and the first secret data r generated in the second step. _{Based on i + 1} , the third step of generating the first secret data r _{i + 2} and transmitting it to the management device via the reader, the reader receiving the random number s and the third step It was the first secret data r _{i + 2,} the tube A fourth step of transmitting device, the management device, the secret data r _{i + 1} received by the first in the second step, the random number s received in the fourth step, the predetermined value k ' And a fifth step of specifying the predetermined value k ′ that makes the hash value obtained on the basis of the first secret data r _{i + 2,} and the management device identifies the identification data of a plurality of tags. Referring to the table data indicating the data, the first value K, and the second value Klast in association with each other, the predetermined value k ′ specified in the fifth step and the first value K or the second value A sixth step of searching for an entry having the same value Klast, and the management apparatus, when an entry having a predetermined value k ′ and the first value K is present in the table data, Copy the first value K to the second value Klast, the predetermined value It has a seventh step of setting the hash value of the value k 'to the first value K.

A communication system according to a second aspect of the invention is a communication system having a tag, a reader, and a management device, wherein the reader transmits a random number s to the tag, and the tag is connected to the first secret data r _i . A hash value obtained using the second secret data k _j as an argument is transmitted as _first secret data r _{i + 1} to the management apparatus via the reader, and the tag receives the random number s received and the generation The first secret data r _{i + 1} is generated based on the _first secret data r _{i + 1} and is transmitted to the management device via the reader, and the reader receives the random number s and the received the received secret data r _{i + 2} The first secret data r _{i + 2} is transmitted to the management device, and the management device is based on the received first secret data r _{i + 1} , the received random number s, and a predetermined value k ′. The hash value obtained Identifying the predetermined value k 'to be the first secret data r _{i + 2,} the management device, corresponding to the relevant identification data and a first value K second value Klast the identification data of a plurality of tags With reference to the table data shown, the entry for which the specified predetermined value k ′ matches the first value K or the second value Klast is searched, and the management apparatus determines the predetermined value k ′. And the first value K match, the first value K is copied to the second value Klast, and the hash value of the predetermined value k ′ is stored in the table data. Set to the first value K.

A communication method according to a third aspect of the invention is a communication method executed by a communication device that communicates with a tag via a reader, and uses the first secret data r _i and the second secret data k _j as arguments. A first step of receiving _first secret data r _{i + 1} that is a hash value generated by the tag from the tag via the reader; a random number s received by the tag from the reader; and the first secret data. a second step of receiving first secret data r _{i + 2} generated based on r _{i + 1} from the tag via the reader; and receiving the random number s and the first secret data r _{i + 2} from the reader. A hash obtained based on the third step, the first secret data r _{i + 1} received in the first step, the random number s received in the third step, and a predetermined value k ′ the value is, the first secret data r _i A fourth step of identifying the predetermined value k 'to be _2, the identification data of a plurality of the tags the identification data a first value K and table data shown in association with the second value Klast Referring to the fifth step of searching for an entry in which the predetermined value k ′ specified in the fourth step matches the first value K or the second value Klast, and the predetermined value k ′. And the first value K match, the first value K is copied to the second value Klast, and the hash value of the predetermined value k ′ is stored in the table data. And a sixth step of setting to the first value K.

A communication device according to a fourth aspect of the invention is a communication device that communicates with a tag via a reader, and the tag is generated using the first secret data r _i and the second secret data k _j as arguments. First secret data r _{i + 1} that is a hash value is received from the tag via the reader, and the tag is generated based on the random number s received from the reader and the first secret data r _{i +} 1. The secret data r _{i + 2} is received from the tag through the reader, the random number s and the first secret data r _{i + 2} are received from the reader, and the identification data of the identification data of the plurality of tags A memory for storing table data indicating the first value K and the second value Klast in association with each other; the first secret data r _{i + 1} received by the interface; The hash value obtained based on the number s and the predetermined value k ′ specifies the predetermined value k ′ that becomes the first secret data r _{i + 2,} and refers to the table data to determine the specific An entry in which the predetermined value k ′ matches the first value K or the second value Klast is searched, and an entry in which the predetermined value k ′ matches the first value K is the table data. And a processing circuit that copies the first value K to the second value Klast and sets the hash value of the predetermined value k ′ to the first value K.

A program according to a fifth aspect of the invention is a program executed by a communication device that communicates with a tag via a reader, and the tag is used with the first secret data r _i and the second secret data k _j as arguments. The first procedure for receiving the first secret data r _{i + 1} that is the hash value generated from the tag via the reader, the random number s received by the tag from the reader, and the first secret data r _{i + 1} The second procedure for receiving the first secret data r _{i + 2} generated based on the tag from the tag via the reader, and the second procedure for receiving the random number s and the first secret data r _{i + 2} from the reader. And a hash value obtained based on the first secret data r _{i + 1} received in the first procedure, the random number s received in the third procedure, and a predetermined value k ′. , The first secret data a fourth step of identifying the _{i + 2} to become the predetermined value k ', the identification data of a plurality of the tags the identification data a first value K and table data shown in association with the second value Klast Referring to the fifth procedure for searching for an entry in which the predetermined value k ′ specified in the fourth procedure matches the first value K or the second value Klast, and the predetermined value k ′. And the first value K match, the first value K is copied to the second value Klast, and the hash value of the predetermined value k ′ is stored in the table data. The communication apparatus is caused to execute a sixth procedure for setting the first value K.

  According to the present invention, it is possible to provide a communication method, a communication system, a communication apparatus, and a program that can achieve non-traceability of a tag accessed through a reader with a smaller processing amount than in the past.

Hereinafter, a communication system according to an embodiment of the present invention will be described.
[Correspondence with Configuration of the Present Invention]
First, the correspondence between the components of the present embodiment and the components of the present invention will be described.
The RF tag 3 is an example of the tag of the present invention, the tag reader 5 is an example of the reader of the present invention, and the management device 7 is an example of the management device and the communication device of the present invention.
The program PRG3 executed by the management device 7 is an example of the program of the present invention.
The table data TD shown in FIG. 3 is an example of the table data of the present invention.

FIG. 1 is an overall configuration diagram of a communication system 1 according to an embodiment of the present invention.
As illustrated in FIG. 1, the communication system 1 includes, for example, an RF tag 3, a tag reader 5, and a management device 7.

In the communication system 1 shown in FIG. 1, there are actually a plurality of RF tags 3 and tag readers 5.
Communication between the RF tag 3 and the tag reader 5 is non-secure, and communication between the tag reader 5 and the management device 7 is secure.

  The communication system 1 employs a protocol with a small calculation amount in the RF tag 3. This protocol uses two secret data shared by the RF tag 3 and the management device 7 in addition to the hash functions employed in various protocols proposed conventionally. The management device 7 uses table data TD, which will be described later. Thereby, the calculation amount in the management apparatus 7 can be reduced. By using the two secret data and the table data TD in this way, the calculation complexity in the management device 7 can be reduced, and the untrackability that makes it impossible to track the tag based on the information acquired by the reader. (untraceability) can be achieved completely, it can be judged whether the information from the tag is appropriate, and even if the secret information of the tag is leaked, the processing related to the tag can be made unidentifiable (detect forgery).

First, the configuration of the RF tag 3, the tag reader 5, and the management device 7 will be described.
FIG. 2 is a configuration diagram of the RF tag 3 and the tag reader 5 shown in FIG.
[RF tag 3]
As shown in FIG. 2, the RF tag 3 includes, for example, an RF circuit 11, a memory 13, and a processing circuit 15.
The RF circuit 11 is a circuit including an antenna coil that performs radio communication with the RF circuit 21 of the tag reader 5 at a predetermined radio frequency.
When the RF tag 3 is a passive type that does not have a battery, the RF circuit 11 receives radio waves from the tag reader 5 and generates an electromotive force by a resonance action. The processing circuit 15 of the RF tag 3 operates by the electromotive force.
In the present embodiment, the memory 13 and the processing circuit 15 are tamper resistant circuits.

The memory 13 stores, for example, a program PRG1 that defines the processing of the processing circuit 15 and various data used for the processing of the processing circuit 15.
As the memory 13, EEPROM, FeRAM, or the like is used.

  The processing circuit 15 executes the program PRG1 read from the memory 13, and performs a communication process with the tag reader 5, an authentication process with the management apparatus 7, an internal secret data r, k update process, and the like. .

[Tag reader 5]
As shown in FIG. 2, the tag reader 5 includes, for example, an RF circuit 21, an interface 23, a memory 25, and a processing circuit 27.
The RF circuit 21 performs radio communication with the RF circuit 11 of the RF tag 3 at a predetermined radio frequency.

The interface 23 communicates with the management device 7 via a secure network.
The memory 25 stores, for example, the program PRG2 that defines the processing of the processing circuit 27 and various data used for the processing of the processing circuit 27.
The processing circuit 27 executes the program PRG2 read from the memory 25, and performs communication processing between the RF tag 3 and the management device 7.
The processing circuit 27 has a random number generation function.
In the present embodiment, the tag reader 5 has a function of writing data to the RF tag 3 in addition to a function of reading data from the RF tag 3.

[Management device 7]
FIG. 3 is a configuration diagram of the management apparatus 7 shown in FIG.
As illustrated in FIG. 3, the management device 7 includes, for example, an interface 31, a memory 33, and a processing circuit 35.
The interface 31 communicates with the tag reader 5 via a secure network.
The memory 33 stores, for example, the program PRG3 that defines the processing of the processing circuit 35 and various data used for the processing of the processing circuit 35.
The processing circuit 35 executes the program PRG3 read from the memory 33, and performs communication processing between the RF tag 3 and the tag reader 5.

[Example of overall operation]
4 and 5 are flowcharts for explaining an overall operation example of the communication system 1 shown in FIG.
Step ST1:
The processing circuit 27 of the tag reader 5 shown in FIG. 2 generates a random number s.

Step ST2:
The processing circuit 27 transmits the random number s generated in step ST1 to the RF tag 3 via the RF circuit 21.

Step ST3:
The processing circuit 15 of the RF tag 3 generates a hash value based on the secret data r _i , k _j read from the memory 13 as shown in the following formula (1), and sets this as secret data r _{i + 1} . In the present embodiment, “XOR” indicates exclusive OR. h () represents a hash function.
In the present embodiment, the hash function H used by the processing circuit 15 of the RF tag 3 and the processing circuit 35 of the management device 7 for generating the hash value is “H: {0, 1} ^l → {0, 1} ^l ”. Defined.

[Equation 1]
_{r i + 1 ← h (r} i XOR k j)
... (1)

Step ST4:
The processing circuit 15 of the RF tag 3 transmits the secret data r _{i + 1} generated in step ST3 to the tag reader 5 via the RF circuit 11.
The processing circuit 27 of the tag reader 5 transmits the secret data r _{i + 1} received by the RF circuit 21 to the management device 7 via the interface 23.
The secret data r _x , k _x (x = i, i + 1,...) Used by the processing circuit 27 is l-bit data. Here, kx indicates a different value in each of the plurality of RF tags 3 used for identifying the RF tag 3. The initial value of k _x is assigned a value calculated in advance in order to ensure that a different value is assigned to each of the plurality of RF tags 3.
When the number of RF tags 3 in the communication system 1 is m and the maximum number of times each RF tag 3 performs authentication is n, it is necessary to have sufficient resistance against unauthorized attacks. Therefore, in the communication system 1, when generating the hash value, a hash chain is constructed as shown below.
The hash chain, starting from the secret seed t, the second of k2 is h (t), the x-th _{k x} is h _{(k x-1).} Here, “3 ≦ x ≦ mn”. In this embodiment, the secret seed t is selected so that the hash chain is longer than mn. The initial value of the secret data k of each RF tag 3 is selected from the _knp- th element of the hash chain. Here, “1 ≦ p ≦ m” holds. The value of each secret data k is stored in the memory 13 of each RF tag 3 and is associated with the identification data IDR of each RF tag 3 in the table data TD of the management device 7. When the authentication is successful, the RF tag 3 and the management device 7 update the secret data k to the next value in the hash chain.

Step ST5:
The processing circuit 15 of the RF tag 3 obtains the secret data r _{i + 1} generated in step ST3, the secret data k _j read from the memory 13, and the random number s received in step ST2, as shown in the following formula (2). A hash value is generated based on this, and this is set as secret data r _{i + 2} .

[Equation 2]
r _{i + 2} ← h (r _{i + 1} XOR k _j XOR s)
... (2)

Step ST6:
The processing circuit 15 of the RF tag 3 transmits the secret data r _{i + 2} generated in step ST5 to the tag reader 5 via the RF circuit 11.
The processing circuit 27 of the tag reader 5 transmits the random number s generated in step ST1 and the secret data r _{i + 2} received by the RF circuit 21 to the management apparatus 7 via the interface 23.

Step ST7:
The processing circuit 15 of the RF tag 3 generates a hash value based on the secret data r _{i + 2} generated in step ST5 and the secret data k _j read from the memory 13, as shown in the following formula (3). Is set to secret data r _{i + 3} .

[Equation 3]
r _{i + 3} ← h (r _{i + 2} XOR k _j )
... (3)

Step ST8:
Based on the secret data r _{i + 1} received in step ST4, the random number s and the secret data r _{i + 2} received in step ST6, the processing circuit 35 of the management device 7 sets a predetermined value k ′ that satisfies the following equation (4). The search is performed from the items K and Klast of the table data TD shown in FIG.

[Equation 4]
h (r _{i + 1} XOR k ′ XOR s) = r _{i + 2}
... (4)

  As shown in FIG. 3, each entry of the table data TD has items IDR, K, and Klast, and the ID of the RF tag 3, the current secret data k, the previous secret data k (the current secret data k) Value before being updated). In the table data TD, the identification data ID of each RF tag 3 and the initial value of the secret data k are first set in the items IDR and K, respectively, and the item Klast is a null value. The item Klast is used to solve the desynchronization problem. When the management device 7 updates the secret data k of the RF tag 3 (for example, the value of the item K corresponding to the RF tag 3), and the RF tag 3 does not receive the information from the management device 7 due to an attack or a communication error However, the management device 7 can specify the previous identification data ID of the RF tag 3 by referring to the item Klast of the table data TD.

Step ST9:
When the predetermined value k ′ is searched from the item K in the above search, the processing circuit 35 sets the value of the item K of the entry to the item of the entry as shown in the following equation (5). Copy to Klast. Further, the processing circuit 35 sets the hash value of k ′ in the item K as shown in the following formula (6).

[Equation 5]
(Value of item Klast of searched entry) ← (value of item K of searched entry)
... (5)

[Equation 6]
(Value of item K of retrieved entry) ← h (k ′)
(6)

The processing circuit 35 does not update the table data TD when the predetermined value k ′ is searched from the item Klast in the above search.
The processing circuit 35 acquires information that can track the usage history of the RF tag 3 from the identification data IDR of the entry specified by the search in step ST9 and the identification data of the tag reader 5 used for the search. it can. Such information may be generated by the processing circuit 35 or may be performed by a server device other than the management device 7 based on the information acquired by the processing circuit 35.

Step ST10:
As shown in the following formula (7), the processing circuit 35 of the management device 7 generates a hash value based on the secret data ri + 2 received in step ST6 and the predetermined value k ′ searched in step ST8. To secret data r _{i + 3} ′.

[Equation 7]
r _{i + 3} '← h (r _{i + 2} XOR k')
... (7)

Step ST11:
The processing circuit 35 of the management device 7 transmits the secret data r _{i + 3} ′ generated in step ST10 to the RF tag 3 via the tag reader 5.

Step ST12:
Processing circuit 15 of the RF tag 3 includes a secret data _{r i + 3} 'received in step ST11, by comparing the secret data _{r i + 3} generated in step ST7, the process proceeds to step ST13 if the match.

Step ST13:
As shown in the following formula (8), the processing circuit 15 of the RF tag 3 generates a hash value based on the secret data r _{i + 3} generated in step ST7 and the secret data k _j, and uses this as secret data r _{i + 4.} Set to.

[Equation 8]
r _{i + 4} ← h (r _{i + 3} XOR k _j )
(8)

Step ST14:
Processing circuit 15 of the RF tag 3, as shown in the following formula (9), to generate a hash value of the secret data k _j, set it to the secret data k _{j + 1.}

[Equation 9]
k _{j + 1} ← h (k _j )
... (9)

[Operation example of RF tag 3]
FIG. 6 is a flowchart for explaining an operation example of the RF tag 3 shown in FIG.
Step ST21:
The RF circuit 11 shown in FIG. 2 performs wireless communication with the RF circuit 21 of the tag reader 5 and receives the random number s generated by the tag reader 5.

Step ST22:
The processing circuit 15 of the RF tag 3 generates a hash value based on the secret data r _i , k _j read from the memory 13 as shown in the above formula (1), and sets this as secret data r _{i + 1} .

Step ST23:
The processing circuit 15 of the RF tag 3 transmits the secret data r _{i + 1} generated in step ST22 to the tag reader 5 via the RF circuit 11.

Step ST24:
The processing circuit 15 of the RF tag 3 receives the secret data r _{i + 1} generated in step ST23, the secret data k _j read from the memory 13, and the random number s received in step ST21, as shown in the above equation (2). A hash value is generated based on this, and this is set as secret data r _{i + 2} .

Step ST25:
The processing circuit 15 of the RF tag 3 transmits the secret data r _{i + 2} generated in step ST24 to the tag reader 5 via the RF circuit 11.

Step ST26:
The processing circuit 15 of the RF tag 3 generates a hash value based on the secret data r _{i + 2} generated in step ST24 and the secret data k _j read from the memory 13, as shown in the above equation (3). Is set to secret data r _{i + 3} .

Step ST27:
The processing circuit 15 of the RF tag 3 determines whether or not the RF circuit 11 has received a response from the management device 7, and proceeds to step ST28 if it is determined that it has been received, and returns to step ST21 otherwise.

Step ST28:
The processing circuit 15 of the RF tag 3 determines whether or not the response received by the RF circuit 11 is a RESET signal. If it is determined that the response is a RESET signal, the processing returns to step ST21; Proceed to ST29.

Step ST29:
The processing circuit 15 of the RF tag 3 determines whether or not the response received by the RF circuit 11 is a FIN signal. If it is determined that the response is a FIN signal, the processing is terminated. Proceed to ST30.

Step ST30:
Processing circuit 15 of the RF tag 3 includes a secret data _{r i + 3} 'RF circuit 11 is a response received above, compares the secret data _{r i + 3} generated in step ST26, the flow advances to step ST31 if the match, If not, the process ends.

Step ST31:
As shown in the above equation (8), the processing circuit 15 of the RF tag 3 generates a hash value based on the secret data r _{i + 3} generated in step ST26 and the secret data k _j, and converts this into secret data ri + 4. Set.

Step ST32:
The processing circuit 15 of the RF tag 3 generates a hash value of the secret data k _j as shown in the above formula (9), and sets this as secret data k _{j + 1} .

  The processing circuit 15 of the RF tag 3 forcibly ends the processing shown in FIG. 6 when the RF circuit 11 no longer provides energy from the RF circuit 21.

[Operation example of tag reader 5]
FIG. 7 is a flowchart for explaining an operation example of the tag reader 5 shown in FIG.
Step ST41:
The processing circuit 27 of the tag reader 5 shown in FIG. 2 generates a random number s.

Step ST42:
The processing circuit 27 of the tag reader 5 transmits the random number s generated in step ST1 to the RF tag 3 via the RF circuit 21.

Step ST43:
The processing circuit 27 of the tag reader 5 waits for a predetermined time T, for example, until the RF circuit 21 receives the secret data r _{i + 1} and r _{i + 2} from the RF tag 3.

Step ST44:
The processing circuit 27 of the tag reader 5 determines whether or not the waiting time has passed the time T. If it is determined that the waiting time has not elapsed, the processing proceeds to step ST45. Otherwise, the processing proceeds to step ST45.

Step ST45:
The processing circuit 27 of the tag reader 5 transmits a FIN signal to the RF tag 3 via the RF circuit 21.

Step ST46:
The processing circuit 27 of the tag reader 5 transmits the random number s generated in step ST41 and the secret data r _{i + 1} and r _{i + 2} received from the RF tag 3 to the management apparatus 7 via the RF circuit 21.

Step ST47:
The processing circuit 27 of the tag reader 5 receives a response from the management device 7.

Step ST48:
The processing circuit 27 of the tag reader 5 determines whether or not the response received in step ST47 is the secret data r _{i + 3} ′. If so, the process proceeds to step ST49, and if not, the process proceeds to step ST50.

Step ST49:
The processing circuit 27 of the tag reader 5 transmits the received secret data r _{i + 3} ′ to the RF tag 3 via the RF circuit 21.

Step ST50:
The processing circuit 27 of the tag reader 5 determines whether or not the response received in step ST47 is a COLLISION signal. If so, the process proceeds to step ST51. If not, the process proceeds to step ST52.

Step ST51:
The processing circuit 27 of the tag reader 5 transmits a RESET signal to the RF tag 3 via the RF circuit 21.

Step ST52:
The processing circuit 27 of the tag reader 5 transmits a FIN signal to the RF tag 3 via the RF circuit 21.

[Management device 7]
FIG. 8 is a flowchart for explaining an operation example of the management apparatus 7 shown in FIG.
Step ST61:
The interface 31 of the management device 7 receives the random number s and the secret data r _{i + 1} and r _{i + 2} from the tag reader 5 and writes them in the memory 33.

Step ST62:
The processing circuit 35 of the management device 7 reads a predetermined value k ′ satisfying the above equation (4) from the memory 33 based on the random number s and the secret data r _{i + 1} and r _{i + 2} read from the memory 33 in FIG. Search is made from items K and Klast of the indicated table data TD.

Step ST63:
If the processing circuit 35 of the management apparatus 7 determines that one or more k ′ has been searched in the search of step ST62, the process proceeds to step ST63, and if not, the process proceeds to step ST64.

Step ST64:
The processing circuit 35 of the management device 7 transmits a FAILURE signal to the tag reader 5 via the interface 31.

Step ST65:
If the processing circuit 35 of the management device 7 determines that one k ′ has been searched in the search in step ST62, the process proceeds to step ST67, and if not, the process proceeds to step ST66.

Step ST66:
The processing circuit 35 of the management device 7 transmits a COLLISION signal to the tag reader 5 via the interface 31.

Step ST67:
If the processing circuit 35 of the management device 7 determines that the predetermined value k ′ has been searched from among the items K in the search of step ST62, the process proceeds to step ST68, and if not, the processing ends.

Step ST68:
As shown in the above formula (5), the processing circuit 35 of the management device 7 copies the value of the item K of the entry for which the predetermined value k ′ has been searched in step ST62 to the item Klast of the entry.
Further, the processing circuit 35 sets the hash value of k ′ in the item K of the entry as shown in the above equation (6).
Note that the processing circuit 35 does not update the table data TD when the predetermined value k ′ is searched from the item Klast in the search.

Step ST69:
As shown in the above equation (7), the processing circuit 35 of the management device 7 generates a hash value based on the secret data r _{i + 2} received in step ST61 and the predetermined value k ′ searched in step ST62. This is set to the secret data r _{i + 3} ′.
Then, the processing circuit 35 transmits the generated secret data r _{i + 3} ′ to the tag reader 5 through the interface 31.

As described above, according to the communication system 1, by specifying the ID of the RF tag 3 using the table data TD in the management device 7 as described above, the total number of RF tags 3 is allowed to m and each tag is allowed. When the maximum number of interactions with the tag reader 5 is n, the calculation of the hash function can be performed 2m times, and the calculation amount of the management device 7 is greatly increased compared to m * n times of the system of Non-Patent Document 1. Can be reduced.
That is, in the system of Non-Patent Document 1, a seed previously assigned to each tag is used as an initial value of an argument, and a hash value is sequentially generated for each tag using the previous hash value as an argument. For each tag, an ID is searched based on the hash value generated at each stage and the value input from the tag. Therefore, it is necessary to perform n hash operations for ID search of each tag, and it is necessary to perform a total of m * n hash operations for m tags.
On the other hand, in the communication system 1, by using the table data TD described above, for each tag, a hash operation for generating k ′ based on the above equation (4) and the table data TD are configured. It is only necessary to perform two times with the hash calculation. Therefore, when the number of RF tags 3 is m (the number of entries in the table data TD is m), it is only necessary to perform a total of m * n hash operations, and the calculation amount of the management device 7 can be greatly reduced.

Moreover, according to the communication system 1, it can have sufficient security as shown below.
Hereinafter, the security of the communication system 1 described above will be described.
Assuming that the hash value h () is a random oracle, the communication system 1 is safe against all possible attacks except for unauthorized modification of the memory 13 of the RF tag 3. On the other hand, updating the information in the memory 13 reduces the possibility of this attack being successful. The following is a security analysis for each attack.

For an attack by interception, the attacker can collect a random number s and three consecutive secret data r during one authentication process. Since s is a random value, the RF tag 3 cannot be tracked. As a result, the attacker must use the value r. On the other hand, if h is a random oracle, an attacker who does not know kj of the RF tag 3 cannot distinguish each output of the RF tag 3 from a random value. The only way to distinguish real random values from random oracle outputs is to regenerate random oracles with the same inputs to get the same output. On the other hand, the attacker cannot know the input of h. This is because the attacker does not know that k _j is one of the parameters of h (). As a result, the attacker considers the output of the RF tag 3 as a random value. Therefore, the attacker cannot track the RF tag 3 because all the values from the RF tag 3 are seen as genuine random values or random values for the attacker.

Regarding forgery, since the attacker does not know k of the RF tag 3, the attacker who cannot generate r _{i + 2} from r _{i + 1} needs to perform repetitive attacks. As a result, the attacker can send two random values, and the probability that this attack forges a special tag is l · 2 ^l−1 . This is because there are two values in the items of K and Klast, which are used for the verification of the above equation (4), and that the possibility of forging an arbitrary tag of the system is m / 2 ^l-1 and ignored. It will be possible. On the other hand, attackers may try to attack repeatedly by forging regular interactions. Here, s is used by forgery, and unlike the one sent by the tag reader 5, the attacker's repeated attack is not successful.

For an attack that controls the random number s, the attacker attempts to generate a response for the RF tag 3, but there are many patterns that must be tracked by controlling the random number s. If the attacker can guess r _{i + 1} before sending the random number s, the attacker can always make the data reply the same by sending the data response continuously with the value r _{i + 1} as the random number S. In that case, r _{i + 2} is always a fixed value h (k _j ) and the attacker can track the tag. On the other hand, since the secret data k _j is a secret value, the attacker cannot predict r _{i + 1} and cannot track the tag by this attack.

For an attack by updating the tag, the attacker may attempt an asynchronous attack by updating the secret key of tag 3. On the other hand, without the help of the management device 7, the attacker cannot know _{ri + 3} . This is because the attacker do not know the current kj, _{k j} is because it requires calculated from _{r i + 2} of _{r i + 3.}

As for the attack due to the database update, the attacker may attempt to perform an attacker attack on the asynchronous k between the database of the management device 7 and the tag. The communication system 1 estimates that the tag 3 is away from the tag reader 5 and that the attacker can deliver data between the two comments. When the tag reader 5 starts the authentication process, the attacker moves s from the tag reader 5 to the RF tag 3, and then moves r _{i + 1} and r _{i + 2} to the tag reader 5. Then, the management device 7 updates k. Thereafter, the server transmits r _{i + 3} ′ even though the tag reader 5 has updated k of the RF tag 3. At this time, if the attacker does not deliver it to tag 3, k will be different between the database and the tag. If the management device 7 uses only the latest k in order to find the ID, this tag 3 cannot be used. On the other hand, the management device 7 stores another k, and the latest k is set in the item of Klast. Using this, the management device 7 identifies the tag 3. When the tag 3 is identified using the Klast item, the management device 7 does not update k, so two items K and Klast are sufficient to protect the system from asynchronous attacks.

  For energy controlled attacks, it is assumed that the tag 3 capacitor does not have enough capacity to operate all processes at once, and then whenever the attacker wants to exclude mission operations, tag processing Assume that it can be stopped. This assumption may weaken other schemes. For example, the system of Non-Patent Document 1 sends data and updates the contents of the memory. The attacker stops the tag authentication process immediately before the tag 3 updates the contents of the memory, and acquires the same response every time. However, the communication system 1 is sufficiently resistant to such attacks. That is, the communication system 1 updates the data before transmitting it. This guarantees variations in the response of the tag 3 to such an attack.

For an attack based on a hash chain, the maximum number n of tag authentication processes needs to be large enough to withstand an attack based on a memory tamper. First, the attacker illegally reads the k and ktamp of the tag. Thereafter, the attacker obtains k and ktarget of other target tags as shown below. Assume that an attacker is lucky enough to acquire a ktamper one before the ktamper in the hash chain. The attacker makes an inquiry to the management apparatus using the random number s, and obtains r _{i + 1} and r _{i + 2} . An attacker can search for ktamper by testing whether it matches with k ′, which is all values in the hash chain starting from ktamper. This is the length of the hash chain is not the 2 ^l, it is shorter and 2 l ^{/ 2.} Such a problem exists not only in the communication system 1 but also in all systems using a hash chain.

  For an attack by a memory tamper, if the attacker obtains k by tampering with the memory of the tag 3 and intercepts communications between the management device and various tags, the attacker Can be tracked. The attacker tests the above equation (4) using the fixed value k and information collected by interception. Then, when any of the intercepted information passes the test, the attacker specifies the information. However, this forward trace is not applicable when information generated before the last update of k is used in communication. That is, even if the attacker knows the current k, k is updated by the one-way function h, and thus cannot know the previous k of the tag 3. Therefore, forward tracing is limited to a short time and cannot be used for processes where authentication continues.

The present invention is not limited to the embodiment described above.
That is, those skilled in the art may make various modifications, combinations, subcombinations, and alternatives regarding the components of the above-described embodiments within the technical scope of the present invention or an equivalent scope thereof.

FIG. 1 is an overall configuration diagram of a communication system according to an embodiment of the present invention. FIG. 2 is a configuration diagram of the RF tag and tag reader shown in FIG. FIG. 3 is a block diagram of the management apparatus shown in FIG. FIG. 4 is a flowchart for explaining an overall operation example of the communication system shown in FIG. FIG. 5 is a flowchart subsequent to FIG. 4 for explaining an example of the overall operation of the communication system shown in FIG. FIG. 6 is a flowchart for explaining an operation example of the RF tag shown in FIG. FIG. 7 is a flowchart for explaining an operation example of the tag reader shown in FIG. FIG. 8 is a flowchart for explaining an operation example of the management apparatus shown in FIG.

Explanation of symbols

  DESCRIPTION OF SYMBOLS 1 ... Communication system, 3 ... RF tag, 5 ... Tag reader, 7 ... Management apparatus, 11 ... RF circuit, 13 ... Memory, 15 ... Processing circuit, 21 ... RF circuit, 23 ... Interface, 25 ... Memory, 27 ... Processing circuit 31 ... Interface, 33 ... Memory, 35 ... Processing circuit, TD ... Table data

Claims (6)

A communication method performed between a tag, a reader and a management device,
A first step in which the reader transmits a random number s to the tag;
The tag transmits a hash value obtained by using the first secret data r _i and the second secret data k _j as arguments to the management device via the reader as _first secret data r _{i + 1} . Process,
The tag generates first secret data r _{i + 2} based on the random number s received in the first step and the first secret data r _{i + 1} generated in the second step, A third step of transmitting to the management device via the reader;
A fourth step in which the reader transmits the random number s and the first secret data r _{i + 2} received in the third step to the management device;
A hash value obtained by the management device based on the first secret data r _{i + 1} received in the second step, the random number s received in the fourth step, and a predetermined value k ′ is obtained. , A fifth step of identifying the predetermined value k ′ to be the first secret data r _{i + 2} ;
The management device refers to the table data indicating the identification data, the first value K, and the second value Klast in association with the identification data of a plurality of tags, and the predetermined data specified in the fifth step A sixth step of searching for an entry in which the value k ′ matches the first value K or the second value Klast;
The management device copies the first value K to the second value Klast when an entry having a predetermined value k ′ and the first value K is present in the table data, and A communication method comprising: a seventh step of setting a hash value of a predetermined value k ′ to the first value K. The management device generates a first hash value r ′ _{i + 3} based on the first secret data r _{i + 2} received in the third step and the predetermined value k ′ specified in the fifth step. And an eighth step of transmitting this to the tag;
The tag generates a second hash value r _{i + 3} based on the first secret data r _{i + 2} generated in the third step and the second secret data k _j, and the second On the condition that the hash value r _{i + 3} matches the first hash value r ′ _{i + 3} received in the eighth step, the hash value of the second secret data k _j is updated to the second value after the update. The communication method according to claim 1, further comprising: a ninth step of setting as secret data k _{j + 1} . A communication system having a tag, a reader and a management device,
The reader sends a random number s to the tag;
The tag transmits a hash value obtained by using the first secret data r _i and the second secret data k _j as arguments to the management device via the reader as _first secret data r _{i + 1} ,
The tag generates first secret data r _{i + 2} based on the received random number s and the generated first secret data r _{i + 1,} and transmits this to the management device via the reader And
The reader sends the random number s and the received first secret data r _{i + 2} to the management device;
A hash value obtained by the management device based on the received first secret data r _{i + 1} , the received random number s, and a predetermined value k ′ is the first secret data r _{i + 2} Identifying the predetermined value k ′
The management device refers to the table data indicating the identification data, the first value K, and the second value Klast in association with the identification data of a plurality of tags, and the specified predetermined value k ′ and the specified data Search for an entry that matches the first value K or the second value Klast;
The management device copies the first value K to the second value Klast when an entry having a predetermined value k ′ and the first value K is present in the table data, and A communication system that sets a hash value of a predetermined value k ′ to the first value K. A communication method executed by a communication device that communicates with a tag via a reader,
A first step of receiving from the tag via the reader the first secret data r _{i + 1} that is a hash value generated by the tag using the first secret data r _i and the second secret data k _j as arguments. When,
A second step of receiving, from the tag, the first secret data r _{i + 2} generated based on the random number s received by the tag from the reader and the first secret data r _{i + 1} ;
A third step of receiving the random number s and the first secret data r _{i + 2} from the reader;
A hash value obtained based on the first secret data r _{i + 1} received in the first step, the random number s received in the third step, and a predetermined value k ′ is the first secret data r _{i +} 1. A fourth step of identifying the predetermined value k ′ to be the secret data r _{i + 2} ;
With reference to the table data indicating the identification data, the first value K, and the second value Klast in association with the identification data of the plurality of tags, the predetermined value k ′ identified in the fourth step A fifth step of searching for an entry that matches the first value K or the second value Klast;
When the entry in which the predetermined value k ′ and the first value K match is present in the table data, the first value K is copied to the second value Klast, and the predetermined value k And a sixth step of setting the hash value of 'to the first value K. A communication device that communicates with a tag via a reader,
The first secret data r _{i + 1} , which is a hash value generated by the tag with the first secret data r _i and the second secret data k _j as arguments, is received from the tag via the reader, and the tag First secret data r _{i + 2} generated based on the random number s received from the reader and the first secret data r _{i + 1} is received from the tag via the reader, and the random number s and the first secret data are received. An interface for receiving data r _{i + 2} from the reader;
A memory for storing table data indicating the identification data, the first value K, and the second value Klast in association with the identification data of the plurality of tags;
The hash value obtained based on the first secret data r _{i + 1} received by the interface, the random number s, and the predetermined value k ′ is the predetermined value k that becomes the first secret data r _{i + 2.} ′ Is identified, and the table data is referenced to search for an entry where the identified predetermined value k ′ matches the first value K or the second value Klast, and the predetermined value k ′ When an entry that matches the first value K exists in the table data, the first value K is copied to a second value Klast, and the hash value of the predetermined value k ′ is copied to the second value Klast. And a processing circuit that sets the value K to 1. A program executed by a communication device that communicates with a tag via a reader,
A first procedure for receiving _first secret data r _{i + 1} , which is a hash value generated by the tag, using the first secret data r _i and the second secret data k _j as arguments, via the reader. When,
A second procedure for receiving, from the tag, the first secret data r _{i + 2} generated based on the random number s received by the tag from the reader and the first secret data r _{i + 1} ;
A third procedure for receiving the random number s and the first secret data r _{i + 2} from the reader;
A hash value obtained on the basis of the first secret data r _{i + 1} received in the first procedure, the random number s received in the third procedure, and a predetermined value k ′ is the first secret data r _{i +} 1. A fourth procedure for specifying the predetermined value k ′ to be secret data r _{i + 2} ;
With reference to the table data indicating the identification data, the first value K, and the second value Klast in association with the identification data of the plurality of tags, the predetermined value k ′ specified in the fourth procedure and A fifth procedure for searching for an entry that matches the first value K or the second value Klast;
When the entry in which the predetermined value k ′ and the first value K match is present in the table data, the first value K is copied to the second value Klast, and the predetermined value k A program for causing the communication apparatus to execute a sixth procedure for setting a hash value of 'to the first value K.

Images