Method of authentication of an entity by a verifying entity

The present invention relates to a method of authenticating an entity by a verification entity.

The present invention is particularly advantageous for applications in the field of cryptographic protocols for the authentication of ultra-low cost electronic microchips, especially in contact or non-contact with RFID (radio-frequency identification) tags.

Low-cost electronic microchips, such as RFID, have many applications such as labeling or tracking objects (drug prescriptions, library books, etc.) and manufacturing, and verifying electronic tickets such as public transport tickets. Used in technology.

Regardless of their application, it is necessary to prevent fraud by counterfeiting microchips, in particular by copying or duplicating them or reproducing the data they transmit. In order to protect those applied technologies from such infringement, it is inevitable that the microchip will need to authenticate when interacting with the microchip reader.

<p><nplcit num="1"><text>A. Juels and SA Weis, "Authenticating Pervasive Devices with Human Protocols", in V. Shoup, Editor, Advances in Cryptology --Crypto 05, Lecture Notes in Computer Science, Vol. 3126, pp. 293-308, Springer Verlag</text></nplcit></p>

<p> However, any authentication protocol used between an authenticated entity such as a low-cost microchip and a verification entity such as a microchip reader is typically a hard-wired logic of this type. The very limited computational resources of the microchip must be considered.</p><p> Symmetrical HB + (Hopper-Blum) authentication protocols specially designed to meet the requirements of RFID microchips have been recently advocated (A. Juels and SA Weis, "Authenticating Pervasive Devices with Human Protocols", in V. Shoup. , Editor, Advances in Cryptology-see Crypto 05, Lecture Notes in Computer Science, Vol. 3126, pp. 293-308, Springer Verlag).</p><p> Figure 1 shows the exchange of data under the HB + protocol between the authenticated entity and the verification entity.</p><p> As can be seen from this figure, for example, an authenticated entity that is an RFID microchip and, for example, a verification entity that is a microchip reader share a pair of private keys x and y consisting of an n-bit binary vector. These private keys are stored in the storage means 10 of the microchip and the storage means 20 of the microchip reader.</p><p> The HB + protocol unfolds r consecutive successful iterations. In each iteration, the microchip randomly draws an n-bit binary vector b (block 100) and sends it to the microchip reader (1). Similarly, the microchip reader randomly extracts an n-bit binary vector a (block 200) and sends it to the microchip (2). Random sampling of the vectors b and a is achieved according to the uniform probability law.</p><p> The microchip then responds (block 120) by calculating the launched challenge a from the microchip reader, and:</p><p><maths num="1"><img file="JP2010528512A_D0001.tif" /></maths></p><p>Sends a response that is affected by the noise z indicated by (3). here,</p><p><maths num="2"><img file="JP2010528512A_D0002.tif" /></maths></p><p>Represents a modulo 2 scalar product operation</p><p><maths num="3"><img file="JP2010528512A_D0003.tif" /></maths></p><p>Represents the modulo 2 sum. Noise bits ν are randomly sampled by the microchip (block 110). The noise bit ν has a value of 1 with a probability of η &lt;1/2 and a value of 0 with a probability of (1-η).</p><p> In the microchip reader, the received response z is the following equation.</p><p><maths num="4"><img file="JP2010528512A_D0004.tif" /></maths></p><p>If does not satisfy, the current sequential assignment is rejected (block 210). In this case, the counter with the number of rejected sequential assignments nbr is incremented by 1 unit (block 220). Number of sequential assignments Counted by nbt counters (block 250) At the end of r consecutive assignments, the number of rejected sequential assignments nbr is less than or equal to the given threshold t (block) 230) and only then is the certification approved (block 240). Of course, the value t is a function of the probability η, and a simple value t is, for example, t = r × η.</p><p> The data exchange recommended by the HB + protocol consists of r iterations of three passes, but the r values of b, a, and z are calculated and the data of 3 passes sent at the same time. It is also possible to reduce to one exchange.</p><p> The advantage of the HB + protocol is that the authentication calculation is fairly simple.</p><p> Moreover, its robustness is due to the difficulty of finding a solution to the noise-free linear system of the LPN (Learning Parity with Noise) problem. Finally, the HB + protocol is a term</p><p><maths num="5"><img file="JP2010528512A_D0005.tif" /></maths></p><p>It has the advantage that the masking effect induced by the binary vector b is combined with the private key y compared to the different historically early HB protocol in terms of response under noisy conditions. The HB protocol was vulnerable to attacks in which an attacker sent a certain challenge a and received a response from a microchip reader. The most common response</p><p><maths num="6"><img file="JP2010528512A_D0006.tif" /></maths></p><p>And a is known. For a sufficient number of a values in the first step</p><p><maths num="7"><img file="JP2010528512A_D0007.tif" /></maths></p><p>In the second step, it was possible to derive x by solving the linear system.</p><p> However, in practice, the HB + protocol has the drawback of hindering its efficient use.</p><p> As already pointed out, the first drawback is that although this protocol is resistant to some aggressive attacks on a, the attacker nevertheless has multiple consecutive authentications (success / failure). Vulnerabilities to other attacks encountered when the results are available remain.</p><p> Such an attack interferes with the challenge a when it is transmitted from the microchip reader to the microchip and continuously modifies the bit. For example, if the first bit of a is modified and the result does not change after this modification, it is clear that the first bit of the secret vector x is 0. Conversely, if the result changes, the first bit of x is probably equal to 1. It is sufficient to modify the second bit of a to find the second bit of x, and repeat up to n bits to get all n bits of x.</p><p> The second drawback of the HB + protocol is that it produces excessive false alarms. A false alarm is defined as a legitimate microchip authentication refusal. The following values: n = 224 bits, η = 0.25, r = 100 sequential substitution, t = η × r = 25, for example, the false positive alarm rate is 45%, which is totally unacceptable. False positive rate, or successful authentication of chips that respond randomly, is 3 x 10^-7It is in the vicinity.</p><p> If t takes a high value such as 35 instead of the expected value t = η × r = 25, the false alarm rate drops to 1%. This is still unacceptable, but the false positive rate is approximately 1.7 x 10^-3Increases to.</p><p> Finally, the third drawback of HB + is that it leads to excessive complexity in communication between the microchip and the microchip reader. The same numbers as before indicate that each authentication requires a 44,900-bit data exchange. That is, in each of the 100 sequential substitutions, there are 224 bits for b, 224 bits for a, and 1 bit for the result z.</p><p> Even at a bit rate of 10000 bps, the microchip reader requires more than 4 seconds to authenticate the microchip, which is from an ergonomic point of view, not to mention problems with powering the microchip. Is unbearable.</p>

