Authentication method

Abstract

A first circuit is authenticated using a second circuit. A first datum and a second datum are stored in the second circuit. The second datum corresponds to an application of a first function to the first datum and a third datum. The second circuit sends the second datum to the first circuit. The first circuit decrypts the second datum and sends a fourth datum representative of a result of the decrypting to the first second circuit for authentication. The second circuit verifies a correspondence between the first datum and the fourth datum.

Claims

1. A method of authenticating a first circuit using a second circuit, comprising: storing, at the second circuit, a first datum and a second datum, the second datum corresponding to an application of a first function to: the first datum; and a third datum; sending, from the second circuit to the first circuit, the second datum; decrypting, at the first circuit, the second datum; and sending, from the first circuit to the second circuit, a fourth datum representative of a result of the decrypting for authentication, wherein the fourth datum corresponds to the first datum encoded using a second function different from the first function.

2. The method of claim 1 wherein the second circuit verifies the correspondence between the first datum and the fourth datum.

3. The method of claim 1 wherein the decrypting comprises applying the second function to the second datum.

4. The method of claim 3 wherein the second function is an inverse of the first function.

5. The method of claim 3 wherein the third datum is a random datum.

6. The method of claim 3 wherein at least one of the first function and the second function is a combination function.

7. The method of claim 6 wherein the combination function is a concatenation function.

8. The method of claim 6 wherein the combination function is an exclusive OR function.

9. The method of claim 1, wherein the first datum is one of a plurality of first datum, the second datum is one of a plurality of second datum and the second circuit stores the plurality of first datum and the plurality of second datum in a correspondence table.

10. A device, comprising, a memory; and cryptographic circuitry coupled to the memory, wherein: the cryptographic circuitry, in operation, responds to receipt of a first datum (D2) from a second device by: decrypting the first datum (D2); and transmitting a second datum (D4) corresponding to a result of the decrypting to the second device, wherein: the first datum (D2) corresponds to application of a first function to: a third datum (D1) stored in the second circuit; and a fourth datum (D3); and the second datum corresponds to the third datum encoded with a second function different from the first function.

11. The device of claim 10 wherein the cryptographic circuitry, in operation, applies the second function to the first datum to decrypt the first datum.

12. The device of claim 11 wherein the second function is an inverse of the first function.

13. The device of claim 10 wherein the fourth datum is a random datum.

14. The device of claim 11 wherein at least one of the first function and the second function is a combination function.

15. The device of claim 14 wherein the combination function is a concatenation function.

16. The device of claim 14 wherein the combination function is an exclusive OR function.

17. A device, comprising, a memory storing a first datum and a second datum, the second datum corresponding to an application of a first function to: the first datum; and a third datum; and authentication circuitry coupled to the memory, wherein the authentication circuitry, in operation: transmits the second datum to a second device; responds to receipt of a fourth datum from the second device by verifying a correspondence between the first datum and the fourth datum, wherein the fourth datum is representative of a result of decrypting of the second datum by the second device and the fourth datum corresponds to the first datum encoded using a second function different from the first function.

18. The device of claim 17 wherein the fourth datum corresponds to application of the second function to the second datum.

19. The device of claim 18 wherein the second function is an inverse of the first function.

20. The device of claim 18 wherein the third datum is a random datum.

21. The device of claim 18 wherein at least one of the first function and the second function is a combination function.

22. The device of claim 21 wherein the combination function is a concatenation function.

23. The device of claim 21 wherein the combination function is an exclusive OR function.

24. A device, comprising, a memory storing a first datum and a second datum, the second datum corresponding to an application of a first function to: the first datum; and a third datum; and authentication circuitry coupled to the memory, wherein the authentication circuitry, in operation: transmits the second datum to a second device; responds to receipt of a fourth datum from the second device by verifying a correspondence between the first datum and the fourth datum, wherein the fourth datum is representative of a result of decrypting of the second datum by the second device, and the first datum is one of a plurality of first datum, the second datum is one of a plurality of second datum and the device stores the plurality of first datum and the plurality of second datum in a correspondence table in the memory.

25. A system, comprising: a first circuit storing a first datum and a second datum, the second datum corresponding to application of a first function to: the first datum; and a third datum; and a second circuit, which, in operation, responds to receipt of the second datum from the first circuit by: decrypting the second datum; and sending a fourth datum representative of a result of the decrypting to the first circuit, wherein the fourth datum corresponds to the first datum encoded using a second function different from the first function.

