Method of authentication of an entity by a verifying entity

Translation of description of equivalent WO 2008149031 A2

METHOD FOR AUTHENTICATION OF AN ENTITY BY AN ENTITY

p0002Auditor

p0003The present invention relates to a method for authenticating an entity to authenticate to a verifier entity.

p0004The invention finds a particularly advantageous application in the field of cryptographic authentication protocol chips at very low cost, with or without contact, including radio frequency RFID tags ( "Radio Frequency IDentification").

p0005Electronic chips at low cost, RFID type for example, are used in many applications such as labeling and tracing objects (drugs, library books, etc.), or the production and verification tickets or electronic tickets, such as tickets.

p0006Whatever the application in question, it is necessary to prevent fraud that may arise based on the falsification of chips, especially their copying or cloning, or replay data they transmit. To protect applications against such attacks, it is imperative to conduct an authentication chip in their interactions with one player.

p0007However, any authentication protocol between an entity to be authenticated as a chip at low cost, and a player acting as Auditor entity must consider the extreme limitation of computational resources of such chips, which are usually hard-wired logic.

p0008Recently, it was proposed (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) symmetric authentication protocol designed specifically to meet the needs of RFID chips. This protocol is known as HB + (Hopper-Blum). Figure 1 shows data exchanges made during the HB + protocol between the prover and the entity Auditor.

p0009As can be seen in this figure, the entity to be authenticated, a chip

p0010RFID for example, and the entity Auditor, a reader of the chip, share a pair of secret keys x and y consisting of binary n-bit vectors.

p0011These secret keys are stored in storage means of the chip and the reader respectively referenced 10 and 20.

p0012HB + protocol runs on successive laps r. Each turn, the chip draws lots (block 100) and transmits (1) to drive a binary vector b of n bits. Similarly, the player draws lots (block 200) and forwards (2) to the chip binary vector of n bits. The draw of the b vectors and is performed according to a law of uniform probability.

p0013The chip then responds to the challenge launched by the reader by calculating (block

p0014120) and passing it (3) z = a noisy response "x ®b" there ® v, where • represents the operation modulo 2 scalar product ® and the modulo 2. v is a noise bit fired exits through the chip (block 1 10); it is set to 1 with a probability η <1/2 and 0 with probability (I - / 7).

p0015The reader rejects the current round (block 210) if the z response received does not check the relationship z = a "x ®b" there; in this case, a counter of the number of rejected nbr rounds is incremented by one unit (block 220). After r rounds, recorded by a counter of the number of laps nbt (block 250), authentication is accepted (block 240) if and only if the number of rejected nbr turns counter is below a given threshold t (block 230). The value of t is of course a function of the probability η; a single value of t is for example t = η rx.

p0016Although the exchange of HB + protocol proposed are structured in r rounds of three passes, it is possible to bring an exchange of three assists in calculating and transmitting once r values ​​of b, a and z.

p0017The advantage of the HB + protocol is the simplicity of the authentication calculations.

p0018In addition, it draws its strength from the difficulty of the problem LNP ( "Low Parity with Noise") to find a solution to a linear system noisy. Finally, the HB + protocol has, by comparison with the HB protocol historically prior and which differed in that the noisy response did not include a term b * y, due to the masking effect induced by the binary vector b coupled to the secret key therein; Indeed, the HB protocol was sensitive to attacks consisting for the opponent to send a constant challenge and listen to the answers of the player; the most common response being a 'x, and being known, one could initially get a "x for a sufficient number of values ​​of a, and secondly deduce x by solving a linear system.

p0019However, the HB + protocol has disadvantages that forbid it to be used effectively in practice.

p0020A first drawback is that even if, as we have seen, it is resistant to certain active attacks has, this protocol remains vulnerable to other attacks encountered when an opponent has access to the results in terms of success / failures of successive authentications.

p0021Such an attack is to intercept the challenge during its transmission from the reader to the chip and to modify the bits in succession. If, for example, the first bit of a is changed, it is understood that if the result is not changed as a result of this change, it can be concluded that the first bit of the secret vector x is probably 0. Conversely, if the result is changed, the first x bit is probably equal to 1. for all n bits of x, just change the second bit has to know the second bit of x, and so on up not .

