Analysis and Correction of the Attack against the LPN-Problem Based Authentication Protocols

Abstract

This paper reconsiders a powerful man-in-the-middle attack against Random-HB# and HB# authentication protocols, two prominent representatives of the HB family of protocols, which are built based on the Learning Parity in Noise (LPN) problem. A recent empirical report pointed out that the attack does not meet the claimed precision and complexity. Performing a thorough theoretical and numerical re-evaluation of the attack, in this paper we identify the root cause of the detected problem, which lies in reasoning based on approximate probability distributions of the central attack events, that can not provide the required precision due to the inherent limitations in the use of the Central Limit Theorem for this particular application. We rectify the attack by employing adequate Bayesian reasoning, after establishing the exact distributions of these events, and overcome the mentioned limitations. We further experimentally confirm the correctness of the rectified attack and show that it satisfies the required, targeted accuracy and efficiency, unlike the original attack.

1. Introduction

The construction of lightweight and secure authentication protocols for RFID (Radio Frequency IDentification) devices is an important task of contemporary cryptography. These devices are employed in supply-chain management, payment and transportation systems, for the tracking of goods and other applications, and are rapidly becoming one of the most pervasive technologies. An RFID system usually consists of two entities—a resource-constrained Tag attached to a physical object and a more computationally powerful Reader, which communicate using authentication protocol in order to validate Tag by the Reader. Reaching high security requirements for such validation while minimizing its resources cost is a very active research area [1,2,3]. One of the important families of authentication protocols for RFID systems is the HB family.

The HB family originates from a lightweight protocol called HB that was proposed by Hopper and Blum [4] and is built over the hardness of the Learning Parity in Noise (LPN) problem. Informally, the LPN problem could be considered as a problem of solving an overdefined system of consistent linear equations over GF(2), the field with two elements, where certain equations are available only in a corrupted form. While the HB protocol resists passive (eavesdropping) attacks, it is shown to be vulnerable against an active adversary who can impersonate a reader and interact with legitimate tags. A modified protocol named HB+ [5,6] was proposed with the aim of addressing this weakness. Soon after, it was shown that the HB+ protocol is defenseless against a stronger adversary who can modify the messages sent by the reader [7]. This attack is known as the GRS man-in-the-middle (MIM) attack. In order to avoid the GRS-MIM attack, different protocol variants were proposed (see, for example, HB++ [8] and HB-MP [9]). However, they were shown to be vulnerable [10], until the HB# and Random-HB# protocols were introduced in [11] and proven to be secure against GRS-MIM. Shortly thereafter, Ouafi, Overback and Vaudenay proposed a more general MIM attack (OOV, by authors’ initials) [12] against HB# and Random-HB#. The attack implies an adversary that can modify the messages exchanged in both directions between the tag and the reader. Moreover, OOV can be regarded as a generic attack against the HB-family. The OOV attack remains one of the keystones in the analysis of HB-like authentication schemes and it is recognized as essential in the security evaluation of any novel HB-like protocol [1].

Some other HB-protocol variants are: HB-MP+ [13], HB-MP++ [14], HB-MP* [15], Trusted-HB [16], NLHB [17], HB^N [18], GHB# [19], HB+PUF [20], PUF-HB [21], and Tree-LSHB [22,23]. However, many of these HB-family protocols have been shown to be vulnerable against several cryptanalysis techniques and MIM attacks [1,7,10,12]. For a detailed overview of the HB-protocols and analysis based on their efficiency and resistance against attacks, see, for example, [24].

Motivation for the work. Recent results presented in [25] showed that the OOV attack is significantly less successful than it was claimed in [12] and pointed out malfunctioning in the core component of the attack. The estimated complexity of the attack is $18\%$ higher for HB# and $55\%$ for Random-HB# than the claimed, in the case of the standard parameter set II. This is a significant increase having in mind the overall complexity and time consumption of the attack, which is claimed to be $2^{29.4}$ for Random-HB#, and $2^{21}$ for HB#. In this paper, we continue on this investigation path and revise the theoretical and numerical analysis behind the attack provided in [12], in order to determine the cause of the mentioned problem and try to solve it, if possible.

Summary of the results. This paper revises the cryptanalysis from [12] providing proof and explaining why the approximations of the probability distributions employed in the core component of the attack are inappropriate in the considered context, which results in lower precision and higher complexity of the OOV attack [12]. Further, this paper provides a derivation of the correct probability distributions on the number of successful authentications that leaks secret information, which can be used to recover secret keys. Finally, a correction of the OOV attack is proposed, which uses the derived, correct probability distributions, satisfying the targeted performances/complexity.

Organization of the work.Section 2 provides background on the HB# and Random-HB# protocols and the OOV attack. Section 3 brings a thorough revision of theoretical analysis behind the OOV attack and points to the critical omissions in it. Section 4 introduces the corrected attack and analyze its performance. Section 5 provides results of experimental analysis. In Section 6, the findings and results presented in the paper are briefly summarized.

2. Preliminaries

A list containing notation used throughout the remainder of the paper is given below.

• Variables are denoted with normal, bold or capital bold letters (e.g., x, $\mathbf{x}$ and $\mathbf{X}$) if they represent single elements, vectors, or matrices, respectively
• ${\mathbb{Z}}_2^m$: set of all m-dimensional binary vectors
• ${\mathbb{Z}}_2^{k\times m}$: set of all $k\times m$-dimensional binary matrices
• ${\mathbf{x}}_i$: i-th element of binary vector $\mathbf{x}$
• ${\mathbf{1}}_i$: binary vector with all zeros, except on the position i
• $\mathbf{x}\oplus \mathbf{y}$: bitwise XOR operation of two binary vectors $\mathbf{x}$ and $\mathbf{y}$
• $\parallel \mathbf{x}\parallel$: the Hamming weight of binary vector $\mathbf{x}$ (sum of its elements)
• $x\stackrel{\$}{\leftarrow }X$: sampling a value x which follows uniform distribution over a finite set X
• $Pr\left[A\right]$: probability of an event A
• ${\mathrm{B}er}_{\tau }$: Bernoulli distribution with parameter $\tau$. $x\leftarrow {\mathrm{B}er}_{\tau }$ is sampling of value x such that $P(x=1)=\tau$, $P(x=0)=1-\tau$
• $Bin(n,p)$: Binomial distribution of n experiments with success probability p of each experiment
• $\mathbf{e}\leftarrow {\mathrm{B}er}_{\tau }^m$: sampling binary vector $\mathbf{e}\in {\mathbb{Z}}_2^m$ such that ${\mathbf{e}}_i\leftarrow {\mathrm{B}er}_{\tau },i=1,\dots ,m$
• $\mathcal{N}(\mu ,{\sigma }^2)$: Normal distribution with mean $\mu$ and variance ${\sigma }^2$
• $\mathsf{\Phi }\left(x\right)$: standard normal cumulative distribution function
• $erfc\left(x\right)=2\mathsf{\Phi }(-x\sqrt{2})$: complementary error function
• $X_n\stackrel{\mathcal{D}}{\to }\mathcal{X}$: sequence of random variables $X_1,X_2,\dots X_n$ converges weakly (in distribution) to a distribution $\mathcal{X}$ as $n\to \infty$
• $P\left(\overline{w}\right)$: probability of acceptance during the OOV attack when the Adversary adds noise vector $\overline{\mathbf{e}},\parallel \overline{\mathbf{e}}\parallel =\overline{w}$ to a regular noise vector $\mathbf{e}$ in a protocol session, that is, $P\left(\overline{w}\right)=Pr[\parallel \mathbf{e}\oplus \overline{\mathbf{e}}\parallel \le thr]$
• $P_{OOV}\left(\overline{w}\right):=\mathsf{\Phi }\left(\frac{thr-(m-\parallel \overline{e}\parallel )\tau -\parallel \overline{e}\parallel (1-\tau )}{\sqrt{m\tau (1-\tau )}}\right)$: approximation of $P\left(\overline{w}\right)$ used in the OOV attack [12].

The HB family of authentication protocols has attracted a lot of attention because of their simple implementations and the provable security based on the well-known hard problem—Learning Parity with Noise (LPN). Random-HB# and HB# are prominent representatives of this family. Their authentication procedure consists of the following steps [11]—first, the Tag sends a random blinding vector $\mathbf{b}$ to the Reader to initiate the authentication and the Reader responds with a random challenge vector $\mathbf{a}$ to the Tag. Then Tag sends $\mathbf{z}=\mathbf{aX}\oplus \mathbf{bY}\oplus \mathbf{e}$ to the Reader, where $\mathbf{e}$ is a noise vector whose bits independently follow Bernoulli distribution with coefficient $\tau$, and $\mathbf{X}\in {\mathbb{Z}}_2^{k_X\times m},\mathbf{Y}\in {\mathbb{Z}}_2^{k_Y\times m}$ are their shared secret keys (random matrices for Random-HB# and so-called Toeplitz matrices for HB#). The Reader validates the Tag, that is, accepts its response, if and only if the Hamming weight $\parallel \mathbf{aX}\oplus \mathbf{bY}\oplus \mathbf{z}\left|\right|$ falls under a certain threshold value (see Figure 1). Standard parameters’ values for these protocols are given in

Table 1. Standard parameter sets I and II for HB# and Random-HB# proposed in [11]. Number l of secret bits is $(k_x+k_y)m$ for Random-HB#, while it is $k_x+k_y+2m-2$ for HB#.

Parameter Set	${\mathit{k}}_{\mathit{x}}$	${\mathit{k}}_{\mathit{y}}$	m	$\mathit{\tau }$	$\mathbf{thr}$
I	80	512	1164	0.25	405
II	80	512	441	0.125	113

.

The mechanism of the OOV attack proposed in [12] is shown in Figure 2. The adversary:

• Collects a triplet $(\overline{\mathbf{a}},\overline{\mathbf{b}},\overline{\mathbf{z}}=\overline{\mathbf{a}}\mathbf{X}\oplus \overline{\mathbf{b}}\mathbf{Y}\oplus \overline{\mathbf{e}})$ of messages exchanged between the Tag and the Reader by eavesdropping one of their communication sessions
• Replaces each triplet $(\mathbf{a},\mathbf{b},\mathbf{z})$ of messages between the Tag and the Reader during n following communication sessions with a triplet $(\mathbf{a}\oplus \overline{\mathbf{a}},\mathbf{b}\oplus \overline{\mathbf{b}},\mathbf{z}\oplus \overline{\mathbf{z}})$
• Counts the number c of “ACCEPT” decisions of the Reader at the end of those n sessions.

The acceptance rate $\frac{c}{n}$, as it turns out, leaks the critical information which reveals the secret values. More precisely, the theoretical analysis from [12] shows that:

$$\frac{c}{n}\approx \mathsf{\Phi }\left(\frac{thr-(m-\parallel \overline{\mathbf{e}}\parallel )\tau -\parallel \overline{\mathbf{e}}\parallel (1-\tau )}{\sqrt{m\tau (1-\tau )}}\right),$$

where $\mathsf{\Phi }$ is the standard normal cumulative distribution function. This formula allows the adversary to estimate the Hamming weight $\parallel \overline{\mathbf{e}}\parallel$ using solely the empirical value $\frac{c}{n}$, for n large enough (Algorithm 1 from [12]).

