JP7423293B2 - Authentication device, authenticated device, authentication method, authenticated method, and computer program. - Google Patents

Description

The present invention relates to an authentication device, an authenticated device, an authentication method, an authenticated method, and a computer program using a challenge-response method.

A challenge-response authentication method is widely used as a means of determining whether a connected device is legitimate. The challenge-response authentication method first generates a response to a different challenge each time based on information known only to each other, according to rules agreed upon by both parties. This method authenticates the device by verifying whether the generated response was generated in accordance with rules agreed upon by both parties. Many devices that implement device authentication using challenge-response authentication have limited resources. In such devices with limited resources, it is common to use a common key cryptosystem that can be implemented with a relatively lightweight circuit scale. AES (Non-Patent Document 1) has been determined as a standard as a common key cryptosystem and is widely used. As long as the confidentiality of the encryption key is ensured, the common key cryptosystem has been proven to be cryptographically safe and is extremely difficult to decipher.

However, recently, a method called a side channel attack has been researched and proposed, which uses statistics to estimate the encryption key that is the basis of cryptographic security. This research proposed a technology that estimates and derives cryptographic keys by measuring side channel information leaking from circuits, such as power consumption and electromagnetic waves during device operation, and analyzing it along with input and output to cryptographic circuits. ing. These methods pose a risk of being relatively easy to implement because an attacker can attack by simply acquiring side channel information without destroying the device, and countermeasures are required in cryptographic processing circuits and programs. .

A side channel attack is a method of estimating a key by correlating input data (or output data) with the obtained power consumption. A differential power analysis method called DPA (Differential Power Analysis) has been proposed as one of the typical attack methods. The DPA method focuses on the correlation between the estimated key, the input/output to the cryptographic processing circuit, and the side channel information such as power consumption obtained through measurement, and calculates the correlation statistically using multiple pieces of acquired data. The key is identified through scientific processing.

Attack methods such as fault injection attacks have also been proposed, in which an error is generated in the internal processing by applying unexpected stimuli to the device, such as applying an unspecified voltage, clock, laser, or electromagnetic wave irradiation. ing.

Fault injection attacks aim to inject a fault into a conditional branch of a success/failure judgment, causing the judgment to be skipped and authenticated as legitimate, or using both incorrect processing results and normal processing results obtained as a result of fault injection as clues. This is an attack that steals encryption keys.

Hereinafter, a side channel attack will be described as an example of an attack to steal an encryption key, but this is merely an example and is not limited to this attack.

Patent No. 6441615 Patent No. 6365076

FIPS 197, Advanced Encryption Standard (AES)

In challenge-response authentication, challenges and responses are exchanged via communication channels between devices, so they are easily intercepted and it is relatively easy to obtain input and output data. In addition to this, by acquiring the power consumption of the processing circuit, side channel attacks are possible, making it an easy target for attacks.

Additionally, in devices that store keys as fixed keys in the device, if the key is identified through a side-channel attack, the secret held by both parties in challenge-response authentication may be known to a third party. As a result, a non-genuine device will be created.
Therefore, as countermeasures against DPA, a method of making power consumption uniform (Patent Document 1) and a method of concealing the power consumption of cryptographic operations with the power consumption of other processes (Patent Document 2) have been proposed. However, the method of Patent Document 1 limits input options in order to equalize power consumption, and is not suitable for challenge-response authentication. Further, the method described in Patent Document 2 requires a plurality of cryptographic processing circuits, which increases the circuit scale, making it difficult to apply to devices with limited resources.

An object of the present invention is to achieve both improvement in side-channel attack resistance and reduction in circuit scale in challenge-response authentication.

The present invention has been made in view of the above-mentioned problems, and is an authentication device used in challenge-response authentication, which includes a generation means for generating data of a plurality of challenges, and a data of the plurality of challenges to be authenticated. a sending means for transmitting data to a plurality of responses; a receiving means for receiving data of a plurality of responses from the authenticated device; a rule specifying a change in the input order and response order of the cryptographic processing of the plurality of challenge data ; and a plurality of rules. The present invention is characterized by comprising an authentication means for performing authentication processing of the authentication target device based on response data.

