Internet DRAFT - draft-wan-hokey-eccho


Network Working Group                                             C. Wan
Internet-Draft                                                     A. Hu
Expires: June 20, 2008                              Southeast University
                                                       December 18, 2007

    An elliptic curve based authenticated key agreement protocol for
                   managing wiress handover security

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-

   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

   The list of Internet-Draft Shadow Directories can be accessed at

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

Copyright Notice

   Copyright (C) The IETF Trust (2007).

Wan & Hu                  Expires June 20, 2008                 [Page 1]
Internet-Draft                    ECCHO                    December 2007


   The roaming of a lot of mobile nodes from one authenticator to
   another may put a heavy burden on the authentication server.  This
   paper proposes an elliptic curve based key agreement protocol with
   authentication property to address this problem.

Table of Contents

   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  3
   2.  UNDERLYING MODEL . . . . . . . . . . . . . . . . . . . . . . .  4
   5.  security considerations  . . . . . . . . . . . . . . . . . . .  8
   6.  IANA considerations  . . . . . . . . . . . . . . . . . . . . .  9
   7.  References . . . . . . . . . . . . . . . . . . . . . . . . . . 10
   Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 11
   Intellectual Property and Copyright Statements . . . . . . . . . . 12

Wan & Hu                  Expires June 20, 2008                 [Page 2]
Internet-Draft                    ECCHO                    December 2007

1.  Introduction

   The problem of wireless access authentication is usually concerned
   with mobility management.  When the mobile node(MN) roams into a
   foreign domain, the foreign network access server (NAS) will act as a
   pass through authenticator(AU), and consults the authentication
   server in the MN's home domain (AAAH) for authentication through the
   foreign domain authentication server (AAAF).  Currently the EAP
   protocol [1] is used for this sort of third-party authentication.
   However, according to [2], the simplest EAP method EAP-MD5 needs more
   than 70 ms time.  This is too time consuming for latency sensitive
   services such as VOIP when the MN moves frequently from one AU to

   To optimize the EAP protocol, several protocols are designed by the
   IEEE and IETF standards organizations.  They are called fast re-
   authentication protocol [4], pre-authentication protocol [6] [5], and
   context transfer authentication protocol [7].  However, if there are
   a lot of MNs roaming from one AU to another, current protocols will
   put a heavy burden on the AAAF for they need to consult AAAF during
   handover authentication.  Assuming an AAAF manages 100 AUs, and every
   AU needs to authenticate 100 MNs at the same time, then the AAAF
   needs to generate 100*100=10,000 MSKs in a short period of time.
   According to [3], the total key generating latency is
   10ms*10,000=100s.  This means an average of several-minute latency on
   the AAAF.  According to [8], the context transfer authentication
   protocol will lead to the domino effect issue, in which a compromise
   of an AU will lead to a compromise of another AU.

   The two key issues remaining to be solved are the heavy burden of
   AAAF and the domino effect.  This paper proposes an elliptic curve
   [9] based key agreement protocol with authentication property for
   solving these two issues.  The novelty of this paper compared with
   [4] [5] [6] [9][10] lies in a different and efficient authenticated
   key agreement technique.

Wan & Hu                  Expires June 20, 2008                 [Page 3]
Internet-Draft                    ECCHO                    December 2007


   Our scheme aims to reduce the burden of the AAAF when there are a lot
   of MNs roaming from one AU to another within the same AAAF domain.
   The AAAF domain is defined by definition 1: Definition 1: We assume
   that the AAAF manages n AUs, and it has the capacity of managing m
   MNs.  The AAAF, the n AUs and the m MNs form an AAAF domain.

   he AAAF periodically creates an elliptic curve named Ep(a ,b ) for
   managing the AUs and the MNs.  Along with the elliptic curve, the
   AAAF creates four sets of prime numbers with different elements:
   MNPRIVATE={mn1, mn2,mnm} , AUPRIVATE={au1,au2,...,aun},
   MNPUBLIC={kmn11,kmn2,...,kmnn} and AUPUBLIC={kau1,kau2,...,kaun}.
   Also the AAAF calculates the lease common multiple M of MNPRIVATE ,
   and the lease common multiple N of AUPRIVATE .

   After creating the data structures above, the AAAF does the following
   steps for managing the AUs:

   Step 1) Randomly pick a base point G0 from Ep(a ,b ), and computes
   GiM = iMG0 , where i is an element of MNPUBLIC .

   Step 2) Computes Gj= jG0 , where j is an element of AUPRIVATE .

   Step 3) AUTHl= {iM,GiM,j,Gj,p,a,g,p} is the keying material
   distributed from the AAAF to the AU l .  Every AU should have a
   different i and j .  Then the AU randomly determines its Diffie-
   Hellman key pair <x2 ,y2>, where y2 =g^x2modp.

   When the MN enters the AAAF domain for the first time, the full EAP
   procedure is established.  And then the AAAF does the following steps
   for managing the MNs:

   Step 1) The AAAF computes Gr= rG0 where r is an element of MNPRIVATE

   Step 2) The AAAF computes GsN = sNG0 where s is an element of

   Step 3) MNt={r,Gr,sN,GsN,p,a,g,p} is the keying material distributed
   from the AAAF to the MN t .  Every MN should have a different r and s
   .  Then the MN randomly determines its Diffie-Hellman key pair
   <x1,y1>, where y1 =g^x1modp.

