Internet DRAFT - draft-kato-fsu-key-exchange
draft-kato-fsu-key-exchange
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]
