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

Highlights

• 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.

Abstract

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.

Introduction

With the rapid proliferation of wireless network technologies and micro-electromechanical systems, it is becoming more and more convenient for subscribers to enjoy desired services/resources from distributed service servers by using mobile devices (e.g., PDAs, PMPs, Smart phones) at any time and anywhere [78], [85]. Meanwhile, it is of utmost importance to ensure that a system’s services will not be consumed by unauthorized users in a fraudulent manner. Among numerous methods available for validating a remote user, password-based authentication is one of the most prevalent and effective approaches. Since the introduction of the seminal work (known as encrypted key exchange) of Bellovin–Merritt [5], there have been a number of remarkable proposals (e.g., [1], [12], [48]) with various levels of security and complexity, catering for diverse application scenarios.

In password-based authentication schemes, the server has to store a sensitive verifier table that contains the passwords (or the salted passwords, e.g., by using Hash or symmetric encryption) of all the registered users. One prominent issue is that once this sensitive password-verifier table is leaked (hacked), all the users’ passwords will be endangered. These days it is no surprise to see news about a catastrophic leakage of thousands of millions of passwords in the headlines [19], [24], and the prevalence of zero-day attacks [6] will further aggravate the situation. Recently, two-server password-only schemes (e.g., [47], [109]) are suggested to solve the server compromise problem, yet they are helpless to deal with another emerging problem – password leakage at the user side (e.g., malwares and social engineering [34], [62]). As deeply investigated in [105], the latter security threat can only be well addressed (i.e., achieving both reasonable security and acceptable usability) by incorporating certain trusted devices.

Owing to its portability, cryptographic capacity and tamper resistance nature, smart cards are usually introduced to serve as the “second line of defense”. In this new type of schemes (see Fig. 1), only the user with the valid smart card and the correct password can pass the verification of the remote server, while a compromise of either factor (but not both factors) would pose no danger to the system, which ensures the so-called ‘two-factor security’ [40], [87]. This sort of schemes has been widely adopted in various security-critical applications, such as e-commerce [27] and e-health [28].

In 1991, Chang and Wu [14] introduced the first smart-card-based password authentication scheme, yet it was not until 2005 that the first scheme that can achieve “truly two-factor security” was given in a seminal work by Fan et al. [30]. Despite the provision of two-factor security, Fan et al.’s scheme [30] fails to support some necessary properties like session key agreement and password update. To eliminate these weaknesses, a number of schemes were further developed [23], [39], [46], [49], [60], [79], [93], [104]. Unfortunately, most of them have been demonstrated either insecure against some basic attacks or lack of some important properties (e.g., users cannot freely choose their own passwords). The past thirty years of research on password-based authentication scheme (i.e., single-factor) has proven to be not an easy task [48], [74], the design of a practical smart-card-based password authentication scheme (i.e., two-factor) can only be harder, for the designers are faced with the challenging task of reconciling stringent usability, efficiency and security requirements [64], [69], [88]. To gain a better grasp of the difficulties and challenges in designing a secure and efficient two-factor scheme, readers are referred to the “break-fix-break-fix” history of this area in Fig. 1 of [88].

What further complicates matters is that, smart cards can no longer be deemed as fully tamper-proof devices. Recent research has reported that, the secret parameters stored in common commercial smart cards can be extracted by side-channel attacks such as power analysis [66], [67], reverse engineering [3], [70] and fault injection attacks (e.g., launched on software-supported Java Cards) [10], [54]. In other words, the previous practice of resting complete trust in the physical security of smart cards (e.g., the schemes in [17], [23], [49], [84], [93]) is highly risky in the presence of state-of-the-art side-channel attacks. In addition, there is a constant arms race going on between attackers and security practitioners. Even though the physical security of smart cards may be evaluated by independent laboratories or certified by third-party certification authorities (e.g., FIPS-201 [68] and ETSI-TS-102 [29]) at the time of their production, how much confidence can we have that they are still tamper-proof after two years of circulation? Considering this, it is more prudent and desirable to assume that the smart cards can be somehow tampered when they are in the hands of the attacker.¹

