idnits 2.17.1 draft-struik-lamps-verification-friendly-ecdsa-01.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an Introduction section. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (March 11, 2021) is 1142 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Unused Reference: 'FIPS-186-4' is defined on line 392, but no explicit reference was found in the text == Unused Reference: 'I-D.ietf-lwig-curve-representations' is defined on line 398, but no explicit reference was found in the text == Unused Reference: 'SEC1' is defined on line 439, but no explicit reference was found in the text == Unused Reference: 'SEC2' is defined on line 442, but no explicit reference was found in the text == Unused Reference: 'ECC' is defined on line 447, but no explicit reference was found in the text == Unused Reference: 'GECC' is defined on line 451, but no explicit reference was found in the text -- Possible downref: Non-RFC (?) normative reference: ref. 'FIPS-186-4' == Outdated reference: A later version (-23) exists of draft-ietf-lwig-curve-representations-19 ** Downref: Normative reference to an Informational draft: draft-ietf-lwig-curve-representations (ref. 'I-D.ietf-lwig-curve-representations') ** Downref: Normative reference to an Informational RFC: RFC 8032 -- Possible downref: Non-RFC (?) normative reference: ref. 'SEC1' -- Possible downref: Non-RFC (?) normative reference: ref. 'SEC2' Summary: 3 errors (**), 0 flaws (~~), 8 warnings (==), 4 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 lamps R. Struik 3 Internet-Draft Struik Security Consultancy 4 Intended status: Standards Track March 11, 2021 5 Expires: September 12, 2021 7 ECDSA Signatures in Verification-Friendly Format 8 draft-struik-lamps-verification-friendly-ecdsa-01 10 Abstract 12 This document specifies how to represent ECDSA signatures so as to 13 facilitate accelerated verification of single signatures and fast 14 batch verification. We demonstrate that this representation 15 technique can be applied retroactively by any device (rather than 16 only by the signer), thereby facilitating transitioning to always 17 generating ECDSA signatures in this way, without changing 18 standardized ECDSA specifications. This facilitates verifying 19 devices to reap the significant speed-up potential (ranging from 20 ~1.3x to more than 2x) fast verification techniques afford. 22 Requirements Language 24 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 25 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 26 "OPTIONAL" in this document are to be interpreted as described in BCP 27 14 [RFC2119] [RFC8174] when, and only when, they appear in all 28 capitals, as shown here. 30 Status of This Memo 32 This Internet-Draft is submitted in full conformance with the 33 provisions of BCP 78 and BCP 79. 35 Internet-Drafts are working documents of the Internet Engineering 36 Task Force (IETF). Note that other groups may also distribute 37 working documents as Internet-Drafts. The list of current Internet- 38 Drafts is at https://datatracker.ietf.org/drafts/current/. 40 Internet-Drafts are draft documents valid for a maximum of six months 41 and may be updated, replaced, or obsoleted by other documents at any 42 time. It is inappropriate to use Internet-Drafts as reference 43 material or to cite them other than as "work in progress." 45 This Internet-Draft will expire on September 12, 2021. 47 Copyright Notice 49 Copyright (c) 2021 IETF Trust and the persons identified as the 50 document authors. All rights reserved. 52 This document is subject to BCP 78 and the IETF Trust's Legal 53 Provisions Relating to IETF Documents 54 (https://trustee.ietf.org/license-info) in effect on the date of 55 publication of this document. Please review these documents 56 carefully, as they describe your rights and restrictions with respect 57 to this document. Code Components extracted from this document must 58 include Simplified BSD License text as described in Section 4.e of 59 the Trust Legal Provisions and are provided without warranty as 60 described in the Simplified BSD License. 62 Table of Contents 64 1. Fostering Fast Verification with ECDSA . . . . . . . . . . . 2 65 2. Review of ECDSA and ECDSA* . . . . . . . . . . . . . . . . . 3 66 3. Signature Verification with ECDSA and ECDSA* . . . . . . . . 4 67 4. Transitionary Considerations . . . . . . . . . . . . . . . . 5 68 5. Implementation Status . . . . . . . . . . . . . . . . . . . . 6 69 6. Informal Comparison with Speed-ups for EdDSA Signatures . . . 6 70 7. Security Considerations . . . . . . . . . . . . . . . . . . . 7 71 8. Privacy Considerations . . . . . . . . . . . . . . . . . . . 7 72 9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 7 73 9.1. OIDs for Use with PKIX and CMS . . . . . . . . . . . . . 7 74 10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 9 75 11. References . . . . . . . . . . . . . . . . . . . . . . . . . 9 76 11.1. Normative References . . . . . . . . . . . . . . . . . . 9 77 11.2. Informative References . . . . . . . . . . . . . . . . . 10 78 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 10 80 1. Fostering Fast Verification with ECDSA 82 ECDSA is one of the most widely used elliptic-curve digital signature 83 algorithms. It has been standardized in FIPS Pub 186-4, ANSI X9.62, 84 BSI, SECG, and IETF, and is widely deployed by a plethora of internet 85 protocols specified by the Internet Engineering Task Force (IETF), 86 with industry specifications in the areas of machine-to-machine 87 communication, such as ZigBee, ISA, and Thread, with wireless 88 communication protocols, such as IEEE 802.11, with payment protocols, 89 such as EMV, with vehicle-to-vehicle (V2V) specifications, as well as 90 with electronic travel documents and other specifications developed 91 under a more stringent regulatory oversight regime, such as, e.g., 92 ICAO and PIV. ECDSA is the only elliptic-curve based signature 93 scheme endorsed by regulatory bodies in both the United States and 94 the European Union. 96 While methods for accelerated verification of ECDSA signatures and 97 for combining this with key computations have been known for over 1 98 1/2 decade (see, e.g., [SAC2005] and [SAC2010]), these have been 99 commonly described in technical papers in terms of ECDSA*, a slightly 100 modified version of ECDSA, where their use with standardized ECDSA 101 seems less well known. It is the purpose of this document to bridge 102 this gap and describe how ECDSA signatures can be easily generated to 103 facilitate more efficient verification, without failing. We 104 emphasize that this does not require changes to standardized 105 specifications of ECDSA, thereby allowing reuse of existing standards 106 and easy integration with existing implementations. We exemplify 107 this for ECDSA certificates. 109 2. Review of ECDSA and ECDSA* 111 In this section, we summarize the properties of the signature scheme 112 ECDSA and of the modified signature scheme ECDSA* that are relevant 113 for our exposition. The signature schemes are defined in terms of a 114 suitable elliptic curve E, hash function H, and several 115 representation functions, where n is the (prime) order of the base 116 point G of this curve, and where E is an elliptic curve in short- 117 Weierstrass form. For full details, we refer to the relevant 118 standards. 120 With the ECDSA signature scheme, the signature over a message m 121 provided by a signing entity with static private key d is an ordered 122 pair (r,s) of integers in the interval [1,n-1], where the value r is 123 derived from a so-called ephemeral signing key R:=k*G generated by 124 the signer via a fixed public conversion function and where the value 125 s is a function of the ephemeral private key k, the static private 126 key d, the value r and the value e derived from message m via hash 127 function H and representation hereof in the interval [0,n-1]. (More 128 specifically, one has e=s*k-d*r (mod n), where r is a function of the 129 x-coordinate of R.) A signature (r,s) over message m purportedly 130 signed by an entity with public key Q:=d*G is accepted if Q is indeed 131 a valid public key, if both signature components r and s are integers 132 in the interval [1,n-1] and if the reconstructed value R' derived 133 from the purported signature, message, and public key yields r, via 134 the same fixed conversion function as used during the signing 135 operation. (More specifically, one computes R':=(1/s)*(e*G+r*Q) and 136 checks that r is the same function of the x-coordinate of R'.) 138 With the ECDSA* signature scheme, one follows the same signing 139 operation, except that one outputs as signature the ordered pair 140 (R,s), rather than the pair (r,s), where R is the ephemeral signing 141 key; one accepts a signature (R,s) over message m purportedly signed 142 by an entity with public key Q by first computing the value r derived 143 from signature component R via the conversion function, checking that 144 Q is indeed a valid public key and that both r and s are integers in 145 the interval [1,n-1], computing R':=(1/s)*(e*G+r*Q) and checking 146 whether, indeed, R'=R. 148 It is known that ECDSA signatures and the corresponding ECDSA* 149 signatures have the same success/failure conditions (i.e., ECDSA and 150 ECDSA* are equally secure): if (r,s) is a valid ECDSA signature for 151 message m purportedly signed by an entity with public key Q, then 152 (R',s) is a valid corresponding ECDSA* signature, where R':=(1/ 153 s)(e*G+r*Q) is a point for which the conversion function yields r. 154 Conversely, if (R,s) is a valid ECDSA* signature for message m 155 purportedly signed by an entity with public key Q, then (r,s) is a 156 valid corresponding ECDSA signature, where r is obtained from R via 157 the conversion function. 159 It is well-known that if an ECDSA signature (r,s) is valid for a 160 particular message m and public key Q, then so is (r,-s) -- the so- 161 called malleability -- and that, similarly, if an ECDSA* signature 162 (R,s) is valid, then so is (-R,-s), where this relies on the fact 163 that the conversion function only depends on the x-coordinate of R. 165 3. Signature Verification with ECDSA and ECDSA* 167 In this section, we more closely scrutinize ECDSA and ECDSA* 168 verification processes. 170 With ECDSA*, signature verification primarily involves checking an 171 elliptic curve equation, viz. checking whether R = (1/s)*(e*G+r*Q), 172 which lends itself to accelerated signature verification techniques 173 and the ability to use batch verification techniques, with 174 significant potential for accelerated verification (with ~1.3x and up 175 and more than 2x speed-up potential, respectively). Here, speed-ups 176 are due to the availability of the point R, which effectively allows 177 checking an equation of the form -s*R + (e*G+r*Q)=O instead (where O 178 is the identity element of the curve). Similarly to the case with 179 EdDSA [RFC8032] (which natively represents the ephemeral signing key 180 R as part of the signature), this offers the potential for batch 181 verification, by checking a randomized linear combination of this 182 equation instead (thereby sharing the so-called point doubling 183 operations amongst all individual verifications and, potentially, 184 sharing scalars for signers of more than one message). In the case 185 of single verifications, efficient tricks allow reducing the bit-size 186 of the scalars involved in evaluating this expression (thereby 187 effectively halving the required point doubling operations). 189 With ECDSA itself, these techniques are generally not available, 190 since one cannot uniquely (and efficiently) reconstruct R from r: 191 both R and -R yield the same r value. If the conversion function 192 only has two pre-images, though, one can use malleability to remove 193 ambiguity altogether. 195 The modified ECDSA signing procedure is as follows: 197 a. Generate ECDSA signature (r,s) of message m; 199 b. If the ephemeral signing key R has odd parity of the 200 y-coordinate, change (r,s) to (r,-s). 202 Note that this modified signing procedure removes the ambiguity in 203 the reconstruction of R from r if the conversion function would 204 otherwise only have two preimages, since R and -R have different 205 parity of the y-coordinate. In practice, this is the case for all 206 prime-order curves, including the NIST prime curves P-256, P-384, 207 P-521, all standardized Brainpool curves, and, e.g., the "BitCoin" 208 curve secp256k1. (This follows from the observation that, for prime- 209 order curves, r generally uniquely represents the x-coordinate of R.) 211 NOTE: With ECDSA, any party (not just the signer) can recompute the 212 ephemeral signing key R' from a valid signature, since R':=(1/ 213 s)(e*G+r*Q). In particular, any party can retroactively put the 214 ECDSA signature in the required form above, thereby allowing 215 subsequent unique reconstruction of the R value from r by verifying 216 entities that know this modified signing procedure was indeed 217 followed (again, subject to the assumption that r would only have two 218 preimages otherwise, as is generally the case with prime-order 219 curves). 221 One can extend this technique to also apply to curves that have a 222 small co-factor h, e.g., h=4 or h=8 (rather than h=1, as is the case 223 with prime-order curves). This extension is out of scope for the 224 current document. 226 4. Transitionary Considerations 228 The modified signing procedure described in Section 3 facilitates the 229 use of accelerated ECDSA verification techniques by devices that wish 230 to do so, provided these know that this modified signing procedure 231 was indeed followed. This can be realized explicitly via a new 232 "fast-verification-friendly" label (e.g., OID) indicating that this 233 was indeed the case. This has the following consequences: 235 a. New device: accept both old and new label and apply speed-ups 236 with new label if possible (and desired); 238 b. Old device: implement flimsy parser that replaces new label by 239 old label and proceed as with traditional ECDSA verification. 241 Note that this parser "label replacement" step is a public operation, 242 so any interface can implement this step. 244 A label can also be realized implicitly (e.g., by stipulating the 245 modified signing procedure in protocol specifications that use ECDSA 246 signatures), where the benefit of not having to introduce a new label 247 explicitly should be weighed against potential disadvantages of 248 implicit labels, such as requiring extra care with specification work 249 to avoid confusion and the likely need to reintroduce an explicit 250 label if ECDSA signatures are processed outside the original context 251 (e.g., using a generic crypographic token). 253 As suggested before, any device can implement the modified ECDSA 254 signing procedure retroactively, so one could conceivably implement 255 this once for all existing ECDSA signatures and only use "new" labels 256 once this task has been completed (i.e., old labels could be 257 mothballed from then on). 259 NOTE: the above labeling procedures assume that old and new labels 260 are not part of the message to be signed. If they are, one may not 261 be able to mothball old labels. In this case, signing devices should 262 always use the old label during ECDSA signing and only change this to 263 the corresponding new label afterwards, whereby verifying devices 264 always replace the new label (since simply a pseudonym) by the 265 corresponding old label before processing the ECDSA signature. This 266 ensures that the signature semantics are not impacted and that old 267 devices' ECDSA verification implementations (after reinstating old 268 labels) work as is, while still being able to flag verification- 269 friendly ECDSA signature formatting. 271 5. Implementation Status 273 [Note to the RFC Editor] Please remove this entire section before 274 publication, as well as the reference to [RFC7942]. 276 The ECDSA* signature scheme has been implemented in V2V 277 specifications [P1609.2], where ECDSA is used with the NIST curves 278 P-224 and P-256. 280 6. Informal Comparison with Speed-ups for EdDSA Signatures 282 The main message of this draft is as follows (no crypto required, 283 except believing that the third step below works): 285 a. EdDSA [RFC8032] does allow speedy signature verification and 286 batch verification, since the signature is (R,s), i.e., it 287 represents the ephemeral signing key R as part of the signature; 289 b. With ECDSA, the signature is (r,s), where r is derived from the 290 signing key R (essentially, r is the x-coordinate of R if the 291 curve has co-factor h=1). However, generally, one cannot go back 292 and get (r,s) --> (R,s), at least not efficiently; 294 c. If one uses the modified ECDSA signing procedure of Section 3, 295 one can, though, thereby allowing similar accelerations (30% and 296 up) for signature verification as EdDSA does. This can be viewed 297 as "point compression" (since it determines which of R and -R 298 apply); 300 d. The rest is detail, where the ideas underlying the speed-ups 301 informally described in Section 3 are described in detail in the 302 papers [SAC2005] and [SAC2010]. 304 7. Security Considerations 306 The signature representation change described in this document is 307 publicly known and, therefore, does not affect security provisions. 308 Obviously, any adversary could change the signature value in a 309 malicious way, so as to make signature verification fail. This does, 310 however, not extend capabilities the adversary already had. 312 8. Privacy Considerations 314 The signature representation change described in this document is 315 publicly known and, therefore, does not affect privacy provisions. 317 9. IANA Considerations 319 This section requests the following IANA code point assignments. 321 Editorial Note: the approach below is simply one way of realizing 322 ECDSA* functionality. Other options to consider include, e.g., 323 introducing a non-critical extension as label, where old devices can 324 simple ignore this. This will be elaborated upon further in next 325 versions of this draft, after feedback. 327 9.1. OIDs for Use with PKIX and CMS 329 This section registers the following object identifiers for the 330 verification-friendly version of ECDSA introduced in this document: 332 a. id-ecdsa-star-with-sha256 ::= {iso(1) identified-organization(3) 333 thawte (101) (100) 81}; 335 b. id-ecdsa-star-with-sha384 ::= {iso(1) identified-organization(3) 336 thawte (101) (100) 82}; 338 c. id-ecdsa-star-with-sha512 ::= {iso(1) identified-organization(3) 339 thawte (101) (100) 83}; 341 d. id-ecdsa-star-with-shake128 ::= {iso(1) identified- 342 organization(3) thawte (101) (100) 84}; 344 e. id-ecdsa-star-with-shake256 ::= {iso(1) identified- 345 organization(3) thawte (101) (100) 85}. 347 Each of these object identifiers indicates the use of ECDSA with the 348 indicated hash function, as the corresponding object identifiers 349 without the "-star-" substring specified in [RFC5480] (for ECDSA with 350 SHA2-hash family members) and in [RFC8692] (for ECDSA with SHAKE 351 family members) do, where the "-star-" substring simply indicates 352 that the modified signing procedure specified in Section 3 of this 353 document was indeed used. 355 These new object identifiers are used with PKIX certificates and CMS 356 in the same way as the corresponding object identifiers without the 357 "-star-" substring, except that verifying devices now have the option 358 to implement ECDSA signature verification as if ECDSA* signatures had 359 been used, since the new object identifiers indicate the modified 360 signing operation was followed, as illustrated in Section 3 of this 361 document. 363 As mentioned in Section 4, any ECDSA signature with the old object 364 identifier can be changed retroactively to one with the corresponding 365 new object identifier, provided one has assurance that the modified 366 ECDSA signing procedure was indeed followed and, conversely, any 367 ECDSA signature with the new object identifier can be changed to one 368 with the corresponding old object identifier, without change in 369 semantics (assuming these object identifiers are not part of the 370 message that is signed). 372 With [RFC5280], the signature algorithm is indicated twice: once as 373 signatureAlgorithm field of the Certificate and once as the Signature 374 field of the sequence tbsCertificate, where the former is not part of 375 the message to be signed, whereas the latter is. Moreover, these two 376 fields are stipulated to be the same (see Sections 4.1.1.2 and 377 4.1.2.3 of [RFC5280]). In this case, old and new labels MUST be used 378 as indicated in the NOTE of Section 3, where the two fields 379 indicating the signature algorithm are always both changed at the 380 same time (thereby, strictly complying with MUST behavior of PKIX 381 that these two fields should be the same). 383 10. Acknowledgements 385 Thanks to Rich Salz for suggesting to informally compare speed-ups 386 with ECDSA* with those of EdDSA (now in Section 6). 388 11. References 390 11.1. Normative References 392 [FIPS-186-4] 393 FIPS 186-4, "Digital Signature Standard (DSS), Federal 394 Information Processing Standards Publication 186-4", US 395 Department of Commerce/National Institute of Standards and 396 Technology, Gaithersburg, MD, July 2013. 398 [I-D.ietf-lwig-curve-representations] 399 Struik, R., "Alternative Elliptic Curve Representations", 400 draft-ietf-lwig-curve-representations-19 (work in 401 progress), December 2020. 403 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 404 Requirement Levels", BCP 14, RFC 2119, 405 DOI 10.17487/RFC2119, March 1997, 406 . 408 [RFC5280] Cooper, D., Santesson, S., Farrell, S., Boeyen, S., 409 Housley, R., and W. Polk, "Internet X.509 Public Key 410 Infrastructure Certificate and Certificate Revocation List 411 (CRL) Profile", RFC 5280, DOI 10.17487/RFC5280, May 2008, 412 . 414 [RFC5480] Turner, S., Brown, D., Yiu, K., Housley, R., and T. Polk, 415 "Elliptic Curve Cryptography Subject Public Key 416 Information", RFC 5480, DOI 10.17487/RFC5480, March 2009, 417 . 419 [RFC7942] Sheffer, Y. and A. Farrel, "Improving Awareness of Running 420 Code: The Implementation Status Section", BCP 205, 421 RFC 7942, DOI 10.17487/RFC7942, July 2016, 422 . 424 [RFC8032] Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital 425 Signature Algorithm (EdDSA)", RFC 8032, 426 DOI 10.17487/RFC8032, January 2017, 427 . 429 [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 430 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, 431 May 2017, . 433 [RFC8692] Kampanakis, P. and Q. Dang, "Internet X.509 Public Key 434 Infrastructure: Additional Algorithm Identifiers for 435 RSASSA-PSS and ECDSA Using SHAKEs", RFC 8692, 436 DOI 10.17487/RFC8692, December 2019, 437 . 439 [SEC1] SEC1, "SEC 1: Elliptic Curve Cryptography, Version 2.0", 440 Standards for Efficient Cryptography, , June 2009. 442 [SEC2] SEC2, "SEC 2: Elliptic Curve Cryptography, Version 2.0", 443 Standards for Efficient Cryptography, , January 2010. 445 11.2. Informative References 447 [ECC] I.F. Blake, G. Seroussi, N.P. Smart, "Elliptic Curves in 448 Cryptography", Cambridge University Press, Lecture Notes 449 Series 265, July 1999. 451 [GECC] D. Hankerson, A.J. Menezes, S.A. Vanstone, "Guide to 452 Elliptic Curve Cryptography", New York: Springer-Verlag, 453 2004. 455 [P1609.2] IEEE 1609.2-2013, "IEEE Standard for Wireless Access in 456 Vehicular Environments-Security Services for Applications 457 and Management Messages", IEEE Vehicular Technology 458 Society, New York: IEEE, 2013. 460 [SAC2005] A. Antipa, D.R. Brown, R. Gallant, R. Lambert, R. Struik, 461 S.A. Vanstone, "Accelerated Verification of ECDSA 462 Signatures", SAC 2005, B. Preneel, S. Tavares, Eds., 463 Lecture Notes in Computer Science, Vol. 3897, pp. 307-318, 464 Berlin: Springer, 2006. 466 [SAC2010] R. Struik, "Batch Computations Revisited: Combining Key 467 Computations and Batch Verifications", SAC 2010, A. 468 Biryukov, G. Gong, D.R. Stinson, Eds., Lecture Notes in 469 Computer Science, Vol. 6544, pp. 130-142, Berlin- 470 Heidelberg: Springer, 2011. 472 Author's Address 473 Rene Struik 474 Struik Security Consultancy 476 Email: rstruik.ext@gmail.com