<p> Therefore, the present invention provides a method of entity authentication by a verification entity. The entity shares a pair of private keys X and Y. The method is that the private keys X and Y are binary matrices of n × m (n, m&gt; 1), and the following steps:</p><p>-The step of exchanging data of n-bit binary vectors a and b randomly extracted from the verification entity and the authenticated entity, respectively, and the authenticated entity is m-bit. Steps to randomly extract the noise binary vector c and the following</p><p><maths num="8"><img file="JP2010528512A_D0008.tif" /></maths></p><p>The step of calculating the m-bit response vector z given in and sending it to the validation entity. Here, each of the m bits is 1 with a probability η less than 1/2.</p><p>-Validation entity is an error vector</p><p><maths num="9"><img file="JP2010528512A_D0009.tif" /></maths></p><p>Steps to calculate the Hamming weight of.</p><p> If the Hamming weight of the error vector of r satisfies a comparative relationship with a parameter that is a function of probability η, then the accepting step.</p><p>It is characterized by repeating r times (r 1).</p><p> Therefore, the method of the present invention has improved resistance to bit-altering attacks of challenge a aimed at reconstructing the private key X, as compared to the HB + protocol. If the first bit of a is modified, the modification affects the product of the first bit of the m-column of X and that bit, and also affects the m-bit of the product aX. Therefore, it affects the entire response z. Therefore, it is impossible to infer any information about the private key X by observing the effect of the authentication result of the modification of the bit of a. This is because multiple m bits of z can be modified without telling their number or position. In the HB + protocol, a 1-bit modification of a directly affects the response z, which consists of only 1 bit.</p><p> In the practice of the method of the present invention, the response z of each sequential assignment is described in m bits as if m sequential assignments were made by only one sequential assignment.</p><p> As a result, in the first extreme situation, it is possible to infer the number of successive substitutions by a factor called degree. And, in practice, limiting the number of sequential assignments to only one maintains the performance of the HB + protocol in terms of false alarm rates, but the number of bits exchanged is from r (2n + 1) to ( It decreases from 44900 bits to 576 bits up to 2n + m), i.e. n = 224, and m = 128, showing a significant improvement. This example fully demonstrates the benefits of the present invention when limiting the number of sequential assignments r, which cannot be expected with the HB + protocol, to 1.</p><p> In the second limit state, the number of sequential substitutions is the same. The total amount of data exchanged will increase slightly, but the false positive rate will be insignificant.</p><p> Of course, the practical state must be selected between these two extreme states in terms of reducing the false alarm rate and the number of bits exchanged between the microchip and the microchip reader.</p><p> That being said, it is clear that the present invention provides better performance than the HB + protocol in terms of false alarm rates and the total amount of information exchanged between the two entities.</p><p> In one configuration example of the present invention, the matrices X and Y are Toeplitz matrices. As described in more detail below, this advantageous feature reduces the storage capacity of microchips and microchip readers to the range (n + m -1) instead of n × m when other matrices are selected. There is a point to do. Another advantage is the simplified calculation of the products aX and bY.</p><p> The present invention also provides an entity that is authenticated by a verification entity. The entity shares a pair of private keys X and Y, and the authenticated entity is a means of storing a private key X and Y consisting of a binary matrix of n × m (n, m&gt; 1) and said. Means of communication with the validation entity and the following steps:</p><p> -A step of randomly sampling an n-bit binary vector b and sending it to a validation entity.</p><p> -The step of receiving the n-bit binary vector a from the validation entity.</p><p> -The step of randomly sampling the m-bit noise binary vector c and each of the m-bits has a probability of less than 1/2 and is 1.</p><p><maths num="10"><img file="JP2010528512A_D0010.tif" /></maths></p><p>The step of calculating the m-bit response vector z and sending it to the validation entity.</p><p>It is characterized by including a calculation means configured to carry out r times (r 1).</p><p> The present invention also provides a computer program comprising program instructions for performing a step performed by the authenticated entity when the program is executed by the computer forming part of the computing means of the authenticated entity. provide.</p><p> The present invention further provides a validation entity that shares a pair of private keys X and Y with the authenticated entity. The verification entity contains means for storing private keys X and Y consisting of a binary matrix of n × m (n, m&gt; 1), means for transmitting to the authenticated entity, and the following steps:</p><p> -The step of receiving the n-bit binary vector b from the authenticated entity.</p><p> -A step of randomly extracting an n-bit binary vector a and sending it to the authenticated entity.</p><p> -A step of receiving an m-bit response vector z from the authenticated entity.</p><p> Error vector</p><p><maths num="11"><img file="JP2010528512A_D0011.tif" /></maths></p><p>The step of calculating the Hamming weight of and the step of approving the authentication when the Hamming weight of r error vectors e satisfies the comparison relationship with the parameter (T, t) which is a function of a predetermined probability η. It is characterized by including a calculation means configured to carry out r times (r 1).</p><p> The present invention finally provides a computer program comprising program instructions that execute a step performed by the verification entity when the program is executed by the computer forming part of the computing means of the verification entity.</p><p> The following description is presented as an example without limitation with reference to the accompanying drawings, and describes what the essence of the present invention lies in and how it is practiced.</p>

