Expected loss analysis for authentication in constrained channels

1. Introduction

Traditionally, authentication is assumed to be taking place on an error-free channel [25,26], and error analysis is performed separately from cryptographic analysis of protocols. However, a number of authentication protocols have been proposed [3–7,16–18,21,22,24,27], where at least some part of the authentication is performed during a challenge–response phase lasting n rounds with no error correction. These protocols are known as distance-bounding protocols and are employed as the main countermeasure against relay attacks by timing transmission delays. However, channel noise necessitates the acceptance of some responses which are not perfectly correct. In addition, increasing n carries a significant cost. The problem is to strike an optimal balance between the increased number of rounds, the probability of falsely authenticating an illegitimate party, and failing to authenticate a legitimate party.

For example the rapid-bit exchange phase in an RFID distance-bounding protocol (i.e. [16]), satisfies these criteria. This is a phase, lasting n rounds, where an equal number of challenges and responses, consisting of single bits, are sent. Since there is no error correction during that phase, some responses received from a legitimate user may be erroneous, due to transmission errors in either direction. This necessitates the use of a tolerance threshold τ, such that if the number of erroneous responses is lower than τ, the communicating party is nevertheless authenticated. Unfortunately, while increasing the number of rounds decreases the probability of incorrect authentication, it also increases communication costs, which is particularly undesirable in power-constrained devices such as RFID tags. The problem then is how to select n, τ in an optimal manner and how to define optimality in the first place.

This paper performs an expected loss analysis of the authentication problem. This is necessary, because of the non-trivial cost of increasing the number of rounds n, the lack of an error-free channel and the need to trade off optimally the costs of incorrectly authenticating an illegitimate entity, or failing to authenticate a legitimate one.

We place the problem in a decision-theoretic framework. We assign a loss ℓ A to the event that we authenticate a malicious party A – which we call the attacker – a loss ℓ U to the event that we fail to authenticate a valid party U – which we call the user – and a loss ℓ B for each round of the challenge–response phase, such that the total communication cost is n ℓ B . Adding a non-negligible cost to the communications is of fundamental importance in resource-constrained environments. Otherwise, n can be made as large as necessary to make the probability of authentication mistakes infinitesimal. Our goal is to select n and τ so as to minimize the expected loss E L of the authentication system. This is achieved through a finite sample analysis.

We should note here that a preliminary version of this paper was presented at INFOCOM [15] and as a technical report at [14]. The current paper features corrections, an extended theoretical analysis, additional experiments and a more realistic attacker model. The main differences are that we consider a stronger attacker model, present an improved choice for the threshold when the gap between the attacker and user is large, as well as new experimental results where we detail the effect of parameters on the choice of threshold and number of rounds. Finally, we present a more extensive experimental comparison with a likelihood-ratio threshold and the exact minimax solution.

The paper is organized as follows. Section 2 introduces notation and our framework. Section 3 contains the expected loss analysis under noise. In particular, Section 3.1 suggests a method to calculate the threshold accompanied by finite sample upper loss bounds and a matching lower bound, while Section 3.2 provides a further loss bound by selecting a near-optimal number of rounds n. These results only require two reasonable assumptions: that the expected error of the attacker is higher than that of the user and that the errors are independent in each round, something that can be achieved by appropriate protocol design. In particular, we analyze methods for selecting a nearly-optimal threshold and number of rounds, prove bounds on the expected loss for our choices, show their dependence on the problem parameters and discuss their relation with the optimal (minimax) solution. Section 4 applies the above analysis to two existing RFID protocols, and shows the effect of channel noise on the expected loss, as well as on our bounds. Since the above analysis requires bounds on the errors made by users and attackers to be known, Section 5 suggests a high-probability method for estimating the channel noise in order to obtain them, under a powerful attacker model. Section 6 presents two sets of simulation experiments. In the first, we investigate the stability of the noise evaluation method under varying noise. This is done both for our method of selecting the threshold with a Bayesian likelihood ratio test, which requires additional assumptions. In the second set of experiments, we directly compare the performance of those two methods as noise and the other problem parameters vary with the minimax solution. Finally, Section 7 concludes the paper with a discussion of related work. For completeness, the Appendix provides known auxiliary results for the finite sample and the Bayesian likelihood ratio test derivations.

2. Preliminaries

We consider sequences x = x 1 , … , x n with all x i in some alphabet X and x ∈ X n . We write X ∗ ≜ ⋃ n = 0 ∞ X n for the set of all sequences. We use ≜ to indicate a definition. P ( A ) denotes the probability of event A, while E denotes expectations so that E ( X | A ) = ∑ u ∈ Ω u P ( X = u | A ) denotes the conditional expectation of a random variable X ∈ Ω when A is true. In addition, I { A } is an indicator function equal to 1 when A is true and 0 otherwise. Finally, we use [ k ] ≜ { 0 , 1 , … , k } to denote the set of integers up to k.

