«Abstract. We study the problem of Key Exchange (KE), where authen- tication is two-factor and based on both electronically stored long keys and ...»
Password Mistyping in
Two-Factor-Authenticated Key Exchange
Vladimir Kolesnikov1 and Charles Rackoﬀ2
Bell Labs, Murray Hill, NJ 07974,USA email@example.com
Dept. Computer Science, University of Toronto, Canada firstname.lastname@example.org
Abstract. We study the problem of Key Exchange (KE), where authen-
tication is two-factor and based on both electronically stored long keys
and human-supplied credentials (passwords or biometrics). The latter
credential has low entropy and may be adversarily mistyped. Our main contribution is the ﬁrst formal treatment of mistyping in this setting.
Ensuring security in presence of mistyping is subtle. We show mistyping- related limitations of previous KE deﬁnitions and constructions (of Boyen et al. [7, 6, 10] and Kolesnikov and Rackoﬀ ).
We concentrate on the practical two-factor authenticated KE setting where servers exchange keys with clients, who use short passwords (mem- orized) and long cryptographic keys (stored on a card). Our work is thus a natural generalization of Halevi-Krawczyk  and Kolesnikov-Rackoﬀ . We discuss the challenges that arise due to mistyping. We propose the ﬁrst KE deﬁnitions in this setting, and formally discuss their guar- antees. We present eﬃcient KE protocols and prove their security.
1 Introduction The problem of securing communication over an insecure network is generally solved using key exchange (KE). KE provides partners with matching randomly chosen keys, which are used for securing their conversation. Of course, no adver- sary Adv should be able to mismatch players. Therefore, players must possess secrets with which they can authenticate themselves. The kind of secrets that are available to players determines the setting of KE. In the simplest KE setting players have a long shared random string. KE is more complicated if parties establish key pairs with the public keys securely published. Using weak and/or fuzzy credentials, such as passwords or biometrics, further complicates the de- sign of KE. Finally, using a combination of credentials may make certain aspects of KE easier (such as incorporating password authentication), but increases the overall complexity of the solution, as discussed in .
Our setting. Two-factor authentication is critical and is used extensively in secure applications such as banking, VPN, etc. Stored long keys protect against online adversaries, but are vulnerable against theft. The extra layer of security is achieved with additional use of a theft-resistant credential, e.g. a short password or a biometric. Unfortunately, neither password nor biometric can be expected to be read reliably into the computer.
2 Vladimir Kolesnikov and Charles Rackoﬀ We give foundation to this setting by generalizing the work of Halevi-Krawczyk (HK)  and Kolesnikov-Rackoﬀ (KR) . Recall, they address the clientserver setting where both long key and a short password are used for KE. The servers are incorruptible, but client’s card or password can be compromised.
Motivated by real scenarios, we study the eﬀects of password mistyping. Mistyping need not be random, but may be skewed by the adversary, e.g. by technical means or social engineering manipulation. We thus consider security against adversaries who can arbitrarily aﬀect user’s mistyping. This consideration is especially relevant in case biometric credentials are used for authentication, since, due to technology limitations, biometric readings are expected to be misread.
Mistyping opens subtle vulnerabilities and raises complex deﬁnitional issues.
In the sequel, we use terms “password” and “mistype”, although our work applies to passwords, biometrics, and other short noisy credentials, as noted in Sect. 5.
1.1 Our contributions and outline of work Our main contribution is the ﬁrst formal treatment of mistyping of passwords in KE that uses a combination of credentials.
We discuss recent deﬁnitions that consider mistyping-related settings and issues – robust fuzzy extractors of [7, 6, 10]. We point out a limitation of the deﬁnitions of [7, 6, 10] with respect to robust handling of biometric misreading/mistyping and discuss possible remedies. We demonstrate and correct a vulnerability of the deﬁnition and protocol of , which can only be exploited when users mistype. These observations further emphasize the subtleties of mistyping and the need for its formal treatment and deeper understanding.
In Sect. 3, we introduce our setting and the framework of  which we build upon. Then, with simple protocols we illustrate mistyping-related issues, discuss natural deﬁnitional approaches to handling mistyping and their shortcomings.
Most of the mistyping-related subtleties we uncover arise due to the simultaneous use of both long keys and passwords. In Sect. 4, we formalize our discussion in a deﬁnition, and formally argue that it prevents attacks that exploit mistyping.
In Sect. 5 we discuss applications of our work in biometric authentication.
In Sect. 6 we give eﬃcient protocols; we prove their security in the full version.
1.2 Related work The problem of key exchange has deservedly received a vast amount of attention.
Password KE was ﬁrst considered by Bellovin and Merritt . Foundations – formal deﬁnitions and protocols – were laid in [3, 8, 13, 9], and other works.
The use of combined keys in authentication, where the client has a password and the public key of the server, was introduced by Gong et al.  and ﬁrst formalized by Halevi and Krawczyk . Kolesnikov and Rackoﬀ  extended this setting by allowing the client to also share a long key with the server, and gave ﬁrst deﬁnitions of KE in their (and thus in the Gong et al. and HK) setting.
Password mistyping in KE. Despite the large research eﬀort, the deﬁnitional issues of KE password mistyping are formally approached only in the Password Mistyping in Two-Factor-Authenticated Key Exchange 3 UC deﬁnition of Canetti et al. . In their password-only setting, mistyping is modelled by Environment Z providing players’ inputs. Additional use of long key makes our setting signiﬁcantly diﬀerent (and more subtle with respect to
mistyping) from that of . Mistyping was also considered in diﬀerent settings:
related-key attacks on blockciphers  and signing authority delegation .
Biometric authentication and fuzzy extractors. A growing body of work, e.g. [12, 5, 10, 11], addresses the use of biometrics in cryptography. Boyen et al. [7, 6, 10] consider its application to KE. They introduce the notion of robust fuzzy extractor (RFE), and give generic constructions of biometric-based KE from RFE. While their setting is similar to ours, the problems solved by [7, 6, 10] are diﬀerent. They give KE protocols that accept “close enough” secrets, thus enabling security and privacy of biometric authentication. They do not aim to give a formal KE deﬁnition that handles biometric/password misreading. Moreover, as shown in Sect. 2, their notion of RFE is insuﬃciently strong to guarantee security of their generic KE protocol in many practical settings.
(However, instantiating their KE protocol with their RFE construction is secure, since the latter satisﬁes stronger requirements than required by the deﬁnition.) 2 Mistyping-related limitations in previous work On robust fuzzy extractor (RFE) deﬁnition and KE protocol [7, 6, 10].
We ﬁrst clarify underlying biometric technology limitations and assumptions.
Biometrics are “fuzzy”, i.e. each scan is likely to be diﬀerent from, but “close” to the “true” scan. Error-correction  is then used to extract non-fuzzy keys usable in cryptography. However, error-correction cannot correct many misreading errors (up to 10%), since this would imply high false acceptance rate3. Thus misreading beyond error-correction ball occurs often, and must be considered.
We note a limitation of RFE deﬁnition [7, 6, 10], prohibiting its use with the generic KE construction (Sect. 3.3 of ) in many scenarios. Roughly, deﬁnition’s domains of correctness and security guarantees coincide. That is, extracted randomness is only guaranteed to be good if the scan is within the error-correction distance t from the original. There are no guarantees on the randomness if this condition does not hold. This is, perhaps, due to the papers’ implicit assumption that “natural” misreadings are almost always “close” and are corrected (i.e. FRR is negligible). However, as discussed above, this assumption often does not hold.
Strengthening the randomness guarantees of RFE would increase its usability.
More speciﬁcally, a RFE (Gen, Rep) may exhibit the following vulnerability.
Given the public helper string P, if the biometric w0 is misread in a special way w outside the error-correction ball, the extracted randomness Rep(w, P ) is predictable. Even more subtly, Rep(w, P ) and Rep(w0, P ) could be related, but unequal. Clearly, KE protocols, including one of Sect. 3.3 of [7, 6], constructed from such RFE would not be secure. One solution is to require, for w outside the 3 In balanced optimized real-life systems, which compare scans directly, False Reject Rate (FRR) is usually 1..10%. Notably, NIST reports FRR of ﬁngerprints 0.1..2%, iris 0.2..1% and face 10%. See  for comprehensive overview and references.
4 Vladimir Kolesnikov and Charles Rackoﬀ error-correction ball, that either Rep(w, P ) = ⊥ (property of RFE construction of [7, 6]) or that Rep(w, P ) is either equal to or independent from Rep(w0, P ).
Finally, although [7, 6, 10] consider adversarial substitution of P with P, they guarantee Rep(w, P ) = ⊥ only for w in the error-correction ball. This vulnerability also can be resolved by separating the error-correction and security domains. We defer detailed deﬁnition, analysis and constructions as future work.
On the deﬁnition and construction of . We present the following practical outside-of-the-model mistyping attack on the protocol (and thus also on the deﬁnition) of Kolesnikov and Rackoﬀ . Speciﬁcally, resistance to Denial of Access (DoA) attacks of the protocol of  is compromised if the honest client ever mistypes. Indeed, since their protocol is not challenge-response, client C’s message can be replayed. This is not a problem if C always types the correct password (session keys of C and server S will be independent). However, if the password was mistyped, both the original and replayed message will cause S to register password failure, violating the intent of the DoA resistance. We stress that the KR protocol is otherwise secure against mistyping (and we prove it in Sect. 6). Our deﬁnitions and protocols address and correct the above insecurity.
Above limitations show subtleties of mistyping and the need to address them.
3 Pre-deﬁnition discussion Our main contribution is a formal treatment of mistyping in the combined keys KE setting of Kolesnikov and Rackoﬀ . The KR setting is a generalization of the Halevi-Krawczyk setting , in which clients have a password and the public key of S. In KR setting, clients carry stealable cards capable of storing cryptographic keys – public key of S and long key shared by C and S. Addition of the cards allows better functionality and security than that of HK. KR deﬁnitions and protocol guarantee and achieve strong security when C’s card is secure, and weaker, password-grade, security, when the card is compromised.
We stress that the deﬁnition of KR does not handle mistyping. That is, it is possible to construct KR-secure protocols that “break” if the client ever mistypes his password. Sect. 3.3 of  provides an example and a short informal discussion on mistyping, and leaves the problem open. In Sect. 3.2, we expand this discussion, present more subtle mistyping threats, and discuss approaches to handling them. This leads to the presentation of our deﬁnitions in Sect. 4.
Notation. We concentrate on the two-factor authentication setting, where a client (denoted C) exchanges keys with a server (S). Both long and short keys are used for KE. Let P be a player. We denote by Pi the i-th instance of P.
We write PiQ to emphasize that Pi intends to do KE with (some instance of) player Q. Denote the adversary by Adv. Sometimes we distinguish the game and real-life adversary, and denote the latter AdvReal. Denote C’s password by pwd and long key by. S’s public/ private keys are pkS and skS. Password failure ⊥.
and the associated control symbol output by S is denoted by P On the Style of Deﬁnition. We chose the game (Bellare-Pointcheval-Rogaway ) style, since this allowed using the intuitive deﬁnition of KR (only existing two-factor-authentication KE deﬁnition). Extending KR allowed reduction of Password Mistyping in Two-Factor-Authenticated Key Exchange 5 security claims of our deﬁnition/setting to those of KR. Further, the stronger and arguably more intuitive UC model unfortunately is sometimes too strict, ruling out some eﬃcient protocols which appear to be good enough in practice.
Proposing a simulation-based (especially, UC) deﬁnition, and exploring the relationship between it and our deﬁnition would add conﬁdence in both our and the UC treatment of the problem. We thus leave as an important next step the design, detailed analysis and comparison of a corresponding UC deﬁnition. We expect that our discussions of ideas and obstacles would aid in this future work.
3.1 Review of the framework of 
Our deﬁnition is an extension of the KE deﬁnition of KR (Def. 2 of ).
Recall, KR (and thus our) deﬁnition follows the common game-based paradigm.
The real world and real adversary AdvReal are abstracted as a game, played by the game adversary Adv. Game includes clients and servers – Interactive Turing Machines (ITM) running the KE protocol Π, communicating via channels controlled by Adv. Game rules mimic reality, and are designed so that Adv’s wins correspond to real-life breaks. Π is deﬁned secure if no polytime Adv is able to win above certain “allowed” probability. Deﬁnition is thus reduced to the design of the game. KR break down the real world into ﬁve intuitive games (KE1, KE2, KE3, DOA and SID), which mimic possible real-life attack scenarios.