idnits 2.17.1 draft-irtf-cfrg-dragonfly-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- -- The document has an IETF Trust Provisions (28 Dec 2009) Section 6.c(i) Publication Limitation clause. 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 12, 2012) is 4213 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- -- Obsolete informational reference (is this intentional?): RFC 5996 (Obsoleted by RFC 7296) Summary: 0 errors (**), 0 flaws (~~), 1 warning (==), 3 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Internet Research Task Force D. Harkins, Ed. 3 Internet-Draft Aruba Networks 4 Intended status: Informational October 12, 2012 5 Expires: April 15, 2013 7 Dragonfly Key Exchange 8 draft-irtf-cfrg-dragonfly-00 10 Abstract 12 This document specifies a key exchange using discrete logarithm 13 cryptogprahy that is authenticated using a password or passphrase. 14 It is resistant to active attack, passive attack, and off-line 15 dictionary attack. 17 Status of this Memo 19 This Internet-Draft is submitted in full conformance with the 20 provisions of BCP 78 and BCP 79. This document may not be modified, 21 and derivative works of it may not be created, except to format it 22 for publication as an RFC or to translate it into languages other 23 than English. 25 Internet-Drafts are working documents of the Internet Engineering 26 Task Force (IETF). Note that other groups may also distribute 27 working documents as Internet-Drafts. The list of current Internet- 28 Drafts is at http://datatracker.ietf.org/drafts/current/. 30 Internet-Drafts are draft documents valid for a maximum of six months 31 and may be updated, replaced, or obsoleted by other documents at any 32 time. It is inappropriate to use Internet-Drafts as reference 33 material or to cite them other than as "work in progress." 35 This Internet-Draft will expire on April 15, 2013. 37 Copyright Notice 39 Copyright (c) 2012 IETF Trust and the persons identified as the 40 document authors. All rights reserved. 42 This document is subject to BCP 78 and the IETF Trust's Legal 43 Provisions Relating to IETF Documents 44 (http://trustee.ietf.org/license-info) in effect on the date of 45 publication of this document. Please review these documents 46 carefully, as they describe your rights and restrictions with respect 47 to this document. Code Components extracted from this document must 48 include Simplified BSD License text as described in Section 4.e of 49 the Trust Legal Provisions and are provided without warranty as 50 described in the Simplified BSD License. 52 Table of Contents 54 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 55 1.1. Requirements Language . . . . . . . . . . . . . . . . . . 3 56 1.2. Definitions . . . . . . . . . . . . . . . . . . . . . . . 3 57 1.2.1. Notations . . . . . . . . . . . . . . . . . . . . . . 3 58 1.2.2. Resistance to Dictionary Attack . . . . . . . . . . . 4 59 2. Discete Logarithm Cryptography . . . . . . . . . . . . . . . . 4 60 2.1. Elliptic Curve Cryptography . . . . . . . . . . . . . . . 4 61 2.2. Finite Field Cryptography . . . . . . . . . . . . . . . . 6 62 3. The Dragonfly Key Exchange . . . . . . . . . . . . . . . . . . 6 63 3.1. Assumptions . . . . . . . . . . . . . . . . . . . . . . . 7 64 3.2. Derviation of the Password Element . . . . . . . . . . . . 8 65 3.2.1. Hunting and Pecking with ECC Groups . . . . . . . . . 9 66 3.2.2. Hunting and Pecking with MODP Groups . . . . . . . . . 10 67 3.3. The Commit Exchange . . . . . . . . . . . . . . . . . . . 11 68 3.4. The Confirm Exchange . . . . . . . . . . . . . . . . . . . 12 69 4. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 12 70 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 12 71 6. Security Considerations . . . . . . . . . . . . . . . . . . . 12 72 7. References . . . . . . . . . . . . . . . . . . . . . . . . . . 13 73 7.1. Normative References . . . . . . . . . . . . . . . . . . . 13 74 7.2. Informative References . . . . . . . . . . . . . . . . . . 13 75 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 14 77 1. Introduction 79 Passwords and passphrases are the predominant way of doing 80 authentication in the Internet today. Many protocols that use 81 passwords and passphrases for authentication exchange password- 82 derived data as a proof-of-knowledge of the password (for example, 83 [RFC5996], and [RFC5433]). This opens the exchange up to an off-line 84 dictionary attack where the attacker gleans enough knowledge from 85 either an active or passive attack on the protocol to run through a 86 pool of potential passwords and compute verifiers until it is able to 87 match the password-derived data. 89 This protocol employs discrete logarithm cryptography to perform an 90 efficient exchange in a way that performs mutual authentication using 91 a password but is resistant to an off-line dictionary attack. 93 1.1. Requirements Language 95 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 96 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 97 document are to be interpreted as described in RFC 2119 [RFC2119]. 99 1.2. Definitions 101 1.2.1. Notations 103 The following notations are used in this memo 105 password 106 A shared, secret and potentially low-entropy word, phrase, code 107 or key used as a credential to mutually authenticate the peers. 108 It is not restricted to characters in a human language. 110 a | b 111 denotes concatenation of string "a" with string "b". 113 len(a) 114 indicates the length in bits of the string "a". 116 LSB(a) 117 returns the least-significant bit of the bitstring "a". 119 min(a,b) 120 returns the lexicographical minimum of strings a and b, or zero 121 (0) if a equals b. 123 max(a,b) 124 returns the lexicographical maximum of strings a and b, or zero 125 (0) if a equals b. 127 The convention for this memo to represent an element in a finite 128 cyclic group is to use an upper-case letter or acronym, while a 129 scalar is indicated with a lower-case letter or acronym. 131 1.2.2. Resistance to Dictionary Attack 133 Resistance to dictionary attack means that any advantage an adversary 134 can gain must be directly related to the number of interactions she 135 makes with an honest protocol participant and not through 136 computation. The adversary will not be able to obtain any 137 information about the password except whether a single guess from a 138 protocol run is correct or incorrect. 140 2. Discete Logarithm Cryptography 142 Dragonfly uses discrete logarithm cryptography to achieve 143 authentication and key agreement (see [SP800-56A]). Each party to 144 the exchange derives ephemeral keys with respect to a particular set 145 of domain parameters (referred to here as a "group"). A group can be 146 based on Finite Field Cryptography (FFC) or Elliptic Curve 147 Cryptography (ECC). 149 Three operations are defined for both types of groups: 151 o "scalar operation"-- takes a scalar and an element in the group 152 to produce another element-- Z = scalar-op(x, Y). 154 o "element operation"-- takes two elements in the group to produce 155 a third-- Z = element-op(X, Y). 157 o "inverse operation"-- takes an element and returns another 158 element such that the element operation on the two produces the 159 identity element of the group-- Y = inverse(X). 161 2.1. Elliptic Curve Cryptography 163 Domain parameters for the ECC groups used by dragonfly are: 165 o A prime, p, determining a prime field GF(p). The cryptographic 166 group will be a subgroup of the full elliptic curve group that 167 consists of points on an elliptic curve -- elements from GF(p) 168 that satisfy the curve's equation -- together with the "point at 169 infinity" that serves as the identity element. The group 170 operation for ECC groups is addition of points on the elliptic 171 curve. 173 o Elements a and b from GF(p) that define the curve's equation. The 174 point (x, y) in GF(p) x GF(p) is on the elliptic curve if and only 175 if (y^2 - x^3 - a*x - b) mod p equals zero (0). 177 o A point, G, on the elliptic curve, which serves as a generator for 178 the ECC group. G is chosen such that its order, with respect to 179 elliptic curve addition, is a sufficiently large prime. 181 o A prime, q, which is the order of G, and thus is also the size of 182 the cryptographic subgroup that is generated by G. 184 The scalar operation is multiplication of a point on the curve by 185 itself a number of times. The point Y is multiplied x-times to 186 produce another point Z: 188 Z = scalar-op(x, Y) = x*Y 190 The element operation is addition of two points on the curve. Points 191 X and Y are summed to produce another point Z: 193 Z = element-op(X, Y) = X + Y 195 The inverse function is defined such that the sum of an element and 196 its inverse is "0", the point-at-infinity of an elliptic curve group: 198 R + inverse(R) = "0" 200 Elliptic curve groups require a mapping function, q = F(Q), to 201 convert a group element to an integer. The mapping function used in 202 this memo returns the x-coordinate of the point it is passed. 204 scalar-op(x, Y) can be viewed as x iterations of element-op() by 205 defining: 207 Y = scalar-op(1, Y) 209 Y = scalar-op(x, Y) = element-op(Y, scalar-op(x-1, Y)), for x > 1 211 A definition of how to add two points on an elliptic curve (i.e. 212 element-op(X, Y)) can be found in [RFC6090]. 214 Note: There is another elliptic curve domain parameter, a co-factor, 215 h, that is defined by the requirement that the size of the full 216 elliptic curve group (including "0") be the product of h and q. 217 Elliptic curve groups used with dragonfly authentication MUST have a 218 co-factor of one (1). 220 2.2. Finite Field Cryptography 222 Domain parameters for the FFC groups used in dragonfly are: 224 o A prime, p, determining a prime field GF(p), the integers modulo 225 p. The FFC group will be a subgroup of GF(p)*, the multiplicative 226 group of non-zero elements in GF(p). The group operation for FFC 227 groups is multiplication modulo p. 229 o An element, G, in GF(p)* which serves as a generator for the FFC 230 group. G is chosen such that its multiplicative order is a 231 sufficiently large prime divisor of ((p-1)/2). 233 o A prime, q, which is the multiplicative order of G, and thus also 234 the size of the cryptographic subgroup of GF(p)* that is generated 235 by G. 237 The scalar operation is exponentiation of a generator modulo a prime. 238 An element Y is taken to the x-th power modulo the prime returning 239 another element, Z: 241 Z = scalar-op(x, Y) = Y^x mod p 243 The element operation is modular multiplication. Two elements, X and 244 Y, are multiplied modulo the prime returning another element, Z: 246 Z = element-op(X, Y) = (X * Y) mod p 248 The inverse function for a MODP group is defined such that the 249 product of an element and its inverse modulo the group prime equals 250 one (1). In other words, 252 (R * inverse(R)) mod p = 1 254 3. The Dragonfly Key Exchange 256 There are two parties to the Dragonfly exchange named, for 257 convenience and by convention, Alice and Bob. The two parties have a 258 shared password that was established in an out-of-band mechanism and 259 they both agree to use a particular domain parameter set (either ECC 260 or FFC). 262 Prior to beginning the Dragonfly exchange, the two peers MUST derive 263 a secret element in the chosen domain parameter set. Two "hunting- 264 and-pecking" techniques to determine a secret element, one for ECC 265 and one for FFC, are described in Section 3.2 but any secure, 266 determinstic method that is agreed up on can be used. For instance, 267 the technique described in [hash2ec] can be used for ECC groups. 269 The Dragonfly exchange consists of two message exchanges, a "Commit 270 Exchange" in which both sides commit to a single guess of the 271 password, and a "Confirm Exchange" in which both sides confirm 272 knowledge of the password. A side effect of running the Dragonfly 273 exchange is an authenticated, shared, and secret key whose 274 cryptographic strength is set by the agreed-upon group. 276 Dragonfly uses a random function, H(), a mapping function, F(), and a 277 key derivation function, KDF(). 279 3.1. Assumptions 281 The Dragonfly protocol achieves security under some basic 282 assumptions: 284 1. Function H is a "random oracle" (see [RANDOR]) that maps a binary 285 string of indeterminate length onto a fixed binary string that is 286 x bits in length. 288 H: {0,1}^* --> {0,1}^x 290 Given knowledge of the input to H, an adversary is unable to 291 distinguish the output of H from a random data source. 293 2. Function F is an injective mapping function that takes an element 294 in a group and returns an integer. For ECC groups function F() 295 returns the x-coordinate of the element (which is a point on the 296 elliptic curve), for FFC groups function F() is the identity 297 function (since all elements in an FFC group are already integers 298 less than the prime): 300 ECC: x = F(P), where P=(x,y) 302 FFC: x = F(x) 304 3. Function KDF is a key derivation function (see, for instance, 305 [SP800-108]) that takes a key to stretch, k, a label to bind to 306 the key, label, and an indication of the desired output, n: 308 stretch = KDF-n(k, label) 310 so that len(stretch) equals n. 312 4. The discrete logarithm problem for the chosen group is hard. 313 That is, given g, p, and y = g^x mod p, it is computationally 314 infeasible to determine x. Similarly, for an ECC group given the 315 curve definition, a generator G, and Y = x * G, it is 316 computationally infeasible to determine x. 318 5. There exists a pool of passwords from which the password shared 319 by the two peers is drawn. This pool can consist of words from a 320 dictionary, for example. Each password in this pool has an equal 321 probability of being the shared password. All potential 322 attackers have access to this pool of passwords. 324 6. The peers have to ability to produce quality random numbers. 326 3.2. Derviation of the Password Element 328 Prior to beginning the exchange of information, the peers MUST derive 329 a secret element, called the Password Element (PE), in the group 330 defined by the chosen domain parameter set. From the point-of-view 331 of an attacker who does not know the password, PE will be a random 332 element in the negotiated group. Two examples are described here for 333 completeness but any method of deterministically mapping a secret 334 string into an element in a selected group can be used, for instance 335 the technique in [hash2ec] for ECC groups. If a different technique 336 than the ones described here is used, the secret string SHOULD 337 include the identities of the peers. 339 To fix PE, both peers MUST have a common view of the password. If 340 either side wants to store a salted version of the password it will 341 be necessary to convey the salt to the other side prior to commensing 342 the exchange. 344 The determinstic process to select the PE begins with choosing a 345 secret seed and then performing a group-specific hunting-and-pecking 346 technique-- one for FFC groups and another for ECC groups. 348 First, an 8-bit counter is set to one (1) and a secret base is 349 computed using the negotiated one-way function with the identities of 350 the two participants, Alice and Bob, the secret password and the 351 counter: 353 base = H((max(Alice,Bob) | min(Alice,Bob) | password | counter) 355 The base is then stretched using the key derivation function, KDF, to 356 the length of the prime from the group's domain parameter set: 358 seed = KDF-n(base, "Dragonfly Hunting and Pecking") 360 where n = len(p). The string bound to the derived seed is for 361 illustrative purposes only. Implementations of the dragonfly key 362 exchange SHOULD use a usage specific label with the KDF. 364 The seed is then passed to the group-specific hunting and pecking 365 technique. 367 Note that if the protocol performing the dragonfly exchange has the 368 ability to exchange random nonces those SHOULD be added to the 369 computation of base to ensure that each run of the protocol produces 370 a different PE. 372 3.2.1. Hunting and Pecking with ECC Groups 374 The ECC specific hunting and pecking technique entails looping until 375 a valid point on the elliptic curve has been found. If the seed is 376 not a quadratic residue modulo p, then the counter is incremented, a 377 new base and new seed are generated and the hunting and pecking 378 continues. If the seed is a quadratic residue modulo p, then the 379 seed is used as the x-coordinate with the equation of the curve to 380 solve for a y-coordinate. An ambiguity exists since two values for 381 the y-coordinate would be valid and the low-order bit of the base is 382 used to unambiguously determine the correct y-coordinate. The 383 resulting (x,y) pair becomes the Password Element, PE. 385 Algorithmically, the process looks like this: 387 found = 0 388 counter = 1 389 n = len(p) 390 do { 391 base = H(max(Alice,Bob) | min(Alice,Bob) | password | counter) 392 seed = KDF-n(seed, "Dragonfly Hunting And Pecking") 393 if (seed < p) 394 then 395 x = seed 396 if ( (x^3 + ax + b) is a quadratic residue mod p) 397 then 398 y = sqrt(x^3 + ax + b) 399 if (LSB(y) == LSB(base)) 400 then 401 PE = (x,y) 402 else 403 PE = (x,p-y) 404 fi 405 found = 1 406 fi 407 fi 408 counter = counter + 1 409 } while (found == 0) 411 Figure 1: Fixing PE for ECC Groups 413 3.2.2. Hunting and Pecking with MODP Groups 415 The MODP specific hunting and pecking technique entails finding a 416 random element which, when used as a generator, will create a group 417 with the same order as the group created by the generator from the 418 domain parameter set. The secret generator is found by 419 exponentiating the seed to the value ((p-1)/q), where p is the prime 420 and q is the order from the domain parameter set. If that value is 421 greater than one (1) it becomes PE, otherwise the counter is 422 incremented, a new base and seed are generated, and the hunting and 423 pecking continues. 425 Algorithmically, the process looks like this: 427 found = 0 428 counter = 1 429 n = len(p) 430 do { 431 base = H(max(Alice,Bob) | min(Alice,Bob) | password | counter) 432 seed = KDF-n(base, "Dragonfly Hunting And Pecking") 433 if (seed < p) 434 then 435 PE = seed ^ ((p-1)/q) mod p 436 if (PE > 1) 437 then 438 found = 1 439 fi 440 fi 441 counter = counter + 1 442 } while (found == 0) 444 Figure 2: Fixing PE for MODP Groups 446 3.3. The Commit Exchange 448 In the Commit Exchange both sides commit to a single guess of the 449 password. The peers generate a scalar and an element, exchange them 450 with each other, and process the other's scalar and element to 451 generate a common and shared secret. 453 First each peer generates two random numbers, private and mask. 454 These two secrets, the Password Element, and the order from the 455 selected domain parameter set are then used to construct the scalar 456 and element: 458 scalar = (private + mask) modulo q 460 Element = inverse(scalar-op(mask, PE)) 462 The mask is no longer needed and MUST be irretrievably destroyed. 464 The peers exchange their scalar and Element and use the other peer's 465 scalar and Element, deemed peer-scalar and Peer-Element, with the 466 Password Element to derive a shared secret, ss: 468 ss = F(scalar-op(private, 469 element-op(peer-Element, 470 scalar-op(peer-scalar, PE)))) 472 To enforce key separation and crypto hygiene, the shared secret is 473 stretched into two subkeys, a key confirmation key, KCK, and a master 474 key, MK. Each of the subkeys SHOULD be at least the length of the 475 prime used in the selected group. 477 KCK | MK = KDF-n(ss, "Dragonfly Key Derivation") 479 where n = len(p)*2. 481 3.4. The Confirm Exchange 483 In the Confirm Exchange both sides confirm that they derived the same 484 secret, and therefore, are in possession of the same password. 486 The Commit Exchange consists of an exchange of data that is the 487 output of the random function, H(), the key confirmation key, and the 488 two scalars and two elements exchanged in the Commit Exchange. The 489 order of the scalars and elements are, scalars before elements, and 490 sender's value before recipient's value. So from each peer's 491 perspective, it would generate: 493 confirm = H(KCK | scalar | peer-scalar | 494 Element | Peer-Element) 496 The two peers exchange these confirmations and verify the correctness 497 of the other peer's confirmation that they receive. If the other 498 peer's confirmation is valid, authentication succeeds; if the other 499 peer's confirmation is not valid, authentication fails. 501 If authentication fails, all ephemeral state created as part of the 502 particular run of the dragonfly exchange MUST be irretrievabley 503 destroyed. If authentication does not fail, MK can be exported as an 504 authenticated and secret key that can be used by another protocol, 505 for instance IPsec, to protect other data. 507 4. Acknowledgements 509 This template was derived from an initial version written by Pekka 510 Savola and contributed by him to the xml2rfc project. 512 5. IANA Considerations 514 This memo includes no request to IANA. 516 6. Security Considerations 518 The dragonfly exchange requires both participants to have an 519 identical representation of the password. Salting of the password 520 merely generates a new credential-- the salted password-- which must 521 be identically represented on both sides. If an adversary is able to 522 gain access to the database of salted passwords, she would be able to 523 impersonate one side to the other, even if she was unable to 524 determine the underlying, unsalted, password. 526 Resistance to dictionary attack means that an adversary must launch 527 an active attack to make a single guess at the password. If the size 528 of the dictionary from which the password was extracted was "d", and 529 each password in the dictionary has an equal probability of being 530 chosen, then the probability of success after a single guess is 1/d. 531 After "x" guesses, and removal of failed guesses from the pool of 532 possible passwords, the probability becomes 1/(d-x). As "x" grows, 533 so does the probability of success. Therefore, it is possible for an 534 adversary to determine the password through repeated brute-force, 535 active, guessing attacks. Users of the dragonfly key exchange SHOULD 536 ensure that the size of the pool from which the password was drawn, 537 "d", is sufficiently large to make this attack preventable. 538 Implementations of dragonfly SHOULD support countermeasures to deal 539 with this attack-- for instance, by refusing authentication attempts 540 for a certain amount of time, after the number of failed 541 authentication attempts reaches a certain threshold. No such 542 threshold or amount of time is recommended in this memo. 544 7. References 546 7.1. Normative References 548 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 549 Requirement Levels", BCP 14, RFC 2119, March 1997. 551 7.2. Informative References 553 [RANDOR] Bellare, M. and P. Rogaway, "Random Oracles are Practical: 554 A Paradigm for Designing Efficient Protocols", Proceedings 555 of the 1st ACM Conference on Computer and Communication 556 Security, ACM Press, 1993, 557 . 559 [RFC5433] Clancy, T. and H. Tschofenig, "Extensible Authentication 560 Protocol - Generalized Pre-Shared Key (EAP-GPSK) Method", 561 RFC 5433, February 2009. 563 [RFC5996] Kaufman, C., Hoffman, P., Nir, Y., and P. Eronen, 564 "Internet Key Exchange Protocol Version 2 (IKEv2)", 565 RFC 5996, September 2010. 567 [RFC6090] McGrew, D., Igoe, K., and M. Salter, "Fundamental Elliptic 568 Curve Cryptography Algorithms", RFC 6090, February 2011. 570 [SP800-108] 571 Chen, L., "Recommendations for Key Derivation Using 572 Pseudorandom Functions", NIST Special Publication 800-108, 573 April 2008. 575 [SP800-56A] 576 Barker, E., Johnson, D., and M. Smid, "Recommendations for 577 Pair-Wise Key Establishment Schemes Using Discrete 578 Logarithm Cryptography", NIST Special Publication 800-56A, 579 March 2007. 581 [hash2ec] Coron, J-B. and T. Icart, "An indifferentiable hash 582 function into elliptic curves", Cryptology ePrint 583 Archive Report 2009/340, 2009. 585 Author's Address 587 Dan Harkins (editor) 588 Aruba Networks 589 1322 Crossman Avenue 590 Sunnyvale, CA 94089-1113 591 United States of America 593 Email: dharkins@arubanetworks.com