idnits 2.17.1 draft-barnes-cfrg-mult-for-7748-00.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 abstract seems to contain references ([1]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. -- The draft header indicates that this document updates RFC7748, but the abstract doesn't seem to mention this, which it should. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (November 04, 2019) is 1635 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: '1' on line 312 Summary: 1 error (**), 0 flaws (~~), 1 warning (==), 3 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group R. Barnes 3 Internet-Draft Cisco 4 Updates: 7748 (if approved) J. Alwen 5 Intended status: Informational Wickr 6 Expires: May 7, 2020 S. Corretti 7 IOHK 8 November 04, 2019 10 Homomorphic Multiplication for X25519 and X448 11 draft-barnes-cfrg-mult-for-7748-00 13 Abstract 15 In some contexts it is useful for holders of the private and public 16 parts of an elliptic curve key pair to be able to independently apply 17 an updates to those values, such that the resulting updated public 18 key corresponds to the updated private key. Such updates are 19 straightforward for older elliptic curves, but for X25519 and X448, 20 the "clamping" prescribed for scalars requires some additional 21 processing. This document defines a multiplication procedure that 22 can be used to update X25519 and X448 key pairs. This algorithm can 23 fail to produce a result, but only with negligible probability. 24 Failures can be detected by the holder of the private key. 26 Note to Readers 28 Source for this draft and an issue tracker can be found at 29 https://github.com/bifurcation/draft-barnes-cfrg-mult-for-7748 [1]. 31 Status of This Memo 33 This Internet-Draft is submitted in full conformance with the 34 provisions of BCP 78 and BCP 79. 36 Internet-Drafts are working documents of the Internet Engineering 37 Task Force (IETF). Note that other groups may also distribute 38 working documents as Internet-Drafts. The list of current Internet- 39 Drafts is at https://datatracker.ietf.org/drafts/current/. 41 Internet-Drafts are draft documents valid for a maximum of six months 42 and may be updated, replaced, or obsoleted by other documents at any 43 time. It is inappropriate to use Internet-Drafts as reference 44 material or to cite them other than as "work in progress." 46 This Internet-Draft will expire on May 7, 2020. 48 Copyright Notice 50 Copyright (c) 2019 IETF Trust and the persons identified as the 51 document authors. All rights reserved. 53 This document is subject to BCP 78 and the IETF Trust's Legal 54 Provisions Relating to IETF Documents 55 (https://trustee.ietf.org/license-info) in effect on the date of 56 publication of this document. Please review these documents 57 carefully, as they describe your rights and restrictions with respect 58 to this document. Code Components extracted from this document must 59 include Simplified BSD License text as described in Section 4.e of 60 the Trust Legal Provisions and are provided without warranty as 61 described in the Simplified BSD License. 63 Table of Contents 65 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 66 2. Updating X25519 / X448 key pairs . . . . . . . . . . . . . . 3 67 3. Failure Cases . . . . . . . . . . . . . . . . . . . . . . . . 4 68 3.1. X25519 . . . . . . . . . . . . . . . . . . . . . . . . . 5 69 3.2. X448 . . . . . . . . . . . . . . . . . . . . . . . . . . 5 70 4. Protocol Considerations . . . . . . . . . . . . . . . . . . . 6 71 5. Security Considerations . . . . . . . . . . . . . . . . . . . 6 72 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 7 73 7. References . . . . . . . . . . . . . . . . . . . . . . . . . 7 74 7.1. Normative References . . . . . . . . . . . . . . . . . . 7 75 7.2. Informative References . . . . . . . . . . . . . . . . . 7 76 7.3. URIs . . . . . . . . . . . . . . . . . . . . . . . . . . 7 77 Appendix A. Test Vectors . . . . . . . . . . . . . . . . . . . . 7 78 A.1. X25519 . . . . . . . . . . . . . . . . . . . . . . . . . 8 79 A.2. X448 . . . . . . . . . . . . . . . . . . . . . . . . . . 8 80 Appendix B. Acknowledgements . . . . . . . . . . . . . . . . . . 10 81 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 10 83 1. Introduction 85 In some contexts it is useful for holders of the private and public 86 parts of an elliptic curve key pair to be able to independently apply 87 an updates to those values, such that the resulting updated public 88 key corresponds to the updated private key. [[ TODO: Cite examples 89 (e.g. HKD like BIP32, Tor Hidden Service Identity Blinding, MLS), 90 security properties]] 92 Such updates are straightforward with traditional elliptic curve 93 groups, such as the NIST and Brainpool curve groups 94 [NISTCurves][RFC5639], or with the proposed Ristretto groups 95 [I-D.hdevalence-cfrg-ristretto]. In these groups, multiplication of 96 points by scalars is a homomorphism with regard to multiplication of 97 scalars, so a key pair can be updated by multiplying the private key 98 and the same "delta" scalar. In other words, the following diagram 99 commutes for all "d", where "d\*" represents scalar multiplication by 100 "d" and "\*G" represents multiplication of a scalar with the base 101 point of the curve: 103 *G 104 Scalars ------> Points 105 | | 106 d* | | d* 107 V V 108 Scalars ------> Points 109 *G 111 The X25519 and X448 functions defined in RFC 7748 [RFC7748], however, 112 require scalars to be "clamped" before point multiplication is 113 performed, which breaks this homomorphism. In particular, scalars 114 are passed through the "decodeScalar25519" or "decodeScalar448" 115 functions, respectively, which force a high-order bit to be set. 116 Since this high-order bit is not guaranteed to be set in the product 117 of two such numbers, the product of of two scalars may not represent 118 a valid private key. In fact, there are points on Curve25519/ 119 Curve448 which are not X25519/X448 public keys, because their 120 discrete logs do not have the correct high bit set. 122 Fortunately, X25519 and X448 use only one coordinate to represent 123 curve points, which means they are insensitive to the sign of the 124 point, so a scalar private key and its negative result in the same 125 public key. And if a given scalar does not have the correct bit set, 126 then its negative modulo the curve order almost certainly does. (We 127 quantify these ideas below.) This allows us to construct an amended 128 multiplication routine that succeeds with overwhelming probability, 129 and where the failure cases are detectable by the holder of the 130 private key. 132 The remainder of this document describes these algorithms, quantifies 133 the failure cases and the resulting probabilities of failure, and 134 discusses how failures can be detected. 136 2. Updating X25519 / X448 key pairs 138 The following procedures allow for updating X25519/X448 public keys 139 and private keys in constant time. The values "sk" and "pk" 140 represent the private and public keys of the key pair, and the value 141 "d" represents a "delta" scalar being applied. All arithmetic 142 operations are performed modulo the order "n" of the relevant curve: 144 o X25519: 146 * "x = 0x14def9dea2f79cd65812631a5cf5d3ed" 148 * "n = 8 * (2^253 + x)" 150 * "b = 254" 152 o X448: 154 * "x = 155 0x8335dc163bb124b65129c96fde933d8d723a70aadc873d6d54a7bb0d" 157 * "n = 4 * (2^446 - x)" 159 * "b = 447" 161 def updatePublic(d, pk): 162 return CurveN(d, pkI) 164 def updatePrivate(d, sk): 165 dc = decodeScalar(d) 166 skc = decodeScalar(sk) 167 skP = dc * skc 168 skN = n - skP 169 cP = (skP >> b) & 1 170 cswap(1 - cP, skP, skN) 171 return skP 173 The pulic operation is clearly just a normal DH operation in the 174 relevant curve. The private operation computes the product of the 175 delta with the private key as well as its negative modulo the curve 176 order. If the product does not have the correct bit set, then the 177 cswap operation ensures that that the negative is returned. 179 If "updatePrivate" and "updatePublic" are called on both halves of a 180 key pair, and "updatePrivate" produces a valid private key (with the 181 relevant high bit set), then the output private and public keys will 182 correspond to each other. (That is, the public key will equal the 183 private key times the base point.) If the "updatePrivate" function 184 does not return a valid private key, then the update has failed, and 185 the delta "d" cannot be used with this key pair. 187 3. Failure Cases 189 An update of a private key "sk" by a delta "d" fails if and only if 190 neither "d*sk" or "n - d*sk" has the relevant bit set. In this 191 section, we will assume that for uniform "d", this product "c = d*sk" 192 is uniformly distributed among scalars modulo "n". From this 193 assumption, we can describe the set of values "c" for which updates 194 fail, and thus estimate the probability that an update will fail. 196 In general, an update fails if neither "c" nor its negative has the 197 relevant high bit set, i.e., if they are not in the range "[M, N]", 198 where "M = 2^b" and "N = 2^{b+1} - 1". So our failure criterion is: 200 (c < M || c > N) && ((n-c) < M || (n-c) > N) 201 <=> (c < M || c > N) && (c < n-N || c > n-M) 203 So the probability of failures is proportional to the size of the set 204 where this conditions applies. In the following subsections, we will 205 calculate these values for X25519 and X448. 207 3.1. X25519 209 In the case of X25519, the following values apply: 211 b = 254 212 n = 8 * (2^253 + x) 213 = 2^255 + 8x 214 M = 2^254 215 N = 2^255 - 1 216 n - M = (2^255 + 8x) - 2^254 217 = 2^254 + 8x 218 n - N = 8x + 1 220 Thus we have "n - N < M < n-M < N", so the failure set "F" and the 221 failure probability "|F|/n" are as follows: 223 F = [0, n-N) U (N, n] 224 = [0, 8x + 1) U (2^255 - 1, 2^255 + 8x] 225 |F|/n = (2 * 8x) / (2^255 + 8x) 226 < 2^130 / 2^255 (since x < 2^125) 227 = 2^-125 229 3.2. X448 231 In the case of Curve448, the following values apply: 233 b = 447 234 n = 4 * (2^446 - x) 235 = 2^448 - 4x 236 M = 2^447 237 N = 2^448 - 1 238 n - M = (2^448 - 4x) - 2^447 239 = 2^447 - 4x 240 n - N = 1 - 4x 242 Thus we have "n - N < 0 < n - M < M < N", so the failure set "F" and 243 the failure probability "|F|/n" are as follows: 245 F = (n-M, M) 246 = (2^447 - 4x, 2^447) 247 |F|/n = (4x - 1) / (2^448 - 4x) 248 < 2^226 / 2^448 (since x < 2^224) 249 = 2^-222 251 4. Protocol Considerations 253 Protocols making use of the update mechanism defined in this document 254 should account for the possibility that updates can fail. As 255 described above, entities updating private keys can tell when the 256 update fails. However, entities that hold only the public key of a 257 key pair will not be able to detect such a failure. So when this 258 mechanism is used in a given protocol context, it should be possible 259 for the private-key updater to inform other actors in the protocol 260 that a failure has occurred. 262 5. Security Considerations 264 [[ TODO: Comment on whether this algorithm achieves the security 265 objective stated in the introduction ]] 267 The major security concerns with this algorithm are implementation- 268 related. The "updatePrivate" function requires access to the private 269 key in ways that are typically not exposed by HSMs or other limited- 270 access crypto libraries. Implementing key updates with such limited 271 interfaces will require either exporting the private key or 272 implementing the update algorithm internally to the HSM/library. 273 (The latter obviously being preferable.) 275 As an algorithm involving secret key material, the "updatePrivate" 276 function needs to be implemented in in a way that does not leak 277 secrets through side channels. While the algorithm specified above 278 is logically constant-time, it reques that multiplication, 279 subtraction, and conditional swap be implemented in constant time. 281 6. IANA Considerations 283 This document makes no request of IANA. 285 7. References 287 7.1. Normative References 289 [RFC7748] Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves 290 for Security", RFC 7748, DOI 10.17487/RFC7748, January 291 2016, . 293 7.2. Informative References 295 [I-D.hdevalence-cfrg-ristretto] 296 Valence, H., Grigg, J., Tankersley, G., Valsorda, F., and 297 I. Lovecruft, "The ristretto255 Group", draft-hdevalence- 298 cfrg-ristretto-01 (work in progress), May 2019. 300 [NISTCurves] 301 "Digital Signature Standard (DSS)", National Institute of 302 Standards and Technology report, 303 DOI 10.6028/nist.fips.186-4, July 2013. 305 [RFC5639] Lochter, M. and J. Merkle, "Elliptic Curve Cryptography 306 (ECC) Brainpool Standard Curves and Curve Generation", 307 RFC 5639, DOI 10.17487/RFC5639, March 2010, 308 . 310 7.3. URIs 312 [1] https://github.com/bifurcation/draft-barnes-cfrg-mult-for-7748 314 Appendix A. Test Vectors 316 All values are presented as little-endian integers. An 317 implementation should verify that the following relations hold: 319 o sk1 = updatePriv(d, sk0) 321 o pk1 = updatePub(d, pk0) 323 o pk1 = CurveN(sk1) 325 A.1. X25519 327 Successful update (no swap): 329 sk0 ff08989a80d6042f21cafd4af63f4334cc9a08e9a18a55f28739dd9c96762b36 330 pk0 4d8ce30b0322cbf5caa30d654f14e986a774fd2a50135165818ef3ed02566462 331 d 7ceff33b5fa2e095c37f773bdcc747e0071bea02d6b58f7a6c4283b1fea5df39 332 dC 78eff33b5fa2e095c37f773bdcc747e0071bea02d6b58f7a6c4283b1fea5df79 333 skC f808989a80d6042f21cafd4af63f4334cc9a08e9a18a55f28739dd9c96762b76 334 skP c848d5753e4d06e9d475d972537b4b8f32c7c81a97c538ced90aa0f64414e661 335 skN a056d97194cb8cd7dd70e3a4a153ac17ce3837e5683ac73126f55f09bbeb191e 336 cP 1 337 sk1 c848d5753e4d06e9d475d972537b4b8f32c7c81a97c538ced90aa0f64414e661 338 pk1 ee043d01816ba2da7cc37421ecbfd8c947afd57b18344dcfe77071929c02e061 340 Successful update (swap): 342 sk0 61b64d3177801e6a8bb742b235edccf32736c76ee0bfd62c9b4a204e7f2dd544 343 pk0 1d415ce35bff1279fb7392ea5ec6e856f670c289d2e4bd2161c876bb7d662a7b 344 d 7ceff33b5fa2e095c37f773bdcc747e0071bea02d6b58f7a6c4283b1fea5df39 345 dC 78eff33b5fa2e095c37f773bdcc747e0071bea02d6b58f7a6c4283b1fea5df79 346 skC 60b64d3177801e6a8bb742b235edccf32736c76ee0bfd62c9b4a204e7f2dd544 347 skP 786eb7c972f788e1d97f14eba675801dbdece5e93183502b65ec6abe2b525c5e 348 skN f030f71d60210adfd866a82c4e59778943131a16ce7cafd49a139541d4ada321 349 cP 0 350 sk1 786eb7c972f788e1d97f14eba675801dbdece5e93183502b65ec6abe2b525c5e 351 pk1 a854ba19d7de3d73531501566b4e4e51ab263d743316525a86d6ecc2bff5036a 353 Failed update: 355 sk0 e09ec60ffb39ef974324161d749df7881124492d369906147ea3a64086c1e857 356 pk0 984398c1dc572f13a20dd046901daf6716615e37d8c701ed75fb3871af14d374 357 d 7ceff33b5fa2e095c37f773bdcc747e0071bea02d6b58f7a6c4283b1fea5df39 358 dC 78eff33b5fa2e095c37f773bdcc747e0071bea02d6b58f7a6c4283b1fea5df79 359 skC e09ec60ffb39ef974324161d749df7881124492d369906147ea3a64086c1e857 360 skP 289faee7d21893c0b2e6bc17f5cef7a600000000000000000000000000000000 361 skN 4000000000000000000000000000000000000000000000000000000000000080 362 cP 0 363 sk1 289faee7d21893c0b2e6bc17f5cef7a600000000000000000000000000000000 364 pk1 af6c6be037cc0622e88a735a98f77ac06f372bad8542bc0f65c0c580b095ae4e 366 A.2. X448 368 Successful update (no swap): 370 sk0 745310aa0942b1cf2d7d4a8eef25c572da5f647ae376e7f1f5dcacdd 371 cc0d09419a0cb773d73d331e68e6f6485427de9ecddb8f73440e0012 372 pk0 e1ff42e736266138310db4beab444fe68440b2f1459c729e537d9833 373 6fa009ce25b3a3c57743577d995cf7f6f18e40f2fb228e5177c06219 374 d f50678b0c8505f04554b7f8e04b1ab1682b681f279df4d84129b07e0 375 4bcfe59f328e9ee2bbb64e9ae94c776593e8bac549fe40d1a4e81371 376 dC f40678b0c8505f04554b7f8e04b1ab1682b681f279df4d84129b07e0 377 4bcfe59f328e9ee2bbb64e9ae94c776593e8bac549fe40d1a4e813f1 378 skC 745310aa0942b1cf2d7d4a8eef25c572da5f647ae376e7f1f5dcacdd 379 cc0d09419a0cb773d73d331e68e6f6485427de9ecddb8f73440e0092 380 skP 908dafad675a0b99fd6991d19e13c3b26f121a4881316601fc192e0a 381 0737b99f44ead69b52684dd00ccb5ea34c1a8ea5d768510f34e873d6 382 skN 3c86b1ffe2afd7f456d384652bf6efd2d0c73e73a53bd50fab75fae8 383 f6c84660bb152964ad97b22ff334a15cb3e5715a2897aef0cb178c29 384 cP 1 385 sk1 908dafad675a0b99fd6991d19e13c3b26f121a4881316601fc192e0a 386 0737b99f44ead69b52684dd00ccb5ea34c1a8ea5d768510f34e873d6 387 pk1 40e213cb2c06c6ec327e80623ecb2625b7a474a9eb4eb7f8c601d148 388 cd7734a59afbb5886efe1cca48b36353d750d076a7fec3f4686ffa27 390 Successful update (swap): 392 sk0 42e35e26d257aed97ec5d66528504acbbd4141dae7eefb232c30f6da 393 8664ef38b083020f0931adaeb511143d80de6942c1096f33fe96c80e 394 pk0 a79df64f2b9c3510ccf27825f7524791ede627ce76f4a174cf050521 395 86e2994aa078cb2a605179cfcd33ec4e6747f222036025f6233c0268 396 d f50678b0c8505f04554b7f8e04b1ab1682b681f279df4d84129b07e0 397 4bcfe59f328e9ee2bbb64e9ae94c776593e8bac549fe40d1a4e81371 398 dC f40678b0c8505f04554b7f8e04b1ab1682b681f279df4d84129b07e0 399 4bcfe59f328e9ee2bbb64e9ae94c776593e8bac549fe40d1a4e813f1 400 skC 40e35e26d257aed97ec5d66528504acbbd4141dae7eefb232c30f6da 401 8664ef38b083020f0931adaeb511143d80de6942c1096f33fe96c88e 402 skP b4ba86f8b4d83a0b4d192df1e0ab71645719e7ddf304fa94f155c3e6 403 ff6c746fdc45aa45e94ab75a146d9f8bf50cc8c4f520bc7d72d4ba8b 404 skN 1859dab49531a8820724e945e95d4121e9c071dd3268417cb539650c 405 fe928b9023ba55ba16b548a5eb9260740af3373b0adf43828d2b4574 406 cP 0 407 sk1 b4ba86f8b4d83a0b4d192df1e0ab71645719e7ddf304fa94f155c3e6 408 ff6c746fdc45aa45e94ab75a146d9f8bf50cc8c4f520bc7d72d4ba8b 409 pk1 eeb52f6eeb3d1785077dca6c763c0489c85f22fe5e96a82c54153ac3 410 33138c250b66445beb28986d3b7dbda1974049949906ab13f69151bc 412 Failed update: 414 sk0 48441950f8dd7ed277ed9727798b283906774ba0b3917fb21371c8f6 415 2e164c3a069e224338d696a3dfe0c99b7277593949b8e555eb0766ed 416 pk0 aaf96ee42f7752c54544225f129cd8bccb8ad834f65f6186d11cbe9b 417 105087ebf04408e0159c726eacaa8975d0c39a9a6304dca2b5d6b2eb 418 d f50678b0c8505f04554b7f8e04b1ab1682b681f279df4d84129b07e0 419 4bcfe59f328e9ee2bbb64e9ae94c776593e8bac549fe40d1a4e81371 420 dC f40678b0c8505f04554b7f8e04b1ab1682b681f279df4d84129b07e0 421 4bcfe59f328e9ee2bbb64e9ae94c776593e8bac549fe40d1a4e813f1 422 skC 48441950f8dd7ed277ed9727798b283906774ba0b3917fb21371c8f6 423 2e164c3a069e224338d696a3dfe0c99b7277593949b8e555eb0766ed 424 skP ecffffffffffffffffffffffffffffffffffffffffffffffffffffff 425 ffffffffffffffffffffffffffffffffffffffffffffffffffffff7f 426 skN e01361ad4a0ae38d543d1637ca09b38540da58bb266d3b11a78f28f3 427 fdffffffffffffffffffffffffffffffffffffffffffffffffffff7f 428 cP 0 429 sk1 ecffffffffffffffffffffffffffffffffffffffffffffffffffffff 430 ffffffffffffffffffffffffffffffffffffffffffffffffffffff7f 431 pk1 a643f22b04d50faf004a08f6ff38acbf0cbca8591b1f07a70e269ce1 432 4e240e5389a583eab63ab6d9d49d4fe051305f6676201d41df60b83d 434 Appendix B. Acknowledgements 436 Thanks to Mike Hamburg for reviewing an early version of the ideas 437 that led to this document. 439 Authors' Addresses 441 Richard L. Barnes 442 Cisco 444 Email: rlb@ipv.sx 446 Joel Alwen 447 Wickr 449 Email: jalwen@wickr.com 451 Sandro Corretti 452 IOHK 454 Email: corettis@gmail.com