26. The system of claim 25 wherein the first circuit, in operation, responds to receipt of the fourth datum by verifying the correspondence between the first datum and the fourth datum.

27. The system of claim 25 wherein the second circuit, in operation, applies the second function to the second datum to decrypt the second datum.

28. The system of claim 27 wherein the second function is an inverse of the first function.

29. The system of claim 25, wherein the first datum is one of a plurality of first datum, the second datum is one of a plurality of second datum and the first circuit stores the plurality of first datum and the plurality of second datum in a correspondence table.

Description

BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWINGS

(1) The foregoing features and advantages, as well as others, will be described in detail in the following description of specific embodiments given by way of illustration and not limitation with reference to the accompanying drawings, in which:

(2) FIG. 1 illustrates schematically a block diagram depicting an example of an authentication method;

(3) FIG. 2 illustrates schematically a block diagram depicting some embodiments of an authentication method; and

(4) FIG. 3 illustrates schematically a block diagram depicting some embodiments of an authentication method.

DETAILED DESCRIPTION

(5) Like features have been designated by like references in the various figures unless the context indicates otherwise. In particular, the structural and/or functional features that are common among the various embodiments may have the same references and may have identical structural, dimensional and material properties.

(6) For the sake of clarity, only the operations and elements that are useful for an understanding of the described embodiments herein have been illustrated and described in detail. In particular, this authentication method can be adapted to conventional communication methods.

(7) Unless indicated otherwise, when reference is made to two elements that are connected together, this means a direct connection without any intermediate elements other than conductors, and when reference is made to two elements that are linked or coupled together, this means that these two elements can be connected or be linked or coupled by way of one or more other elements.

(8) In the following disclosure, unless indicated otherwise, when reference is made to absolute positional qualifiers, such as the terms “front,” “back,” “top,” “bottom,” “left,” “right,” etc., or to relative positional qualifiers, such as the terms “above,” “below,” “higher,” “lower,” etc., or to qualifiers of orientation, such as “horizontal,” “vertical,” etc., reference is made to the orientation shown in the figures.

(9) Unless specified otherwise, the expressions “around,” “approximately,” “substantially” and “in the order of” signify within 10%, and preferably within 5%.

(10) FIG. 1 depicts, schematically and in the form of blocks, the implementation of an authentication method between two circuits 100 (Verifier) and 200 (Prover).

(11) The circuit 100 is, for example, part of a hardware item, while the circuit 200 is, for example, part of a consumable or accessory. The circuit 100 has the role of a verifier circuit vis-à-vis the circuit 200, the prover circuit, which authenticates itself.

(12) The authentication method of FIG. 1 is an authentication method of a verifier/prover type, wherein the prover circuit 200 has to transmit, to the verifier circuit, a secret datum, for example a password, in order to authenticate itself.

(13) The sequence of an example of this method is the following.

(14) On the side of the circuit 100, a block 101 (Generate C) depicts a first step of the method in which the verifier circuit 100 generates a datum C. A new datum C is generated with each execution of the authentication act. Each datum C is different from that of the preceding authentication act. For instance, the datum C is generated by a counter, or by a system for generating a random number.

(15) The datum C is then sent to the prover circuit 200.

(16) On the side of the circuit 200, a block 201 (H) depicts a step of encoding the datum C by means of a secret datum S possessed by the prover circuit 200. The datum C is encoded by means of an encoding function H using the secret datum S as the encryption or signature key. For instance, the function H is an encryption function, for example a permutation. According to another example, the function H is a signature function.

(17) The encoded datum, designated as R, is then sent to the prover circuit 100.

(18) A block 103 (Verify) of the circuit 100 depicts a verification step for verifying, by the verifier circuit 100, the encoded datum R received from the prover circuit. For this purpose, the verifier circuit uses a verification function Verify. The function Verify takes, as an input, the datum C contained in the circuit 100, the encoded datum R and provides, as an output, an indication VF representative of the result of the authentication, for example a flag comprising a True state and a False state. The True state signifies that the authentication is successful, and the False state signifies the opposite. According to some embodiments, the circuit 100 knows the secret datum S, and the function Verify further takes the secret datum S as an input. For instance, in this case, the secret datum S is used as a symmetrical encryption key, the function Verify decrypts the datum R with the secret datum S, and then verifies if it corresponds to the expected datum. According to a further example, the function Verify does not require the decryption of the encoded datum R.

(19) A drawback of the authentication method described in relation to FIG. 1 is that a person successful in analyzing the operation of the verifier circuit 100 could create a clone prover circuit adapted to authenticate itself vis-à-vis the verifier circuit, for example by extracting the secret datum S and/or the encryption function H.

