JP7213724B2 - Authentication method, authentication system, authenticated device and authenticating device - Google Patents

Description

The present invention relates to an authentication method, an authentication system, an authenticated device and an authenticating device.

Printers can maintain consistent image quality with proper maintenance. Maintenance includes replacement of consumables and periodic replacement parts. However, if the consumables or replacement parts are not genuine, the printer may malfunction. Non-genuine products are, for example, consumables and replacement parts for different types of printers. User convenience is improved by adding optional devices such as a feeder and a paper discharge device to the printer. If the optional device is not genuine, the printer may still malfunction. Therefore, it is important to determine whether the device connected to the printer is genuine. Japanese Patent Application Laid-Open No. 2002-200000 describes verifying whether the process cartridge is genuine by authenticating the process cartridge mounted in the image forming apparatus.

JP 2017-143437 A

In order to determine whether or not a device attached to an image forming apparatus is genuine, there are a method using common key cryptography, a method using an encrypted hash function, and the like. In particular, a challenge-response authentication method using common key cryptography is widely used. The authentication device generates random number data (challenge) and transmits it to the device to be authenticated. The device to be authenticated encrypts the challenge with the common key, generates encrypted data (response), and returns it to the authentication device. The authentication device authenticates the device to be authenticated based on whether the received response matches the response obtained by encrypting the challenge with the common key. Thus, the challenge-response authentication method is based on the premise that the authenticating device and the authenticated device have a common key. It is important that an attacker cannot steal the common key. The authenticating device and the device to be authenticated hold a common key using a high-security tamper-resistant chip such as a security LSI, and perform authentication processing. However, if the common key is analyzed and exposed by either the authenticating device or the device to be authenticated, the genuine product can be duplicated. SUMMARY OF THE INVENTION Accordingly, an object of the present invention is to make it more difficult to forge a device to be authenticated.

The present invention, for example,
An authentication method for authenticating a device to be authenticated by an authentication device,
the device to be authenticated transmitting identification information of a key table held by the device to be authenticated to the authentication device;
the authenticator receiving identification information of the key table from the authenticated device;
the authentication device transmitting identification information in an authentication table held by the authentication device to the device to be authenticated;
the authenticated device receiving identification information from the authentication table;
The authentication device transmits to the device to be authenticated a challenge corresponding to a pair of the identification information of the key table received from the device to be authenticated and the identification information of the authentication table held by the authentication device. and
the authenticated device receiving the challenge from the authenticator;
The device to be authenticated acquires from the key table a key corresponding to a pair of identification information in a key table held by the device to be authenticated and identification information in an authentication table held by the authentication device. When,
the authenticated device generating a response from the key obtained from the key table and the challenge;
the authenticated device transmitting the response to the authenticating device;
the authenticating device receiving the response from the authenticated device;
The authentication device acquiring from the authentication table a response corresponding to a pair of the identification information of the key table received from the device to be authenticated and the identification information of the authentication table held by the authentication device. When,
An authentication method is provided, wherein the authentication device authenticates the device to be authenticated based on the response received from the device to be authenticated and the response obtained from the authentication table.

According to the present invention, it becomes possible to make it more difficult to forge a device to be authenticated.

FIG. 1 shows an image forming apparatus as an example of an authentication system; FIG. 1 shows an image forming apparatus as an example of an authentication system; Diagram explaining the chip to be certified and the engine controller Diagram showing key table and authentication table Diagram explaining how to generate a key Diagram explaining how to generate the key table and authentication table Sequence diagram showing the authentication procedure Flowchart explaining the authentication method A diagram showing a key table and an authentication table according to the second embodiment. Flowchart explaining the authentication method Flowchart explaining the authentication method

Embodiments are described in detail below with reference to the accompanying drawings. It should be noted that the following embodiments are not intended to limit the invention according to the scope of claims. Although multiple features are described in the embodiments, not all of these multiple features are essential to the invention, and multiple features may be combined arbitrarily. Furthermore, in the accompanying drawings, the same or similar components are denoted by the same reference numerals, and redundant description is omitted.

<Example 1>
[Image forming apparatus (authentication system)]
FIG. 1A shows a schematic configuration of an image forming apparatus 100, an optional paper feeding device 300, and an optional paper discharging device 400. As shown in FIG. The image forming apparatus 100 is a printer, copier, multifunction machine, or the like that forms an image on a sheet according to an electrophotographic process. Sheets on a sheet stacking unit 11 are supplied by a paper feeding unit 12 and conveyed by conveying rollers 13 and 14 . The conveyed sheet is conveyed to the transfer nip portion formed by the transfer roller 20 and the photosensitive drum 18, and the toner image formed on the photosensitive drum 18 is transferred onto the sheet. The surface of the photosensitive drum 108 is uniformly charged by the charging roller 17, and then irradiated with light from the exposure unit 21 to form an electrostatic latent image. Then, the formed electrostatic latent image is developed with toner by a developing roller to form a toner image. After the image transferred to the sheet is fixed by the fixing device 200 , the sheet is discharged outside the apparatus conveyed by the conveying roller 26 and the discharging roller 27 . Here, the process cartridge 102 is configured by integrating the photosensitive drum 108 , the charging roller 17 , the developing roller 16 and the cleaner 18 , and is a replacement part that can be attached to and detached from the image forming apparatus 100 . Further, the fixing device 200 is also a replacement part that can be attached to and detached from the image forming apparatus 100 .

