At Eurocrypt 2011, Kiltz et al. presented two efficient authentication protocols for resource-constrained devices such as radio-frequency identification tags. Kiltz et al. proved that their protocols were provably secure against active attackers. However, they did not refer to the security against man-in-the-middle (MIM) attackers. In this paper, we analyze the security of the protocols against the MIM attacks and reveal the vulnerabilities. More concretely, we propose MIM attacks on them and evaluate authentication rounds required in these attacks precisely. We assume that the tag and reader share a 2l-bit secret key. The expected number of authentication rounds to recover the secret information in the first and second protocol is at most 2l+2 and 4l+4, respectively. These attacks do not contradict the proof of security since the MIM attack is located outside the attack model that Kiltz et al. considered.