Network Working Group                                            A. Kato
Internet-Draft                                  NTT Software Corporation
Intended status: Informational                               T. Hardjono
Expires: September 19, 2016                                          MIT
                                                            T. Kobayashi
                                                                T. Saito
                                                               K. Suzuki
                                                                     NTT
                                                          March 18, 2016


                            FSU Key Exchange
                     draft-kato-fsu-key-exchange-01

Abstract

   This draft proposes an identity-based authenticated key exchange
   protocol following the extended Canetti-Krawczyk (id-eCK) model.  The
   protocol is currently the most efficient among the id-eCK protocols.

Status of This Memo

   This Internet-Draft is submitted in full conformance with the
   provisions of BCP 78 and BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF).  Note that other groups may also distribute
   working documents as Internet-Drafts.  The list of current Internet-
   Drafts is at http://datatracker.ietf.org/drafts/current/.

   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."

   This Internet-Draft will expire on September 19, 2016.

Copyright Notice

   Copyright (c) 2016 IETF Trust and the persons identified as the
   document authors.  All rights reserved.

   This document is subject to BCP 78 and the IETF Trust's Legal
   Provisions Relating to IETF Documents
   (http://trustee.ietf.org/license-info) in effect on the date of
   publication of this document.  Please review these documents
   carefully, as they describe your rights and restrictions with respect
   to this document.  Code Components extracted from this document must



Kato, et al.           Expires September 19, 2016               [Page 1]


Internet-Draft              FSU Key Exchange                  March 2016


   include Simplified BSD License text as described in Section 4.e of
   the Trust Legal Provisions and are provided without warranty as
   described in the Simplified BSD License.

Table of Contents

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   3
     1.1.  Our Motivation  . . . . . . . . . . . . . . . . . . . . .   3
   2.  Requirements Terminology  . . . . . . . . . . . . . . . . . .   4
   3.  Notation  . . . . . . . . . . . . . . . . . . . . . . . . . .   4
   4.  Data Type and Its Conversions . . . . . . . . . . . . . . . .   6
     4.1.  BitString-to-OctetString Conversion (BS2OSP)  . . . . . .   7
     4.2.  OctetString-to-BitString Conversion (OS2BSP)  . . . . . .   7
     4.3.  FieldElement-to-Integer Conversion (FE2IP)  . . . . . . .   7
     4.4.  Integer-to-FieldElement Conversion (I2FEP)  . . . . . . .   7
     4.5.  FieldElement-to-OctetString Conversion (FE2OSP) . . . . .   7
     4.6.  OctetString-to-FieldElement Conversion (OS2FEP) . . . . .   8
     4.7.  EllipticCurvePoint-to-OctetString Conversion (ECP2OSP)  .   8
     4.8.  OctetString-to-EllipticCurvePoint Conversion (OS2ECPP)  .   8
   5.  Building Block of FSU Key Exchange  . . . . . . . . . . . . .   8
     5.1.  Key Derivation Function . . . . . . . . . . . . . . . . .   8
     5.2.  Hashing to Point  . . . . . . . . . . . . . . . . . . . .   9
       5.2.1.  IHF1  . . . . . . . . . . . . . . . . . . . . . . . .  10
       5.2.2.  OS2FQE  . . . . . . . . . . . . . . . . . . . . . . .  11
     5.3.  Group Membership Test Function  . . . . . . . . . . . . .  12
   6.  FSU Key Exchange  . . . . . . . . . . . . . . . . . . . . . .  13
     6.1.  System Parameter Setup  . . . . . . . . . . . . . . . . .  13
     6.2.  Key Distribution by KGC . . . . . . . . . . . . . . . . .  14
     6.3.  FSU Key Exchange Protocol . . . . . . . . . . . . . . . .  14
   7.  Security Considerations . . . . . . . . . . . . . . . . . . .  16
   8.  Acknowledgements  . . . . . . . . . . . . . . . . . . . . . .  16
   9.  Algorithm Identifiers . . . . . . . . . . . . . . . . . . . .  16
   10. Change log  . . . . . . . . . . . . . . . . . . . . . . . . .  17
   11. Test Vectors  . . . . . . . . . . . . . . . . . . . . . . . .  17
   12. References  . . . . . . . . . . . . . . . . . . . . . . . . .  17
     12.1.  Normative References . . . . . . . . . . . . . . . . . .  17
     12.2.  Informative References . . . . . . . . . . . . . . . . .  17
   Appendix A.  Construction of Data Conversion  . . . . . . . . . .  19
     A.1.  Construction of BS2OSP  . . . . . . . . . . . . . . . . .  19
     A.2.  Construction of OS2BSP  . . . . . . . . . . . . . . . . .  19
     A.3.  Construction of FE2IP . . . . . . . . . . . . . . . . . .  20
     A.4.  Construction of I2FEP . . . . . . . . . . . . . . . . . .  20
     A.5.  Construction of FE2OSP  . . . . . . . . . . . . . . . . .  21
     A.6.  Construction of OS2FEP  . . . . . . . . . . . . . . . . .  22
     A.7.  Construction of ECP2OSP . . . . . . . . . . . . . . . . .  22
     A.8.  Construction of OS2ECPP . . . . . . . . . . . . . . . . .  24
   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .  25




Kato, et al.           Expires September 19, 2016               [Page 2]


Internet-Draft              FSU Key Exchange                  March 2016


1.  Introduction

   Authenticated key exchange (AKE) is a core security function within
   many deployed systems today.  It is a foundational function that
   allows end-users and systems alike to be authenticated prior to
   access to resource and services.  Over the past two decades key
   exchange schemes have been proposed, based on symmetric and
   asymmetric key cryptography.

   A more recent approach to AKE protocol has been the introduction of
   identity binding to the exchange [7] [8], obviating the need to rely
   on a public key infrastructure in which digital certificates need to
   be exchanged by users or end-points that wish to communicate signed
   and/or encrypted messages.

   Identity-based AKE (ID-AKE) schemes rely on the use of the trusted
   intermediary referred to as the Key Generation Center (KGC).  The
   role of the KGC, among others, is to generate a pair of master public
   and secret keys based on the user's identity and to extract a user's
   secret key corresponding to his or her identity.

   In a 2-pass ID-AKE scheme, an "initiator" entity wishing to share a
   key with a second entity (referred to as the "responder") sends
   ephemeral public information to the responder.  In its turn, the
   responder sends another ephemeral public information to the initiator
   entity.  Following this, each entity would then generate a session
   from a number of parameters, notably their respective secret keys
   (given by the KGC), their own secret values of the ephemeral
   information, the identity of the peer they're communicating with, and
   the ephemeral information they received from that peer.

   We propose a provably secure ID-AKE scheme called "FSU" [4] [5] [6]
   based on the previous model of [9]  and which builds on the previous
   efforts in [10] [11] .  The model underlying the FSU was chosen due
   to the merit of provable security based on an adversarial model in
   which the adversary has the freedom to choose keys reveal.

1.1.  Our Motivation

   In order to establish secure communications, the encryption is used,
   and a key exchange protocol is necessary to use the encryption.  If
   the key exchange protocol has vulnerability, an attacker can
   intercept all messages, so encrypted session becomes meaningless.  In
   practice, man in the middle attack and a forward security of key
   exchange protocol are serious issues.

   In recent years, IoT technology gathers many attentions.  It is
   expected that 26-30 billion devices will be wirelessly connected by



Kato, et al.           Expires September 19, 2016               [Page 3]


Internet-Draft              FSU Key Exchange                  March 2016


   2020.  And to set up a huge number of devices with certificates or
   passwords for key exchange and to maintain the certificates or
   passwords require many costs.  Furthermore, the leakage of a secret
   key for key exchange and a session key for encryption likely to occur
   because of resource restriction of device and installation
   environment of device.

   To resolve above problems, we propose an ID-based authenticated key
   exchange protocol FSU.  In usual PKI based cryptography, a device
   must set up password or generate own secret key.  On the other hand,
   in the FSU protocol the trusted third party generate the secret key
   for a huge number of IoT devices, so the manufacture and users of the
   devices can maintain secret key for the devices unitarily.  The FSU
   Protocol use existing ID, which can be any string, e.g., e-mail
   address and serial number, as public key instead of certificate or
   password.  Thus, the authentication server is not required to manage
   the certificates and the passwords of device any more.  Finally, the
   FSU protocol provides the highest security against leakages of secret
   keys.  Thus, security of a session key is preserved even if some
   secret keys are leaked because of resource restriction and
   installation environment of devices.

2.  Requirements Terminology

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
   memo are to be interpreted as described in [1].

3.  Notation

   This section shows notation used in this memo.

   Let F_q be a finite field with q = p^n elements for a prime p and an
   integer n and let E(F_q) be an elliptic curve with an order r and an
   embedding degree k defined over F_q.  An embedding degree k is
   defined as a minimum integer k such that r is a divisor of q^k - 1.

   Let G_1 (resp.  G_2) be an additive group with an order r generated
   by E(F_q) (resp.  E'(F_q)).  Let G_T be multiplicative groups with
   the same order r.  Let P_1, P_2 be generators of G_1, G_2
   respectively.  We say that (G_1, G_2, G_T) are bilinear map groups if
   there exists a pairing e: (G_1, G_2) -> G_T satisfying the following
   properties:

   1.  Bilinearity: for any Q_1 in G_1, for any Q_2 in G_2, for any a, b
       in Z_r, we have the relation e(aQ_1, bQ_2) = e(Q_1,Q_2)^{ab}.





Kato, et al.           Expires September 19, 2016               [Page 4]


Internet-Draft              FSU Key Exchange                  March 2016


   2.  Non-degeneracy: for any Q_1 in G_1, e(Q_1,Q_2) = 1 only if Q_2 =
       O_{G_2} and for any Q_2 in G_2, e(Q_1,Q_2) = 1 only if Q_1 =
       O_{G_1}.

   3.  Computability: for any Q_1 in G_1, for any Q_2 in G_2, the
       bilinear map is efficiently computable.

   This pairing is described in specification of optimal ate pairing
   specification[3].  It is defined by Pairing-Parm-ID following way.

      Pairing-Param-ID = {
          G1-Curve-ID,
          G2-Curve-ID
          GT-Field-ID
      }

   G1-Curve-ID and G2-Curve-ID is an identifiers of elliptic curve.  And
   GT-Field-ID is an identifier of the G_T range of finite field.  G1-
   Curve-ID , G2-Curve-ID and GT-Field-ID are described in [2] the
   following way.































Kato, et al.           Expires September 19, 2016               [Page 5]


Internet-Draft              FSU Key Exchange                  March 2016


    G1-Curve-ID = {
        p_b    : A prime specifying base field F_p.
        A, B   : The coefficients of the equation y^2 = x^3 A * x + B
                defining E.
        G = (x, y) : The base point, i.e., a point with x and y
                 being its x- and y-coordinates in E, respectively.
        r      : The prime order of the group generated by G.
        h      : The cofactor of G in E.
   }
    G2-Curve-ID = {
        p_b    : A prime specifying base field F_p.
        e2     : The constant of an irreducible polynomial specifying
                 extension field F_{p^2} = Fp[u] / (u^2 - e2).
        A', B' : The coefficients of the equation y^2 = x^3 A' * x +
                   B' defining E'.
        G' = (x', y') : The base point, i.e., a point with x' and y'
                 being its x- and y-coordinates in E', respectively.
        r'      : The prime order of the group generated by G'.
        h'      : The cofactor of G' in E'.
   }

   GT-Filed-ID = {
        p_b    : A prime specifying base field.
        r      : The prime order of the subgroup of F_{p^12}.
        e2     : The constant of the irreducible polynomial of F_{p^2} =
                 F_p [u] / (u^2 - e2).
        e6     : The constant of the irreducible polynomial of F_{p^6} =
                 F_{p^2}[v] / (v^3 - e6).
        e12    : The constant of the irreducible polynomial of F_{p^12}
                 = F_{p^6}[w] / (w^2 - e12).
        h''    : The cofactor of G_T
    }

   In addition, this memo uses the following functions.

   floor(x) : The function returning an integer such that max{x' in Z |
   x' <= x}.

   ceil(x) : The function returning an integer such that min{x' in Z |
   x' >= x}.

   O_E : The point at infinity over elliptic curve E.

4.  Data Type and Its Conversions

   This section describes data type and its conversion used in this
   memo.




Kato, et al.           Expires September 19, 2016               [Page 6]


Internet-Draft              FSU Key Exchange                  March 2016


4.1.  BitString-to-OctetString Conversion (BS2OSP)

   This memo uses conversion from bit strings to octet strings.
   Informally, the idea is to pad the bit string with 0's on the left to
   make its length a multiple of 8, then chop the result up into octets.
   Formally, the conversion routine, BS2OSP(B), is specified in
   Appendix A.1

4.2.  OctetString-to-BitString Conversion (OS2BSP)

   This memo uses conversion from octet strings to bit strings.
   Informally, the idea is simply to view the octet string as a bit
   string.  Formally, the conversion routine, OS2BSP(M), is specified in
   Appendix A.2

4.3.  FieldElement-to-Integer Conversion (FE2IP)

   This memo uses conversion from field elements to integers.  An finite
   field element should be represented as a polynomial with subfield
   coefficients, which can be represented as a sequence of the
   coefficients.  Informally, the idea is simply to view the sequence of
   the coefficients as the radix-p^m representation of the base field
   elements, where p^m is the number of the subfield elements.
   Formally, the conversion routine, FE2IP(a), is specified in
   Appendix A.3

4.4.  Integer-to-FieldElement Conversion (I2FEP)

   This memo uses conversion from integers to field elements.  A field
   element should be represented as a polynomial with subfield
   coefficients, and it can be represented as a sequence of the
   coefficients.  Informally, the idea is to represent the integer with
   radix-p^m positional number system where p^m is the number of the
   subfield element, and then convert the each digit to the each
   coefficient of the polynomial.  Formally, the conversion routine,
   I2FEP(x), is specified in Appendix A.4:

4.5.  FieldElement-to-OctetString Conversion (FE2OSP)

   This memo uses conversion from field elements to octet strings.  This
   conversion is constructed by using FE2IP and I2SOP conversions.
   Formally, the conversion routine, FE2OSP(a), is specified in
   Appendix A.5.








Kato, et al.           Expires September 19, 2016               [Page 7]


Internet-Draft              FSU Key Exchange                  March 2016


4.6.  OctetString-to-FieldElement Conversion (OS2FEP)

   This memo uses conversion from octet strings to field elements.  This
   conversion is constructed by using OS2IP and I2FEP conversions.
   Formally, the conversion routine, OS2FEP(M), is specified in
   Appendix A.6.

4.7.  EllipticCurvePoint-to-OctetString Conversion (ECP2OSP)

   This memo uses conversion from elliptic curve points to octet
   strings.  Informally the idea is that, if point compression is being
   used, the compressed y-coordinate is placed in the leftmost octet of
   the octet string along with an indication that point compression is
   on, and the x-coordinate is placed in the remainder of the octet
   string; otherwise if point compression is off, the leftmost octet
   indicates that point compression is off, and remainder of the octet
   string contains the x-coordinate followed by the y-coordinate.
   Formally, the conversion routine, ECP2OSP(P,R), is specified in
   Appendix A.7.

4.8.  OctetString-to-EllipticCurvePoint Conversion (OS2ECPP)

   This memo uses conversion from octet strings to elliptic curve
   points.  Informally, the idea is that, if the octet string represents
   a compressed point, the compressed y-coordinate is recovered from the
   leftmost octet, the x-coordinate is recovered from the remainder of
   the octet string, and then the point compression process is reversed;
   otherwise the leftmost octet of the octet string is removed, the
   x-coordinate is recovered from the left half of the remaining octet
   string, and the y-coordinate is recovered from the right half of the
   remaining octet string.  Formally, the conversion routine,
   OS2ECPP(M), is specified in Appendix A.8.

5.  Building Block of FSU Key Exchange

   This section describes building block for constructing FSU Key
   Exchange.

5.1.  Key Derivation Function

   MGF1 is a mask generation function, parameterized by a hash function.
   MGF1(M,n) is defined as follows:

   System parameters:

   o  Hash : a hash function

   o  hashLen : the length in octets of the hash function output



Kato, et al.           Expires September 19, 2016               [Page 8]


Internet-Draft              FSU Key Exchange                  March 2016


   Input:

   o  M : a seed from which a mask is generated, an octet string

   o  n : the octet length of the output, a positive integer

   Output:

   o  mask : a mask, an octet string of length n

   Method:

   1.   Let n_0 be the octet length of M.  If n_0 + 4 is greater than
        the input limitation for the hash function, output INVALID and
        stop.

   2.   Set cThreshold = ceil(n / hashLen)

   3.   If cThreshold > 2^32, output INVALID and stop

   4.   Let M' be the empty octet string

   5.   Set counter = 0

   6.   B = B_{0}, ..., B{31} such that counter = B_{31} + B_{30}*2 +
        ... + B_{0}*2^{31}

   7.   Compute C = BS2OSP(B)

   8.   Compute H = Hash(M||C)

   9.   Set M' = M'||H

   10.  Set counter = counter + 1

   11.  If counter < cThreshold, go back to step 6.

   12.  Set mask = M'_0M'_1...M'_{n-1} where M' = M'_0M'_1M'_2...

   13.  Output mask

5.2.  Hashing to Point

   Hashed value should be converted to elliptic curve point as described
   in this section.  Formally, the conversion routine,
   HASHINGTOPOINT(Curve-ID, Hash, M), is specified as follows:

   Input:



Kato, et al.           Expires September 19, 2016               [Page 9]


Internet-Draft              FSU Key Exchange                  March 2016


   o  Curve-ID : an elliptic curve parameter

   o  Hash : a hash function

   o  M : an octet string

   Output:

   o  P : an elliptic curve point

   Method:

   1.   Set i = 0

   2.   B = B_{0}, ..., B{15} such that counter = B_{15} + B_{14}*2 +
        ... + B_{0}*2^{15}

   3.   Compute C = BS2OSP(B)

   4.   x_0 = OS2FQE(C||M, Hash, F_{p^m}) in F_{p^m}

   5.   t = x_0^3 + A * x_0 + B

   6.   If t=0, set P =(x_0, 0) and output h'*P

   7.   If t is not square in F_{p^m}, set i = i + 1 and go back to step
        2

   8.   Set alpha be one of square roots of t.  Then, -alpha is another
        square root of t.

   9.   Set y_1 = FE2IP(alpha)

   10.  Set y_2 = FE2IP(-alpha)

   11.  If y_1 > y_2, set y_0 = -alpha

   12.  Else (i.e. y_1 <= y_2), set y_0 = alpha

   13.  Set P = (x_0, y_0)

   14.  Output h * P

5.2.1.  IHF1

   Bit string should be converted to hashed non-negative integer less
   than an assigned integer as described in this section.  Formally, the
   conversion routine, IHF1(s,n,Hash) is defined as follows:



Kato, et al.           Expires September 19, 2016              [Page 10]


Internet-Draft              FSU Key Exchange                  March 2016


   Input:

   o  s: an octet string

   o  n : an integer

   o  Hash : a hash function

   Output:

   o  v in Z_n

   Method:

   1.   Set hashLen be the length of the output of the hash function
        Hash

   2.   Set h_0 be the zero string of length hashLen

   3.   h_1 = Hash(h_0 || s)

   4.   B = B_0,...,B_{l-1} = OS2BSP(h_1)

   5.   a_1 = sum_{i = 0}^{l-1} 2^{l-1-i} * B_{i}

   6.   h_2 = Hash(h_1 || s)

   7.   B = B_0,...,B_{l-1} = OS2BSP(h_2)

   8.   a_2 = sum_{i=0}^{l-1} 2^{l-1-i} * B_{i}

   9.   v = 2^{hashLen} * a_1 + a_2 mod n

   10.  Output v

5.2.2.  OS2FQE

   Octet string should be converted to hashed finite field element as
   described in this section.  Formally, the conversion routine,
   OS2FQE(s,Hash,F_{p^m}) is defined as follows:

   Input:

   o  s: an octet string

   o  Hash : a hash function





Kato, et al.           Expires September 19, 2016              [Page 11]


Internet-Draft              FSU Key Exchange                  March 2016


   o  F_{p^m} : a finite field with p^m elements where p is a prime, and
      m > 0 is an integer

   Output:

   o  a: an element in F_{p^m}

   Method:

   1.  Set i = 0

   2.  B = B_{0}, ..., B{31} such that counter = B_{31} + B_{30}*2 + ...
       + B_{0}*2^{31}

   3.  Compute C = BS2OSP(B)

   4.  Compute t_i = IHF1(C||s,p,Hash)

   5.  If i < m, set i = i + 1 and go back to step2

   6.  Compute a = sum_{i=0}^{m-1} t_i * beta^i where beta is the
       variable of the polynomial

   7.  Output a

5.3.  Group Membership Test Function

   GROUPMEMBERSHIPTEST(Curve-ID, P) is a test function that an elliptic
   curve point is on the correct curve and group.  GROUPMEMBERSHIPTEST
   is defined as follows:

   Input:

   o  Curve-ID : an elliptic curve identifier

   o  P = (x,y) : an elliptic curve point

   Output:

   o  boolean : an integer in {0,1}

   Method:

   1.  If P = O_E, then output 1

   2.  If y^2 != x^3 + A * x + B, then output 0

   3.  If h != 1 && r * P != O_E, then output 0



Kato, et al.           Expires September 19, 2016              [Page 12]


Internet-Draft              FSU Key Exchange                  March 2016


   4.  Output 1

6.  FSU Key Exchange

   This section provides the specification of ID-based authenticated key
   exchange protocol FSU [4] that is an extension of FSU (Fujioka-
   Suzuki-Ustaoglu) protocol standardized in ISO/IEC11770-3 [5] [6].

6.1.  System Parameter Setup

   Key Generation Center (KGC) defines the following system parameters
   in FSU:

   o  Pairing-Param-ID : An identifier for showing asymmetric pairing.
      i.e., G1-Curve-ID, G2-Curve-ID and GT-Filed-ID.

   o  G1-Curve-ID is an identifier for showing an elliptic curve which
      defines cyclic groups G_1 with prime p_b_1, coefficients A_1 and
      B_1, generator P_1, order r, and cofactor h_1.

   o  G2-Curve-ID is an identifier for showing an elliptic curve which
      defines cyclic groups G_2 with prime p_b_2, irreducible polynomial
      e2_2, coefficients A_2 and B_2, generator P_2, order r, and
      cofactor h_2.

   o  GT-Field-ID is an identifier for showing a pairing co-domain group
      which is subgroup of order r in G_{phi_12(p)}.  G_{phi_12(p)} is
      the 12-th cyclotomic subgroup of order p^4-p^2+1 in F_{p^12}^*.

   o  HASH-ID : An identifier for showing a hash function i,e., Hash :
      {0,1}^* -> {0,1}^hashLen.

   o  hashLen : Length of output by Hash.

   o  KDF-ID : An identifier for showing key derivation function, i.e.,
      MGF1: {0,1}^* -> {0,1}^n.

   o  n : Length of output by key derivation function.

   o  R : A point compression type of conversion between elliptic curve
      point and octet string specifically "Compressed", "Uncompressed",
      or "Hybrid".

   KGC generates the master secret key MSK and master public key MPK
   from system parameters as following.

   1.  KGC selects a random integer z in Z_r.




Kato, et al.           Expires September 19, 2016              [Page 13]


Internet-Draft              FSU Key Exchange                  March 2016


   2.  KGC computes Z_v = z * P_v for v is in {1, 2}.

   3.  KGC sets MSK = z and MPK = (Z_1, Z_2).

   Hash function H_v are defined as H_v(M) = HASHINGTOPOINT(Gv-Curve-ID,
   Hash, "FSU"||ECP2OSP(Z_1, R)||ECP2OSP(Z_2, R)||M) for v in {1, 2}.
   Hash function H is defined as H(M) = MGF1("FSU"||ECP2OSP(Z_1,
   R)||ECP2OSP(Z_2, R)||M, n).

6.2.  Key Distribution by KGC

   This subsection explains operations of key distribution by KGC.
   There are two types of static secret key in FSU Key Exchange,
   respectively static secret key based on cyclic groups in G_1 and in
   G_2.  FSU Key Exchange requires that an initiator and a responder use
   static secret key with different types, respectively.  Hence, KCG
   needs to define a rule for key distribution for users.  For example,
   clients use static secret keys in G_1 and servers use them in G_2.

   KGC generates static secret key D_{i, v} for an identifier ID_i for i
   in {A, B} of user in G_v as following.

   1.  Let MPK be (Z_1, Z_2) and MSK be z.

   2.  KGC Compute D_{i ,v} = z*H_v(ID_i).

   3.  Distribute D_{i ,v} to a user with ID_i.

6.3.  FSU Key Exchange Protocol

   This subsection describes FSU Key Exchange Protocol in an initiator
   U_A with an identifier ID_A and static secret key D_{A,1} and a
   responder U_B with an identifier ID_B and static secret key D_{B,2}.

   Computation of ephemeral public key by U_A

   1.  U_A selects a random integer x_A in Z_r.

   2.  U_A computes the ephemeral public key X_{A,v} = x_A * P_v for v
       in {1,2}.

   3.  U_A computes XOS_{A,v} = ECP2OSP(X_{A,v}, R) for v in {1,2}.

   4.  U_A sends (ID_A, ID_B, XOS_{A,1}, XOS_{A,2}) to U_B.

   Computation of ephemeral public key by U_B

   1.  U_B receives (ID_A, ID_B, XOS_{A,1}, XOS_{A,2}).



Kato, et al.           Expires September 19, 2016              [Page 14]


Internet-Draft              FSU Key Exchange                  March 2016


   2.  U_B computes X_{A,v} = OS2ECPP(XOS_{A,v}) for v in {1,2}.

   3.  If (GROUPMEMBERSHIPTEST(G1-Curve-ID, X_{A,1}) = 0 ||
       GROUPMEMBERSHIPTEST(G2-Curve-ID, X_{A,2}) = 0 || e(X_{A,1}, P_2)
       != e(P_1, X_{A,2})), then abort.

   4.  U_B selects a random ephemeral secret key x_B in Z_r.

   5.  U_B computes the ephemeral public key X_{B,v} = x_B * P_v for v
       in {1,2}.

   6.  U_B computes XOS_{B,v} = ECP2OSP(X_{B,v}, R) for v in {1,2}.

   7.  U_B sends (ID_B, ID_A, XOS_{B,1}, XOS_{B,2}) to U_A.

   Computation of session key by U_B

   1.  U_B computes sigma_1 = e(H_1(ID_A), D_{B,2}).

   2.  U_B computes sigma_2 = e(H_1(ID_A) + X_{A,1}, D_{B,2} + x_B *
       Z_2).

   3.  U_B computes sigma_3 = x_B * X_{A,1}.

   4.  U_B computes sigma_4 = x_B * X_{A,2}.

   5.  U_B computes sigmaOS_j = FE2OSP(sigma_j) for j in {1,2}.

   6.  U_B computes sigmaOS_j' = ECP2OSP(simga_j',R) for j' in {3,4}.

   7.  Set sid =
       (ID_A||ID_B||XOS_{A,1}||XOS_{A,2}||XOS_{B,1}||XOS_{B,2}).

   8.  U_B computes session key K =
       H(sigmaOS_1||sigmaOS_2||sigmaOS_3||sigmaOS_4||sid).

   Computation of session key by U_A

   1.   U_A computes X_{B,v} = OS2ECPP(XOS_{B,v}) for v in {1,2}.

   2.   If (GROUPMEMBERSHIPTEST(G1-Curve-ID, X_{B,1}) = 0 ||
        GROUPMEMBERSHIPTEST(G2-Curve-ID, X_{B, 2}) = 0 || e(X_{B,1},
        P_2) != e(P_1, X_{B,2})), then abort.

   3.   U_A computes sigma_1 = e(D_{A,1}, H_2(ID_B)).

   4.   U_A computes sigma_2 = e(D_{A,1} + x_A * Z_1, H_2(ID_B) +
        X_{B,2}).



Kato, et al.           Expires September 19, 2016              [Page 15]


Internet-Draft              FSU Key Exchange                  March 2016


   5.   U_A computes sigma_3 = x_A * X_{B,1}.

   6.   U_A computes sigma_4 = x_A * X_{B,2}.

   7.   U_A computes sigmaOS_j = FE2OSP(sigma_j) for j in {1,2}.

   8.   U_A computes sigmaOS_j' = ECP2OSP(simga_j',R) for j' in {3,4}.

   9.   Set sid =
        (ID_A||ID_B||XOS_{A,1}||XOS_{A,2}||XOS_{B,1}||XOS_{B,2}).

   10.  U_A compute session key K =
        H(sigmaOS_1||sigmaOS_2||sigmaOS_3||sigmaOS_4||sid).

7.  Security Considerations

   This memo specifies identity-based authenticated key exchange
   protocol FSU [4] [6] [5] which is secure in the id-eCK(id-based
   extended Canetti-Krawczyk) security model under the GBDH(gap bilinear
   DH) assumption [4].

   id-eCK security model is the most strong security model in the
   meaning of that it ensures the safety of session key if any non-
   trivial combinations of master key, static key, and ephemeral key are
   leaked.

   And id-eCK security model guarantees following 4 security notions:

      MitM(resistance to man in the middle attacks),

      wPFS(weak perfect forward security),

      KCI(resistance to key compromise impersonation attacks),

      RLE(resilience to leakage of ephemeral private keys).

8.  Acknowledgements

   TBD

9.  Algorithm Identifiers

   TBD








Kato, et al.           Expires September 19, 2016              [Page 16]


Internet-Draft              FSU Key Exchange                  March 2016


10.  Change log

   NOTE TO RFC EDITOR: Please remove this section in before final RFC
   publication.

11.  Test Vectors

   TBD

12.  References

12.1.  Normative References

   [1]        Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", RFC 2119, March 1997.

   [2]        Kasamatsu, K., Kanno, S., Kato, A., Scott, M., Kobayashi,
              T., and Y. Kawahara, "Barreto-Naehrig Curves", draft-
              kasamatsu-bncurves-02 (work in progress), 2015.

   [3]        Kato, A., Scott, M., Kobayashi, T., and Y. Kawahara,
              "Barreto-Naehrig Curves", draft-kato-optimal-ate-
              pairings-01 (work in progress), 2015.

12.2.  Informative References

   [4]        Fujioka, A., Hoshino, F., Kobayashi, T., Suzuki, K.,
              Ustaglu, B., and K. Yoneyama, "id-eCK Secure ID-Based
              Authenticated Key Exchange on Symmetric and Asymmetric
              Pairing", Proceedings IEICE Transactions 96-A(6):
              1139-1155, 2013.

   [5]        Fujioka, A., Suzuki, K., and B. Ustaglu, "Ephemeral Key
              Leakage Resilient and Efficient ID-AKEs That Can Share
              Identities, Private and Master Keys", Proceedings Pairing
              2010 Lecture Notes in Computer Science Volume 6487, pp
              187-205, 2010.

   [6]        "Information technology -- Security techniques -- Key
              management -- Part 3: Mechanisms using asymmetric
              techniques.", ISO/IEC 11770-3: 2015, 2015.

   [7]        Shamir, A., "Identity-based Cryptosystems and Signature
              Schemes", Proceedings CRYPTO '84, LNCS 196, pages 47-53,
              Springer-Verlag, 1984.






Kato, et al.           Expires September 19, 2016              [Page 17]


Internet-Draft              FSU Key Exchange                  March 2016


   [8]        Boneh, D. and M. Franklin, "Identity-Based Encryption from
              the Weil Pairing", Proceedings CRYPTO 2001, LNCS 2139,
              pages 213-229, Springer-Verlag, 2001.

   [9]        Huang, H. and Z. Cao, "An ID-based Authenticated Key
              Exchange Protocol Based on Bilinear Diffie-Hellman
              Problem", Proceedings the 4th International Symposium on
              Information, Computer, and Communications Security
              (ASIACCS '09) pp. 333-342, ACM, 2009.

   [10]       Canetti, R. and H. Krawczyk, "Analysis of Key-Exchange
              Protocols and Their Use for Building Secure Channels",
              Proceedings Eurocrypt 2001 (LNCS2015), pp. 453-474,
              Springer-Verlag, 2001.

   [11]       LaMacchia, B., Lauter, K., and A. Mityagin, "Stronger
              Security of Authenticated Key Exchange", Proceedings in
              Provable Security (LNCS 4784), pp. 1-16, Springer, 2007.

































Kato, et al.           Expires September 19, 2016              [Page 18]


Internet-Draft              FSU Key Exchange                  March 2016


Appendix A.  Construction of Data Conversion

A.1.  Construction of BS2OSP

   Concrete construction of BS2OSP(B) is specified as follows:

   Input:

   o  B = B_0 B_1 ... B_{l-1} : a bit string of length l

   Output:

   o  M = M_0 M_1 ... M_{n-1}: an octet string of length n = ceil(l/8).

   Method:

   1.  If l = 0, then output empty octet string and stop.

   2.  For j in {0,...,8n-1}, if j >= 8n - l, set B'_j = B_{j-(8n-l)},
       otherwise set B'_j = 0.

   3.  For i in {0,...,n-1}, set M_i = B'_{8i} B'_{8i+1}...B'_{8i+7}.

   4.  Output M = M_0 M_1 ... M_{n-1}.

A.2.  Construction of OS2BSP

   Concrete construction of OS2BSP(M) is specified as follows:

   Input:

   o  M = M_0M_1...M{n-1}: an octet string of length n.

   Output:

   o  B = B_0B_1...B_{l-1} : a bit string of lenth l = 8*n

   Method:

   1.  If l = 0, then output empty octet string and stop.

   2.  For i in {0, ..., n-1} , j in {0,...,7}, set B_{8i + j} in {0,1}
       as M_i = B_{8i} B_{8i+1}...B_{8i+7}.

   3.  Output B = B_0 B_1 ... B_{l-1}.






Kato, et al.           Expires September 19, 2016              [Page 19]


Internet-Draft              FSU Key Exchange                  March 2016


A.3.  Construction of FE2IP

   Concrete construction of FE2IP(a) is specified as follows:

   System parameters:

   o  F_{p^{m_2}}/F_{p^{m_1}}: a field extension with an irreducible
      polynomial Irr(F_{p^m_2} / F_{p^m_1};beta)

   Input:

   o  a : a field element in F_{p^m_2}

   Output:

   o  x : an integer in {0,...,p^{m_2} - 1}

   Method:

   1.  If m_2 = 1 (i.e.  F_{p^m_2} is prime field)

          A field element of F_{p^{m_2}} must be represented an an
          integer in {0, ..., p-1}

          (A) Set x = a

          (B) Output x

   2.  Else (i.e. m_2 > 1)

          (A) Let the coefficients a_i in F_{p^m_1} for i in {0,...,m_2
          / m_1 - 1} such that a = sum_{i=0}^{m_2 / m_1 - 1} a_i *
          beta^i

          (B) Compute x = sum_{i=0}^{m_2 / m_1 - 1} FE2IP(a_i) *
          (p^{m_1})^i

          (C) Output x

A.4.  Construction of I2FEP

   Concrete construction of I2FEP(x) is specified as follows:

   System parameters:

   o  F_{p^{m_2}}/F_{p^{m_1}}: a field extension with an irreducible
      polynomial Irr(F_{p^m_2} / F_{p^m_1};beta)




Kato, et al.           Expires September 19, 2016              [Page 20]


Internet-Draft              FSU Key Exchange                  March 2016


   Input:

   o  x : an integer in {0,...,p^{m_2} - 1}

   Output:

   o  a : a field element in F_{p^m_2}

   Method:

   1.  If m_2 = 1 (i.e.  F_{p^m_2} is prime field)

          A field element of F_{p^{m_2}} must be represented an an
          integer in {0, ..., p-1}

          (A) Set a = x

          (B) Output a

   2.  Else (i.e. m_2 > 1)

          (A) Let x_i be an element in {0,...,p^{m_1}-1} for i in
          {0,...,m_2 / m_1 - 1} such that x = sum_{i=0}^{m_2 / m_1 -1}
          x_i * p^{m_1}^i

          (B) Compute a = sum_{i=0}^{m_2 / m_1 - 1} I2FEP(x_i) * beta^i

          (C) Output a

A.5.  Construction of FE2OSP

   System parameter:

   o  F_{p^m} : a finite field with p^m elements where p is a prime, and
      m > 0 is an integer

   o  n : an integer equivalent to ceil(m * log_2 p / 8)

   Input:

   o  a : a field element in F_{p^m}

   Output:

   o  M : an octet string

   Method:




Kato, et al.           Expires September 19, 2016              [Page 21]


Internet-Draft              FSU Key Exchange                  March 2016


   1.  Compute I = FE2IP(a)

   2.  Compute X = x_{0}, ..., X_{n-1} such that I = x_{n-1} + x_{n-2}*2
       + ... + x_{1}*2^{n-2} + x_{0}*2^{n-1}

   3.  Compute M = BS2OSP(X)

   4.  Output M

A.6.  Construction of OS2FEP

   System parameter:

   o  F_{p^m} : a finite field with p^m elements where p is a prime, and
      m > 0 is an integer

   o  n : an integer equivalent to ceil(m * log_2 p / 8)

   Input:

   o  M : an octet string

   Output:

   o  a : a field element in F_{p^m}

   Method:

   1.  Compute X = OS2BSP(M)

   2.  Let X be x_0,...,x_{l-1}

   3.  Compute I = sum_{i=0}^{l-1} 2^{l-1-i} * x_{i}

   4.  Compute a = I2FEP(I)

   5.  Output a

A.7.  Construction of ECP2OSP

   Concrete construction of ECP2OSP(P,R), is specified as follows:

   System parameters:

   o  Curve-ID : an elliptic curve parameter

   Input:




Kato, et al.           Expires September 19, 2016              [Page 22]


Internet-Draft              FSU Key Exchange                  March 2016


   o  P : a point on an elliptic curve over F_{p^m}

   o  R : compression type specifically "Compressed", "Uncompressed", or
      "Hybrid"

   Output:

   o  M : an octet string of length n

   Method:

   1.  If P = O_E

          (A) Compute M = BS2OSP(00000000)

          (B) Output M

   2.  If P = (x,y) != O_E && R = Compressed

          (A) Set X = FE2OSP(x)

          (B) If p is odd && y = 0 , set y' = 0

          (C) Else if p is odd && y != 0, set y' = y_i mod 2 such that y
          = y_{m-1} * beta^{m-1} + ... + y_1 * beta + y_0 and i is the
          smallest integer such that y_i != 0

          (D) If y' = 0, compute L = BS2OSP(00000100)

          (E) If y' = 1, compute L = BS2OSP(00000101)

          (F) Output M = L || X

   3.  If P = (x,y) != O_E && R = Uncompressed

          (A) Set X = FE2OSP(x)

          (B) Set Y = FE2OSP(y)

          (C) Compute L = BS2OSP(00000100)

          (D) Output M = L || X || Y

   4.  If P = (x,y) != O_E && R = Hybrid

          (A) Set X = FE2OSP(x)

          (B) Set Y = FE2OSP(y)



Kato, et al.           Expires September 19, 2016              [Page 23]


Internet-Draft              FSU Key Exchange                  March 2016


          (C) If y = 0, set y' = 0

          (D) Else (i.e. y != 0) y' = y_i mod 2 such that y = y_{m-1} *
          beta^{m-1} + ... + y_1 * beta + y_0 and i is the smallest
          integer such that y_i != 0

          (E) If y' = 0, compute L = BS2OSP(00000110)

          (F) If y' = 1, compute L = BS2OSP(00000111)

          (G) Output M = L || X || Y

A.8.  Construction of OS2ECPP

   Concrete construction of OS2ECPP(M), is specified as follows:

   System parameters

   o  Curve-ID : an elliptic curve parameter

   Input:

   o  M : an octet string

   Output:

   o  P : an elliptic curve point

   Method:

   1.  If M = BS2OSP(00000000), output P = O_E

   2.  If M has length ceil(m * log_2 p / 8) + 1

          (A) Let M be L||X where L is a single octet

          (B) Compute x = OS2FEP(X)

          (C) If L = BS2OSP(00000010), then set y' = 0

          (D) Else if L = BS2OSP(00000011), then set y' = 1

          (E) Else output INVALID and stop

          (F) Compute w = x^3 + A * x + B

          (G) Compute gamma = square(w)




Kato, et al.           Expires September 19, 2016              [Page 24]


Internet-Draft              FSU Key Exchange                  March 2016


          (H) If there is no gamma in F_{p^m}, then output INVALID and
          stop

          (I) Else if gamma = 0, then set y = 0

          (J) Else if gamma_i = y' mod 2 where gamma = gamma_{m-1} *
          beta^{m-1} + ... + gamma_{1} * beta + gamma_{0} and i is the
          smallest integer such that gamma_i != 0

          (K) Else if gamma_i != y' mod 2, set y = -gamma where gamma =
          gamma_{m-1} * beta^{m-1} + ... + gamma_{1} * beta + gamma_{0}
          and i is the smallest integer such that gamma_i != 0

          (L) Output P = (x,y)

   3.  If M has length 2 * floor(m * log_2 p / 8) + 1

          (A) Let M be L || X || Y where L is a single octet, X is
          floor(m * log_2 p / 8) octets, and Y is floor(m * log_2 p / 8)
          octets

          (B) Unless L is BS2OSP(00000100), BS2OSP(00000110) or
          BS2OSP(00000111), output INVALID and stop.

             (a) Compute x = OS2FEP(X)

             (b) Compute y = OS2FEP(Y)

             (c) If (x,y) does not satisfy the equation of elliptic
             curve, then output INVALID and stop

             (d) Output P = (x,y)

Authors' Addresses

   Akihiro Kato
   NTT Software Corporation

   EMail: kato.akihiro-at-po.ntts.co.jp


   Thomas Hardjono
   MIT

   EMail: hardjono-at-mit.edu






Kato, et al.           Expires September 19, 2016              [Page 25]


Internet-Draft              FSU Key Exchange                  March 2016


   Tetsutaro Kobayashi
   NTT

   EMail: kobayashi.tetsutaro-at-lab.ntt.co.jp


   Tsunekazu Saito
   NTT

   EMail: saito.tsunekazu-at-lab.ntt.co.jp


   Koutarou Suzuki
   NTT

   EMail: suzuki.koutarou-at-lab.ntt.co.jp



































Kato, et al.           Expires September 19, 2016              [Page 26]