We consider additive-error challenge–response authentication protocols. In such protocols, a verifier V grants access to a prover P , if the latter can demonstrate its identity via possession of a shared secret. The protocol has three phases: (i) An initialization phase; (ii) A challenge–response phase, lasting n rounds, performed without error correction under noisy conditions; (iii) A termination phase. During the challenge–response phase the verifier V sends n challenges c 1 , … , c n , with c k ∈ X , to the prover  P , which responds by transmitting n responses r 1 , … , r n , with r k ∈ X . We use c = ( c k ) k = 1 n and r = ( r k ) k = 1 n to denote the complete challenge and response sequences, respectively. The verifier V uses an error function E : X × X → [ 0 , 1 ] to calculate an error ε i = E ( r i , c i ) for the ith round. The errors when interacting with a valid user may be non-zero due to noise constraints in the channel. However, as the attacker has to resort to guessing the responses, the expected error of the attacker should be higher than that of the user.

In order to trade off false acceptances with false rejections, we use a threshold value τ, such that a prover is accepted if and only if the total error observed is smaller than τ. The verifier V calculates the total error ε ≜ ∑ i = 1 n ε i , and rejects the prover P , if and only if ε ⩾ τ .

The relation of ε to the challenge and response strings c and r strongly depends on the protocol. In order to make our analysis generally applicable, we make the following assumption about the protocol.

Assumption 1.

We assume there exists some p A ⩽ E ( ε i | A ) , a lower bound on the expected per-round error of the attacker and some p U ⩾ E ( ε i | U ) , an upper bound on the error of a legitimate user. In addition, we assume that the protocol is such that all errors are independently (but not necessarily identically) distributed.

These bounds depend on the noise during the challenge–response phase and on the protocol under consideration. The independence assumption can be satisfied for the interaction with the user when the channel noise is independent. The interaction with the attacker requires constructing an appropriate protocol, so that learning attackers are precluded. We shall return to this issue in Section 4, which discusses specific protocols.

3. Expected loss analysis

In order to perform an expected loss analysis, we must specify the potential losses arising from every aspect of the decision process defined by the protocol. For every round of the challenge–response phase, we suffer loss ℓ B , due to the cost in time and energy of transmission. In addition, we suffer a loss of ℓ A for each false acceptance and a loss ℓ U for each false rejection.1

¹

These losses are subjectively set to application-dependent values. Clearly, for cases where falsely authenticating an attacker the impact is severe, ℓ A must be much greater than ℓ U . In addition, ℓ B must be sufficiently low that running the protocol at all is worthwhile.

Given that we perform n rounds, we define the total loss when the prover P is either the legitimate user U or the attacker A as given by: L = n ℓ B + ℓ U , if ε ⩾ τ and P = U , n ℓ B + ℓ A , if ε < τ and P = A , n ℓ B , otherwise .(1) Armed with this information, we can now embark upon an expected loss analysis. We wish to devise an algorithm that guarantees an upper bound on the expected loss E L of the authentication system. To start with, we note that the expected loss when the communicating party is an attacker A or the user U, is given respectively by: E ( L | A ) = n ℓ B + P ( ε < τ | A ) · ℓ A + P ( ε ⩾ τ | A ) · 0 , (2) E ( L | U ) = n ℓ B + P ( ε < τ | U ) · 0 + P ( ε ⩾ τ | U ) · ℓ U . (3) The expected loss is in either case bounded by the worst-case expected loss: L ≜ max { E ( L | A ) , E ( L | U ) } ⩾ E L .(4) If we can find an expression that bounds both E ( L | A ) and E ( L | U ) , we automatically obtain a bound on the expected loss, E L . First, we shall see how to select a near-optimal threshold, given a fixed number of rounds of the protocol. Then we shall look at two approximate methods for selecting the number of rounds itself. These will be compared with the optimal (but computationally more expensive) solution.

3.1. Choice of threshold

We want a threshold τ such that no matter whether the prover P is the attacker A or the legitimate user U the expected loss E ( L | P ) is as small as possible. As we increase the threshold τ, E ( L | P = U ) decreases, while E ( L | P = A ) increases and vice-versa. Intuitively, to minimize the worst-case expected loss, we can use τ such that E ( L | P = A , τ ) = E ( L | P = U , τ ) , which corresponds to an equalizing strategy. We shall define a threshold τ minimizing an upper bound on the worst-case expected loss in Theorem 1 on page 314. As an intermediate step, we obtain a bound on the worst-case expected loss for any given threshold τ. Formally, we can show in the following lemma.

Lemma 1.

Let ε i ∈ [ 0 , 1 ] be the error of the ith round. If, for all i > 0 , it holds that E ( ε i | A ) ⩾ p A and E ( ε i | U ) ⩽ p U , for some p A , p U ∈ [ 0 , 1 ] such that n p U ⩽ τ ⩽ n p A , then: L ( n ; τ ) ≜ n ℓ B + max { e − 2 n ( n p U − τ ) 2 ℓ U , e − 2 n ( n p A − τ ) 2 ℓ A } ⩾ max { E ( L | A ) , E ( L | U ) } ⩾ E L . (5)

Proof.

The expected loss when P = A , is simply: E ( L | A ) = n ℓ B + P ( ∑ i ε i < τ | A ) ℓ A ⩽ n ℓ B + P ( ∑ i ε i − n E ( ε i | A ) < τ − n p A | A ) ℓ A ⩽ n ℓ B + e − 2 n ( n p A − τ ) 2 ℓ A , the last two steps used the fact that E ( ε i | A ) ⩾ p A and the Hoeffding inequality (21). Specifically, in our case, Lemma 3 (page 326) applies with X i = ε i . Then, it is easy to see that μ i = E ( ε i | A ) for all i and b i − a i = 1 , so P ( ε < n p A + n t | A ) ⩽ e − 2 n t 2 . By setting τ = n p A + n t , we obtain t = ( τ − n p A ) / n , which we can plug into the above inequality, thus arriving at the required result.

