The invention is directed to a method for checking the integrity of messages between a mobile station and the cellular network. Two time-varying parameters are used in MAC calculation, one of which is generated by the mobile station, and the other by the network. The parameter specified by the network is used in one session only, and is transmitted to the mobile station in the beginning of the connection. The parameter specified by the mobile station is stored in the mobile station between connections in order to allow the mobile station to use a different parameter in the next connection. The parameter specified by the mobile station is transmitted to the network in the beginning of the connection.