On the security of AUTH, a provably secure authentication protocol based on the subspace LPN problem

At the 2011 Eurocrypt, Kiltz et al., in their best paper price awarded paper, proposed an ultra-lightweight authentication protocol, called $AUTH$ . While the new protocol is supported by a delicate security proof based on the conjectured hardness of the learning parity with noise problem, this security proof does not include man-in-the-middle attacks. In this paper, we show that $AUTH$ is weak against MIM adversaries by introducing a very efficient key recovery MIM attack that has only linear complexity with respect to the length of the secret key.