Wan & Hu                  Expires June 20, 2008                 [Page 4]
Internet-Draft                    ECCHO                    December 2007


   In this subsection, let's focus on the handover scenario.  We will
   present a key agreement and authentication mechanism without the
   participation of the AAAF.  Our scheme is based on the following
   elliptic curve assumption:

   Assumption 1: Giving a base point G on Ep(a,b), we can easily compute
   its rank k point K :K= kG ; on the other hand, giving K and G , one
   can not compute k .  Thus k can be used as private key, and K can be
   used as public key.

   Our scheme uses the following lemma:

   Lemma 1: if public-private key pairs <k1,K1> and <k2,K2> are on the
   same elliptic curve, they have the same base point G , and k1 is a
   divisor of k2 , then <k2/k1,K2> forms a new public-private key pair
   and the base point for <k2/k1,K2> is K1 .

   Proof of Lemma 1: K2=k2G=k2 /k1*(k2G)=k2/k1 K1

   To protect the key agreement procedure, we use the following
   encryption/decryption algorithm: Algorithm 1: <k,K> is the key pair
   of user A with a base point G on Ep(a b), A keeps k , and sends K ,G
   , Ep(a,b) to user B. If B wants to send message to A, then it can
   code the message to a point M on Ep(a,b), B randomly generates an
   integer r , computes C1=M+rK,C2=rG , and sends C1,C2 to A. when
   receiving C1,C2, A can get the message as follows: M=C1-kC2=M+rK-

   When t roams to l , l holds AUTHl and t holds MNt . l and t can
   authenticate each other and establish their shared key using AUTHl
   and MNt .  The key agreement and authentication procedure in the
   handover scenario includes three message exchanges.  They are
   described below:

   Message 1) l sends message Q1 to t , which is defined as follows: Q1=
   {iM,Gj} .

   Message 2) After receiving Q1 , the MN can compute its private iM/r
   with the base point Gr .  Also the MN uses GsN as the public key of
   AU with the base point Gj .Then the MN can send Q2 to the AU.  We use
   the Diffie-Hellman protocol to negotiate a shared key.  So Q2 is
   defined as follows: Q2={sN, Gr,(y1)GsN}, where y1 is protected by
   algorithm 1 and AU's public key GsN .

   Message 3) After getting the Q2 message, AU can compute its private
   key sN/j with a base point Gj .  Then it can extract y1 using

Wan & Hu                  Expires June 20, 2008                 [Page 5]
Internet-Draft                    ECCHO                    December 2007

   algorithm 1.  Then the AU can send Q3 to the MN to negotiate a shared
   key.  Q3 is defined as follows: Q3={ Gj (y2)GiM} where y2 is
   protected using algorithm 1 and MN's public key GiM .

   After the 3-pass message exchanges, the AU and the MN can generate
   the shared key respectively.  For the AU, it generates the shared key
   as follows: SS=y1 ^x2modp=g^(x1*x2)modp.  For the MN, it generates
   the shared key as follows: SS=y1 ^x1modp=g^(x1*x2)modp.

