A first cryptographic device is authenticated by a second cryptographic device. The second cryptographic device stores an alternative version of a secret value associated with the first cryptographic device as a countermeasure to compromise of the secret value. In conjunction with a protocol carried out between the first cryptographic device and the second cryptographic device, the second cryptographic device determines the secret value based at least in part on the alternative version of the secret value, and utilizes the determined secret value to authenticate the first cryptographic device. The alternative version of the secret value may comprise a randomly-skewed version of the secret value. For example, the secret value may comprise a key or other parameter of the first cryptographic device and the alternative version of the secret value may comprise a randomly-skewed version of the key or other parameter.