After the adversary discovers the Hamming weight of the noise vector $\overline{\mathbf{e}}$, he can reconstruct the vector by flipping its bits (more precisely, he flips $\overline{\mathbf{z}}=\overline{\mathbf{a}}\mathbf{X}\oplus \overline{\mathbf{b}}\mathbf{Y}\oplus \overline{\mathbf{e}}$ which secretly contains $\overline{\mathbf{e}}$) and measures weight of $\overline{\mathbf{e}}$ after the flipping. If the weight has increased, the flipped bit was 0, otherwise, it was 1. This way, he reconstructs the noise vector $\overline{\mathbf{e}}$ and obtains the linear combination $\overline{\mathbf{a}}\mathbf{X}\oplus \overline{\mathbf{b}}\mathbf{Y}$ since $\overline{\mathbf{a}}\mathbf{X}\oplus \overline{\mathbf{b}}\mathbf{Y}=\overline{\mathbf{z}}\oplus \overline{\mathbf{e}}$ (Algorithm 2 from [12]). The whole previous procedure is repeated also for other modification triplets $({\overline{\mathbf{a}}}_{\mathbf{i}},{\overline{\mathbf{b}}}_{\mathbf{i}},{\overline{\mathbf{z}}}_{\mathbf{i}}={\overline{\mathbf{a}}}_{\mathbf{i}}\mathbf{X}\oplus {\overline{\mathbf{b}}}_{\mathbf{i}}\mathbf{Y}\oplus {\overline{\mathbf{e}}}_{\mathbf{i}})$ obtained by eavesdropping, until the adversary collects enough of these linear combinations ${\overline{\mathbf{a}}}_{\mathbf{i}}\mathbf{X}\oplus {\overline{\mathbf{b}}}_{\mathbf{i}}\mathbf{Y}={\overline{\mathbf{z}}}_{\mathbf{i}}\oplus {\overline{\mathbf{e}}}_{\mathbf{i}}$ to form a full system of linear equations. The secret keys $\mathbf{X}$ and $\mathbf{Y}$ are then recovered as the solution to this system.

As illustrated above, in each corrupted communication session, the Reader computes:

$$\begin{array}{cc}\hfill \parallel \mathbf{aX}\oplus \widehat{\mathbf{b}}\mathbf{Y}\oplus \widehat{\mathbf{z}}\parallel & = \parallel \mathbf{aX}\oplus (\mathbf{b}\oplus \overline{\mathbf{b}})\mathbf{Y}\oplus (\mathbf{z}\oplus \overline{\mathbf{z}})\parallel \hfill \\ \hfill & = \parallel (\mathbf{aX}\oplus \mathbf{bY}\oplus \mathbf{z})\oplus (\overline{\mathbf{a}}\mathbf{X}\oplus \overline{\mathbf{b}}\mathbf{Y}\oplus \overline{\mathbf{z}})\parallel \hfill \\ \hfill & = \parallel \mathbf{e} \oplus \overline{\mathbf{e}}\parallel \hfill \end{array}$$

and the Tag successfully authenticates iff $\parallel \mathbf{e} \oplus \overline{\mathbf{e}}\parallel \le thr$, whereas in a regular session, the Tag successfully authenticates iff $\parallel \mathbf{e}\parallel \le thr$. This way, by creating the cumulative noise $\mathbf{e}\oplus \overline{\mathbf{e}}$, the adversary manipulates the verification criterion of the Reader and changes its theoretical acceptance rate from $Pr[\parallel \mathbf{e}\parallel \le thr]$ to $P\left(\overline{w}\right):=Pr[\parallel \mathbf{e}\oplus \overline{\mathbf{e}}\parallel \le thr]\approx \mathsf{\Phi }\left(\frac{thr-(m-\parallel \overline{e}\parallel )\tau -\parallel \overline{e}\parallel (1-\tau )}{\sqrt{m\tau (1-\tau )}}\right)$.

Let us provide a simple and useful characterization of the OOV attack Algorithm 1 [12] output by introducing the notion of “decision zones.”

Definition 1.

(“OOV decision zones”). OOV $\overline{w}$-decision zone is an interval $I_{\overline{w}}^{OOV}$ such that OOV Algorithm 1 estimates $\parallel \overline{\mathbf{e}}\parallel$ as $\overline{w}$ iff $\frac{c}{n}\in I_{\overline{w}}^{OOV}$.

After eavesdropping a triplet, the adversary considers all weights of the noise vector $\overline{\mathbf{e}}$ possible. He decides that $\parallel \overline{\mathbf{e}}\parallel$ is $\overline{w}$$\iff \overline{w}-\frac{1}{2}\le P_{OOV}^{-1}\left(\frac{c}{n}\right)<\overline{w}+\frac{1}{2}$$\iff \frac{c}{n}\in I_{\overline{w}}^{OOV}=(P_{OOV}(\overline{w}+\frac{1}{2}),P_{OOV}(\overline{w}-\frac{1}{2})]$, since P is a monotone decreasing function (see Figure 3a).

After flipping a bit in the noise vector, whose weight is previously estimated as $\overline{w}$, the adversary considers only two weights possible: $\overline{w}-1$ and $\overline{w}+1$, so there are two decision zones — $I_{\overline{w}-1}^{OOV}=(P_{OOV}\left(\overline{w}\right),\infty )$ and $I_{\overline{w}+1}^{OOV}=(-\infty ,P_{OOV}\left(\overline{w}\right)]$ (see Figure 3b).

In [12], the complexity of the OOV attack is estimated as an overall number of modified authentication sessions, which is minimized if the expected noise vector weight $w_{exp}$ coincides with the so-called optimal weight when it is polynomial (for weights not near enough the optimal one, it becomes exponential). To achieve this, different strategies are introduced in [12], such as flipping the adequate number of last bits when $w_{exp}\le w_{opt}$ before weight measurement, or removing the already recovered 1-bits when $w_{exp}\ge w_{opt}$.

Also, ref [12] provides an optimized version of the attack which uses flipping block-by-block in the noise vector recovery process instead of bit-by-bit. However, it is observed empirically in [25] that the actual benefit that this optimized version brings is somewhat overestimated. An explanation was offered that it uses insufficient sample sizes for decision making when measuring the weights, which are further away from the optimal one.

3. Revision of the OOV Attack

The previous work [25] has shown that the OOV attack predominantly incorrectly estimates weights of noise vectors. The probability of key recovery, that is, efficiency of the attack, is shown to be significantly lower compared to the values claimed in [12]. For the standard parameter set II, the probability of correct key recovery is shown to be 0.158 in the case of HB# and ${10}^{-7}$ in the case of Random-HB#. The analysis presented in [25] reveals that, in order to achieve the precision of key recovery claimed in [12], it is necessary to increase the number of intercepted authentications by 18% in the case of HB# and by 55% in the case of Random-HB#. Since the number of intercepted authentication sessions is the unit of the attack complexity, the complexity increases accordingly. Furthermore, the analysis from [25] shows that the weight estimation error cannot be corrected by taking a larger “sample” n, i.e., larger number of intercepted authentication sessions. On the contrary, by increasing the sample, the quality of the weight estimate worsens. So, for example, experimental evaluation on the standard parameter set II shows that the percentage of correctly estimated weights is only 5%, even if a very large number of modifications is used (for more details, see Section 4.4 in [25]).

This has led us to conduct a thorough revision of cryptanalysis from [12], which we provide in this Section. We shall prove that the attack’s erroneous output is caused by inadequate, non-Bayesian inference over improper, approximate probability distributions of acceptance rates, which cannot be improved due to Central limit theorem application limitations for these protocols. We identify the exact distributions and the exact error of the approximations from [12]. Then we employ Bayesian reasoning over the exact distributions to construct proper decision zones, and show how OOV weight decision making proposed in [12] deviates significantly from the proper, Bayesian one.

3.1. Revision of the Theoretical Analysis behind the OOV Weight Estimate

Here, we revise the derivation of approximations of acceptance rates used in the OOV weight estimate process and report their significant imprecision. Specifically, this derivation is given in the “Correctness” paragraph, Section 2.1 in [12].

3.1.1. Incorrect Claim that Cumulative Noise Vector $\mathbf{e}\oplus \overline{\mathbf{e}}$ Follows Binomial Distribution

The mentioned paragraph begins with calculation of the probability that i-th bit of cumulative noise vector $\mathbf{e}\oplus \overline{\mathbf{e}}$ is 1:

