Cryptographic Systems: User Authentication and Authenticated Key-exchange

Jonathan Katz, Columbia University

When designing a cryptographic system, failure to take into account the behavior of the system’s users can have severe consequences. Nowhere is this more evident than in the design of protocols for user authentication and authenticated key-exchange. The standard protocols for these tasks are secure when parties use long, hard-to-guess secrets; however, these same protocols can be completely broken by an off-line dictionary attack when users choose weak passwords which are easy for an attacker to guess.

A long-standing goal of computer security has been to design password-only authentication and key-exchange protocols which are resistant to such attacks even when users choose poor passwords (as is typically the case). Many previously-proposed solutions offer “heuristic” security guarantees without a proof of security in the standard cryptographic model.

We propose the first efficient protocols for password-only authentication and key-exchange which are provably secure against off-line dictionary attacks. Proofs of security are in the standard cryptographic model using a well-known cryptographic assumption, and the protocols require only slightly more computation than the original key-exchange protocol of Diffie and Hellman (which provides no authentication at all).

We will also discuss more recent work focusing on password-based authentication and key-exchange in the public-key model.