<figref num="1">Demonstrates the data exchange between authenticated and verification entities under the HB + protocol.</figref><figref num="2">Demonstrates the exchange of data between an authenticated entity and a verification entity in the method of the invention.</figref><figref num="3">The entity authenticated by the method of FIG. 2 is illustrated.</figref><figref num="4">The verification entity for authenticating the entity of FIG. 3 using the method of FIG. 2 is illustrated.</figref>

FIG. 2 shows, for example, an authentication method that allows a verification entity, which is a contact or non-contact microchip reader, to verify the identity of the authenticated entity, which in this example is an RFID microchip.

The method shown in FIG. 2 is called the symmetrical method, in which two entities (microchip and microchip reader) share the same private key. The key specified by these X and Y is an n × m (n, m&gt; 1) binary matrix consisting of n rows and m columns. The private keys X and Y are stored in the storage means 10 of the microchip and the storage means 20 of the microchip reader (see FIGS. 2, 3, and 4).

The method of the present invention comprises a plurality of steps that are repeated r times (r 1)). The expression "r times" indicates that the exchange between the microchip and the microchip reader is sequentially performed r times of three-pass sequential substitution as shown in FIG. The number of sequential assignments nbt is incremented by a counter for each sequential assignment or in parallel with 3 passes (block 250). Each path contains the transmission of r-items of data from one entity to another.