(20) FIG. 2 depicts, schematically and in the form of blocks, some embodiments of an authentication method between two circuits 300 (Verifier) and 400 (Prover). The authentication method is an authentication method of the type challenge/response.

(21) In some embodiments, the circuit 300 is, for example, part of a hardware item, while the circuit 400 is, for example, part of a consumable or an accessory. The circuit 300 has the role of verifier circuit vis-à-vis the circuit 400, the prover circuit, which authenticates itself.

(22) The verifier circuit 300 comprises a correspondence table, or data base, 301 comprising a plurality of data pairs (A, A′). In an embodiment, each data pair (A, A′) may be represented by the following formula:
ƒ(A′)=g(A;rand)  [Algorithm 1]
wherein:

(23) ƒ is a secret encryption function;

(24) g is a combination function; and

(25) rand is a random datum.

(26) According to an embodiment, the function ƒ is an invertible function. In this case, each data pair (A, A′) is composed of a datum A, generated similarly to datum C described in relation to FIG. 1, and of a datum A′ defined by the following formula:
A′=ƒ.sup.−1(A″)  [Algorithm2]
wherein:

(27) ƒ.sup.1 represents the inverse function of the secret encryption function ƒ, and

(28) A″ represents the result of the function g applied to the datum A and a random datum rand. That is: A″=g(A; rand).

(29) According to a second embodiment, function ƒ is not an invertable function. In this case, each data pairs (A, A′) comprises a datum A′, generated similarly to datum C described in relation to FIG. 1, and of a datum A defined by the above-mentioned formula [Algorithm 1]. An inverse function of function g is used to determine datum A based on ƒ(A′). The computation of this inverse function can, for example, use datum rand, or a piece of information derived from the datum rand, for example, its length. As an example, function g is a concatenation function, and datum A is obtained by truncating image ƒ(A′) of datum A′ by function ƒ.

(30) The data pairs (A, A′) are generated by one or the other above-described embodiments during a personalization phase, for example implemented by a circuit external to circuit 300. Data pairs (A, A′) are then stored in the correspondence table 301 of the circuit 300, for example when the circuit is manufactured. More specifically, during a phase of personalizing the circuit 300, a circuit external to the circuit 300 retrieves the data A from the correspondence table 301 in order to calculate the corresponding data A′. The data pairs (A, A′) are then stored in the correspondence table 301. Thus, during the active phase of the circuit 300, the circuit 300 only stores the data A and A′. An advantage of this feature is that neither the secret function ƒ nor its inverse function ƒ.sup.1 is known by the verifier circuit 300.

(31) The sequence of the embodiment of this method is the following.

(32) On the side of the circuit 300, a block 303 (Pick a pair) depicts a step of choosing, from the correspondence table 301, a data pair (A, A′). For instance, the verifier circuit 300 chooses a data pair in a random manner.

(33) The datum A′ of the pair (A, A′) is then sent to the prover circuit 400.

(34) A block 401 (f) of the circuit 400 depicts a step of obtaining the datum A″ from the datum A′. For this purpose, the circuit 400 uses the secret encryption function ƒ which the circuit 300 does not know, in order to obtain the datum A″.

(35) A block 403 (Extract A) depicts a step of determining the datum A from the datum A″. As explained in the foregoing, the function g is a function by means of which it is possible to combine the datum A with the random datum rand. According to some embodiments, the function g is a concatenation function for concatenating the datum A and the datum rand, and, in this case, the function by means of which it is possible to determine A is a truncation function by means of which it is possible to eliminate the datum rand.

(36) A block 405 (H) depicts a step of encoding the secret datum S possessed by the prover circuit 400. The secret datum S is encoded by means of the datum A and an encoding function H similar to the one described in relation to FIG. 1.

(37) The encoded secret datum, designated as R, is then sent to the prover circuit 300.

(38) A block 305 (Verify) of the circuit 300 depicts a verification step for verifying, by the verifier circuit 300, the encoded secret datum R received from the prover circuit. For this purpose, the verifier circuit uses a verification function Verify of the same type as the function Verify described in relation to FIG. 1, providing the binary value VF.

(39) An advantage of this embodiment is that a person having access to the data A′ and R transmitted between the circuits 300 and 400, in certain embodiments, contained in the circuit 300, will not be able to access the secret datum S without knowing the secret encryption function ƒ It is thus not necessary to protect the circuit 300 against the extraction of this secret function.