According to the present invention, in challenge-response authentication, it is possible to both improve resistance to side channel attacks and reduce circuit scale.

1 is a diagram showing the configuration of Embodiment 1. FIG. 3 is a diagram showing a flowchart in Embodiment 1. FIG. FIG. 3 is a diagram showing an example of rules used in challenge-response authentication. FIG. 3 is a diagram showing data observed by an attacker.

(Embodiment 1)
Hereinafter, preferred embodiments of the present invention will be described in detail with reference to the drawings. Note that the following embodiments are merely illustrative, and are not intended to limit the scope of the present invention.

FIG. 1 is a block diagram showing the configuration of a challenge-response authentication device according to a first embodiment. The challenge-response authentication device 1 includes an authentication device 10 and a device to be authenticated 20. The authentication device 10 is connected so that the authentication device 20 can receive a challenge sent by the authentication device 10, and is also connected so that the authentication device 10 can receive a response sent from the authentication device 20. The authentication device 10 authenticates whether the authentication device 20 is a legitimate device by verifying the response generated by the authentication device 20 in response to the challenge sent by itself, and notifies the higher-level system of the authentication result. do.

Next, the configurations of the authentication device 10 and the device to be authenticated 20 will be explained. The authentication device 10 includes a rule storage means 100, a challenge storage means 101, a challenge generation means 102, a challenge transmission means 103, a response reception means 104, a response storage means 105, a verification means 106, and a key storage means 107. The authenticated device 20 includes a rule storage means 200, a challenge storage means 201, a challenge reception means 202, a response storage means 203, a response transmission means 204, a response generation means 205, and a key storage means 206. Common rules shared in advance are stored in the rule storage means 100 of the authentication device 10 and the rule storage means 200 of the authenticated device 20. Information necessary to generate a response is shared, such as the algorithm used, the input order for cryptographic challenge processing, and response transmission rules. In this embodiment, the description will be made using AES (Advanced Encryption Standard), which is widely used as a common key encryption method, but other algorithms may be used. The response generation rule 3 is held in the rule storage means 100 of the authentication device 10 and the rule storage means 200 of the authenticated device 20. The rule storage means 100 and the rule storage means 200 need to be protected with the same security as a key, and are preferably stored in a secure storage or the like so that an attacker cannot access them. Writing of the initial response generation rule 3 is achieved by writing the response generation rule 3 at a factory or the like when the product is shipped. The response generation rules 3 may be rewritable or non-rewritable, and it is safer if a protocol can be constructed and updated to safely update the rules agreed upon in advance.

Next, a typical flow of authentication processing in the challenge-response authentication device 1 will be explained. In the authentication device 10, first, a challenge CHn is generated by the challenge generating means 102. The size of the challenge CHn needs to be an integral multiple of the AES block length. Subsequently, the generated challenge CHn is transmitted to the authenticated device 20 via the challenge transmitting means 103. Subsequently, the authenticated device 20 receives the challenge CHn transmitted from the authentication device 10 using the challenge receiving means 202 . Subsequently, the received challenge CHn is stored in the challenge storage means 201. The response generation means 205 generates a response RSm according to the challenge stored in the challenge storage means 201 and the response generation rule 3 stored in the rule storage means 200. Here, the key used for response generation is acquired from the key storage means 206 as needed. The generated response RSm is stored in the response storage means 203. Subsequently, it is transmitted to the authentication device 10 via the response transmission means 204 as a response RSm. Subsequently, the authentication device 10 receives the response RSm transmitted from the device to be authenticated 20 using the response receiving means 104 . Subsequently, the verification means 106 uses the received response RSm and challenge CHn to verify whether they match the expected value generated according to the rules stored in the rule storage means 100. If a match is confirmed as a result of the verification by the verification means 106, the device to be authenticated 20 determines that it is a legitimate device and notifies the higher-level system that the authentication has been successful. On the other hand, if no match is confirmed as a result of the verification by the verification means 106, it is determined that the device to be authenticated 20 is an unauthorized device, and the higher-level system is notified that the authentication has failed.