p0022A second drawback of HB + protocol is that it leads to a number of false alerts excessively high, a false alarm is defined as the rejection of legitimate chips authentication. For example, with the values ​​"= 224 bits / 7 = 0.25, r = 100 rpm and t = η = xr 25, the false alarm rate is 45%, value totally unacceptable. The rate of false positives, that is to say, successful authentication for chips answering at random, was close to 3^• 10^-7 .

p0023If instead of taking the expected value for t = η xr 25, it takes a higher value such as 35, the false alarm rate down 1%, which is still unacceptable, but the false positive rate increases to about 1.7 to 10^"3.

p0024A third drawback of HB + is the excessive complexity that it induces in the communication between the chip and the reader. With the same numbers as above, you can see that it is necessary to exchange 44900 bits on each authentication, ie, to each of the 100 laps, 224 b bits to 224 bits for a, and a bit to the result z.

p0025We see that even with a rate of 10,000 bits / s, it takes more than four seconds to the reader to authenticate a chip, which remains a prohibitive value for the ergonomics of the system, not including food problems of the chip that result.

p0026The invention therefore relates to a method for authenticating an entity to a verifier entity, said entities sharing a pair of secret keys X and Y. Said method is characterized in that said secret keys X and Y are binary matrices nxm (n, m> l), and in that it comprises repeating steps r times (r> 1) comprising:

p0027- For the prover and the entity auditor to exchange binary vectors and alleging b n bits at random by the Auditor entity and the entity to be authenticated, and for the entity to be authenticated, draw lots a noise binary vector c of m bits, each of said m bits being equal to 1 with a probability η less than 1/2, and calculate and transmit the entity Auditor az response vector of m bits equal at z = aX bY ® ® c,

p0028- For the entity auditor to calculate the Hamming weight of an error vector e = z ® ®bY aX, then, for the entity auditor to accept authentication if the weight of the vectors r d Hamming error e satisfy a relation of comparison parameter to a function of the probability η.

p0029Thus, we can see that the process according to the invention provides, in relation to HB + protocol, better resistance to attacks of modifying the bits of the challenge in order to reconstruct the secret X. Indeed, if the first bit of a is changed, this change affects the products of this bit with the first bits of the m columns of X, which also affects the m bits of the product aX and therefore the response z as a whole. Therefore, it is not possible to infer from the observation of the effect of a change in a bit on the authentication result of any information about the secret X since many of the m bits of z may be changed without that we knew their number nor their position, whereas in the case of the HB + protocol any modification of a bit of a directly affects the response z, the latter being constituted as a single bit.

p0030Regarding the performance of the method, object of the invention, it should be noted that the z response at every turn is writing on m bits, everything is in substance as if it was on m turns into one. It follows that, in a first end position, can be reduced to an order of the factor m the number of turns, so in practice limit the number of rounds to one, which keeps performance HB + protocol in false alarm rate, but by reducing the number of bits exchanged r (2n + \) to (2n + m), ie of 44900 bits to 576 bits, with "= 224 and m = 128 this represents a considerable gain. We understand from this example the interest of the invention enable to limit the number r 1 of rounds, which is impossible to consider in the case of HB + protocol.

p0031In a second extreme situation, the number of turns is the same. In this case, the number of exchanged data increases slightly, but against the false alarm rate becomes insignificant.

p0032Of course, a realistic situation will be chosen between these two extremes with both a reduction in the false alarm rate and the number of bits exchanged between the chip and the reader. Regardless, it is clear that the present invention provides better performance than the HB + protocol in terms of the false alarm rate and amount of information to be exchanged between the two entities.

p0033In a particular embodiment of the invention, the matrices X and Y are Toeplitz matrices. chips will be seen in detail later this advantageous arrangement limits the storage capacity and readers (n + m - 1) instead of n × m in the case of selected matrices any. Another advantage is to simplify the calculation of άX and bY products.

p0034The invention also relates to an entity to be authenticated by a verifying entity, said entities sharing a pair of secret keys X and Y, remarkable in that said entity to be authenticated comprises secret key storage means X and Y consist of binary matrices n × m (n, m> l), means of communication with the entity's auditor, and computing means for performing time r (r ≥ l) the steps: - to draw lots and transmit to the verifying entity a binary vector b of n bits,

p0035- Receiving from the entity a Auditor binary vector of n bits,