The option paper feeding device 300 is a device provided to increase the stacking amount of sheets, and is detachable from the image forming apparatus 100 . The optional paper discharge device 400 is a device for sorting and discharging sheets on which images are formed, and is detachable from the image forming apparatus.

FIG. 1B shows a configuration in which the process cartridge 102 is provided with an authentication chip in the configuration described in FIG. 1A. The engine controller 101 has a control device 105 , an authentication chip 106 and a communication circuit 104 . The control device 105 is a controller that centrally controls the entire image forming apparatus 100 . The authentication chip 106 is a semiconductor integrated circuit that authenticates the chip 103 to be authenticated. A communication circuit 104 is a communication circuit for communicating with the process cartridge 102 . A process cartridge 102 is a replacement part that can be attached to and detached from the main body of the image forming apparatus 100, and includes a photosensitive drum and a developing unit for supplying toner to the photosensitive drum. The process cartridge 102 has a chip 103 to be authenticated. The chip to be authenticated 103 is a tamper-resistant chip. When the controller 105 detects that the process cartridge 102 is attached using the attachment sensor 209, the controller 105 instructs the authentication chip 106 for authentication. Control device 105 transmits the challenge generated by authentication chip 106 to authenticated chip 103 via communication circuit 104 . The control device 105 transfers the response received from the chip to be authenticated 103 via the communication circuit 104 to the authentication chip 106 . Control device 105 receives the authentication result from authentication chip 106 . The to-be-authenticated chip 103 may be incorporated into consumables or replacement parts (fixing device 200) of the image forming apparatus 100, or optional devices (optional paper feeding device 300, optional paper discharging device 400, etc.). FIG. 2 shows the internal configuration of the engine controller 101 and the chip 103 to be authenticated. The authentication chip 106 has an input/output circuit 201a, a microcomputer 202a, a volatile memory 203a, a comparator 204 and a nonvolatile memory 205a. The input/output circuit 201a functions as a communication circuit that receives commands and the like output from the control device 105 and transfers them to the microcomputer 202a. Further, the input/output circuit 201a transfers the response data from the microcomputer 202a to the control device 105. FIG. The microcomputer 202a is a processor circuit for executing internal processing according to commands received from the control device 105. FIG. A program for controlling the authentication chip 106 and an authentication table 208 are written in the nonvolatile memory 205a. The volatile memory 203a is a memory that temporarily stores data when the microcomputer 202a performs data processing. The comparator 204 is a circuit that compares two input data, determines whether the two data are equal or different, and outputs the determination result.

The input/output circuit 201b is a circuit electrically connected to the communication circuit 104 when the process cartridge 102 is attached to the image forming apparatus 100 main body. The input/output circuit 201b receives commands and challenges transmitted from the control device 105 via the communication circuit 104 and outputs them to the microcomputer 202b. The input/output circuit 201b receives the response output from the microcomputer 202b via the communication circuit 104 and outputs it to the microcomputer 202a. The microcomputer 202b is a processor circuit for executing internal processing according to commands from the control device 105. FIG. A program for controlling the chip to be authenticated 103 and a key table 207 are written in the nonvolatile memory 205b. The volatile memory 203b is a memory for temporarily storing data when the microcomputer 202b executes data processing. The cryptographic circuit 206b is a circuit that executes cryptographic calculations for authentication processing according to commands from the microcomputer 202b.

The starting point of authentication processing is the control device 105 . Control device 105 outputs various commands necessary for authentication processing to authentication chip 106 and to-be-authenticated chip 103 . The authentication chip 106 and the chip to be authenticated 103 each execute processing according to the command, and return the execution result to the control device 105 as a response to the command.

[Key table and authentication table]
FIG. 3A shows key tables 207-1 to 207-n holding keys used for authentication. One of the key tables 207-1 to 207-n is written in the non-volatile memory 205b of the chip 103 to be authenticated. FIG. 3B shows authentication tables 208-1 to 208-m. One authentication table 208 out of the authentication tables 208-1 to 208-m is written in the nonvolatile memory 205a of the authentication chip 106. FIG.