(40) A further advantage of this embodiment is that a person having access to the data and to the functions of the verifier circuit 300 will not be able to generate new pairs (A, A′) since the secret function ƒ is only encoded in the prover circuit 400.

(41) Thus, in some embodiments, the circuits 300 and 400 adapted to implement the method described in relation to FIG. 2 are defined by the following features.

(42) The circuit 300 comprises a correspondence table storing the data A and A′. The circuit 300 is further adapted to implement the function Verify.

(43) The circuit 400 is adapted to implement the encryption function ƒ and the function H, and to extract the datum A from the datum A″.

(44) As illustrated, in some embodiments, the verifier 300 of FIG. 2 includes a processor P1 and a memory M1, in addition to the illustrated discrete circuitry 301, 303, 305. In some embodiments, the processor P1 and the memory M1 may be employed, alone or in various combinations with the illustrated discrete circuitry, to provide the functionality of the verifier 300. In some embodiments, the prover 400 of FIG. 2 includes a processor P2 and a memory M2, in addition to the illustrated discrete circuitry 401, 403 and 405. In some embodiments, the processor P2 and the memory M2 may be employed, alone or in various combinations with the illustrated discrete circuitry to provide the functionality of the prover 400.

(45) FIG. 3 depicts, schematically and in the form of blocks, some embodiments of an authentication method between two circuits 500 (Verifier) and 600 (Prover). The authentication method is an authentication method of the type of challenge/response.

(46) The circuit 500 is, for example, part of a hardware item, while the circuit 600 is, for example, part of a consumable or an accessory. The circuit 500 has the role of a verifier circuit vis-à-vis the circuit 600, the prover circuit, which authenticates itself.

(47) The verifier circuit 500 comprises a correspondence table, or data base, 501 comprising a plurality of data triplets (B, B′, rand). In an embodiment, each data triplet (B, B′, rand) may be represented by the following formula:
ƒ(B′)=g(B;rand)  [Algorithm 3]
wherein:

(48) ƒ is a secret encryption function; and

(49) g is a combination function.

(50) According to a first embodiment, the function ƒ is an invertible function. In this case, each data pair (B, B′, rand) is composed of a datum B, generated similarly to datum C described in relation to FIG. 1, of a random datum rand, and of a datum B′ defined by the following formula:
B′=ƒ.sup.−1(B″)  [Algorithm4]
wherein:

(51) ƒ.sup.1 represents the inverse function of a secret encryption function ƒ, and

(52) B″ represents the result of the expression g(B, rand).

(53) According to a second embodiment, function ƒ is not an invertible function. In this case, each data triplets (B, B′, rand) is composed of a datum B′, generated similarly to datum C described in relation to FIG. 1, a randomly generated datum rand, and a datum B defined by the above-mentioned formula [Algorithm 3]. An inverse function of function g is used to determine, using datum rand, datum B based on ƒ(B′). The computation of this inverse function can, for example, use the datum rand, or a datum derived from the datum rand. As an example, when data are binary words, function g is a logical combination function g of type exclusive OR (XOR) defined by the following formula:
g(B;rand))=B⊕rand  [Algorithm5]
wherein:

(54) B and rand are binary words; and

(55) symbol ⊕ represents the exclusive OR function.

(56) The data triplets (B, B′, rand) are generated by one or the other above-described embodiments during a personalization phase, for example implemented by a circuit external to circuit 500. For example, each datum B is stored in the correspondence table 501 of the circuit 500 during the manufacture of the circuit 500. For example, during a phase of personalizing the circuit 500, a circuit external to the circuit 500 uses the data B from the correspondence table 501 to calculate the corresponding data B′. Data triplets (B, B′, rand) are, then stored in the correspondence table 501. Thus, during the active phase of the circuit 500, the circuit 500 only stores the data B, B′, and rand. An advantage of this feature is that neither the secret function ƒ nor, if applicable, its inverse function ƒ.sup.1 is known by the verifier circuit 500.

(57) The sequence of the embodiment of this method is the following.

(58) A block 503 (Pick a triplet) illustrates a step of choosing, from the correspondence table 501, a data triplet (B, B′, rand). For instance, the verifier circuit 500 chooses a data triplet in a random manner.

(59) The data B′ and rand of the triplet (B, B′, rand) are then sent to the prover circuit 600.

(60) A block 601 (f) depicts a step of extracting the datum B″ from the datum B′. The circuit 600 uses the secret encryption function ƒ to obtain the datum B″.

