Network Working Group                                         Pars Mutaf
Internet-Draft                                     Institut National des
Expires: June 21, 2008                                Telecommunications
                                                       December 19, 2007


                          Verbal Key Exchange
                         draft-mutaf-dke-02.txt

Status of this Memo

   By submitting this Internet-Draft, each author represents that any
   applicable patent or other IPR claims of which he or she is aware
   have been or will be disclosed, and any of which he or she becomes
   aware will be disclosed, in accordance with Section 6 of BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF), its areas, and its working groups.  Note that
   other groups may also distribute working documents as Internet-
   Drafts.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   The list of current Internet-Drafts can be accessed at
   http://www.ietf.org/ietf/1id-abstracts.txt.

   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html.

   This Internet-Draft will expire on June 21, 2008.

Copyright Notice

   Copyright (C) The IETF Trust (2007).

Abstract

   This document describes a verbal key exchange protocol in which a
   short fingerprint is used to represent a "one-time" public key
   fingerprint.  The one-time public key is immediately used for key
   exchange, before an attacker has time to find a public/private key
   pair that gives the same fingerprint and mount a Man-in-the-Middle
   attack.  The protocol, however, requires that both users be present
   for fingerprint verification, making it suitable for mobile users
   only.



Mutaf                     Expires June 21, 2008                 [Page 1]


Internet-Draft             Verbal Key Exchange             December 2007


Table of Contents

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . . . 3
   2.  Protocol description  . . . . . . . . . . . . . . . . . . . . . 3
   3.  Security considerations . . . . . . . . . . . . . . . . . . . . 4
   4.  Related work  . . . . . . . . . . . . . . . . . . . . . . . . . 5
   5.  IANA considerations . . . . . . . . . . . . . . . . . . . . . . 6
   6.  Acknowledgements  . . . . . . . . . . . . . . . . . . . . . . . 6
   7.  Conclusion  . . . . . . . . . . . . . . . . . . . . . . . . . . 6
   8.  Informative References  . . . . . . . . . . . . . . . . . . . . 6
   Author's Address  . . . . . . . . . . . . . . . . . . . . . . . . . 7
   Intellectual Property and Copyright Statements  . . . . . . . . . . 8







































Mutaf                     Expires June 21, 2008                 [Page 2]


Internet-Draft             Verbal Key Exchange             December 2007


1.  Introduction

   Public key authentication is a difficult problem since a Public Key
   Infrastructure (PKI) is generally required.  The problem is less
   challenging when two mobile users wishing to establish a security
   association are both present, i.e. when they meet each other.  The
   users can verify a shared public key by comparing its "fingerprint".
   However, up to 160 bits long fingerprints are generally recommended
   today.  Such a fingerprint looks like "E582 94F2 E9A2 2748 6E8B 061B
   31CC 528F D7FA 8919" which is difficult to read and type by users.
   Simply displaying the fingerprint and assuming that the user will
   check it visually is not acceptable.  The users must be forced to
   really check the fingerprint, and therefore the operation must be
   user-friendly.

   This document describes how an easy to exchange small fingerprint can
   be used to authenticate a "one-time" public key.  The one-time public
   key is immediately used for key exchange, before an attacker has time
   to find a public/private key pair that gives the same fingerprint and
   mount a Man-in-the-Middle attack.


2.  Protocol description

   The proposed protocol is briefly described below:


          Initiator              MitM                 Responder

                                salt Z
         ^ ----------------------------------------------->
       T |              one-time public key PK
         v <----------------------------------------------

           <============ Fingerprint words
   human verification      representing PK
   of words                 salted with Z ================

           -----------------{secret key}PK---------------->

   where
            PK: A one-time RSA public key
            ==: The responder user tells the words representing
                the fingerprint to the initiator user through
                oral communication.
           MitM: Man in the Middle

                                 Figure 1



Mutaf                     Expires June 21, 2008                 [Page 3]


