Preserving privacy for free: Efficient and provably secure two-factor authentication scheme with user anonymity

• We show a number of latest privacy-preserving two-factor schemes are problematic.
• De-synchronization attack is a serious threat to anonymous schemes and deserves attention.
• We present a new scheme to overcome the identified flaws with nearly no additional cost.
• Security and privacy provisions of our scheme can be proved in a widely accepted model.

Due to its simplicity, portability and robustness, two-factor authentication has received much interest in the past two decades. While security-related issues have been well studied, how to preserve user privacy in this type of protocols still remains an open problem. In ICISC 2012, Kim–Kim presented an efficient two-factor authentication scheme that attempts to provide user anonymity and to guard against various known attacks, offering many merits over existing works.However, in this paper we shall show that user privacy of Kim–Kim’s scheme is achieved at the price of severe usability downgrade – a de-synchronization attack on user’s pseudonym identities may render the scheme completely unusable unless the user re-registers. Besides this defect, it is also prone to known key attack and privileged insider attack. It is noted that our de-synchronization attack can also be applied to several latest schemes that strive to preserve user anonymity. As our main contribution, an enhanced scheme with provable security is suggested, and what we believe is most interesting is that superior security and privacy can be achieved at nearly no additional communication or computation cost. As far as we know, this work is the first one that defines a formal model to capture the feature of user un-traceability and that highlights the damaging threat of de-synchronization attack on privacy-preserving two-factor authentication schemes.