Mobile Cloud Computing (MCC) fuels innovation in Mobile Computing and opens new pathways between mobile devices and infrastructures. There are several issues in MCC environment as it integrates various technologies. Among all issues, security lies on the top where many users are not willing to adopt the cloud services. This paper focuses on the authentication. The objective of this paper is to provide a mechanism for authenticating all the entities involved in accessing the cloud services. A mechanism called Key Based Mutual Authentication (KBMA) is proposed which is divided into two processes namely registration and authentication. Registration is a one-time process where the users are registered for accessing the cloud services by giving the desired unique information. Authentication process is carried out mutually to verify the identities of Device and Cloud Service Provider (CSP). Scyther tool is used for analysing the vulnerability in terms of attacks. The result claims show that the proposed mechanism is resilient against various attacks.