p0036- To draw lots of noise a binary vector c of m bits, each of said m bits being equal to 1 with a probability η less than 1/2, and calculate and transmit to the Auditor entity az response vector m bits equal to z = aX @bY @ c.

p0037The invention further relates to a computer program comprising program instructions for implementing the steps performed by said entity to be authenticated when said program is executed by a computer forming part of said means for calculating the prover.

p0038The invention further relates to a verifying entity sharing a pair of secret keys X and F with an entity to be authenticated, remarkable in that said verifying entity comprises secret key storage means X and Y consist of binary matrices nx m (n, m> l), communication means with the entity to be authenticated, and means of calculation able to perform r times (r ≥ l) the steps of:

p0039- Receiving from the entity to be authenticated a binary vector b of n bits,

p0040- To draw lots and send to the entity to be authenticated a binary vector of n bits, - to receive the prover an m-bit z response vector,

p0041- To calculate the Hamming weight of z = e ® ® error vector aX bY and accept authentication if the Hamming weight of the error vectors e r satisfy a relation of comparison with a parameter (T, t) according to a predetermined probability η.

p0042Finally, the invention relates to a computer program comprising program instructions for implementing the steps carried out by said verifying entity when said program is executed by a computer forming part of said means for calculating the verifying entity.

p0043The description given by way of example, which follows in the accompanying drawings explains in what the invention is and how it can be achieved. 2 shows exchanges between the prover and the entity Auditor during the process according to the invention.

p0044Figure 3 is a diagram of an entity to be authenticated according to the method of Figure 2.

p0045Figure 4 is a diagram of a verifying entity to authenticate the entity of Figure 3 according to the method of Figure 2.

p0046In Figure 2 is illustrated an authentication method in a verifying entity, a chip reader with or without contact, for example, to verify the identity of an entity to be authenticated, which in this example may be an RFID chip . The process described in Figure 2 is a so-called symmetric when both entities, chip and reader share the same secret key. Thereof, designated X and Y are binary matrices nxm (n, m> l) having n rows and m columns. Secret keys X and Y are stored in storage means of the chip and the reader respectively referenced 10 and 20 in Figure 2 and in Figures 3 and 4.

p0047The process according to the invention is structured in repeated steps r times (r> 1). An "r time" that trade between the chip and the reader can be performed sequentially r rounds three assists, as shown in Figure 2, where the number of nbt towers is incremented by 1 at every turn by a counter (block 250), or in parallel on three passes, each pass comprising transmitting r a data entity to another. In the example in Figure 2, the chip 1 raffling each round (block

p0048100) and transmits (1) to the reader 2, a single-line binary vector b of n bits. The reader transmits 2 (2) while the chip 1 a challenge (block 200) is an n-bit binary vector-liner drawn. The draw binary vectors b and is made according to a uniform distribution of 0 and 1 bits.

