A challenge manipulation and restoration capability is provided for use during network authentication. A mobile device (MD) and a subscriber server (SS) each have provisioned therein a binding key (B-KEY) that is associated with a subscriber identity of a network authentication module (NAM) of the MD. The SS obtains an authentication vector (AV) in response to a request from a Radio Access Network (RAN) when the MD attempts to attach to the RAN. The AV includes an original authentication challenge parameter (ACP). The SS encrypts the original ACP based on its B-KEY, and updates the AV by replacing the original ACP with the encrypted ACP. The MD receives the encrypted ACP, and decrypts the encrypted ACP based on its B-KEY to recover the original ACP. The MD provides the original ACP to the NAM for use in computing an authentication response for validation by the RAN.