As shown in FIG. 3A, there are a plurality (finite number) of key tables 207, and each key table 207 is added with identification information (key table ID). Similarly, there are a plurality (finite number) of authentication tables 208, and each authentication table 208 is added with identification information (authentication table ID). Here, the number of key table IDs is n. The number of authentication table IDs is m. In one key table 207, m keys that are the same as the number of authentication table IDs are written in association with the authentication table IDs. The key written in each key table 207 differs for each key table ID. In other words, the key written in the key table 207 to which a certain key table ID is added is different from the key written in the key table 207 to which another key table ID is added.

In FIG. 3A, the variable i indicating the key table ID takes any value from 1 to n. Also, the variable j indicating the authentication table ID takes any value from 1 to m. Among the plurality of keys written in the key table 207-i with key table ID=i, the key corresponding to authentication table ID=j is represented as key (i, j).

In the authentication table 208, the same number of n challenge-response pairs as in the key table 207 are written in association with the key table ID. The challenge-response pairs written are different for each authentication table 208 . The pairs written to one authentication table 208 are different from the pairs written to another authentication table 208 . A plurality of challenges and responses written in the authentication table 208-j with the authentication table ID=j, and the challenges and responses corresponding to the key table ID=i are challenge (i, j) and response (i, j), respectively. is expressed as Challenge (i,j) and response (i,j) form a pair.

Generate key, challenge and response
FIG. 4 is a diagram for explaining a key generation method. A random number generator 401 generates keys (1, 1) to (n, m). Random number generator 401 is a circuit external to the authentication system. In FIG. 4, rows correspond to authentication table IDs and columns correspond to key table IDs. Such a key group may be referred to as key matrix 400 . Key matrix 400 holds n×m keys.

FIG. 5 is a diagram illustrating a method of generating a challenge-response pair. As shown in FIG. 5, m keys held in columns corresponding to key table IDs are stored in the key table 207 to which key table IDs are assigned. For example, m keys (i, 1) to (i, m) held in the i-th column are stored in the key table 207-i assigned i as the key table ID.

In order to create the authentication table 208-j with the authentication table ID=j, the keys (1, j) to (n, j) held in the j-th row in the key matrix are acquired one by one and encrypted. supplied to circuit 206c. The random number generator 501 generates challenges (1, j) to (n, j) and supplies them one by one to the encryption circuit 206c. Cryptographic circuit 206c generates response (i, j) using key (i, j) and challenge (i, j). i takes a value from 1 to n. As a result, responses (1, j) to (n, j) are generated. As shown in FIG. 5, authentication table 208-j stores pairs of challenges (i, j) and responses (i, j). Eventually, n pairs are written to authentication table 208-j.

The encryption circuit 206c is an encryption circuit that performs the same processing as the encryption circuit 206b provided in the chip 103 to be authenticated. If the same key and the same challenge are input to the encryption circuit 206b and the encryption circuit 206c, respectively, the encryption circuit 206b and the encryption circuit 206c output the same output data (response).

The suffixes i and j of the challenge and response indicate the key table ID and authentication table ID corresponding to the key used to generate the response, respectively. The same authentication table ID may be assigned to multiple authentication tables. In this case, the random number generator 501 may generate different challenges for multiple authentication tables assigned the same authentication table ID. For example, the challenge (1,j) for one authentication table and the challenge (1,j) for another authentication table may be different. This is useful for making the authentication table 208 different for each authentication chip 106 . For example, all authentication chips 106 can each hold a different authentication table 208 . Also, while limiting the number of authentication table IDs, it is possible to write different pairs in all existing authentication tables 208 . On the other hand, multiple key tables 207 with the same key table ID must all have the same key.

The cryptographic circuits 206b and 206c calculate responses using, for example, an encrypted hash function or a common key cryptographic function. As the cryptographic hash function, for example, SHA-256 standardized by NIST_FIPS_PUB 180-4 may be adopted.
Response (i, j) = SHA-256 (key (i, j)|challenge (i, j)) (1)
Here, "key (i, j)|challenge (i, j)" means concatenating key (i, j) and challenge (i, j). That is, "|" is the concatenation operator. As the common key encryption function, for example, AES standardized by NIST_FIPS_PUB 197 may be adopted.
Response (i, j) = AES (Key = key (i, j), Message = challenge (i, j)) (2)
The generated key table 207 is written in the non-volatile memory 205b of the chip 103 to be authenticated at the factory where the process cartridge 102 is manufactured. The generated authentication table 208 is written in the non-volatile memory 205 of the authentication chip 106 at the factory where the engine controller 101 is manufactured.

