idnits 2.17.1 draft-davidben-tls-batch-signing-02.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 : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (November 01, 2019) is 1635 days in the past. Is this intentional? Checking references for intended status: Experimental ---------------------------------------------------------------------------- == Outdated reference: A later version (-01) exists of draft-davidben-tls13-pkcs1-00 Summary: 0 errors (**), 0 flaws (~~), 2 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 TLS D. Benjamin 3 Internet-Draft Google LLC 4 Intended status: Experimental November 01, 2019 5 Expires: May 4, 2020 7 Batch Signing for TLS 8 draft-davidben-tls-batch-signing-02 10 Abstract 12 This document describes a mechanism for batch signing in TLS. 14 Status of This Memo 16 This Internet-Draft is submitted in full conformance with the 17 provisions of BCP 78 and BCP 79. 19 Internet-Drafts are working documents of the Internet Engineering 20 Task Force (IETF). Note that other groups may also distribute 21 working documents as Internet-Drafts. The list of current Internet- 22 Drafts is at https://datatracker.ietf.org/drafts/current/. 24 Internet-Drafts are draft documents valid for a maximum of six months 25 and may be updated, replaced, or obsoleted by other documents at any 26 time. It is inappropriate to use Internet-Drafts as reference 27 material or to cite them other than as "work in progress." 29 This Internet-Draft will expire on May 4, 2020. 31 Copyright Notice 33 Copyright (c) 2019 IETF Trust and the persons identified as the 34 document authors. All rights reserved. 36 This document is subject to BCP 78 and the IETF Trust's Legal 37 Provisions Relating to IETF Documents 38 (https://trustee.ietf.org/license-info) in effect on the date of 39 publication of this document. Please review these documents 40 carefully, as they describe your rights and restrictions with respect 41 to this document. Code Components extracted from this document must 42 include Simplified BSD License text as described in Section 4.e of 43 the Trust Legal Provisions and are provided without warranty as 44 described in the Simplified BSD License. 46 Table of Contents 48 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 49 2. Conventions and Definitions . . . . . . . . . . . . . . . . . 2 50 3. Batch SignatureSchemes . . . . . . . . . . . . . . . . . . . 3 51 3.1. Signing . . . . . . . . . . . . . . . . . . . . . . . . . 4 52 3.2. Verifying . . . . . . . . . . . . . . . . . . . . . . . . 6 53 4. Security Considerations . . . . . . . . . . . . . . . . . . . 7 54 4.1. Correctness . . . . . . . . . . . . . . . . . . . . . . . 7 55 4.2. Domain Separation . . . . . . . . . . . . . . . . . . . . 8 56 4.3. Payload Confidentiality . . . . . . . . . . . . . . . . . 8 57 4.4. Information Leaks . . . . . . . . . . . . . . . . . . . . 8 58 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 9 59 6. Normative References . . . . . . . . . . . . . . . . . . . . 9 60 Appendix A. Test Vectors . . . . . . . . . . . . . . . . . . . . 10 61 Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . 10 62 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 10 64 1. Introduction 66 TLS [RFC8446] clients and servers authenticating with certificates 67 perform online signatures with the private key associated with their 68 certificate. In some cases, signing throughput may be limited. For 69 instance, RSA signing is CPU-intensive compared to many other 70 algorithms used in TLS. The private key may also be stored on a 71 hardware module or be accessed remotely on another server. Under 72 load, this can result in DoS concerns or impact system performance. 74 To mitigate these concerns, this document introduces a mechanism for 75 batch signing in TLS. It allows TLS implementations to satisfy many 76 concurrent requests with a single signing operation, at a logarithmic 77 cost to signature size. A server under load could, for instance, 78 preferentially serve batch-capable clients as part of its DoS 79 strategy. 81 2. Conventions and Definitions 83 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 84 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 85 "OPTIONAL" in this document are to be interpreted as described in BCP 86 14 [RFC2119] [RFC8174] when, and only when, they appear in all 87 capitals, as shown here. All TLS notation comes from section 3 of 88 [RFC8446]. 90 3. Batch SignatureSchemes 92 A batch SignatureScheme signs a number of input messages from 93 different connections concurrently and returns a corresponding batch 94 signature for each input message. 96 Each SignatureScheme is parameterized by the following: 98 o A base signature algorithm 100 o A hash function 102 This document defines the following values: 104 enum { 105 ecdsa_secp256r1_sha256_batch(TBD1), 106 ecdsa_secp384r1_sha384_batch(TBD2), 107 ecdsa_secp521r1_sha512_batch(TBD3), 108 ed25519_batch(TBD4), 109 ed448_batch(TBD5), 110 rsa_pss_pss_sha256_batch(TBD6), 111 rsa_pss_rsae_sha256_batch(TBD7), 112 rsa_pkcs1_sha256_legacy_batch(TBD8), 113 (65536) 114 } SignatureScheme 116 "ecdsa_secp256r1_sha256_batch", "ecdsa_secp384r1_sha384_batch", and 117 "ecdsa_secp521r1_sha512_batch" use base signature algorithms of 118 "ecdsa_secp256r1_sha256", "ecdsa_secp384r1_sha384", and 119 "ecdsa_secp521r1_sha512" with SHA-256, SHA-384, and SHA-512 [SHS], 120 respectively, as the hash function. 122 "ed25519_batch" uses a base signature algorithm of "ed25519" with 123 SHA-512 as the hash function. "ed448_batch" uses a base signature 124 algorithm of "ed448" with 64 bytes (512 bits) of SHAKE256 [FIPS202] 125 output as the hash function. 127 "rsa_pss_pss_sha256_batch" and "rsa_pss_rsae_sha256_batch" use base 128 signature algorithms of "rsa_pss_pss_sha256" and 129 "rsa_pss_rsae_sha256" with SHA-256 as the hash function. 131 "rsa_pkcs1_sha256_legacy_batch" uses a base signature algorithm of 132 "rsa_pkcs1_sha256_legacy" [I-D.davidben-tls13-pkcs1] with SHA-256 as 133 the hash function. As with "rsa_pkcs1_sha256_legacy", this code 134 point is only defined for use with client certificates. 136 Batch signing is only defined for use with TLS 1.3. If TLS 1.2 is 137 negotiated, the above code points MUST NOT be used in 138 ServerKeyExchange or CertificateVerify messages. Note, however, a 139 client which supports both TLS 1.2 and TLS 1.3 MAY offer the code 140 points in the ClientHello. 142 These code points do not correspond to certificate signature 143 algorithms. Implementations wishing to advertise support for the 144 base signature algorithm should send the base algorithm's 145 corresponding code point. 147 3.1. Signing 149 Signing is performed by building a Merkle tree on top of the signing 150 inputs, interspersed with blinding values. An example tree for three 151 messages is shown below: 153 level 3: t30 154 _____/ \_____ 155 / \ 156 level 2: t20 t21 157 / \ / \ 158 / \ / \ 159 level 1: t10 t11 t12 t13=t10 160 / \ / \ / \ 161 level 0: t00 t01 t02 t03 t04 t05 162 | | | 163 m0 m1 m2 165 In general, let n be the number of input messages. If n is greater 166 than 2^31, the signing procedure fails and returns an error. 167 Otherwise, it builds a tree with l levels numbered 0 to l-1, where l 168 is ceil(log_2(n)) + 2. Hashes in the tree are built from the 169 following functions: 171 HashLeaf(msg) = Hash(0x00 || msg) 172 HashNode(left, right) = Hash(0x01 || left || right) 174 "0x00" and "0x01" denote byte strings containing a single byte with 175 value zero and one, respectively. "||" denotes concatenation. "left" 176 and "right" are byte strings with length Hash.length. 178 Tree levels are computed iteratively as follows: 180 1. Initialize level 0 with 2*n elements. For i between 0 and n-1, 181 inclusive, set element 2*i to the output of HashLeaf(m[i]) and 182 element 2*i+1 to a random string of Hash.length bytes. The 183 random values placed at odd indices preserve signature payload 184 confidentiality (see Section 4.3). 186 2. For i between 1 and l-1, inclusive, compute level i from level 187 i-1 as follows: 189 * If level i-1 has an odd number of elements, pad it to an even 190 number of elements with a copy of its first element. That is, 191 if the previous level contained three hashes, x, y, z, it 192 should now contain four elements, x, y, z, x. 194 * Initialize level i with half as many elements as level i-1. 195 Set element j to the output of HashNode(left, right) where 196 "left" is element 2*j of level i-1 and "right" is element 197 2*j+1 of level i-1. "left" and "right" are the left and right 198 children of element j. 200 Level l-1 will contain a single element, the root of the tree. The 201 signer then computes a digital signature using the base signature 202 algorithm. This signature is computed over the concatenation of: 204 o A string that consists of octet 32 (0x20) repeated 64 times 206 o The context string "TLS batch signature" 208 o A single 0 byte which serves as the separator 210 o The batch signature algorithm's SignatureScheme code point, 211 expressed as a big-endian 16-bit integer. Note this is the code 212 point of the batch algorithm, not the original base algorithm. 214 o The value at the root of the tree 216 This structure is intended to provide key separation with other 217 signatures in TLS (see Section 4.2). 219 The signer then constructs a BatchSignature structure, as defined 220 below, for each input message. It encodes each to bytes to obtain 221 the final signatures. 223 opaque Node[Hash.length]; 225 struct { 226 uint32 index; 227 Node path; 228 opaque root_signature<0..2^16-1>; 229 } BatchSignature; 231 To assemble the BatchSignature structure for message i: 233 1. Set "index" to i. This will be a value between 0 and n-1, 234 inclusive. 236 2. Set "path" to an array of l-1 hashes. Set element j of this 237 array to element k of level j, where k is ((2 * i) >> j) ^ 1. 238 ">>" denotes a bitwise right-shift, and "^" denotes a bitwise 239 exclusive OR (XOR) operation. This element is the sibling of the 240 ancestor of message i in the tree. Note the root is never 241 included. 243 3. Set "root_signature" to the digital signature computed above. 245 For example, in the diagram below, the "path" field of the signature 246 of "m2" contains the marked nodes, in order from bottom to top. 248 level 3: t30 249 _____/ \_____ 250 / \ 251 level 2: *t20 t21 252 / \ / \ 253 / \ / \ 254 level 1: t10 t11 t12 *t13=t10 255 / \ / \ / \ 256 level 0: t00 t01 t02 t03 t04 *t05 257 | | | 258 m0 m1 m2 260 3.2. Verifying 262 The signature is verified by recovering the root hash from the 263 supplied "path" and "index" fields and then verifying the signature 264 in the "root_signature" field. This is done as follows: 266 1. If decoding the BatchSignature structure fails, terminate the 267 algorithm and reject the signature. 269 2. If the value of the "index" field is 2^31 or higher, or if the 270 number of elements in the "path" field is higher than 32, 271 terminate the algorithm and reject the signature. Otherwise, set 272 "remaining" to double this value. 274 3. Set "hash" to the output of HashLeaf(message). 276 4. For each element "v" of the "path" field, in order: 278 * If "remaining" is odd, set "hash" to the output of HashNode(v, 279 hash). Otherwise, set "hash" to the output of HashNode(hash, 280 v) 282 * Set "remaining" to remaining >> 1. 284 5. If "remaining" is non-zero, the signature is invalid. Terminate 285 the algorithm and reject the signature. 287 6. As in the signing algorithm, concatenate the following: 289 * A string that consists of octet 32 (0x20) repeated 64 times 291 * The context string "TLS batch signature" 293 * A single 0 byte which serves as the separator 295 * The batch signature algorithm's SignatureScheme code point, 296 expressed as a big-endian 16-bit integer. Note this is the 297 code point of the batch algorithm, not the original base 298 algorithm. 300 * The value of "hash" 302 7. Verify that the "root_signature" field is a valid signature for 303 the concatenation, using the base signature algorithm. If it is 304 invalid, terminate the algorithm and reject the signature. 305 Otherwise, accept the signature. 307 Note there are many possible valid signatures for a given message, 308 depending on how many and what messages were batched together. 310 4. Security Considerations 312 4.1. Correctness 314 Batch signatures sign the root of a Merkle tree (see Section 3.1) so, 315 provided the hash is collision-resistant and the base algorithm is 316 secure, an attacker can only forge signatures of messages in the 317 leaves of the Merkle tree. These leaves are the input messages, with 318 the exception of padding and blinding nodes, discussed below. 320 When building the tree, this mechanism pads odd-length levels with 321 extra copies of nodes already in the tree. This is equivalent to 322 signing multiple copies of some input messages to bring the total to 323 a power of two. This avoids introducing other messages for which the 324 signature would also be valid. Verification (see Section 3.2) 325 implicitly rejects odd indices in the tree to likewise ensure 326 blinding values are not mistaken for message hashes. 328 4.2. Domain Separation 330 Signatures made by the same key in different contexts should be 331 separated to avoid potential cross-protocol attacks. Inputs to the 332 batch signing algorithm include any existing context strings, such as 333 TLS 1.3's distinct client and server labels or new labels that may be 334 allocated by future versions of TLS. By signing over those labels, 335 batch signing preserves separation between those inputs. 337 The root signature additionally includes its own context string. 338 This separates it from unbatched TLS 1.3 signatures, defined in 339 section 4.4.3 of [RFC8446]. Like TLS 1.3, it additionally includes a 340 64-byte padding prefix to clear the ClientHello.random and 341 ServerHello.random prefixes in the TLS 1.2 ServerKeyExchange signing 342 payload. This allows the same key to be used for batched and 343 unbatched signatures, simplifying deployment. 345 Finally, including the code point in the signature payload provides 346 separation in case the same base signature algorithm is used in two 347 batch constructions with, say, different hash functions. 349 4.3. Payload Confidentiality 351 The signing payload in TLS 1.3 is the handshake transcript. This 352 contains information which is normally encrypted, such as the server 353 certificate. Path elements in a batch signature are computed from 354 payloads from other connections in the same batch. A naive 355 construction could permit one peer to learn confidential information 356 in other connections' signing payloads, such as which server 357 certificate was selected in response to an encrypted SNI. 359 This mechanism avoids these attacks by pairing each input with a 360 secret blinding value. An input's signature path will reveal the 361 corresponding blinding value at level 0, but all other inputs in the 362 path are incorporated in nodes at level 1 or higher. Provided the 363 hash is preimage-resistant, these nodes do not reveal the original 364 payload. 366 In the event of entropy failure when generating the blinding values, 367 signatures remain unforgeable. The blinding values are only needed 368 for payload confidentiality. 370 4.4. Information Leaks 372 A server observing multiple batched client signatures with the same 373 root hash learns the two connections were created by the same client. 374 However, the connections are already correlatable via the client 375 certificate itself, so this does not reveal additional information in 376 most deployments. Clients can partition the contexts in which 377 signing requests may be batched to further mitigate these issues. 379 Additionally, a single batch signature reveals the number of signing 380 requests in that batch, rounded up to a power of two. This may 381 reveal some information about a service's signing load. 383 5. IANA Considerations 385 IANA is requested to create the following entries in the TLS 386 SignatureScheme registry, defined in [RFC8446]. The "Reference" 387 column should be set to this document. 389 +-------+-------------------------------+-------------+ 390 | Value | Description | Recommended | 391 +-------+-------------------------------+-------------+ 392 | TBD1 | ecdsa_secp256r1_sha256_batch | Y | 393 | | | | 394 | TBD2 | ecdsa_secp384r1_sha384_batch | Y | 395 | | | | 396 | TBD3 | ecdsa_secp521r1_sha512_batch | Y | 397 | | | | 398 | TBD4 | ed25519_batch | Y | 399 | | | | 400 | TBD5 | ed448_batch | Y | 401 | | | | 402 | TBD6 | rsa_pss_pss_sha256_batch | Y | 403 | | | | 404 | TBD7 | rsa_pss_rsae_sha256_batch | Y | 405 | | | | 406 | TBD8 | rsa_pkcs1_sha256_legacy_batch | N | 407 +-------+-------------------------------+-------------+ 409 6. Normative References 411 [FIPS202] Dworkin, M., "SHA-3 Standard: Permutation-Based Hash and 412 Extendable-Output Functions", National Institute of 413 Standards and Technology report, 414 DOI 10.6028/nist.fips.202, July 2015. 416 [I-D.davidben-tls13-pkcs1] 417 Benjamin, D., "Legacy RSASSA-PKCS1-v1_5 codepoints for TLS 418 1.3", draft-davidben-tls13-pkcs1-00 (work in progress), 419 July 2019. 421 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 422 Requirement Levels", BCP 14, RFC 2119, 423 DOI 10.17487/RFC2119, March 1997, 424 . 426 [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 427 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, 428 May 2017, . 430 [RFC8446] Rescorla, E., "The Transport Layer Security (TLS) Protocol 431 Version 1.3", RFC 8446, DOI 10.17487/RFC8446, August 2018, 432 . 434 [SHS] Dang, Q., "Secure Hash Standard", National Institute of 435 Standards and Technology report, 436 DOI 10.6028/nist.fips.180-4, July 2015. 438 Appendix A. Test Vectors 440 TODO: Include test vectors. Probably use 441 ecdsa_secp256r1_sha256_batch. RSA signatures are big and Ed25519 442 isn't as common. Include some negative examples for verifying as 443 well as intermediate values so signing code can at least compare 444 against the tree-building vectors. (Blinding values and most of our 445 defined signature schemes are non-deterministic.) 447 Acknowledgments 449 The mechanism described in this document is derived from a similar 450 construction by Adam Langley in the Roughtime protocol. Adam also 451 provided the initial suggestion to apply a similar technique to TLS. 453 Author's Address 455 David Benjamin 456 Google LLC 458 Email: davidben@google.com