idnits 2.17.1 draft-brown-ec-2y2-x3-x-mod-8-to-91-plus-5-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 -- Couldn't find a document date in the document -- date freshness check skipped. -- 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: Experimental ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: '0' on line 1160 -- Looks like a reference, but probably isn't: '1' on line 1161 -- Looks like a reference, but probably isn't: '33' on line 220 -- Looks like a reference, but probably isn't: '2' on line 1159 -- Looks like a reference, but probably isn't: '137' on line 1108 -- Looks like a reference, but probably isn't: '3' on line 1110 == Unused Reference: 'NIST-P-256' is defined on line 710, but no explicit reference was found in the text == Unused Reference: 'Zigbee' is defined on line 713, but no explicit reference was found in the text == Unused Reference: 'Brainpool' is defined on line 719, but no explicit reference was found in the text == Unused Reference: 'SEC2' is defined on line 725, but no explicit reference was found in the text == Unused Reference: 'BitCoin' is defined on line 737, but no explicit reference was found in the text == Unused Reference: 'Gordon' is defined on line 743, but no explicit reference was found in the text == Unused Reference: 'YY' is defined on line 757, but no explicit reference was found in the text Summary: 0 errors (**), 0 flaws (~~), 8 warnings (==), 9 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Internet-Draft D. Brown 2 Intended status: Experimental BlackBerry 3 Expires: 2018 Apr 14 2017 Oct 11 5 Elliptic curve 2y^2=x^3+x over field size 8^91+5 6 8 Abstract 10 This document specifies: the field of size 8^91+5, the elliptic 11 curve 2y^2=x^3+x (over this field), encoding a point (on the curve) 12 into 34 bytes, public key validation, encoding a private key into 34 13 bytes, and encoding 34 bytes into a point. Test vectors and 14 pseudocode are to be provided. 16 Status of This Memo 18 This Internet-Draft is submitted in full conformance with the 19 provisions of BCP 78 and BCP 79. Internet-Drafts are working 20 documents of the Internet Engineering Task Force (IETF). Note that 21 other groups may also distribute working documents as 22 Internet-Drafts. The list of current Internet-Drafts is at 23 http://datatracker.ietf.org/drafts/current. 25 Internet-Drafts are draft documents valid for a maximum of six 26 months and may be updated, replaced, or obsoleted by other documents 27 at any time. It is inappropriate to use Internet-Drafts as 28 reference material or to cite them other than as "work in progress." 30 Copyright Notice 32 Copyright (c) 2017 IETF Trust and the persons identified as the 33 document authors. All rights reserved. 35 This document is subject to BCP 78 and the IETF Trust's Legal 36 Provisions Relating to IETF Documents 37 (http://trustee.ietf.org/license-info) in effect on the date of 38 publication of this document. Please review these documents 39 carefully, as they describe your rights and restrictions with 40 respect to this document. 42 This document may not be modified, and derivative works of it may 43 not be created, except to format it for publication as an RFC or to 44 translate it into languages other than English. 46 Internet-Draft 2017 Oct 11 48 Table of Contents 50 1. Introduction 51 1.1. Background 52 1.2. Motivation 53 2. Requirements Language (RFC 2119) 54 3. Encoding a point into 34 bytes 55 3.1. Encoding a point into bytes 56 3.2. Decoding bytes into a point 57 4. Point validation 58 4.1. When a point MUST be validated 59 4.2. How to validate a point (given only x) 60 5. OPTIONAL encodings 61 5.1. Encoding scalar multipliers as 34 bytes 62 5.2. Encoding 34 bytes into a point (sketch) 63 6. Cryptographic schemes 64 6.1. Diffie--Hellman key agreement 65 6.2. Signatures 66 6.3 Menezes--Qu--Vanstone key agreement 67 7. IANA Considerations 68 8. Security considerations 69 8.1. Field choice 70 8.2. Curve choice 71 8.3. Encoding choices 72 8.4. General subversion concerns 73 9. References 74 9.1. Normative References 75 9.2. Informative References 76 Appendix A. Test vectors 77 Appendix B. Motivation: minimizing the room for backdoors 78 Appendix C. Pseudocode 79 C.1. Byte encoding 80 C.2. Byte decoding 81 C.3. Fermat inversion 82 C.4. Branchless Legendre symbol computation 83 C.5. Field multiplication and squaring 84 C.6. Field element partial reduction 85 C.7. Field element final reduction 86 C.8. Scalar point multiplication 87 C.9. Diffie--Hellman pseudocode 88 C.10. Elligator i 90 1. Introduction 92 This document specifies some conventions for using the elliptic 93 curve 2y^2=x^3+x over the field of size 8^91+5 in cryptography. 95 This draft focuses on applications to Diffie--Hellman exchange. 97 Internet-Draft 2017 Oct 11 99 1.1. Background 101 This document presumes that its reader already has familiarity with 102 elliptic curve cryptography. 104 The symbol '^', as used in '2y^2=x^3+x' and '8^91+5' means 105 exponentiation, also known as powering. In particular, it does not 106 mean bit-wise exclusive-or (as in the C programming language 107 operator). For example, y^3=yyy (or y*y*y, if * is used for 108 multiplication.) 110 In particular, p=8^91+5 is a (positive) prime number. Its encoding 111 into bytes, using little-endian ordering (least significant bytes 112 first), requires 35 bytes, and has the form {5,0,0,...,2}, with the 113 first byte equal to 5, the last 2, and the 33 intermediate bytes are 114 each 0. A byte encoding of p is not needed for this document, and 115 is only shown here for illustrative purposes. Its hexadecimal 116 representation (i.e. big-endian, base 16), is 20...05, with 67 zeros 117 between 2 and 5. 119 1.2. Motivation 121 The motivations for curve 2y^2=x^3+x over field 8^91+5 are discussed 122 in Appendix B. 124 In short, the main motivation is that the description of the curve 125 is very short (for an elliptic curve), thereby reducing the room for 126 a secretly embedded trapdoor, as in [Teske]. 128 2. Requirements Language (RFC 2119) 130 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 131 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 132 document are to be interpreted as described in RFC 2119 [BCP14]. 134 3. Encoding a point into 34 bytes 136 Elliptic curve cryptography uses points for public keys and raw 137 shared secrets. A point can be defined as either pair (x,y), where 138 x and y are field elements, or a special point O located at 139 infinity. Field elements for this curve are integers modulo 8^91+5. 141 Note: for practicality, an implementation will usually represent 142 the x-coordinate as a ratio (X:Z) of field elements. This 143 specification ignores that detail, assuming x has been normalized 144 to (x:1). 146 Internet-Draft 2017 Oct 11 148 To interoperably communicate, points must be encoded as byte 149 strings. 151 This draft specifies an encoding of finite points (x,y) as strings 152 of 34 bytes, as described in the following sections. 154 Note: The 34-byte encoding is not injective. Each point is 155 generally among a group of four points that share the same byte 156 encoding. 158 Note: The 34-byte encoding is not surjective. Approximately half 159 of 34-byte strings do not encode a finite point (x,y). 161 Note: In many typical ECC schemes, the 34-byte encoding works 162 well, despite being neither injective nor surjective. 164 3.1. Encoding a point into bytes 166 In short: a finite point (x,y) by the little-endian byte 167 representation of x or -x, whichever fits into 34 bytes. 169 In detail: a point (x,y) is encoded into 34 bytes b[0], b[1], ..., 170 b[33], as follows. 172 First, ensure that x is fully reduced mod p=8^91+5, so that 174 0 <= x < 8^91+5. 176 Second, further reduce x by a flipping its sign. Let 178 x' =: min(x,p-x) mod 2^272. 180 Third, set the byte string b to be the little-endian encoding of the 181 reduced integer x', by finding the unique integers b[i] such that 182 0<=b[i]<256 and 184 (x' mod 2^272) = b[0] + b[1]*256 + ... + b[33]*256^33. 186 Pseudocode can be found in Appendix C. 188 Internet-Draft 2017 Oct 11 190 3.2. Decoding bytes into a point 192 In short: the bytes are little-endian decoded into an integer which 193 becomes the x-coordinate. The y-coordinate is implicit (in 194 Diffie--Hellman). 196 +-------------------------------------------------------+ 197 | | 198 | \ W / /A\ |R) |N | I |N | /G ! | 199 | \/ \/ / \ |^\ | \| | | \| \_7 0 | 200 | | 201 | | 202 | WARNING: Some byte strings b decode to an invalid | 203 | point (x,y) that does not belong to the curve | 204 | 2y^2=x^3+x. In some situations, such invalid b can | 205 | lead to a severe attack. In these situations, the | 206 | decoded point (x,y) MUST be validated, as described | 207 | below in Section 4. | 208 | | 209 +-------------------------------------------------------+ 211 (TO DO: if y is needed explicitly, then one of y matching x must be 212 solved; in that case, y-needing application, after a point (x,y) is 213 encoded to b, it should be replaced by (x',y'), where (x',y') is the 214 decoding of b. In the rare case that x and x' do not match, then 215 (x,y) should be re-generated or rejected.) 217 In greater detail: if the 34 bytes are b[0], b[1], ..., b[33], each 218 with an integer value between 0 and 255 inclusive, then 220 x = b[0] + b[1]256 + ... + b[i]256^i + ... + b[33]256^33 222 4. Point validation 224 In elliptic curve cryptography, scalar multiplying an invalid public 225 key by a private key risks leaking information about the private 226 key. 228 4.1. When a point MUST be validated 230 Public keys from other parties MUST undergo validation if they are 231 combined with private keys as part of multiple Diffie--Hellman 232 computations: 234 Internet-Draft 2017 Oct 11 236 +---------------------------------------------------------------+ 237 | | 238 | STATIC _ ___ | 239 | SECRET ---\ |\/| | | (_` | | 240 | SCALAR ---/ POINT | | \_/ ._) | BE VALIDATED. | 241 | MULTIPLIER | 242 | | 243 +---------------------------------------------------------------+ 245 Additionally, public keys SHOULD undergo validation if they are 246 received from an unauthenticated source, even if scalar is ephemeral 247 or public. 249 TO DO: certain exceptional exemptions to the point validation 250 REQUIREMENT may be added in future versions of this draft. In 251 particular, when one party has received key confirmation from the 252 other side, some of the harm of an using invalid point is 253 diminished. The difference in risk is similar to the difference 254 between online and offline attacks on passwords. In this setting, 255 (after key confirmation is received) alternatives to point 256 validation might suffice, such as somehow limiting the rate or 257 amount of use of the static scalar secret. So, point validation 258 would be reduced to a RECOMMENDATION, but at least one of point 259 validation or rate-limiting would still be REQUIREMENT. For this 260 draft, point validation remains a REQUIREMENT, even if the key 261 confirmation is received. (Not every protocol makes a clear 262 distinction between ephemeral and static keys, and it seems that 263 only one side of Diffie--Hellman key exchange can receive key 264 confirmation before using the key.) 266 4.2. How to validate a point (given only x) 268 Upon decoding the 34 bytes into x, the next step is to compute 269 z=2(x^3+x). Then one checks if z has a nonzero square root. If z 270 has a nonzero square root, then the represented point is valid, 271 otherwise it is not valid. 273 Equivalently, one can check that x^3 + x has no square root (that 274 is, x^3+x is a quadratic non-residue). 276 To check z for a square root, one can compute the Legendre symbol 277 (z/p) and check that is 1. (Equivalently, one can check that 278 ((x^3+x)/p)=-1.) 280 The Legendre symbol can be computed using Gauss' quadratic 281 reciprocity law, but this requires implementing modular integer 282 arithmetic for moduli smaller than 8^91+5. 284 Internet-Draft 2017 Oct 11 286 More slowly, but perhaps more simply, one compute the Legendre 287 symbol using powering in the field: (z/p) = z^((p-1)/2) = 288 z^(2^272+2). This will have value 0,1 or p-1 (which is equivalent 289 to -1). 291 More generally, in signature applications, where the y-coordinate is 292 also needed, the computation of y, which involves computing a square 293 root will generally include a check that x is valid. 295 The curve 2y^2=x^3+x is not twist-secure. So, using the Montgomery 296 ladder for scalar multiplication is not enough to thwart invalid 297 public key attacks. In other words, public key validation MUST be 298 combined with the Montgomery ladder, unless the scalar multiplier 299 involved is public or a single-DH-use secret (i.e. computing kG and 300 kP, counts as a single DH use of k). 302 Note: a given point need only be validated once, if the 303 implementation can track validation state. 305 OPTIONAL: In some rare situations, it is also necessary to ensure 306 that the point has large order, not just that it is on the curve. 308 For points on this curve, each point has large order, unless it has 309 torsion by 12. In other words, if 12P != O, then the point P has 310 large order. 312 OPTIONAL: In even rarer situations, it may be necessary to ensure 313 that the point also has prime order. To be completed. 315 5. OPTIONAL encodings 317 The following two encodings are not usually required to obtain 318 interoperability in the typical ECC applications, but can sometimes 319 be useful. 321 5.1. Encoding scalar multipliers as 34 bytes 323 To be completed. 325 Basically, little-endian byte encoding of integers is recommended. 327 The main application is to signatures. 329 Another application is for test vectors (to be completed). 331 Internet-Draft 2017 Oct 11 333 5.2. Encoding 34 bytes into a point (sketch) 335 In special applications, beyond mere Diffie--Hellman key exchange or 336 digital signatures, it may be desired to encode arbitrary bytes as 337 points. 339 Example reasons are anonymity, or hiding the presence of a key 340 exchange. 342 Note: the point encoding described earlier does a different job. 343 It encodes every point. The task here is to encode every byte 344 string. 346 This method is slower than the representations above, and yields 347 biased elliptic curve points, but has the advantage that the 348 byte-strings are unbiased. 350 The idea is a minor variation of the Elligator 2 construction 351 [Elligator]. Unfortunately, Elligator 2 itself fails for curves 352 with j-invariant 1728, which includes 2y^2=x^3+x. In case of 353 confusion, this map here can be called Elligator i. 355 Fix a square root i of -1 in the field. 357 Given any random field element r, compute 359 x=i- 3i/(1-ir^2) 361 If there is no y solving 2y^2=x^3+x for this x, then replace x by 362 x+i and try to solve for y once again. 364 If the first x fails, then the second x succeeds. 366 So, now r determines a unique x. To determine y, solve it per the 367 equation, getting two roots. Label the 2 roots y0 and y1 according 368 to a deterministic rule. Then choose y0 if the first x works, else 369 choose y2. This ensures that the map from r^2 to (x,y) is 370 injective. 372 Finally, to encode a byte string b, just let it represent a field 373 element r. Note that -r will be require more than 34 bytes. So the 374 map from b to (x,y) is now injective. 376 This map is reversible. 378 To be completed. 380 Internet-Draft 2017 Oct 11 382 6. Cryptographic schemes 384 To be completed, or even removed! 386 List all possible cryptographic schemes in which this curve could be 387 used is outside the scope of this short document. Only a few 388 highlights are mentioned. 390 6.1. Diffie--Hellman key agreement 392 To be completed. 394 Question: should DH use cofactor multiplication? For now, let's say 395 no. 397 Non-cofactor multiplication risks leaking the private key mod 72, or 398 at least mod 12, or perhaps even worse (if the field arithmetic has 399 additional leaks). 401 But cofactor multiplication reduces the private key size similarly. 402 Also, if we start from a 34-byte private key scalar, then we achieve 403 a similar effect to cofactor multiplication. 405 6.2. Signatures 407 For signatures, such as ECDSA, the verifier must fully decompress 408 the 34-byte representation. The verifier must do this twice, once 409 with the signer's public key, and once with one component of the 410 signature. 412 To do this, the verifier can take, and make the most natural choice 413 of the two possible y. The signer, anticipating the verifier, then 414 must ensure that the signature will verify correctly under the 415 verifier's choices for the y values. The signer incurs only a small 416 extra cost for ensuring this. 418 To be completed. 420 Given that this curve is experimental and non-radically distinct 421 from previous curves, signers and may opt to consider an 422 experimental and non-radically distinct signature scheme with the 423 curve 2y^2=x^3+x. 425 The RKHD ElGamal signatures is an example of such a signature 426 scheme. 428 Internet-Draft 2017 Oct 11 430 In short, fix a base point G. The signing key is d, the verifying 431 key is Q=dG. A pair (R,s), R is a point, and s is an integer, is a 432 (valid) signature of message with integer hash h, if 434 sG = rR + hQ 436 where r is obtained from R by re-interpreting its byte as an 437 integer. 439 To sign a message with hash h, the signer computes a 440 message-unique secret k, computes R=kG, computers r as above, and 441 computes 443 s = rk + hd mod n 445 where n is the order of G. 447 The signer may compute k as the hash of s and h, or through some 448 other method which ensures that k depends (pseudorandomly) on h. 450 The signer MUST choose k such that no linear relation between the k 451 for different h can be discovered by the adversary. The signer 452 SHOULD use some kind of pseudorandom function to achieve this. 454 Note: this ElGamal signature variant corresponds to type 4 ElGamal 455 signature in the Handbook of Applied Cryptography. 457 6.3 Menezes--Qu--Vanstone key agreement 459 To be completed. 461 7. IANA Considerations 463 This document requires no actions by IANA, yet. 465 8. Security considerations 467 No cryptographic algorithms is without risks. Consequently, risks 468 are comparative. This section will not fully list the risks of all 469 other forms of elliptic curve cryptography. Instead it will list 470 the most plausible risks of this curve, and only to a limited degree 471 contrast these to a few other standardized curves. 473 8.1. Field choice 475 The field 8^91+5 has the following risks. 477 Internet-Draft 2017 Oct 11 479 - 8^91+5 is a special prime. As such, it is perhaps vulnerable to 480 some kind of attack. For example, for some curve shapes, the 481 supersingularity depends on the prime, and the curve size is 482 related in a simple way to the field size, causing a potential 483 correlation between the field size and the effectiveness of an 484 attack, such as the Pohlig--Hellman attack. 486 Many other standard curves, such as the NIST P-256 and 487 Curve25519, also use special prime field sizes, so have a similar 488 risk. Yet other standard curves, such as the Brainpool, use 489 pseudorandom field sizes, so have less risk to this threat. 491 - 8^91+5, while implementable in five 64-bit words, has some risk of 492 overflowing, or of not fully reducing properly. Perhaps a smaller 493 field, such as that used in Curve25519, has a simpler reduction 494 and overflow-avoidance properties. 496 - 8^91+5, by virtue of being well-above 256 bits in size, risks its 497 user doing extra, and perhaps unnecessary, computation to protect 498 their 128-bit keys, whereas smaller curves might be faster (as 499 expected) yet still provide enough security. In other words, the 500 extra cost is wasteful, and partially a form of denial of service. 502 - 8^91+5, is smaller than 8^95-9, yet uses no fewer symbols. Since 503 larger field sizes lead to strong Pollard rho resistance, it can 504 be argued that this field size does not optimize security against 505 (specification) simplicity. (The main reason this document 506 prefers 8^91+5 over 8^95-9 is its simpler field inversion.) 507 Similarly, 8^91+5 is smaller than the six-symbol primes 9^99+4 and 508 9^87+4, but these are not close to powers of two, which means that 509 modular multiplication and reduction for them is not likely to be 510 as efficient as for 8^91+5. 512 - 8^91+5, is smaller than 2^283 (used by sect283k1 in Zigbee), and 513 many other five-symbol and four-symbol powers of primes (such as 514 9^97). So, it less to provide less resistance to Pollard rho. 515 Recent progress in the elliptic curve discrete logarithm problem, 516 [HPST] and [Nagao], is the main reason to prefer prime fields 517 instead of power of prime fields. A second reason to prefer prime 518 field 8^91+5 (and other large characteristic fields) over small 519 characteristic fields, is the generally better software speed of 520 large characteristic fields: which arises because most software is 521 implemented on a general purpose hardware processor that has fast 522 multiplication circuits. (This speed advantage probably does not 523 apply for hardware.) 525 Internet-Draft 2017 Oct 11 527 8.2. Curve choice 529 A first risk of using 2y^2=x^3+x is the fact that it is a special 530 curve, with complex multiplication leading to an efficient 531 endomorphism. Many other standard curves, NIST P-256, Curve25519, 532 Brainpool, do not have any efficient endomorphisms. Yet some 533 standard curves do, NIST K-283 and secp256k1 (in BitCoin). 534 Furthermore, it is not implausible [KKM] that special curves, 535 including those efficient endomorphisms, may survive an attack on 536 random curves. 538 A second risk of 2y^2=x^3+x over 8^91+5 is the fact that it is not 539 twist-secure. What may happen is that an implementer may use the 540 Montgomery ladder in Diffie--Hellman and re-use private keys. They 541 may think, despite the (ample?) warnings in this document, that 542 public key validation in unnecessary, modeling their implementation 543 after Curve25519 or some other twist-secure curve. This implementer 544 is at risk of an invalid public key attack. Moreover, the 545 implementer has an incentive to skip public-key validation, for 546 better performance. Finally, even if the implementer uses 547 public-key validation, then the cost of public-key validation is 548 non-negligible. 550 A third risk is a biased ephemeral private key generation in a 551 digital signature scheme. Most standard curve lack this risk 552 because the field is close to a power of two, and the cofactor is a 553 power of two. 555 A fourth risk is a Cheon-type attack. Few standard curves address 556 this risk. 558 A fifth risk is a small-subgroup confinement attack, which can also 559 leak a few bits of the private key. 561 8.3. Encoding choices 563 To be completed. 565 8.4. General subversion concerns 567 Although the main motivation of curve 2y^2=x^3+x over 8^91+5 is to 568 minimize the risk of subversion via a backdoor, such as the one 569 described by [Teske], it is only fair to point out that its 570 appearance in this very document can be viewed with suspicion as an 571 possible effort at subversion (via a front-door). (See [BCCHLV] for 572 some further discussion.) 574 Internet-Draft 2017 Oct 11 576 Any other standardized curve can be view with a similar suspicion 577 (except, perhaps, by the honest authors of those standards for whom 578 such suspicion seems absurd and unfair). A skeptic can then examine 579 both (a) the reputation of the (alleged) author of the standard, 580 making an ad hominem argument, and (b) the curve's intrinsic merits. 582 By the very definition of this document, the user is encouraged to 583 take an especially skeptical viewpoint of curve 2y^2=x^3+x over 584 8^91+5. So, it is expected that skeptical users of the curve will 585 either 587 - use the curve for its other merits (other than its backdoor 588 mitigations), such as efficient endomorphism, field inversion, 589 high Pollard rho resistance within five 64-bit words, meanwhile 590 holding to the evidence-supported belief ECC that is now so mature 591 that worries about subverted curves are just far-fetched nonsense, 592 or 594 - as an additional of layer of security in addition to other 595 algorithms (ECC or otherwise), as an extra cost to address the 596 non-zero probability of other curves being subverted. 598 To paraphrase, consider users seriously worried about subverted 599 curves (or other cryptographic algorithms), either because they 600 estimate as high either the probability of subversion or the value 601 of the data needing protection. These users have good reason to 602 like 2y^2=x^3+x over 8^91+5 for its compact description. 603 Nevertheless, the best way to resist subversion of cryptographic 604 algorithms seems to be combine multiple dissimilar cryptographic 605 algorithms, in a strongest-link manner. Diversity hedges against 606 subversion, and should the first defense against it. 608 8.5. Concerns about 'aegis' 610 The exact curve 2y^2=x^3+x over 8^91+5 was (seemingly) first 611 described to the public in 2017 [AB]. So, it has a very low age. 613 Furthermore, it has not been submitted for a publication with peer 614 review to any cryptographic forum such as the IACR conferences like 615 Crypto and Eurocrypt. So, it has been review by very few eyes, most 616 of which had little incentive to study it seriously. 618 Under the metric of aegis, as in age * eyes, it scores low. 619 Counting myself (but not quantifying incentive) it gets an aegis 620 score of 0.1 (using a rating 0.1 of my eyes factor in the aegis 621 score: I have not discovered any major ECC attacks of my own.) This 622 is far smaller than some more well-studied curves. 624 Internet-Draft 2017 Oct 11 626 However, in its defense, the curve 2y^2=x^3+x over 8^91+5 has 627 similarities to some of the better-studied curves with much higher 628 aegis: 630 - Curve25519: has field size 8^85-19, which a little similar to 631 8^91+5; has equation of the form by^2=x^3+ax+x, with b and a 632 small, which is similar to 2y^2=x^3+x. Curve25519 has been around 633 for over 10 years, has (presumably) many eyes looking at it, and 634 has been deployed thereby creating an incentive to study. An 635 estimated aegis score is 10000. 637 - P-256: has a special field size, and maybe an estimated aegis 638 score of 200000. (It is a high-incentive target. Also, it has 639 received much criticism, showing some intent of cryptanalysis. 640 Indeed, there has been incremental progress in finding minor 641 weakness (implementation security flaws), suggestive of actual 642 cryptanalytic effort.) The similarity to 2y^2=x^3+x over 8^91+5 643 is very minor, so very little of the P-256 aegis would be relevant 644 to this document. 646 - secp256k1: has a special field size, though not quite as special 647 as 8^91+5, and has special field equation with an efficient 648 endomorphism by a low-norm complex algebraic integer, quite 649 similar to 2y^2=x^3+x. It is about 17 years old, and though not 650 studied much in academic work, its deployment in Bitcoin has at 651 least created an incentive to attack it. An estimated aegis score 652 is 10000. 654 - Miller's curve: Miller's 1985 paper introducing ECC suggested, 655 among other choices, a curve equation y^2=x^3-ax, where a is a 656 quadratic non-residue. Curve 2y^2=x^3+x is isomorphic to 657 y^2=x^3-x, which is essentially one of Miller's curves, except 658 that a=1 is a quadratic residue. Miller's curve has not been 659 studied directly, but probably much more so than this than the 660 curve in this document. Miller also hinted that it was not 661 prudent to use a special curve y^2=x^3-ax: such a comment may have 662 encourage some cryptanalysts, but discouraged cryptographers, 663 perhaps balancing out the effect on the eyes factor the aegis 664 score. An estimate aegis score is 300. 666 Obvious cautions to the reader: 668 - Small changes in a cryptographic algorithm sometimes cause large 669 differences in security. So security arguments based on 670 similarity in cryptographic schemes should be given low priority. 672 Internet-Draft 2017 Oct 11 674 - Security flaws have sometimes remained undiscovered for years, 675 despite both incentives and peer reviews (and lack of hard 676 evidence of conspiracy). So, the eyes-part of the aegis score is 677 very subjective, and perhaps vulnerable false positives by a herd 678 effect. Despite this caveat, it is not recommended to ignore the 679 eyes factor in the aegis score: don't just flip through old books 680 (of say, fiction), looking for cryptographic algorithms that might 681 never have been studied. 683 9. References 685 9.1. Normative References 687 [BCP14] Bradner, S., "Key words for use in RFCs to Indicate 688 Requirement Levels", BCP 14, RFC 2119, March 1997, 689 . 691 9.2. Informative References 693 To be completed. 695 [AB] A. Allen and D. Brown. ECC mod 8^91+5, presentation to CFRG, 696 2017. 697 699 [KKM] A. Koblitz, N. Koblitz and A. Menezes. Elliptic Curve 700 Cryptography: The Serpentine Course of a Paradigm Shift, IACR 701 ePrint, 2008. 703 [BCCHLV] D. Bernstein, T. Chou, C. Chuengsatiansup, A. Hulsing, 704 T. Lange, R. Niederhagen and C. van Vredendaal. How to 705 manipulate curve standards: a white paper for the black 706 hat, IACR ePrint, 2014. 708 [Elligator] To do: fill in this reference. 710 [NIST-P-256] To do: NIST recommended 15 elliptic curves for 711 cryptography, the most popular of which is P-256. 713 [Zigbee] To do: Zigbee allows the use of a small-characteristic 714 special curve, which was also recommended by NIST, called K-283, and 715 also known as sect283k1. These types of curves were introduced by 716 Koblitz. These types of curves were not recommended by NSA in Suite 717 B. 719 [Brainpool] To do: the Brainpool consortium (???) recommended some 720 elliptic curves in which both the field size and the curve equation 721 were derived pseudorandomly from a nothing-up-my-sleeve number. 723 Internet-Draft 2017 Oct 11 725 [SEC2] Standards for Efficient Cryptography. SEC 2: Recommended 726 Elliptic Curve Domain Parameters, version 2.0, 2010. 727 729 [IT] T. Izu and T. Takagi. Exceptional procedure attack on elliptic 730 curve cryptosystems, Public key cryptography -- PKC 2003, 731 Lecture Notes in Computer Science, Springer, pp. 224--239, 732 2003. 734 [PSM] To do: Projective coordinates leak. Pointcheval, Smart, 735 Malone-Lee? 737 [BitCoin] To do: BitCoin uses curve secp256k1, which has an 738 efficient endomorphism. 740 [Bleichenbacher] To do: Bleichenbacher showed how to attack DSA 741 using a bias in the per-message secrets. 743 [Gordon] To do: Gordon showed how to embed a trapdoor in DSA 744 parameters. 746 [HPST] Y. Huang, C. Petit, N. Shinohara and T. Takagi. On 747 Generalized First Fall Degree Assumptions, IACR ePrint 2015. 748 750 [Nagao] K. Nagao. Equations System coming from Weil descent and 751 subexponential attack for algebraic curve cryptosystem, IACR 752 ePrint, 2015. 754 [Teske] E. Teske. An Elliptic Curve Trapdoor System, IACR ePrint, 755 2003. 757 [YY] To do: Yung and Young, generalized Gordon's ideas [Gordon] into 758 Secretly-embedded trapdoor ... also known as a backdoor. 760 Appendix A. Test vectors 762 To be completed. 764 Appendix B. Motivation: minimizing the room for backdoors 766 To be completed. 768 See [AB] for some details. 770 The field and curve are described with very few symbols, while 771 retaining many basic security and speed features. 773 Internet-Draft 2017 Oct 11 775 A prime field was chosen due to recent asymptotic advances on 776 discrete logarithms in low-characteristic fields [HPST] and 777 [Nagao]. According to [Teske], some characteristic-two elliptic 778 curves could be equipped with a secretly embedded backdoor. 780 Note: this curve is isomorphic to the non-Montgomery curve 781 y^2=x^3-x, which requires just 9 symbols in its description, 1 782 fewer than required by 2y^2=x^3+x. 784 Appendix C. Pseudocode 786 This section uses a C-like pseudocode to describe some of the 787 algorithms useful for implementing this curve. 789 Real-world implementations adapting this pseudocode had better 790 harden this pseudocode against real-world implementation issues. 791 Better yet, real-world code could start from scratch, using the 792 pseudocode only for comparison. 794 Note: the pseudocode relies on some C idioms (hacks?), which might 795 make the pseudocode unclear to those unfamiliar with these idioms. 797 Note: this pseudocode was adapted from a few different 798 experimental prototypes of the author, (which might not be 799 consistent). The pseudocode has not yet received any independent 800 review. 802 Note: this pseudocode uses a terse non-conventional coding style, 803 partly as an exercise in arbitrary source code compression (code 804 golf), but also in the mathematics tradition of using many 805 single-letter variable names, which enables seeing an entire 806 formula in a single view and emphasizes the essential mathematical 807 operations rather than the variable's purpose. 809 Note: the pseudocode does not use the C operator ^ for bitwise XOR 810 of integers, which (luckily) avoid possible confusion with the use 811 of ^ as exponentiation operator in the rest of this document. 813 Internet-Draft 2017 Oct 11 815 C.1. Byte encoding 817 Pseudocode for byte representation encoding process is 819 bite(c b,f x) { 820 i j=34,k=5; f t; 821 mal(t,-1,x); 822 mal(x,cmp(t,x),x); 823 fix(x); 824 for(;j--;) b[j]=x[j/7]>>((8*j)%55); 825 for(;--k;) b[7*k-1]+=x[k]<<(8-k); 826 } 828 The input variable is x and the output variable is b. The declared 829 types and functions are as follows: 831 - type c: curve representative, length-34 array of non-negative 832 8-bit integers ("characters"), 834 - type f: field element, a length-5 array of 64-bit integers 835 (negatives allowed), representing a field element as an integer in 836 base 2^55, 838 - type i: 64-bit integers (e.g. entries of f), 840 - function mal: multiply a field element by a small integer (result 841 stored in 1st argument), 843 - function fix: fully reduce an integer modulo 8^91+5, 845 - function cmp: compare two field element (after fixing), returning 846 -1, 0 or 1. 848 Note: The two for-loops in the pseudocode are just radix 849 conversion, from base 2^55 to base 2^8. Because both bases are 850 powers of two, this amount to moving bits around. The entries of 851 array b are compute modulo 256. The second loop copies the bits 852 that the first loop misses (the bottom bits of each entry of f). 854 Note: Encoding is lossy, several different (x,y) may encode to the 855 same byte string b. Usually, if (x,y) generated as a part of 856 Diffie--Hellman key exchange, this lossiness has no effect. 858 Note: Encoding should not be confused with encryption. Encoding 859 is merely a conversion or representation process, whose inverse is 860 called decoding. 862 Internet-Draft 2017 Oct 11 864 C.2. Byte decoding 866 Pseudocode for decoding is: 868 feed(f x,c b) { 869 i j=34; 870 mal(x,0,x); 871 for(;j--;) x[j/7]+=((i)b[j])<<((8*j)%55); 872 fix(x); 873 } 875 with similar conventions as used in the pseudocode function bite 876 (defined in the section on encoding), and some extra conventions: 878 - the expression (i)b[j] means that 8-bit integer b[j] is converted 879 to a 64-bit integer (so is no longer treated modulo 256). (In C, 880 this is operation is called casting.) 882 Note: the decode function 'feed' only has 1 for-loop, which is the 883 approximate inverse of the first of the 2 for-loops in the encode 884 function 'bite'. The reason the 'bite' needs the 2nd for-loop is 885 due to the lossy conversion from integers to bytes, whereas in the 886 other direction the conversion is not lossy. The second loop 887 recovers the lost information. 889 C.3. Fermat inversion 891 Projective coordinates help avoid costly inversion steps during 892 scalar multiplication. 894 Projective coordinates are not suitable as the final representation 895 of an elliptic curve point, for two reasons. 897 - Projective coordinates for a point are generally not unique: each 898 point can be represented in projective coordinates in multiple 899 different ways. So, projective coordinates are unsuitable for 900 finalizing a shared secret, because the two parties computing the 901 shared secret point may end up with different projective 902 coordinates. 904 - Projective coordinates have been shown to leak information about 905 the scalar multiplier [PSM], which could be the private 906 key. It would be unacceptable for a public key to leak 907 information about the private key. In digital signatures, even a 908 few leaked bits can be fatal, over a few signatures 909 [Bleichenbacher]. 911 Internet-Draft 2017 Oct 11 913 Therefore, the final computation of an elliptic curve point, after 914 scalar multiplication, should translate the point to a unique 915 representation, such as the affine coordinates described in this 916 report. 918 For example, when using a Montgomery ladder, scalar multiplication 919 yields a representation (X:Z) of the point in projective 920 coordinates. Its x-coordinate is then x=X/Z, which can be computed 921 by computing the 1/Z and then multiplying by X. 923 The safest, most prudent way to compute 1/Z is to use a side-channel 924 resistant method, in particular at least, a constant-time method. 925 This reduces the risk of leaking information about Z, which might in 926 turn leak information about X or the scalar multiplier. Fermat 927 inversion, computation of Z^(p-2) mod p, is one method to compute 928 the inverse in constant time (if the inverse exists). 930 Pseudocode for Fermat inversion is: 932 i inv(f y,f x) { 933 i j=272;f z; 934 squ(z,x); 935 mul(y,x,z); 936 for(;j--;) squ(z,z); 937 mul(y,z,y); 938 return !!cmp(y,(f){}); 939 } 941 Other inversion techniques, such as the binary extended GCD, may be 942 faster, but generally run in variable-time. 944 When field elements are sometimes secret keys, using a variable-time 945 algorithm risk leaking these secrets, and defeating security. 947 C.4. Branchless Legendre symbol computation 949 Pseudocode for branchlessly computing if a field element x has a 950 square root: 952 i has_root(f x) { 953 i j=270;f y,z; 954 squ(y,x);squ(z,y); 955 for(;j--;)squ(z,z); 956 mul(y,y,z); 957 return 0==cmp(y,(f){1}); 958 } 960 Internet-Draft 2017 Oct 11 962 Note: Legendre symbol is usually most appropriately applied to 963 public keys, which mostly obviates the need for side-channel 964 resistance. In this case, the implementer can use quadratic 965 reciprocity for greater speed. 967 C.5. Field multiplication and squaring 969 To be completed. 971 Note (on security): Field multiplication can be achieved most 972 quickly by using hardware integer multiplication circuits. It is 973 critical that those circuits have no bugs or backdoors. 974 Furthermore, those circuits typically can only multiple integers 975 smaller than the field elements. Larger inputs to the circuits 976 will cause overflows. It is critical to avoid these overflows, 977 not just to avoid interoperability failures, but also to avoid 978 attacks where the attackers supplies inputs likely induce 979 overflows [bug attacks], [IT]. The following pseudocode 980 should therefore be considered only for illustrative purposes. 981 The implementer is responsible for ensuring that inputs cannot 982 cause overflows or bugs. 984 The pseudocode below for multiplying and squaring: uses unrolled 985 loops for efficiency, uses refactoring for source code compression, 986 relies on a compiler optimizer to detect common sub-expressions (in 987 squaring). 989 #define TRI(m,_)\ 990 zz[0]=m(0,0)_(1,4)_(2,3)_(3,2)_(4,1);\ 991 zz[1]=m(0,1)_(1,0)_(2,4)_(3,3)_(4,2);\ 992 zz[2]=m(0,2)_(1,1)_(2,0)_(3,4)_(4,3);\ 993 zz[3]=m(0,3)_(1,2)_(2,1)_(3,0)_(4,4);\ 994 zz[4]=m(0,4)_(1,3)_(2,2)_(3,1)_(4,0); 995 #define CYC(M) ff zz; TRI(+M,-20*M); mod(z,zz); 996 #define MUL(j,k) x[j]*(ii)y[k] 997 #define SQR(j,k) x[j]*(ii)x[k] 998 #define SQU(j,k) SQR(j>k?j:k,j>55) 1041 #define MOD(x)(x&((((i)1)<<5)-1)) 1042 #define Q(j) QUO(QUO(zz[j])) 1043 #define P(j) MOD(QUO(zz[j])) 1044 #define R(j) MOD(zz[j]) 1045 mod(f z,ff zz){ 1046 z[0]=R(0)-P(4)*20-Q(3)*20; 1047 z[1]=R(1)-P(0)-Q(4)*20; 1048 z[2]=R(2)-P(1)-Q(0); 1049 z[3]=R(3)-P(2)-Q(1); 1050 z[4]=R(4)-P(3)-Q(2); 1051 z[1]+=QUO(z[0]); 1052 z[0]=MOD(z[0]); 1053 } 1055 TO DO: add notes answering these questions: 1057 - How small must be the input limbs to avoid overflow? 1059 Internet-Draft 2017 Oct 11 1061 - How small are the output limbs (to know how to safely use of 1062 output in further calculations). 1064 C.7. Field element final reduction 1066 To be completed. 1068 The partial reduction technique is sometimes known as lazy 1069 reduction. It is an optimization technique. It aims to do only 1070 enough calculation to avoid overflow errors. 1072 For interoperability, field elements need to be fully reduced, 1073 because partial reduction means the elements still have multiple 1074 different representations. 1076 Pseudocode that aims for final reduction is the following: 1078 #define FIX(j,r,k) {q=x[j]>>r;\ 1079 x[j]-=q<>53; 1085 } 1087 C.8. Scalar point multiplication 1089 Work in progress. 1091 A recommended method of scalar point multiplication is the 1092 Montgomery ladder. However, the curve 2y^2=x^3+x has an efficient 1093 endomorphism. So, this can be used to speed-up scalar point 1094 multiplication, as suggested by Gallant, Lambert and Vanstone. 1096 Combining both GLV and Montgomery is also possible, such as 1097 suggested as by Bernstein. 1099 Note: The following pseudocode is not entirely consistent with 1100 previous pseudocode examples. 1102 Note and Warning: The following pseudocode uses secret indices to 1103 access (small) arrays. This has a risk of cache-timing attacks. 1105 Internet-Draft 2017 Oct 11 1107 typedef f p[2]; 1108 typedef struct rung {i x0; i x1; i y; i z;} k[137]; 1109 monty_2d (f ps,k sk,f px) { 1110 i j,h; f z; p w[3],x[3],y[2]={{{},{1}}},z[2]; 1111 fix(px);mal(y[0][0],1,px); 1112 endomorphism_1_plus_i(z[0],px); 1113 endo_i(y[1],y[0]); endo_i(z[1],z[0]); 1114 copy(x[1],y[0]); copy(x[2],z[0]); 1115 double_xz(x[0],y[0]); 1116 for(j=0;j<137;j+=){ 1117 double_xz(w[0], x[sk[j].x0 /* cache attack here? */ ]); 1118 diff_add (w[1],x[1],x[sk[j].x1],y[sk[j].y]); 1119 diff_add (2[2],x[2],x[0], z[sk[j].z]); 1120 for(h=0;h<3;h++) {copy(x[h],w[h]);} 1121 } 1122 inv(ps,x[1][1]); 1123 mul(ps,x[1][0],ps); 1124 fix(ps); 1125 } 1127 Note: The pseudocode uses some other functions not defined here, 1128 but whose meaning can be inferred by ECC experts. 1130 Note: The pseudocode uses a specialized format for the scalar. 1131 Normal scalars would have to be re-coded into this format, and 1132 re-coding has non-negligible run-time. Perhaps in 1133 Diffie--Hellman, re-coding is not necessary if one can ensure that 1134 uniformly selection of coded scalars is not a security risk. 1136 TO DO: 1137 - Define the functions used by monty_2d. 1138 - Prove that these function avoid overflow. 1139 - Define functions to re-code scalars for monty_2d. 1141 C.9. Diffie--Hellman pseudocode 1143 To be completed. 1145 This pseudocode would show how to use to scalar multiplication, 1146 combined with point validation, and so on. 1148 C.10. Elligator i 1150 To be completed. 1152 Internet-Draft 2017 Oct 11 1154 This pseudocode would show how to implement to the Elligator i map 1155 from byte strings to points. 1157 Pseudocode (to be verified): 1159 typedef f xy[2] ; 1160 #define X p[0] 1161 #define Y p[1] 1162 lift(xy p, f r) { 1163 f t ; i b ; 1164 fix(r); 1165 squ(t,r); // r^2 1166 mul(t,I,t); // ir^2 1167 sub(t,(f){1},t); // 1-ir^2 1168 inv(t,t); // 1/(1-ir^2) 1169 mal(t,3,t); // 3/(1-ir^2) 1170 mul(t,I,t); // 3i/(1-ir^2) 1171 sub(X,I,t); // i-3i/(1-ir^2) 1172 b = get_y(t,X); 1173 mal(t,1-b,I); // (1-b)i 1174 add(X,X,t); // EITHER x OR x + i 1175 get_y(Y,X); 1176 mal(Y,2*b-1,Y); // (-1)^(1-b)"" 1177 fix(X); fix(Y); 1178 } 1180 drop(f r, xy p) 1181 { 1182 f t ; i b,h ; 1183 fix(X); fix(Y); 1184 get_y(t,X); 1185 b=eq(t,Y); 1186 mal(t,1-b,I); 1187 sub(t,X,t); // EITHER x or x-i 1188 sub(t,I,t); // i-x 1189 inv(t,t); // 1/(i-x) 1190 mal(t,3,t); // 3/(i-x) 1191 add(t,I,t); // i+ 3/(i-x) 1192 mal(t,-1,t); // -i-3/(i-x)) = (1-3i/(i-x))/i 1193 b = root(r,t) ; 1194 fix(r); 1195 h = (r[4]<(1LL<<52)) ; 1196 mal(r,2*h-1,r); 1197 fix(r); 1198 } 1200 Internet-Draft 2017 Oct 11 1202 elligator(xy p,c b) {f r; feed(r,b); lift(p,r);} 1204 crocodile(c b,xy p) {f r; drop(r,p); bite(b,r);} 1206 Acknowledgments 1208 Thanks to John Goyo and various other BlackBerry employees for past 1209 technical review, to Gaelle Martin-Cocher for encouraging 1210 submission of this I-D. 1212 Author's Address 1214 Dan Brown 1215 4701 Tahoe Blvd. 1216 BlackBerry, 5th Floor 1217 Mississauga, ON 1218 Canada 1219 danibrown@blackberry.com