[Authentication sequence]
FIG. 6A is a sequence diagram regarding the authentication method. FIG. 7A is a flow chart showing an authentication method executed by the chip 103 to be authenticated. FIG. 7B is a flow chart showing the authentication method executed by the authentication chip 106. FIG. Here, the chip to be authenticated 103 holds a key table 207 to which i is assigned as the key table ID. Also, the authentication chip 106 holds an authentication table 208 to which j is given as an authentication table ID.

In Sq1, chip 103 to be authenticated transmits its own key table ID to authentication chip .
In S1, when the conditions for starting authentication are satisfied, the microcomputer 202b of the chip to be authenticated 103 reads the key table ID from the nonvolatile memory 205b and transmits the key table ID to the authentication chip 106 via the input/output circuit 201b. The authentication start condition is, for example, that the process cartridge 102 is electrically connected to the main body of the image forming apparatus 100, or that an authentication command is received from the authentication chip 106, or the like.
・At S11, the microcomputer 202a of the authentication chip 106 receives the key table ID from the chip to be authenticated 103 through the communication circuit 104, the control device 105 and the input/output circuit 201a.

In Sq2, the authentication chip 106 transmits its own authentication table ID to the chip 103 to be authenticated.
In S12, the microcomputer 202a of the authentication chip 106 reads the authentication table ID from the nonvolatile memory 205a and transmits the authentication table ID to the chip 103 to be authenticated through the input/output circuit 201a, the control device 105 and the communication circuit 104.
・At S2, the microcomputer 202b of the chip to be authenticated 103 receives the authentication table ID from the authentication chip 106. FIG.

In Sq3, the authenticating chip 106 sends a challenge (i, j) to the authenticated chip 103. FIG.
・At S13, the microcomputer 202a of the authentication chip 106 acquires the challenge (i, j) corresponding to the pair of the authentication table ID of the authentication chip 106 and the key table ID of the chip to be authenticated 103 from the authentication table 208 of the nonvolatile memory 205a. . Furthermore, the microcomputer 202a transmits the challenge (i, j) to the chip to be authenticated 103 through the input/output circuit 201a, the control device 105 and the communication circuit 104. FIG.
· In S3, the microcomputer 202b of the chip to be authenticated 103 receives the challenge (i, j) from the authentication chip .

In Sq4, the chip to be authenticated 103 transmits the response (i, j) corresponding to the challenge (i, j) to the authentication chip .
・At S4, the microcomputer 202b of the chip to be authenticated 103 acquires the key (i, j) corresponding to the pair of the authentication table ID of the authentication chip 106 and the key table ID of the chip to be authenticated 103 from the key table 207. Further, the microcomputer 202b supplies the key (i, j) and the challenge (i, j) to the cryptographic circuit 206b, causing the cryptographic circuit 206b to generate a response (i, j).
In S5, the microcomputer 202b transmits the response (i, j) generated by the encryption circuit 206b to the authentication chip 106 through the input/output circuit 201b.
· In S14, the microcomputer 202a of the authentication chip 106 receives the response (i, j) from the chip 103 to be authenticated.
In S15, the microcomputer 202a supplies the received response (i, j) and the response (i, j) obtained from the authentication table 208 to the comparator 204 to compare them.
In S16, the microcomputer 202a receives the comparison result from the comparator 204, creates an authentication result based on the comparison result, and outputs the authentication result to the control device 105. FIG. If the received response (i, j) and the response (i, j) acquired from the authentication table 208 do not match, the authentication result is authentication failure. On the other hand, if the received response (i, j) and the response (i, j) obtained from the authentication table 208 match, the authentication result is authentication success. If the authentication result is authentication failure, the control device 105 suspends the image forming process, and displays on the display unit of the image forming apparatus (not shown) to let the user decide whether to permit image formation. . If the authentication result is authentication success, the control device 105 permits the image forming apparatus 100 to form an image.

If the chip to be authenticated 103 is a genuine product, all the keys stored in the key table 207 of the nonvolatile memory 205b are correct. Therefore, the key (i,j) is also a correct key. The cryptographic circuit 206b has the same cryptographic algorithm as the cryptographic circuit 206c used to generate the authentication table 208. FIG. Therefore, the response (i, j) generated by the cryptographic circuit 206b and the response (i, j) generated by the cryptographic circuit 206c and held in the authentication table 208 match.

[Effect of attack]
A description will be given of the effects when the authentication chip 106 and the chip to be authenticated 103 are attacked by an analyst. When the attack target is the authentication chip 106, the authentication table 208 stored in the nonvolatile memory 205a is analyzed. In order to enable authentication with all authentication chips 106, it is necessary to analyze all responses written in all existing authentication chips 106. FIG. However, the authentication tables 208 written in the authentication chips 106 are all different for each authentication chip 106 . Therefore, it is practically difficult to collect all responses.