Internet-Draft             Verbal Key Exchange             December 2007


   The fingerprint is represented using words from a dictionary.  It is
   assumed that both hosts have the same dictionary containing N words.
   Or, the responder may return a dictionary to the initiator (TBD).
   Using a dictionary has two benefits.  First, well-known words from a
   dictionary are easier to spell and understand than a 40-bit
   hexadecimal sequence like "E58294F2E9".  Secondly, using a large
   dictionary containing N words, one can represent a larger number of
   bits per word.  Each word in the dictionary will contribute log2(N)
   bits of entropy.  If the dictionary contains N=1024 words, 4 words
   such as
                               tokyo
                               pizza
                               madonna
                               mercedes

   can represent a 4*10=40 bits long fingerprint.  The initiator user
   should be asked to type the same words to ensure that the
   verification takes place.  The initiator, having the same dictionary,
   can reduce the verification effort using automated word completion.



3.  Security considerations

   The fingerprint is used to authenticate a "one-time" public key.
   MitM has to find a PK' giving the same fingerprint as PK, and return
   it to the initiator before the legitimate PK. 2^40, for example, is
   large enough to assume that the attacker cannot reasonably succeed.
   Since RSA key generation is a slow operation, an attacker may
   anticipate by generating and storing 2^40 public keys for all
   possible fingerprints.  In this case, the random salt Z will force
   the attacker to do 2^40 fingerprint computations from the salt and
   the pre-computed RSA public keys.  To defeat a powerful attacker
   having 2^40 pre-computed public keys, the fingerprint computation
   should preferably be a difficult task.

   The fingerprint size can be increased either by increasing the number
   of words in the dictionary (N), or the number of read/typed words (S)
   by the users.  The entropy per word increases logarithmically with N.
   Doubling the dictionary size will add only 1 bit of entropy per word.
   The fingerprint size increases linearly with S at the cost of
   reading/typing more words and hence increasing the key exchange time.
   Since most of the human effort will be made by the verifier typing
   the words read by the responder, an implementation should consider
   user friendly techniques e.g. word completion.  Using GUI word
   completion making use of a keyboard and pointer, words can be entered
   very easily in a way that is probably acceptable to the user.




Mutaf                     Expires June 21, 2008                 [Page 4]


Internet-Draft             Verbal Key Exchange             December 2007


   A too large dictionary will increase the word completion complexity.
   The initiator user will either need to type more letters to reduce
   the size of a list of words, or scroll over a large list for
   searching a word in a list.  This will increase the key agreement
   time perceived by the responder user and the effort made by the
   initiator user.  On the other hand, a very small dictionary will
   increase the number of words needed to represent a fingerprint, hence
   also increase the user effort.


4.  Related work

   In [SAS], Serge Vaudenay brings an alternative solution in which a
   15-bit authentication string e.g. a 5-digit PIN code or a short
   hexadecimal sequence of 4 characters from {0123456789abcdef} is
   enough for authentication.  The SAS scheme does not require public
   key operations for authentication and its security is orthogonal to
   the computational power of the man-in-the-middle.  It also allows for
   mutual authentication and does not require a dictionary.  In [MAS],
   the number of moves for this solution is reduced to three.  [SEEING2]
   gives a brief description of the protocol.

   Other solutions have been proposed in the literature, exploiting the
   presence of both users (i.e. user contact) for authentication.  For
   example, in "Seeing is Believing", cell phones equipped with a
   camera, authenticate each other using a two-dimensional barcode
   representation of a public key.  The public key is verified by taking
   its photo displayed on the peer device's screen [SEEING] [SEEING2].

   "Loud & Clear" is another solution based on a text-to-speech engine
   to read an auditorially-robust, grammatically-correct sentence
   derived from the fingerprint of a device's public key.  The text
   representing the fingerprint is heard from both devices equipped with
   speakers, and compared by the user(s).  Or, alternatively, the
   fingerprint is heard from one device, displayed by the second device,
   and compared [LOUD].

   "Pretty Good Privacy" uses a dictionary of words for reliable public
   key fingerprint transmission over a potentially noisy voice channel,
   in a clear unambiguous way.  This is apparently inspired from the
   NATO phonetic alphabet used by pilots [PGPWORDLIST].  "Diceware" also
   uses a dictionary of 6^5=7,776 unique words that are easy to spell
   and remember for creating passphrases, passwords, and other
   cryptographic variables.  Each word adds log2(7,776)=12.9 bits of
   entropy to the passphrase [DICEWARE].






