idnits 2.17.1 draft-nygren-tls-client-puzzles-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 : ---------------------------------------------------------------------------- ** 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 304 has weird spacing: '...ficulty filte...' == Line 369 has weird spacing: '...ficulty secon...' == Line 373 has weird spacing: '...olution list ...' -- The document date (December 28, 2016) is 2647 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 525, but no explicit reference was found in the text == Outdated reference: A later version (-28) exists of draft-ietf-tls-tls13-13 == Outdated reference: A later version (-10) exists of draft-ietf-ipsecme-ddos-protection-06 Summary: 1 error (**), 0 flaws (~~), 7 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 S. Erb 4 Intended status: Standards Track Akamai Technologies 5 Expires: July 1, 2017 A. Biryukov 6 D. Khovratovich 7 University of Luxembourg 8 A. Juels 9 Cornell University 10 December 28, 2016 12 TLS Client Puzzles Extension 13 draft-nygren-tls-client-puzzles-02 15 Abstract 17 Client puzzles allow a TLS server to defend itself against asymmetric 18 DDoS attacks. In particular, it allows a server to request clients 19 perform a selected amount of computation prior to the server 20 performing expensive cryptographic operations. This allows servers 21 to employ a layered defense that represents an improvement over pure 22 rate-limiting strategies. 24 Client puzzles are implemented as an extension to TLS 1.3 25 [I-D.ietf-tls-tls13] wherein a server can issue a HelloRetryRequest 26 containing the puzzle as an extension. The client must then resend 27 its ClientHello with the puzzle results in the extension. 29 Status of This Memo 31 This Internet-Draft is submitted in full conformance with the 32 provisions of BCP 78 and BCP 79. 34 Internet-Drafts are working documents of the Internet Engineering 35 Task Force (IETF). Note that other groups may also distribute 36 working documents as Internet-Drafts. The list of current Internet- 37 Drafts is at http://datatracker.ietf.org/drafts/current/. 39 Internet-Drafts are draft documents valid for a maximum of six months 40 and may be updated, replaced, or obsoleted by other documents at any 41 time. It is inappropriate to use Internet-Drafts as reference 42 material or to cite them other than as "work in progress." 44 This Internet-Draft will expire on July 1, 2017. 46 Copyright Notice 48 Copyright (c) 2016 IETF Trust and the persons identified as the 49 document authors. All rights reserved. 51 This document is subject to BCP 78 and the IETF Trust's Legal 52 Provisions Relating to IETF Documents 53 (http://trustee.ietf.org/license-info) in effect on the date of 54 publication of this document. Please review these documents 55 carefully, as they describe your rights and restrictions with respect 56 to this document. Code Components extracted from this document must 57 include Simplified BSD License text as described in Section 4.e of 58 the Trust Legal Provisions and are provided without warranty as 59 described in the Simplified BSD License. 61 Table of Contents 63 1. Overview and rationale . . . . . . . . . . . . . . . . . . . 2 64 2. Notational Conventions . . . . . . . . . . . . . . . . . . . 3 65 3. Handshake Changes . . . . . . . . . . . . . . . . . . . . . . 4 66 3.1. The ClientPuzzleExtension Message . . . . . . . . . . . . 5 67 4. Usage by Servers . . . . . . . . . . . . . . . . . . . . . . 6 68 5. Proposed Client Puzzles . . . . . . . . . . . . . . . . . . . 6 69 5.1. Cookie Client Puzzle Type . . . . . . . . . . . . . . . . 7 70 5.2. SHA-256 CPU Puzzle Type . . . . . . . . . . . . . . . . . 7 71 5.3. SHA-512 CPU Puzzle Type . . . . . . . . . . . . . . . . . 8 72 5.4. Equihash: Memory-hard Generalized Birthday Problem Puzzle 73 Type . . . . . . . . . . . . . . . . . . . . . . . . . . 8 74 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 10 75 7. Security Considerations . . . . . . . . . . . . . . . . . . . 10 76 8. Privacy Considerations . . . . . . . . . . . . . . . . . . . 11 77 9. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 11 78 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 11 79 10.1. Normative References . . . . . . . . . . . . . . . . . . 11 80 10.2. Informative References . . . . . . . . . . . . . . . . . 12 81 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 13 83 1. Overview and rationale 85 Adversaries can exploit the design of the TLS protocol to craft 86 powerful asymmetric DDOS attacks. Once an attacker has opened a TCP 87 connection, the attacker can transmit effectively static content that 88 causes the server to perform expensive cryptographic operations. 89 Rate limiting offers one possible defense against this type of 90 attack; however, pure rate limiting systems represent an incomplete 91 solution: 93 1. Rate limiting systems work best when a small number of bots are 94 attacking a single server. Rate limiting is much more difficult 95 when a large number of bots are directing small amounts of 96 traffic to each member of a large distributed pool of servers. 98 2. Rate limiting systems encounter problems where a mixture of 99 "good" and "bad" clients are hidden behind a single NAT or Proxy 100 IP address and thus are all stuck being treated on equal footing. 102 3. Rate limiting schemes often penalize well-behaved good clients 103 (which try to complete handshakes and may limit their number of 104 retries) much more heavily than they penalize attacking bad 105 clients (which may try to disguise themselves as good clients, 106 but which otherwise are not constrained to behave in any 107 particular way). 109 Client puzzles are complementary to rate-limiting and give servers 110 another option than just rejecting some fraction of requests. A 111 server can provide a puzzle (of varying and server-selected 112 complexity) to a client as part of a HelloRetryRequest extension. 113 The client must choose to either abandon the connection or solve the 114 puzzle and resend its ClientHello with a solution to the puzzle. 115 Puzzles are designed to have asymmetric complexity such that it is 116 much cheaper for the server to generate and validate puzzles than it 117 is for clients to solve them. 119 Client puzzle systems may be inherently "unfair" to clients that run 120 with limited resources (such as mobile devices with batteries and 121 slow CPUs). However, client puzzle schemes will typically only be 122 evoked when a server is under attack and would otherwise be rejecting 123 some fraction of requests. The overwhelming majority of transactions 124 will never involve a client puzzle. Indeed, if client puzzles are 125 successful in forcing adversaries to use a new attack vector, the 126 presence of client puzzles will be completely transparent to end 127 users. 129 It is likely that not all clients will choose to support this 130 extension. During attack scenarios, servers will still have the 131 option to apply traditional rate limiting schemes (perhaps with 132 different parameters) to clients not supporting this extension or 133 using a version of TLS prior to 1.3. 135 2. Notational Conventions 137 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 138 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 139 document are to be interpreted as described in [RFC2119]. 141 Messages are formatted with the notation as described within 142 [I-D.ietf-tls-tls13]. 144 3. Handshake Changes 146 Client puzzles are implemented as a new ClientPuzzleExtension to TLS 147 1.3 [I-D.ietf-tls-tls13]. A client supporting the 148 ClientPuzzleExtension MUST indicate support by sending a 149 ClientPuzzleExtension along with their ClientHello containing a list 150 of puzzle types supported, but with no puzzle response. When a 151 server wishes to force the client to solve a puzzle, it MAY send a 152 HelloRetryRequest with a ClientPuzzleExtension containing a puzzle of 153 a supported puzzle type and with associated parameters. To continue 154 with the handshake, a client MUST resend their ClientHello with a 155 ClientPuzzleExtension containing a response to the puzzle. The 156 ClientHello must otherwise be identical to the initial ClientHello, 157 other than for attributes that are defined by specification to not be 158 identical. 160 Puzzles issued by the server contain a token that the client must 161 include in their response. This allows a server to issue puzzles 162 without retaining state, which is particularly useful when used in 163 conjunction with DTLS. 165 If a puzzle would consume too many resources, a client MAY choose to 166 abort the handshake with the new fatal alert "puzzle_too_hard" and 167 terminate the connection. 169 A typical handshake when a puzzle is issued will look like: 171 Client Server 173 ClientHello 174 + ClientPuzzleExtension 175 + ClientKeyShare --------> 176 <-------- HelloRetryRequest 177 + ClientPuzzleExtension 178 ClientHello 179 + ClientPuzzleExtension 180 + ClientKeyShare --------> 181 ServerHello 182 ServerKeyShare 183 {EncryptedExtensions*} 184 {ServerConfiguration*} 185 {Certificate*} 186 {CertificateRequest*} 187 {CertificateVerify*} 188 <-------- {Finished} 189 {Certificate*} 190 {CertificateVerify*} 191 {Finished} --------> 192 [Application Data] <-------> [Application Data] 194 Figure 1. Message flow for a handshake with a client puzzle 196 * Indicates optional or situation-dependent messages that are not 197 always sent. 199 {} Indicates messages protected using keys derived from the ephemeral 200 secret. 202 [] Indicates messages protected using keys derived from the master 203 secret. 205 Note in particular that the major cryptographic operations (starting 206 to use the ephemeral secret and generating the CertificateVerify) are 207 performed _after_ the server has received and validated the 208 ClientPuzzleExtension response from the client. 210 3.1. The ClientPuzzleExtension Message 212 The ClientPuzzleExtension message contains an indication of supported 213 puzzle types during the initial ClientHello, a selected puzzle type 214 and puzzle challenge during HelloRetryRequest, and the puzzle type 215 and puzzle response in the retried ClientHello: 217 struct { 218 ClientPuzzleType type<1..255>; 219 opaque client_puzzle_challenge_response<0..2^16-1>; 220 } ClientPuzzleExtension; 222 enum { 223 cookie (0), 224 sha256_cpu (1), 225 sha512_cpu (2), 226 birthday_puzzle (3), 227 (0xFFFF) 228 } ClientPuzzleType; 230 type During initial ClientHello, a vector of supported client puzzle 231 types. During the HelloRetryRequest, a vector of exactly one 232 element containing the proposed puzzle. During the retried 233 ClientHello, a vector containing exactly one element with the type 234 of the puzzle being responded to. 236 client_puzzle_challenge_response Data specific to the puzzle type, 237 as defined in Section (#puzzles). In the initial ClientHello, 238 this MUST be empty (zero-length). During HelloRetryRequest, this 239 contains the challenge. During the retried ClientHello, this 240 contains a response to the challenge. Puzzles containing a token 241 may have it within this field. 243 4. Usage by Servers 245 Servers MAY send puzzles to clients when under duress, and the 246 percentage of clients receiving puzzles and the complexity of the 247 puzzles both MAY be selected as a function of the degree of duress. 249 Servers MAY also occasionally send puzzles to clients under normal 250 operating circumstances to ensure that the extension works properly. 252 Servers MAY use additional factors, such as client IP reputation 253 information, to determine when to send a puzzle as well as the 254 complexity. 256 5. Proposed Client Puzzles 258 Having multiple client puzzle types allows good clients a choice to 259 implement puzzles that match with their hardware capabilities 260 (although this also applies to bad clients). It also allows "broken" 261 puzzles to be phased out and retired, such as when cryptographic 262 weaknesses are identified. 264 5.1. Cookie Client Puzzle Type 266 The "cookie" ClientPuzzleType is intended to be trivial. The 267 client_puzzle_challenge_response data field is defined to be a token 268 that the client must echo back. 270 During an initial ClientHello, this MUST be empty (zero-length). 271 During HelloRetryRequest, the server MAY send a cookie challenge of 272 zero or more bytes as client_puzzle_challenge_response . During the 273 retried ClientHello, the client MUST respond by resending the 274 identical cookie sent in the HelloRetryRequest. 276 5.2. SHA-256 CPU Puzzle Type 278 This puzzle forces the client to calculate a SHA-256 [RFC5754] 279 multiple times. In particular, the server selects a difficulty and a 280 random salt. The client solves the puzzle by finding any nonce where 281 a SHA-256 hash across the nonce, the salt and a label contains 282 difficulty leading zero bits. 284 struct { 285 opaque token<0..2^16-1>; 286 uint16 difficulty; 287 uint8 salt<0..2^16-1>; 288 } SHA256CPUPuzzleChallenge; 290 struct { 291 opaque token<0..2^16-1>; 292 uint64 challenge_solution; 293 } SHA256CPUPuzzleResponse; 295 token The token allows the server to encapsulate and drop state, and 296 also acts as a cookie for DTLS. During an initial ClientHello, 297 this MUST be empty (zero-length). During HelloRetryRequest, the 298 server MAY send a token challenge of zero or more bytes. During 299 the retried ClientHello, the client MUST respond by resending the 300 identical token sent in the HelloRetryRequest. Servers MAY 301 included an authenticated version of difficulty and salt in this 302 token if they wish to be stateless. 304 difficulty filter affecting the time to find solution. 306 salt A server selected variable-length bytestring. 308 challenge_solution The solution response to the puzzle, as solved by 309 the client. 311 To find the response, the client must find a numeric value of 312 challenge_solution where: 314 SHA-256(challenge_solution || salt || label) contains difficulty 315 leading zeros. 317 where "||" denotes concatenation and where label is the NUL- 318 terminated value "TLS SHA256CPUPuzzle" (including the NUL 319 terminator). 321 Clients offering to support this puzzle type SHOULD support a 322 difficulty value of at least 18. [[TODO: is this a good value? 323 https://en.bitcoin.it/wiki/Non-specialized_hardware_comparison has a 324 comparison of SHA256 on various hardware.]] 326 5.3. SHA-512 CPU Puzzle Type 328 The SHA-512 CPU Puzzle Type is identical to the "SHA256 CPU Puzzle 329 Type" except that the SHA-512 [RFC5754] hash function is used instead 330 of SHA-256. The label used is the value "TLS SHA512CPUPuzzle". 332 Clients offering to support this puzzle type SHOULD support 333 difficulty values of at least 17. [[TODO: is this a good value?]] 335 5.4. Equihash: Memory-hard Generalized Birthday Problem Puzzle Type 337 Using Equihash, the asymmetric memory-hard generalized birthday 338 problem PoW [NDSS2016], this puzzle will force a client to use a 339 significant amount of memory to solve. The solution to this puzzle 340 can be trivially verified. 342 struct { 343 opaque token<0..2^16-1>; 344 uint16 n; 345 uint16 k; 346 uint16 difficulty; 347 uint8 salt<0..2^16-1>; 348 } BirthdayPuzzleChallenge; 350 struct { 351 opaque token<0..2^16-1>; 352 uint8 V<20>; 353 uint8 solution<0..2^16-1>; 354 } BirthdayPuzzleResponse; 356 token The token allows the server to encapsulate and drop state, and 357 also acts as a cookie for DTLS. During an initial ClientHello, 358 this MUST be empty (zero-length). During HelloRetryRequest, the 359 server MAY send a token challenge of zero or more bytes. During 360 the retried ClientHello, the client MUST respond by resending the 361 identical token sent in the HelloRetryRequest. Servers MAY 362 included an authenticated version of n, k, difficulty and salt in 363 this token if they wish to be stateless. 365 salt A server selected variable-length bytestring. 367 n, k parameters affecting the complexity of Wagner's algorithm. 369 difficulty secondary filter affecting the time to find solution. 371 V 20 byte nonce used in solution. 373 solution list of 2^k (n/(k+1)+1)-bit nonces used in solution, 374 referred to as xi below. 376 In the further text, the output of blake2b is treated as a 512-bit 377 register with most significant bits coming from the last bytes of 378 blake2b output (i.e. little-endian conversion). 380 To compute the response, the client must find a V and 2^k solutions 381 such that: 383 blake2b(salt||V||x1) XOR blake2b(salt||V||x2) XOR ... XOR 384 blake2b(I||V||x(2^k)) = 0 385 blake2b(label||salt||V||x1||x2||...||x(2^k)) has difficulty leading 386 zero bits. 388 where "||" denotes concatenation and where label is the NUL- 389 terminated value "TLS BirthdayPuzzle" (including the NUL terminator). 390 Incomplete bytes in nonces xi are padded with zero bits, which occupy 391 the most significant bits. 393 The client MUST provide the solution list in an order that allows a 394 server to verify the solution was created using Wagner's algorithm: 396 blake2b(salt||V||x(w_2^l+1)) XOR blake2b(salt||V||x(w_2^l+2)) XOR ... 397 XOR blake2b(I||V||x(w*2^l+2^l)) has nl/(k+1) leading zero bits for 398 all w,l. 400 and two 2^(l-1)(n/(k+1)+1)-bit numbers Z1 and Z2 must satisfy Z1. 508 [RFC5754] Turner, S., "Using SHA2 Algorithms with Cryptographic 509 Message Syntax", RFC 5754, DOI 10.17487/RFC5754, January 510 2010, . 512 10.2. Informative References 514 [DN92] Dwork, C. and M. Naor, "Pricing via Processing or 515 Combatting Junk Mail", Proceedings of Crypto'92 , 1992, 516 . 519 [I-D.ietf-ipsecme-ddos-protection] 520 Nir, Y. and V. Smyslov, "Protecting Internet Key Exchange 521 Protocol version 2 (IKEv2) Implementations from 522 Distributed Denial of Service Attacks", draft-ietf- 523 ipsecme-ddos-protection-06 (work in progress), April 2016. 525 [I-D.josefsson-scrypt-kdf] 526 Percival, C. and S. Josefsson, "The scrypt Password-Based 527 Key Derivation Function", draft-josefsson-scrypt-kdf-05 528 (work in progress), May 2016. 530 [I-D.nir-tls-puzzles] 531 Nir, Y., "Using Client Puzzles to Protect TLS Servers From 532 Denial of Service Attacks", draft-nir-tls-puzzles-00 (work 533 in progress), April 2014. 535 [JB99] Juels, A. and J. Brainard, "Client Puzzles: A 536 Cryptographic Defense Against Connection Depletion 537 Attacks", Proceedings of NDSS'99 , 1999, 538 . 541 [NDSS2016] 542 Biryukov, A. and D. Khovratovich, "Equihash: Asymmetric 543 proof-of-work based on the Generalized Birthday problem", 544 February 2016, 545 . 549 [SEC2001.DEAN] 550 Dean, D. and A. Stubblefield, "Using Client Puzzles to 551 Protect TLS", Proceedings of the 10th USENIX Security 552 Symposium , August 2001, 553 . 556 Authors' Addresses 558 Erik Nygren 559 Akamai Technologies 561 EMail: erik+ietf@nygren.org 562 URI: http://erik.nygren.org/ 564 Samuel Erb 565 Akamai Technologies 567 EMail: serb@akamai.com 569 Alex Biryukov 570 University of Luxembourg 572 EMail: alex.biryukov@uni.lu 574 Dmitry Khovratovich 575 University of Luxembourg 577 EMail: khovratovich@gmail.com 579 Ari Juels 580 Cornell University 582 EMail: juels@cornell.edu