3 Proposed Protocol

The goals of this project is to design a protocol that the reader authenticate the incoming user while preserving the privacy of the user. The use of this protocol may, for instance, be used in application, such as secure entry systems. We will not, however, focus on protection against availability or physical tampering attack. This simple protocol involves two flows with a challenge-response approach. In addition, it uses nonces (random numbers) to provide anonymity for each user response, so that reader would have no knowledge of user’s identity during the process of authentication. Thus, the privacy is preserved.

3.1 Preliminary Assumption

The protocol uses a hash function, and a pseudo-random number generator.

3.1.1 Hash

A hash function h is an one-way function that maps an arbitrary length input to a k-bit output, i.e. h : {0,1}^*→{0,1}^k. The typical requirement for this cryptographic checksum functions are

• Pre-image resistance: for any given input x, it is computationally efficient to compute h(x). However, given an arbitrary output y, it is computationally infeasible to find an input such that h(x) = y.
• 2nd pre-image resistance: given x, it is computationally infeasible to find x′≠x, such that h(x) = h(x′)
• Collision resistance: it is computationally infeasible to find any pair of distinct inputs x and x’, such that h(x) = h(x′)

3.1.2 Pseudo-random Number Generator

A pseudo-random number generator (PRNG) is a deterministic algorithm, which given an input seed and outputs a binary sequence of length k, which appears to be random.

3.2 Assumption

Our protocol works under the following assumption

• Each user device has a Psuedo-random number generator, that performs a 16-bit number at (seemly) random.
• Each user device has a rewritable memory, which is used to preload two secret function, and its identity parameter.
• Each user device is implemented with a standardized cryptographic hash functions, such as Sha-1, which was pre-assumably implementable on RFID tags.
• The reader and the user device communicate over an insecure channel, so their communications are subject to eavesdropping.

3.3 Set Up Phase

Each user t is preloaded with two polynomial functions:

On the other hand, reader r is preloaded with three different polynomial functions

Those coefficients needs to be carefully selected, so that A(x,y) ⋅C(x) + B(x,y) ⋅D(x) + E(x) ≡ 0 is guaranteed. The coefficients can be found via algorithms that solves linear equations.

3.4 Authentication Process

The protocol is summarized in Figure.1

1. Reader: A reader generates a random bit-string γ₀ {0,1}^l, and sends this nonce M₀ =< γ₀ > to user t.
2. User: The user i generates a random bit-string γ₁ {0,1}^l as temporary session secret, and computes γ₂ = h(γ₀|γ₁), where h(x) is our hash function. Next, user computes its polynomial functions A(γ₂,t) and B(γ₂,i), and sends back to the reader with message M₁ =< γ₁,A(γ₂,t),B(γ₂,t) >.
3. Reader: The reader is not able to compute γ₂ = h(γ₀|γ₁), and computes its secret functions with γ₂. The reader will authenticate user t, if A(γ₂,t) ⋅ C(γ₂) + B(γ₂,t) ⋅ D(γ₂) + E(γ₂) ≡ 0; reject this user, otherwise.

3.5 Security Analysis

The protocol has satisfied following privacy and security properties

• Strong Authentication: The identity of user i is never exposed in any phase of authentication, even to a valid reader. Therefore, the user identity stays anonymous.
• User Impersonation Attack: For a attacker to clone a user, it needs to compute valid coefficients {a₁₁,a₁₀,a₀₁,a₀₀},{b₁₁,b₁₀,b₀₁,b₀₀}, which were pre-computed onto user and stayed secret in transmission. Thus, it is hard to compute such valid pairs of coefficients without any prior acknowledgement of the user. However, an attack under the scenario of compromission of a legitimate reader enables the adversary to produce a valid user, and we will address this issue and solution below.
• Reply Attack: The scheme resists reply attack, since it is a challenge-response authentication protocol using several random numbers generated as temporary secret for each session. The message M₀ and M₁ are composed with those nonces, and thus those message cannot be reused in future sessions.

3.6 Potential Attack

If a reader is compromised, then C(x),D(x),E(x) are compromised. If the attack can somehow figure out Â,, such that Â(x,y) ⋅C(x) + (x,y) ⋅D(x) + E(x) = 0. That means some other user device î with secret functions Â, is compromised.

3.6.1 Improved Scheme

To prevent this attack, for any reader that could be potentially compromised. We preloaded the reader functions with elliptic curve point α to convert the numeric output into points on the elliptic curve in finite field, i.e. α × C(x),α × D(x),α × E(x). In this scenario, the authentication equation becomes

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

3.6.2 Tag Compromise Attack

The proposed improvement seems to be promising against eavesdropping attack. However, its vulnerability is shown when multiple tags are compromised. All tags are preloaded with the same coefficient < a₁₁,a₁₀,a₀₁,a₀₀,b₁₁,b₁₀,b₀₁,b₀₀ >. If an attacker has compromised k tags, then the attacker could obtain the following linear equations:

3.6.3 Misuse of Anonymous Authentication

While the anonymous authentication provides user privacy, but this property may be misused to crash the system. The most obvious approach is that when an attack compromise one or several valid user devices, and launch multiple DoS attack simultaneously. The entry system would follow with a shut-down of authenticating service. Since this simple model does not support any mechanism to further identify who the user was, hence, the attacker could go away without leaving any trace after his successful attack.