Next, a challenge-response authentication flow between the authenticating device 10 and the authenticated device 20 in the first embodiment will be described using FIG. 2. The authentication device 10 assigns 0 to the counter n in S100. Subsequently, a challenge CHn is generated in S101. Subsequently, in S102, a challenge CHn is transmitted to the authenticated device 20, and a counter n is incremented by one. The authentication device 10 obtains the number N of challenge CHn to be transmitted in advance from the rule storage means 100, and compares it with the number N of challenge CHn to be transmitted in S103. As a result of the comparison, if the counter n is less than N, the process returns to S101 and the step of transmitting the challenge CHn is repeated. If the conditions are met, preparations are made to receive a response and 0 is assigned to the counter m in S104. The authenticated device 20 assigns 0 to the counter n in S200. In S201, a challenge CHn is received from the authentication device 10. Subsequently, in S202, the challenge CHn is stored in the challenge storage means 201, and the counter n is incremented by one. Subsequently, in S203, the number n of received challenges is compared with the number N of challenges CHn transmitted from the authentication device 10, acquired in advance from the rule storage means 200. As a result of the comparison, if the counter n is less than N, the process returns to S201 and the step of receiving the challenge CHn is repeated. If the conditions are met, preparations are made to receive a response and 0 is assigned to the counter m in S204. Subsequently, in S205, a response RSm is generated, stored in the response storage means 203, and the counter m is incremented by one. The response generated here is generated in accordance with the algorithm described in response generation rule 3, which is determined in advance and is stored in the rule storage means 200. Response generation may be performed serially using one processing circuit, or may be performed in parallel if there are multiple processing circuits. In S206, the authenticated device compares the number M of transmitted responses stored in the rule storage means 200 and the number m of generated responses, and if m is less than M, repeats the response generation step S205. If the conditions are met, the response order stored in the response storage means 203 is controlled and rearranged in accordance with the response transmission rule stored in the rule storage means 200 in S207. In addition, here, in order to simplify the explanation, it is described that the order stored in the response storage means 203 is changed, but it may be managed using an index or the like, or may be controlled using an address obtained when a response is generated. The replacement method does not matter. Subsequently, in S208, 0 is assigned to the counter m, and in S209, the response RSm is transmitted to the authentication device, and the counter m is incremented by 1. In S210, the number M of transmitted responses stored in the rule storage means 200 is compared with the number m of transmitted responses, and if m is less than M, response transmission S209 is repeated. Here, the processing from S205 to S210 will be explained in more detail using the reference example of the rule shown in FIG. 3(a). This is an example using AES 128-bit encryption, and in this embodiment, the number N of challenge transmissions and the number M of response transmissions indicate the number of blocks, where one block is 128 bits, which is the block length of the common cipher AES. Six blocks are sent and received as a challenge, and three blocks are sent and received as a response. In S205, a rule is generated using the response generation rule 30 described in the rule. The response generation rule 30 further includes a usage challenge 300, a cryptographic processing input order 301, and a response order 302. The explanation will be given assuming that n of the cryptographic process Encn is the cryptographic process order. The challenge CH2 is used as an input to the cryptographic processing Enc3, and is transmitted as the response RS1. Next, the challenge CH3 is used as an input in the encryption process Enc2, and the encrypted result is used as a response RS3, and the challenge 6 is used as an input in the encryption process Enc1 and transmitted as a response RS2.

Subsequently, in S105, the authentication device 10 receives a response RSm from the device to be authenticated 20. Subsequently, in S106, the received response RSm is stored in the response storage means 105, and the counter m is incremented by one. Next, in S107, the number m of received responses is compared with the number M of transmitted responses stored in the rule storage means 100, and if m is less than M, response reception S105 is repeatedly performed. If the conditions are met, in S108 the verification means 106 verifies whether all the received responses RSm are responses generated according to the challenge CHn and the prearranged rules, including the response order. Here, the rules determined in advance are acquired from the rule storage means 100, and keys are acquired from the key storage means 107 as needed. If a match is confirmed as a result of the verification in S108, the device to be authenticated 20 is determined to be a legitimate device, and the system is notified of successful authentication in S109. On the other hand, if no match is confirmed as a result of the verification in S108, the device to be authenticated is determined to be an unauthorized device, and the system is notified in S110 that the authentication has failed.