When the attack target is the authenticated chip 103, the key table 207 stored in the nonvolatile memory 205b is the analysis target. A plurality of keys corresponding to a plurality of authentication tables 208 are written in the nonvolatile memory 205b. For example, suppose key (i,j) is exposed to an attacker. In this case, the key (i,j) is valid only for the authentication chip 106 having the authentication table 208 with the authentication table ID=j.

As shown in FIG. 6A, after the chip to be authenticated 103 sends the key table ID to the authentication chip 106, the authentication chip 106 sends the authentication table ID and the challenge. Therefore, when the chip to be authenticated 103 transmits the key table ID to the authentication chip 106, the authentication table ID of the authentication chip 106 is still unknown. Therefore, in order to tamper with all authentication table IDs, an attacker needs to disclose all keys from one key table. A destructive attack, which is a marvelous analysis technique for tamper-resistant chips, may also be used. This is an attack that involves chip cutting and chip chipping. Therefore, exposing multiple keys before completely destroying the chip is much more difficult than exposing a single key.

As described above, according to the first embodiment, the difficulty of analyzing the authentication chip 106 and the chip to be authenticated 103 is higher than in the conventional art. In particular, the analysis of the authentication chip 106 is so difficult that it becomes virtually meaningless.

<Example 2>
The authentication system of the second embodiment is a more secure improvement of the authentication system of the first embodiment. In the second embodiment, descriptions common to the first embodiment will be omitted, and differences will be described in detail.

FIG. 6B is a sequence diagram showing the authentication method of the second embodiment. Although the challenge (i, j) was transmitted in Sq3 of FIG. 6A, the authentication chip 106 transmits the password to the authenticated chip 103 in addition to the challenge (i, j) in Sq3' of FIG. 6B. If the received password and the password held in the nonvolatile memory 205b match, the authenticated chip 103 generates a response (i, j) and transmits the response (i, j) in Sq4'. On the other hand, if the received password and the password held in the nonvolatile memory 205b do not match, the authenticated chip 103 does not generate a response (i, j) and transmits an error message in Sq4'. That is, the authentication process is canceled.

FIG. 8A shows the key table 207' of the second embodiment. FIG. 8B shows the authentication table 208' of the second embodiment. As compared to the key table 207 and authentication table 208 of Example 1, the key table 207' and authentication table 208' of Example 2 each have a password. A password is generated for each pair of key table ID and authentication table ID. In the authentication table 208'-j (j is an integer from 1 to m), there are a plurality of passwords corresponding to pairs of authentication table ID j and all key table IDs, integers from 1 to n. written. The password to be written differs for each pair of key table ID and authentication table ID. A password corresponding to a pair of key table ID and authentication table ID is also written in the key table 207'. That is, the password (i, j) held in the key table 207' matches the password (i, j) held in the authentication table 208'. The password is generated by a random number generator, for example, and written in advance in the key table 207' and the authentication table 208'. The authentication table 208 ′ is written into the non-volatile memory 205 a of the authentication chip 106 . The key table 207 ′ is written in the non-volatile memory 205 b of the chip 103 to be authenticated.

[Authentication processing in the chip to be authenticated]
FIG. 9 shows an authentication method executed by the chip 103 to be authenticated. S3 of the first embodiment is replaced with S6, S7, and S8 in the second embodiment.
· In S6, the microcomputer 202b of the chip to be authenticated 103 receives the challenge (i, j) and the password (i, j) from the authentication chip 106.
・At S7, the microcomputer 202b acquires the password (i, j) corresponding to the pair (i, j) of its own key table ID and the authentication table ID of the authentication chip 106 from the key table 207' of the nonvolatile memory 205b. . Further, the microcomputer 202b determines whether the password obtained from the key table 207' matches the received password (i, j). If both match, the microcomputer 202b proceeds to S4. That is, if these passwords match, a response is generated and sent. On the other hand, if the two do not match, the microcomputer 202b proceeds to S8 without generating a response.
· In S8, the microcomputer 202b transmits an error message to the authentication chip 106.

[Authentication processing by authentication chip]
FIG. 10 shows the authentication method executed by the authentication chip 106. FIG. S13 and S14 of the first embodiment are replaced with S17, S18 and S19 in the second embodiment.
・At S17, the microcomputer 202a of the authentication chip 106 stores the password (i, j) and the challenge (i, j) corresponding to the pair (i, j) of the received key table ID and its own authentication table ID in a nonvolatile manner. obtained from the key table 207' in the security memory 205b. Furthermore, the microcomputer 202a transmits the password (i, j) and the challenge (i, j) to the chip 103 to be authenticated.
· In S18, the microcomputer 202a receives a response (i, j) or an error message from the chip 103 to be authenticated.
· In S19, the microcomputer 202a determines whether or not the response (i, j) has been received from the chip 103 to be authenticated. When the response (i, j) is received, the microcomputer 202a advances to S15 and executes the comparison processing of the response (i, j). On the other hand, if an error message is received, the microcomputer 202a proceeds to S16 and outputs to the control device 105 an authentication result indicating authentication failure.