The other case, P = U , is handled similarly and we conclude that E ( L | U ) ⩽ n ℓ B + e − 2 n ( n p U − τ ) 2 ℓ U .  □

The given upper bound is tight, as can be seen by the following lemma, which proves a matching lower bound for the example of Bernoulli-distributed errors.

Lemma 2.

Modifying our assumptions slightly, let ε i ∈ { 0 , 1 } be the Bernoulli-distributed error of the ith round, such that, for all i > 0 , it holds that P ( ε i | A ) = p A and P ( ε i | U ) = p U , for some p A , p U ∈ [ 0 , 1 ] such that n p U ⩽ τ ⩽ n p A , then: E L ⩾ min { E ( L | A ) , E ( L | U ) } ⩾ n ℓ B + ( n τ ) τ min { ℓ A p A τ ( 1 − p A ) n − τ , ℓ U p U τ ( 1 − p U ) n − τ } . (6)

Proof.

The expected loss when P = U , is simply: E ( L | U ) = n ℓ B + P ( ∑ i ε i ⩾ τ | U ) ℓ U ⩾ n ℓ B + P ( ∑ i ε i = τ | U ) ℓ U = n ℓ B + n τ p U τ ( 1 − p U ) n − τ ℓ U ⩾ n ℓ B + ( n p U τ ) τ ( 1 − p U ) n − τ ℓ U . The other case, P = A , is handled similarly and we conclude that E ( L | A ) ⩾ n ℓ B + ( n p A τ ) τ ( 1 − p A ) n − τ ℓ A .  □

To see that the upper and lower bounds match, consider that P = U and τ = n c with c < 1 . Then Lemmas 1 and 2 give us: n ℓ B + e − 2 n ( n p U − τ ) 2 ℓ U ⩾ n ℓ B + ( n p U τ ) τ ( 1 − p U ) n − τ ℓ U , e − 2 n ( n p U − τ ) 2 ⩾ ( n p U τ ) τ ( 1 − p U ) n − τ , e − 2 ( p U − c ) 2 n ⩾ e [ c ln p U c + ( 1 − c ) ln ( 1 − p U ) ] n . Thus, the upper and lower bounds given for the expected loss ( E L ) are of the same order with regard to n.

Having bounded the loss suffered when choosing a specific threshold, we now choose a threshold τ ˆ n ∗ that minimizes the above bound for fixed n. In fact, we can show that such a threshold results in a particular upper bound on the expected loss.

Theorem 1.

Let ρ ≜ ℓ A / ℓ U and select τ = τ ˆ n ∗ ≜ n ( p A + p U ) 2 − ln ρ 4 Δ .(7) If n p U ⩽ τ ⩽ n p A , then the expected loss E L is bounded by: E ( L | n , τ ˆ n ∗ ) ⩽ L 1 ( n ) ≜ n ℓ B + e − n 2 Δ 2 · ℓ A ℓ U(8) with Δ ≜ p A − p U .

Proof.

Substitute (7) in the first exponential of (5) to obtain: e − 2 n ( n p U − τ ˆ ∗ ) 2 ℓ U = e − n 2 Δ 2 e − ln 2 ρ 8 n Δ 2 ℓ A ℓ U . It is easy to see that the exact same result is obtained by substituting (7) in the second exponential of (5). Thus, both E ( L | A ) and E ( L | U ) are bounded by the same quantity and consequently, so is max { E ( L | A ) , E ( L | U ) } . Thus, L ( n , τ ˆ n ∗ ) ⩽ n ℓ B + e − n 2 Δ 2 ℓ A ℓ U , where we simplified the bound by noting that ln 2 ρ 8 n Δ 2 > 0 .  □

The intuition behind the algorithm and the analysis is that it is possible to bound the probability that A makes less errors than expected, or that U makes more than expected. For this reason, the τ ˆ n ∗ chosen in the theorem must lie between n p U and n p A . We now shall find choices for n which upper bound the overall loss.

3.2. Choice of the number of rounds

Using similar techniques to those employed for obtaining a suitable value for the threshold, we now indicate two choices for the number of rounds n and provide a matching bound on the expected loss. The first, originally mentioned in [14,15] can be used for any value of Δ. In this paper, we also introduce a significantly improved one, which can be used as long as Δ is not too small.

The first choice of n approximately minimizes a simple upper bound on the worst-case expected loss. In fact, the following theorem shows that this choice guarantees a specific amount of loss.

Theorem 2.

Assume ℓ A , ℓ U , ℓ B > 0 . If we choose τ = τ ˆ n ∗ and n = n ˆ ∗ ≜ 1 + 2 C K − 1 C ,(9) where C = Δ 2 and K = ℓ A ℓ U / ℓ B , then the expected loss E L is bounded by: E ( L | τ ˆ n ∗ , n ˆ ∗ ) ⩽ L 2 ≜ 8 K / C · ℓ B = 8 ℓ B ( ℓ A ℓ U ) 1 / 4 Δ .(10)

Proof.