The effects of the invention according to this proposal will be explained.

In conventional examples, in challenge-response authentication, input/output data (challenge CHn, response RSm) is exchanged via a communication path, and side channels such as power consumption during encryption processing can be obtained by an attacker. Met. In other words, it was not resistant to side channel attacks. Therefore, it was vulnerable to attacks on encryption key estimation. Further, the encryption key is often written in a fixed manner in the device, and once the key is stolen, it becomes possible to disguise the device to be authenticated and authenticate an unauthorized device. Furthermore, if the same shared key is used by multiple devices, the impact will extend to the multiple devices as well. On the other hand, in the present application, the order of the challenge CHn, the response RSm, and the cryptographic processing executed using them is changed in the series of challenges and responses authentication. This makes it difficult to map input/output and waveforms, increasing the difficulty of key analysis and increasing resistance to side channel attacks. Here, the effect will be explained in more detail using FIG. 4 as an example and comparing it with information that an attacker can observe. The attacker cannot obtain connection information in the range 40 that cannot be observed by the attacker. This information is equivalent to the content described in Rule 3, which was determined in advance. The attacker attempts to analyze challenge CH1 (400) to challenge CH6 (405) and power waveform 1 (440) to power waveform 3 (442) that can be observed as side channels. However, power waveform 1 (440) is a waveform generated from challenge CH6 (405), and this correspondence cannot be observed, making side channel attacks difficult. Responses RS1 (430) to RS3 (432) are similarly difficult to analyze because they cannot be correlated with the power waveforms 440 to 442.

Additionally, it is highly resistant to fault injection attacks because multiple challenges are used for authentication. In order to further increase the resistance, it is better to provide a means to update the rules agreed upon in advance. In this way, the present invention can provide resistance to side channel attacks.

(Embodiment 2)
Embodiment 2 will be described below with reference to the drawings. Regarding the drawings used to explain this embodiment, parts having the same functions are given the same reference numerals, and the explanation will be omitted.
Note that the following embodiments are merely illustrative, and are not intended to limit the scope of the present invention.

Embodiment 2 will be described using FIG. 3(b). Here, the processing from S205 to S210 will be explained in more detail using the reference example of the rule shown in FIG. 3(b). This is an example using AES 128-bit encryption, and in this embodiment, the number N of challenge transmissions and the number M of response transmissions indicate the number of 128-bit blocks, which is the block length of the common cipher AES. Six blocks are sent and received as a challenge, and three blocks are sent and received as a response. In S205, a rule is generated using the response generation rule 30 described in the rule. The response generation rule 30 further includes a usage challenge 300, a cryptographic processing input order 301, and a response order 302. The explanation will be given assuming that n of the cryptographic process Encn is the cryptographic process order. In this embodiment, dummy303 is used in the usage challenge in addition to that in the first embodiment. The challenge CH2 is used as an input to the cryptographic processing Enc3, and is transmitted as the response RS1. Next, the challenge CH3 is used as an input in the encryption process Enc4, and the encrypted result is used as a response RS3, and the challenge 6 is used as an input in the encryption process Enc1 and transmitted as a response RS2. Here, the cryptographic process is performed using the input of dummy as the cryptographic process Enc2, and the output of this cryptographic process is not used for the response. This makes it more difficult for an attacker to correlate the challenge, the observed power waveform, and the response by adding an extra power waveform for cryptographic processing. In particular, not all challenges are used, and cryptographic processing for unexpected data is inserted, resulting in a configuration with greater resistance to side channel attacks than in the first embodiment.

(Other examples)
The present invention provides a system or device with a program that implements one or more of the functions of the embodiments described above via a network or a storage medium, and one or more processors in the computer of the system or device reads and executes the program. This can also be achieved by processing. It can also be realized by a circuit (for example, ASIC) that realizes one or more functions.

