A note on the security of hHB

A couple of days ago, a modification to the HB+ protocol was proposed [1] 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.

Function f
The inverse function f^{-1} is defined as follows.
Inverse of function f

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.

[1] https://eprint.iacr.org/2014/562.pdf

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s