The security of a two-party authentication protocol relies on the stored secrets of each entity are not easily compromised by adversaries. However, in the real world, hackers can always divulge the stored secrets. In this paper, we introduce the concept of the stolen-secret attack and point out that all existing secret-key based authentication protocols and password based authentication protocols suffer from this attack. We also propose two methods that defend against the stolen-secret attack. Security proof and implementation analysis are given for both methods to illustrate their soundness and usefulness.