We shall bound each one of the summands of (8) by 2 K / C · ℓ B . For the first term we have: n ℓ B = 1 + 2 C K − 1 C ℓ B ⩽ 1 + 2 C K C ℓ B ⩽ 2 C K C ℓ B = 2 K C ℓ B . For the second term, by noting that e x ⩾ 1 + x , we have: ℓ U ℓ A · e − n 2 Δ 2 ⩽ ℓ U ℓ A 1 + n 2 Δ 2 = K ℓ B 1 + n C 2 = 2 K ℓ B 1 + 1 + 2 C K ⩽ 2 K ℓ B 1 + 2 C K ⩽ 2 K ℓ B 2 C K = 2 K C ℓ B . Summing the two bounds, we obtain the required result. □

In particular, this theorem proves that our worst-case expected loss L grows sublinearly both with increasing round cost (with rate O ( ε 1 / 2 ) ) and with increasing authentication costs (with rate O ( ε 1 / 4 ) ). Furthermore, the expected loss is bounded symmetrically for both user and attacker access. Finally, there is a strong dependence on the margin Δ between the attacker and the user error rates, which is an expected result.

3.2.1. Improved choice for large Δ

As the above value is somewhat too conservative, especially for large values of Δ, we can obtain instead a value for the number of rounds by directly minimizing (8). Observe that by differentiating the right-hand side, we have: ℓ B = Δ 2 ℓ A ℓ U 2 e − n Δ 2 2 , n = 2 Δ 2 ln Δ 2 ℓ A ℓ U 2 ℓ B , Δ > 2 e ℓ B ( ℓ A ℓ U ) − 1 / 4 . This is a good choice for the number of rounds as long as Δ is not too small. We can now prove a bound for this choice.

Theorem 3.

Assume ℓ A , ℓ U , ℓ B > 0 and Δ > 2 e ℓ B ( ℓ A ℓ U ) − 1 / 4 . If we choose τ = τ ˆ n ∗ and n = n ˜ ∗ ≜ ⌈ 2 Δ 2 ln Δ 2 ℓ A ℓ U 2 ℓ B ⌉ ,(11) then the expected loss is bounded by E ( L | n ˜ ∗ , τ ˆ n ∗ ) ⩽ L 3 ≜ ℓ B [ 1 + 2 Δ 2 ( 1 + ln Δ 2 ℓ A ℓ U 2 ℓ B ) ] .(12)

Proof.

Plugging n = n ˜ ∗ into (8), we obtain E ( L | n ˜ ∗ , τ ˆ n ∗ ) ⩽ n ˜ ∗ ℓ B + e − n ˜ ∗ 2 Δ 2 · ℓ A ℓ U . Taking the first term, we have: n ˜ ∗ ℓ B ⩽ ℓ B + 2 ℓ B Δ 2 ln Δ 2 ℓ A ℓ U 2 ℓ B , where we used the fact that ⌈ x ⌉ ⩽ x + 1 .

Taking now the second term, and using fact that ⌈ x ⌉ ⩾ x , we have: e − Δ 2 2 n ˜ ∗ · ℓ A ℓ U ⩽ e − ln Δ 2 ℓ A ℓ U 2 ℓ B · ℓ A ℓ U = 2 ℓ B Δ 2 . Adding together the two terms, we obtain the required result. □

In order to measure the quality of those bounds, we shall now compare them, by applying them to a family of RFID protocols.

3.2.2. The effect of problem parameters on the security variables

Since different choices for the three losses, as well as different amounts of distinguishability Δ have a direct effect on the number of rounds and threshold, it is instructive to show how these change. In particular, Fig. 1 shows how the threshold, and two choices for the number of rounds, change as a function of Δ, for four different combinations of ℓ A , ℓ B , when ℓ U = 1 .

OPEN IN VIEWER

Fig. 1.

