idnits 2.17.1 draft-struik-lamps-verification-friendly-ecdsa-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 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 doesn't use any RFC 2119 keywords, yet seems to have RFC 2119 boilerplate text. -- The document date (February 22, 2021) is 1159 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Unused Reference: 'FIPS-186-4' is defined on line 263, but no explicit reference was found in the text == Unused Reference: 'I-D.ietf-lwig-curve-representations' is defined on line 269, but no explicit reference was found in the text == Unused Reference: 'RFC7748' is defined on line 279, but no explicit reference was found in the text == Unused Reference: 'SEC1' is defined on line 297, but no explicit reference was found in the text == Unused Reference: 'SEC2' is defined on line 300, but no explicit reference was found in the text == Unused Reference: 'ECC' is defined on line 305, but no explicit reference was found in the text == Unused Reference: 'GECC' is defined on line 309, but no explicit reference was found in the text == Outdated reference: A later version (-23) exists of draft-ietf-lwig-curve-representations-19 Summary: 1 error (**), 0 flaws (~~), 10 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 lwig R. Struik 3 Internet-Draft Struik Security Consultancy 4 Intended status: Informational February 22, 2021 5 Expires: August 26, 2021 7 ECDSA Signatures in Verification-Friendly Format 8 draft-struik-lamps-verification-friendly-ecdsa-00 10 Abstract 12 This document specifies how to represent ECDSA signatures so as to 13 facilitate fast verification of single signatures and fast batch 14 verification. We illustrate that this technique can be applied 15 retroactively by any device (rather than only by the signer), thereby 16 facilitating transitioning to always generating ECDSA signatures in 17 this way. 19 Requirements Language 21 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 22 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 23 "OPTIONAL" in this document are to be interpreted as described in BCP 24 14 [RFC2119] [RFC8174] when, and only when, they appear in all 25 capitals, as shown here. 27 Status of This Memo 29 This Internet-Draft is submitted in full conformance with the 30 provisions of BCP 78 and BCP 79. 32 Internet-Drafts are working documents of the Internet Engineering 33 Task Force (IETF). Note that other groups may also distribute 34 working documents as Internet-Drafts. The list of current Internet- 35 Drafts is at https://datatracker.ietf.org/drafts/current/. 37 Internet-Drafts are draft documents valid for a maximum of six months 38 and may be updated, replaced, or obsoleted by other documents at any 39 time. It is inappropriate to use Internet-Drafts as reference 40 material or to cite them other than as "work in progress." 42 This Internet-Draft will expire on August 26, 2021. 44 Copyright Notice 46 Copyright (c) 2021 IETF Trust and the persons identified as the 47 document authors. All rights reserved. 49 This document is subject to BCP 78 and the IETF Trust's Legal 50 Provisions Relating to IETF Documents 51 (https://trustee.ietf.org/license-info) in effect on the date of 52 publication of this document. Please review these documents 53 carefully, as they describe your rights and restrictions with respect 54 to this document. Code Components extracted from this document must 55 include Simplified BSD License text as described in Section 4.e of 56 the Trust Legal Provisions and are provided without warranty as 57 described in the Simplified BSD License. 59 Table of Contents 61 1. Fostering Fast Verification with ECDSA . . . . . . . . . . . 2 62 2. Review of ECDSA and ECDSA* . . . . . . . . . . . . . . . . . 3 63 3. Signature Verification with ECDSA and ECDSA* . . . . . . . . 4 64 4. Transitionary Considerations . . . . . . . . . . . . . . . . 5 65 5. Implementation Status . . . . . . . . . . . . . . . . . . . . 5 66 6. Security Considerations . . . . . . . . . . . . . . . . . . . 6 67 7. Privacy Considerations . . . . . . . . . . . . . . . . . . . 6 68 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 6 69 9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 6 70 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 6 71 10.1. Normative References . . . . . . . . . . . . . . . . . . 6 72 10.2. Informative References . . . . . . . . . . . . . . . . . 7 73 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 7 75 1. Fostering Fast Verification with ECDSA 77 ECDSA is one of the most widely used elliptic-curve digital signature 78 algorithms. It has been standardized in FIPS Pub 186-4, ANSI X9.62, 79 BSI, SECG, and IETF, and is widely deployed by a plethora of internet 80 protocols specified by the Internet Engineering Task Force (IETF), 81 with industry specifications in the areas of machine-to-machine 82 communication, such as ZigBee, ISA, and Thread, with wireless 83 communication protocols, such as IEEE 802.11, with payment protocols, 84 such as EMV, with vehicle-to-vehicle (V2V) specifications, as well as 85 with electronic travel documents and other specifications developed 86 under a more stringent regulatory oversight regime, such as, e.g., 87 ICAO and PIV. ECDSA is the only elliptic-curve based signature 88 scheme endorsed by regulatory bodies in both the United States and 89 the European Union. 91 While methods for accelerated verification of ECDSA signatures and 92 for combining this with key computations have been known for over 1 93 1/2 decade (see, e.g., [SAC2005] and [SAC2010]), these have been 94 commonly described in technical papers in terms of ECDSA*, a slightly 95 modified version of ECDSA, where their use with standardized ECDSA 96 seems less well known. It is the purpose of this document to fill 97 this seeming void and describe how ECDSA signatures can be easily 98 generated to facilitate more efficient verification, without failing. 99 We emphasize that this does not require changes to standardized 100 specifications of ECDSA, thereby allowing reuse of existing standards 101 and easy integration with existing implementations. 103 2. Review of ECDSA and ECDSA* 105 In this section, we summarize the properties of the signature scheme 106 ECDSA and of the modified signature scheme ECDSA* that are relevant 107 for our exposition. The signature schemes are defined in terms of a 108 suitable elliptic curve E, hash function H, and several 109 representation functions, where n is the (prime) order of the base 110 point G of this curve, and where E is an elliptic curve in short- 111 Weierstrass form. For full details, we refer to the relevant 112 standards. 114 With the ECDSA signature scheme, the signature over a message m 115 provided by a signing entity with static private key d is an ordered 116 pair (r,s) of integers in the interval [1,n-1], where the value r is 117 derived from a so-called ephemeral signing key R:=k*G generated by 118 the signer via a fixed public conversion function and where the value 119 s is a function of the ephemeral private key k, the static private 120 key d, the value r and the value e derived from message m via hash 121 function H and representation hereof in the interval [0,n-1]. (More 122 specifically, one has e=s*k-d*r (mod n), where r is a function of the 123 x-coordinate of R.) A signature (r,s) over message m purportedly 124 signed by an entity with public key Q:=d*G is accepted if Q is indeed 125 a valid public key, if both signature components r and s are integers 126 in the interval [1,n-1] and if the reconstructed value R' derived 127 from the purported signature, message, and public key yields r, via 128 the same fixed conversion function as used during the signing 129 operation. (More specifically, one computes R':=(1/s)*(e*G+r*Q) and 130 checks that r is the same function of the x-coordinate of R'.) 132 With the ECDSA* signature scheme, one follows the same signing 133 operation, except that one outputs as signature the ordered pair 134 (R,s), rather than the pair (r,s), where R is the ephemeral signing 135 key; one accepts a signature (R,s) over message m purportedly signed 136 by an entity with public key Q by first computing the value r derived 137 from signature component R via the conversion function, checking that 138 both r and s are integers in the interval [1,n-1], computing R':=(1/ 139 s)*(e*G+r*Q) and checking whether, indeed, R'=R. 141 It is known that ECDSA signatures and the corresponding ECDSA* 142 signatures have the same success/failure conditions (i.e., ECDSA and 143 ECDSA* are equally secure): if (r,s) is a valid ECDSA signature for 144 message m purportedly signed by an entity with public key Q, then 145 (R',s) is a valid corresponding ECDSA* signature, where R':=((1/ 146 s)(e*G+r*Q) is a point for which the conversion function yields r. 147 Conversely, if (R,s) is a valid ECDSA* signature for message m 148 purportedly signed by an entity with public key Q, then (r,s) is a 149 valid corresponding ECDSA signature, where r is obtained from R via 150 the conversion function. 152 It is well-known that if an ECDSA signature (r,s) is valid for a 153 particular message m and public key Q, then so is (r,-s) -- the so- 154 called malleability -- and that, similarly, if an ECDSA* signature 155 (R,s) is valid, hen so is (-R,-s), where the latter relies on the 156 fact that the conversion function only depends on the x-coordinate of 157 R. 159 3. Signature Verification with ECDSA and ECDSA* 161 In this section, we more closely scrutinize ECDSA and ECDSA* 162 verification processes. 164 With ECDSA*, signature verification primarily involves checking an 165 elliptic curve equation, viz. checking whether R = (1/s)*(e*G+r*Q), 166 which lends itself to accelerated signature verification techniques 167 and the ability to use batch verification techniques, with 168 significant potential for accelerated verification (~30% and up). 169 Here, speed-ups are due to the availability of the point R, which 170 effectively allows checking an equation of the form -s*R + 171 (e*G+r*Q)=O instead (where O is the identity element of the curve). 172 Similarly to the case with EdDSA [RFC8032], this offers the potential 173 for batch verification, by checking a randomized linear combination 174 of this equation instead (thereby sharing the so-called point 175 doubling operations amongst all individual verifications and, 176 potentially, sharing scalars for signers of more than one message). 177 In the case of single verifications, efficient tricks allow reducing 178 the bit-size of the scalars involved in evaluating this expression 179 (thereby effectively halving the required point doubling operations). 181 With ECDSA itself, these techniques are generally not available, 182 since one cannot generally uniquely (and efficiently) reconstruct R 183 from r: both R and -R yield the same r value. If the conversion 184 function only has two pre-images, though, one can use malleability to 185 remove ambiguity altogether. 187 The modified ECDSA signing procedure is as follows: 189 a. Generate ECDSA signature (r,s) of message m; 191 b. If the ephemeral signing key R has odd y-coordinate, change (r,s) 192 to (r,-s). 194 Note that this modified signing procedure removes the ambiguity in 195 the reconstruction of R from r if the conversion function would 196 otherwise only have two preimages, since R and -R have different 197 parity. In practice, this is the case for all prime-order curves, 198 including the NIST prime curves P-256, P-384, P-521, and all 199 standardized Brainpool curves. 201 NOTE: With ECDSA, any party (not just the signer) can recompute the 202 ephemeral signing key R' from a valid signature, since R':=(1/ 203 s)(e*G+r*Q). In particular, any party can retroactively put the 204 ECDSA signature in the required form above, thereby allowing 205 subsequent unique reconstruction of the R value from r by verifying 206 entities that know this modified signing procedure was indeed 207 followed. 209 4. Transitionary Considerations 211 The modified signing procedure described in Section 3 facilitates the 212 use of accelerated ECDSA verification techniques by devices that wish 213 to do so, provided these know that this modified signing procedure 214 was indeed followed. This can be realized via a new "fast- 215 verification-friendly" label (e.g., OID) indicating that this was 216 indeed the case. This has the following consequences: 218 a. New device: accept both old and new label and apply speed-ups if 219 possible (and desired); 221 b. Old device: implement flimsy parser that replaces new label by 222 old label and proceed as with traditional ECDSA verification. 224 Note that this parser "label replacement" step is a public operation, 225 so any interface can implement this step. 227 As suggested before, any device can implement the modified ECDSA 228 signing procedure retroactively, so one could conceivably implement 229 this once for all existing ECDSA signatures and only use "new" labels 230 once this task has been completed (i.e., old labels could be 231 mothballed from then on). 233 5. Implementation Status 235 [Note to the RFC Editor] Please remove this entire section before 236 publication, as well as the reference to [RFC7942]. 238 The ECDSA* signature scheme has been implemented in V2V specification 239 [P1609.2]. 241 6. Security Considerations 243 The representation conversions described in this document are 244 publicly known and, therefore, do not affect security provisions. 246 7. Privacy Considerations 248 The representation conversions described in this document are 249 publicly known and, therefore, do not affect privacy provisions. 251 8. IANA Considerations 253 With the current draft, no IANA code point assignments are requested. 255 9. Acknowledgements 257 place holder. 259 10. References 261 10.1. Normative References 263 [FIPS-186-4] 264 FIPS 186-4, "Digital Signature Standard (DSS), Federal 265 Information Processing Standards Publication 186-4", US 266 Department of Commerce/National Institute of Standards and 267 Technology, Gaithersburg, MD, July 2013. 269 [I-D.ietf-lwig-curve-representations] 270 Struik, R., "Alternative Elliptic Curve Representations", 271 draft-ietf-lwig-curve-representations-19 (work in 272 progress), December 2020. 274 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 275 Requirement Levels", BCP 14, RFC 2119, 276 DOI 10.17487/RFC2119, March 1997, 277 . 279 [RFC7748] Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves 280 for Security", RFC 7748, DOI 10.17487/RFC7748, January 281 2016, . 283 [RFC7942] Sheffer, Y. and A. Farrel, "Improving Awareness of Running 284 Code: The Implementation Status Section", BCP 205, 285 RFC 7942, DOI 10.17487/RFC7942, July 2016, 286 . 288 [RFC8032] Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital 289 Signature Algorithm (EdDSA)", RFC 8032, 290 DOI 10.17487/RFC8032, January 2017, 291 . 293 [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 294 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, 295 May 2017, . 297 [SEC1] SEC1, "SEC 1: Elliptic Curve Cryptography, Version 2.0", 298 Standards for Efficient Cryptography, , June 2009. 300 [SEC2] SEC2, "SEC 2: Elliptic Curve Cryptography, Version 2.0", 301 Standards for Efficient Cryptography, , January 2010. 303 10.2. Informative References 305 [ECC] I.F. Blake, G. Seroussi, N.P. Smart, "Elliptic Curves in 306 Cryptography", Cambridge University Press, Lecture Notes 307 Series 265, July 1999. 309 [GECC] D. Hankerson, A.J. Menezes, S.A. Vanstone, "Guide to 310 Elliptic Curve Cryptography", New York: Springer-Verlag, 311 2004. 313 [P1609.2] IEEE 1609.2-2013, "IEEE Standard for Wireless Access in 314 Vehicular Environments-Security Services for Applications 315 and Management Messages", IEEE Vehicular Technology 316 Society, New York: IEEE, 2013. 318 [SAC2005] A. Antipa, D.R. Brown, R. Gallant, R. Lambert, R. Struik, 319 S.A. Vanstone, "Accelerated Verification of ECDSA 320 Signatures", SAC 2005, B. Preneel, S. Tavares, Eds., 321 Lecture Notes in Computer Science, Vol. 3897, pp. 307-318, 322 Berlin: Springer, 2006, 2005. 324 [SAC2010] R. Struik, "Batch Computations Revisited: Combining Key 325 Computations and Batch Verifications", SAC 2010, A. 326 Biryukov, G. Gong, D.R. Stinson, Eds., Lecture Notes in 327 Computer Science, Vol. 6544, pp. 130-142, Berlin- 328 Heidelberg: Springer, 2011, 2005. 330 Author's Address 332 Rene Struik 333 Struik Security Consultancy 335 Email: rstruik.ext@gmail.com