In the example of FIG. 2, the microchip 1 is randomly sampled for each sequential assignment (block 100), and a sequence of n-bit binary vectors b is transmitted to the microchip reader 2 (1). The microchip reader 2 then transmits a randomly sampled sequence of n-bit binary vectors, challenge a (block 200), to the microchip 1 (2). The binary vectors b and a are randomly sampled according to a 0 and 1 bit uniform distribution.

In response to the challenge a, the microchip 1 is a modulo 2 sum.

<maths num="12"><img file="JP2010528512A_D0012.tif" /></maths>

A sequence of m-bit binary vectors z (block 120') is transmitted to the microchip reader 2 (3). Where c is a sequence of m-bit noise binary vectors randomly sampled by Microchip 1 according to the law of probability (block 110'). Each bit of c is guaranteed to be equal to 1 according to the law of probability, with equal probability, or probability less than parameter η, which is less than 1/2, or probability equal to parameter η. Therefore, each bit of the noise vector c is randomly selected independently of the others according to Bernoulli's principle by the parameter η &lt;1/2. The noise vector c may be randomly extracted from all vectors of m bits whose sum (hamming weight) of the bits is η &lt;1/2 and the value is η × m or less. Of course, the noise vector c may be randomly sampled by the microchip at the same time as the binary vector b is randomly sampled. It should be recalled that the binary vector b is used to mask the aggressive attack of Berthold a.

In each sequential substitution, the microchip reader 2 has the following equation:

<maths num="13"><img file="JP2010528512A_D0013.tif" /></maths>

The m-bit error vector given in e is calculated (block 210'). Here, z is the response vector transmitted by the microchip 1, and the Hamming weight PH (e) (block 220') of the error vector e is obtained in this way.

After r successive substitutions, the approval or rejection of the authentication of the microchip 1 by the microchip reader 2 is a function of r Hamming weights PH (e) of the error vector e and the probability η obtained in each successive assignment. It is determined by comparison with the parameters that are.

Several strategies are also possible.

