The initial signaling and data exchanges over open wireless transmission channels in vehicular ad hoc networks (VANETs) renders these networks susceptible to security and privacy violation attacks such as impersonation and packet replays. To curb this, a number of protocols have been proposed such as Public Key Infrastructure (PKI) based schemes, identity (ID) based schemes, anonymity based approaches and password or biometric based schemes. However, PKI based schemes have high computational overheads while ID based schemes are vulnerable to denial of service attacks (DoS). On the other hand, password and biometric based schemes employ the long term shared secrets stored in tamper proof devices (TPD) as the sole authentication factor, rendering them vulnerable to side-channel attacks. On their part, anonymity based approaches employ either digital certificates, pseudonyms or group signatures. However, these schemes do not offer trajectory privacy, conventional signature signing and verification is inefficient, and certificate storage or revocation leads to high storage and computation costs. In this paper, a multi-factor mutual authentication protocol that addressed some of these attacks is proposed. This scheme eliminates the requirement for long term storage of secret keys on TPD and remained secure even in the face of on-broad unit (OBU) active physical attack. Simulation results showed that the proposed protocol is robust against attacks such as privileged insider, masquerade and packet replay. It also preserved backward key secrecy, forward key secrecy, password secrecy and anonymity. Its performance evaluation revealed that it exhibited average computation and communication overheads, in addition to average beacon generation and verification latencies.