Paper 2006/057

Key Exchange Using Passwords and Long Keys

Vladimir Kolesnikov and Charles Rackoff


We propose a new model for key exchange (KE) based on a combination of different types of keys. In our setting, servers exchange keys with clients, who memorize short passwords and carry (stealable) storage cards containing long (cryptographic) keys. Our setting is a generalization of that of Halevi and Krawczyk \cite{HaleviKr99} (HK), where clients have a password and the public key of the server. We point out a subtle flaw in the protocols of HK and demonstrate a practical attack on them, resulting in a full password compromise. We give a definition of security of KE in our (and thus also in the HK) setting and discuss many related subtleties. We define and discuss protection against denial of access (DoA) attacks, which is not possible in any of the previous KE models that use passwords. Finally, we give a very simple and efficient protocol satisfying all our requirements.

Note: This is an extended version of the TCC 2006 publication with the same title. This version adds proofs of security and discussions on password updates and storing passords on the server.

Available format(s)
Publication info
Published elsewhere. Theory of Cryptography Conference 2006
password-based key exchangehybrid modellong key
Contact author(s)
vlad @ cs utoronto ca
2006-02-23: revised
2006-02-15: received
See all versions
Short URL
Creative Commons Attribution


      author = {Vladimir Kolesnikov and Charles Rackoff},
      title = {Key Exchange Using Passwords and Long Keys},
      howpublished = {Cryptology ePrint Archive, Paper 2006/057},
      year = {2006},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.