Effect of gap Δ on the threshold and number of rounds, for different choices of ℓ A , ℓ B , with ℓ U = 1 . (a)  ℓ A = 10 , ℓ B = 10 − 2 . (b)  ℓ A = 10 2 , ℓ B = 10 − 2 . (c)  ℓ A = 10 , ℓ B = 10 − 3 . (d)  ℓ A = 10 2 , ℓ B = 10 − 3 . (Colors are visible in the online version of the article; https://dx-doi-org.web.bisu.edu.cn/10.3233/JCS-140521.)

In all settings, both the number of rounds and the threshold decrease as Δ increases. However, we also observe that they all increase when ℓ B decreases (compare Fig. 1(a) and (c)), or when ℓ A increases (compare Fig. 1(a) and (b)). Indeed, the number of rounds is highest in Fig. 1(d), which intuitively makes sense, since the threshold is generally proportional to the number of rounds, while the latter increases when the ratio ℓ A / ℓ B increases. Finally, note that although the improved number of rounds is initially quite close to the original choice, there is a significant difference for larger Δ.

In the following sections, rather than working with abstract values of Δ and with the direct expected loss calculations and bounds, we shall consider a specific family of protocols which implements such a challenge–response phase. Under assumptions on the noise and the protocol implementation, we shall show that our analysis is applicable, and we shall provide simulated experiments which compare our choices of threshold with the optimal choice, as well as a Bayesian variant.

Currently, the most well-known protocols employing an authentication phase without any error correction and under resource constraints are RFID distance bounding protocols. These are used for authentication between a reader (the verifier) and an RFID tag (the prover). These challenge–response protocols use a rapid-bit exchange phase in order to ensure that the tag is at an appropriate distance from the reader. This way, then can avoid man-in-the-middle relay attacks, due to the time delay that these attacks introduce.

For illustrative purposes, we shall examine the properties of two such protocols, for which it is possible to derive simple expressions for p A , p U , given symmetric channel noise.2

We consider an exchange between the verifier V and the prover P , which in case of an RFID protocol are embodied as an RFID reader and an RFID tag, respectively. As tags are generally underpowered (or completely unpowered) communication normally has limited range and can suffer from significant noise. To model noise in the physical medium, we assume that in any exchange between V and P , the former may send a symbol x ∈ X , while the latter may receive a symbol x ˆ ∈ X such that x ≠ x ˆ . We shall denote the probability of erroneous transmission in the data layer as: ω ≜ P ( x ˆ = j | x = i ) for i ≠ j . For simplicity, we shall only treat the case of symmetric channel noise such that: P ( x ˆ = y | x ≠ y ) = 1 | X | − 1 , ∀ y ≠ x , x , y ∈ X . However, all our results carry over for the case of asymmetric channel noise ω 1 , ω 2 for each direction, by taking ω = max j ω j . The noise is particularly important for distance-bounding protocols, as they include a challenge–response phase where single-bit messages are exchanged rapidly between the reader and tag, so as to verify that the tag is in close proximity, by taking advantage of the bounded speed of light. This phase, called the rapid-bit exchange phase, closely corresponds to our analysis in the previous section.

In particular, two RFID distance bounding protocols, the Swiss-Knife protocol [18] and the variant Hitomi [21] are additive-error authentication protocols satisfying our assumptions. Both protocols include an initialization and a termination phase with error correction, as well as a distance-bounding (rapid-bit exchange) phase without error correction. In the initialization phase, the session keys are agreed. The distance bounding phase is an n-round phase where a sequence of challenges ( c t ) t = 1 n and responses ( r t ) t = 1 n are exchanged without error correction. This is also called the rapid-bit exchange phase. However, the received challenges and responses c ˆ t , r ˆ t may differ from the ones sent due to noise. Let r t ∗ denote the correct response to the ith challenge. Then the error at time t is simply equal to 1 whenever the received response does not match the correct response, i.e. ε t ≜ I { r ˆ t ≠ r t ∗ } . During the termination phase, the challenges and responses are sent over the error corrected channel to the verifier, who checks if they match those used in the rapid-bit exchange.

In order to satisfy Assumption 1 for both the user and attacker, we need the actual channel noise to be independent, but not necessarily identically distributed for every challenge and response. We also require the protocol to be constructed in such a way that it holds: P ( c t = i | c 1 , … , c t − 1 ) = 1 2 , P ( r t = j | r 1 , … , r t − 1 , c 1 , … , c t ) = 1 2 ,(13) in order to ensure that the attacker has no advantage when trying to guess future challenges and responses from previous ones. The first part can be achieved by ensuring that the challenges are uniformly distributed in { 0 , 1 } . The second part is slightly more involved, as the correct response depends both on a shared secret and on a cryptographic hash function using a random nonce. The hash function must be such that a uniform distribution of nonces results in a uniform bit distribution for each hash. In practice, this assumption must be relaxed to that of computational indistinguishability of the actual distributions from the uniform one. Finally, these probabilities must be independent of previous runs of the protocol, in order to prevent learning attackers (i.e. attackers that build knowledge by observing multiple runs of the protocol).

4.2. Validation experiments

In this section, we experimentally validate our theoretical analysis for the above protocols. In the results shown here, we chose the following values for the losses: ℓ A = 10 , ℓ U = 1 , ℓ B = 10 − 2 for illustrative purposes.

More specifically, Fig. 2 depicts the worst-case expected loss for different choices of the number of rounds, and our near-optimal threshold, as well as the values of theoretical bounds. For the optimal number of rounds n ∗ we obtain the loss E ( L | n ∗ ) . This is of course smaller than E ( L | n ˆ ∗ ) , the loss suffered by choosing n ˆ ∗ , with the gap becoming smaller for larger error rates. Since when this occurs, the expected loss is very close to L 1 , this implies that the bound of Theorem 1 can be further tightened for small ω. Indeed, we see that the improved bound L 3 obtained for the improved number of rounds n ˜ ∗ almost matches the bound L 1 ( n ˆ ∗ ) , but it fails to hold for large ω, i.e. for small Δ, as expected.

OPEN IN VIEWER

Fig. 2.

The worst-case expected loss L and the bounds L 1 and L 2 from Theorems 1 and 2 respectively vs. the channel error rate ω. The lowest line depicts the worst-case expected loss when the number of rounds is chosen optimally, while the second line depicts the same thing according to our first choice of number of rounds. The alternative line L 3 is only valid for large Δ and hence small amounts of noise. Thus, the region of small Δ is depicted with a thinner line. (Colors are visible in the online version of the article; https://dx-doi-org.web.bisu.edu.cn/10.3233/JCS-140521.)

One potentially major problem with the above approach is that knowledge of ω is necessary, at least in order to calculate a bound on the error probabilities for the user. In this section, we discuss how this can be done leveraging the coding performed during the initial and final phases of the protocol.

We assume some coding function Φ : X m → X k , with k > m , and a metric γ on X k (where usually X = { 0 , 1 } and γ is the Hamming distance) such that: γ min ≜ min { γ ( Φ ( x ) , Φ ( y ) ) : x , y ∈ X m , x ≠ y }(14) is the minimum (Hamming) distance between valid codewords. For a given x ∈ X m , the source transmits ϕ = Φ ( x ) and the sink receives ϕ ˆ , with ϕ , ϕ ˆ ∈ X n . As before, we assume that the physical channel has a symmetric error rate ω = P ( ϕ i ˆ ≠ ϕ i ) , where ϕ i denotes the ith bit of ϕ. This is then decoded as x ˆ ≜ arg min { γ ( ϕ ˆ , Φ ( y ) ) : y ∈ X m } . Let θ be the number of errors in the string ϕ ˆ , or more precisely θ = γ ( ϕ , ϕ ˆ ) . Let θ ˆ ≜ γ ( Φ ( x ˆ ) , ϕ ˆ ) be the distance between the closest valid codeword Φ ( x ˆ ) and the received ϕ ˆ . If θ < ( γ min − 1 ) / 2 , then θ = θ ˆ .

The crux of our method for estimating ω relies on the number of errors θ being less than ( γ min − 1 ) / 2 , in which case, the estimated number of errors θ ˆ will equal θ. Let ω ˆ ≜ θ ˆ n be our empirical error rate. In that case, the expected empirical error rate equals the true error rate. More formally: E ( ω ˆ | θ ⩽ ( γ min − 1 ) / 2 ) = ω .(15) If θ > ( γ min − 1 ) / 2 then the protocol fails in any case, due to decoding errors in the initial or final phases. If not, then the above equation holds and we can obtain high probability bounds for ω via the Hoeffding inequality (Appendix A.1, Lemma 3). In particular, it is easy to show that, for any δ ∈ [ 0 , 1 ] : P ( | ω ˆ − ω | ⩾ ln 2 / δ 2 k ) ⩽ δ ,(16) by substituting the square-root term into (21), and setting μ i = ω , ∑ X i = θ ˆ , a i = 0 , b i = 1 . Consequently, for the Swiss-Knife family of protocols the following values for p A and p U hold with probability 1 − δ : p A = 1 2 , p U = 2 ω ˆ − 2 ln 2 / δ k .(17) Experimental investigations presented in the next section indicate that this choice has good performance in terms of expected loss.

This follows directly from Theorems 1 and 2 and the fact that an increased estimated noise results in a smaller value for Δ. More precisely, the number of rounds is decreasing with Δ, and so a decrease in Δ leads to an increase in the number of rounds. The threshold itself is proportional to the number of rounds, with offset − ln ρ 4 Δ . Consequently, when ρ > 1 , meaning that ℓ A > ℓ U , any increase in Δ would lead to a decrease in the threshold. Consequently, we would tolerate a smaller number of errors.

In this section, we describe some experiments where we evaluate the different components of the proposed approach. In these experiments, we measure the expected loss for varying noise conditions while varying three different aspects of the challenge–response protocol. The first is the method used to calculate the threshold, where we compare the proposed bound with a simple likelihood ratio test. The second is the method used to estimate the channel noise, where we compare the method described in Section 5, with an arbitrary selection of noise and a simple empirical estimate. Finally, we vary the problem parameters, such as the cost per bit ℓ B and the cost of successful attack ℓ A , and see if we obtain qualitatively different solutions. In the latter experiment, we also compare against the minimax choice of threshold and number of rounds, which can perform much better than the approximation. On the other hand, it can be difficult to compute.

6.2. Evaluation of noise estimation

The actual values p A , p U depend on ω, which is unknown. We compare three methods for choosing p A , p U . Firstly, guessing a value ω ˆ for the channel noise. Secondly, using the maximum likelihood noise estimate ω ˆ = θ ˆ / k . In both cases, we simply use ω ˆ as described at the beginning of Section 4 to obtain p A , p U . In the third case, we use the high-probability bounds (17) for p A , p U , with an arbitrary value of δ. For those experiments, we use ℓ A = 10 , ℓ U = 1 , ℓ B = 10 − 2 , while we used k = 2 10 for the coded messages in the initialization phase.

OPEN IN VIEWER

Fig. 3.

The worst-case expected loss as a function of noise. We plot the evolution of the loss as noise changes, for a number of different cases. Firstly, for the case where we arbitrarily assume a noise value ω ˆ ∈ { 10 − 1 , 10 − 2 , 10 − 3 } . Secondly, for an empirically estimated ω ˆ = k ˆ / n , and finally for p A , p U calculated via Eq. (17) with δ ∈ { 10 − 1 , 10 − 2 } . (a) Our threshold. (b) Likelihood ratio. (Colors are visible in the online version of the article; https://dx-doi-org.web.bisu.edu.cn/10.3233/JCS-140521.)

In the first experiment, shown in Fig. 3(a), we use the nearly-optimal threshold and number of rounds that we have derived in our analysis. In the second experiment, shown in Fig. 3(b), we replace our choice of threshold with a choice similar to that of Baignères et al. [1]. Their threshold is derived via a likelihood ratio test, which is asymptotically optimal (c.f. [11,12]) but they do not consider specific losses. Since in our case we have unequal losses ℓ A and ℓ U , we re-derive their threshold via a Bayesian test (to which a Bayesian formulation of the Neyman–Pearson lemma [12] applies) to obtain: τ ˜ = n ln 1 − p U 1 − p A − ln ρ ln 1 − p U 1 − p A − ln p U p A .(18) For equal losses, ρ = 1 , and τ ˜ equals the threshold used in [1]. Such tests have good asymptotic properties [10,12]. Interestingly, for small Δ, the form of τ ˜ is similar to τ ˆ n ∗ : Let p ¯ such that p A = p ¯ + Δ / 2 and p U = p ¯ − Δ / 2 . Then (18) can be approximated by τ ˜ ∗ = n p ¯ − p ¯ ( 1 − p ¯ ) Δ ln ρ . More details on the derivation of (18) are given in Appendix A.2 on page 326.

Figure 3 depicts the worst-case expected loss L as a function of the actual noise ω. Figure 3(a) shows L using the threshold τ derived from our expected loss analysis (7), while in Fig. 3(b) we use the asymptotically optimal threshold of (18). In both cases, we plot L , while the actual noise ω is changing, for a number of different cases. Initially, we investigate the evolution of L for three arbitrarily chosen values ω ˆ ∈ { 10 − 1 , 10 − 2 , 10 − 3 } . Additionally, we examine the evolution of the worst-case expected loss, when the noise is empirically estimated ω ˆ = θ ˆ / n and finally when p A and p U are calculated via Eq. (17) with δ ∈ { 10 − 1 , 10 − 2 } .

As it can be seen in Fig. 3, in all cases (using ours Fig. 3(a) or Baignères et al. [1] threshold Fig. 3(b)) the worst-case expected loss is very low for small values of the actual noise and increases sharply when the actual noise approaches the value of 10 − 1 . It is interesting to see that when we use the optimistic4

⁴

Experiments with pessimistic high probability estimates for the noise showed a significant increase in the number of rounds used, which resulted in a higher expected loss.

high probability estimates for p A , p U , we obtain almost always better performance than simply guessing the noise, or using the plain empirical estimate ω ˆ directly. Furthermore, using the asymptotically optimal threshold (18), we observe a deterioration in the results. Thus, our approach results in a clearly dominating performance over other methods.

As mentioned in Section 7, the choice of the threshold by Baignères et al. [1] is only asymptotically optimal. Ours, while not optimal, gives a worst-case expected loss guarantee for any finite sample size. Thus, it has better performance when the asymptotic approximation is not sufficiently good, which occurs when both the number of rounds n and the gap Δ are small. In addition, it is much less sensitive to the estimate of ω than the likelihood ratio threshold.

6.3. Comparison with the minimax solution

When computational considerations are not an issue, i.e. when we can perform an exhaustive search, it is possible to optimize directly for the minimax solution. That is, given particular parameters χ ≜ { p A , p U , ℓ A , ℓ U , ℓ B } we can find a threshold τ and number of rounds n minimizing the worst-case expected loss, that is: min { max P ∈ { A , U } E ( L | P , τ , n , χ ) : n ∈ [ n max ] , t ∈ [ n ] } .(19) Note here that for any decision rule such that n > n max ≜ min { ℓ A , ℓ U } / ℓ B , then our cost is trivially larger than either rejecting or accepting immediately. Consequently, we only need to consider a finite set of number of rounds to recover the minimax solution. In particular, the complexity of the solution includes O ( n max 2 ) evaluations of the maximum expected loss, with each evaluation requiring the computation of the binomial cumulative probability function. This in turn has quadratic complexity, giving an overall complexity of O ( n max 4 ) .

We performed a thorough experimental comparison between the minimax solution, our suggested threshold and number of rounds, and the threshold chosen via the likelihood ratio test. In all cases, the noise was estimated with k = 2 10 and using the high-probability bound for p A , p U . The user loss was fixed to ℓ A = 1 , while we varied the bit cost ℓ B and the attacker loss ℓ A .

OPEN IN VIEWER

Fig. 4.

Comparison of the worst-case expected loss, for: (i) the approximate number of rounds and threshold, (ii) the threshold given by the likelihood ratio test, as well (iii) the exact minimax solution for both the threshold and the number of rounds. We show results for four different cases, where we vary the bit cost ℓ B and the attack cost ℓ A . (a)  ℓ B = 10 − 2 , ℓ A = 10 . (b)  ℓ B = 10 − 1 , ℓ A = 10 . (c)  ℓ B = 10 − 2 , ℓ A = 10 2 . (d)  ℓ B = 10 − 3 , ℓ A = 10 2 . (Colors are visible in the online version of the article; https://dx-doi-org.web.bisu.edu.cn/10.3233/JCS-140521.)

The results for four different choices of those parameters, as ω varies, are shown in Fig. 4. It can be seen that our choice always dominates the likelihood ratio, while of course the minimax solution is clearly the best. It can also be seen that whenever the ratio between the attack cost ℓ A and the bit cost ℓ B is small, the three methods are closer together.

To the best of our knowledge, we have performed the first expected loss analysis of additive error challenge–response authentication protocols under channel constraints. Such an analysis is necessary, because of the inherent cost of increasing the number of rounds n and the need to trade off optimally the costs of incorrectly authenticating an illegitimate entity, or failing to authenticate a legitimate one, as well as the lack of an error-free channel. In order to achieve this, we made the assumption of bounds on the expected errors of a user and an attacker. In addition, we assumed that these are independent from errors in the previous rounds.5

The rapid-bit exchange phase considered in parts of this paper was introduced in [6] to compute an upper bound on the distance of the prover P from the verifier V . This is composed of n challenge–response rounds, used to calculate a round-trip time and thus place a bound on the distance. Subsequently, a broad range of distance bounding protocols were proposed, both for RFID [16,18,21,22,24], as well as other wireless devices [8,9,27].

Hancke and Kuhn [16] were the first to indicate that since the rapid-bit exchange phase is taking place in a noisy channel, challenges and responses may be corrupted. Thus, a legitimate user may fail to get authenticated. Their protocol (henceforth HaKu), employed n rounds and authenticated any prover who made a number of mistakes ε less than an acceptance threshold τ, so as to reduce the number of false rejections. Using the binomial distribution and an assumption on the error rates they give expressions for the false accept and false reject probability as a function of n and τ, but they provide no further analysis. Nevertheless, they indicate that the number of challenge–response rounds n in the rapid bit exchange phase should be chosen according to the expected error rate. Kim et al. [18] extend this approach with the Swiss-Knife protocol by considering three types of errors. Finally [24], rather than using a threshold τ, proposed a protocol (henceforth ECMAD) using an error correcting code (ECC). ECMAD, which extends the MAD protocol [8], uses only k of the n total rounds for the challenges and responses. The remaining n − k rounds are used to transmit the ( n , k ) ECC. This has the effect of achieving better security (in terms of false acceptance rates) with the same number of rounds n.

All these approaches use n rounds in the noisy authentication phase. However, they do not define the optimal n. They simply state that the probability of authenticating a user becomes much higher than the probability of authenticating an attacker as n increases. However, a large value of n is incompatible with the requirements of many applications and devices (i.e. high value of n leads to high overhead for resource-constrained devices). This can be modelled by assigning an explicit cost to every round, which should take into account the transmission energy, computation and time overhead. This cost has so far not been explicitly taken into consideration.

Another work that is closely related to ours is [23], which, given a required false acceptance and false rejection rate, provides a lower bound on the number of required rounds. This analysis is performed for both HaKu and ECMAD. However, it assumes that the number of rounds n would be large enough for the binomial distribution of errors to be approximately normal. Our analysis is more general, since it uses finite-sample bounds that hold for any bounded error function.

Recently, Baignères et al. [1] have given an analysis on the related topic of distinguishing between a real and a fake solver of challenge–response puzzles. More precisely, they study CAPTCHA-like protocols and provide a threshold which minimizes the probability of error in these protocols. The main differences between the analysis presented in this paper and [1] can be summarized as: (a) We perform an expected loss analysis rather than an error analysis; (b) Our bounds hold uniformly, while [1] uses an asymptotically optimal distinguisher; (c) We consider bounded errors rather than { 0 , 1 } errors for each challenge–response; (d) We additionally propose a method to estimate channel noise. This is of course not applicable in the context of [1], due to the different setting.

A more general work on authentication under noisy conditions was presented in [19]. This provided tight information-theoretic upper and lower bounds on the attacker’s success in impersonation and substitution attacks, proving that it decreased with noise. However, this is somewhat misleading, as it ignores the efficiency of the protocol. Our analysis shows that, when one considers losses due to communication overhead and false rejections of users, the expected loss increases, which is a natural result.

In this paper, we perform a detailed expected loss analysis for a general class of additive-error authentication protocols in a noisy channel. The analysis is performed by assigning a loss ℓ B to each round, and losses ℓ A , ℓ U to false acceptance and false rejection, respectively.

We show how a nearly-optimal threshold τ ˆ n ∗ for a given number of rounds n can be chosen and give worst-case bounds on the expected loss for that choice. Thus, the bounds hold no matter if the party that attempts to get authenticated is either a legitimate user U or an attacker A. This extends our previous work [21], which proposed a new distance bounding protocol (Hitomi) and only calculated a value for the threshold τ, without providing any bounds.

We also show how a nearly-optimal number of rounds n ˆ ∗ can be chosen and give further bounds on the expected loss. The bounds hold for any bounded error function, and not only for { 0 , 1 } errors.6

Finally, we provided high-probability estimates for the current noise level in the channel by leveraging the coding performed in the initial and final phases of the protocol, which takes place in a coded channel. This enables us to significantly weaken assumptions on knowledge of the noise level in the channel and in turn, provide an authentication algorithm which has low expected loss with high probability. Experimentally, we obtain uniformly superior results to guessing or direct empirical noise estimates. Finally, we repeated those experiments with an asymptotically optimal threshold similar to that used by Baignères et al. [1]. Our results indicate a significant improvement through the use of a threshold with uniform, rather than asymptotic, guarantees. Consequently, it is our view that algorithms motivated by an asymptotic analysis should be avoided in the finite-sample regime of most challenge–response authentication protocols.

Our analysis is particularly significant for areas of communications where challenges and responses are costly and where there exists significant uncertainty about the correctness of any single response.