According to the second embodiment, since the password is added to the challenge, the security of the authentication system is further improved compared to the first embodiment. It is extremely difficult to statically read data stored in a tamper-resistant non-volatile memory on a chip. The existence of the password makes it more difficult to reveal the key through dynamic access to the authenticated chip 103 . This is because if the passwords do not match, no response is generated. Thus, in the second embodiment, the difficulty of analyzing the chip 103 to be authenticated is higher than in the first embodiment.

<Summary>
The to-be-authenticated chip 103 is an example of a to-be-authenticated device authenticated by the authenticating device. The nonvolatile memory 205 b is an example of a holding circuit (memory) that holds (stores) the key table 207 . The microcomputer 202b and the input/output circuit 201b are an example of a circuit (processor or communication circuit) that transmits identification information (eg, key table ID) of the key table held by the holding circuit to the authentication device. The microcomputer 202b and the input/output circuit 201b are an example of a circuit that receives identification information (eg, authentication table ID) of the authentication table held by the authentication device from the authentication device. The microcomputer 202b and the input/output circuit 201b are an example of a circuit that receives a challenge corresponding to a pair of identification information in the key table and identification information in the authentication table from the authentication device. The microcomputer 202b is an example of a circuit (processor) that acquires from the key table 207 a key corresponding to a pair of identification information of the key table and identification information of the authentication table. The encryption circuit 206b is an example of a circuit that generates a response from the key obtained from the key table 207 and the challenge received from the authentication device. The microcomputer 202b and the input/output circuit 201b are an example of a circuit that transmits a response to the authentication device. Thus, the identification information of the authentication table is transmitted after the identification information of the key table is transmitted. Therefore, the identification information of the authentication table is unknown when the identification information of the key table is transmitted. Therefore, an attacker must disclose all keys from one key table, making it more difficult than before to forge a device to be authenticated. Specifically, the authenticated device holds the key, but the verifier does not. Therefore, all keys are not leaked from the authentication device. Also, although the authenticating device holds the response, the device to be authenticated does not hold the response. Therefore, all responses are not leaked from the device to be authenticated. Therefore, counterfeiting the authenticated device will be more difficult than in the past.

The authentication chip 106 is an example of an authentication device that authenticates the device to be authenticated. The microcomputer 202a and the input/output circuit 201a are an example of a circuit that receives the identification information of the key table from the device to be authenticated. The nonvolatile memory 205a is an example of a holding circuit that holds an authentication table. The microcomputer 202a and the input/output circuit 201a are an example of a circuit that transmits the identification information of the authentication table held by the holding circuit to the device to be authenticated. The microcomputer 202a is an example of a circuit that acquires from the authentication table a challenge corresponding to a pair of the key table identification information received from the device to be authenticated and the authentication table identification information held by the holding circuit. The microcomputer 202a and the input/output circuit 201a are an example of a circuit that transmits the challenge acquired from the authentication table to the device to be authenticated. The microcomputer 202a and the input/output circuit 201a are an example of a circuit that receives a response to the challenge from the device to be authenticated. The microcomputer 202a is an example of a circuit that acquires from the authentication table a response corresponding to a pair of the identification information of the key table received from the device to be authenticated and the identification information of the authentication table held by the holding circuit. Comparator 204 is an example of a circuit that authenticates the device to be authenticated based on the response received from the device to be authenticated and the response obtained from the authentication table. Thus, the identification information of the authentication table is transmitted after the identification information of the key table is transmitted. Therefore, the identification information of the authentication table is unknown when the identification information of the key table is transmitted. Therefore, an attacker must disclose all keys from one key table, making it more difficult than before to forge a device to be authenticated.

As shown in FIGS. 4 and 5, the identification information of the key table 207 may correspond to one column number in the key matrix 400 in which a plurality of keys are arranged in a matrix. The identification information of authentication table 208 may correspond to one row number in key matrix 400 . The key table 207 may hold m keys stored in one column in the key matrix 400 and indicated by the identification information in the key table 207 . Thus, m keys are stored in the key table 207 . Therefore, it is difficult to expose all keys. In particular, if the device to be authenticated is mounted on a tamper-resistant chip, the tamper-resistant chip will be destroyed if the key is to be taken out. Therefore, exposing all keys is even more difficult. In other words, it is difficult to forge the device to be authenticated. Even if the authentication table held by the authentication device is exposed, the key table of the device to be authenticated cannot be forged. This is because all the keys held in the key table are required to forge the device to be authenticated.