p0049In response to the challenge, the chip 1 transmits (3) the reader 2 a binary vector-liner z of m bits equal to the sum modulo 2 z = aX ® bY ® c (block 120), where c is a binary vector-liner m-bit noise, drawn (block 1 10 ') by the chip 1 according to a probability distribution, ensuring that each bit of c is equal to 1 with equal probability, or less than or equal to a η parameter less than 1/2. To do this, each bit of the noise vector c can be drawn independently according to a Bernoulli distribution with parameter η <1/2. The noise vector c can also be drawn among all m-bit vectors for which the sum of bits or Hamming weight is not greater than or equal to the value xm η with η <\ l 2. Of Naturally, the noise vector c can be drawn by the chip while it raffling binary vector b which we recall that serves masking the active attacks on the vector.

p0050Each turn, the reader 2 calculates (block 210 ') an error vector e m bits equal to z = e ® aX ®bY where z is the response vector sent by the chip 1 and the Hamming weight PH (e) (block 220 ') of the error vector e obtained.

p0051After r rounds, the acceptance or rejection of the authentication of the chip 1 by the reader 2 is determined from the r Hamming weight PH (e) of an error vectors obtained at every turn and comparing them to a dependent parameter η probability.

p0052Several strategies are possible.

p0053A first strategy, shown in Figure 2, is to accept authentication (block 240 ') if and only if the sum S of the Hamming weight of the error vectors e r (block 221') is less than a threshold T given (block 230), for example equal to r (η + ε) m where ε is a margin of less than 1/2, possibly zero. A second strategy is to accept the authentication if and only if the Hamming weight of the error vector e obtained in each round is smaller than a threshold t.

p0054A third strategy is to accept the authentication if and only if the Hamming weight of the error vector e obtained in each turn is equal to a value t.

p0055In the latter two cases, the parameter t is (η + ε) m where ε is a margin of less than 1/2, possibly zero.

p0056Taking r = 1, n = 256, m = 128, η = 0.25 and a draw of the noise vector c among the binary vectors of length 128 and Hamming weight 32 or η xm, the authentication of the chip will be accepted according to the third strategy above if and only if the weight of the error vector e is at every turn exactly equal to 32, this with ε = 0.

p0057In this example, it can be seen that the total length trade is only 640 bits, or (2n + m). On the other hand, one can observe that the false alarm rate is strictly zero and that the false positive rate for an attack of trying a random value z is around 10⁸ , Which is quite acceptable in practice.

p0058In Figure 2, the sequence of exchanges between the chip 1 and player 2 is: b sending the reader has sent to the chip, the draw of the chip c and z sending the reader. However, note that another sequence could also be used, ie: sending a ivy, draw b and c by the chip and sending b and z to the reader. The latter sequence has the advantage of reducing the number of exchanges. According to an embodiment which greatly reduces the amount of memory needed to store the X and Y plates and the complexity of the calculations to be performed by the chip and the entity Auditor, each of X and Y matrices can be selected within a sub-set of strict all nxm matrices and described in the chip using a number of bits strictly less than n × m. Thus, for example, the amount of memory required to store each matrix may be reduced to only (n + m -1) where X and Y are Toeplitz matrices, namely matrices with constant coefficients along diagonals, and whose set of coefficients is fully determined by the coefficients of the first row and the first column. If X is a Toeplitz matrix and if X_1} denotes the coefficient of the i-th row and the j - th column, x_h] is equal to v,₊if u * ^East greater than or equal to j, and χ_{U] → ι} on the other hand.

p0059The following embodiment allows the product very effectively one bit of a binary vector, for example, and a Toeplitz matrix, X, for example, described by means of (n + m - 1) coefficients of the first row and the first column, and using two m-bit registers, one for calculating the current line of the matrix and the other, initialized to 0, to accumulate the partial results of the matrix-vector product. The first register is initialized with the first line of X, then each bit of the vector is treated as follows: if the current bit of a is equal to 1, the value of the current line of X is combined with "or" bitwise exclusive with the current value of the accumulation register partial results. Otherwise, the current value of the register is not changed. In both cases, when the current line is not the last line of the matrix X, the register holding the current row of this matrix is ​​maintained by rotating the contents of the register one bit to the right, followed by the copy in the left cell of the register of the coefficient of the first column for the new current line.

p0060As shown in Figure 3, the chip 1 to be authenticated by the reader 2, these two entities sharing a pair of secret X and Y keys, includes means 10 for storing secret keys X and Y consist of binary matrices nxm (n, m> l), means 12 for communication with the reader 2, and means 1 1 calculation able to perform r times (r ≥ l) the steps according to the method described with reference to Figure 2:

p0061- To draw lots and send to the reader 2 a binary vector b of n bits, - to receive the reader 2 has a binary vector of n bits,

p0062- To draw lots of noise a binary vector c of m bits, each of said m bits being equal to 1 with a probability η less than 1/2, and calculate and transmit to the reader 2 z response vector of m bits equal to z = aX ®bY ® v.

p0063Similarly, one can see in Figure 4 a reader 2 responsible for authenticating a smart 1, comprising means 20 for storage of secret keys X and Y consist of binary matrices n × m (n, m> l), means 22 communication with the chip 1 to be authenticated, and means 21 for calculation adapted to perform r times (r ≥ l) the steps according to the method described with reference to Figure 2:

p0064- To receive from chip 1 to be authenticated a binary vector b of n bits, - to draw lots and send the chip 1 a binary vector AE n bits,

p0065- To receive the chip 1 z? E m bits response vector,

p0066- To calculate the Hamming weight of z = e ® ® error vector aX bY and accept authentication if the Hamming weight of e r error vectors satisfy a comparison relation to a function parameter the probability η. In particular, authentication is accepted if the sum of the Hamming weight of an error vector obtained for the r rounds is below a parameter equal to a threshold T, as has been described in detail above.