Techniques and apparatus for protecting sequence numbers used in authentication procedures are described. One technique includes receiving, from a network, an authentication request comprising at least a random challenge. After receipt of the authentication request, a synchronization parameter is generated based at least in part on a key shared by the network and the UE, the random challenge, and a first message authentication code (MAC). The synchronization parameter and the first MAC are transmitted to the network in response to the authentication request.