(61) A block 603 (Extract B) depicts a step of extracting or determining the datum B from the datum B″. This step may use the random datum rand. As stated in the foregoing, the function g is a function by means of which it is possible to combine the datum B with the random datum rand. According to some embodiments where the data are binary words, the function g is a logical combination function of exclusive OR type. In this case, the extraction of the datum B may include application of a function g, defined by the following formula:
g(g(B;rand);rand)=B⊕rand⊕rand  [Algorithm 6]
wherein the symbol ⊕ represents the exclusive OR function.

(62) A block 605 (H) illustrates a step of encoding the secret datum S possessed by the prover circuit 600. The secret datum S is encoded by means of the datum B and an encoding function H similar to the one described in relation to FIG. 1.

(63) The encoded secret datum, designated as R, is then sent to the prover circuit 500.

(64) A block 505 (Verify) depicts a verification step for verifying, by the verifier circuit 500, the encoded secret datum R received from the prover circuit. For this purpose, the verifier circuit uses a verification function Verify of the same type as the function Verify described in relation to FIGS. 1 and 2. Thus, the function Verify takes, as an input, the datum B and the encoded secret datum R, and provides, as an output, a binary indication VF.

(65) The advantages of this embodiment are the same as the advantages of the embodiment described in relation to FIG. 2.

(66) Thus, the circuits 500 and 600 adapted to implement the method described in relation to FIG. 2 are defined by the following features.

(67) The circuit 500 comprises a correspondence table storing the data B, B′ and rand. The circuit 500 is further adapted to implement the function Verify.

(68) The circuit 600 is adapted to implement the encryption function ƒ and the function H, and to extract the datum B from the datum B″ and, for example, from the random datum rand.

(69) As illustrated, in some embodiments, the verifier 500 of FIG. 3 includes a processor P3 and a memory M3, in addition to the illustrated discrete circuitry 501, 503, 505. In some embodiments, the processor P3 and the memory M3 may be employed, alone or in various combinations with the illustrated discrete circuitry, to provide the functionality of the verifier 500. In some embodiments, the prover 600 of FIG. 3 includes a processor P4 and a memory M4, in addition to the illustrated discrete circuitry 601, 603 and 605. In some embodiments, the processor P4 and the memory M4 may be employed, alone or in various combinations with the illustrated discrete circuitry to provide the functionality of the prover 600.

(70) An advantage of the authentication methods described in relation to FIGS. 2 and 3 is that they can be used to complement a classic authentication method, for example of the type described in relation to FIG. 1.

(71) Various embodiments and variants have been described. Those skilled in the art will understand that certain features of these embodiments can be combined and other variants will readily occur to those skilled in the art.

(72) In addition, a prover circuit of the same type as the circuits 400 and 600 comprising a correspondence table comprising all the data R corresponding to the data A′ or B′ sent by a verifier circuit of the same type as the circuits 300 and 500, is some embodiments.

(73) Finally, the practical implementation of the embodiments and variants described herein is within the capabilities of those skilled in the art based on the functional description provided hereinabove.

(74) Some embodiments may take the form of or comprise computer program products. For example, according to one embodiment there is provided a computer readable medium comprising a computer program adapted to perform one or more of the methods or functions described above. The medium may be a physical storage medium, such as for example a Read Only Memory (ROM) chip, or a disk such as a Digital Versatile Disk (DVD-ROM), Compact Disk (CD-ROM), a hard disk, a memory, a network, or a portable media article to be read by an appropriate drive or via an appropriate connection, including as encoded in one or more barcodes or other related codes stored on one or more such computer-readable mediums and being readable by an appropriate reader device.

(75) Furthermore, in some embodiments, some or all of the methods and/or functionality may be implemented or provided in other manners, such as at least partially in firmware and/or hardware, including, but not limited to, one or more application-specific integrated circuits (ASICs), digital signal processors, discrete circuitry, logic gates, standard integrated circuits, controllers (e.g., by executing appropriate instructions, convolutional accelerators, and including microcontrollers and/or embedded controllers), field-programmable gate arrays (FPGAs), complex programmable logic devices (CPLDs), etc., as well as devices that employ RFID technology, and various combinations thereof.

(76) The various embodiments described above can be combined to provide further embodiments.

(77) These and other changes can be made to the embodiments in light of the above-detailed description. In general, in the following claims, the terms used should not be construed to limit the claims to the specific embodiments disclosed in the specification and the claims, but should be construed to include all possible embodiments along with the full scope of equivalents to which such claims are entitled. Accordingly, the claims are not limited by the disclosure.