Mistyping in Password-Assisted Key Exchange

We study the problem of Key Exchange (KE), where authentication is in part based on human-supplied credentials, such as passwords and biometrics. In contrast with electronically stored credentials, such as secret keys, the former may be occasionally (in general, {em adversarily}) mistyped. Our main contribution is the first formal treatment of mistyping in this setting. Ensuring security in presence of mistyping is subtle. We demonstrate mistyping-related vulnerabilities of some of previous KE definitions and constructions (of Boyen et al. cite{BoyenDoKaOsSm05,BoyenDoKaOsSm05revi sed,DodisKaReSm06} and Kolesnikov and Rackoff cite{KolesnikovRa06}). We concentrate on the practical two-factor authenticated KE setting where {em servers} exchange keys with {em clients}, who use short passwords (memorized) and long cryptographic keys (stored on a card). Our work is thus a natural extension of Halevi-Krawczyk cite{HaleviKr99} and Kolesnikov-Rackoff cite{KolesnikovRa0 6}. We discuss the challenges that arise due to mistyping. We propose the first KE definitions in this setting, and formally discuss their guarantees. We present efficient KE protocols and prove their security.