The first strategy represented by FIG. 2 is that the sum S (block 221') of the Hamming weights of r error vectors e is below a given threshold value T where, for example, r (η + ε) m. Approve authentication if (block 230') and only then (block 240'). Here, ε is a margin of 1/2 or less, and is probably zero.

The second strategy approves authentication only if the Hamming weight of the error vector e obtained in each sequential substitution is less than or equal to the threshold T.

Finally, the third strategy approves authentication only if and only if the Hamming weight of the error vector e obtained in each sequential assignment is equal to the value t.

In the second and third strategies, the parameter t has a value (η + ε) m. Where ε is a margin less than or equal to 1/2, probably zero.

A noise vector c randomly selected from a binary vector of length 128, with r = 1, n = 256, m = 128, η = 0.25, and its Hamming weight is 32, ie η x m, of the microchip. Authentication is only approved under the third strategy above if and only if the weight of the error vector e in each sequential assignment is exactly equal to 32. Where ε = 0.

In this example, the total length of the data exchange is only 640 bits, or (2n + m) bits. On the other hand, the false positive alarm rate is strictly zero, and the positive rate for attacks with a random value of z is 10.^-8It is in the vicinity and is practically accepted as a whole.

In FIG. 2, a series of exchanges between the microchip 1 and the microchip reader 2 are as follows: a step of transmitting b to the microchip reader, a step of transmitting a to the microchip, the micro A step in which the chip randomly extracts c, and a step in which z is transmitted to the microchip reader. It should be noted that different sequences can be used equally. That is: a step of transmitting a to the microchip, a step of the microchip randomly sampling b and c, and a step of the microchip reader transmitting b and z. This sequence has the advantage of reducing the number of data exchanges.

In an implementation that greatly reduces the amount of memory required to store the matrices X and Y and greatly reduces the complexity of the calculations performed by the microchip and the validation entity, the respective matrices X and Y are n. It can be selected from within the strict subset of all n × m matrices defined within the microchip that use multiple bits less than × m. For example, the amount of memory required to store each matrix can only be reduced to (n + m -1) if X and Y are Toeplitz matrices. That is, since all the coefficients are a matrix of constant coefficients along the diagonal line, the whole is determined by the coefficients in the first row and the first column. X is the Toeplitz matrix, x_{i, j}If is a coefficient in the i-th row and j-th column, then x_{i, j}Is x if i is greater than or equal to j_{i-j + 1,1}Equal to, otherwise x_{1, j-i + 1}Is equal to.

The following implementation is very efficient, for example X, which is a Toeplitz matrix defined by the coefficients of a binary vector, eg a, and (n + m -1) of its first row and its first column. Calculates the bit-by-bit product of, using two m-bit registers. One of the registers is used to calculate the current row of the matrix, the other is initialized to 0 and is used to store the partial result of the vector-matrix product. The first register is initialized in the first line of X. After that, each bit of the vector a is processed by the following method. If the current bit of a is 1, the value of the current row of X is combined bit by bit using the exclusive OR operator with the current value of the partial result storage register. Otherwise, the current value of this register will not be modified. Either way, if the current row is not the last row in matrix X, the register containing the current row in that matrix will be in the leftmost cell of this register with the first corresponding to the new current row. It is updated by copying the coefficients of the column and then rotating the contents of this register to the right by 1 bit.

In two entities sharing a pair of private keys X and Y, the microchip 1 authenticated by the microchip reader 2 is n x m (n, m&gt; 1), as shown in FIG. ) Means 10 for storing the private keys X and Y consisting of a binary matrix, means 12 for transmitting with the microchip reader 2, and the following steps of the method described with reference to FIG.

-A step of randomly sampling an n-bit binary vector b and sending it to the microchip reader 2.

-The step of receiving the n-bit binary vector a from the microchip reader 2.

-The step of randomly extracting the m-bit noise binary vector c and each of the m-bits has a probability η of 1/2 or less and is 1, and the following

<maths num="14"><img file="JP2010528512A_D0014.tif" /></maths>

The step of calculating the m-bit response vector z, which is, and sending it to the microchip reader 2. , Includes calculation means 11, which are configured to execute, r times.

Similarly, in FIG. 4, the microchip reader 2 for authenticating the microchip 1 is authenticated with means 20 for storing the private keys X and Y consisting of a binary matrix of n × m (n, m&gt; 1). Microchip 1 and means of transmission 22 and the following steps of the method described with reference to FIG.

-The step of receiving the n-bit binary vector b from the authenticated microchip 1.

-A step of randomly extracting an m-bit binary vector a and transmitting it to the microchip 1.

-The step of receiving the m-bit response vector z from the microchip 1.

Error vector

<maths num="15"><img file="JP2010528512A_D0015.tif" /></maths>

The step of calculating the Hamming weight of and the step of approving the authentication when the Hamming weight of r error vectors e satisfies the comparison relationship with the parameter which is a function of the probability η. , Includes computing means 21, which is configured to execute, r times (r 1). Specifically, as described in detail so far, authentication is approved when the sum of the Hamming weights of the error vector e obtained over r successive substitutions is less than the parameter which is the threshold value T.

X, Y private key (binary matrix of n × m) a, b binary vector c noise binary vector e error vector z response vector η probability