In this paper, we analyze the security vulnerabilities of EMAP, an efficient RFID mutual authentication protocol recently proposed by Peris-Lopez et al. [15]. We present two effective attacks, a de-synchronization attack and a fulldisclosure attack, against the protocol. The former permanently disables the authentication capability of a RFID tag by destroying synchronization between the tag and the RFID reader. The latter completely compromises a tag by extracting all the secret information stored in the tag. The de-synchronization attack can be carried out in just round of interaction in EMAP while the full-disclosure attack is accomplished across several runs of EMAP. We also discuss ways to counter the attacks.