4.2 The Naive Authentication Protocol

Set-up Phase
When each tag is manufactured, each smart tag is associated with a secret identifier, u, and two polynomial functions:

When a RFID reader is initialized, the reader is preloaded with an elliptic point α, and three different polynomial functions

Communication Phase
Each transmission starts, when the reader first sends a random session nonce, γ₀ to the tag. After receiving data from reader, the tag generate a random session nonce of its own, called γ₁, and hash the concatenations of these two random session. Afterwards, the user computes its secret functions A and B given γ₂. That is, γ₂ = H(γ₁|γ₀). Last, the tag sends back a packet of data < γ₁,A(γ₂,u),B(γ₂,u) > to reader side.

Authentication Phase
With the carefully selected coefficients, the authentication process could be achieved by checking the following equality, as shown in the figure 1 below⁵:

	Ĉ(γ2) × A(γ2,u) + (γ2) × B(γ2,u)
	= α × C(γ2) ⋅ A(γ2,u) + α × D(γ2) ⋅ B(γ2,u)
	= α ×C(γ2) ⋅ A(γ2,u) + D(γ2) ⋅ B(γ2,u)
	= α × E(γ2)			(Equation 6)

4.2.1 Security Analysis

Vulnerability to Tag Compromise Attack
All tags are preloaded with the same coefficient < a₁₁,a₁₀,a₀₁,a₀₀,b₁₁,b₁₀,b₀₁,b₀₀ >. Assume an attacker has compromised k tags, and each secret function in the tag could leak out 2 pieces of meaningful information about the tag secret u. In other words, the attacker could obtain the following equations:

Tag 1:
…
Tag k:

If the attacker could fix the dynamic input x, such as having a rogue reader interrogating the compromised tags, then x would no longer be an effect. In that case, there would be in total 4k equations for k different tags, and the unknowns include _{(k+8) unknowns}. Since the number of variables is less than the number of equation in the linear system, thus, the attacker is able to reveal the secret parameters by solving this linear system.