Authentication table 208 holds n responses generated from n keys and n challenges. In addition, authentication table 208 also holds the n challenges. The n keys are stored in one row in the key matrix 400 and pointed to by the identification information in the authentication table 208 . Thus, since the authentication table 208 has n responses, it is difficult to disclose all of them. In particular, if the authentication device is mounted on a tamper-resistant chip, the tamper-resistant chip will be destroyed if the response is to be retrieved. Therefore, exposing all responses is even more difficult. In other words, it is difficult to forge the authenticating device and the authenticated device.

Each of the n challenges may be an independent random number. Also, each of the n responses may be calculated by inputting one challenge out of the n challenges and one key out of the n keys into a one-way function. . Here, the one-way function is the same function used to generate the response from the key retrieved from the key table and the challenge received from the authenticator. This would make it possible to simply compare the two responses, easing the authentication process. The one-way function may be a symmetric key cryptographic function or a cryptographic hash function.

As described in embodiment 2, the authenticator sends the password to the authenticated device, the authenticated device receives the password from the authenticator, and determines whether the password received from the authenticator is the correct password. good too. If the password received from the authenticator is the correct password, the authenticated device may generate a response from the key retrieved from the key table and the challenge. This further improves the security of the authentication system. The authentication table may acquire a password corresponding to a pair of the identification information of the key table received from the device to be authenticated and the identification information of the authentication table held by the authentication device. The device to be authenticated may obtain from the key table a password corresponding to a pair of identification information in the key table held by the device to be authenticated and identification information in the authentication table received from the authentication device. The device to be authenticated may determine whether the password received from the authenticator is the correct password by comparing the password received from the authenticator with the password retrieved from the key table.

Consumables for image forming apparatuses include, for example, cartridges containing photosensitive drums. The optional device of the image forming apparatus may be, for example, an optional paper feeding device for feeding sheets or an optional paper discharging device for processing (discharging) sheets.

The invention is not limited to the embodiments described above, and various modifications and variations are possible without departing from the spirit and scope of the invention. Accordingly, the claims are appended to publicize the scope of the invention.

100... Image forming apparatus (authentication system), 103... Chip to be authenticated, 106... Authentication chip

Claims (22)

