idnits 2.17.1 draft-kato-fsu-key-exchange-01.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == The document doesn't use any RFC 2119 keywords, yet has text resembling RFC 2119 boilerplate text. -- The document date (March 18, 2016) is 2961 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- No issues found here. Summary: 1 error (**), 0 flaws (~~), 2 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group A. Kato 3 Internet-Draft NTT Software Corporation 4 Intended status: Informational T. Hardjono 5 Expires: September 19, 2016 MIT 6 T. Kobayashi 7 T. Saito 8 K. Suzuki 9 NTT 10 March 18, 2016 12 FSU Key Exchange 13 draft-kato-fsu-key-exchange-01 15 Abstract 17 This draft proposes an identity-based authenticated key exchange 18 protocol following the extended Canetti-Krawczyk (id-eCK) model. The 19 protocol is currently the most efficient among the id-eCK protocols. 21 Status of This Memo 23 This Internet-Draft is submitted in full conformance with the 24 provisions of BCP 78 and BCP 79. 26 Internet-Drafts are working documents of the Internet Engineering 27 Task Force (IETF). Note that other groups may also distribute 28 working documents as Internet-Drafts. The list of current Internet- 29 Drafts is at http://datatracker.ietf.org/drafts/current/. 31 Internet-Drafts are draft documents valid for a maximum of six months 32 and may be updated, replaced, or obsoleted by other documents at any 33 time. It is inappropriate to use Internet-Drafts as reference 34 material or to cite them other than as "work in progress." 36 This Internet-Draft will expire on September 19, 2016. 38 Copyright Notice 40 Copyright (c) 2016 IETF Trust and the persons identified as the 41 document authors. All rights reserved. 43 This document is subject to BCP 78 and the IETF Trust's Legal 44 Provisions Relating to IETF Documents 45 (http://trustee.ietf.org/license-info) in effect on the date of 46 publication of this document. Please review these documents 47 carefully, as they describe your rights and restrictions with respect 48 to this document. Code Components extracted from this document must 49 include Simplified BSD License text as described in Section 4.e of 50 the Trust Legal Provisions and are provided without warranty as 51 described in the Simplified BSD License. 53 Table of Contents 55 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 56 1.1. Our Motivation . . . . . . . . . . . . . . . . . . . . . 3 57 2. Requirements Terminology . . . . . . . . . . . . . . . . . . 4 58 3. Notation . . . . . . . . . . . . . . . . . . . . . . . . . . 4 59 4. Data Type and Its Conversions . . . . . . . . . . . . . . . . 6 60 4.1. BitString-to-OctetString Conversion (BS2OSP) . . . . . . 7 61 4.2. OctetString-to-BitString Conversion (OS2BSP) . . . . . . 7 62 4.3. FieldElement-to-Integer Conversion (FE2IP) . . . . . . . 7 63 4.4. Integer-to-FieldElement Conversion (I2FEP) . . . . . . . 7 64 4.5. FieldElement-to-OctetString Conversion (FE2OSP) . . . . . 7 65 4.6. OctetString-to-FieldElement Conversion (OS2FEP) . . . . . 8 66 4.7. EllipticCurvePoint-to-OctetString Conversion (ECP2OSP) . 8 67 4.8. OctetString-to-EllipticCurvePoint Conversion (OS2ECPP) . 8 68 5. Building Block of FSU Key Exchange . . . . . . . . . . . . . 8 69 5.1. Key Derivation Function . . . . . . . . . . . . . . . . . 8 70 5.2. Hashing to Point . . . . . . . . . . . . . . . . . . . . 9 71 5.2.1. IHF1 . . . . . . . . . . . . . . . . . . . . . . . . 10 72 5.2.2. OS2FQE . . . . . . . . . . . . . . . . . . . . . . . 11 73 5.3. Group Membership Test Function . . . . . . . . . . . . . 12 74 6. FSU Key Exchange . . . . . . . . . . . . . . . . . . . . . . 13 75 6.1. System Parameter Setup . . . . . . . . . . . . . . . . . 13 76 6.2. Key Distribution by KGC . . . . . . . . . . . . . . . . . 14 77 6.3. FSU Key Exchange Protocol . . . . . . . . . . . . . . . . 14 78 7. Security Considerations . . . . . . . . . . . . . . . . . . . 16 79 8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 16 80 9. Algorithm Identifiers . . . . . . . . . . . . . . . . . . . . 16 81 10. Change log . . . . . . . . . . . . . . . . . . . . . . . . . 17 82 11. Test Vectors . . . . . . . . . . . . . . . . . . . . . . . . 17 83 12. References . . . . . . . . . . . . . . . . . . . . . . . . . 17 84 12.1. Normative References . . . . . . . . . . . . . . . . . . 17 85 12.2. Informative References . . . . . . . . . . . . . . . . . 17 86 Appendix A. Construction of Data Conversion . . . . . . . . . . 19 87 A.1. Construction of BS2OSP . . . . . . . . . . . . . . . . . 19 88 A.2. Construction of OS2BSP . . . . . . . . . . . . . . . . . 19 89 A.3. Construction of FE2IP . . . . . . . . . . . . . . . . . . 20 90 A.4. Construction of I2FEP . . . . . . . . . . . . . . . . . . 20 91 A.5. Construction of FE2OSP . . . . . . . . . . . . . . . . . 21 92 A.6. Construction of OS2FEP . . . . . . . . . . . . . . . . . 22 93 A.7. Construction of ECP2OSP . . . . . . . . . . . . . . . . . 22 94 A.8. Construction of OS2ECPP . . . . . . . . . . . . . . . . . 24 95 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 25 97 1. Introduction 99 Authenticated key exchange (AKE) is a core security function within 100 many deployed systems today. It is a foundational function that 101 allows end-users and systems alike to be authenticated prior to 102 access to resource and services. Over the past two decades key 103 exchange schemes have been proposed, based on symmetric and 104 asymmetric key cryptography. 106 A more recent approach to AKE protocol has been the introduction of 107 identity binding to the exchange [7] [8], obviating the need to rely 108 on a public key infrastructure in which digital certificates need to 109 be exchanged by users or end-points that wish to communicate signed 110 and/or encrypted messages. 112 Identity-based AKE (ID-AKE) schemes rely on the use of the trusted 113 intermediary referred to as the Key Generation Center (KGC). The 114 role of the KGC, among others, is to generate a pair of master public 115 and secret keys based on the user's identity and to extract a user's 116 secret key corresponding to his or her identity. 118 In a 2-pass ID-AKE scheme, an "initiator" entity wishing to share a 119 key with a second entity (referred to as the "responder") sends 120 ephemeral public information to the responder. In its turn, the 121 responder sends another ephemeral public information to the initiator 122 entity. Following this, each entity would then generate a session 123 from a number of parameters, notably their respective secret keys 124 (given by the KGC), their own secret values of the ephemeral 125 information, the identity of the peer they're communicating with, and 126 the ephemeral information they received from that peer. 128 We propose a provably secure ID-AKE scheme called "FSU" [4] [5] [6] 129 based on the previous model of [9] and which builds on the previous 130 efforts in [10] [11] . The model underlying the FSU was chosen due 131 to the merit of provable security based on an adversarial model in 132 which the adversary has the freedom to choose keys reveal. 134 1.1. Our Motivation 136 In order to establish secure communications, the encryption is used, 137 and a key exchange protocol is necessary to use the encryption. If 138 the key exchange protocol has vulnerability, an attacker can 139 intercept all messages, so encrypted session becomes meaningless. In 140 practice, man in the middle attack and a forward security of key 141 exchange protocol are serious issues. 143 In recent years, IoT technology gathers many attentions. It is 144 expected that 26-30 billion devices will be wirelessly connected by 145 2020. And to set up a huge number of devices with certificates or 146 passwords for key exchange and to maintain the certificates or 147 passwords require many costs. Furthermore, the leakage of a secret 148 key for key exchange and a session key for encryption likely to occur 149 because of resource restriction of device and installation 150 environment of device. 152 To resolve above problems, we propose an ID-based authenticated key 153 exchange protocol FSU. In usual PKI based cryptography, a device 154 must set up password or generate own secret key. On the other hand, 155 in the FSU protocol the trusted third party generate the secret key 156 for a huge number of IoT devices, so the manufacture and users of the 157 devices can maintain secret key for the devices unitarily. The FSU 158 Protocol use existing ID, which can be any string, e.g., e-mail 159 address and serial number, as public key instead of certificate or 160 password. Thus, the authentication server is not required to manage 161 the certificates and the passwords of device any more. Finally, the 162 FSU protocol provides the highest security against leakages of secret 163 keys. Thus, security of a session key is preserved even if some 164 secret keys are leaked because of resource restriction and 165 installation environment of devices. 167 2. Requirements Terminology 169 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 170 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 171 memo are to be interpreted as described in [1]. 173 3. Notation 175 This section shows notation used in this memo. 177 Let F_q be a finite field with q = p^n elements for a prime p and an 178 integer n and let E(F_q) be an elliptic curve with an order r and an 179 embedding degree k defined over F_q. An embedding degree k is 180 defined as a minimum integer k such that r is a divisor of q^k - 1. 182 Let G_1 (resp. G_2) be an additive group with an order r generated 183 by E(F_q) (resp. E'(F_q)). Let G_T be multiplicative groups with 184 the same order r. Let P_1, P_2 be generators of G_1, G_2 185 respectively. We say that (G_1, G_2, G_T) are bilinear map groups if 186 there exists a pairing e: (G_1, G_2) -> G_T satisfying the following 187 properties: 189 1. Bilinearity: for any Q_1 in G_1, for any Q_2 in G_2, for any a, b 190 in Z_r, we have the relation e(aQ_1, bQ_2) = e(Q_1,Q_2)^{ab}. 192 2. Non-degeneracy: for any Q_1 in G_1, e(Q_1,Q_2) = 1 only if Q_2 = 193 O_{G_2} and for any Q_2 in G_2, e(Q_1,Q_2) = 1 only if Q_1 = 194 O_{G_1}. 196 3. Computability: for any Q_1 in G_1, for any Q_2 in G_2, the 197 bilinear map is efficiently computable. 199 This pairing is described in specification of optimal ate pairing 200 specification[3]. It is defined by Pairing-Parm-ID following way. 202 Pairing-Param-ID = { 203 G1-Curve-ID, 204 G2-Curve-ID 205 GT-Field-ID 206 } 208 G1-Curve-ID and G2-Curve-ID is an identifiers of elliptic curve. And 209 GT-Field-ID is an identifier of the G_T range of finite field. G1- 210 Curve-ID , G2-Curve-ID and GT-Field-ID are described in [2] the 211 following way. 213 G1-Curve-ID = { 214 p_b : A prime specifying base field F_p. 215 A, B : The coefficients of the equation y^2 = x^3 A * x + B 216 defining E. 217 G = (x, y) : The base point, i.e., a point with x and y 218 being its x- and y-coordinates in E, respectively. 219 r : The prime order of the group generated by G. 220 h : The cofactor of G in E. 221 } 222 G2-Curve-ID = { 223 p_b : A prime specifying base field F_p. 224 e2 : The constant of an irreducible polynomial specifying 225 extension field F_{p^2} = Fp[u] / (u^2 - e2). 226 A', B' : The coefficients of the equation y^2 = x^3 A' * x + 227 B' defining E'. 228 G' = (x', y') : The base point, i.e., a point with x' and y' 229 being its x- and y-coordinates in E', respectively. 230 r' : The prime order of the group generated by G'. 231 h' : The cofactor of G' in E'. 232 } 234 GT-Filed-ID = { 235 p_b : A prime specifying base field. 236 r : The prime order of the subgroup of F_{p^12}. 237 e2 : The constant of the irreducible polynomial of F_{p^2} = 238 F_p [u] / (u^2 - e2). 239 e6 : The constant of the irreducible polynomial of F_{p^6} = 240 F_{p^2}[v] / (v^3 - e6). 241 e12 : The constant of the irreducible polynomial of F_{p^12} 242 = F_{p^6}[w] / (w^2 - e12). 243 h'' : The cofactor of G_T 244 } 246 In addition, this memo uses the following functions. 248 floor(x) : The function returning an integer such that max{x' in Z | 249 x' <= x}. 251 ceil(x) : The function returning an integer such that min{x' in Z | 252 x' >= x}. 254 O_E : The point at infinity over elliptic curve E. 256 4. Data Type and Its Conversions 258 This section describes data type and its conversion used in this 259 memo. 261 4.1. BitString-to-OctetString Conversion (BS2OSP) 263 This memo uses conversion from bit strings to octet strings. 264 Informally, the idea is to pad the bit string with 0's on the left to 265 make its length a multiple of 8, then chop the result up into octets. 266 Formally, the conversion routine, BS2OSP(B), is specified in 267 Appendix A.1 269 4.2. OctetString-to-BitString Conversion (OS2BSP) 271 This memo uses conversion from octet strings to bit strings. 272 Informally, the idea is simply to view the octet string as a bit 273 string. Formally, the conversion routine, OS2BSP(M), is specified in 274 Appendix A.2 276 4.3. FieldElement-to-Integer Conversion (FE2IP) 278 This memo uses conversion from field elements to integers. An finite 279 field element should be represented as a polynomial with subfield 280 coefficients, which can be represented as a sequence of the 281 coefficients. Informally, the idea is simply to view the sequence of 282 the coefficients as the radix-p^m representation of the base field 283 elements, where p^m is the number of the subfield elements. 284 Formally, the conversion routine, FE2IP(a), is specified in 285 Appendix A.3 287 4.4. Integer-to-FieldElement Conversion (I2FEP) 289 This memo uses conversion from integers to field elements. A field 290 element should be represented as a polynomial with subfield 291 coefficients, and it can be represented as a sequence of the 292 coefficients. Informally, the idea is to represent the integer with 293 radix-p^m positional number system where p^m is the number of the 294 subfield element, and then convert the each digit to the each 295 coefficient of the polynomial. Formally, the conversion routine, 296 I2FEP(x), is specified in Appendix A.4: 298 4.5. FieldElement-to-OctetString Conversion (FE2OSP) 300 This memo uses conversion from field elements to octet strings. This 301 conversion is constructed by using FE2IP and I2SOP conversions. 302 Formally, the conversion routine, FE2OSP(a), is specified in 303 Appendix A.5. 305 4.6. OctetString-to-FieldElement Conversion (OS2FEP) 307 This memo uses conversion from octet strings to field elements. This 308 conversion is constructed by using OS2IP and I2FEP conversions. 309 Formally, the conversion routine, OS2FEP(M), is specified in 310 Appendix A.6. 312 4.7. EllipticCurvePoint-to-OctetString Conversion (ECP2OSP) 314 This memo uses conversion from elliptic curve points to octet 315 strings. Informally the idea is that, if point compression is being 316 used, the compressed y-coordinate is placed in the leftmost octet of 317 the octet string along with an indication that point compression is 318 on, and the x-coordinate is placed in the remainder of the octet 319 string; otherwise if point compression is off, the leftmost octet 320 indicates that point compression is off, and remainder of the octet 321 string contains the x-coordinate followed by the y-coordinate. 322 Formally, the conversion routine, ECP2OSP(P,R), is specified in 323 Appendix A.7. 325 4.8. OctetString-to-EllipticCurvePoint Conversion (OS2ECPP) 327 This memo uses conversion from octet strings to elliptic curve 328 points. Informally, the idea is that, if the octet string represents 329 a compressed point, the compressed y-coordinate is recovered from the 330 leftmost octet, the x-coordinate is recovered from the remainder of 331 the octet string, and then the point compression process is reversed; 332 otherwise the leftmost octet of the octet string is removed, the 333 x-coordinate is recovered from the left half of the remaining octet 334 string, and the y-coordinate is recovered from the right half of the 335 remaining octet string. Formally, the conversion routine, 336 OS2ECPP(M), is specified in Appendix A.8. 338 5. Building Block of FSU Key Exchange 340 This section describes building block for constructing FSU Key 341 Exchange. 343 5.1. Key Derivation Function 345 MGF1 is a mask generation function, parameterized by a hash function. 346 MGF1(M,n) is defined as follows: 348 System parameters: 350 o Hash : a hash function 352 o hashLen : the length in octets of the hash function output 353 Input: 355 o M : a seed from which a mask is generated, an octet string 357 o n : the octet length of the output, a positive integer 359 Output: 361 o mask : a mask, an octet string of length n 363 Method: 365 1. Let n_0 be the octet length of M. If n_0 + 4 is greater than 366 the input limitation for the hash function, output INVALID and 367 stop. 369 2. Set cThreshold = ceil(n / hashLen) 371 3. If cThreshold > 2^32, output INVALID and stop 373 4. Let M' be the empty octet string 375 5. Set counter = 0 377 6. B = B_{0}, ..., B{31} such that counter = B_{31} + B_{30}*2 + 378 ... + B_{0}*2^{31} 380 7. Compute C = BS2OSP(B) 382 8. Compute H = Hash(M||C) 384 9. Set M' = M'||H 386 10. Set counter = counter + 1 388 11. If counter < cThreshold, go back to step 6. 390 12. Set mask = M'_0M'_1...M'_{n-1} where M' = M'_0M'_1M'_2... 392 13. Output mask 394 5.2. Hashing to Point 396 Hashed value should be converted to elliptic curve point as described 397 in this section. Formally, the conversion routine, 398 HASHINGTOPOINT(Curve-ID, Hash, M), is specified as follows: 400 Input: 402 o Curve-ID : an elliptic curve parameter 404 o Hash : a hash function 406 o M : an octet string 408 Output: 410 o P : an elliptic curve point 412 Method: 414 1. Set i = 0 416 2. B = B_{0}, ..., B{15} such that counter = B_{15} + B_{14}*2 + 417 ... + B_{0}*2^{15} 419 3. Compute C = BS2OSP(B) 421 4. x_0 = OS2FQE(C||M, Hash, F_{p^m}) in F_{p^m} 423 5. t = x_0^3 + A * x_0 + B 425 6. If t=0, set P =(x_0, 0) and output h'*P 427 7. If t is not square in F_{p^m}, set i = i + 1 and go back to step 428 2 430 8. Set alpha be one of square roots of t. Then, -alpha is another 431 square root of t. 433 9. Set y_1 = FE2IP(alpha) 435 10. Set y_2 = FE2IP(-alpha) 437 11. If y_1 > y_2, set y_0 = -alpha 439 12. Else (i.e. y_1 <= y_2), set y_0 = alpha 441 13. Set P = (x_0, y_0) 443 14. Output h * P 445 5.2.1. IHF1 447 Bit string should be converted to hashed non-negative integer less 448 than an assigned integer as described in this section. Formally, the 449 conversion routine, IHF1(s,n,Hash) is defined as follows: 451 Input: 453 o s: an octet string 455 o n : an integer 457 o Hash : a hash function 459 Output: 461 o v in Z_n 463 Method: 465 1. Set hashLen be the length of the output of the hash function 466 Hash 468 2. Set h_0 be the zero string of length hashLen 470 3. h_1 = Hash(h_0 || s) 472 4. B = B_0,...,B_{l-1} = OS2BSP(h_1) 474 5. a_1 = sum_{i = 0}^{l-1} 2^{l-1-i} * B_{i} 476 6. h_2 = Hash(h_1 || s) 478 7. B = B_0,...,B_{l-1} = OS2BSP(h_2) 480 8. a_2 = sum_{i=0}^{l-1} 2^{l-1-i} * B_{i} 482 9. v = 2^{hashLen} * a_1 + a_2 mod n 484 10. Output v 486 5.2.2. OS2FQE 488 Octet string should be converted to hashed finite field element as 489 described in this section. Formally, the conversion routine, 490 OS2FQE(s,Hash,F_{p^m}) is defined as follows: 492 Input: 494 o s: an octet string 496 o Hash : a hash function 497 o F_{p^m} : a finite field with p^m elements where p is a prime, and 498 m > 0 is an integer 500 Output: 502 o a: an element in F_{p^m} 504 Method: 506 1. Set i = 0 508 2. B = B_{0}, ..., B{31} such that counter = B_{31} + B_{30}*2 + ... 509 + B_{0}*2^{31} 511 3. Compute C = BS2OSP(B) 513 4. Compute t_i = IHF1(C||s,p,Hash) 515 5. If i < m, set i = i + 1 and go back to step2 517 6. Compute a = sum_{i=0}^{m-1} t_i * beta^i where beta is the 518 variable of the polynomial 520 7. Output a 522 5.3. Group Membership Test Function 524 GROUPMEMBERSHIPTEST(Curve-ID, P) is a test function that an elliptic 525 curve point is on the correct curve and group. GROUPMEMBERSHIPTEST 526 is defined as follows: 528 Input: 530 o Curve-ID : an elliptic curve identifier 532 o P = (x,y) : an elliptic curve point 534 Output: 536 o boolean : an integer in {0,1} 538 Method: 540 1. If P = O_E, then output 1 542 2. If y^2 != x^3 + A * x + B, then output 0 544 3. If h != 1 && r * P != O_E, then output 0 545 4. Output 1 547 6. FSU Key Exchange 549 This section provides the specification of ID-based authenticated key 550 exchange protocol FSU [4] that is an extension of FSU (Fujioka- 551 Suzuki-Ustaoglu) protocol standardized in ISO/IEC11770-3 [5] [6]. 553 6.1. System Parameter Setup 555 Key Generation Center (KGC) defines the following system parameters 556 in FSU: 558 o Pairing-Param-ID : An identifier for showing asymmetric pairing. 559 i.e., G1-Curve-ID, G2-Curve-ID and GT-Filed-ID. 561 o G1-Curve-ID is an identifier for showing an elliptic curve which 562 defines cyclic groups G_1 with prime p_b_1, coefficients A_1 and 563 B_1, generator P_1, order r, and cofactor h_1. 565 o G2-Curve-ID is an identifier for showing an elliptic curve which 566 defines cyclic groups G_2 with prime p_b_2, irreducible polynomial 567 e2_2, coefficients A_2 and B_2, generator P_2, order r, and 568 cofactor h_2. 570 o GT-Field-ID is an identifier for showing a pairing co-domain group 571 which is subgroup of order r in G_{phi_12(p)}. G_{phi_12(p)} is 572 the 12-th cyclotomic subgroup of order p^4-p^2+1 in F_{p^12}^*. 574 o HASH-ID : An identifier for showing a hash function i,e., Hash : 575 {0,1}^* -> {0,1}^hashLen. 577 o hashLen : Length of output by Hash. 579 o KDF-ID : An identifier for showing key derivation function, i.e., 580 MGF1: {0,1}^* -> {0,1}^n. 582 o n : Length of output by key derivation function. 584 o R : A point compression type of conversion between elliptic curve 585 point and octet string specifically "Compressed", "Uncompressed", 586 or "Hybrid". 588 KGC generates the master secret key MSK and master public key MPK 589 from system parameters as following. 591 1. KGC selects a random integer z in Z_r. 593 2. KGC computes Z_v = z * P_v for v is in {1, 2}. 595 3. KGC sets MSK = z and MPK = (Z_1, Z_2). 597 Hash function H_v are defined as H_v(M) = HASHINGTOPOINT(Gv-Curve-ID, 598 Hash, "FSU"||ECP2OSP(Z_1, R)||ECP2OSP(Z_2, R)||M) for v in {1, 2}. 599 Hash function H is defined as H(M) = MGF1("FSU"||ECP2OSP(Z_1, 600 R)||ECP2OSP(Z_2, R)||M, n). 602 6.2. Key Distribution by KGC 604 This subsection explains operations of key distribution by KGC. 605 There are two types of static secret key in FSU Key Exchange, 606 respectively static secret key based on cyclic groups in G_1 and in 607 G_2. FSU Key Exchange requires that an initiator and a responder use 608 static secret key with different types, respectively. Hence, KCG 609 needs to define a rule for key distribution for users. For example, 610 clients use static secret keys in G_1 and servers use them in G_2. 612 KGC generates static secret key D_{i, v} for an identifier ID_i for i 613 in {A, B} of user in G_v as following. 615 1. Let MPK be (Z_1, Z_2) and MSK be z. 617 2. KGC Compute D_{i ,v} = z*H_v(ID_i). 619 3. Distribute D_{i ,v} to a user with ID_i. 621 6.3. FSU Key Exchange Protocol 623 This subsection describes FSU Key Exchange Protocol in an initiator 624 U_A with an identifier ID_A and static secret key D_{A,1} and a 625 responder U_B with an identifier ID_B and static secret key D_{B,2}. 627 Computation of ephemeral public key by U_A 629 1. U_A selects a random integer x_A in Z_r. 631 2. U_A computes the ephemeral public key X_{A,v} = x_A * P_v for v 632 in {1,2}. 634 3. U_A computes XOS_{A,v} = ECP2OSP(X_{A,v}, R) for v in {1,2}. 636 4. U_A sends (ID_A, ID_B, XOS_{A,1}, XOS_{A,2}) to U_B. 638 Computation of ephemeral public key by U_B 640 1. U_B receives (ID_A, ID_B, XOS_{A,1}, XOS_{A,2}). 642 2. U_B computes X_{A,v} = OS2ECPP(XOS_{A,v}) for v in {1,2}. 644 3. If (GROUPMEMBERSHIPTEST(G1-Curve-ID, X_{A,1}) = 0 || 645 GROUPMEMBERSHIPTEST(G2-Curve-ID, X_{A,2}) = 0 || e(X_{A,1}, P_2) 646 != e(P_1, X_{A,2})), then abort. 648 4. U_B selects a random ephemeral secret key x_B in Z_r. 650 5. U_B computes the ephemeral public key X_{B,v} = x_B * P_v for v 651 in {1,2}. 653 6. U_B computes XOS_{B,v} = ECP2OSP(X_{B,v}, R) for v in {1,2}. 655 7. U_B sends (ID_B, ID_A, XOS_{B,1}, XOS_{B,2}) to U_A. 657 Computation of session key by U_B 659 1. U_B computes sigma_1 = e(H_1(ID_A), D_{B,2}). 661 2. U_B computes sigma_2 = e(H_1(ID_A) + X_{A,1}, D_{B,2} + x_B * 662 Z_2). 664 3. U_B computes sigma_3 = x_B * X_{A,1}. 666 4. U_B computes sigma_4 = x_B * X_{A,2}. 668 5. U_B computes sigmaOS_j = FE2OSP(sigma_j) for j in {1,2}. 670 6. U_B computes sigmaOS_j' = ECP2OSP(simga_j',R) for j' in {3,4}. 672 7. Set sid = 673 (ID_A||ID_B||XOS_{A,1}||XOS_{A,2}||XOS_{B,1}||XOS_{B,2}). 675 8. U_B computes session key K = 676 H(sigmaOS_1||sigmaOS_2||sigmaOS_3||sigmaOS_4||sid). 678 Computation of session key by U_A 680 1. U_A computes X_{B,v} = OS2ECPP(XOS_{B,v}) for v in {1,2}. 682 2. If (GROUPMEMBERSHIPTEST(G1-Curve-ID, X_{B,1}) = 0 || 683 GROUPMEMBERSHIPTEST(G2-Curve-ID, X_{B, 2}) = 0 || e(X_{B,1}, 684 P_2) != e(P_1, X_{B,2})), then abort. 686 3. U_A computes sigma_1 = e(D_{A,1}, H_2(ID_B)). 688 4. U_A computes sigma_2 = e(D_{A,1} + x_A * Z_1, H_2(ID_B) + 689 X_{B,2}). 691 5. U_A computes sigma_3 = x_A * X_{B,1}. 693 6. U_A computes sigma_4 = x_A * X_{B,2}. 695 7. U_A computes sigmaOS_j = FE2OSP(sigma_j) for j in {1,2}. 697 8. U_A computes sigmaOS_j' = ECP2OSP(simga_j',R) for j' in {3,4}. 699 9. Set sid = 700 (ID_A||ID_B||XOS_{A,1}||XOS_{A,2}||XOS_{B,1}||XOS_{B,2}). 702 10. U_A compute session key K = 703 H(sigmaOS_1||sigmaOS_2||sigmaOS_3||sigmaOS_4||sid). 705 7. Security Considerations 707 This memo specifies identity-based authenticated key exchange 708 protocol FSU [4] [6] [5] which is secure in the id-eCK(id-based 709 extended Canetti-Krawczyk) security model under the GBDH(gap bilinear 710 DH) assumption [4]. 712 id-eCK security model is the most strong security model in the 713 meaning of that it ensures the safety of session key if any non- 714 trivial combinations of master key, static key, and ephemeral key are 715 leaked. 717 And id-eCK security model guarantees following 4 security notions: 719 MitM(resistance to man in the middle attacks), 721 wPFS(weak perfect forward security), 723 KCI(resistance to key compromise impersonation attacks), 725 RLE(resilience to leakage of ephemeral private keys). 727 8. Acknowledgements 729 TBD 731 9. Algorithm Identifiers 733 TBD 735 10. Change log 737 NOTE TO RFC EDITOR: Please remove this section in before final RFC 738 publication. 740 11. Test Vectors 742 TBD 744 12. References 746 12.1. Normative References 748 [1] Bradner, S., "Key words for use in RFCs to Indicate 749 Requirement Levels", RFC 2119, March 1997. 751 [2] Kasamatsu, K., Kanno, S., Kato, A., Scott, M., Kobayashi, 752 T., and Y. Kawahara, "Barreto-Naehrig Curves", draft- 753 kasamatsu-bncurves-02 (work in progress), 2015. 755 [3] Kato, A., Scott, M., Kobayashi, T., and Y. Kawahara, 756 "Barreto-Naehrig Curves", draft-kato-optimal-ate- 757 pairings-01 (work in progress), 2015. 759 12.2. Informative References 761 [4] Fujioka, A., Hoshino, F., Kobayashi, T., Suzuki, K., 762 Ustaglu, B., and K. Yoneyama, "id-eCK Secure ID-Based 763 Authenticated Key Exchange on Symmetric and Asymmetric 764 Pairing", Proceedings IEICE Transactions 96-A(6): 765 1139-1155, 2013. 767 [5] Fujioka, A., Suzuki, K., and B. Ustaglu, "Ephemeral Key 768 Leakage Resilient and Efficient ID-AKEs That Can Share 769 Identities, Private and Master Keys", Proceedings Pairing 770 2010 Lecture Notes in Computer Science Volume 6487, pp 771 187-205, 2010. 773 [6] "Information technology -- Security techniques -- Key 774 management -- Part 3: Mechanisms using asymmetric 775 techniques.", ISO/IEC 11770-3: 2015, 2015. 777 [7] Shamir, A., "Identity-based Cryptosystems and Signature 778 Schemes", Proceedings CRYPTO '84, LNCS 196, pages 47-53, 779 Springer-Verlag, 1984. 781 [8] Boneh, D. and M. Franklin, "Identity-Based Encryption from 782 the Weil Pairing", Proceedings CRYPTO 2001, LNCS 2139, 783 pages 213-229, Springer-Verlag, 2001. 785 [9] Huang, H. and Z. Cao, "An ID-based Authenticated Key 786 Exchange Protocol Based on Bilinear Diffie-Hellman 787 Problem", Proceedings the 4th International Symposium on 788 Information, Computer, and Communications Security 789 (ASIACCS '09) pp. 333-342, ACM, 2009. 791 [10] Canetti, R. and H. Krawczyk, "Analysis of Key-Exchange 792 Protocols and Their Use for Building Secure Channels", 793 Proceedings Eurocrypt 2001 (LNCS2015), pp. 453-474, 794 Springer-Verlag, 2001. 796 [11] LaMacchia, B., Lauter, K., and A. Mityagin, "Stronger 797 Security of Authenticated Key Exchange", Proceedings in 798 Provable Security (LNCS 4784), pp. 1-16, Springer, 2007. 800 Appendix A. Construction of Data Conversion 802 A.1. Construction of BS2OSP 804 Concrete construction of BS2OSP(B) is specified as follows: 806 Input: 808 o B = B_0 B_1 ... B_{l-1} : a bit string of length l 810 Output: 812 o M = M_0 M_1 ... M_{n-1}: an octet string of length n = ceil(l/8). 814 Method: 816 1. If l = 0, then output empty octet string and stop. 818 2. For j in {0,...,8n-1}, if j >= 8n - l, set B'_j = B_{j-(8n-l)}, 819 otherwise set B'_j = 0. 821 3. For i in {0,...,n-1}, set M_i = B'_{8i} B'_{8i+1}...B'_{8i+7}. 823 4. Output M = M_0 M_1 ... M_{n-1}. 825 A.2. Construction of OS2BSP 827 Concrete construction of OS2BSP(M) is specified as follows: 829 Input: 831 o M = M_0M_1...M{n-1}: an octet string of length n. 833 Output: 835 o B = B_0B_1...B_{l-1} : a bit string of lenth l = 8*n 837 Method: 839 1. If l = 0, then output empty octet string and stop. 841 2. For i in {0, ..., n-1} , j in {0,...,7}, set B_{8i + j} in {0,1} 842 as M_i = B_{8i} B_{8i+1}...B_{8i+7}. 844 3. Output B = B_0 B_1 ... B_{l-1}. 846 A.3. Construction of FE2IP 848 Concrete construction of FE2IP(a) is specified as follows: 850 System parameters: 852 o F_{p^{m_2}}/F_{p^{m_1}}: a field extension with an irreducible 853 polynomial Irr(F_{p^m_2} / F_{p^m_1};beta) 855 Input: 857 o a : a field element in F_{p^m_2} 859 Output: 861 o x : an integer in {0,...,p^{m_2} - 1} 863 Method: 865 1. If m_2 = 1 (i.e. F_{p^m_2} is prime field) 867 A field element of F_{p^{m_2}} must be represented an an 868 integer in {0, ..., p-1} 870 (A) Set x = a 872 (B) Output x 874 2. Else (i.e. m_2 > 1) 876 (A) Let the coefficients a_i in F_{p^m_1} for i in {0,...,m_2 877 / m_1 - 1} such that a = sum_{i=0}^{m_2 / m_1 - 1} a_i * 878 beta^i 880 (B) Compute x = sum_{i=0}^{m_2 / m_1 - 1} FE2IP(a_i) * 881 (p^{m_1})^i 883 (C) Output x 885 A.4. Construction of I2FEP 887 Concrete construction of I2FEP(x) is specified as follows: 889 System parameters: 891 o F_{p^{m_2}}/F_{p^{m_1}}: a field extension with an irreducible 892 polynomial Irr(F_{p^m_2} / F_{p^m_1};beta) 894 Input: 896 o x : an integer in {0,...,p^{m_2} - 1} 898 Output: 900 o a : a field element in F_{p^m_2} 902 Method: 904 1. If m_2 = 1 (i.e. F_{p^m_2} is prime field) 906 A field element of F_{p^{m_2}} must be represented an an 907 integer in {0, ..., p-1} 909 (A) Set a = x 911 (B) Output a 913 2. Else (i.e. m_2 > 1) 915 (A) Let x_i be an element in {0,...,p^{m_1}-1} for i in 916 {0,...,m_2 / m_1 - 1} such that x = sum_{i=0}^{m_2 / m_1 -1} 917 x_i * p^{m_1}^i 919 (B) Compute a = sum_{i=0}^{m_2 / m_1 - 1} I2FEP(x_i) * beta^i 921 (C) Output a 923 A.5. Construction of FE2OSP 925 System parameter: 927 o F_{p^m} : a finite field with p^m elements where p is a prime, and 928 m > 0 is an integer 930 o n : an integer equivalent to ceil(m * log_2 p / 8) 932 Input: 934 o a : a field element in F_{p^m} 936 Output: 938 o M : an octet string 940 Method: 942 1. Compute I = FE2IP(a) 944 2. Compute X = x_{0}, ..., X_{n-1} such that I = x_{n-1} + x_{n-2}*2 945 + ... + x_{1}*2^{n-2} + x_{0}*2^{n-1} 947 3. Compute M = BS2OSP(X) 949 4. Output M 951 A.6. Construction of OS2FEP 953 System parameter: 955 o F_{p^m} : a finite field with p^m elements where p is a prime, and 956 m > 0 is an integer 958 o n : an integer equivalent to ceil(m * log_2 p / 8) 960 Input: 962 o M : an octet string 964 Output: 966 o a : a field element in F_{p^m} 968 Method: 970 1. Compute X = OS2BSP(M) 972 2. Let X be x_0,...,x_{l-1} 974 3. Compute I = sum_{i=0}^{l-1} 2^{l-1-i} * x_{i} 976 4. Compute a = I2FEP(I) 978 5. Output a 980 A.7. Construction of ECP2OSP 982 Concrete construction of ECP2OSP(P,R), is specified as follows: 984 System parameters: 986 o Curve-ID : an elliptic curve parameter 988 Input: 990 o P : a point on an elliptic curve over F_{p^m} 992 o R : compression type specifically "Compressed", "Uncompressed", or 993 "Hybrid" 995 Output: 997 o M : an octet string of length n 999 Method: 1001 1. If P = O_E 1003 (A) Compute M = BS2OSP(00000000) 1005 (B) Output M 1007 2. If P = (x,y) != O_E && R = Compressed 1009 (A) Set X = FE2OSP(x) 1011 (B) If p is odd && y = 0 , set y' = 0 1013 (C) Else if p is odd && y != 0, set y' = y_i mod 2 such that y 1014 = y_{m-1} * beta^{m-1} + ... + y_1 * beta + y_0 and i is the 1015 smallest integer such that y_i != 0 1017 (D) If y' = 0, compute L = BS2OSP(00000100) 1019 (E) If y' = 1, compute L = BS2OSP(00000101) 1021 (F) Output M = L || X 1023 3. If P = (x,y) != O_E && R = Uncompressed 1025 (A) Set X = FE2OSP(x) 1027 (B) Set Y = FE2OSP(y) 1029 (C) Compute L = BS2OSP(00000100) 1031 (D) Output M = L || X || Y 1033 4. If P = (x,y) != O_E && R = Hybrid 1035 (A) Set X = FE2OSP(x) 1037 (B) Set Y = FE2OSP(y) 1038 (C) If y = 0, set y' = 0 1040 (D) Else (i.e. y != 0) y' = y_i mod 2 such that y = y_{m-1} * 1041 beta^{m-1} + ... + y_1 * beta + y_0 and i is the smallest 1042 integer such that y_i != 0 1044 (E) If y' = 0, compute L = BS2OSP(00000110) 1046 (F) If y' = 1, compute L = BS2OSP(00000111) 1048 (G) Output M = L || X || Y 1050 A.8. Construction of OS2ECPP 1052 Concrete construction of OS2ECPP(M), is specified as follows: 1054 System parameters 1056 o Curve-ID : an elliptic curve parameter 1058 Input: 1060 o M : an octet string 1062 Output: 1064 o P : an elliptic curve point 1066 Method: 1068 1. If M = BS2OSP(00000000), output P = O_E 1070 2. If M has length ceil(m * log_2 p / 8) + 1 1072 (A) Let M be L||X where L is a single octet 1074 (B) Compute x = OS2FEP(X) 1076 (C) If L = BS2OSP(00000010), then set y' = 0 1078 (D) Else if L = BS2OSP(00000011), then set y' = 1 1080 (E) Else output INVALID and stop 1082 (F) Compute w = x^3 + A * x + B 1084 (G) Compute gamma = square(w) 1085 (H) If there is no gamma in F_{p^m}, then output INVALID and 1086 stop 1088 (I) Else if gamma = 0, then set y = 0 1090 (J) Else if gamma_i = y' mod 2 where gamma = gamma_{m-1} * 1091 beta^{m-1} + ... + gamma_{1} * beta + gamma_{0} and i is the 1092 smallest integer such that gamma_i != 0 1094 (K) Else if gamma_i != y' mod 2, set y = -gamma where gamma = 1095 gamma_{m-1} * beta^{m-1} + ... + gamma_{1} * beta + gamma_{0} 1096 and i is the smallest integer such that gamma_i != 0 1098 (L) Output P = (x,y) 1100 3. If M has length 2 * floor(m * log_2 p / 8) + 1 1102 (A) Let M be L || X || Y where L is a single octet, X is 1103 floor(m * log_2 p / 8) octets, and Y is floor(m * log_2 p / 8) 1104 octets 1106 (B) Unless L is BS2OSP(00000100), BS2OSP(00000110) or 1107 BS2OSP(00000111), output INVALID and stop. 1109 (a) Compute x = OS2FEP(X) 1111 (b) Compute y = OS2FEP(Y) 1113 (c) If (x,y) does not satisfy the equation of elliptic 1114 curve, then output INVALID and stop 1116 (d) Output P = (x,y) 1118 Authors' Addresses 1120 Akihiro Kato 1121 NTT Software Corporation 1123 EMail: kato.akihiro-at-po.ntts.co.jp 1125 Thomas Hardjono 1126 MIT 1128 EMail: hardjono-at-mit.edu 1129 Tetsutaro Kobayashi 1130 NTT 1132 EMail: kobayashi.tetsutaro-at-lab.ntt.co.jp 1134 Tsunekazu Saito 1135 NTT 1137 EMail: saito.tsunekazu-at-lab.ntt.co.jp 1139 Koutarou Suzuki 1140 NTT 1142 EMail: suzuki.koutarou-at-lab.ntt.co.jp