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 . To transfer secret vector to the tag, it uses a function , the shared secret and random coins. This procedure is given below.
Assuming that the random bits of 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 makes the GRS-attack on the vector cumbersome, we can still make a slight modification of the attack.
The initial step is to pertube the first position of , i.e., . We the run the protocol times until we obtain a or , based on some threshold parameter. From this line of execution, we can decide the value of . Repeating the process gives us the secret vector .
Thwarting the attack
Assuming that the protocol keeps the integrity of and via the function , we can form a new secret vector , and generate from in the same way that is generated from . This would further increase the transmission complexity of the protocol by a factor 2.
Let us now assume that we know . Assume that we are sending bit of the vector . The function sends some permutation of , where each . However, we do not care which permutation.
Let us pick the first position of the -vectors and pertube that position for each . This means that if that particular position in the secret is non-zero, then will take a uniformly random value in the current position . If we do it for all positions, then we can test it against the verifier and thus obtain the first bit of .