Mutaf                     Expires June 21, 2008                 [Page 5]


Internet-Draft             Verbal Key Exchange             December 2007


5.  IANA considerations

   TBD.


6.  Acknowledgements

   Erik Rescorla suggested using a salt and made me aware of attacks
   using pre-computed RSA keys.

   Michael Richardson and Nicolas Williams suggested a name like Verbal
   Key Exchange.  Michael Richardson suggested that in IKEv2 one can
   authenticate the Diffie-Hellman exponent directly.


7.  Conclusion

   This document described a verbal key exchange protocol.


8.  Informative References

   [DICEWARE]
              The Diceware Passphrase Home Page,
              "http://world.std.com/~reinhold/diceware.html/".

   [LOUD]     Goodrich, M., Sirivianos, M., Solis, J., Tsudik, G., and
              E. Uzun, "Loud And Clear: Human Verifiable Authentication
              Based on Audio", IEEE ICDCS 2006.

   [MAS]      Laur, S., Asokan, N., and K. Nyberg, "Efficient mutual
              data authentication using manually  authenticated
              strings", Cryptology ePrint Archive, Report 2005/424,
              2006.

   [PGPWORDLIST]
              PGP word list,
              "http://en.wikipedia.org/wiki/PGP_word_list".

   [SAS]      Vaudenay, S., "Secure Communications over Insecure
              Channels Based on Short Authenticated Strings", Advances
              in Cryptology, CRYPTO 2005.

   [SEEING]   McCune, J., Perrig, A., and M. Reiter, "Seeing is
              Believing", Proceedings of the IEEE Symposium on Security
              and Privacy, Oakland, CA. May 2005.

   [SEEING2]  Saxena, N., Ekberg, J., Kostiainen, K., and N. Asokan,



Mutaf                     Expires June 21, 2008                 [Page 6]


Internet-Draft             Verbal Key Exchange             December 2007


              "Secure Device Pairing based on a Visual Channel",
              Proceedings of the IEEE Symposium on Security and Privacy,
              Oakland, CA. May 2006.


Author's Address

   Pars Mutaf
   Institut National des Telecommunications

   Email: pars.mutaf@gmail.com








































Mutaf                     Expires June 21, 2008                 [Page 7]


Internet-Draft             Verbal Key Exchange             December 2007


Full Copyright Statement

   Copyright (C) The IETF Trust (2007).

   This document is subject to the rights, licenses and restrictions
   contained in BCP 78, and except as set forth therein, the authors
   retain all their rights.

   This document and the information contained herein are provided on an
   "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
   OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND
   THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS
   OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF
   THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
   WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.


Intellectual Property

   The IETF takes no position regarding the validity or scope of any
   Intellectual Property Rights or other rights that might be claimed to
   pertain to the implementation or use of the technology described in
   this document or the extent to which any license under such rights
   might or might not be available; nor does it represent that it has
   made any independent effort to identify any such rights.  Information
   on the procedures with respect to rights in RFC documents can be
   found in BCP 78 and BCP 79.

   Copies of IPR disclosures made to the IETF Secretariat and any
   assurances of licenses to be made available, or the result of an
   attempt made to obtain a general license or permission for the use of
   such proprietary rights by implementers or users of this
   specification can be obtained from the IETF on-line IPR repository at
   http://www.ietf.org/ipr.

   The IETF invites any interested party to bring to its attention any
   copyrights, patents or patent applications, or other proprietary
   rights that may cover technology that may be required to implement
   this standard.  Please address the information to the IETF at
   ietf-ipr@ietf.org.


Acknowledgment

   Funding for the RFC Editor function is provided by the IETF
   Administrative Support Activity (IASA).





Mutaf                     Expires June 21, 2008                 [Page 8]