idnits 2.17.1 draft-groves-sakke-03.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 : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (October 27, 2011) is 4565 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Informational ---------------------------------------------------------------------------- No issues found here. Summary: 0 errors (**), 0 flaws (~~), 1 warning (==), 2 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group Groves 3 Internet Draft CESG 4 Intended Status: Informational October 27, 2011 5 Expires: April 29, 2012 7 Sakai-Kasahara Key Establishment (SAKKE) 8 draft-groves-sakke-03 10 Status of this Memo 12 This Internet-Draft is submitted to IETF in full conformance with the 13 provisions of BCP 78 and BCP 79. 15 Internet-Drafts are working documents of the Internet Engineering 16 Task Force (IETF), its areas, and its working groups. Note that 17 other groups may also distribute working documents as Internet- 18 Drafts. 20 Internet-Drafts are draft documents valid for a maximum of six months 21 and may be updated, replaced, or obsoleted by other documents at any 22 time. It is inappropriate to use Internet-Drafts as reference 23 material or to cite them other than as "work in progress." 25 The list of current Internet-Drafts can be accessed at 26 http://www.ietf.org/ietf/1id-abstracts.txt. 28 The list of Internet-Draft Shadow Directories can be accessed at 29 http://www.ietf.org/shadow.html. 31 This Internet-Draft will expire on April 29, 2012. 33 Copyright Notice 35 Copyright (c) 2011 IETF Trust and the persons identified as the 36 document authors. All rights reserved. 38 This document is subject to BCP 78 and the IETF Trust's Legal 39 Provisions Relating to IETF Documents 40 (http://trustee.ietf.org/license-info) in effect on the date of 41 publication of this document. Please review these documents 42 carefully, as they describe your rights and restrictions with 43 respect to this document. Code Components extracted from this 44 document must include Simplified BSD License text as described in 45 Section 4.e of the Trust Legal Provisions and are provided without 46 warranty as described in the Simplified BSD License. 48 Abstract 50 In this document the Sakai-Kasahara Identifier-Based Encryption 51 algorithm (SAKKE) is described. This uses Identifier-Based 52 Encryption to exchange a shared secret from a Sender to a Receiver. 54 Table of Contents 56 1. Introduction.....................................................2 57 1.1. Requirements Terminology....................................3 58 2. Notation and Definitions.........................................3 59 2.1. Notation....................................................3 60 2.2. Definitions.................................................5 61 2.3. Parameters to be Defined or Negotiated......................6 62 3. Elliptic Curves and Pairings.....................................6 63 3.1. E(F_p^2) and the Distortion Map.............................7 64 3.2. The Tate-Lichtenbaum Pairing................................7 65 4. Representation of Values.........................................9 66 5. Supporting Algorithms............................................9 67 5.1. Hashing to an Integer Range.................................9 68 6. The SAKKE Cryptosystem..........................................10 69 6.1. Setup......................................................10 70 6.1.1. Secret Key Extraction.................................11 71 6.1.2. User Provisioning.....................................11 72 6.2. Key Exchange...............................................11 73 6.2.1. Sender................................................11 74 6.2.2. Receiver..............................................12 75 6.3. Group Communications.......................................12 76 7. Security Considerations.........................................13 77 8. IANA Considerations.............................................14 78 9. References......................................................14 79 9.1. Normative References.......................................14 80 9.2. Informative References.....................................15 81 Appendix A. Test Data..............................................15 83 1. Introduction 85 This document defines an efficient use of Identifier-Based Encryption 86 (IBE) based on bilinear pairings. The Sakai-Kasahara IBE 87 cryptosystem [S-K] is described for establishment of a shared secret 88 value. This document adds to the IBE options available in [RFC5091], 89 providing an efficient primitive and an additional family of curves. 91 This document is restricted to a particular family of curves (see 92 Section 2.1) which have the benefit of a simple and efficient method 93 of calculating the pairing on which the Sakai-Kasahara IBE 94 cryptosystem is based. 96 Identifier-Based Encryption schemes allow public and private keys to 97 be derived from Identifiers. In fact, the Identifier can itself be 98 viewed as corresponding to a public key or certificate in a 99 traditional public key system. However, in IBE, the Identifier can 100 be formed by both Sender and Receiver, which obviates the necessity 101 of providing public keys through a third party or of transmitting 102 certified public keys during each session establishment. 103 Furthermore, in an IBE system, calculation of keys can occur as 104 needed, and indeed, messages can be sent to users who are yet to 105 enrol. 107 The Sakai-Kasahara primitive described in this document supports 108 simplex transmission of messages from a Sender to a Receiver. The 109 choice of elliptic curve pairing on which the primitive is based 110 allows simple and efficient implementations. 112 The Sakai-Kasahara Key Establishment scheme described in this 113 document is drawn from the SK-KEM scheme (as modified to support 114 multi-party communications) submitted to the IEEE P1363 Working Group 115 in [SK-KEM]. 117 1.1. Requirements Terminology 119 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 120 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 121 document are to be interpreted as described in [RFC2119]. 123 2. Notation and Definitions 125 2.1. Notation 127 n A security parameter; the size of symmetric keys in bits to 128 be exchanged by SAKKE. 130 p A prime, which is the order of the finite field F_p. In 131 this document p is always congruent to 3 modulo 4. 133 F_p The finite field of order p. 135 F* The multiplicative group of the non-zero elements in the 136 field F; e.g., (F_p)* is the multiplicative group of the 137 finite field F_p. 139 q An odd prime that divides p + 1. To provide the desired 140 level of security, lg(q) MUST be greater than 2*n. 142 E An elliptic curve defined over F_p, having a subgroup of 143 order q. In this document we use supersingular curves with 144 equation y^2 = x^3 - 3 * x modulo p. This curve is chosen 145 because of the efficiency and simplicity advantages it 146 offers. The choice of -3 for the coefficient of x provides 147 advantages for elliptic curve arithmetic which are explained 148 in [P1363]. A further reason for this choice of curve is 149 that Barreto's trick [Barreto] of eliminating the 150 computation of the denominators when calculating the pairing 151 applies. 153 E(F) The additive group of points of affine coordinates (x,y) 154 with x, y in the field F, that satisfy the curve equation 155 for E. 157 P A point of E(F_p) that generates the cyclic subgroup of 158 order q. The coordinates of P are given by P = (P_x,P_y). 159 These coordinates are in F_p, and they satisfy the curve 160 equation. 162 0 The null element of any additive group of points on an 163 elliptic curve, also called the point at infinity. 165 F_p^2 The extension field of degree 2 of the field F_p. In this 166 document we use a particular instantiation of this field; 167 F_p^2 = F_p[i] where i^2 + 1 = 0. 169 PF_p The projectivisation of F_p. We define this to be 170 (F_p^2)*/(F_p)*. Note that PF_p is cyclic and has order p + 171 1, which is divisible by q. 173 G[q] The q-torsion of a group G. This is the subgroup generated 174 by points of order q in G. 176 < , > A version of the Tate-Lichtenbaum pairing. In this document 177 this is a bilinear map from E(F_p)[q] x E(F_p)[q] onto the 178 subgroup of order q in PF_p. A full definition is given in 179 Section 3.2. 181 Hash A cryptographic hash function. 183 lg(x) The base 2 logarithm of the real value x. 185 The following conventions are assumed for curve operations. 187 Point addition - If A and B are two points on a curve E, their sum 188 is denoted as A + B. 190 Scalar multiplication - If A is a point on a curve, and k an 191 integer, the result of adding A to itself a total of k times is 192 denoted [k]A. 194 We assume that the following concrete representations of mathematical 195 objects are used. 197 Elements of F_p - The p elements of F_p are represented directly 198 using the integers from 0 to p-1. 200 Elements of F_p^2 - The elements of F_p^2 = F_p[i] are represented 201 as x_1 + i * x_2, where x_1 and x_2 are elements of F_p. 203 Elements of PF_p - Elements of PF_p are cosets of (F_p)* in 204 (F_p^2)*. Every element of F_p^2 can be written unambiguously in 205 the form x_1 + i * x_2, where x_1 and x_2 are elements of F_p. 206 Thus elements of PF_p (except the unique element of order 2) can 207 be represented unambiguously by x_2 / x_1 in F_p. Since q is odd, 208 every element of PF_p[q] can be represented by an element of F_p 209 in this manner. 211 This representation of elements in PF_p[q] allows efficient 212 implementation of PF_p[q] group operations, as these can be defined 213 using arithmetic in F_p. If a and b are elements of F_p representing 214 elements A and B of PF_p[q] respectively, then A * B in PF_p[q] is 215 represented by (a + b)/(1 - a * b) in F_p. 217 2.2. Definitions 219 Identifier - Each user of an IBE system MUST have a unique, 220 unambiguous identifying string that can be easily derived by all 221 valid communicants. This string is the user's Identifier. An 222 Identifier is an integer in the range 2 to q-1. The method by which 223 Identifiers are formed MUST be defined for each application. 225 Key Management Server (KMS) - The Key Management Server is a trusted 226 3rd party for the IBE system. It derives system secrets and 227 distributes key material to those authorised to obtain it. 228 Applications MAY support the use mutual communication between the 229 users of multiple KMSs. We denote KMSs by KMS_T, KMS_S etc. 231 Public parameters - The public parameters are a set of parameters 232 that are held by all users of an IBE system. Such a system MAY 233 contain multiple KMSs. Each application of SAKKE MUST define the set 234 of public parameters to be used. The parameters needed are p, q, E, 235 P, g=, Hash and n. 237 Master Secret (z_T) - The Master Secret z_T is the master key 238 generated and privately kept by KMS_T and is used by KMS_T to 239 generate the private keys of the users that it provisions; it is an 240 integer in the range 2 to q-1. 242 KMS Public Key: Z_T = [z_T]P - The KMS Public Key Z_T is used to form 243 Public Key Establishment Keys for all users provisioned by KMS_T; it 244 is a point of order q in E(F_p). It MUST be provisioned by KMS_T to 245 all who are authorised to send messages to users of the IBE system. 247 Receiver Secret Key (RSK) - Each user enrolled in an IBE system is 248 provisioned with a Receiver Secret Key by its KMS. The RSK provided 249 to a user with Identifier a by KMS_T is denoted K_(a,T). In SAKKE, 250 the RSK is a point of order q in E(F_p). 252 Shared Secret Value - The aim of the SAKKE scheme is for the Sender 253 to securely transmit a Shared Secret Value to the Receiver. The 254 Shared Secret Value is an integer in the range 0 to (2^n) - 1; it is 255 denoted SSV. 257 Encapsulated Data - The Encapsulated Data are used to transmit secret 258 information securely to the Receiver. They can be computed directly 259 from the Receiver's Identifier, the public parameters, the KMS Public 260 Key, and the Shared Secret Value to be transmitted. In SAKKE the 261 Encapsulated Data are a point of order q in E(F_p) and an integer in 262 the range 0 to (2^n) - 1. They are formatted as described in Section 263 4. 265 2.3. Parameters to be Defined or Negotiated 267 In order for an application to make use of the SAKKE algorithm, the 268 communicating hosts MUST agree on values for several of the 269 parameters described above. The curve equation (E) and the pairing 270 (< , >) are constant and used for all applications. 272 For the following parameters, each application MUST either define an 273 application-specific constant value or define a mechanism for hosts 274 to negotiate a value: 276 * n 278 * p 280 * q 282 * P = (P_x,P_y) 284 * g = 286 * Hash 288 3. Elliptic Curves and Pairings 290 E is a supersingular elliptic curve (of j-invariant 1728). E(F_p) 291 contains a cyclic subgroup of order q, denoted E(F_p)[q], whereas the 292 larger object E(F_p^2) contains the direct product of two cyclic 293 subgroups of order q, denoted E(F_p^2)[q]. 295 P is a generator of E(F_p)[q]. It is specified by the (affine) 296 coordinates (P_x,P_y) in F_p, satisfying the curve equation. 298 Routines for point addition and doubling on E(F_p) can be found in 299 Appendix A.10 of [P1363]. 301 3.1. E(F_p^2) and the Distortion Map 303 If (Q_x,Q_y) are (affine) coordinates in F_p for some point (denoted 304 Q) on E(F_p)[q], then (-Q_x,iQ_y) are (affine) coordinates in F_p^2 305 for some point on E(F_p^2)[q]. This latter point is denoted [i]Q, by 306 analogy with the definition for scalar multiplication. The two 307 points P and [i]P together generate E(F_p^2)[q]. The map [i]: E(F_p) 308 -> E(F_p^2) is sometimes termed the distortion map. 310 3.2. The Tate-Lichtenbaum Pairing 312 We proceed to describe the pairing < , > to be used in SAKKE. We 313 will need to evaluate polynomials f_R that depend on points on 314 E(F_p)[q]. Miller's algorithm [Miller] provides a method for 315 evaluation of f_R(X), where X is some element of E(F_p^2)[q] and R is 316 some element of E(F_p)[q] and f_R is some polynomial over F_p whose 317 divisor is (q)(R) - (q)(0). Note that f_R is defined only up to 318 scalars of F_p. 320 The version of the Tate-Lichtenbaum pairing used in this document is 321 given by = f_R([i]Q)^c / (F_p)*. It satisfies the bilinear 322 relation <[x]R,Q> = = ^x for all Q, R in E(F_p)[q], for 323 all integers x. Note that the domain of definition is restricted to 324 E(F_p)[q] x E(F_p)[q] so that certain optimisations are natural. 326 We provide pseudocode for computing , with elliptic curve 327 arithmetic expressed in affine coordinates. We make use of Barreto's 328 trick [Barreto] for avoiding the calculation of denominators. Note 329 that this section does not fully describe the most efficient way of 330 computing the pairing; it is possible to compute the pairing without 331 any explicit reference to the extension field F_p^2. This reduces 332 the number and complexity of the operations needed to compute the 333 pairing. 335 337 /* 338 Copyright (c) 2011 IETF Trust and the persons identified as authors 339 of this code. All rights reserved. 341 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 342 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 343 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 344 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 345 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 346 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 347 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 348 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 349 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 350 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 351 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 352 */ 354 Routine for computing the pairing : 356 Input R, Q points on E(F_p)[q]; 358 Initialise variables: 359 v = (F_p)*; // An element of PF_p[q] 360 C = R; // An element of E(F_p)[q] 361 c = (p+1)/q; // An integer 363 for bits of q-1, starting with the second MSB, ending 364 with the LSB, do 366 // gradient of line through C, C, [-2]C. 367 l = 3*( C_x^2 - 1 ) / ( 2*C_y ); 369 //accumulate line evaluated at [i]Q into v 370 v = v^2 * ( l*( Q_x + C_x ) + ( i*Q_y - C_y ) ); 372 C = [2]C; 374 if bit is 1 then 376 // gradient of line through C, R, -C-R. 377 l = ( C_y - R_y )/( C_x - R_x ); 379 //accumulate line evaluated at [i]Q into v 380 v = v * ( l*( Q_x + C_x ) + ( i*Q_y - C_y ) ); 382 C = C+R; 384 end if; 385 end for; 387 t = v^c; 388 return representative in F_p of t; 390 End of routine; 392 Routine for computing representative in F_p of elements of PF_p: 394 Input t, in F_p^2, representing an element of PF_p; 396 Represent t as a + i*b, with a,b in F_p; 397 return b/a; 399 End of routine; 400 402 4. Representation of Values 404 This section provides canonical representations of values which MUST 405 be used to ensure interoperability of implementations. The following 406 representations MUST be used for input into hash functions and for 407 transmission. 409 Integers Integers MUST be represented as an octet string, 410 with bit length a multiple of 8. To achieve this, 411 the integer is represented most significant bit 412 first, and padded with zero bits on the left until 413 an octet string of the necessary length is 414 obtained. This is the Octet String representation 415 described in Section 6 of [RFC6090]. 417 F_p elements Elements of F_p MUST be represented as integers in 418 the range 0 to p-1 using the octet string 419 representation defined above. Such octet strings 420 MUST have length L = Ceiling(lg(p)/8). 422 PF_p elements Elements of PF_p MUST be represented as an element 423 of F_p using the algorithm in Section 3.2. They 424 are therefore represented as octet strings as 425 defined above and are L octets in length. 426 Representation of the unique element of order 2 in 427 PF_p will not be required. 429 Points on E Elliptic Curve Points MUST be represented in 430 Uncompressed representation as defined in Section 431 2.2 of [RFC5480]. For an elliptic curve point ( x 432 , y ) with x and y in F_p, this representation is 433 given by 0x04 || x' || y' , where x' is the octet 434 string representing x, y' is the octet string 435 representing y and || denotes concatenation. The 436 representation is 2*L+1 octets in length. 438 Encapsulated Data The Encapsulated Data MUST be represented as an 439 Elliptic Curve Point concatenated with an integer 440 in the range 0 to (2 ^ n) - 1. Since the length 441 of the representation of elements of F_p is well 442 defined given p, these data can be unambiguously 443 parsed to retrieve their components. The 444 Encapsulated Data is 2*L + n + 1 octets in 445 length. 447 5. Supporting Algorithms 449 5.1. Hashing to an Integer Range 451 We use the function HashToIntegerRange( s, n, hashfn) to hash strings 452 to an integer range. Given a string, s, a hash function, hashfn, and 453 an integer, n, this function returns a value between 0 and n - 1. 455 Input: 457 * an octet string, s 459 * an integer, n <= (2^hashlen)^hashlen 461 * a hash function, hashfn, with output length hashlen bits. 463 Output: 465 * an integer, v in the range 0 to n-1 467 Method: 469 1) Let A = hashfn( s ) 471 2) Let h_0 = 00...00, a string of null bits of length hashlen bits 473 3) Let l = Ceiling( lg( n ) / hashlen ) 475 4) For each i in 1 to l do: 477 a) Let h_i = hashfn(h_(i - 1)) 479 b) Let v_i = hashfn(h_i || A), where || denotes concatenation 481 5) Let v' = v_1 || ... || v_l 483 6) Let v = v' mod n 485 6. The SAKKE Cryptosystem 487 This chapter describes the Sakai-Kasahara Key Establishment 488 algorithm. It draws from the cryptosystem first described in [S-K]. 490 6.1. Setup 492 All users share a set of public parameters with a KMS. In most 493 circumstances it is expected that a system will only use a single 494 KMS. However, it is possible for users provisioned by different KMSs 495 to interoperate provided that they use a common set of public 496 parameters, and that they each possess the necessary KMS Public 497 Keys. In order to facilitate this interoperation, it is anticipated 498 that parameters will be published in application specific standards. 500 KMS_T chooses its KMS Master Secret, z_T. It MUST randomly select a 501 value in the range 2 to q-1, and assigns this value to z_T. It MUST 502 derive its KMS Public Key, Z_T, by performing the calculation Z_T = 503 [z_T]P. 505 6.1.1. Secret Key Extraction 507 The KMS derives each Receiver Secret Key from an Identifier and its 508 KMS Master Secret. It MUST derive a Receiver Secret Key for each 509 user that it provisions. 511 For Identifier 'a', the Receiver Secret Key K_(a,T) provided by KMS_T 512 MUST be derived by KMS_T as K_(a,T) = [(a + z_T)^-1]P, where 'a' is 513 interpreted as an integer, and the inversion is performed modulo q. 515 6.1.2. User Provisioning 517 The KMS MUST provide its KMS Public Key to all users through an 518 authenticated channel. Receiver Secret Keys MUST be supplied to all 519 users through a channel that provides confidentiality and mutual 520 authentication. The mechanisms that provide security for these 521 channels are beyond the scope of this document: they are application 522 specific. 524 Upon receipt of key material, each user MUST verify its Receiver 525 Secret Key. For Identifier 'a', Receiver Secret Keys from KMS_T are 526 verified by checking that the following equation holds: < [a]P + Z , 527 K_(a,T) > = g, where 'a' is interpreted as an integer. 529 6.2. Key Exchange 531 A Sender forms Encapsulated Data and sends it to the Receiver, who 532 processes it. The result is a shared secret which can be used as 533 keying material for securing further communications. We denote the 534 Sender "A", with Identifier a; we denote the Receiver "B", with 535 Identifier b; Identifiers are to be interpreted as integers in the 536 algorithms below. Let A be provisioned by KMS_T and B be provisioned 537 by KMS_S. 539 6.2.1. Sender 541 In order to form Encapsulated Data to send to device B who is 542 provisioned by KMS_S, A needs to hold Z_S. It is anticipated that 543 this will have been provided to A by KMS_T along with its User 544 Private Keys. The Sender MUST carry out the following steps. 546 1) Select a random ephemeral integer value for the Shared Secret 547 Value SSV in the range 0 to 2^n - 1. 549 2) Compute r = HashToIntegerRange( SSV || b , q , Hash ). 551 3) Compute R_(b,S) = [r]([b]P + Z_S) in E(F_p). 553 4) Compute the Hint, H. 555 a) Compute g^r. Note that g is an element of PF_p[q] 556 represented by an element of F_p. Thus, in order to 557 calculate g^r, the operation defined in Section 2.1 for 558 calculation of A * B in PF_p[q] is to be used as part of a 559 square and multiply (or similar) exponentiation algorithm, 560 rather than the regular F_p operations. 562 b) Compute H := SSV xor HashToIntegerRange( g^r, 2^n, Hash ). 564 5) Form the Encapsulated Data ( R_(b,S) , H ) and transmit it to 565 B. 567 6) Output SSV for use to derive key material for the application 568 to be keyed. 570 6.2.2. Receiver 572 Device B receives Encapsulated Data from device A. In order to 573 process this, it requires its Receiver Secret Key, K_(b,S), which 574 will have been provisioned in advance by KMS_S. The method by which 575 keys are provisioned by the KMS is application specific. The 576 Receiver MUST carry out the following steps to derive and verify the 577 Shared Secret Value. 579 1) Parse the Encapsulated Data ( R_(b,S) , H ) and extract R_(b,S) 580 and H. 582 2) Compute w := < R_(b,S) , K_(b,S) >. Note that by bilinearity w 583 = g^r. 585 3) Compute SSV = H xor HashToIntegerRange( w, 2^n, Hash ). 587 4) Compute r = HashToIntegerRange( SSV || b , q , Hash ). 589 5) Compute TEST = [r]([b]P + Z_S) in E(F_p). If TEST does not 590 equal R_(b,S) then B MUST NOT use the SSV to derive key 591 material. 593 6) Output SSV for use to derive key material for the application 594 to be keyed. 596 6.3. Group Communications 598 The SAKKE scheme can be used to exchange Shared Secret Values for 599 group communications. To provide a Shared Secret to multiple 600 Receivers, a Sender MUST form Encapsulated Data for each of their 601 Identifiers, and transmit the appropriate data to each Receiver. Any 602 party possessing the group Shared Secret Value MAY extend the group 603 by forming Encapsulated Data for a new group member. 605 Whilst the Sender needs to form multiple Encapsulated Data, the fact 606 that the sending operation avoids pairings means that the extension 607 to multiple Receivers can be carried out more efficiently than for 608 alternative IBE schemes which require the Sender to compute a 609 pairing. 611 7. Security Considerations 613 This document describes the SAKKE cryptographic algorithm. We assume 614 that the security provided by this algorithm depends entirely on the 615 secrecy of the secret keys it uses, and that for an adversary to 616 defeat this security, he will need to perform computationally 617 intensive cryptanalytic attacks to recover a secret key. Note that a 618 security proof exists for SAKKE in the Random Oracle Model [SK-KEM]. 620 When defining public parameters, guidance on parameter sizes from 621 [SP800-57] SHOULD be followed. Note that the size of the F_p^2 622 discrete logarithm on which the security rests is 2*lg(p). Table 1 623 shows bits of security afforded by various sizes of p. If k bits of 624 security are needed, then lg(q) SHOULD be chosen to be at least 2*k. 625 Similarly, if k bits of security are needed, then a Hash with output 626 size at least 2*k SHOULD be chosen. 628 Bits of Security | lg(p) 629 ------------------------- 630 80 | 512 631 112 | 1024 632 128 | 1536 633 192 | 3840 634 256 | 7680 636 Table 1: Comparable strengths, taken from Table 2 of [SP800-57] 638 The KMS Master Secret provides the security for each device 639 provisioned by the KMS. It MUST NOT be revealed to any other 640 entity. Each user's Receiver Secret Key protects the SAKKE 641 communications it receives. This key MUST NOT be revealed to any 642 other entity than the trusted KMS and the authorised user. 644 In order to ensure that the Receiver Secret Key is received only by 645 an authorised device, it MUST be provided through a secure channel. 646 The security offered by this system is no greater than the security 647 provided by this delivery channel. 649 Note that IBE systems have different properties than other asymmetric 650 cryptographic schemes with regards to key recovery. The KMS (and 651 hence any administrator with appropriate privileges) can create 652 Receiver Secret Keys for arbitrary Identifiers, and procedures to 653 monitor the creation of Receiver Secret Keys such as logging of 654 administrator actions SHOULD be defined by any functioning 655 implementation of SAKKE. 657 Identifiers MUST be defined unambiguously by each application of 658 SAKKE. Note that it is not necessary to hash the data in a format 659 for Identifiers (except in the case where its size would be greater 660 than that of q). In this way any weaknesses that might be caused by 661 collisions in hash functions can be avoided without reliance on the 662 structure of the Identifier format. Applications of SAKKE MAY 663 include a time/date component in their Identifier format to ensure 664 that Identifiers (and hence Receiver Secret Keys) are only valid for 665 a fixed period of time. 667 The randomness of values stipulated to be selected at random in SAKKE 668 described in this document is essential to the security provided by 669 SAKKE. If the ephemeral value r selected by the Sender is not chosen 670 at random then the SSV, which is used to provide key material for 671 further communications, could be predictable. Guidance on the 672 generation of random values for security can be found in [RFC4086]. 674 8. IANA Considerations 676 This document has no IANA actions. 678 9. References 680 9.1. Normative References 682 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 683 Requirement Levels", BCP 14, RFC 2119, March 1997. 685 [RFC5480] Turner, S., Brown, D., Yiu, K., Housley, R. and 686 T. Polk, "Elliptic Curve Cryptography Subject 687 Public Key Information", RFC 5480, March 2009. 689 [RFC6090] McGrew, D., Igoe, K. and M. Salter, "Fundamental 690 Elliptic Curve Cryptography Algorithms", RFC 6090, 691 February 2011. 693 [S-K] Sakai, R., Ohgishi, K. and M. Kasahara, "ID based 694 cryptosystem with pairing on elliptic curve", 695 Symposium on Cryptography and Information Security 696 - SCIS, 2003. 698 [SK-KEM] Barbosa, M., Chen, L., Cheng, Z., Chimley, M., 699 Dent, A., Farshim, P., Harrison, K., Malone-Lee, 700 J., Smart, N. and F. Vercauteren, "SK-KEM: An 701 Identity-Based KEM", submission for IEEE P1363.3, 702 June 2006. 703 (http://grouper.ieee.org/groups/1363/IBC/ 704 submissions/Barbosa-SK-KEM-2006-06.pdf) 706 [SP800-57] E. Barker, W. Barker, W. Burr, W. Polk and M. 707 Smid, "Recommendation for Key Management - Part 1: 708 General (Revised)," NIST Special Publication 709 800-57, March 2007. 711 9.2. Informative References 713 [Barreto] Barreto, P., Kim, H., Lynn, B. and M. Scott 714 "Efficient Algorithms for Pairing-Based 715 Cryptosystems", Advances in Cryptology - Crypto 716 2002, LNCS 2442, Springer-Verlag (2002), 717 pp.354-368. 719 [MIKEY-SAKKE] Groves, M., "MIKEY-SAKKE: Sakai-Kasahara Key 720 Exchange in Multimedia Internet KEYing (MIKEY)", 721 draft-groves-mikey-sakke-03 [work in progress], 722 October 2011. 724 [Miller] Miller, V., "The Weil pairing, and its efficient 725 calculation", J. Cryptology 17 (2004), 235-261. 727 [P1363] IEEE P1363-2000, "Standard Specifications for 728 Public-Key Cryptography," 2001. 730 [RFC4086] Eastlake, D., Schiller, J., and S. Crocker, 731 "Randomness Requirements for Security", BCP 106, 732 RFC 4086, June 2005. 734 [RFC5091] Boyen, X. and L. Martin, "Identity Based 735 Cryptography Standard (IBCS) #1: Supersingular 736 Curve Implementations of the BF and BB1 737 Cryptosystems", RFC 5091, December 2007. 739 Appendix A. Test Data 741 This appendix provides test data for SAKKE with the public parameters 742 defined in Appendix A of [MIKEY-SAKKE]. "b" represents the 743 Identifier of the Responder. The value "mask" is the value used to 744 mask the SSV, and is defined to be HashToIntegerRange( g^r, 2^n, Hash 745 ). 747 // -------------------------------------------------------- 748 // KMS generates: 750 z = AFF429D3 5F84B110 D094803B 3595A6E2 998BC99F 752 Zx = 5958EF1B 1679BF09 9B3A030D F255AA6A 753 23C1D8F1 43D4D23F 753E69BD 27A832F3 754 8CB4AD53 DDEF4260 B0FE8BB4 5C4C1FF5 755 10EFFE30 0367A37B 61F701D9 14AEF097 756 24825FA0 707D61A6 DFF4FBD7 273566CD 757 DE352A0B 04B7C16A 78309BE6 40697DE7 758 47613A5F C195E8B9 F328852A 579DB8F9 759 9B1D0034 479EA9C5 595F47C4 B2F54FF2 761 Zy = 1508D375 14DCF7A8 E143A605 8C09A6BF 762 2C9858CA 37C25806 5AE6BF75 32BC8B5B 763 63383866 E0753C5A C0E72709 F8445F2E 764 6178E065 857E0EDA 10F68206 B63505ED 765 87E534FB 2831FF95 7FB7DC61 9DAE6130 766 1EEACC2F DA3680EA 4999258A 833CEA8F 767 C67C6D19 487FB449 059F26CC 8AAB655A 768 B58B7CC7 96E24E9A 39409575 4F5F8BAE 770 // -------------------------------------------------------- 771 // Creating Encapsulated Data 773 b = 3230 31312D30 32007465 6C3A2B34 774 34373730 30393030 31323300 776 SSV = 12345678 9ABCDEF0 12345678 9ABCDEF0 778 r = HashToIntegerRange( 779 12345678 9ABCDEF0 12345678 9ABCDEF0 780 32303131 2D303200 74656C3A 2B343437 781 37303039 30303132 3300, q, SHA-256 ) 783 = 13EE3E1B 8DAC5DB1 68B1CEB3 2F0566A4 784 C273693F 78BAFFA2 A2EE6A68 6E6BD90F 785 8206CCAB 84E7F42E D39BD4FB 131012EC 786 CA2ECD21 19414560 C17CAB46 B956A80F 787 58A3302E B3E2C9A2 28FBA7ED 34D8ACA2 788 392DA1FF B0B17B23 20AE09AA EDFD0235 789 F6FE0EB6 5337A63F 9CC97728 B8E5AD04 790 60FADE14 4369AA5B 21662132 47712096 792 Rbx = 44E8AD44 AB8592A6 A5A3DDCA 5CF896C7 793 18043606 A01D650D EF37A01F 37C228C3 794 32FC3173 54E2C274 D4DAF8AD 001054C7 795 6CE57971 C6F4486D 57230432 61C506EB 796 F5BE438F 53DE04F0 67C776E0 DD3B71A6 797 29013328 3725A532 F21AF145 126DC1D7 798 77ECC27B E50835BD 28098B8A 73D9F801 799 D893793A 41FF5C49 B87E79F2 BE4D56CE 801 Rby = 557E134A D85BB1D4 B9CE4F8B E4B08A12 802 BABF55B1 D6F1D7A6 38019EA2 8E15AB1C 803 9F76375F DD1210D4 F4351B9A 009486B7 804 F3ED46C9 65DED2D8 0DADE4F3 8C6721D5 805 2C3AD103 A10EBD29 59248B4E F006836B 806 F097448E 6107C9ED EE9FB704 823DF199 807 F832C905 AE45F8A2 47A072D8 EF729EAB 808 C5E27574 B07739B3 4BE74A53 2F747B86 810 g^r = 7D2A8438 E6291C64 9B6579EB 3B79EAE9 811 48B1DE9E 5F7D1F40 70A08F8D B6B3C515 812 6F2201AF FBB5CB9D 82AA3EC0 D0398B89 813 ABC78A13 A760C0BF 3F77E63D 0DF3F1A3 814 41A41B88 11DF197F D6CD0F00 3125606F 815 4F109F40 0F7292A1 0D255E3C 0EBCCB42 816 53FB182C 68F09CF6 CD9C4A53 DA6C74AD 817 007AF36B 8BCA979D 5895E282 F483FCD6 819 mask = HashToIntegerRange( 820 7D2A8438 E6291C64 9B6579EB 3B79EAE9 821 48B1DE9E 5F7D1F40 70A08F8D B6B3C515 822 6F2201AF FBB5CB9D 82AA3EC0 D0398B89 823 ABC78A13 A760C0BF 3F77E63D 0DF3F1A3 824 41A41B88 11DF197F D6CD0F00 3125606F 825 4F109F40 0F7292A1 0D255E3C 0EBCCB42 826 53FB182C 68F09CF6 CD9C4A53 DA6C74AD 827 007AF36B 8BCA979D 5895E282 F483FCD6, 2^128, SHA-256 ) 829 = 9BD4EA1E 801D37E6 2AD2FAB0 D4F5BBF7 831 H = 89E0BC66 1AA1E916 38E6ACC8 4E496507 833 // -------------------------------------------------------- 834 // Receiver processing 836 // Device receives Kb from KMS 838 Kbx = 93AF67E5 007BA6E6 A80DA793 DA300FA4 839 B52D0A74 E25E6E7B 2B3D6EE9 D18A9B5C 840 5023597B D82D8062 D3401956 3BA1D25C 841 0DC56B7B 979D74AA 50F29FBF 11CC2C93 842 F5DFCA61 5E609279 F6175CEA DB00B58C 843 6BEE1E7A 2A47C4F0 C456F052 59A6FA94 844 A634A40D AE1DF593 D4FECF68 8D5FC678 845 BE7EFC6D F3D68353 25B83B2C 6E69036B 847 Kby = 155F0A27 241094B0 4BFB0BDF AC6C670A 848 65C325D3 9A069F03 659D44CA 27D3BE8D 849 F311172B 55416018 1CBE94A2 A783320C 850 ED590BC4 2644702C F371271E 496BF20F 851 588B78A1 BC01ECBB 6559934B DD2FB65D 852 2884318A 33D1A42A DF5E33CC 5800280B 853 28356497 F87135BA B9612A17 26042440 854 9AC15FEE 996B744C 33215123 5DECB0F5 856 // Device processes Encapsulated Data 858 w = 7D2A8438 E6291C64 9B6579EB 3B79EAE9 859 48B1DE9E 5F7D1F40 70A08F8D B6B3C515 860 6F2201AF FBB5CB9D 82AA3EC0 D0398B89 861 ABC78A13 A760C0BF 3F77E63D 0DF3F1A3 862 41A41B88 11DF197F D6CD0F00 3125606F 863 4F109F40 0F7292A1 0D255E3C 0EBCCB42 864 53FB182C 68F09CF6 CD9C4A53 DA6C74AD 865 007AF36B 8BCA979D 5895E282 F483FCD6 867 SSV = 12345678 9ABCDEF0 12345678 9ABCDEF0 869 r = 13EE3E1B 8DAC5DB1 68B1CEB3 2F0566A4 870 C273693F 78BAFFA2 A2EE6A68 6E6BD90F 871 8206CCAB 84E7F42E D39BD4FB 131012EC 872 CA2ECD21 19414560 C17CAB46 B956A80F 873 58A3302E B3E2C9A2 28FBA7ED 34D8ACA2 874 392DA1FF B0B17B23 20AE09AA EDFD0235 875 F6FE0EB6 5337A63F 9CC97728 B8E5AD04 876 60FADE14 4369AA5B 21662132 47712096 878 TESTx = 44E8AD44 AB8592A6 A5A3DDCA 5CF896C7 879 18043606 A01D650D EF37A01F 37C228C3 880 32FC3173 54E2C274 D4DAF8AD 001054C7 881 6CE57971 C6F4486D 57230432 61C506EB 882 F5BE438F 53DE04F0 67C776E0 DD3B71A6 883 29013328 3725A532 F21AF145 126DC1D7 884 77ECC27B E50835BD 28098B8A 73D9F801 885 D893793A 41FF5C49 B87E79F2 BE4D56CE 887 TESTy = 557E134A D85BB1D4 B9CE4F8B E4B08A12 888 BABF55B1 D6F1D7A6 38019EA2 8E15AB1C 889 9F76375F DD1210D4 F4351B9A 009486B7 890 F3ED46C9 65DED2D8 0DADE4F3 8C6721D5 891 2C3AD103 A10EBD29 59248B4E F006836B 892 F097448E 6107C9ED EE9FB704 823DF199 893 F832C905 AE45F8A2 47A072D8 EF729EAB 894 C5E27574 B07739B3 4BE74A53 2F747B86 896 TEST == Rb 898 // -------------------------------------------------------- 899 // HashToIntegerRange( M, q, SHA-256 ) Example 901 M = 12345678 9ABCDEF0 12345678 9ABCDEF0 902 32303131 2D303200 74656C3A 2B343437 903 37303039 30303132 3300 905 A = E04D4EF6 9DF86893 22B39AE3 80284617 906 4A93BEDB 1E3D2A2C 5F2C7EA0 05513EBA 907 h0 = 00000000 00000000 00000000 00000000 908 00000000 00000000 00000000 00000000 909 h1 = 66687AAD F862BD77 6C8FC18B 8E9F8E20 910 08971485 6EE233B3 902A591D 0D5F2925 911 h2 = 2B32DB6C 2C0A6235 FB1397E8 225EA85E 912 0F0E6E8C 7B126D00 16CCBDE0 E667151E 913 h3 = 12771355 E46CD47C 71ED1721 FD5319B3 914 83CCA3A1 F9FCE3AA 1C8CD3BD 37AF20D7 915 h4 = FE15C0D3 EBE314FA D720A08B 839A004C 916 2E6386F5 AECC19EC 74807D19 20CB6AEB 918 v1 = FA2656CA 1D2DBD79 015AE918 773DFEDC 919 24957C91 E3C9C335 40D6BF6D 7C3C0055 921 v2 = F016CD67 59620AD7 87669E3A DD887DF6 922 25895A91 0CEE1486 91A06735 B2F0A248 924 v3 = AC45C6F9 7F83BCE0 A2BBD0A1 4CF4D7F4 925 CB3590FB FAF93AE7 1C64E426 185710B5 927 v4 = E65D50BD 551A54EF 981F535E 072DE98D 928 2223ACAD 4621E026 3B0A61EA C56DB078 930 v mod q = 13EE3E1B 8DAC5DB1 68B1CEB3 2F0566A4 931 C273693F 78BAFFA2 A2EE6A68 6E6BD90F 932 8206CCAB 84E7F42E D39BD4FB 131012EC 933 CA2ECD21 19414560 C17CAB46 B956A80F 934 58A3302E B3E2C9A2 28FBA7ED 34D8ACA2 935 392DA1FF B0B17B23 20AE09AA EDFD0235 936 F6FE0EB6 5337A63F 9CC97728 B8E5AD04 937 60FADE14 4369AA5B 21662132 47712096 939 // -------------------------------------------------------- 941 Author's Address 943 Michael Groves 944 CESG 945 Hubble Road 946 Cheltenham 947 GL51 8HJ 948 UK 950 Email: Michael.Groves@cesg.gsi.gov.uk 952 Acknowledgement 953 Funding for the RFC Editor function is provided by the IETF 954 Administrative Support Activity (IASA).