Wan & Hu                  Expires June 20, 2008                 [Page 6]
Internet-Draft                    ECCHO                    December 2007


   Our efficiency goals include reducing the burden of the AAAF and the
   total security costs.

   In our scheme, the AAAF is not involved in the handover
   authentication procedure, thus the burden of the AAAF is reduced.
   The security cost of our scheme can be analyzed from the following
   three factors: time of key generating using one way hash algorithm(Cg
   ), encryption or signature time ( Ce ), decryption or verification
   time( Cd ).  Since the private key generating in our scheme is a
   simple process of division, the comparison ignores its cost.  Table 1
   compares the security cost between the proposed scheme and previous
   methods.  According to section 7.13 in [1], the comparison assumes
   that the conversation between the AU and the AAAF, the conversation
   between AAAF and AAAH are protected by their pre-established trust
   relationship.  Table 1 security cost comparison between our scheme
   and previous schemes.
              MN            AU        AAAF       AAAH
   EAPMD5     ce            ce+cd     2ce+2cd    ce+2cd
   [4]        cg+ce+cd      ce+cd     cg+2ce+2cd 0
   [10]       cg+ce+2cd     cg+ce+2ce 0          0
   Our scheme cg+ce+cd      cg+ce+cd  0          0

Wan & Hu                  Expires June 20, 2008                 [Page 7]
Internet-Draft                    ECCHO                    December 2007

5.  security considerations

   Our security goals are analyzed as follows:

   (1) Authentication property: Only the authenticated MN and the legal
   AU can hold a unique t MN and AUTHl .  The attacker with a fake MNt
   or AUTHl will not be able to calculate their public-private key pair,
   thus it can not join the key agreement session.  Compared with [10],
   our scheme needs not verify the certificates for authentication.

   (2) Man-in-the-middle attack: Man-in-the-middle attack is the main
   vulnerability of Diffie-Hellman protocol.  We use Gj and Gr for
   identifying AU and MN, and the key agreement is protected by the
   public-private key pairs of the AU and the MN, so the manin- the-
   middle attack does not work here.

   (3) Domino effect analysis: There is no context transfer among AUs,
   so the domino effect is avoided.

Wan & Hu                  Expires June 20, 2008                 [Page 8]
Internet-Draft                    ECCHO                    December 2007

6.  IANA considerations

   To be completed.

Wan & Hu                  Expires June 20, 2008                 [Page 9]
Internet-Draft                    ECCHO                    December 2007

7.  References

   [1]   Aboba, B. and Et. Al, "Extensible Authentication
         Protocol(EAP)", June 2004.

   [2]   Sethom, K. and H. Afifi, "Requirements and Adaptation Solutions
         for Transparent Handover", 2004.

   [3]   Sethom, K. and Et. Al, "A Distributed and Secured Architecture
         to Enhance Smooth Handoffs in Wide Area Wireless IP
         Infrastructures", July 2006.

   [4]   Narayanan, V., "EAP Extensions for EAP Reauthentication
         Protocol (ERP)", Novermber 2007.

   [5]   IEEE, Institute of Electrical and Electronics Engineers.,
         "Supplement to Standard for Telecommunications and Information
         Exchange Between Systems - LAN/MAN Specific Requirements - Part
         11: Wireless LAN Medium Access Control (MAC) and Physical Layer
         (PHY) Specifications: Specification for Enhanced Security",

   [6]   Ohba, Y., "EAP Pre-authentication Problem Statement",
         September 2007.

   [7]   IEEE, Institute of Electrical and Electronics Engineers.,
         "Recommended Practice for Multi-Vendor Access Point
         Interoperability via an Inter-Access Point Protocol Across
         Distribution Systems Supporting IEEE 802.11 Operation",
         July 2003.

   [8]   Housley, R., "Guidance for Authentication, Authorization, and
         Accounting (AAA) Key Management", July 2007.

   [9]   , SECG., "Elliptic Curve Cryptography", 2000.

   [10]  Harn, L., "Authenticated Diffie-Hellman key agreement protocol
         using a single cryptographic assumption", August 2005.

Wan & Hu                  Expires June 20, 2008                [Page 10]
Internet-Draft                    ECCHO                    December 2007

Authors' Addresses

   Changsheng Wan
   Southeast University
   Sipailou 2,Nanjing,Jiangsu ,210096

   Phone: 86-25-83795112-802

   Aiqun Hu
   Southeast University
   Sipailou 2,Nanjing,Jiangsu ,210096

   Phone: 86-25-83795112-808

Wan & Hu                  Expires June 20, 2008                [Page 11]
Internet-Draft                    ECCHO                    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

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

   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


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

Wan & Hu                  Expires June 20, 2008                [Page 12]