An authentication method for authenticating a device to be authenticated by an authentication device,
the device to be authenticated transmitting identification information of a key table held by the device to be authenticated to the authentication device;
the authenticator receiving identification information of the key table from the authenticated device;
the authentication device transmitting identification information in an authentication table held by the authentication device to the device to be authenticated;
the authenticated device receiving identification information from the authentication table;
The authentication device transmits to the device to be authenticated a challenge corresponding to a pair of the identification information of the key table received from the device to be authenticated and the identification information of the authentication table held by the authentication device. and
the authenticated device receiving the challenge from the authenticator;
The device to be authenticated acquires from the key table a key corresponding to a pair of identification information in a key table held by the device to be authenticated and identification information in an authentication table held by the authentication device. When,
the authenticated device generating a response from the key obtained from the key table and the challenge;
the authenticated device transmitting the response to the authenticating device;
the authenticating device receiving the response from the authenticated device;
The authentication device acquiring, from the authentication table, a response corresponding to a pair of the identification information of the key table received from the device to be authenticated and the identification information of the authentication table held by the authentication device. When,
An authentication method, wherein the authentication device authenticates the device to be authenticated based on the response received from the device to be authenticated and the response obtained from the authentication table. The identification information of the key table corresponds to one column number in a key matrix in which a plurality of keys are arranged in a matrix,
the identification information of the authentication table corresponds to one row number in the key matrix;
2. The key table according to claim 1, wherein said key table holds m keys stored in a column in said key matrix and indicated by identification information of said key table. Described authentication method. The authentication table is one row in the key matrix, n generated from n keys and n challenges stored in one row indicated by the identification information of the authentication table. and the n challenges. 4. The authentication method according to claim 3, wherein each of said n challenges is an independent random number. Each of the n responses is calculated by inputting one of the n challenges and one of the n keys into a one-way function,
4. The one-way function is the same function used to generate the response from the key obtained from the key table and the challenge received from the authenticator. 4. The authentication method according to 4. 6. The authentication method according to claim 5, wherein said one-way function is a common key cryptographic function or a cryptographic hash function. the authenticating device transmitting a password to the authenticated device;
the authenticated device receiving the password from the authenticator;
the authenticated device determining whether the password received from the authenticator is a correct password;
3. The device to be authenticated generates a response from the key obtained from the key table and the challenge when the password received from the authenticating device is a correct password. 7. The authentication method according to any one of 6. the authentication device acquiring a password corresponding to a pair of the identification information of the key table received from the device to be authenticated and the identification information of the authentication table held by the authentication device; 8. The authentication method according to claim 7, further comprising: The device to be authenticated obtains from the key table a password corresponding to a pair of the identification information of the key table held by the device to be authenticated and the identification information of the authentication table received from the authentication device. further having
The device to be authenticated determines whether the password received from the authentication device is correct by comparing the password received from the authentication device and the password obtained from the key table. The authentication method according to claim 7, characterized by: An authentication system having an authenticated device and an authenticating device,
The device to be authenticated
transmitting identification information of a key table held by the device to be authenticated to the authentication device;
receiving identification information of an authentication table from the authentication device;
receiving a challenge corresponding to a pair of the identification information of the key table and the identification information of the authentication table held by the authentication device;
obtaining from the key table a key corresponding to a pair of the identification information of the key table held by the device to be authenticated and the identification information of the authentication table;
generating a response from the key obtained from the key table and the challenge;
configured to transmit the response to the authentication device;
The authentication device
receiving identification information of the key table from the device to be authenticated;
transmitting identification information in an authentication table held by the authentication device to the device to be authenticated;
sending the challenge to the authenticated device;
receiving the response from the authenticated device;
obtaining from the authentication table a response corresponding to a pair of the identification information of the key table received from the device to be authenticated and the identification information of the authentication table held by the authentication device;
An authentication system configured to authenticate the device to be authenticated based on the response received from the device to be authenticated and the response obtained from the authentication table. The identification information of the key table corresponds to one column number in a key matrix in which a plurality of keys are arranged in a matrix,
the identification information of the authentication table corresponds to one row number in the key matrix;
11. The key table according to claim 10, wherein said key table holds m keys stored in a column in said key matrix and indicated by identification information of said key table. Authentication system as described. The authentication table is one row in the key matrix, n generated from n keys and n challenges stored in one row indicated by the identification information of the authentication table. and the n challenges. An authenticated device authenticated by an authenticator,
a memory configured to store a key table;
a communication circuit,
transmitting identification information of the key table held by the memory to the authentication device;
receiving identification information of an authentication table held by the authentication device from the authentication device;
receiving a challenge corresponding to a pair of identification information of the key table and identification information of the authentication table from the authentication device;
a communication circuit configured to send a response to the authentication device;
a processor,
obtaining from the key table a key corresponding to a pair of the identification information of the key table and the identification information of the authentication table;
a processor configured to generate the response from the key obtained from the key table and the challenge;
A device to be authenticated, characterized by comprising: The identification information of the key table corresponds to one column number in a key matrix in which a plurality of keys are arranged in a matrix,
the identification information of the authentication table corresponds to one row number in the key matrix;
14. The method according to claim 13, wherein said key table holds m keys stored in a column in said key matrix and indicated by identification information of said key table. Authenticated Device as described. The authentication table is one row in the key matrix, n generated from n keys and n challenges stored in one row indicated by the identification information of the authentication table. and the n challenges. 16. The device to be authenticated according to any one of claims 13 to 15, wherein the device to be authenticated is mounted in a consumable item, a replacement part, or an optional device of an image forming apparatus. 17. The apparatus to be authenticated according to claim 16, wherein the consumables for the image forming apparatus are cartridges containing photosensitive drums. 17. The apparatus to be authenticated according to claim 16, wherein the optional device of said image forming apparatus includes an optional paper feeding device for supplying sheets or an optional paper discharging device for processing sheets. . An authentication device that authenticates an authenticated device,
a communication circuit for receiving identification information of a key table from the device to be authenticated;
a memory for storing an authentication table;
a processor;
The communication circuit is configured to transmit identification information of an authentication table held by the memory to the device to be authenticated,
The processor is configured to obtain from the authentication table a challenge corresponding to a pair of the key table identification information received from the authenticated device and the authentication table identification information held by the memory. has been
the communication circuit is configured to transmit the challenge obtained from the authentication table to the device to be authenticated and to receive a response to the challenge from the device to be authenticated;
The processor acquires from the authentication table a response corresponding to a pair of the identification information of the key table received from the device to be authenticated and the identification information of the authentication table held by the memory, and An authentication device configured to authenticate the device to be authenticated based on the response received from the authentication device and the response obtained from the authentication table. The identification information of the key table corresponds to one column number in a key matrix in which a plurality of keys are arranged in a matrix,
the identification information of the authentication table corresponds to one row number in the key matrix;
20. The key table according to claim 19, wherein said key table holds m keys stored in a column in said key matrix and indicated by identification information of said key table. Authenticator as described. The authentication table is one row in the key matrix, n generated from n keys and n challenges stored in one row indicated by the identification information of the authentication table. and the n challenges. 20. The authentication device according to claim 19, wherein the authentication device is mounted on a main body of an image forming apparatus.

Images