Here we give a concrete example to show that, under the new (but practical) assumption that smart cards can be somehow tampered when lost, two-factor schemes which were traditionally regarded secure may no longer be secure anymore. Consider a two-factor scheme in the client–server remote authentication environment, a user-chosen password is used to unlock the smart card which stores the user’s private key, and a standard challenge response protocol (e.g., authenticated key exchanged protocol [51]) between the card and server (which keeps the user’s corresponding public key) is used to prove user authenticity. This kind of design is quite intuitive and the resulting scheme is indeed secure if the smart cards are assumed to be tamper-proof. However, such an assumption about smart cards, as mentioned earlier, would not always be the case in reality. Once the sensitive data in the card is extracted, the proof-of-concept two-factor scheme will fall: an attacker with the victim’s lost card can extract the private key stored in the card memory, and then use this key to impersonate the victim to the server. One may wonder what if the user’s private key is not stored in plain-text but encrypted by user password? This case has been investigated in [94] and it falls short of two-factor security, too.

While security-related issues have long been the focus of the community, much less attention has been paid to how to design a privacy-preserving two-factor scheme. These years, with privacy concerns being raised rapidly among individuals and human rights organizations [2], [7], user anonymity becomes an admired property of such schemes. Instead of a unique notion of what it means to be “user anonymity”, there are a variety of flavors such as sender identity protection, sender un-traceability, sender k-anonymity, blender anonymity, controllable anonymity and so on [38], [41], [42], and quite varied (sometimes even contradictory) notions may be implemented in different application environments [53], [81]. As for remote user authentication, the notion of user anonymity is defined against the public (eavesdropping attackers) rather than the server because the server has to obtain the user’s real identity for revoking, accounting and/or billing purposes [65]. Basically, this notion means user identity-protection (i.e., “initiator anonymity” in [41] or “basic user anonymity” in [38]), which guarantees that the adversary could not determine the real identity of the user. Comparatively, a more admired property of user anonymity is user un-traceability (i.e., “initiator un-traceability” in [41] or “non-linkability” in [38]), which means that the adversary can neither discern who the user is nor tell apart whether two conversations are originated from the same (unknown) user. This stronger notion of user anonymity has been adopted in most two-factor authentication schemes that endeavor to preserve user privacy [36], [39], [49], [61], [98], [103]. Throughout this paper, unless otherwise specified, by “user anonymity” we will always mean “user un-traceability”.

In 2004, to provide user anonymity, Das et al. [22] proposed the first dynamic ID-based two-factor authentication scheme, in which the user’s real identity is concealed in session-variant pseudo-identities and also there is no other user-specific information leaked through the protocol transcripts. In this way, the user’s real identity is protected and an outsider cannot trace different sessions belonging to the same user. This scheme only involves lightweight one-way hash functions and thus is highly suitable for smart card environments.

Unfortunately, in 2009 Wang et al. [93] pointed out that Das et al.’s seminal scheme [22] is completely insecure for its independence of using passwords and fails to provide mutual authentication and user anonymity. Accordingly, they suggested an improved version, which was later found incapable of providing user anonymity and prone to impersonation attack by Yeh et al. [108] and Wen–Li [96], respectively. To the designers’ disappointment, both the enhancements of Yeh et al. and Wen–Li have been found vulnerable to the most damaging attack – offline dictionary attack [63]. In fact, attacks against most of previous protocols with only a heuristic analysis have been shown [63], [77], [87], [88], [99], suggesting the need for rigorous proofs of security in a formal, well-defined model.

