# A note on the security of hHB

A couple of days ago, a modification to the HB+ protocol was proposed  on ePrint. The proposal, called the hHB protocol, is an attempt to repair the man-in-the-middle vurnerability of HB+, in which the author is claiming to offer a provable security against these kinds of attacks. We show that there exists a trivial method to partially obtain the shared secret vectors.

In each round of hHB, the reader chooses a random vector ${x} \leftarrow^{\} \{0,1\}^k$. To transfer secret vector ${x}=x_1x_2...x_k$ to the tag, it uses a function $f(\lambda_1,\lambda_2,\lambda_3)$, the shared secret ${s}$ and random coins. This procedure is given below. Assuming that the random bits of ${x}=x_1x_2...x_k$ were successfully transferred to the tag, the following is performed to complete the authentication. According to the author, this will ensure that no man-in-the-middle attacks are possible. Although the non-constant vector ${x}$ makes the GRS-attack on the vector ${a}$ cumbersome, we can still make a slight modification of the attack.

The initial step is to pertube the first position of $b$, i.e., $b_1 \leftarrow b_1 \oplus \delta$. We the run the protocol $r$ times until we obtain a $\textsf{accept}$ or $\textsf{reject}$, based on some threshold parameter. From this line of execution, we can decide the value of $y_1$. Repeating the process $k-1$ gives us the secret vector $y=y_1y_2...y_k$.

Thwarting the attack

Assuming that the protocol keeps the integrity of $x$ and $s$ via the function $f$, we can form a new secret vector $t$, and generate $y$ from $t$ in the same way that $x$ is generated from $s$. This would further increase the transmission complexity of the protocol by a factor 2.

Let us now assume that we know $y$. Assume that we are sending bit $j$ of the vector $x$. The function $f$ sends some permutation of ${(c_1,t_1),(c_2,t_2),(c_3,t_3)}$, where each $c_i \leftarrow^\ \{0,1\}^k$. However, we do not care which permutation. The inverse function $f^{-1}$ is defined as follows. Let us pick the first position of the $c_i$-vectors and pertube that position for each $c_i$. This means that if that particular position $s_i$ in the secret is non-zero, then $x$ will take a uniformly random value in the current position $j$. If we do it for all positions, then we can test it against the verifier and thus obtain the first bit of $s$.