We present a simple key-recovery attack on the LCMQ Authentication Protocol, an RFID authentication protocol proposed by Li, Gong, and Qin in 2013. We show that a successful attack is performed by solving a \textit{Learning Parity with Noise} instance in a not-too-large dimension. For the proposed LCMQ parameters, the attack requires only a few invocations with the tag under attack. When there is no restriction on the number of invocations, state-of-the-art LPN solvers recover the keys with complexity below $2^{51}$ and $2^{86}$, when attacking LCMQ parameters for security levels $80$-bit and $128$-bit, respectively. To the best of our knowledge, this is the first attack on LCMQ with complexity below exhaustive key search.