$$Pr[{(\mathbf{e}\oplus \overline{\mathbf{e}})}_{\mathbf{i}}=1]=\left\{\begin{array}{c}\tau ,{\overline{\mathbf{e}}}_{\mathbf{i}}=0\hfill \\ 1-\tau ,{\overline{\mathbf{e}}}_{\mathbf{i}}=1\hfill \end{array}\right.$$

Then it says (exact quotation): “Hence, $m-\overline{w}$ bits of $\mathbf{e}\oplus \overline{\mathbf{e}}$ follow a Bernoulli distribution of parameter $\tau$ and the other $\overline{w}$ bits follow a Bernoulli distribution of parameter $1-\tau$, thus$\parallel \mathbf{e} \oplus \overline{\mathbf{e}}\parallel$ follows a binomial distribution.” [12].

However, that is not correct: $\parallel \mathbf{e}\oplus \overline{\mathbf{e}}\parallel$ does not follow binomial distribution, because that is by definition a distribution of sum of independent and identically distributed Bernoulli trials i.e., of the same parameter (probability of success). Here, the Hamming weight of cumulative noise $\parallel \mathbf{e}\oplus \overline{\mathbf{e}}\parallel ={\sum }_{i=1}^m{(\mathbf{e}\oplus \overline{\mathbf{e}})}_{\mathbf{i}}$, as we can see, is a sum of Bernoulli trials of mixed parameter values $\tau$ or $1-\tau$ and actually corresponds to a more general so-called Poisson-Binomial Distribution. We elaborate more on this distribution in the upcoming Section 3.2.

3.1.2. Approximation of Acceptance Rates $P\left(\overline{w}\right)\approx P_{OOV}\left(\overline{w}\right)$ without Error Estimation

The “Correctness” paragraph [12] continues with the calculations of the expected weight of the vector $\mathbf{e}\oplus \overline{\mathbf{e}}$ as $\mu =E(\parallel \mathbf{e}\oplus \overline{\mathbf{e}}\parallel )=\overline{w}(1-\tau )+(m-\overline{w})\tau$ and its variance ${\sigma }^2=Var(\parallel \mathbf{e}\oplus \overline{\mathbf{e}}\parallel )=m\tau (1-\tau )$, which are correct, and derives approximation of acceptance rate during the attack:

$$\begin{array}{c}\hfill P\left(\overline{w}\right)=Pr[\parallel \mathbf{e}\oplus \overline{\mathbf{e}}\parallel \le thr]\approx \mathsf{\Phi }\left(\frac{thr-(m-\overline{w})\tau -\overline{w}(1-\tau )}{\sqrt{m\tau (1-\tau )}}\right),\end{array}$$

(1)

where $\mathsf{\Phi }$ is the standard normal cumulative distribution function, by referring to the Central Limit Theorem (CLT)—Formula (1) in [12].

Here, ref [12] applies CLT to sum $\parallel \mathbf{e}\oplus \overline{\mathbf{e}}\parallel$ without discussing the magnitude of error of this approximation—the theorem itself only points to its convergence when $m\to \infty$.

3.1.3. Unknown Error Bound of the Weight Estimate Process

In the rest of the “Correctness” paragraph [12], the authors merge previous approximation (1) with the second one (which is a consequence of the Law of large numbers):

$$\begin{array}{c}\hfill \frac{c}{n}\approx P\left(\overline{w}\right)\end{array}$$

(2)

to conclude that:

$$\begin{array}{c}\hfill \frac{c}{n}\approx \mathsf{\Phi }\left(\frac{thr-(m-\overline{w})\tau -\overline{w}(1-\tau )}{\sqrt{m\tau (1-\tau )}}\right)=:P_{OOV}\left(\overline{w}\right).\end{array}$$

(3)

The idea behind the merging of the two approximations can be explained in the following way: $c/n$ converges to $P\left(\overline{w}\right)$ when $n\to \infty$ (by the Law of large numbers), while $|P_{OOV}\left(\overline{w}\right)-P\left(\overline{w}\right)|$ converges to 0 when $m\to \infty$ (by the Central Limit Theorem). Thus, $c/n$ gets arbitrarily close to $P_{OOV}\left(\overline{w}\right)$, if both n and m are large enough. This can be represented as:

$$\frac{c}{n}\underset{n\to \infty }{\overset{\mathrm{Law} \mathrm{of} \mathrm{large} \mathrm{numbers}}{\to }}P\left(\overline{w}\right)\underset{m\to \infty }{\overset{CLT}{\leftarrow }}{P}_{OOV}\left(\overline{w}\right)\Rightarrow \frac{c}{n}\approx P_{OOV}\left(\overline{w}\right).$$

Unlike $P\left(\overline{w}\right)\approx P_{OOV}\left(\overline{w}\right)$, ref [12] actually does derive error for $\frac{c}{n}\approx P\left(\overline{w}\right)$ approximation, and how large n should be in order to make the error negligible:

$\frac{c}{n}\in (P\left(\overline{w}\right)-|r{P}^{\prime }\left(\overline{w}\right)|,P\left(\overline{w}\right)+|r{P}^{\prime }\left(\overline{w}\right)\left|\right)$ with probability $1-erfc\left(\theta \right)$ for $n(r,\overline{w})=\frac{{\theta }^2}{r^2}R\left(\overline{w}\right)$ (Formula (2) in [12]) where $erfc\left(\theta \right)$ gets exponentially small as $\theta$ (i.e., n) increases asymptotically. Therefore, $\frac{c}{n}$ is used to estimate $P\left(\overline{w}\right)$ for n large enough.

However, as the final approximation (3) contains estimate $P\left(\overline{w}\right)\approx P_{OOV}\left(\overline{w}\right)$ whose error was not assessed in [12], its error is also unknown. The bound of the error for (3) is essential, because if these approximate values $P_{OOV}\left(\overline{w}\right)$ deviate too much from the actual $P\left(\overline{w}\right)$ values, it could lead to the wrong decision of $\overline{w}$. Let us remember that in the OOV attack the weight of noise vector $\overline{\mathbf{e}}$ is $\overline{w}$, if $P_{OOV}-1\left(\frac{c}{n}\right)$ is closest to $\overline{w}$, for all possible values of $\overline{w}$.

3.1.4. Main Conclusions

We summarize the mistakes in the theoretical analysis behind the OOV attack from [12], found in the analysis given above, which will turn out as crucial for high error rate of the OOV weight estimate:

• The distribution of the Hamming weight of cumulative noise vector is wrongly assessed as Binomial,
• Approximation $P\left(\overline{w}\right)\approx P_{OOV}\left(\overline{w}\right)$ lacks error estimation,
• The error of the weight estimate procedure is unknown. Since error bound of $P\left(\overline{w}\right)\approx P_{OOV}\left(\overline{w}\right)$ is unknown, this consequently also stands for the final approximation $\frac{c}{n}\approx P_{OOV}\left(\overline{w}\right)$ which produces the output of weight estimate procedure.

In the following sections, we introduce our research process to overcome the listed omissions.

3.2. Error Estimation of Acceptance Rates Approximation $P\left(\overline{w}\right)\approx P_{OOV}\left(\overline{w}\right)$

First, we infer the standard upper error bound of $P\left(\overline{w}\right)\approx P_{OOV}\left(\overline{w}\right)$ by applying Berry-Esseen inequality for CLT approximations. The obtained result indicates that distance between $P\left(\overline{w}\right)$ and $P_{OOV}\left(\overline{w}\right)$ could be too high and thus prevent a correct weight estimation. Then, we proceed to infer the exact distribution of the acceptance rates and the exact error of this approximation.

3.2.1. Standard Upper Error Bound for CLT Approximations

Approximation $P\left(\overline{w}\right)=Pr[\parallel \mathbf{e}\oplus \overline{\mathbf{e}}\parallel \le thr]\approx P_{OOV}\left(\overline{w}\right)=\mathsf{\Phi }\left(\frac{thr-(m-\overline{w})\tau -\overline{w}(1-\tau )}{\sqrt{m\tau (1-\tau )}}\right)$ was derived in [12] using the CLT, which only implies its convergence when $m\to \infty$. The Berry-Eseen inequality further refines this result by providing bound on its maximal error. Here, we show that the sum $\parallel \mathbf{e}\oplus \overline{\mathbf{e}}\parallel$ follows Poisson-Binomial distribution, not the plain Binomial distribution as claimed in [12]. Then we apply a general CLT for non-identical random variables to this distribution in order to obtain $P\left(\overline{w}\right)\approx P_{OOV}\left(\overline{w}\right)$, and we estimate its precision using the Berry-Eseen inequality.

Definition 2.

Poisson-Binomial distribution is a probability distribution of a sum ${\sum }_{i=0}^n{X}_i$ of independent Bernoulli random variables $X_1,\dots ,X_n$ with possibly different probabilities of success $p_1,\dots ,p_n$, and we denote it by $\mathcal{PB}(p_1,\dots ,p_n)$. Binomial distribution is a special case of the Poisson-Binomial distribution where $X_1,\dots ,X_n$ share the same probability of success.

Lemma 1.

The Hamming weight of cumulative noise vector $\parallel \mathbf{e}\oplus \overline{\mathbf{e}}\parallel$, where $\parallel \overline{\mathbf{e}}\parallel =\overline{w}$, which the Reader computes in the verification phase after MIM modification $(\overline{\mathbf{a}},\overline{\mathbf{b}},\overline{\mathbf{z}}=\overline{\mathbf{a}}\mathbf{X}\oplus \overline{\mathbf{b}}\mathbf{Y}\oplus \overline{\mathbf{e}})$ of Random HB# or HB# protocol session, follows Poisson-Binomial distribution

$\mathcal{PB}(\underset{\overline{w}}{\underbrace{1-\tau ,\dots ,1-\tau }},\underset{m-\overline{w}}{\underbrace{\tau ,\dots ,\tau }})$.

Proof. 

Since a new noise vector $\mathbf{e}\leftarrow {\mathrm{B}er}_{\tau }^m$ is being generated in each modification session, and $\overline{\mathbf{e}}\leftarrow {\mathrm{B}er}_{\tau }^m$ remains fixed during all modifications, notice that:

$$\begin{array}{c}\hfill \parallel \mathbf{e}\oplus \overline{\mathbf{e}}\parallel =\sum _{k=1}^m({\mathbf{e}}_{\mathbf{k}}\oplus {\overline{\mathbf{e}}}_{\mathbf{k}})=\sum _{\begin{array}{c}k=1\\ {\overline{\mathbf{e}}}_{\mathbf{k}}=1\end{array}}^m({\mathbf{e}}_{\mathbf{k}}\oplus 1)+\sum _{\begin{array}{c}k=1\\ {\overline{\mathbf{e}}}_{\mathbf{k}}=0\end{array}}^m{\mathbf{e}}_{\mathbf{k}}=\sum _{k=1}^{\overline{w}}{\tilde{s}}_k+\sum _{k=1}^{m-\overline{w}}{s}_k,\end{array}$$

(4)

where $s_k$ and ${\tilde{s}}_k$ are Bernoulli random variables, such that $Pr[s_k=1]=\tau$ and $Pr[{\tilde{s}}_k=1]=1-\tau$ (see Figure 4).

Therefore, $\parallel \mathbf{e}\oplus \overline{\mathbf{e}}\parallel \leftarrow \mathcal{PB}(\underset{\overline{w}}{\underbrace{1-\tau ,\dots ,1-\tau }},\underset{m-\overline{w}}{\underbrace{\tau ,\dots ,\tau }})$.  □

Theorem 1

(General CLT, Lyapunov condition [26]). Let $X_1,X_2\dots$ be a sequence of independent (and not necessarily identical) random variables such that $E{X}_i={\mu }_i$, $Var{X}_i={\sigma }_i^2<\infty$ and $D_n^2=Var\left({\sum }_{i=1}^n{X}_i\right)={\sum }_{i=1}^n{\sigma }_i^2$. If there is $\delta >0$ such that:

$$\underset{n\to \infty }{lim}\frac{1}{D_n^{2+\delta }}\sum _{i=1}^{n}E\left(\right|X_i-{\mu }_i{\left|\right)}^{2+\delta }=0\left(\mathit{Lyapunov}\mathit{condition}\right)$$

then the distributions of $\frac{{\sum }_{i=1}^n{X}_i-{\sum }_{i=1}^n{\mu }_i}{D_n}$ converge weakly to $\mathcal{N}(0,1)$ as $n\to \infty$, that is,

$$\frac{{\sum }_{i=1}^n{X}_i-{\sum }_{i=1}^n{\mu }_i}{D_n}\stackrel{\mathcal{D}}{\to }\mathcal{N}(0,1).$$

Theorem 2

(General CLT for Poisson-Binomial distribution). If random variable X follows Poisson-Binomial distribution i.e., $X={\sum }_{i=1}^n{X}_i$, $X_i\leftarrow {\mathrm{B}er}_{p_i}$, where $D_n^2=Var\left(X\right)={\sum }_{i=1}^n{p}_i(1-p_i)$, and $D_n\to \infty (n\to \infty )$, then:

$$\frac{X-{\sum }_{i=1}^n{p}_i}{D_n}\stackrel{\mathcal{D}}{\to }\mathcal{N}(0,1).$$

Proof of Theorem 2. 

Let ${\mu }_i=E\left(X_i\right)=p_i$. We prove the Lyapunov condition is satisfied for $\delta =1$.

Since $X_i:\left(\begin{array}{cc}1& 0\\ p_i& 1-p_i\end{array}\right),{|X_i-{\mu }_i|}^3:\left(\begin{array}{cc}{(1-{\mu }_i)}^3& {\mu }_i^3\\ p_i& 1-p_i\end{array}\right)$, we have that:

$$\begin{array}{cc}\hfill E|X_i-{\mu }_i{|}^3& ={(1-{\mu }_i)}^3{p}_i+{\mu }_i^3(1-p_i)\hfill \\ \hfill & ={(1-p_i)}^3{p}_i+p_i^3(1-p_i)\hfill \\ \hfill & =p_i(1-p_i)[{(1-p_i)}^2+p_i^2]\hfill \\ \hfill & =p_i(1-p_i)[1-2p_i(1-p_i)]\le p_i(1-p_i),i=1,\dots ,n.\hfill \end{array}$$

Therefore ${\sum }_{i=1}^{n}E\left(\right|X_i-{\mu }_i{\left|\right)}^3\le {\sum }_{i=1}^n{p}_i(1-p_i)=D_n^2$ and

$$\frac{1}{D_n^3}\sum _{i=1}^{n}E\left(\right|X_i-{\mu }_i{\left|\right)}^3\le \frac{D_n^2}{D_n^3}=\frac{1}{D_n}\to 0(n\to \infty ).$$

 □

Since $\mu =E(\parallel \mathbf{e}\oplus \overline{\mathbf{e}}\parallel )=\overline{w}(1-\tau )+(m-\overline{w})\tau$ and $Var(\parallel \mathbf{e}\oplus \overline{\mathbf{e}}\parallel )=m\tau (1-\tau )$, as a direct consequence of Theorem 2 and Lemma 1, we have that:

Lemma 2.

For the cumulative noise vector $\mathbf{e}\oplus \overline{\mathbf{e}}$ it holds that:

$$\frac{\parallel \mathbf{e}\oplus \overline{\mathbf{e}}\parallel -(m-\overline{w})\tau -\overline{w}(1-\tau )}{\sqrt{m\tau (1-\tau )}}\stackrel{\mathcal{D}}{\to }\mathcal{N}(0,1),m\to \infty .$$

In order to estimate the precision of this approximation, we proceed to use the standard error measure for general CLT:

Theorem 3

(Berry-Eseen inequality for non-identical random variables [27]). Let $X_1,\dots ,X_n$ be independent random variables such that $E{X}_i=0$, $Var{X}_i={\sigma }_i^2$, and $D_n^2=Var\left({\sum }_{i=1}^n{X}_i\right)={\sum }_{i=1}^n{\sigma }_i^2$. Then for every n there is an absolute constant C such that:

$$\underset{x\in \mathbb{R}}{sup}\left|Pr\left[\frac{X}{D_n}\le x\right]-\mathsf{\Phi }\left(x\right)\right|\le C·\frac{{\sum }_{i=1}^{n}E{\left|X_i\right|}^3}{D_n^3}.$$

It was proven that $0.4097\approx \frac{\sqrt{10}+3}{6\sqrt{2\pi }}=C_0\le C\le C_1=0.5600$ ([28]). $C_0$ is the biggest known lower bound and $C_1$ the smallest known upper bound for C in literature, to the best of our knowledge.

Theorem 4

(Berry-Eseen inequality for Poisson-Binomial distribution). If random variable X follows Poisson-Binomial distribution, that is, $X={\sum }_{i=1}^n{X}_i$, $X_i\leftarrow {\mathrm{B}er}_{p_i}$, where $D_n^2=Var\left(X\right)={\sum }_{i=1}^n{p}_i(1-p_i)$, and $D_n\to \infty (n\to \infty )$, then for every n there is a constant $C\in [C_0,C_1]$ such that:

$$\underset{x\in \mathbb{R}}{sup}\left|Pr\left[\frac{X-{\sum }_{i=1}^n{p}_i}{D_n}\le x\right]-\mathsf{\Phi }\left(x\right)\right|\le C·\frac{{\sum }_{i=1}^n{p}_i(1-p_i)[{(1-p_i)}^2+p_i^2]}{D_n^3}$$

Proof. 

Let $Y_i=X_i-{\mu }_i$, ${\mu }_i=E{X}_i=p_i$. Then $E{Y}_i=0,Var\left(Y_i\right)=p_i(1-p_i)$ and $E|Y_i{|}^3=p_i(1-p_i)[{(1-p_i)}^2+p_i^2]$ (see proof of Theorem 2). The claim follows directly by applying Berry-Eseen inequality to random variables $Y_1,\dots ,Y_n$.  □

Lemma 3.

For the cumulative noise vector $\mathbf{e}\oplus \overline{\mathbf{e}}$ it holds that:

$$\underset{x\in \mathbb{R}}{sup}\left|Pr\left[\frac{\parallel \mathbf{e}\oplus \overline{\mathbf{e}}\parallel -(m-\overline{w})\tau -\overline{w}(1-\tau )}{\sqrt{m\tau (1-\tau )}}\le x\right]-\mathsf{\Phi }\left(x\right)\right|\le C·\frac{[{(1-\tau )}^2+{\tau }^2]}{\sqrt{m\tau (1-\tau )}},$$

where $C\in [C_0,C_1]$.

Proof. 

This is a direct consequence of the inequality above, taken in consideration that: $\parallel \mathbf{e}\oplus \overline{\mathbf{e}}\parallel ={\sum }_{i=1}^m{X}_i$, $X_i\leftarrow {\mathrm{B}er}_{p_i}$, $p_i=\left\{\begin{array}{c}1-\tau ,i=1,\dots ,\overline{w}\hfill \\ \tau ,i=\overline{w}+1,\dots ,m\hfill \end{array}\right.,$

${\sum }_{i=1}^m{p}_i=(m-\overline{w})\tau +\overline{w}(1-\tau )$,

$D_m^2=Var\left(X\right)=m\tau (1-\tau )$,

${\sum }_{i=1}^n{p}_i(1-p_i)[{(1-p_i)}^2+p_i^2]=m\tau (1-\tau )[{(1-\tau )}^2+{\tau }^2]=D_m^2[{(1-\tau )}^2+{\tau }^2]$.  □

As a consequence of this Lemma, by taking $x=\frac{thr-\mu }{\sigma }$, $\mu =(m-\overline{w})\tau +\overline{w}(1-\tau )$ and ${\sigma }^2=m\tau (1-\tau )$, the standard Berry-Eseen upper bound estimate for the error of the approximation $P\left(\overline{w}\right)\approx P_{OOV}\left(\overline{w}\right)$ is:

$$\begin{array}{c}\hfill \left|Pr[\parallel \mathbf{e}\oplus \overline{\mathbf{e}}\parallel \le thr]-\mathsf{\Phi }\left(\frac{thr-\mu }{\sigma }\right)\right|\le \overline{C},\end{array}$$

(5)

where $\overline{C}\in [C_0·\frac{[{(1-\tau )}^2+{\tau }^2]}{\sigma },C_1·\frac{[{(1-\tau )}^2+{\tau }^2]}{\sigma }]$.

Using Formula (5) we derive that for the standard parameter set I, where $\tau =0.25$ and $m=1164$, the error upper bound lies in the interval $[0.017334,0.023691]$, while for the standard parameter set II, where $\tau =0.125$ and $m=441$, the error upper bound is from the interval $[0.046091,0.062994]$.

The exact $P\left(\overline{w}\right)$ lies somewhere in the interval $[(P_{OOV}\left(\overline{w}\right)-\overline{C},P_{OOV}\left(\overline{w}\right)+\overline{C}]$. Nevertheless, this interval is wider, i.e., covers the interval in which the adversary has to decide between adjacent weights $\overline{w}$ and $\overline{w}+1$ (see Figure 5). It is possible that the adversary is incapable to determine and decide accurately if $\frac{c}{n}$ is closest to $P\left(\overline{w}\right)$ or $P(\overline{w}+1)$, which directly jeopardizes his decision making. For example, if $\frac{c}{n}$ is in the position marked in Figure 6, the adversary will decide that the weight is $\overline{w}$, because $P_{OOV}\left(\overline{w}\right)$ is closest to it, but since $\frac{c}{n}$ is in a possible location of $P(\overline{w}+1)$, it could in fact be closest to $P(\overline{w}+1)$, and the actual weight could be $\overline{w}+1$. In order to investigate possibility of such scenarios of erroneous weight conclusions due to high error of approximation, in the next Section, we shall determine where precisely are $P\left(\overline{w}\right)$ values.

3.2.2. The Exact Distribution of the Acceptance Rates

Here, we calculate the exact acceptance rate of HB# and Random-HB# protocols while under the OOV attack, by using Lemma 1 from Section 3.2.1.

Theorem 5.

Let $P\left(\overline{w}\right)=P[\parallel \mathbf{e}\oplus \overline{\mathbf{e}}\parallel \le thr]$ denote the probability of successful authentication after MIM modification using triplet $(\overline{\mathbf{a}},\overline{\mathbf{b}},\overline{\mathbf{z}}=\overline{\mathbf{a}}\mathbf{X}\oplus \overline{\mathbf{b}}\mathbf{Y}\oplus \overline{\mathbf{e}})$ of exchanged messages caught in a Random HB# or HB# protocol session, where $\overline{w}=\parallel \overline{\mathbf{e}}\parallel$. Then:

$$\begin{array}{c}\hfill P\left(\overline{w}\right)=PB\left(\overline{w}\right):=\sum _{j=0}^{thr}\sum _{\begin{array}{c}i=max\{0,j+\overline{w}-m\}\end{array}}^{min\{\overline{w},j\}}\left(\genfrac{}{}{0pt}{}{\overline{w}}{i}\right)\left(\genfrac{}{}{0pt}{}{m-\overline{w}}{j-i}\right){\tau }^{\overline{w}+j-2i}{(1-\tau )}^{m-(\overline{w}+j-2i)}.\end{array}$$

(6)

In addition, if c is the number of successful authentications after n MIM modifications, then for acceptance rate $\frac{c}{n}$ it holds that

$$\frac{c}{n}\leftarrow \frac{Bin(n,P\left(\overline{w}\right))}{n}.$$

Proof. 

Since:

$$\parallel \mathbf{e}\oplus \overline{\mathbf{e}}\parallel =\sum _{k=1}^m({\mathbf{e}}_{\mathbf{k}}\oplus {\overline{\mathbf{e}}}_{\mathbf{k}})=\sum _{\begin{array}{c}k=1\\ {\overline{\mathbf{e}}}_{\mathbf{k}}=1\end{array}}^m({\mathbf{e}}_{\mathbf{k}}\oplus 1)+\sum _{\begin{array}{c}k=1\\ {\overline{\mathbf{e}}}_{\mathbf{k}}=0\end{array}}^m{\mathbf{e}}_{\mathbf{k}}=\sum _{k=1}^{\overline{w}}{\tilde{s}}_k+\sum _{k=1}^{m-\overline{w}}{s}_k,$$

where $s_k\leftarrow {\mathrm{B}er}_{\tau }$, ${\tilde{s}}_k\leftarrow {\mathrm{B}er}_{1-\tau }$ (see Proof of Lemma 1) we have that:

$$\begin{array}{cc}\hfill P\left(\overline{w}\right)& =Pr[\parallel \mathbf{e}\oplus \overline{\mathbf{e}}\parallel \le thr]\hfill \\ \hfill & =\sum _{j=0}^{thr}Pr[\parallel \mathbf{e}\oplus \overline{\mathbf{e}}\parallel =j]\hfill \\ \hfill & =\sum _{j=0}^{thr}Pr[\sum _{k=1}^{\overline{w}}{\tilde{s}}_k+\sum _{k=1}^{m-\overline{w}}{s}_k=j]\hfill \\ \hfill & =\sum _{j=0}^{thr}\sum _{i=0}^j\left\{Pr[\sum _{k=1}^{\overline{w}}{\tilde{s}}_k=i]·Pr[\sum _{k=1}^{m-\overline{w}}{s}_k=j-i]|i\le \overline{w},j-i\le m-\overline{w}\right\}\hfill \\ \hfill & =\sum _{j=0}^{thr}\sum _{\begin{array}{c}i\le \overline{w}\\ j-i\le m-\overline{w}\\ i=0\end{array}}^j\left[\left(\genfrac{}{}{0pt}{}{\overline{w}}{i}\right){(1-\tau )}^i{\tau }^{\overline{w}-i}\right]\left[\left(\genfrac{}{}{0pt}{}{m-\overline{w}}{j-i}\right){\tau }^{j-i}{(1-\tau )}^{m-\overline{w}-j+i}\right]\hfill \\ \hfill & =\sum _{j=0}^{thr}\sum _{\begin{array}{c}i=max\{0,j+\overline{w}-m\}\end{array}}^{min\{\overline{w},j\}}\left(\genfrac{}{}{0pt}{}{\overline{w}}{i}\right)\left(\genfrac{}{}{0pt}{}{m-\overline{w}}{j-i}\right){\tau }^{\overline{w}+j-2i}{(1-\tau )}^{m-(\overline{w}+j-2i)}.\hfill \end{array}$$

 □

(Number of successes in $\overline{w}$ Bernoulli experiments can not exceed $\overline{w}$. Similarly for $m-\overline{w}$.)

3.2.3. Exact Error of the Approximation $P\left(\overline{w}\right)\approx P_{OOV}\left(\overline{w}\right)$

Finally, we are able to derive the exact error of the $P_{OOV}$ approximation as:

$$|P\left(\overline{w}\right)-P_{OOV}\left(\overline{w}\right)|=|\sum _{j=0}^{thr}\sum _{\begin{array}{c}i=max\{0,j+\overline{w}-m\}\end{array}}^{min\{\overline{w},j\}}\left(\genfrac{}{}{0pt}{}{\overline{w}}{i}\right)\left(\genfrac{}{}{0pt}{}{m-\overline{w}}{j-i}\right){\tau }^{\overline{w}+j-2i}{(1-\tau )}^{m-(\overline{w}+j-2i)}-\mathsf{\Phi }\left(\frac{thr-\mu }{\sigma }\right)|,$$

(7)

where $\mu =(m-\overline{w})\tau +\overline{w}(1-\tau )$ and ${\sigma }^2=m\tau (1-\tau )$.

Although, in theory, this error diminishes for m large enough (see Figure 7), in the OOV attack m is the dimension of secret matrices. Thus, this error is a constant intrinsic to the protocol and the adversary is unable to manipulate it.

The exact error values for standard protocol parameters are shown in Figure 8.

Note that the error gets higher as $\overline{w}$ approaches the claimed optimal weight $w_{opt}$, where it reaches its maximum. This weight is 228 for the standard parameter set I, while it is 77 for the other one.

3.3. Proper Decision Zones

The OOV decision zones, which are based on the inverse function $P_{OOV}^{-1}\left(\frac{c}{n}\right)$ values, have the following potential drawbacks, in general case:

• the inverse function might not preserve the ratios of distances, so, for example, it could be possible that $P^{-1}\left(\frac{c}{n}\right)$ is closer to $\overline{w}$ than to $\overline{w}+1$, while $\frac{c}{n}$ is actually closer to $P(\overline{w}+1)$ than to $P\left(\overline{w}\right)$,
• $P_{OOV}$ is used as an approximation of exact acceptance rates P with unknown precision,
• $\overline{w}$ should be determined by considering which of the possible distributions is $\frac{c}{n}$ most likely sampled from, i.e., by probabilistic reasoning, instead of simply applying the inverse function to $\frac{c}{n}$ value.

We employ the Bayesian reasoning over the exact distributions of acceptance rates to construct proper decision zones. The noise vector weight $\parallel \overline{\mathbf{e}}\parallel$ is estimated as $\overline{w}$ if the observed empirical acceptance frequency $\frac{c}{n}$ most likely follows the exact distribution $\frac{Bin(n,P\left(\overline{w}\right))}{n},\overline{w}\in W$, where W is the set of all the weights $\overline{w}$ the adversary considers possible.

As a general weight decision rule, $\overline{w}=\underset{w\in W}{\mathrm{argmax}}Pr[\parallel \overline{\mathbf{e}}\parallel =w|\frac{c}{n} \mathrm{observed} \mathrm{acceptance} \mathrm{rate}\left)\right]$$=\underset{w\in W}{\mathrm{argmax}}\{P{\left(w\right)}^{\frac{c}{n}}{(1-P\left(w\right))}^{1-\frac{c}{n}}·P_{occur}{\left(w\right)}^{\frac{1}{n}}\}$, where $P_{occur}\left(w\right)=Pr[\parallel \overline{\mathbf{e}}\parallel =w]$ is the probability of occurrence of noise vector whose weight is w. By its logarithmic transformation, we obtain that the adversary decides the noise vector weight as $\overline{w}$ iff:

$$\overline{w}=\underset{w\in W}{\mathrm{argmax}}\{F(c,n)=c_0\left(w\right)+c_1\left(w\right)\frac{c}{n}\},$$

where $c_0\left(w\right)=log(1-P\left(w\right))+\frac{log\left(P_{occur}\left(w\right)\right)}{n}$, $c_1\left(w\right)=log\frac{P\left(w\right)}{1-P\left(w\right)}$. After the mere eavesdropping, $P_{occur}\left(w\right)=\left(\genfrac{}{}{0pt}{}{m}{w}\right){\tau }^w{(1-\tau )}^{m-w}$. If the eavesdropped vector was flipped in f positions to reach optimal weight, $P_{occur}\left(w\right)=PB(f,m,\tau ,w)-PB(f,m,\tau ,w-1)$. When recovering bits, $P_{occur}(w-1)=\tau$ and $P_{occur}(w+1)=1-\tau$. The values $P\left(w\right)$ and $P_{occur}\left(w\right)$ may be calculated in advance, so decision making is highly efficient.

However, when considering weights near $w_{opt}$ and standard parameter sets, for n large enough, the decision making can be further simplified. Namely, after comparing variances $Var\left(w\right)=\frac{P\left(w\right)(1-P(w\left)\right)}{n}$ of the exact distributions for the consecutive weights $w-1$, w and $w+1$ in such case, we have found their differences as insufficient to impact the Bayesian decision. Also, probabilities of occurrence of these weights produce negligible priors (observe division by n in $c_0\left(w\right)$).

Therefore, because these distributions $\frac{Bin(n,P\left(\overline{w}\right))}{n}\stackrel{\mathcal{D}}{\to }\mathcal{N}(P\left(\overline{w}\right),Var\left(\overline{w}\right))$ are almost symmetrical, for all practical purposes, $\overline{w}$-decision zones will be $(\frac{P\left(\overline{w}\right)+P(\overline{w}+1)}{2},\frac{P(\overline{w}-1)+P\left(\overline{w}\right)}{2}),$ $\overline{w}=1,\dots ,m$ after eavesdropping, while they will be $(-\infty ,\frac{P(\overline{w}-1)+P(\overline{w}+1)}{2})$ and $(\frac{P(\overline{w}-1)+P(\overline{w}+1)}{2},\infty )$ when deciding between $\overline{w}+1$ and $\overline{w}-1$ after flipping a bit. We shall also call them “PB-decision zones", since they use the exact values $P\left(\overline{w}\right)=PB\left(\overline{w}\right)$. Figure 9 provides a graphical illustration of the PB-decision zones used in the processes of weight estimate after eavesdropping and bit recovery.

Expressed more formally—probability that $\frac{c}{n}$ is sampled from $\mathcal{N}(P\left(\overline{w}\right),Var\left(\overline{w}\right))$ is $g(c,n,\overline{w})=\frac{1}{\sqrt{2\pi Var\left(\overline{w}\right)}}{e}^{-\frac{(\frac{c}{n}-P{\left(\overline{w}\right)}^2)}{2Var\left(\overline{w}\right)}}{P}_{occur}\left(\overline{w}\right)$, so according to maximum a posteriori (MAP) test, we choose hypothesis $W=\overline{w}$ over $W=\overline{w}+i,i\in \{1,2\}$ iff $g(c,n,\overline{w})>g(c,n,\overline{w}+i)$ that is,

$$\sqrt{\frac{Var(\overline{w}+i)}{Var\left(\overline{w}\right)}}·\frac{P_{occur}\left(\overline{w}\right)}{P_{occur}(\overline{w}+1)}\ge e^{-\frac{{(\frac{c}{n}-P(\overline{w}+i))}^2}{2Var(\overline{w}+i)}+\frac{{(\frac{c}{n}-P\left(\overline{w}\right))}^2}{2Var\left(\overline{w}\right)}}=e^{-\frac{n}{2}(\frac{{(\frac{c}{n}-P(\overline{w}+i))}^2}{P(\overline{w}+i)(1-P(\overline{w}+i))}-\frac{{(\frac{c}{n}-P\left(\overline{w}\right))}^2}{P\left(\overline{w}\right)(1-P\left(\overline{w}\right))})},$$

that is, iff condition ${(\frac{c}{n}-P(\overline{w}+i))}^2>{\delta }^2{(\frac{c}{n}-P\left(\overline{w}\right))}^2$ is satisfied, where ${\delta }^2=\frac{P(\overline{w}+i)(1-P(\overline{w}+i))}{P\left(\overline{w}\right)(1-P\left(\overline{w}\right))}$$=\frac{Var(\overline{w}+i)}{Var\left(\overline{w}\right)}$, i.e., $\frac{c}{n}<B$ or $\frac{c}{n}>A$ when $\delta <1$, or $A<\frac{c}{n}<B$ when $\delta >1$, where $A=P(\overline{w}+i)+\frac{\delta }{\delta +1}(P\left(\overline{w}\right)-P(\overline{w}+i)),B=P\left(\overline{w}\right)+\frac{\delta }{\delta -1}(P\left(\overline{w}\right)-P(\overline{w}+i))$. However, since $B<0$ for $\delta <1$, and $B\ge 1$ for $\delta >1$, for weights near the optimal one, the condition is equivalent to $\frac{c}{n}>A$. Furthermore, $Pr\left[\frac{c}{n}\in (\frac{P\left(\overline{w}\right)+P(\overline{w}+i)}{2},A)|\frac{c}{n}\stackrel{\mathcal{D}}{\to }\mathcal{N}(P\left(w\right),{\sigma }^2),w\in \{\overline{w},\overline{w}+i\}\right]$ is negligible in such case, so we reduce this decision to condition $\frac{c}{n}>\frac{P\left(\overline{w}\right)+P(\overline{w}+i)}{2}$, that is, that the observed frequency $\frac{c}{n}$ is closer to $P\left(\overline{w}\right)$ than to $P(\overline{w}+i)$ (P is monotone decreasing function).

3.4. The Exact and the Approximate Probability Distribution Relation

We now show that the decisions the adversary makes about noise vectors weights can differ depending on whether he uses the OOV approximation or the exact distribution.

We have noticed that the OOV w-decision zones are substantially shifted to the left with respect to PB-w decision zones, and that they often largely overlap with the correct PB-$w+1$ decision zone (see Figure 10). As a consequence, there is a high chance that the OOV adversary decides the weight is w, while the actual weight is $w+1$.

This adverse phenomena is especially pronounced in the expected case—when $\overline{w}$ is near the optimal weight $w_{opt}$, since there is the biggest distance between $P\left(\overline{w}\right)$ and $P_{OOV}\left(\overline{w}\right)$—degrading significantly the precision of the weight estimate.

Furthermore, the shift of the OOV decision zones can not be repaired by employing larger “sample size” n, that is, number of intercepted authentications, because the approximation $P_{OOV}\left(\overline{w}\right)\approx P\left(\overline{w}\right)$ has a high fixed error in this scenario (as shown in the previous Section). The convergence $\frac{c}{n}\to P_{OOV}\left(\overline{w}\right)$ occurs only when both $m\to \infty$ and $n\to \infty$:

$$\frac{c}{n}\underset{n\to \infty }{\overset{}{\to }}P\left(\overline{w}\right)\underset{m\to \infty }{\overset{}{\leftarrow }}{P}_{OOV}\left(\overline{w}\right)\Rightarrow \frac{c}{n}\underset{n\to \infty ,m\to \infty }{\to }{P}_{OOV}\left(\overline{w}\right).$$

However, in the context of the OOV attack, m is a constant protocol parameter and thus:

$$\frac{c}{n}\underset{n\to \infty }{\overset{}{\to }}P\left(\overline{w}\right)\underset{\mathrm{fixed} \mathrm{distance}}{\overset{}{\leftarrow }}{P}_{OOV}\left(\overline{w}\right)\Rightarrow |\frac{c}{n}-P_{OOV}\left(\overline{w}\right)|\underset{n\to \infty }{\to }|P\left(\overline{w}\right)-P_{OOV}\left(\overline{w}\right)|.$$

This explains the experimental observations from [25] that the weight estimate does not improve by increasing the sample size.

4. Correction of the OOV Attack

In this section, we give a correction of the OOV-MIM attack and show that it meets the targeted precision, unlike the original attack.

4.1. Correction of the OOV Attack Algorithm

In order to solve the problem of high error of the approximation $P_{OOV}\left(\overline{w}\right)\approx P\left(\overline{w}\right)$, we eliminate this approximation altogether, since we have shown that it can not be improved. Instead we employ the acceptance rates obtained from the exact distribution. That is, instead of:

$$\frac{c}{n}\underset{n\to \infty }{\overset{}{\to }}P\left(\overline{w}\right)\underset{m\to \infty }{\overset{}{\leftarrow }}{P}_{OOV}\left(\overline{w}\right)\Rightarrow \frac{c}{n}\approx P_{OOV}\left(\overline{w}\right)=\mathsf{\Phi }\left(\frac{thr-(m-\overline{w})\tau -\overline{w}(1-\tau )}{\sqrt{m\tau (1-\tau )}}\right),$$

we use Poisson-Binomial cumulative distribution function:

$$\frac{c}{n}\underset{n\to \infty }{\overset{}{\to }}P\left(\overline{w}\right)\Rightarrow \frac{c}{n}\approx P\left(\overline{w}\right)=\sum _{j=0}^{thr}\sum _{\begin{array}{c}i=max\{0,j+\overline{w}-m\}\end{array}}^{min\{\overline{w},j\}}\left(\genfrac{}{}{0pt}{}{\overline{w}}{i}\right)\left(\genfrac{}{}{0pt}{}{m-\overline{w}}{j-i}\right){\tau }^{\overline{w}+j-2i}{(1-\tau )}^{m-(\overline{w}+j-2i).}$$

Then, we incorporate it in proper, Bayesian decision zones described in Section 3.3 with their corresponding optimal weights and modification samples. Noise vector $\overline{\mathbf{e}}$ Hamming weight will be estimated as $\overline{w}$ if and only if $\frac{c}{n}$ is nearest to $P\left(\overline{w}\right)$, for all weights $w\in \{0,\dots ,m\}$ considered possible.

Hence, the pseudocode of the proposed correction of the weight estimate procedure is given in Algorithm 1:

Algorithm 1PB-OOV weight estimate alg. Approximating $\overline{w}=\parallel \overline{\mathbf{e}}\parallel$

1: Input: $\overline{\mathbf{a}},\overline{\mathbf{b}},\overline{\mathbf{z}}=\overline{\mathbf{a}}\mathbf{X}\oplus \overline{\mathbf{b}}\mathbf{Y}\oplus \overline{\mathbf{e}},n$ 2: Output:  estimate of noise vector weight     $\overline{w}=\parallel \overline{\mathbf{a}}\mathbf{X}\oplus \overline{\mathbf{b}}\mathbf{Y}\oplus \overline{\mathbf{z}}\parallel$, where $\boxed{P\left(\overline{w}\right)={\sum }_{j=0}^{thr}{\sum }_{\begin{array}{c}i=max\{0,j+\overline{w}-m\}\end{array}}^{min\{\overline{w},j\}}\left(\genfrac{}{}{0pt}{}{\overline{w}}{i}\right)\left(\genfrac{}{}{0pt}{}{m-\overline{w}}{j-i}\right){\tau }^{\overline{w}+j-2i}{(1-\tau )}^{m-(\overline{w}+j-2i)}}$ 3: Processing: 4: $c=0$ 5: for$i=1\dots n$do 6:     During i-th session, the adversary modifies and replaces messages: 7:     $\mathbf{a}$ with $\widehat{\mathbf{a}}=\mathbf{a}\oplus \overline{\mathbf{a}}$, $\mathbf{b}$ with $\widehat{\mathbf{b}}=\mathbf{b}\oplus \overline{\mathbf{b}}$, $\mathbf{z}$ with $\widehat{\mathbf{z}}=\mathbf{z}\oplus \overline{\mathbf{z}}$ 8:     if Verifier accepts the modified response then 9:         $c=c+1$ 10:     end if 11: end for 12: return$\overline{w}=\underset{w}{\mathrm{argmin}}\left\{\right|\frac{c}{n}-P\left(w\right)\left|\right|w=0,\dots ,m\}$.

Since the PB Decision zone for $w\supset I=[P\left(w\right)-\overline{r},P\left(w\right)+\overline{r}]$, where $\overline{r}=\frac{1}{2}min\{P\left(w\right)-P(w+1),P(w-1)-P\left(w\right)\}$ we have that:

$Pr[\frac{c}{n}\in \mathrm{PB} \mathrm{Decision} \mathrm{zone} \mathrm{for} w]\ge Pr\left[\frac{c}{n}\in I|\frac{c}{n}\stackrel{\mathcal{D}}{\to }\mathcal{N}(P\left(\overline{w}\right),{\sigma }^2)\right]=1-erfc\left(\theta \right),\theta =\frac{\overline{r}·\sqrt{n}}{\sqrt{2P\left(\overline{w}\right)(1-P\left(\overline{w}\right))}}$.

Therefore, after the eavesdropping, PB-OOV adversary chooses sample of size $n_{PB}=4{\theta }^2{R}_{PB}\left(w\right)$, $R_{PB}\left(w\right)=2\frac{P\left(w\right)(1-P(w\left)\right)}{{\overline{r}}^2}$ to achieve the required precision $1-erfc\left(\theta \right)$, which is based on exact values $PB\left(w\right)$ instead of approximate ones $P_{OOV}\left(w\right)$ as in Formula (2) from [12]. Accordingly, he uses optimal weight $w_{opt}^{PB}$ which minimizes this sample across all weights and its value is 229 for parameter set I, and 78 for parameter set II. After the flipping, he will use samples of size ${\theta }^2{R}_{PB}\left(w\right)$ to recover bits.

It should be noted that the values $P\left(w\right),w=0,\dots ,m$ can be calculated in advance, as a part of the preprocessing step, and stored in a table to be later used during the attack.

4.2. Comparison of the OOV and PB-OOV Attack Success

In this section we analyze the probability of success of the OOV and PB-OOV attack. Namely, we derive the probability the OOV adversary will correctly reconstruct a noise vector (and consequently recover the key) and show that, as a consequence of the approximation employed, the OOV attack is significantly less efficient than claimed in [12]. Oppositely, the PB-OOV attack proposed in Section 4.1, achieves the desired precision and efficiency.

4.2.1. Noise Vector Hamming Weight Estimate

OOV adversary. First, let us observe the distribution of acceptance rate $\frac{c}{n}$ during the attack when $\parallel \overline{\mathbf{e}}\parallel =\overline{w}$:

$$c=\sum _{i=1}^n{X}_i,X_i\leftarrow {\mathrm{B}er}_{P\left(\overline{w}\right)}\Rightarrow \frac{c}{n}\stackrel{\mathcal{D}}{\to }\mathcal{N}(P\left(\overline{w}\right),{\sigma }^2(\overline{w},n)),$$

where $\sigma =\sigma (\overline{w},n):=\sqrt{\frac{P\left(\overline{w}\right)(1-P\left(\overline{w}\right))}{n}}$.

The probability that the OOV adversary estimates that noise vector $\overline{\mathbf{e}}$ has weight $w_{est}$, when its weight is $\overline{w}$ (which may or may not be equal to $w_{est}$), using n modifications of authentication sessions is:

$$p_0(w_{est},\overline{w},n)=Pr\left[\frac{c}{n}\in \mathrm{OOV} \mathrm{Decision} \mathrm{zone} \mathrm{for} w_{est}|\parallel \overline{\mathbf{e}}\parallel =\overline{w}\right]$$

$$=Pr\left[\frac{c}{n}\in (P_{OOV}(w_{est}+\frac{1}{2}),P_{OOV}(w_{est}-\frac{1}{2}))|\frac{c}{n}\stackrel{\mathcal{D}}{\to }\mathcal{N}(P(\overline{w}),{\sigma }^2)\right]$$

$$\begin{array}{c}\hfill =\mathsf{\Phi }(\frac{P_{OOV}(w_{est}-\frac{1}{2})-P(\overline{w})}{\sigma })-\mathsf{\Phi }(\frac{P_{OOV}(w_{est}+\frac{1}{2})-P(\overline{w})}{\sigma }),\end{array}$$

(8)

Therefore, the adversary makes correct decision when $\parallel \overline{\mathbf{e}}\parallel =\overline{w}$, using n modifications, with probability $p_0(\overline{w},\overline{w},n)$.

After evaluating Formula (8), we have found that the weight will either be estimated as one lower (when the adversary is wrong, which is the majority of the time for the weights near the expected ones) or make a correct guess, that is, all other cases will appear with negligible probability (see

Table 2. Comparison of the claimed and real precision of the OOV weight estimate showing that the real precision is remarkably smaller than the claimed one.

	Parameter Set I		Parameter Set II
	HB#	Random-HB#	HB#	Random-HB#
claimed precision $=1-erfc\left(\theta \right)$	0.999315	0.999997	0.998641	0.999992
real precision $=p_0(w_{exp},w_{exp},4n_{w_{exp}})$	0.087803	0.031017	0.038852	0.006860
$p_0(w_{exp}-1,w_{exp},4n_{w_{exp}})$	0.912197	0.968983	0.961146	0.993139

). This supports the experimental findings from [25]. Table 2 shows comparison between the claimed and real precision $p_0(\overline{w},\overline{w},n)$ of the OOV weight estimate (see Appendix A

Table A1. Parameters’ values used in the OOV and PB-OOV attack.

	Parameter Set I		Parameter Set II
	HB#	Random-HB#	HB#	Random-HB#
$\theta$	2.401	3.308	2.265	3.164
$R\left(w_{exp}\right)$	16,780.41 *		269.39
$R\left(w_{opt}\right)$	2742.61
$R(w_{exp}-1)$	15,789.60		270.95
$R(w_{opt}-1)$	2743.75
$n_{w_{exp}}={\theta }^{2}R\left(w_{exp}\right)$	96,736	183,626	1382	2697
$n_{w_{opt}}={\theta }^{2}R\left(w_{opt}\right)$	15,811	30,012
$n_{w_{exp}-1}={\theta }^{2}R(w_{exp}-1)$	91,024	172,783	1390	2712
$n_{w_{opt}-1}={\theta }^{2}R(w_{opt}-1)$	15,817	30,024

* R_exp is calculated using Formula (2) from the OOV paper [12].

for details on the parameters’ values). It can be noticed that, for parameter set II, in the case of Random-HB#, the claimed precision is by two orders of magnitude smaller than the claimed. In all other cases, the discrepancy is somewhat smaller but, still, the real precision is by an order of magnitude smaller than the claimed.

PB-OOV adversary. Since $(\frac{P\left(w\right)+P(w+1)}{2},\frac{P(w-1)+P\left(w\right)}{2}),w=1,\dots ,m$ is PB-w decision zone after the eavesdropping, and PB-OOV adversary uses exact values $P\left(w\right)$ instead of the approximate ones $P_{OOV}\left(w\right)$, by analogous analysis as above, we obtain that he estimates the weight as $w_{est}$ when its actual value is $\overline{w}$ with probability:

$$p_0^{\prime }(w_{est},\overline{w},n)=\mathsf{\Phi }(\frac{P(w_{est}-1)+P(w_{est})-2P(\overline{w})}{2\sigma })-\mathsf{\Phi }(\frac{P(w_{est})+P(w_{est}+1)-2P(\overline{w})}{2\sigma })$$

Unlike the OOV weight estimate, whose precision is shown to be remarkably lower than the claimed, precision of the PB-OOV weight estimate is within the given boundaries (see

Table 3. Precision of the proposed PB-OOV algorithm meets the targeted precision for weight estimate.

	Parameter Set I		Parameter Set II
	HB#	Random-HB#	HB#	Random-HB#
targeted precision $=1-erfc\left(\theta \right)$	0.999315	0.999997	0.998641	0.999992
real precision $=p_0^{\prime }(w_{exp},w_{exp},4n_{w_{exp}})$	0.999506	0.999998	0.998641	0.999992

). This is also confirmed by the experimental results presented in Section 5.3.

4.2.2. Noise Vector Bits Recovery

Here, we compare the success rate of the OOV adversary and PB-OOV adversary when it comes to the reconstruction of noise vectors, that is, bit recovery.

OOV adversary. After the adversary has estimated the weight of the observed vector $\overline{\mathbf{e}}$ as $w_{est}$ after eavesdropping, he tries to recover its bits by flipping one by one each bit ${\overline{\mathbf{e}}}_{\mathbf{i}}$ and estimating new weight as $w_{est}-1$ or $w_{est}+1$. If the weight has decreased, he concludes the flipped bit is 1, otherwise, that the bit is 0. Therefore, he recovers a bit correctly, depending on its value, with probabilities:

$$=\left\{\begin{array}{c}Pr\left[\frac{c}{n}\in \mathrm{OOV} \mathrm{Decision} \mathrm{zone} \mathrm{for} w_{est}-1\right],{\overline{\mathbf{e}}}_{\mathbf{i}}=1\hfill \\ Pr\left[\frac{c}{n}\in \mathrm{OOV} \mathrm{Decision} \mathrm{zone} \mathrm{for} w_{est}+1\right],{\overline{\mathbf{e}}}_{\mathbf{i}}=0\hfill \end{array}\right.$$

$$=\left\{\begin{array}{c}Pr\left[\frac{c}{n}>P_{OOV}\left(w_{est}\right)|\frac{c}{n}\stackrel{\mathcal{D}}{\to }\mathcal{N}(P(\overline{w}-1),{\sigma }^2(\overline{w}-1,n))\right],{\overline{\mathbf{e}}}_{\mathbf{i}}=1\hfill \\ Pr\left[\frac{c}{n}\le P_{OOV}\left(w_{est}\right)|\frac{c}{n}\stackrel{\mathcal{D}}{\to }\mathcal{N}(P(\overline{w}+1),{\sigma }^2(\overline{w}+1,n))\right],{\overline{\mathbf{e}}}_{\mathbf{i}}=0\hfill \end{array}\right.$$

$$\begin{array}{c}\hfill =\left\{\begin{array}{c}{p}_{i_1}(w_{est},\overline{w},n)=1-\mathsf{\Phi }\left(\frac{P_{OOV}\left(w_{est}\right)-P(\overline{w}-1)}{\sigma (\overline{w}-1,n)}\right),{\overline{\mathbf{e}}}_{\mathbf{i}}=1\hfill \\ p_{i_0}(w_{est},\overline{w},n)=\mathsf{\Phi }\left(\frac{P_{OOV}\left(w_{est}\right)-P(\overline{w}+1)}{\sigma (\overline{w}+1,n)}\right),{\overline{\mathbf{e}}}_{\mathbf{i}}=0.\hfill \end{array}\right.\end{array}$$

(9)

The results of evaluation of Formula (9) are shown in

Table 4. Comparison of the claimed and real precision of the OOV bit recovery depending on the initial weight estimate.

	Parameter Set I		Parameter Set II
	HB#	Random-HB#	HB#	Random-HB#
claimed precision $=1-\frac{1}{2}erfc\left(\theta \right)$	0.999658	0.9999986	0.999320	0.999996
$p_{i_1}(w_{exp},w_{exp},n_{w_{exp}})$	$1-4.4\times {10}^{-9}$	$1-1.1\times {10}^{-15}$	$1-5.5\times$${10}^{-9}$	$1-7.1\times$${10}^{-16}$
$p_{i_1}(w_{opt},w_{opt},n_{w_{opt}})$	$1-4.6\times {10}^{-13}$	$1-3.9\times {10}^{-23}$
$p_{i_0}(w_{exp},w_{exp},n_{w_{exp}})$	0.858089	0.930114	0.764623	0.843169
$p_{i_0}(w_{opt},w_{opt},n_{w_{opt}})$	0.365592	0.317990
$p_{i_1}(w_{exp}-1,w_{exp},n_{w_{exp}-1})$	0.991712	0.999518	0.993508	0.999740
$p_{i_1}(w_{opt}-1,w_{opt},n_{w_{opt}-1})$	0.999908	$1-1.3\times {10}^{-7}$
$p_{i_0}(w_{exp}-1,w_{exp},n_{w_{exp}-1})$	0.999997	$1-2.8\times {10}^{-10}$	0.999957	$1-2.1\times$${10}^{-8}$
$p_{i_0}(w_{opt}-1,w_{opt},n_{w_{opt}-1})$	0.998863	0.999987

. First, it should be noted that the probability for bit recovery is very asymmetrical, that is, the precision for 0-bit recovery is very different from the precision for 1-bit, while the claimed precision is uniform for both bit values. Secondly, when the weight is correctly estimated, the precision for 0-bit is much lower than the claimed and it would make reconstruction of the noise vector (and further the key recovery itself) practically impossible. This is in accordance with the experimental results from [25]. On the other hand, the OOV adversary has more success in bits recovery when the initial weight estimate is incorrect, since the relative change remains intact if the measured weights are both one lower than the actual ones. The two errors made in the weight estimate processes can neutralize each other; however, even with this mutual cancellation of the errors, the claimed precision is not achieved. Namely, the precision for 1-bit recovery is lower than the targeted $1-\frac{1}{2}erfc\left(\theta \right)$ and that lowers the probability of the attack success.

Let us further consider the probability that the OOV adversary will successfully recover a complete noise vector. We observe the expected case $\parallel \overline{\mathbf{e}}\parallel =w_{exp}$ ($=w_{opt}$ for parameter set II). As we have already noted: (a) $w_{est}$ is either $\parallel \overline{\mathbf{e}}\parallel$ or $\parallel \overline{\mathbf{e}}\parallel -1$, and (b) the noise vector is practically impossible to recover when $w_{est}=\parallel \overline{\mathbf{e}}\parallel$ due to too high error for 0-bit. Thus, for parameter set II, the probability of the OOV Adversary successfully recovering a complete m-bit noise vector of weight $\parallel \overline{\mathbf{e}}\parallel =w_{opt}$ is:

$$pvr\left(w_{exp}\right)=pvr\left(w_{opt}\right)=p_0{p}_{i_0}^{m-w_{opt}}{p}_{i_1}^{w_{opt}},$$

(10)

where $p_0=p_0(w_{opt}-1,w_{opt},4{\theta }^{2}R\left(w_{opt}\right)),p_{i_k}=p_{i_k}(w_{opt}-1,w_{opt},{\theta }^{2}R(w_{opt}-1)),k=0,1$.

Similarly, for parameter set I, the adversary needs to recover and remove $\Delta =w_{est}-w_{opt}$ errors in a noise vector in order to achieve the optimal weight. This is expected to happen after recovering $\Delta /\tau$ bits, thus:

$$pvr\left(w_{exp}\right)=p_0{p}_{i_0}^{*w_0}{p}_{i_0}^{m-w_{exp}-w_0}{p}_{i_1}^{*\Delta }{p}_{i_1}^{w_{exp}-\Delta },$$

(11)

where: $p_0=p_0(w_{exp}-1,w_{exp},4{\theta }^{2}R\left(w_{exp}\right)),p_{i_k}^{*}=p_{i_k}(w_{exp}-1,w_{exp},{\theta }^{2}R(w_{exp}-1)),p_{i_k}=p_{i_k}(w_{opt},w_{opt}+1,{\theta }^{2}R\left(w_{opt}\right)),k=0,1,w_0=\frac{\Delta (1-\tau )}{\tau }=\frac{(w_{exp}-1-w_{opt})(1-\tau )}{\tau }$.

Using Formulas (10) and (11) we can evaluate the probability that the OOV adversary will correctly recover a complete noise vector in the expected case, and compare the obtained probability with the claimed one, which is calculated based on the claimed probabilities of correct weight estimate and bit guess as $(1-erfc\left(\theta \right)){(1-\frac{1}{2}erfc\left(\theta \right))}^m$. Results of the comparison are given in

Table 5. Comparison of the claimed and real precision of the OOV noise vector recovery showing that the real precision is smaller than the claimed one.

	Parameter Set I		Parameter Set II
	HB#	Random-HB#	HB#	Random-HB#
claimed precision	0.670720	0.998314	0.739967	0.998306
$pvr\left(w_{exp}\right)$	0.245168	0.932141	0.573019	0.973427

. Although the difference between the claimed and real precision on the noise vector level does not seem remarkable for Random-HB#, it does make a significant impact on the key recovery probability, having in mind the number of noise vector that have to be reconstructed, which is 592. More details will be provided in the next Section 4.2.3.

PB-OOV adversary. For the PB-OOV adversary, by replacing $P_{OOV}$ with P, and $P_{OOV}\left(w_{est}\right)$ with $\frac{P(w_{est}-1)+P(w_{est}+1)}{2}$ (i.e., by using proper PB $\overline{w}$-decision zones) in the derivation above, the probabilities of successful bit recovery, depending on its value are:

$$\begin{array}{c}\hfill \left\{\begin{array}{c}{p}_{i_1}^{\prime }(w_{est},\overline{w},n)=1-\mathsf{\Phi }\left(\frac{P(\overline{w}+1)-P(\overline{w}-1)}{2\sigma (\overline{w}-1,n)}\right),{\overline{\mathbf{e}}}_{\mathbf{i}}=1\hfill \\ p_{i_0}^{\prime }(w_{est},\overline{w},n)=\mathsf{\Phi }\left(\frac{P(\overline{w}-1)-P(\overline{w}+1)}{2\sigma (\overline{w}+1,n)}\right),{\overline{\mathbf{e}}}_{\mathbf{i}}=0.\hfill \end{array}\right.\end{array}$$

(12)

Table 6. Precision of the proposed PB-OOV algorithm meets the targeted precision for bit recovery.

	Parameter Set I		Parameter Set II
	HB#	Random-HB#	HB#	Random-HB#
targeted precision $=1-\frac{1}{2}erfc\left(\theta \right)$	0.999658	0.9999986	0.999320	0.999996
$p_{i_1}^{\prime }(w_{exp},w_{exp},n_{w_{exp}})$	0.999623	0.9999983	0.999345	0.999996
$p_{i_1}^{\prime }(w_{opt},w_{opt},n_{w_{opt}})$	0.999660	0.9999986
$p_{i_0}^{\prime }(w_{exp},w_{exp},n_{w_{exp}})$	0.999874	0.9999998	0.999351	0.999996
$p_{i_0}^{\prime }(w_{opt},w_{opt},n_{w_{opt}})$	0.999659	0.9999986

shows the precision the PB-OOV adversary achieves in the bit recovery process, when the standard parameter sets are employed. The results obtained by evaluating Formula (12) prove that the PB-OOV on the bit level does achieve the targeted precision using the OOV sample (i.e., the number of modifications). This is also confirmed by the experimental results presented in Section 5.3.

Further, we analyze the probability that the PB-OOV adversary will successfully recover a complete noise vector. We observe the expected case $\parallel \overline{\mathbf{e}}\parallel =w_{exp}$($=w_{opt}$ for parameter set II). For parameter set II, the probability is given by the formula:

$$pv{r}^{\prime }\left(w_{opt}\right)=p_0^{\prime }{p}_{i_0}^{\prime m-w_{opt}}{p}_{i_1}^{\prime w_{opt}},$$

(13)

where $p_0^{\prime }=p_0^{\prime }(w_{opt},w_{opt},{\theta }^{2}R{w}_{opt})),p_{i_k}^{\prime }=p_{i_k}^{\prime }(w_{opt},w_{opt},{\theta }^{2}R\left(w_{opt}\right)),k=0,1$.

Similarly, for parameter set I, we have that:

$$pv{r}^{\prime }\left(w_{exp}\right)=p_0^{\prime }{p}_{i_0}^{\prime *w_0}{p}_{i_0}^{\prime m-w_{exp}-w_0}{p}_{i_1}^{\prime *\Delta }{p}_{i_1}^{\prime w_{exp}-\Delta }$$

(14)

where $p_0^{\prime }=p_0^{\prime }(w_{exp},w_{exp},4{\theta }^{2}R\left(w_{exp}\right))$, $p_{i_k}^{\prime *}=p_{i_k}^{\prime }(w_{exp},w_{exp},{\theta }^{2}R\left({\overline{w}}_{exp}\right))$, $p_{i_k}^{\prime }=p_{i_k}^{\prime }(w_{opt},w_{opt}$, ${\theta }^{2}R\left({\overline{w}}_{opt}\right))$, $k=0,1$, $w_0=\frac{\Delta (1-\tau )}{\tau }=\frac{(w_{exp}-w_{opt})(1-\tau )}{\tau }$.

Using Formulas (13) and (14), we can evaluate the probability that the PB-OOV adversary will correctly recover a complete noise vector in the expected case.

Table 7. Precision of the proposed PB-OOV algorithm meets the targeted precision for noise vector recovery.

	Parameter Set I		Parameter Set II
	HB#	Random-HB#	HB#	Random-HB#
claimed precision	0.670720	0.998314	0.739967	0.998306
$pv{r}^{\prime }\left(w_{exp}\right)$	0.698279	0.998538	0.749770	0.998443

shows the results of this evaluation, which confirm that the PB-OOV attack does meet the targeted precision.

4.2.3. Secret Keys Recovery Comparison

Finally, let us compare the precision of the OOV attack and PB-OOV attack. We observe the expected case $\overline{w}=w_{exp}$($=w_{opt}$ for parameter set II). Let l be the number of secret bits, that is, secret key length and m be the noise vector length. The claimed probability of key recovery in [12] is calculated as $ckr={(1-erfc\left(\theta \right))}^{\lceil \frac{l}{m}\rceil }{(1-\frac{1}{2}erfc\left(\theta \right))}^l$. This probability is equal $0.37$.

As we have shown in Section 4.2.2, the PB-OOV attack achieves the claimed precision on bit level, therefore it can recover the secret key with probability 0.37. Let us further compare this value with the probability that the OOV adversary recovers the key. In the case of Random-HB#, the number of secret bits is $l=(k_x+k_y)m$ and the adversary has to recover $k_x+k_y=592$ complete noise vectors of length m. The probability of a key recovery can be calculated using the values from Table 5 as $pvr{\left(w_{exp}\right)}^{592}$. For parameter set I, the probability of key recovery is $8.6\times {10}^{-19}$, and for parameter set II, it is equal $1.2\times {10}^{-7}$. This is remarkably smaller than the claimed 0.37. In the case of HB#, the adversary has to recover $\lfloor \frac{l}{m}\rfloor$ complete noise vectors and additional $lmodm$ bits. For parameter set I, the probability of key recovery for HB# is 0.024, and for parameter set II, it is 0.159.

More formally, the OOV attack reconstructs the secret keys if it recovers:

-

$\lfloor \frac{l}{m}\rfloor$ whole m-bit noise vectors—which happens with probability $pvr{\left(\overline{w}\right)}^{\lfloor \frac{l}{m}\rfloor }$,

-

and then the remaining $lmodm$ bits, by guessing incorrectly one more noise vector weight, and recovering each one of them—which happens with probability $pvrest\left(\overline{w}\right)=p_0{p}_{i_1}^{(lmodm)\tau }{p}_{i_0}^{(lmodm)(1-\tau )}$ for parameter set II and

$pvrest\left(\overline{w}\right)=p_0^{*}{p}_{i_1}^{*\Delta }{p}_{i_0}^{*\frac{\Delta (1-\tau )}{\tau }}{p}_{i_1}^{(lmodm-\frac{\Delta }{\tau })\tau }{p}_{i_0}^{(lmodm-\frac{\Delta }{\tau })(1-\tau )}$ for parameter set I, since $\frac{\Delta }{\tau }<lmodm$.

Therefore, the probability of successful recovery of secret keys using OOV attack will be:

$$\begin{array}{c}\hfill Pr\left[\mathrm{OOV}-\mathrm{Attack} \mathrm{success}\right]=pvr{\left(\overline{w}\right)}^{\lfloor \frac{l}{m}\rfloor }pvrest\left(\overline{w}\right)\end{array}$$

(15)

and similarly, probability of successful recovery of secret keys using PB-OOV attack is:

$$\begin{array}{c}\hfill Pr\left[\mathrm{PB}-\mathrm{OOV}-\mathrm{Attack} \mathrm{success}\right]=pv{r}^{\prime }{\left(\overline{w}\right)}^{\lfloor \frac{l}{m}\rfloor }pvres{t}^{\prime }\left(\overline{w}\right),\end{array}$$

(16)

where $pvres{t}^{\prime }$ is the same as $pvrest$, but with symbols $p^{\prime }$ instead of p.

Complexity comparison. The complexity of the OOV attack needed to achieve the required (claimed) key recovery rate is $Comp{l}^{OOV}=\underset{n}{\mathrm{argmin}}\{Pr\left[\mathrm{OOV}-\mathrm{Attack} \mathrm{success}\right]\left(n\right)\ge ckr\}$. By increasing the number of modifications n until the claimed key recovery rate is reached, we have estimated that the complexity of the OOV attack is higher than the claimed—for parameter set II by 55% in the case of Random-HB# and by 18% for HB# (this supports the results from [25] based on experimental evaluation), and for parameter set I by 150% in the case of Random-HB# and 35% for HB#. On the other hand, since the PB-OOV attack achieves the required precision on a bit recovery level targeted in [12], its precision and complexity is in accordance with the one claimed for the original OOV attack.

5. Experimental Results and Discussion

5.1. Evaluation of the Acceptance Rates

We have conducted a set of experiments to confirm the convergence of experimentally obtained acceptance rates to the corresponding PB values. There were 4 rounds of tests, for $n=2500$, $n=5000$, n = 10,000 and n = 15,000. For each n, we generated 500 noise vectors and flipped the appropriate number of their last bits, so that the expected weight of the noise vectors is optimal, that is, 78. For each test vector $e_i$, we measured the acceptance rate and analyzed how it relates to $P_{OOV}(\parallel e_i\parallel )$ and $PB(\parallel e_i\parallel )$. In general, it can be noted that the experimental acceptance rates lie above the corresponding OOV points, but compared to the corresponding PB points, they are evenly distributed above and bellow (see Figure 11). It can also be noticed that as n increases, the experimental points concentrate around the PB points, as expected. This further explains and confirms that the OOV algorithm relaying on the OOV approximation has high error rate when it comes to weight estimate, while the corrected PB-OOV algorithm gives much better results.

Furthermore, we compare experimentally obtained acceptance rates $\frac{c\left(e_i\right)}{n}$ with OOV and PB reference points, i.e., $P_{OOV}(\parallel e_i\parallel )$ and $PB(\parallel e_i\parallel )$, using a standard error measure—Mean absolute error (MAE), and show how it relates to the correctness of weight estimates. That is, for a set ${\left\{e_i\right\}}_{i=1}^N$ of test noise vectors, we observe the MAE between the acceptance rates $\frac{c\left(e_i\right)}{n}$, where n is the number of intercepted authentication sessions (i.e., modifications), and $P_{OOV}(\parallel e_i\parallel )$ and $PB(\parallel e_i\parallel )$:

$$Avg\_dis{t}_n^{OOV}=\frac{1}{N}\sum _{i=1}^N|\frac{c\left(e_i\right)}{n}-P_{OOV}(\parallel e_i\parallel \left)\right|,$$

$$Avg\_dis{t}_n^{PB}=\frac{1}{N}\sum _{i=1}^N|\frac{c\left(e_i\right)}{n}-PB(\parallel e_i\parallel \left)\right|.$$

From the previous theoretical analysis given in Section 4.1, we have that $\frac{c\left(e_i\right)}{n}\underset{n\to \infty }{\overset{}{\to }}PB(\parallel e_i\parallel ),i=1,\dots ,N$. Therefore:

$$Avg\_dis{t}_n^{OOV}\underset{n\to \infty }{\overset{}{\to }}\frac{1}{N}\sum _{i=1}^N\left|PB\right(\parallel e_i\parallel )-P_{OOV}(\parallel e_i\parallel \left)\right|,$$

$$Avg\_dis{t}_n^{PB}\underset{n\to \infty }{\overset{}{\to }}0.$$

Consequently, the expected MAE value for the OOV points, across all possible weights $\parallel e_i\parallel$, as $n\to \infty$, converges to:

$$E(Avg\_dis{t}_{\infty }^{OOV})=\frac{1}{N}\sum _{i=1}^N\sum _{w=1}^m|PB\left(w\right)-P_{OOV}\left(w\right)|(PB(f,m,\tau ,w)-PB(f,m,\tau ,w-1)),$$

since $Pr[\parallel e_i\parallel =w]=PB(f,m,\tau ,w)-PB(f,m,\tau ,w-1)$, after flipping f last bits in $e_i$, while for the PB points they converge to: $E(Avg\_dis{t}_{\infty }^{PB})=0.$

This is in accordance with the experimental results shown in Figure 12, for different number of modifications n. Furthermore, Figure 12 and Figure 13 show that there is an inverse correlation between the distance (between the experimental and OOV points, i.e., PB points, respectively) and the accuracy of weight estimation.

5.2. Precision Comparison of the OOV and PB-OOV Weight Estimate: Experimental

Here, the differences in the weight estimate quality between the original OOV Algorithm 1 and the PB-OOV Algorithm 1 proposed in Section 4.1 are experimentally proven. We have analyzed and compared effectiveness of the two algorithms for different Hamming weights. For the standard parameter set I, 99% of all noise vectors have the weight between 250 and 330. The comparison of the algorithms is based on the sample of 5000 noise vectors whose Hamming weight is from that interval. The number of modifications employed for weight estimation corresponds to the HB# scenario. The success rate of the OOV algorithm is 20% and for the PB-OOV it is 98%. Detailed results are given in Figure 14a. For the standard parameter set II, 99% of all noise vectors have the weight between 60 and 95 (this is after flipping $(w_{opt}-m\tau )/(1-2\tau )$ bits to obtain a vector of the optimal weight from a vector of the expected weight) and the comparison of the two algorithms is based on the sample of 5000 noise vectors with the Hamming weight in this interval. The number of modifications employed for weight estimation corresponds to the HB# scenario. The experimental results again show that the success rate of the OOV algorithm is much worse than PB-OOV (11% in contrast to 99%). Details are given in Figure 14b.

5.3. Evaluation of the PB-OOV Attack Precision

In Section 2.1 from [12], the authors derive the error formula and calculate the number of modifications n that should provide the aimed accuracy of the OOV attack, that is, of the weight estimate and bit recovery. However, the analysis given in Section 4.2 shows that the precision deviates significantly from the one claimed. The analysis provides the theoretical proof that supports the experimental findings presented in [25]. On the other hand, the analysis of the proposed PB-OOV algorithm given in Section 4.2, shows that this algorithm does achieve the desired precision and efficiency. We have conducted a series of experiments in order to experimentally verify the correctness of the PB-OOV attack. The experimental results presented in this section support the conclusions of the theoretical analysis.

The tests are conducted for both HB# and Random-HB# protocols and parameter set II. The number of modifications used (“sample size”) is the one from the [12]. For the HB# protocol we have tested the weight estimate and bit recovery precision for 2000 randomly generated noise vectors of the optimal weight. The weights of two noise vector were incorrectly estimated as 79, since the obtained acceptance rates were 0.473227 and 0.475217. This gives success rate of 0.999 in weight estimation step. When the weight of a vector is incorrectly guessed, it further causes high error rate in the bit recovery process, since the algorithm relies on the initial weight estimate $w_{est}$ and chooses between $w_{est}-1$ and $w_{est}+1$ after flipping the observed bit. However, when the weight estimate is correct, targeted bit precision is $1-\frac{1}{2}erfc\left(\theta \right)$, and our tests verify that the PB-OOV attack complies with this. Namely, in the set of noise vectors whose weight is correctly estimated, the average bit guessing success rate in our test is 0.999342, compared to the targeted 0.999320. For Random-HB#, we have randomly generated 25,000 noise vectors of the optimal weight. The PB-OOV attack correctly estimated all weights, while the achieved average bit guessing success rate was 0.999996, which is in line with the targeted precision. An interesting finding regarding the OOV attack is that the bit guessing precision may significantly differ for 0-bits and 1-bits, for example, in the case of HB# and parameter set II, precision for 0-bit is 0.764623, while for 1-bit it is remarkably higher and equal $1-5.5\times {10}^{-9}$ (see Table 4). On the other hand, the proposed PB-OOV algorithm does not have this strong and distinct bias.

Table 8. PB-OOV experimentally obtained precision.

	HB#	Random-HB#
num. tests	2000	25,000
targeted OOV weight est. precision $=1-erfc\left(\theta \right)$	0.998641	0.999992
experimentally obtained weight est. precision	0.999	1
targeted OOV bit precision $=1-\frac{1}{2}erfc\left(\theta \right)$	0.999320	0.999996
experimentally obtained avg. bit precision	0.999342	0.999996
experimentally obtained 0-bit precision	0.999344	0.999996
experimentally obtained 1-bit precision	0.999333	0.999995

summarizes the results of the tests.

6. Conclusions

This paper provides a detailed examination of the OOV attack reported in [12] against the LPN based authentication protocols known as HB# and Random-HB#. We have found that the problem of discrepancy between the theoretically estimated performances and complexity in [12] and the experimentally evaluated ones in [25] arises from non-Bayesian reasoning with inadequate approximations of the probability distributions on the acceptance rates during the attack, which can not be improved due to the limitations of Central limit theorem use in the attack context. We give a correction of the attack by employing proper, Bayesian inference after establishing the exact underlying probability distributions, and prove that the new version of the attack, unlike the original one, achieves the targeted precision and complexity.

Since the OOV attack is recognized as one of the cornerstones in the analysis of any HB-like authentication protocol, our correction of the OOV attack is not only significant against Random-HB# and HB#, but also for practical security analysis of all new members of the HB-family. An interesting future direction could be a design of improved MIM attacks against HB-like protocols, which could be based on the corrected version of the OOV attack proposed in this paper.