The widespread use of wireless cellular networks has made security an ever increasing concern. GSM is the most popular wireless cellular standard, but security is an issue. The most critical weakness in the GSM protocol is the use of one-way entity authentication, i.e., only the mobile station is authenticated by the network. This creates many security problems including vulnerability against man-in-the-middle attacks. Several solutions have been proposed to establish mutual entity authentication. However, none provide a aw-free bilateral authentication protocol. In this paper, we show that a recently proposed solution is vulnerable to a "type attack". Then, we propose a novel mutual entity authentication using the TESLA protocol. The proposed solution not only provides secure bilateral authentication, but also decreases the call setup time and the required connection bandwidth. An important feature of the proposed protocol is that it is compatible with the GSM standard.
 M. Rahnema. Overview of the GSM System and Protocol Architecture. IEEE Communnications Magazine, pages 92-100, 1993.
 B. Mallinder. An Overview of the GSM System. In Proceedings of the Nordic Seminar on Digital Band Mobile Radio Communnications, pages 12-15, 1988.
 K. Schramm. DES Sidechannel Collision Attacks on Smartcard Implementations. M.Sc. thesis, Ruhr-Universit Bochum, 2002.
 A. Peinado. Privacy and Authentication Protocol Providing Anonymous Channels in GSM. Computer Communication, 27:1709-1715, 2004.
 C.C. Chang, J.S. Lee, and Y.F. Chang. E_cient Authentication Protocols of GSM. Computer Communication, 28:921-928, 2005.
 V. Bocan and V. Cretu. Mitigating Denial of Service Threats in GSM Networks. In Proceedings of the International Conference on Availability, Reliability and Security (ARES2006), pages 523-528, 2006.
 K. Al-Tawil, A. Akrami, and H. Youssef. A New Authentication Protocol for GSM Network. In Proceedings of the IEEE 23rd Annual Conference on Local Computer Networks, pages 21-30, Boston, 1998.
 . Aydemir and A. Aydin Sel_cuk. A Strong User Authentication Protocol for GSM. In Proceedings of the IEEE International Workshop on Enabling Technologies, pages 150-153, 2005.
 W.D. Lin and J.-K. Jan. A Wireless-Based Authentication and Anonymous Channels for Large Scale Area. In Proceedings of the IEEE Symposium on Computers and Communications (ISCC), page 3641, 2001.
 C. Lee, M. Hwang, and W. Yang. Extension of Authentication Protocol for GSM. IEE Proceedings Communications, 150(2):91-95, 2003.
 P. R. Zimmermann. The Official PGP User's Guide, volume 1995. MIT Press, 1995.
 ITUT. The directory: Authentication framework. Technical report.
 D. Brown. Techniques for Privacy and Authentication in Personal Communication Systems. IEEE Personal Communications, pages 6-10, 1995.
 A. Perrig, R. Canetti, J.D. Tygar, and D. Song. The TESLA Broadcast Authentication Protocol. UC Berkeley and IBM Research, 5(2), 2002.
 R.J. Anderson, F. Bergadano, B. Crispo, J.H. Lee, C. Manifavas, and R.M. Needham. A New Family of Authentication Protocols. Operating Systems Review, 32(4):9-20, 1998.
 M. Bohge and W. Trappe. TESLA Certificates: An Authentication Tool for Networks of Compute- Constrained Devices. In Proceedings of the ACM Workshop on Security (WiSE'03), San Diego, CA, USA, 2003.
 M. Schwartz. Mobile Wireless Communications. Cambridge University Press, 2005.
 W. Stalling. Cryptography and Network Security. Prentice Hall, 2003.
 C. Blanchard. Security for the Third Generation (3G) Mobile System. Information Security Technical Report, 5(3):55-65, 2000.
 J.F. Stach, E.K. Parka, and K. Makkib. Performance of an Enhanced GSM Protocol Supporting Non-Repudiation of Service. Computer Communication, 22:675-680, 1999.
 R. Thomas, H. Gilbert, and G. Mazziotto. Inuence of the Mobile Station on the Performance of a Radio Mobile Cellular Network. In Proceedings of the 3rd Nordic Seminar, Copenhagen, Denmark, 1988.