1 Challenge-Response Authentication Device 10 Authentication Device 20 Authenticated Device 100 Rule Storage Means 200 Rule Storage Means

Claims (12)

An authentication device used in challenge-response authentication,
a generation means for generating data for a plurality of challenges;
Transmitting means for transmitting data of the plurality of challenges to the authenticated device;
receiving means for receiving data of a plurality of responses from the authenticated device;
The method further comprises: an authentication means that performs authentication processing of the authenticated device based on a rule that specifies the replacement of the input order of the encryption processing of the data of the plurality of challenges and the order of the responses, and data of the plurality of responses. Authentication device. The authentication device according to claim 1, wherein the rule includes making the number of data of the plurality of challenges different from the number of data of the plurality of responses. The authentication device according to claim 1 or 2, further comprising a secure storage for storing the rules. An authenticated device used in challenge-response authentication,
receiving means for receiving data of a plurality of challenges from the authentication device;
an encryption means for encrypting the data of the plurality of challenges based on a rule that specifies the exchange of the input order and the response order of the encryption processing of the data of the plurality of challenges;
The authentication device performs authentication processing of the authenticated device using the encryption result of the encryption means based on a rule that specifies the exchange of the input order of the encryption processing of the data of the plurality of challenges and the response order. 1. A device to be authenticated, comprising: a transmitting means for transmitting data of a plurality of responses to the authentication device in order to perform the authentication. 5. The authenticated device according to claim 4, wherein the rule includes making the number of data of the plurality of challenges different from the number of data of the plurality of responses. The authenticated device according to claim 4 or 5, further comprising a secure storage for storing the rules. The authenticated device according to any one of claims 4 to 6, wherein the encryption means encrypts the data of the plurality of challenges using common key encryption. Any one of claims 4 to 7, wherein the rule includes encrypting data that has not been transmitted from the authentication device as challenge data using the encryption means. The certified device described in section. An authentication method used in challenge-response authentication,
a generation step in which the generation means generates data for a plurality of challenges;
a transmitting step in which the transmitting means transmits data of the plurality of challenges to the authenticated device;
a receiving step in which the receiving means receives data of a plurality of responses from the authenticated device;
The authentication means has an authentication step of performing authentication processing of the authenticated device based on a rule that specifies the exchange of the input order of the cryptographic processing of the data of the plurality of challenges and the order of the responses, and the data of the plurality of responses . An authentication method characterized by: An authenticated method used in challenge-response authentication,
a receiving step in which the receiving means receives data of a plurality of challenges from the authentication device;
an encryption step in which the encryption means encrypts the data of the plurality of challenges based on a rule that specifies the exchange of the input order of the encryption processing of the data of the plurality of challenges and the order of the responses;
The transmitting means uses the encryption result of the encryption step to cause the authentication device to authenticate the authentication device based on a rule that specifies the exchange of the input order of the encryption processing of the data of the plurality of challenges and the order of the responses. An authentication method comprising the step of transmitting data of a plurality of responses to the authentication device in order to perform authentication processing . computer,
An authentication device used in challenge-response authentication,
a generation means for generating data for a plurality of challenges;
Transmitting means for transmitting data of the plurality of challenges to the authenticated device;
receiving means for receiving data of a plurality of responses from the authenticated device;
The method further comprises: an authentication means that performs authentication processing of the authenticated device based on a rule that specifies the replacement of the input order of the encryption processing of the data of the plurality of challenges and the order of the responses, and data of the plurality of responses. A program that functions as an authentication device. computer,
An authenticated device used in challenge-response authentication,
receiving means for receiving data of a plurality of challenges from the authentication device;
an encryption means for encrypting the data of the plurality of challenges based on a rule that specifies the exchange of the input order and the response order of the encryption processing of the data of the plurality of challenges;
The authentication device performs authentication processing of the authenticated device using the encryption result of the encryption means based on a rule that specifies the exchange of the input order of the encryption processing of the data of the plurality of challenges and the response order. 1. A program for functioning as an authenticated device, characterized in that the program has a transmitting means for transmitting data of a plurality of responses to the authenticating device in order to perform the authentication.

Images