In ICISC 2012, Kim–Kim [50] observed that previous dynamic ID-based schemes with each having its own merits and demerits, and developed a simple and elegant anonymous authentication scheme using smart cards. This protocol is efficient for resource-limited mobile devices (smart cards) in terms of computation, communication and storage overheads, and keeps the merits (e.g., user anonymity, sound repairability, half-forward secrecy and robust security) of the most known schemes [30], [61], [106], [108]. Hence, it exhibits great application potentiality. In order to preserve user anonymity, this protocol adopts a synchronization mechanism to maintain consistency of the one-time pseudonym identities between the user and the server. As we shall show later, it is just this synchronization mechanism that makes Kim–Kim’s scheme vulnerable to de-synchronization attack, in which an attacker can easily break the consistency of pseudonym identities shared between the victim user and the server, and thereafter the victim user will always fail to login unless she re-registers.

To the best of our knowledge, though de-synchronization attack can hardly be seen as a new kind of threat, and actually it has been intensively discussed in the cryptographic protocol community (e.g., RFID authentication protocols [86], [107] and multimedia watermarking schemes [71]), yet little attention has been paid to this damaging threat in the domain of two-factor authentication. Unsurprisingly, quite a number of newly proposed two-factor schemes [44], [45], [52], [55], [61], [92], [97], [110], which strive to achieve user anonymity by employing a similar strategy to that of Kim–Kim’s scheme [50], invariably suffer from this vulnerability. In these schemes, an attacker who merely modifies or blocks a single message flow (e.g., the second flow of [44], [52], [61], third flow of [55], fourth flow of [97]), can render the user unable to be authenticated by the server in any of her following protocol runs. This once again underlines the importance of being fully aware of potential threats when designing a complex protocol. What is more, though various countermeasures to the problem of de-synchronization have been suggested in other protocol domains (see, e.g. [13], [58], [71]), as we will show in Section 3.1, they cannot be readily applied to the domain of two-factor authentication, and thus how to remedy a two-factor scheme with the de-synchronization problem is left as a largely unexplored issue.

There have been a number of privacy-preserving two-factor schemes [15], [49], [52], [55], [61], [96], [100] proposed, nevertheless, most of them are either inefficient to be implemented on smart cards (e.g., the scheme in [100]), or insecure against some serious threats like offline dictionary attack (e.g., the schemes in [15], [49], [96]) and de-synchronization attack (e.g., the schemes in [52], [55], [61]). It still remains an open problem as to how to develop a privacy-preserving two-factor protocol that can guard against various known attacks while maintaining acceptable efficiency. Most concretely, the current crux lies in simultaneously preserving user privacy without de-synchronization problem, achieving truly two-factor security and maintaining high efficiency [94], [88], under the non-tamper resistance assumption of the smart cards.

In a nutshell, the contributions of this paper are threefold:

• We use Kim–Kim’s two-factor authentication scheme as a case study and demonstrate that quite a number of latest privacy-preserving two-factor schemes (e.g., [44], [52], [95], [97], [110]) are prone to de-synchronization attack. In other words, the user privacy of these schemes is preserved at the cost of significantly reduced usability, which indicates the infeasibility of their strategy for achieving user anonymity. Our results highlight the devastating threat of de-synchronization attack on two-factor schemes with user anonymity.

• As our main contribution, we put forward an improvement over Kim–Kim’s scheme. Our new scheme makes up the missing security provisions necessary for real-life application environments while keeping the desirable features of the original protocol. Interestingly, the performance evaluation demonstrates that it attains the property of user anonymity “for free”, i.e., without incurring additional cost (in terms of communication, computation and storage) as compared to related non-privacy-preserving schemes.

• We further prove the proposed scheme in the random oracle model and the ideal cipher model. Remarkably, for the first time the notion of user un-traceability is captured in a formal model for smart-card-based password authentication.

The rest of the paper is organized as follows: Section 2 briefly reviews Kim–Kim’s scheme. After that, we describe its security pitfalls in Section 3. Our improved scheme is presented in Section 4. Section 5 and Section 6 provide the security analysis and performance evaluation of the proposed scheme, respectively. Section 7 concludes with some directions for future research.