idnits 2.17.1 draft-nygren-tls-client-puzzles-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 abstract seems to contain references ([I-D.ietf-tls-tls13]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == Line 384 has weird spacing: '... seed the s...' == Line 387 has weird spacing: '... mem the nu...' == Line 389 has weird spacing: '... noff the n...' -- The document date (July 02, 2015) is 3221 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: 'I-D.josefsson-scrypt-kdf' is defined on line 514, but no explicit reference was found in the text == Outdated reference: A later version (-28) exists of draft-ietf-tls-tls13-06 == Outdated reference: A later version (-10) exists of draft-ietf-ipsecme-ddos-protection-01 == Outdated reference: A later version (-05) exists of draft-josefsson-scrypt-kdf-03 Summary: 1 error (**), 0 flaws (~~), 8 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group E. Nygren 3 Internet-Draft Akamai Technologies 4 Intended status: Standards Track July 02, 2015 5 Expires: January 3, 2016 7 TLS Client Puzzles Extension 8 draft-nygren-tls-client-puzzles-00 10 Abstract 12 Client puzzles allow a TLS server to defend itself against asymmetric 13 DDoS attacks. In particular, it allows a server to request clients 14 perform a selected amount of computation prior to the server 15 performing expensive cryptographic operations. This allows servers 16 to employ a layered defense that represents an improvement over pure 17 rate-limiting strategies. 19 Client puzzles are implemented as an extension to TLS 1.3 20 [I-D.ietf-tls-tls13] wherein a server can issue a HelloRetryRequest 21 containing the puzzle as an extension. The client must then resend 22 its ClientHello with the puzzle results in the extension. 24 Status of This Memo 26 This Internet-Draft is submitted in full conformance with the 27 provisions of BCP 78 and BCP 79. 29 Internet-Drafts are working documents of the Internet Engineering 30 Task Force (IETF). Note that other groups may also distribute 31 working documents as Internet-Drafts. The list of current Internet- 32 Drafts is at http://datatracker.ietf.org/drafts/current/. 34 Internet-Drafts are draft documents valid for a maximum of six months 35 and may be updated, replaced, or obsoleted by other documents at any 36 time. It is inappropriate to use Internet-Drafts as reference 37 material or to cite them other than as "work in progress." 39 This Internet-Draft will expire on January 3, 2016. 41 Copyright Notice 43 Copyright (c) 2015 IETF Trust and the persons identified as the 44 document authors. All rights reserved. 46 This document is subject to BCP 78 and the IETF Trust's Legal 47 Provisions Relating to IETF Documents 48 (http://trustee.ietf.org/license-info) in effect on the date of 49 publication of this document. Please review these documents 50 carefully, as they describe your rights and restrictions with respect 51 to this document. Code Components extracted from this document must 52 include Simplified BSD License text as described in Section 4.e of 53 the Trust Legal Provisions and are provided without warranty as 54 described in the Simplified BSD License. 56 Table of Contents 58 1. Overview and rationale . . . . . . . . . . . . . . . . . . . 2 59 2. Notational Conventions . . . . . . . . . . . . . . . . . . . 3 60 3. Handshake Changes . . . . . . . . . . . . . . . . . . . . . . 3 61 3.1. The ClientPuzzleExtension Message . . . . . . . . . . . . 5 62 4. Usage by Servers . . . . . . . . . . . . . . . . . . . . . . 6 63 5. Proposed Client Puzzles . . . . . . . . . . . . . . . . . . . 6 64 5.1. Cookie Client Puzzle Type . . . . . . . . . . . . . . . . 6 65 5.2. SHA-256 CPU Reverse Puzzle Type . . . . . . . . . . . . . 6 66 5.3. SHA-512 CPU Reverse Puzzle Type . . . . . . . . . . . . . 8 67 5.4. SHA-256 Memory Reverse Puzzle Type . . . . . . . . . . . 8 68 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 10 69 7. Security Considerations . . . . . . . . . . . . . . . . . . . 10 70 8. Privacy Considerations . . . . . . . . . . . . . . . . . . . 11 71 9. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 11 72 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 11 73 10.1. Normative References . . . . . . . . . . . . . . . . . . 11 74 10.2. Informative References . . . . . . . . . . . . . . . . . 12 76 1. Overview and rationale 78 Adversaries can exploit the design of the TLS protocol to craft 79 powerful asymmetric DDOS attacks. Once an attacker has opened a TCP 80 connection, the attacker can transmit effectively static content that 81 causes the server to perform expensive cryptographic operations. 82 Rate limiting offers one possible defense against this type of 83 attack; however, pure rate limiting systems represent an incomplete 84 solution: 86 1. Rate limiting systems work best when a small number of bots are 87 attacking a single server. Rate limiting is much more difficult 88 when a large number of bots are directing small amounts of 89 traffic to each member of a large distributed pool of servers. 91 2. Rate limiting systems encounter problems where a mixture of 92 "good" and "bad" clients are hidden behind a single NAT or Proxy 93 IP address and thus are all stuck being treated on equal footing. 95 3. Rate limiting schemes often penalize well-behaved good clients 96 (which try to complete handshakes and may limit their number of 97 retries) much more heavily than they penalize attacking bad 98 clients (which may try to disguise themselves as good clients, 99 but which otherwise are not constrained to behave in any 100 particular way). 102 Client puzzles are complementary to rate-limiting and give servers 103 another option than just rejecting some fraction of requests. A 104 server can provide a puzzle (of varying and server-selected 105 complexity) to a client as part of a HelloRetryRequest extension. 106 The client must choose to either abandon the connection or solve the 107 puzzle and resend its ClientHello with a solution to the puzzle. 108 Puzzles are designed to have asymmetric complexity such that it is 109 much cheaper for the server to generate and validate puzzles than it 110 is for clients to solve them. 112 Client puzzle systems may be inherently "unfair" to clients that run 113 with limited resources (such as mobile devices with batteries and 114 slow CPUs). However, client puzzle schemes will typically only be 115 evoked when a server is under attack and would otherwise be rejecting 116 some fraction of requests. The overwhelming majority of transactions 117 will never involve a client puzzle. Indeed, if client puzzles are 118 successful in forcing adversaries to use a new attack vector, the 119 presence of client puzzles will be completely transparent to end 120 users. 122 It is likely that not all clients will choose to support this 123 extension. During attack scenarios, servers will still have the 124 option to apply traditional rate limiting schemes (perhaps with 125 different parameters) to clients not supporting this extension or 126 using a version of TLS prior to 1.3. 128 2. Notational Conventions 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 [RFC2119]. 134 Messages are formatted with the notation as described within 135 [I-D.ietf-tls-tls13]. 137 3. Handshake Changes 139 Client puzzles are implemented as a new ClientPuzzleExtension to TLS 140 1.3 [I-D.ietf-tls-tls13]. A client supporting the 141 ClientPuzzleExtension MUST indicate support by sending a 142 ClientPuzzleExtension along with their ClientHello containing a list 143 of puzzle types supported, but with no puzzle response. When a 144 server wishes to force the client to solve a puzzle, it MAY send a 145 HelloRetryRequest with a ClientPuzzleExtension containing a puzzle of 146 a supported puzzle type and with associated parameters. To continue 147 with the handshake, a client MUST resend their ClientHello with a 148 ClientPuzzleExtension containing a response to the puzzle. The 149 ClientHello must otherwise be identical to the initial ClientHello, 150 other than for attributes that are defined by specification to not be 151 identical. 153 Puzzles issued by the server contain a token that the client must 154 include in their response. This allows a server to issue puzzles 155 without retaining state, which is particularly useful when used in 156 conjunction with DTLS. 158 If a puzzle would consume too many resources, a client MAY choose to 159 abort the handshake with the new fatal alert "puzzle_too_hard" and 160 terminate the connection. 162 A typical handshake when a puzzle is issued will look like: 164 Client Server 166 ClientHello 167 + ClientPuzzleExtension 168 + ClientKeyShare --------> 169 <-------- HelloRetryRequest 170 + ClientPuzzleExtension 171 ClientHello 172 + ClientPuzzleExtension 173 + ClientKeyShare --------> 174 ServerHello 175 ServerKeyShare 176 {EncryptedExtensions*} 177 {ServerConfiguration*} 178 {Certificate*} 179 {CertificateRequest*} 180 {CertificateVerify*} 181 <-------- {Finished} 182 {Certificate*} 183 {CertificateVerify*} 184 {Finished} --------> 185 [Application Data] <-------> [Application Data] 187 Figure 1. Message flow for a handshake with a client puzzle 189 * Indicates optional or situation-dependent messages that are not 190 always sent. 192 {} Indicates messages protected using keys derived from the ephemeral 193 secret. 195 [] Indicates messages protected using keys derived from the master 196 secret. 198 Note in particular that the major cryptographic operations (starting 199 to use the ephemeral secret and generating the CertificateVerify) are 200 performed _after_ the server has received and validated the 201 ClientPuzzleExtension response from the client. 203 3.1. The ClientPuzzleExtension Message 205 The ClientPuzzleExtension message contains an indication of supported 206 puzzle types during the initial ClientHello, a selected puzzle type 207 and puzzle challenge during HelloRetryRequest, and the puzzle type 208 and puzzle response in the retried ClientHello: 210 struct { 211 ClientPuzzleType type<1..255>; 212 opaque client_puzzle_challenge_response<0..2^16-1>; 213 } ClientPuzzleExtension; 215 enum { 216 cookie (0), 217 sha256_reverse_cpu (1), 218 sha512_reverse_cpu (2), 219 sha256_reverse_memory (3), 220 (0xFFFF) 221 } ClientPuzzleType; 223 type During initial ClientHello, a vector of supported client puzzle 224 types. During the HelloRetryRequest, a vector of exactly one 225 element containing the proposed puzzle. During the retried 226 ClientHello, a vector containing exactly one element with the type 227 of the puzzle being responded to. 229 client_puzzle_challenge_response Data specific to the puzzle type, 230 as defined in Section (#puzzles). In the initial ClientHello, 231 this MUST be empty (zero-length). During HelloRetryRequest, this 232 contains the challenge. During the retried ClientHello, this 233 contains a response to the challenge. Puzzles containing a token 234 may have it within this field. 236 4. Usage by Servers 238 Servers MAY send puzzles to clients when under duress, and the 239 percentage of clients receiving puzzles and the complexity of the 240 puzzles both MAY be selected as a function of the degree of duress. 242 Servers MAY also occasionally send puzzles to clients under normal 243 operating circumstances to ensure that the extension works properly. 245 Servers MAY use additional factors, such as client IP reputation 246 information, to determine when to send a puzzle as well as the 247 complexity. 249 5. Proposed Client Puzzles 251 Having multiple client puzzle types allows good clients a choice to 252 implement puzzles that match with their hardware capabilities 253 (although this also applies to bad clients). It also allows "broken" 254 puzzles to be phased out and retired, such as when cryptographic 255 weaknesses are identified. 257 5.1. Cookie Client Puzzle Type 259 The "cookie" ClientPuzzleType is intended to be trivial. The 260 client_puzzle_challenge_response data field is defined to be a token 261 that the client must echo back. 263 During an initial ClientHello, this MUST be empty (zero-length). 264 During HelloRetryRequest, the server MAY send a cookie challenge of 265 zero or more bytes as client_puzzle_challenge_response . During the 266 retried ClientHello, the client MUST respond by resending the 267 identical cookie sent in the HelloRetryRequest. 269 5.2. SHA-256 CPU Reverse Puzzle Type 271 This puzzle forces the client to calculate a SHA-256 [RFC5754] 272 multiple times. In particular, the server selects a random number 273 and challenge includes both the maximum possible value that the 274 random number could be as well as a salt bytestring. The server 275 communicates the maximum possible value that the number could be, 276 along with the salt and the result of performing a SHA-256 across a 277 number, the salt, and a label. The client solves the puzzle by 278 finding the number (within the range) where the SHA-256 matches the 279 provided value. 281 struct { 282 opaque token<0..2^16-1>; 283 uint64 challenge_max; 284 uint8 salt<0..2^16-1>; 285 uint8 sha256_result<32>; 286 } SHA256CPUReversePuzzleChallenge; 288 struct { 289 opaque token<0..2^16-1>; 290 uint64 challenge_solution; 291 } SHA256CPUReversePuzzleResponse; 293 token The token allows the server to encapsulate and drop state, and 294 also acts as a cookie for DTLS. During an initial ClientHello, 295 this MUST be empty (zero-length). During HelloRetryRequest, the 296 server MAY send a token challenge of zero or more bytes. During 297 the retried ClientHello, the client MUST respond by resending the 298 identical token sent in the HelloRetryRequest. Servers MAY 299 included an authenticated version of challenge_max, sha256_result, 300 and salt in this token if they wish to be stateless. 302 salt A server selected variable-length bytestring. 304 sha256_result The expected result of performing a SHA-256 across the 305 challenge_solution, salt, and label. 307 challenge_max The upper bound of the range that challenge_solution 308 is within. This is selected by the server to select the hardness 309 of the puzzle. The computational work that a client will need to 310 expend is intended to be O(challenge_max). 312 challenge_solution The solution response to the puzzle, as solved by 313 the client. The server guarantees that 0 <= challenge_solution <= 314 challenge_max. 316 To find the response, the client must find the numeric value of 317 challenge_solution where: 319 sha256_result = SHA-256(challenge_solution + salt + label) 321 where "+" denotes concatenation and where label is the NUL-terminated 322 value "TLS SHA256CPUReversePuzzle" (including the NUL terminator). 324 Clients offering to support this puzzle type SHOULD support 325 challenge_max values of at least 500,000. [[TODO: is this a good 326 value? https://en.bitcoin.it/wiki/Non- 327 specialized_hardware_comparison has a comparison of SHA256 on various 328 hardware.]] 329 (_TODO / Open question: Should this be HMAC-SHA256(salt, 330 challenge_solution + label) or similar?_) 332 5.3. SHA-512 CPU Reverse Puzzle Type 334 The SHA-512 CPU Reverse Puzzle Type is identical to the "SHA256 CPU 335 Reverse Puzzle Type" except that the SHA-512 [RFC5754] hash function 336 is used instead of SHA-256. The label used is the value "TLS 337 SHA512CPUReversePuzzle" and SHA512CPUReversePuzzleChallenge is 338 updated accordingly: 340 struct { 341 opaque token<0..2^16-1>; 342 uint64 challenge_max; 343 uint8 salt<0..2^16-1>; 344 uint8 sha512_result<64>; 345 } SHA512CPUReversePuzzleChallenge; 347 Clients offering to support this puzzle type SHOULD support 348 challenge_max values of at least 250,000. [[TODO: is this a good 349 value?]] 351 5.4. SHA-256 Memory Reverse Puzzle Type 353 [[_TODO: This puzzle is a place-holder not intended to be implemented 354 until a better and asymmetric memory-hard puzzle is proposed and 355 specified. Another, and likely better, alternative for a symmetric 356 memory-hard puzzle would be to leverage the scrypt KDF._ 357 [I-D.josefsson-scrypt-kdf]]] 359 This puzzle is be more memory-heavy than CPU-heavy which may be a 360 good option for mobile clients. Unfortunately, the memory-hard 361 aspect of this puzzle is not yet asymmetric. 363 This puzzle starts similar to SHA256CPUReversePuzzle but to fold in 364 another bytestring from information provided by the server. 366 struct { 367 opaque token<0..2^16-1>; 368 uint64 challenge_max; 369 uint8 salt<0..2^16-1>; 370 uint8 seed<0..2^16-1>; 371 uint64 mem; 372 unit32 noff; 373 uint8 sha256_result<32>; 374 } SHA256MemoryReversePuzzleChallenge; 376 struct { 377 opaque token<0..2^16-1>; 378 uint64 challenge_solution; 379 } SHA256MemoryReversePuzzleResponse; 381 Additional parameters to those in SHA256CPUReversePuzzleChallenge and 382 SHA256CPUReversePuzzleResponse: 384 seed the seed to a PRF (pseudorandom function) from which a 385 bytestream is generated 387 mem the number of bytes to expand from the PRF into memory 389 noff the number of offsets into the expand to pull from the PRF 391 So in specific: 393 expanded = PRF(seed, 0...mem-1) 394 extraction = SHA-256(expanded[PRF(seed, mem)] 395 + expanded[PRF(seed, mem+1)] 396 + ... 397 + expanded[PRF(seed, mem+noff)]) 399 (_TODO: Formalize the details of the PRF, unless this puzzle is 400 eliminated or replaced._) 402 In this case, challenge_solution is searched for in: 404 sha256_result = SHA-256(challenge_solution + salt 405 + label + extraction) 407 Where label is the NUL-terminated string "TLS 408 SHA256MemoryReversePuzzle". 410 Resource usage by clients is then _either_: 412 - Memory of O(1) and CPU of O(challenge_max) + O(noff * mem) 413 - Memory of O(mem) and CPU of O(challenge_max) + O(noff) 415 Servers MAY precompute sets of extractions and reuse them across 416 multiple clients. 418 6. IANA Considerations 420 The IANA will need to assign an extension codepoint value for 421 ClientPuzzleExtension. 423 The IANA will need to assign an AlertDescription codepoint value for 424 puzzle_too_hard. 426 The IANA will also need to maintain a registry of client puzzle 427 types. 429 7. Security Considerations 431 A hostile server could cause a client to consume unbounded resources. 432 Clients MUST bound the amount of resources (cpu/time and memory) they 433 will spend on a puzzle. 435 A puzzle type with economic utility could be abused by servers, 436 resulting in unnecessary resource usage by clients. In the worst 437 case, this could open up a new class of attacks where clients might 438 be directed to malicious servers to get delegated work. As such, any 439 new puzzle types SHOULD NOT be ones with utility for other purposes 440 (such as mining cryptocurrency or cracking password hashes). 441 Including fixed labels in new puzzle definitions may help mitigate 442 this risk. 444 Depeding on the structure of the puzzles, it is possible that an 445 attacker could send innocent clients to a hostile server and then use 446 those clients to solve puzzles presented by another target server 447 that the attacker wishes to attack. There may be ways to defend 448 against this by including IP information in the puzzles (not 449 currently proposed in this draft), although that introduces 450 additional issues. 452 All extensions add complexity, which could expose additional attack 453 surfaces on the client or the server. Using cryptographic primitives 454 and patterns already in-use in TLS can help reduce (but certainly not 455 eliminate) this complexity. 457 An attacker that can force a server into client puzzle mode could 458 result in a denial of service to clients not supporting puzzles or 459 not having the resources to complete the puzzles. This is not 460 necessarily worse than if the server was overloaded and forced to 461 deny service to all clients or to a random selection of clients. By 462 using client puzzles, clients willing to rate-limit themselves to the 463 rate at which they can solve puzzles should still be able to obtain 464 service while the server is able to stay available for these clients. 466 It is inevitable that attackers will build hardware optimized to 467 solve particular puzzles. Using common cryptographic primitives 468 (such as SHA-256) also means that commonly deployed clients may have 469 hardware assistance, although this also benefits legitimate clients. 471 8. Privacy Considerations 473 Measuring the response time of clients to puzzles gives an indication 474 of the relative capabilities of clients. This could be used as an 475 input for client fingerprinting. 477 Client's support for this extension, as well as which puzzles they 478 support, could also be used as an input for client fingerprinting. 480 9. Acknowledgments 482 Some of this was inspired by work done by Kyle Rose in 2001, as well 483 as a 2001 paper by Drew Dean (Xerox PARC) and Adam Stubblefield 484 (Rice) [SEC2001.DEAN]. Discussions with Eric Rescorla, Yoav Nir, 485 Richard Willey, Samuel Erb, Rich Salz, Kyle Rose, Brian Sniffen, and 486 others on the TLS working group have heavily influenced this proposal 487 and contributed to its content. An alternate approach was proposed 488 in [I-D.nir-tls-puzzles]. Some similar mechanisms for protecting IKE 489 are discused in [I-D.ietf-ipsecme-ddos-protection]. 491 10. References 493 10.1. Normative References 495 [I-D.ietf-tls-tls13] 496 Rescorla, E., "The Transport Layer Security (TLS) Protocol 497 Version 1.3", draft-ietf-tls-tls13-06 (work in progress), 498 June 2015. 500 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 501 Requirement Levels", BCP 14, RFC 2119, March 1997. 503 [RFC5754] Turner, S., "Using SHA2 Algorithms with Cryptographic 504 Message Syntax", RFC 5754, January 2010. 506 10.2. Informative References 508 [I-D.ietf-ipsecme-ddos-protection] 509 Nir, Y. and V. Smyslov, "Protecting Internet Key Exchange 510 (IKE) Implementations from Distributed Denial of Service 511 Attacks", draft-ietf-ipsecme-ddos-protection-01 (work in 512 progress), March 2015. 514 [I-D.josefsson-scrypt-kdf] 515 Percival, C. and S. Josefsson, "The scrypt Password-Based 516 Key Derivation Function", draft-josefsson-scrypt-kdf-03 517 (work in progress), May 2015. 519 [I-D.nir-tls-puzzles] 520 Nir, Y., "Using Client Puzzles to Protect TLS Servers From 521 Denial of Service Attacks", draft-nir-tls-puzzles-00 (work 522 in progress), April 2014. 524 [SEC2001.DEAN] 525 Xerox PARC and Rice University, "Using Client Puzzles to 526 Protect TLS", Proceedings of the 10th USENIX Security 527 Symposium , August 2001, 528 . 531 Author's Address 533 Erik Nygren 534 Akamai Technologies 536 EMail: erik+ietf@nygren.org 537 URI: http://erik.nygren.org/