idnits 2.17.1 draft-davidben-tls-batch-signing-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 : ---------------------------------------------------------------------------- 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 (July 29, 2019) is 1733 days in the past. Is this intentional? Checking references for intended status: Experimental ---------------------------------------------------------------------------- No issues found here. Summary: 0 errors (**), 0 flaws (~~), 1 warning (==), 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 July 29, 2019 5 Expires: January 30, 2020 7 Batch Signing for TLS 8 draft-davidben-tls-batch-signing-00 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 January 30, 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 . . . . . . . . . . . . . . . . . . . 2 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 . . . . . . . . . . . . . . . . . . . . 7 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. 79 2. Conventions and Definitions 81 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 82 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 83 "OPTIONAL" in this document are to be interpreted as described in BCP 84 14 [RFC2119] [RFC8174] when, and only when, they appear in all 85 capitals, as shown here. All TLS notation comes from section 3 of 86 [RFC8446]. 88 3. Batch SignatureSchemes 90 A batch SignatureScheme signs a number of input messages from 91 different connections concurrently and returns a corresponding batch 92 signature for each input message. 94 Each SignatureScheme is parameterized by the following: 96 o A base signature algorithm 98 o A hash function 100 This document defines the following values: 102 enum { 103 ecdsa_secp256r1_sha256_batch(TBD1), 104 ecdsa_secp384r1_sha384_batch(TBD2), 105 ecdsa_secp521r1_sha512_batch(TBD3), 106 ed25519_batch(TBD4), 107 ed448_batch(TBD5), 108 rsa_pss_pss_sha256_batch(TBD6), 109 rsa_pss_rsae_sha256_batch(TBD7), 110 rsa_pkcs1_sha256_legacy_batch(TBD8), 111 (65536) 112 } SignatureScheme 114 "ecdsa_secp256r1_sha256_batch", "ecdsa_secp384r1_sha384_batch", and 115 "ecdsa_secp521r1_sha512_batch" use base signature algorithms of 116 "ecdsa_secp256r1_sha256", "ecdsa_secp384r1_sha384", and 117 "ecdsa_secp521r1_sha512" with SHA-256, SHA-384, and SHA-512 [SHS], 118 respectively, as the hash function. 120 "ed25519_batch" uses a base signature algorithm of "ed25519" with 121 SHA-512 as the hash function. "ed448_batch" uses a base signature 122 algorithm of "ed448" with SHAKE256 [FIPS202] as the hash function. 124 "rsa_pss_pss_sha256_batch" and "rsa_pss_rsae_sha256_batch" use base 125 signature algorithms of "rsa_pss_pss_sha256" and 126 "rsa_pss_rsae_sha256" with SHA-256 as the hash function. 128 "rsa_pkcs1_sha256_legacy_batch" uses a base signature algorithm of 129 "rsa_pkcs1_sha256_legacy" [I-D.davidben-tls13-pkcs1] with SHA-256 as 130 the hash function. As with "rsa_pkcs1_sha256_legacy", this code 131 point is only defined for use with client certificates. 133 Batch signing is only defined for use with TLS 1.3. If TLS 1.2 is 134 negotiated, the above code points MUST NOT be used in 135 ServerKeyExchange or CertificateVerify messages. Note, however, a 136 client which supports both TLS 1.2 and TLS 1.3 MAY offer the code 137 points in the ClientHello. 139 These code points do not correspond to certificate signature 140 algorithms. Implementations wishing to advertise support for the 141 base signature algorithm should send the base algorithm's 142 corresponding code point. 144 3.1. Signing 146 Signing is performed by building a Merkle tree on top of the signing 147 inputs, interspersed with blinding values. An example tree for three 148 messages is shown below: 150 level 3: t30 151 _____/ \_____ 152 / \ 153 level 2: t20 t21 154 / \ / \ 155 / \ / \ 156 level 1: t10 t11 t12 t13=t10 157 / \ / \ / \ 158 level 0: t00 t01 t02 t03 t04 t05 159 | | | 160 m0 m1 m2 162 In general, let n be the number of input messages. If n is greater 163 than 2^31, the signing procedure fails and returns an error. 164 Otherwise, it builds a tree with l levels numbered 0 to l-1, where l 165 is ceil(log_2(n)) + 2. Hashes in the tree are built from the 166 following functions: 168 HashLeaf(msg) = Hash(0x00 || msg) 169 HashNode(left, right) = Hash(0x01 || left || right) 171 "0x00" and "0x01" denote byte strings containing a single byte with 172 value zero and one, respectively. "||" denotes concatenation. "left" 173 and "right" are byte strings with length Hash.length. 175 Tree levels are computed iteratively as follows: 177 1. Initialize level 0 with 2*n elements. For i between 0 and n-1, 178 inclusive, set element 2*i to the output of HashLeaf(m[i]) and 179 element 2*i+1 to a random byte of string of Hash.length bytes. 180 The random values placed at odd indices preserve signature 181 payload confidentiality (see Section 4.3). 183 2. For i between 1 and l-1, inclusive, compute level i from level 184 i-1 as follows: 186 * If level i-1 has an odd number of elements, pad it to an even 187 number of elements with a copy of its first element. That is, 188 if the previous level contained three hashes, x, y, z, it 189 should now contain four elements, x, y, z, x. 191 * Initialize level i with half as many elements as level i-1. 192 Set element j to the output of HashNode(left, right) where 193 "left" is element 2*j of level i-1 and "right" is element 194 2*j+1 of level i-1. "left" and "right" are the left and right 195 children of element j. 197 Level l-1 will contain a single element, the root of the tree. The 198 signer then computes a digital signature using the base signature 199 algorithm. This signature is computed over the concatenation of: 201 o A string that consists of octet 32 (0x20) repeated 64 times 203 o The context string "TLS batch signature" 205 o A single 0 byte which serves as the separator 207 o The batch signature algorithm's SignatureScheme code point, 208 expressed as a big-endian 16-bit integer. Note this is the code 209 point of the batch algorithm, not the original base algorithm. 211 o The value at the root of the tree 213 This structure is intended to provide key separation with other 214 signatures in TLS (see Section 4.2). 216 The signer then constructs a BatchSignature structure, as defined 217 below, for each input message. It encodes each to bytes to obtain 218 the final signatures. 220 opaque Node[Hash.length]; 222 struct { 223 uint32 index; 224 Node path; 225 opaque root_signature<0..2^16-1>; 226 } BatchSignature; 228 To assemble the BatchSignature structure for message i: 230 1. Set "index" to i. This will be value between 0 and n-1, 231 inclusive. 233 2. Set "path" to an array of l-1 hashes. Set element j of this 234 array to element k of level j, where k is (i >> j) ^ 1. ">>" 235 denotes a bitwise right-shift, and "^" denotes a bitwise 236 exclusive OR (XOR) operation. This element is the sibling of the 237 ancestor of message i in the tree. Note the root is never 238 included. 240 3. Set "root_signature" to the digital signature computed above. 242 For example, in the diagram below, the "path" field of the signature 243 of "m2" contains the marked nodes, in order from bottom to top. 245 level 3: t30 246 _____/ \_____ 247 / \ 248 level 2: *t20 t21 249 / \ / \ 250 / \ / \ 251 level 1: t10 t11 t12 *t13=t10 252 / \ / \ / \ 253 level 0: t00 t01 t02 t03 t04 *t05 254 | | | 255 m0 m1 m2 257 3.2. Verifying 259 The signature is verified by recovering the root hash from the 260 supplied "path" and "index" fields and then verifying the signature 261 in the "root_signature" field. This is done as follows: 263 1. If decoding the BatchSignature structure fails, terminate the 264 algorithm and reject the signature. 266 2. If the value of the "index" field is 2^31 or higher, or if the 267 number of elements in the "path" field is higher than 32, 268 terminate the algorithm and reject the signature. Otherwise, set 269 "remaining" to double this value. 271 3. Set "hash" to the output of HashLeaf(message). 273 4. For each element "v" of the "path" field, in order: 275 * If "remaining" is odd, set "hash" to the output of HashNode(v, 276 hash). Otherwise, set "hash" to the output of HashNode(hash, 277 v) 279 * Set "remaining" to remaining >> 1. 281 5. If "remaining" is non-zero, the signature is invalid. Terminate 282 the algorithm and reject the signature. 284 6. As in the signing algorithm, concatenate the following: 286 * A string that consists of octet 32 (0x20) repeated 64 times 288 * The context string "TLS batch signature" 290 * A single 0 byte which serves as the separator 292 * The batch signature algorithm's SignatureScheme code point, 293 expressed as a big-endian 16-bit integer. Note this is the 294 code point of the batch algorithm, not the original base 295 algorithm. 297 * The value of "hash" 299 7. Verify that the "root_signature" field is a valid signature for 300 the concatenation, using the base signature algorithm. If it is 301 invalid, terminate the algorithm and reject the signature. 302 Otherwise, accept the signature. 304 Note there are many possible valid signatures for a given message, 305 depending on how many and what messages were batched together. 307 4. Security Considerations 309 4.1. Correctness 311 Batch signatures sign the root of a Merkle tree (see Section 3.1) so, 312 provided the hash is collision-resistant and the base algorithm is 313 secure, an attacker can only forge signatures of messages in the 314 leaves of the Merkle tree. These leaves are the input messages, with 315 the exception of padding and blinding nodes, discussed below. 317 When building the tree, this mechanism pads odd-length levels with 318 extra copies of nodes already in the tree. This is equivalent to 319 signing multiple copies of some input messages to bring the total to 320 a power of two. This avoids introducing other messages for which the 321 signature would also be valid. Verification (see Section 3.2) 322 implicitly rejects odd indices in the tree to likewise ensure 323 blinding values are not mistaken for message hashes. 325 4.2. Domain Separation 327 Signatures made by the same key in different contexts should be 328 separated to avoid potential cross-protocol attacks. Inputs to the 329 batch signing algorithm include any context strings, so batch signing 330 inherits preserves separation 331 The root signature additionally includes its own context string. 332 This separates it from unbatched TLS 1.3 signatures, defined in 333 section 4.4.3 of [RFC8446]. Like TLS 1.3, it additionally includes a 334 64-byte padding prefix to clear the ClientHello.random and 335 ServerHello.random prefixes in the TLS 1.2 ServerKeyExchange signing 336 payload. This allows the same key to be used for batched and 337 unbatched signatures, simplifying deployment. 339 Finally, including the code point in the signature payload provides 340 separation in case the same base signature algorithm is used in two 341 batch constructions with, say, different hash functions. 343 4.3. Payload Confidentiality 345 The signing payload in TLS 1.3 is the handshake transcript. This 346 contains information which is normally encrypted, such as the server 347 certificate. Path elements in a batch signature are computed from 348 payloads from other connections in the same batch. A naive 349 construction could permit one peer to learn confidential information 350 in other connections' signing payloads, such as which server 351 certificate was selected in response to an encrypted SNI. 353 This mechanism avoids these attacks by pairing each input with a 354 secret blinding value. An input's signature path will reveal the 355 corresponding blinding value at level 0, but all other inputs in the 356 path are incorporated in nodes at level 1 or higher. Provided the 357 hash is preimage-resistant, these nodes do not reveal the original 358 payload. 360 In the event of entropy failure when generating the blinding values, 361 signatures remain unforgeable. The blinding values are only needed 362 for payload confidentiality. 364 4.4. Information Leaks 366 A server observing multiple batched client signatures with the same 367 root hash learns the two connections were created by the same client. 368 However, the connections are already correlatable via the client 369 certificate itself, so this does not reveal additional information in 370 most deployments. Clients can partition the contexts in which 371 signing requests may be batched to further mitigate these issues. 373 Additionally, a single batch signature reveals the number of signing 374 requests in that batch, rounded up to a power of two. This may 375 reveal some information about a service's signing load. 377 5. IANA Considerations 379 IANA is requested to create the following entries in the TLS 380 SignatureScheme registry, defined in [RFC8446]. The "Reference" 381 column should be set to this document. 383 +-------+-------------------------------+-------------+ 384 | Value | Description | Recommended | 385 +-------+-------------------------------+-------------+ 386 | TBD1 | ecdsa_secp256r1_sha256_batch | Y | 387 | | | | 388 | TBD2 | ecdsa_secp384r1_sha384_batch | Y | 389 | | | | 390 | TBD3 | ecdsa_secp521r1_sha512_batch | Y | 391 | | | | 392 | TBD4 | ed25519_batch | Y | 393 | | | | 394 | TBD5 | ed448_batch | Y | 395 | | | | 396 | TBD6 | rsa_pss_pss_sha256_batch | Y | 397 | | | | 398 | TBD7 | rsa_pss_rsae_sha256_batch | Y | 399 | | | | 400 | TBD8 | rsa_pkcs1_sha256_legacy_batch | N | 401 +-------+-------------------------------+-------------+ 403 6. Normative References 405 [FIPS202] Dworkin, M., "SHA-3 Standard: Permutation-Based Hash and 406 Extendable-Output Functions", National Institute of 407 Standards and Technology report, 408 DOI 10.6028/nist.fips.202, July 2015. 410 [I-D.davidben-tls13-pkcs1] 411 Benjamin, D., "Legacy RSASSA-PKCS1-v1_5 codepoints for TLS 412 1.3", draft-davidben-http2-tls13-00 (work in progress), 413 July 2019. 415 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 416 Requirement Levels", BCP 14, RFC 2119, 417 DOI 10.17487/RFC2119, March 1997, 418 . 420 [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 421 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, 422 May 2017, . 424 [RFC8446] Rescorla, E., "The Transport Layer Security (TLS) Protocol 425 Version 1.3", RFC 8446, DOI 10.17487/RFC8446, August 2018, 426 . 428 [SHS] Dang, Q., "Secure Hash Standard", National Institute of 429 Standards and Technology report, 430 DOI 10.6028/nist.fips.180-4, July 2015. 432 Appendix A. Test Vectors 434 TODO: Include test vectors. Probably use 435 ecdsa_secp256r1_sha256_batch. RSA signatures are big and Ed25519 436 isn't as common. Include some negative examples for verifying as 437 well as intermediate values so signing code can at least compare 438 against the tree-building vectors. (Blinding values and most of our 439 defined signature schemes are non-deterministic.) 441 Acknowledgments 443 The mechanism described in this document is derived from a similar 444 construction by Adam Langley in the Roughtime protocol. Adam also 445 provided the initial suggestion to apply a similar technique to TLS. 447 Author's Address 449 David Benjamin 450 Google LLC 452 Email: davidben@google.com